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