]>
Commit | Line | Data |
---|---|---|
d02b48c6 | 1 | /* crypto/bn/bn_prime.c */ |
58964a49 | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
d02b48c6 RE |
3 | * All rights reserved. |
4 | * | |
5 | * This package is an SSL implementation written | |
6 | * by Eric Young (eay@cryptsoft.com). | |
7 | * The implementation was written so as to conform with Netscapes SSL. | |
8 | * | |
9 | * This library is free for commercial and non-commercial use as long as | |
10 | * the following conditions are aheared to. The following conditions | |
11 | * apply to all code found in this distribution, be it the RC4, RSA, | |
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | |
13 | * included with this distribution is covered by the same copyright terms | |
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | |
15 | * | |
16 | * Copyright remains Eric Young's, and as such any Copyright notices in | |
17 | * the code are not to be removed. | |
18 | * If this package is used in a product, Eric Young should be given attribution | |
19 | * as the author of the parts of the library used. | |
20 | * This can be in the form of a textual message at program startup or | |
21 | * in documentation (online or textual) provided with the package. | |
22 | * | |
23 | * Redistribution and use in source and binary forms, with or without | |
24 | * modification, are permitted provided that the following conditions | |
25 | * are met: | |
26 | * 1. Redistributions of source code must retain the copyright | |
27 | * notice, this list of conditions and the following disclaimer. | |
28 | * 2. Redistributions in binary form must reproduce the above copyright | |
29 | * notice, this list of conditions and the following disclaimer in the | |
30 | * documentation and/or other materials provided with the distribution. | |
31 | * 3. All advertising materials mentioning features or use of this software | |
32 | * must display the following acknowledgement: | |
33 | * "This product includes cryptographic software written by | |
34 | * Eric Young (eay@cryptsoft.com)" | |
35 | * The word 'cryptographic' can be left out if the rouines from the library | |
36 | * being used are not cryptographic related :-). | |
37 | * 4. If you include any Windows specific code (or a derivative thereof) from | |
38 | * the apps directory (application code) you must include an acknowledgement: | |
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | |
40 | * | |
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | |
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
51 | * SUCH DAMAGE. | |
52 | * | |
53 | * The licence and distribution terms for any publically available version or | |
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | |
55 | * copied and put under another distribution licence | |
56 | * [including the GNU Public Licence.] | |
57 | */ | |
58 | ||
59 | #include <stdio.h> | |
60 | #include <time.h> | |
61 | #include "cryptlib.h" | |
62 | #include "bn_lcl.h" | |
ec577822 | 63 | #include <openssl/rand.h> |
d02b48c6 RE |
64 | |
65 | /* The quick seive algorithm approach to weeding out primes is | |
66 | * Philip Zimmermann's, as implemented in PGP. I have had a read of | |
67 | * his comments and implemented my own version. | |
68 | */ | |
69 | #include "bn_prime.h" | |
70 | ||
58964a49 RE |
71 | static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2, |
72 | BN_MONT_CTX *mont); | |
d02b48c6 RE |
73 | static int probable_prime(BIGNUM *rnd, int bits); |
74 | static int probable_prime_dh(BIGNUM *rnd, int bits, | |
75 | BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); | |
76aa0ddc | 76 | static int probable_prime_dh_safe(BIGNUM *rnd, int bits, |
d02b48c6 | 77 | BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); |
eb952088 | 78 | |
76aa0ddc | 79 | BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, BIGNUM *add, |
b4f76582 | 80 | BIGNUM *rem, void (*callback)(int,int,void *), void *cb_arg) |
d02b48c6 RE |
81 | { |
82 | BIGNUM *rnd=NULL; | |
dfeab068 | 83 | BIGNUM t; |
d02b48c6 RE |
84 | int i,j,c1=0; |
85 | BN_CTX *ctx; | |
76aa0ddc | 86 | int checks = BN_prime_checks(bits); |
d02b48c6 RE |
87 | |
88 | ctx=BN_CTX_new(); | |
89 | if (ctx == NULL) goto err; | |
dfeab068 RE |
90 | if (ret == NULL) |
91 | { | |
92 | if ((rnd=BN_new()) == NULL) goto err; | |
93 | } | |
94 | else | |
95 | rnd=ret; | |
96 | BN_init(&t); | |
d02b48c6 RE |
97 | loop: |
98 | /* make a random number and set the top and bottom bits */ | |
99 | if (add == NULL) | |
100 | { | |
101 | if (!probable_prime(rnd,bits)) goto err; | |
102 | } | |
103 | else | |
104 | { | |
76aa0ddc | 105 | if (safe) |
d02b48c6 | 106 | { |
76aa0ddc | 107 | if (!probable_prime_dh_safe(rnd,bits,add,rem,ctx)) |
d02b48c6 RE |
108 | goto err; |
109 | } | |
110 | else | |
111 | { | |
112 | if (!probable_prime_dh(rnd,bits,add,rem,ctx)) | |
113 | goto err; | |
114 | } | |
115 | } | |
116 | /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */ | |
58964a49 | 117 | if (callback != NULL) callback(0,c1++,cb_arg); |
d02b48c6 | 118 | |
76aa0ddc | 119 | if (!safe) |
d02b48c6 | 120 | { |
76aa0ddc | 121 | i=BN_is_prime(rnd,checks,callback,ctx,cb_arg); |
d02b48c6 RE |
122 | if (i == -1) goto err; |
123 | if (i == 0) goto loop; | |
124 | } | |
125 | else | |
126 | { | |
76aa0ddc | 127 | /* for "safe prime" generation, |
d02b48c6 RE |
128 | * check that (p-1)/2 is prime. |
129 | * Since a prime is odd, We just | |
130 | * need to divide by 2 */ | |
dfeab068 | 131 | if (!BN_rshift1(&t,rnd)) goto err; |
d02b48c6 | 132 | |
76aa0ddc | 133 | for (i=0; i<checks; i++) |
d02b48c6 | 134 | { |
58964a49 | 135 | j=BN_is_prime(rnd,1,callback,ctx,cb_arg); |
d02b48c6 RE |
136 | if (j == -1) goto err; |
137 | if (j == 0) goto loop; | |
138 | ||
dfeab068 | 139 | j=BN_is_prime(&t,1,callback,ctx,cb_arg); |
d02b48c6 RE |
140 | if (j == -1) goto err; |
141 | if (j == 0) goto loop; | |
142 | ||
58964a49 | 143 | if (callback != NULL) callback(2,c1-1,cb_arg); |
76aa0ddc | 144 | /* We have a safe prime test pass */ |
d02b48c6 RE |
145 | } |
146 | } | |
147 | /* we have a prime :-) */ | |
148 | ret=rnd; | |
149 | err: | |
150 | if ((ret == NULL) && (rnd != NULL)) BN_free(rnd); | |
dfeab068 | 151 | BN_free(&t); |
d02b48c6 RE |
152 | if (ctx != NULL) BN_CTX_free(ctx); |
153 | return(ret); | |
154 | } | |
155 | ||
b4f76582 BL |
156 | int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *), |
157 | BN_CTX *ctx_passed, void *cb_arg) | |
d02b48c6 RE |
158 | { |
159 | int i,j,c2=0,ret= -1; | |
160 | BIGNUM *check; | |
58964a49 RE |
161 | BN_CTX *ctx=NULL,*ctx2=NULL; |
162 | BN_MONT_CTX *mont=NULL; | |
d02b48c6 | 163 | |
58964a49 RE |
164 | if (!BN_is_odd(a)) |
165 | return(0); | |
d02b48c6 RE |
166 | if (ctx_passed != NULL) |
167 | ctx=ctx_passed; | |
168 | else | |
169 | if ((ctx=BN_CTX_new()) == NULL) goto err; | |
170 | ||
58964a49 RE |
171 | if ((ctx2=BN_CTX_new()) == NULL) goto err; |
172 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | |
173 | ||
dfeab068 | 174 | check= &(ctx->bn[ctx->tos++]); |
58964a49 RE |
175 | |
176 | /* Setup the montgomery structure */ | |
177 | if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err; | |
178 | ||
d02b48c6 RE |
179 | for (i=0; i<checks; i++) |
180 | { | |
181 | if (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err; | |
58964a49 | 182 | j=witness(check,a,ctx,ctx2,mont); |
d02b48c6 RE |
183 | if (j == -1) goto err; |
184 | if (j) | |
185 | { | |
186 | ret=0; | |
187 | goto err; | |
188 | } | |
58964a49 | 189 | if (callback != NULL) callback(1,c2++,cb_arg); |
d02b48c6 RE |
190 | } |
191 | ret=1; | |
192 | err: | |
193 | ctx->tos--; | |
194 | if ((ctx_passed == NULL) && (ctx != NULL)) | |
195 | BN_CTX_free(ctx); | |
58964a49 RE |
196 | if (ctx2 != NULL) |
197 | BN_CTX_free(ctx2); | |
198 | if (mont != NULL) BN_MONT_CTX_free(mont); | |
d02b48c6 RE |
199 | |
200 | return(ret); | |
201 | } | |
202 | ||
203 | #define RECP_MUL_MOD | |
204 | ||
6b691a5c UM |
205 | static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2, |
206 | BN_MONT_CTX *mont) | |
d02b48c6 | 207 | { |
58964a49 RE |
208 | int k,i,ret= -1,good; |
209 | BIGNUM *d,*dd,*tmp,*d1,*d2,*n1; | |
210 | BIGNUM *mont_one,*mont_n1,*mont_a; | |
d02b48c6 | 211 | |
dfeab068 RE |
212 | d1= &(ctx->bn[ctx->tos]); |
213 | d2= &(ctx->bn[ctx->tos+1]); | |
214 | n1= &(ctx->bn[ctx->tos+2]); | |
58964a49 RE |
215 | ctx->tos+=3; |
216 | ||
dfeab068 RE |
217 | mont_one= &(ctx2->bn[ctx2->tos]); |
218 | mont_n1= &(ctx2->bn[ctx2->tos+1]); | |
219 | mont_a= &(ctx2->bn[ctx2->tos+2]); | |
58964a49 | 220 | ctx2->tos+=3; |
d02b48c6 RE |
221 | |
222 | d=d1; | |
223 | dd=d2; | |
224 | if (!BN_one(d)) goto err; | |
225 | if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ | |
226 | k=BN_num_bits(n1); | |
227 | ||
58964a49 RE |
228 | if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err; |
229 | if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err; | |
230 | if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err; | |
d02b48c6 | 231 | |
58964a49 | 232 | BN_copy(d,mont_one); |
d02b48c6 RE |
233 | for (i=k-1; i>=0; i--) |
234 | { | |
58964a49 RE |
235 | if ( (BN_cmp(d,mont_one) != 0) && |
236 | (BN_cmp(d,mont_n1) != 0)) | |
237 | good=1; | |
238 | else | |
239 | good=0; | |
240 | ||
241 | BN_mod_mul_montgomery(dd,d,d,mont,ctx2); | |
4f9b306c | 242 | |
58964a49 | 243 | if (good && (BN_cmp(dd,mont_one) == 0)) |
d02b48c6 RE |
244 | { |
245 | ret=1; | |
246 | goto err; | |
247 | } | |
248 | if (BN_is_bit_set(n1,i)) | |
249 | { | |
58964a49 | 250 | BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2); |
d02b48c6 RE |
251 | } |
252 | else | |
253 | { | |
254 | tmp=d; | |
255 | d=dd; | |
256 | dd=tmp; | |
257 | } | |
258 | } | |
58964a49 | 259 | if (BN_cmp(d,mont_one) == 0) |
d02b48c6 RE |
260 | i=0; |
261 | else i=1; | |
262 | ret=i; | |
263 | err: | |
58964a49 RE |
264 | ctx->tos-=3; |
265 | ctx2->tos-=3; | |
d02b48c6 RE |
266 | return(ret); |
267 | } | |
268 | ||
6b691a5c | 269 | static int probable_prime(BIGNUM *rnd, int bits) |
d02b48c6 RE |
270 | { |
271 | int i; | |
272 | MS_STATIC BN_ULONG mods[NUMPRIMES]; | |
dfeab068 | 273 | BN_ULONG delta,d; |
d02b48c6 | 274 | |
dfeab068 | 275 | again: |
d02b48c6 RE |
276 | if (!BN_rand(rnd,bits,1,1)) return(0); |
277 | /* we now have a random number 'rand' to test. */ | |
278 | for (i=1; i<NUMPRIMES; i++) | |
279 | mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]); | |
280 | delta=0; | |
281 | loop: for (i=1; i<NUMPRIMES; i++) | |
282 | { | |
283 | /* check that rnd is not a prime and also | |
284 | * that gcd(rnd-1,primes) == 1 (except for 2) */ | |
285 | if (((mods[i]+delta)%primes[i]) <= 1) | |
286 | { | |
dfeab068 | 287 | d=delta; |
d02b48c6 RE |
288 | delta+=2; |
289 | /* perhaps need to check for overflow of | |
dfeab068 RE |
290 | * delta (but delta can be upto 2^32) |
291 | * 21-May-98 eay - added overflow check */ | |
292 | if (delta < d) goto again; | |
d02b48c6 RE |
293 | goto loop; |
294 | } | |
295 | } | |
296 | if (!BN_add_word(rnd,delta)) return(0); | |
297 | return(1); | |
298 | } | |
299 | ||
6b691a5c UM |
300 | static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem, |
301 | BN_CTX *ctx) | |
d02b48c6 RE |
302 | { |
303 | int i,ret=0; | |
304 | BIGNUM *t1; | |
305 | ||
dfeab068 | 306 | t1= &(ctx->bn[ctx->tos++]); |
d02b48c6 RE |
307 | |
308 | if (!BN_rand(rnd,bits,0,1)) goto err; | |
309 | ||
310 | /* we need ((rnd-rem) % add) == 0 */ | |
311 | ||
312 | if (!BN_mod(t1,rnd,add,ctx)) goto err; | |
313 | if (!BN_sub(rnd,rnd,t1)) goto err; | |
314 | if (rem == NULL) | |
315 | { if (!BN_add_word(rnd,1)) goto err; } | |
316 | else | |
317 | { if (!BN_add(rnd,rnd,rem)) goto err; } | |
318 | ||
319 | /* we now have a random number 'rand' to test. */ | |
320 | ||
321 | loop: for (i=1; i<NUMPRIMES; i++) | |
322 | { | |
323 | /* check that rnd is a prime */ | |
e14d4443 | 324 | if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1) |
d02b48c6 RE |
325 | { |
326 | if (!BN_add(rnd,rnd,add)) goto err; | |
327 | goto loop; | |
328 | } | |
329 | } | |
330 | ret=1; | |
331 | err: | |
332 | ctx->tos--; | |
333 | return(ret); | |
334 | } | |
335 | ||
76aa0ddc | 336 | static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd, |
6b691a5c | 337 | BIGNUM *rem, BN_CTX *ctx) |
d02b48c6 RE |
338 | { |
339 | int i,ret=0; | |
340 | BIGNUM *t1,*qadd=NULL,*q=NULL; | |
341 | ||
342 | bits--; | |
dfeab068 RE |
343 | t1= &(ctx->bn[ctx->tos++]); |
344 | q= &(ctx->bn[ctx->tos++]); | |
345 | qadd= &(ctx->bn[ctx->tos++]); | |
d02b48c6 RE |
346 | |
347 | if (!BN_rshift1(qadd,padd)) goto err; | |
348 | ||
349 | if (!BN_rand(q,bits,0,1)) goto err; | |
350 | ||
351 | /* we need ((rnd-rem) % add) == 0 */ | |
352 | if (!BN_mod(t1,q,qadd,ctx)) goto err; | |
353 | if (!BN_sub(q,q,t1)) goto err; | |
354 | if (rem == NULL) | |
355 | { if (!BN_add_word(q,1)) goto err; } | |
356 | else | |
357 | { | |
358 | if (!BN_rshift1(t1,rem)) goto err; | |
359 | if (!BN_add(q,q,t1)) goto err; | |
360 | } | |
361 | ||
362 | /* we now have a random number 'rand' to test. */ | |
363 | if (!BN_lshift1(p,q)) goto err; | |
364 | if (!BN_add_word(p,1)) goto err; | |
365 | ||
366 | loop: for (i=1; i<NUMPRIMES; i++) | |
367 | { | |
368 | /* check that p and q are prime */ | |
369 | /* check that for p and q | |
370 | * gcd(p-1,primes) == 1 (except for 2) */ | |
e14d4443 UM |
371 | if ( (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) || |
372 | (BN_mod_word(q,(BN_ULONG)primes[i]) == 0)) | |
d02b48c6 RE |
373 | { |
374 | if (!BN_add(p,p,padd)) goto err; | |
375 | if (!BN_add(q,q,qadd)) goto err; | |
376 | goto loop; | |
377 | } | |
378 | } | |
379 | ret=1; | |
380 | err: | |
381 | ctx->tos-=3; | |
382 | return(ret); | |
383 | } | |
384 | ||
58964a49 | 385 | #if 0 |
6b691a5c | 386 | static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx) |
58964a49 RE |
387 | { |
388 | int k,i,nb,ret= -1; | |
389 | BIGNUM *d,*dd,*tmp; | |
390 | BIGNUM *d1,*d2,*x,*n1,*inv; | |
391 | ||
dfeab068 RE |
392 | d1= &(ctx->bn[ctx->tos]); |
393 | d2= &(ctx->bn[ctx->tos+1]); | |
394 | x= &(ctx->bn[ctx->tos+2]); | |
395 | n1= &(ctx->bn[ctx->tos+3]); | |
396 | inv=&(ctx->bn[ctx->tos+4]); | |
58964a49 RE |
397 | ctx->tos+=5; |
398 | ||
399 | d=d1; | |
400 | dd=d2; | |
401 | if (!BN_one(d)) goto err; | |
402 | if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ | |
403 | k=BN_num_bits(n1); | |
404 | ||
405 | /* i=BN_num_bits(n); */ | |
406 | #ifdef RECP_MUL_MOD | |
407 | nb=BN_reciprocal(inv,n,ctx); /**/ | |
408 | if (nb == -1) goto err; | |
409 | #endif | |
410 | ||
411 | for (i=k-1; i>=0; i--) | |
412 | { | |
413 | if (BN_copy(x,d) == NULL) goto err; | |
414 | #ifndef RECP_MUL_MOD | |
415 | if (!BN_mod_mul(dd,d,d,n,ctx)) goto err; | |
416 | #else | |
417 | if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err; | |
418 | #endif | |
419 | if ( BN_is_one(dd) && | |
420 | !BN_is_one(x) && | |
421 | (BN_cmp(x,n1) != 0)) | |
422 | { | |
423 | ret=1; | |
424 | goto err; | |
425 | } | |
426 | if (BN_is_bit_set(n1,i)) | |
427 | { | |
428 | #ifndef RECP_MUL_MOD | |
429 | if (!BN_mod_mul(d,dd,a,n,ctx)) goto err; | |
430 | #else | |
431 | if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err; | |
432 | #endif | |
433 | } | |
434 | else | |
435 | { | |
436 | tmp=d; | |
437 | d=dd; | |
438 | dd=tmp; | |
439 | } | |
440 | } | |
441 | if (BN_is_one(d)) | |
442 | i=0; | |
443 | else i=1; | |
444 | ret=i; | |
445 | err: | |
446 | ctx->tos-=5; | |
447 | return(ret); | |
448 | } | |
449 | #endif |