summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/dsa/dsa_gen.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/dsa/dsa_gen.c')
-rw-r--r--src/lib/libcrypto/dsa/dsa_gen.c220
1 files changed, 94 insertions, 126 deletions
diff --git a/src/lib/libcrypto/dsa/dsa_gen.c b/src/lib/libcrypto/dsa/dsa_gen.c
index d7d30bf90a..dc9c249310 100644
--- a/src/lib/libcrypto/dsa/dsa_gen.c
+++ b/src/lib/libcrypto/dsa/dsa_gen.c
@@ -59,28 +59,32 @@
59#undef GENUINE_DSA 59#undef GENUINE_DSA
60 60
61#ifdef GENUINE_DSA 61#ifdef GENUINE_DSA
62#define HASH SHA 62/* Parameter generation follows the original release of FIPS PUB 186,
63 * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) */
64#define HASH EVP_sha()
63#else 65#else
64#define HASH SHA1 66/* Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
67 * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in
68 * FIPS PUB 180-1) */
69#define HASH EVP_sha1()
65#endif 70#endif
66 71
72#ifndef OPENSSL_NO_SHA
73
67#include <stdio.h> 74#include <stdio.h>
68#include <time.h> 75#include <time.h>
69#include "cryptlib.h" 76#include "cryptlib.h"
70#include "sha.h" 77#include <openssl/evp.h>
71#include "bn.h" 78#include <openssl/bn.h>
72#include "dsa.h" 79#include <openssl/dsa.h>
73#include "rand.h" 80#include <openssl/rand.h>
74 81#include <openssl/sha.h>
75DSA *DSA_generate_parameters(bits,seed_in,seed_len,counter_ret,h_ret,callback, 82
76 cb_arg) 83DSA *DSA_generate_parameters(int bits,
77int bits; 84 unsigned char *seed_in, int seed_len,
78unsigned char *seed_in; 85 int *counter_ret, unsigned long *h_ret,
79int seed_len; 86 void (*callback)(int, int, void *),
80int *counter_ret; 87 void *cb_arg)
81unsigned long *h_ret;
82void (*callback)();
83char *cb_arg;
84 { 88 {
85 int ok=0; 89 int ok=0;
86 unsigned char seed[SHA_DIGEST_LENGTH]; 90 unsigned char seed[SHA_DIGEST_LENGTH];
@@ -88,49 +92,66 @@ char *cb_arg;
88 unsigned char buf[SHA_DIGEST_LENGTH],buf2[SHA_DIGEST_LENGTH]; 92 unsigned char buf[SHA_DIGEST_LENGTH],buf2[SHA_DIGEST_LENGTH];
89 BIGNUM *r0,*W,*X,*c,*test; 93 BIGNUM *r0,*W,*X,*c,*test;
90 BIGNUM *g=NULL,*q=NULL,*p=NULL; 94 BIGNUM *g=NULL,*q=NULL,*p=NULL;
95 BN_MONT_CTX *mont=NULL;
91 int k,n=0,i,b,m=0; 96 int k,n=0,i,b,m=0;
92 int counter=0; 97 int counter=0;
93 BN_CTX *ctx=NULL,*ctx2=NULL; 98 int r=0;
99 BN_CTX *ctx=NULL,*ctx2=NULL,*ctx3=NULL;
94 unsigned int h=2; 100 unsigned int h=2;
95 DSA *ret=NULL; 101 DSA *ret=NULL;
96 102
97 if (bits < 512) bits=512; 103 if (bits < 512) bits=512;
98 bits=(bits+63)/64*64; 104 bits=(bits+63)/64*64;
99 105
106 if (seed_len < 20)
107 seed_in = NULL; /* seed buffer too small -- ignore */
108 if (seed_len > 20)
109 seed_len = 20; /* App. 2.2 of FIPS PUB 186 allows larger SEED,
110 * but our internal buffers are restricted to 160 bits*/
100 if ((seed_in != NULL) && (seed_len == 20)) 111 if ((seed_in != NULL) && (seed_len == 20))
101 memcpy(seed,seed_in,seed_len); 112 memcpy(seed,seed_in,seed_len);
102 113
103 ctx=BN_CTX_new(); 114 if ((ctx=BN_CTX_new()) == NULL) goto err;
104 if (ctx == NULL) goto err; 115 if ((ctx2=BN_CTX_new()) == NULL) goto err;
105 ctx2=BN_CTX_new(); 116 if ((ctx3=BN_CTX_new()) == NULL) goto err;
106 if (ctx2 == NULL) goto err; 117 if ((ret=DSA_new()) == NULL) goto err;
107 ret=DSA_new(); 118
108 if (ret == NULL) goto err; 119 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
109 r0=ctx2->bn[0]; 120
110 g=ctx2->bn[1]; 121 BN_CTX_start(ctx2);
111 W=ctx2->bn[2]; 122 r0 = BN_CTX_get(ctx2);
112 q=ctx2->bn[3]; 123 g = BN_CTX_get(ctx2);
113 X=ctx2->bn[4]; 124 W = BN_CTX_get(ctx2);
114 c=ctx2->bn[5]; 125 q = BN_CTX_get(ctx2);
115 p=ctx2->bn[6]; 126 X = BN_CTX_get(ctx2);
116 test=ctx2->bn[7]; 127 c = BN_CTX_get(ctx2);
128 p = BN_CTX_get(ctx2);
129 test = BN_CTX_get(ctx2);
117 130
118 BN_lshift(test,BN_value_one(),bits-1); 131 BN_lshift(test,BN_value_one(),bits-1);
119 132
120 for (;;) 133 for (;;)
121 { 134 {
122 for (;;) 135 for (;;) /* find q */
123 { 136 {
137 int seed_is_random;
138
124 /* step 1 */ 139 /* step 1 */
125 if (callback != NULL) callback(0,m++,cb_arg); 140 if (callback != NULL) callback(0,m++,cb_arg);
126 141
127 if (!seed_len) 142 if (!seed_len)
128 RAND_bytes(seed,SHA_DIGEST_LENGTH); 143 {
144 RAND_pseudo_bytes(seed,SHA_DIGEST_LENGTH);
145 seed_is_random = 1;
146 }
129 else 147 else
130 seed_len=0; 148 {
131 149 seed_is_random = 0;
150 seed_len=0; /* use random seed if 'seed_in' turns out to be bad*/
151 }
132 memcpy(buf,seed,SHA_DIGEST_LENGTH); 152 memcpy(buf,seed,SHA_DIGEST_LENGTH);
133 memcpy(buf2,seed,SHA_DIGEST_LENGTH); 153 memcpy(buf2,seed,SHA_DIGEST_LENGTH);
154 /* precompute "SEED + 1" for step 7: */
134 for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--) 155 for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
135 { 156 {
136 buf[i]++; 157 buf[i]++;
@@ -138,18 +159,23 @@ char *cb_arg;
138 } 159 }
139 160
140 /* step 2 */ 161 /* step 2 */
141 HASH(seed,SHA_DIGEST_LENGTH,md); 162 EVP_Digest(seed,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
142 HASH(buf,SHA_DIGEST_LENGTH,buf2); 163 EVP_Digest(buf,SHA_DIGEST_LENGTH,buf2,NULL,HASH, NULL);
143 for (i=0; i<SHA_DIGEST_LENGTH; i++) 164 for (i=0; i<SHA_DIGEST_LENGTH; i++)
144 md[i]^=buf2[i]; 165 md[i]^=buf2[i];
145 166
146 /* step 3 */ 167 /* step 3 */
147 md[0]|=0x80; 168 md[0]|=0x80;
148 md[SHA_DIGEST_LENGTH-1]|=0x01; 169 md[SHA_DIGEST_LENGTH-1]|=0x01;
149 if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,q)) abort(); 170 if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,q)) goto err;
150 171
151 /* step 4 */ 172 /* step 4 */
152 if (DSA_is_prime(q,callback,cb_arg) > 0) break; 173 r = BN_is_prime_fasttest(q, DSS_prime_checks, callback, ctx3, cb_arg, seed_is_random);
174 if (r > 0)
175 break;
176 if (r != 0)
177 goto err;
178
153 /* do a callback call */ 179 /* do a callback call */
154 /* step 5 */ 180 /* step 5 */
155 } 181 }
@@ -159,26 +185,33 @@ char *cb_arg;
159 185
160 /* step 6 */ 186 /* step 6 */
161 counter=0; 187 counter=0;
188 /* "offset = 2" */
162 189
163 n=(bits-1)/160; 190 n=(bits-1)/160;
164 b=(bits-1)-n*160; 191 b=(bits-1)-n*160;
165 192
166 for (;;) 193 for (;;)
167 { 194 {
195 if (callback != NULL && counter != 0)
196 callback(0,counter,cb_arg);
197
168 /* step 7 */ 198 /* step 7 */
169 BN_zero(W); 199 BN_zero(W);
200 /* now 'buf' contains "SEED + offset - 1" */
170 for (k=0; k<=n; k++) 201 for (k=0; k<=n; k++)
171 { 202 {
203 /* obtain "SEED + offset + k" by incrementing: */
172 for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--) 204 for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
173 { 205 {
174 buf[i]++; 206 buf[i]++;
175 if (buf[i] != 0) break; 207 if (buf[i] != 0) break;
176 } 208 }
177 209
178 HASH(buf,SHA_DIGEST_LENGTH,md); 210 EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
179 211
180 /* step 8 */ 212 /* step 8 */
181 if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0)) abort(); 213 if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))
214 goto err;
182 BN_lshift(r0,r0,160*k); 215 BN_lshift(r0,r0,160*k);
183 BN_add(W,W,r0); 216 BN_add(W,W,r0);
184 } 217 }
@@ -198,32 +231,36 @@ char *cb_arg;
198 if (BN_cmp(p,test) >= 0) 231 if (BN_cmp(p,test) >= 0)
199 { 232 {
200 /* step 11 */ 233 /* step 11 */
201 if (DSA_is_prime(p,callback,cb_arg) > 0) 234 r = BN_is_prime_fasttest(p, DSS_prime_checks, callback, ctx3, cb_arg, 1);
202 goto end; 235 if (r > 0)
236 goto end; /* found it */
237 if (r != 0)
238 goto err;
203 } 239 }
204 240
205 /* step 13 */ 241 /* step 13 */
206 counter++; 242 counter++;
243 /* "offset = offset + n + 1" */
207 244
208 /* step 14 */ 245 /* step 14 */
209 if (counter >= 4096) break; 246 if (counter >= 4096) break;
210
211 if (callback != NULL) callback(0,counter,cb_arg);
212 } 247 }
213 } 248 }
214end: 249end:
215 if (callback != NULL) callback(2,1,cb_arg); 250 if (callback != NULL) callback(2,1,cb_arg);
216 251
217 /* We now need to gernerate g */ 252 /* We now need to generate g */
218 /* Set r0=(p-1)/q */ 253 /* Set r0=(p-1)/q */
219 BN_sub(test,p,BN_value_one()); 254 BN_sub(test,p,BN_value_one());
220 BN_div(r0,NULL,test,q,ctx); 255 BN_div(r0,NULL,test,q,ctx);
221 256
222 BN_set_word(test,h); 257 BN_set_word(test,h);
258 BN_MONT_CTX_set(mont,p,ctx);
259
223 for (;;) 260 for (;;)
224 { 261 {
225 /* g=test^r0%p */ 262 /* g=test^r0%p */
226 BN_mod_exp(g,test,r0,p,ctx); 263 BN_mod_exp_mont(g,test,r0,p,ctx,mont);
227 if (!BN_is_one(g)) break; 264 if (!BN_is_one(g)) break;
228 BN_add(test,test,BN_value_one()); 265 BN_add(test,test,BN_value_one());
229 h++; 266 h++;
@@ -246,83 +283,14 @@ err:
246 if (counter_ret != NULL) *counter_ret=counter; 283 if (counter_ret != NULL) *counter_ret=counter;
247 if (h_ret != NULL) *h_ret=h; 284 if (h_ret != NULL) *h_ret=h;
248 } 285 }
249 BN_CTX_free(ctx); 286 if (ctx != NULL) BN_CTX_free(ctx);
250 BN_CTX_free(ctx2); 287 if (ctx2 != NULL)
251 return(ok?ret:NULL);
252 }
253
254int DSA_is_prime(w, callback,cb_arg)
255BIGNUM *w;
256void (*callback)();
257char *cb_arg;
258 {
259 int ok= -1,j,i,n;
260 BN_CTX *ctx=NULL,*ctx2=NULL;
261 BIGNUM *w_1,*b,*m,*z;
262 int a;
263
264 if (!BN_is_bit_set(w,0)) return(0);
265
266 ctx=BN_CTX_new();
267 if (ctx == NULL) goto err;
268 ctx2=BN_CTX_new();
269 if (ctx2 == NULL) goto err;
270
271 m= ctx2->bn[2];
272 b= ctx2->bn[3];
273 z= ctx2->bn[4];
274 w_1=ctx2->bn[5];
275
276 /* step 1 */
277 n=50;
278
279 /* step 2 */
280 if (!BN_sub(w_1,w,BN_value_one())) goto err;
281 for (a=1; !BN_is_bit_set(w_1,a); a++)
282 ;
283 if (!BN_rshift(m,w_1,a)) goto err;
284
285 for (i=1; i < n; i++)
286 { 288 {
287 /* step 3 */ 289 BN_CTX_end(ctx2);
288 BN_rand(b,BN_num_bits(w)-2/*-1*/,0,0); 290 BN_CTX_free(ctx2);
289 BN_set_word(b,0x10001L);
290
291 /* step 4 */
292 j=0;
293 if (!BN_mod_exp(z,b,m,w,ctx)) goto err;
294
295 /* step 5 */
296 for (;;)
297 {
298 if (((j == 0) && BN_is_one(z)) || (BN_cmp(z,w_1) == 0))
299 break;
300
301 /* step 6 */
302 if ((j > 0) && BN_is_one(z))
303 {
304 ok=0;
305 goto err;
306 }
307
308 j++;
309 if (j >= a)
310 {
311 ok=0;
312 goto err;
313 }
314
315 if (!BN_mod_mul(z,z,z,w,ctx)) goto err;
316 if (callback != NULL) callback(1,j,cb_arg);
317 }
318 } 291 }
319 292 if (ctx3 != NULL) BN_CTX_free(ctx3);
320 ok=1; 293 if (mont != NULL) BN_MONT_CTX_free(mont);
321err: 294 return(ok?ret:NULL);
322 if (ok == -1) DSAerr(DSA_F_DSA_IS_PRIME,ERR_R_BN_LIB);
323 BN_CTX_free(ctx);
324 BN_CTX_free(ctx2);
325
326 return(ok);
327 } 295 }
328 296#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-10-25 01:12:07 +0000