]>
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 | */ | |
bfe30e4d | 58 | /* ==================================================================== |
435037d4 | 59 | * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. |
bfe30e4d BM |
60 | * |
61 | * Redistribution and use in source and binary forms, with or without | |
62 | * modification, are permitted provided that the following conditions | |
63 | * are met: | |
64 | * | |
65 | * 1. Redistributions of source code must retain the above copyright | |
66 | * notice, this list of conditions and the following disclaimer. | |
67 | * | |
68 | * 2. Redistributions in binary form must reproduce the above copyright | |
69 | * notice, this list of conditions and the following disclaimer in | |
70 | * the documentation and/or other materials provided with the | |
71 | * distribution. | |
72 | * | |
73 | * 3. All advertising materials mentioning features or use of this | |
74 | * software must display the following acknowledgment: | |
75 | * "This product includes software developed by the OpenSSL Project | |
76 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | |
77 | * | |
78 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
79 | * endorse or promote products derived from this software without | |
80 | * prior written permission. For written permission, please contact | |
81 | * openssl-core@openssl.org. | |
82 | * | |
83 | * 5. Products derived from this software may not be called "OpenSSL" | |
84 | * nor may "OpenSSL" appear in their names without prior written | |
85 | * permission of the OpenSSL Project. | |
86 | * | |
87 | * 6. Redistributions of any form whatsoever must retain the following | |
88 | * acknowledgment: | |
89 | * "This product includes software developed by the OpenSSL Project | |
90 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | |
91 | * | |
92 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
93 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
94 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
95 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
96 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
97 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
98 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
99 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
100 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
101 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
102 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
103 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |
104 | * ==================================================================== | |
105 | * | |
106 | * This product includes cryptographic software written by Eric Young | |
107 | * (eay@cryptsoft.com). This product includes software written by Tim | |
108 | * Hudson (tjh@cryptsoft.com). | |
109 | * | |
110 | */ | |
d02b48c6 RE |
111 | |
112 | #include <stdio.h> | |
113 | #include <time.h> | |
114 | #include "cryptlib.h" | |
115 | #include "bn_lcl.h" | |
ec577822 | 116 | #include <openssl/rand.h> |
d02b48c6 | 117 | |
e9224c71 GT |
118 | /* NB: these functions have been "upgraded", the deprecated versions (which are |
119 | * compatibility wrappers using these functions) are in bn_depr.c. | |
120 | * - Geoff | |
121 | */ | |
122 | ||
4486d0cd | 123 | /* The quick sieve algorithm approach to weeding out primes is |
d02b48c6 RE |
124 | * Philip Zimmermann's, as implemented in PGP. I have had a read of |
125 | * his comments and implemented my own version. | |
126 | */ | |
127 | #include "bn_prime.h" | |
128 | ||
7999c65c BM |
129 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
130 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); | |
d02b48c6 | 131 | static int probable_prime(BIGNUM *rnd, int bits); |
76aa0ddc | 132 | static int probable_prime_dh_safe(BIGNUM *rnd, int bits, |
020fc820 | 133 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); |
eb952088 | 134 | |
e9224c71 GT |
135 | int BN_GENCB_call(BN_GENCB *cb, int a, int b) |
136 | { | |
137 | /* No callback means continue */ | |
138 | if(!cb) return 1; | |
139 | switch(cb->ver) | |
140 | { | |
141 | case 1: | |
142 | /* Deprecated-style callbacks */ | |
26196762 BL |
143 | if(!cb->cb.cb_1) |
144 | return 1; | |
e1898724 | 145 | cb->cb.cb_1(a, b, cb->arg); |
e9224c71 GT |
146 | return 1; |
147 | case 2: | |
148 | /* New-style callbacks */ | |
e1898724 | 149 | return cb->cb.cb_2(a, b, cb); |
e9224c71 GT |
150 | default: |
151 | break; | |
152 | } | |
153 | /* Unrecognised callback type */ | |
154 | return 0; | |
155 | } | |
156 | ||
157 | int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, | |
158 | const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) | |
d02b48c6 | 159 | { |
c86f2054 | 160 | BIGNUM *t; |
4486d0cd | 161 | int found=0; |
d02b48c6 | 162 | int i,j,c1=0; |
e74231ed | 163 | BN_CTX *ctx; |
a87030a1 | 164 | int checks = BN_prime_checks_for_size(bits); |
d02b48c6 | 165 | |
96a4c31b AL |
166 | if (bits < 2) |
167 | { | |
168 | /* There are no prime numbers this small. */ | |
169 | BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); | |
170 | return 0; | |
171 | } | |
172 | else if (bits == 2 && safe) | |
173 | { | |
174 | /* The smallest safe prime (7) is three bits. */ | |
175 | BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); | |
176 | return 0; | |
177 | } | |
178 | ||
d02b48c6 RE |
179 | ctx=BN_CTX_new(); |
180 | if (ctx == NULL) goto err; | |
c86f2054 GT |
181 | BN_CTX_start(ctx); |
182 | t = BN_CTX_get(ctx); | |
183 | if(!t) goto err; | |
d02b48c6 RE |
184 | loop: |
185 | /* make a random number and set the top and bottom bits */ | |
186 | if (add == NULL) | |
187 | { | |
e9224c71 | 188 | if (!probable_prime(ret,bits)) goto err; |
d02b48c6 RE |
189 | } |
190 | else | |
191 | { | |
76aa0ddc | 192 | if (safe) |
d02b48c6 | 193 | { |
e9224c71 | 194 | if (!probable_prime_dh_safe(ret,bits,add,rem,ctx)) |
d02b48c6 RE |
195 | goto err; |
196 | } | |
197 | else | |
198 | { | |
e46a059e | 199 | if (!bn_probable_prime_dh(ret,bits,add,rem,ctx)) |
d02b48c6 RE |
200 | goto err; |
201 | } | |
202 | } | |
e9224c71 GT |
203 | /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ |
204 | if(!BN_GENCB_call(cb, 0, c1++)) | |
205 | /* aborted */ | |
206 | goto err; | |
d02b48c6 | 207 | |
76aa0ddc | 208 | if (!safe) |
d02b48c6 | 209 | { |
e9224c71 | 210 | i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb); |
d02b48c6 RE |
211 | if (i == -1) goto err; |
212 | if (i == 0) goto loop; | |
213 | } | |
214 | else | |
215 | { | |
76aa0ddc | 216 | /* for "safe prime" generation, |
d02b48c6 RE |
217 | * check that (p-1)/2 is prime. |
218 | * Since a prime is odd, We just | |
219 | * need to divide by 2 */ | |
c86f2054 | 220 | if (!BN_rshift1(t,ret)) goto err; |
d02b48c6 | 221 | |
76aa0ddc | 222 | for (i=0; i<checks; i++) |
d02b48c6 | 223 | { |
e9224c71 | 224 | j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb); |
d02b48c6 RE |
225 | if (j == -1) goto err; |
226 | if (j == 0) goto loop; | |
227 | ||
c86f2054 | 228 | j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb); |
d02b48c6 RE |
229 | if (j == -1) goto err; |
230 | if (j == 0) goto loop; | |
231 | ||
e9224c71 GT |
232 | if(!BN_GENCB_call(cb, 2, c1-1)) |
233 | goto err; | |
76aa0ddc | 234 | /* We have a safe prime test pass */ |
d02b48c6 RE |
235 | } |
236 | } | |
237 | /* we have a prime :-) */ | |
4486d0cd | 238 | found = 1; |
d02b48c6 | 239 | err: |
c86f2054 GT |
240 | if (ctx != NULL) |
241 | { | |
242 | BN_CTX_end(ctx); | |
243 | BN_CTX_free(ctx); | |
244 | } | |
d870740c | 245 | bn_check_top(ret); |
e9224c71 | 246 | return found; |
d02b48c6 RE |
247 | } |
248 | ||
e9224c71 | 249 | int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb) |
e74231ed | 250 | { |
e9224c71 | 251 | return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); |
e74231ed BM |
252 | } |
253 | ||
e9224c71 GT |
254 | int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, |
255 | int do_trial_division, BN_GENCB *cb) | |
d02b48c6 | 256 | { |
e74231ed BM |
257 | int i, j, ret = -1; |
258 | int k; | |
259 | BN_CTX *ctx = NULL; | |
aff0825c | 260 | BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ |
e74231ed | 261 | BN_MONT_CTX *mont = NULL; |
657e60fa | 262 | const BIGNUM *A = NULL; |
d02b48c6 | 263 | |
91b3f0e6 | 264 | if (BN_cmp(a, BN_value_one()) <= 0) |
983495c4 BM |
265 | return 0; |
266 | ||
4486d0cd | 267 | if (checks == BN_prime_checks) |
e74231ed BM |
268 | checks = BN_prime_checks_for_size(BN_num_bits(a)); |
269 | ||
e74231ed | 270 | /* first look for small factors */ |
58964a49 | 271 | if (!BN_is_odd(a)) |
2c5fadbc NL |
272 | /* a is even => a is prime if and only if a == 2 */ |
273 | return BN_is_word(a, 2); | |
a87030a1 | 274 | if (do_trial_division) |
1baa9490 | 275 | { |
a87030a1 BM |
276 | for (i = 1; i < NUMPRIMES; i++) |
277 | if (BN_mod_word(a, primes[i]) == 0) | |
278 | return 0; | |
e9224c71 GT |
279 | if(!BN_GENCB_call(cb, 1, -1)) |
280 | goto err; | |
1baa9490 | 281 | } |
a87030a1 | 282 | |
d02b48c6 | 283 | if (ctx_passed != NULL) |
e74231ed | 284 | ctx = ctx_passed; |
d02b48c6 | 285 | else |
e74231ed BM |
286 | if ((ctx=BN_CTX_new()) == NULL) |
287 | goto err; | |
9b141126 UM |
288 | BN_CTX_start(ctx); |
289 | ||
aff0825c BM |
290 | /* A := abs(a) */ |
291 | if (a->neg) | |
292 | { | |
9b141126 UM |
293 | BIGNUM *t; |
294 | if ((t = BN_CTX_get(ctx)) == NULL) goto err; | |
7999c65c BM |
295 | BN_copy(t, a); |
296 | t->neg = 0; | |
297 | A = t; | |
aff0825c BM |
298 | } |
299 | else | |
300 | A = a; | |
9b141126 UM |
301 | A1 = BN_CTX_get(ctx); |
302 | A1_odd = BN_CTX_get(ctx); | |
303 | check = BN_CTX_get(ctx); | |
304 | if (check == NULL) goto err; | |
e74231ed | 305 | |
aff0825c BM |
306 | /* compute A1 := A - 1 */ |
307 | if (!BN_copy(A1, A)) | |
e74231ed | 308 | goto err; |
aff0825c | 309 | if (!BN_sub_word(A1, 1)) |
e74231ed | 310 | goto err; |
aff0825c | 311 | if (BN_is_zero(A1)) |
e74231ed BM |
312 | { |
313 | ret = 0; | |
314 | goto err; | |
315 | } | |
58964a49 | 316 | |
aff0825c | 317 | /* write A1 as A1_odd * 2^k */ |
e74231ed | 318 | k = 1; |
aff0825c | 319 | while (!BN_is_bit_set(A1, k)) |
e74231ed | 320 | k++; |
aff0825c | 321 | if (!BN_rshift(A1_odd, A1, k)) |
e74231ed BM |
322 | goto err; |
323 | ||
aff0825c | 324 | /* Montgomery setup for computations mod A */ |
e74231ed BM |
325 | mont = BN_MONT_CTX_new(); |
326 | if (mont == NULL) | |
327 | goto err; | |
aff0825c | 328 | if (!BN_MONT_CTX_set(mont, A, ctx)) |
e74231ed BM |
329 | goto err; |
330 | ||
331 | for (i = 0; i < checks; i++) | |
d02b48c6 | 332 | { |
983495c4 | 333 | if (!BN_pseudo_rand_range(check, A1)) |
e74231ed | 334 | goto err; |
e74231ed BM |
335 | if (!BN_add_word(check, 1)) |
336 | goto err; | |
aff0825c | 337 | /* now 1 <= check < A */ |
e74231ed | 338 | |
aff0825c | 339 | j = witness(check, A, A1, A1_odd, k, ctx, mont); |
d02b48c6 RE |
340 | if (j == -1) goto err; |
341 | if (j) | |
342 | { | |
343 | ret=0; | |
344 | goto err; | |
345 | } | |
e9224c71 GT |
346 | if(!BN_GENCB_call(cb, 1, i)) |
347 | goto err; | |
d02b48c6 RE |
348 | } |
349 | ret=1; | |
350 | err: | |
9b141126 | 351 | if (ctx != NULL) |
aff0825c | 352 | { |
9b141126 UM |
353 | BN_CTX_end(ctx); |
354 | if (ctx_passed == NULL) | |
355 | BN_CTX_free(ctx); | |
aff0825c | 356 | } |
e74231ed BM |
357 | if (mont != NULL) |
358 | BN_MONT_CTX_free(mont); | |
d02b48c6 | 359 | |
e74231ed | 360 | return(ret); |
a87030a1 BM |
361 | } |
362 | ||
e46a059e FLM |
363 | int bn_probable_prime_dh(BIGNUM *rnd, int bits, |
364 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) | |
365 | { | |
366 | int i,ret=0; | |
367 | BIGNUM *t1; | |
368 | ||
369 | BN_CTX_start(ctx); | |
370 | if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; | |
371 | ||
372 | if (!BN_rand(rnd,bits,0,1)) goto err; | |
373 | ||
374 | /* we need ((rnd-rem) % add) == 0 */ | |
375 | ||
376 | if (!BN_mod(t1,rnd,add,ctx)) goto err; | |
377 | if (!BN_sub(rnd,rnd,t1)) goto err; | |
378 | if (rem == NULL) | |
379 | { if (!BN_add_word(rnd,1)) goto err; } | |
380 | else | |
381 | { if (!BN_add(rnd,rnd,rem)) goto err; } | |
382 | ||
383 | /* we now have a random number 'rand' to test. */ | |
384 | ||
385 | loop: | |
386 | for (i=1; i<NUMPRIMES; i++) | |
387 | { | |
388 | /* check that rnd is a prime */ | |
389 | if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1) | |
390 | { | |
391 | if (!BN_add(rnd,rnd,add)) goto err; | |
392 | goto loop; | |
393 | } | |
394 | } | |
395 | ret=1; | |
396 | err: | |
397 | BN_CTX_end(ctx); | |
398 | bn_check_top(rnd); | |
399 | return(ret); | |
400 | } | |
401 | ||
7999c65c BM |
402 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
403 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) | |
d02b48c6 | 404 | { |
e74231ed BM |
405 | if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ |
406 | return -1; | |
407 | if (BN_is_one(w)) | |
408 | return 0; /* probably prime */ | |
409 | if (BN_cmp(w, a1) == 0) | |
410 | return 0; /* w == -1 (mod a), 'a' is probably prime */ | |
411 | while (--k) | |
d02b48c6 | 412 | { |
e74231ed BM |
413 | if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ |
414 | return -1; | |
415 | if (BN_is_one(w)) | |
416 | return 1; /* 'a' is composite, otherwise a previous 'w' would | |
417 | * have been == -1 (mod 'a') */ | |
418 | if (BN_cmp(w, a1) == 0) | |
419 | return 0; /* w == -1 (mod a), 'a' is probably prime */ | |
d02b48c6 | 420 | } |
e74231ed BM |
421 | /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', |
422 | * and it is neither -1 nor +1 -- so 'a' cannot be prime */ | |
d870740c | 423 | bn_check_top(w); |
e74231ed | 424 | return 1; |
d02b48c6 RE |
425 | } |
426 | ||
6b691a5c | 427 | static int probable_prime(BIGNUM *rnd, int bits) |
d02b48c6 RE |
428 | { |
429 | int i; | |
75a8e30f | 430 | prime_t mods[NUMPRIMES]; |
96a4c31b AL |
431 | BN_ULONG delta; |
432 | BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1]; | |
433 | char is_single_word = bits <= BN_BITS2; | |
d02b48c6 | 434 | |
dfeab068 | 435 | again: |
d02b48c6 | 436 | if (!BN_rand(rnd,bits,1,1)) return(0); |
96a4c31b | 437 | /* we now have a random number 'rnd' to test. */ |
d02b48c6 | 438 | for (i=1; i<NUMPRIMES; i++) |
75a8e30f | 439 | mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]); |
96a4c31b AL |
440 | /* If bits is so small that it fits into a single word then we |
441 | * additionally don't want to exceed that many bits. */ | |
442 | if (is_single_word) | |
443 | { | |
444 | BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1; | |
445 | if (size_limit < maxdelta) | |
446 | maxdelta = size_limit; | |
447 | } | |
d02b48c6 | 448 | delta=0; |
e55fca76 | 449 | loop: |
96a4c31b | 450 | if (is_single_word) |
d02b48c6 | 451 | { |
96a4c31b AL |
452 | BN_ULONG rnd_word = BN_get_word(rnd); |
453 | ||
454 | /* In the case that the candidate prime is a single word then | |
455 | * we check that: | |
456 | * 1) It's greater than primes[i] because we shouldn't reject | |
457 | * 3 as being a prime number because it's a multiple of | |
458 | * three. | |
459 | * 2) That it's not a multiple of a known prime. We don't | |
460 | * check that rnd-1 is also coprime to all the known | |
461 | * primes because there aren't many small primes where | |
462 | * that's true. */ | |
463 | for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++) | |
d02b48c6 | 464 | { |
96a4c31b AL |
465 | if ((mods[i]+delta)%primes[i] == 0) |
466 | { | |
467 | delta+=2; | |
468 | if (delta > maxdelta) goto again; | |
469 | goto loop; | |
470 | } | |
471 | } | |
472 | } | |
473 | else | |
474 | { | |
475 | for (i=1; i<NUMPRIMES; i++) | |
476 | { | |
477 | /* check that rnd is not a prime and also | |
478 | * that gcd(rnd-1,primes) == 1 (except for 2) */ | |
479 | if (((mods[i]+delta)%primes[i]) <= 1) | |
480 | { | |
481 | delta+=2; | |
482 | if (delta > maxdelta) goto again; | |
483 | goto loop; | |
484 | } | |
d02b48c6 RE |
485 | } |
486 | } | |
487 | if (!BN_add_word(rnd,delta)) return(0); | |
96a4c31b AL |
488 | if (BN_num_bits(rnd) != bits) |
489 | goto again; | |
d870740c | 490 | bn_check_top(rnd); |
d02b48c6 RE |
491 | return(1); |
492 | } | |
493 | ||
020fc820 RL |
494 | static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, |
495 | const BIGNUM *rem, BN_CTX *ctx) | |
d02b48c6 RE |
496 | { |
497 | int i,ret=0; | |
9b141126 | 498 | BIGNUM *t1,*qadd,*q; |
d02b48c6 RE |
499 | |
500 | bits--; | |
9b141126 UM |
501 | BN_CTX_start(ctx); |
502 | t1 = BN_CTX_get(ctx); | |
503 | q = BN_CTX_get(ctx); | |
504 | qadd = BN_CTX_get(ctx); | |
505 | if (qadd == NULL) goto err; | |
d02b48c6 RE |
506 | |
507 | if (!BN_rshift1(qadd,padd)) goto err; | |
508 | ||
509 | if (!BN_rand(q,bits,0,1)) goto err; | |
510 | ||
511 | /* we need ((rnd-rem) % add) == 0 */ | |
512 | if (!BN_mod(t1,q,qadd,ctx)) goto err; | |
513 | if (!BN_sub(q,q,t1)) goto err; | |
514 | if (rem == NULL) | |
515 | { if (!BN_add_word(q,1)) goto err; } | |
516 | else | |
517 | { | |
518 | if (!BN_rshift1(t1,rem)) goto err; | |
519 | if (!BN_add(q,q,t1)) goto err; | |
520 | } | |
521 | ||
522 | /* we now have a random number 'rand' to test. */ | |
523 | if (!BN_lshift1(p,q)) goto err; | |
524 | if (!BN_add_word(p,1)) goto err; | |
525 | ||
e55fca76 FLM |
526 | loop: |
527 | for (i=1; i<NUMPRIMES; i++) | |
d02b48c6 RE |
528 | { |
529 | /* check that p and q are prime */ | |
530 | /* check that for p and q | |
531 | * gcd(p-1,primes) == 1 (except for 2) */ | |
e14d4443 UM |
532 | if ( (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) || |
533 | (BN_mod_word(q,(BN_ULONG)primes[i]) == 0)) | |
d02b48c6 RE |
534 | { |
535 | if (!BN_add(p,p,padd)) goto err; | |
536 | if (!BN_add(q,q,qadd)) goto err; | |
537 | goto loop; | |
538 | } | |
539 | } | |
540 | ret=1; | |
541 | err: | |
9b141126 | 542 | BN_CTX_end(ctx); |
d870740c | 543 | bn_check_top(p); |
d02b48c6 RE |
544 | return(ret); |
545 | } |