]>
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 RE |
131 | static int probable_prime(BIGNUM *rnd, int bits); |
132 | static int probable_prime_dh(BIGNUM *rnd, int bits, | |
020fc820 | 133 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); |
76aa0ddc | 134 | static int probable_prime_dh_safe(BIGNUM *rnd, int bits, |
020fc820 | 135 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); |
eb952088 | 136 | |
e9224c71 GT |
137 | int BN_GENCB_call(BN_GENCB *cb, int a, int b) |
138 | { | |
139 | /* No callback means continue */ | |
140 | if(!cb) return 1; | |
141 | switch(cb->ver) | |
142 | { | |
143 | case 1: | |
144 | /* Deprecated-style callbacks */ | |
145 | cb->cb_1(a, b, cb->arg); | |
146 | return 1; | |
147 | case 2: | |
148 | /* New-style callbacks */ | |
149 | return cb->cb_2(a, b, cb); | |
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 | { |
dfeab068 | 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 RE |
165 | |
166 | ctx=BN_CTX_new(); | |
167 | if (ctx == NULL) goto err; | |
dfeab068 | 168 | BN_init(&t); |
d02b48c6 RE |
169 | loop: |
170 | /* make a random number and set the top and bottom bits */ | |
171 | if (add == NULL) | |
172 | { | |
e9224c71 | 173 | if (!probable_prime(ret,bits)) goto err; |
d02b48c6 RE |
174 | } |
175 | else | |
176 | { | |
76aa0ddc | 177 | if (safe) |
d02b48c6 | 178 | { |
e9224c71 | 179 | if (!probable_prime_dh_safe(ret,bits,add,rem,ctx)) |
d02b48c6 RE |
180 | goto err; |
181 | } | |
182 | else | |
183 | { | |
e9224c71 | 184 | if (!probable_prime_dh(ret,bits,add,rem,ctx)) |
d02b48c6 RE |
185 | goto err; |
186 | } | |
187 | } | |
e9224c71 GT |
188 | /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ |
189 | if(!BN_GENCB_call(cb, 0, c1++)) | |
190 | /* aborted */ | |
191 | goto err; | |
d02b48c6 | 192 | |
76aa0ddc | 193 | if (!safe) |
d02b48c6 | 194 | { |
e9224c71 | 195 | i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb); |
d02b48c6 RE |
196 | if (i == -1) goto err; |
197 | if (i == 0) goto loop; | |
198 | } | |
199 | else | |
200 | { | |
76aa0ddc | 201 | /* for "safe prime" generation, |
d02b48c6 RE |
202 | * check that (p-1)/2 is prime. |
203 | * Since a prime is odd, We just | |
204 | * need to divide by 2 */ | |
e9224c71 | 205 | if (!BN_rshift1(&t,ret)) goto err; |
d02b48c6 | 206 | |
76aa0ddc | 207 | for (i=0; i<checks; i++) |
d02b48c6 | 208 | { |
e9224c71 | 209 | j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb); |
d02b48c6 RE |
210 | if (j == -1) goto err; |
211 | if (j == 0) goto loop; | |
212 | ||
e9224c71 | 213 | j=BN_is_prime_fasttest_ex(&t,1,ctx,0,cb); |
d02b48c6 RE |
214 | if (j == -1) goto err; |
215 | if (j == 0) goto loop; | |
216 | ||
e9224c71 GT |
217 | if(!BN_GENCB_call(cb, 2, c1-1)) |
218 | goto err; | |
76aa0ddc | 219 | /* We have a safe prime test pass */ |
d02b48c6 RE |
220 | } |
221 | } | |
222 | /* we have a prime :-) */ | |
4486d0cd | 223 | found = 1; |
d02b48c6 | 224 | err: |
dfeab068 | 225 | BN_free(&t); |
d02b48c6 | 226 | if (ctx != NULL) BN_CTX_free(ctx); |
e9224c71 | 227 | return found; |
d02b48c6 RE |
228 | } |
229 | ||
e9224c71 | 230 | int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb) |
e74231ed | 231 | { |
e9224c71 | 232 | return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); |
e74231ed BM |
233 | } |
234 | ||
e9224c71 GT |
235 | int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, |
236 | int do_trial_division, BN_GENCB *cb) | |
d02b48c6 | 237 | { |
e74231ed BM |
238 | int i, j, ret = -1; |
239 | int k; | |
240 | BN_CTX *ctx = NULL; | |
aff0825c | 241 | BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ |
e74231ed | 242 | BN_MONT_CTX *mont = NULL; |
657e60fa | 243 | const BIGNUM *A = NULL; |
d02b48c6 | 244 | |
91b3f0e6 | 245 | if (BN_cmp(a, BN_value_one()) <= 0) |
983495c4 BM |
246 | return 0; |
247 | ||
4486d0cd | 248 | if (checks == BN_prime_checks) |
e74231ed BM |
249 | checks = BN_prime_checks_for_size(BN_num_bits(a)); |
250 | ||
e74231ed | 251 | /* first look for small factors */ |
58964a49 | 252 | if (!BN_is_odd(a)) |
983495c4 | 253 | return 0; |
a87030a1 | 254 | if (do_trial_division) |
1baa9490 | 255 | { |
a87030a1 BM |
256 | for (i = 1; i < NUMPRIMES; i++) |
257 | if (BN_mod_word(a, primes[i]) == 0) | |
258 | return 0; | |
e9224c71 GT |
259 | if(!BN_GENCB_call(cb, 1, -1)) |
260 | goto err; | |
1baa9490 | 261 | } |
a87030a1 | 262 | |
d02b48c6 | 263 | if (ctx_passed != NULL) |
e74231ed | 264 | ctx = ctx_passed; |
d02b48c6 | 265 | else |
e74231ed BM |
266 | if ((ctx=BN_CTX_new()) == NULL) |
267 | goto err; | |
9b141126 UM |
268 | BN_CTX_start(ctx); |
269 | ||
aff0825c BM |
270 | /* A := abs(a) */ |
271 | if (a->neg) | |
272 | { | |
9b141126 UM |
273 | BIGNUM *t; |
274 | if ((t = BN_CTX_get(ctx)) == NULL) goto err; | |
7999c65c BM |
275 | BN_copy(t, a); |
276 | t->neg = 0; | |
277 | A = t; | |
aff0825c BM |
278 | } |
279 | else | |
280 | A = a; | |
9b141126 UM |
281 | A1 = BN_CTX_get(ctx); |
282 | A1_odd = BN_CTX_get(ctx); | |
283 | check = BN_CTX_get(ctx); | |
284 | if (check == NULL) goto err; | |
e74231ed | 285 | |
aff0825c BM |
286 | /* compute A1 := A - 1 */ |
287 | if (!BN_copy(A1, A)) | |
e74231ed | 288 | goto err; |
aff0825c | 289 | if (!BN_sub_word(A1, 1)) |
e74231ed | 290 | goto err; |
aff0825c | 291 | if (BN_is_zero(A1)) |
e74231ed BM |
292 | { |
293 | ret = 0; | |
294 | goto err; | |
295 | } | |
58964a49 | 296 | |
aff0825c | 297 | /* write A1 as A1_odd * 2^k */ |
e74231ed | 298 | k = 1; |
aff0825c | 299 | while (!BN_is_bit_set(A1, k)) |
e74231ed | 300 | k++; |
aff0825c | 301 | if (!BN_rshift(A1_odd, A1, k)) |
e74231ed BM |
302 | goto err; |
303 | ||
aff0825c | 304 | /* Montgomery setup for computations mod A */ |
e74231ed BM |
305 | mont = BN_MONT_CTX_new(); |
306 | if (mont == NULL) | |
307 | goto err; | |
aff0825c | 308 | if (!BN_MONT_CTX_set(mont, A, ctx)) |
e74231ed BM |
309 | goto err; |
310 | ||
311 | for (i = 0; i < checks; i++) | |
d02b48c6 | 312 | { |
983495c4 | 313 | if (!BN_pseudo_rand_range(check, A1)) |
e74231ed | 314 | goto err; |
e74231ed BM |
315 | if (!BN_add_word(check, 1)) |
316 | goto err; | |
aff0825c | 317 | /* now 1 <= check < A */ |
e74231ed | 318 | |
aff0825c | 319 | j = witness(check, A, A1, A1_odd, k, ctx, mont); |
d02b48c6 RE |
320 | if (j == -1) goto err; |
321 | if (j) | |
322 | { | |
323 | ret=0; | |
324 | goto err; | |
325 | } | |
e9224c71 GT |
326 | if(!BN_GENCB_call(cb, 1, i)) |
327 | goto err; | |
d02b48c6 RE |
328 | } |
329 | ret=1; | |
330 | err: | |
9b141126 | 331 | if (ctx != NULL) |
aff0825c | 332 | { |
9b141126 UM |
333 | BN_CTX_end(ctx); |
334 | if (ctx_passed == NULL) | |
335 | BN_CTX_free(ctx); | |
aff0825c | 336 | } |
e74231ed BM |
337 | if (mont != NULL) |
338 | BN_MONT_CTX_free(mont); | |
d02b48c6 | 339 | |
e74231ed | 340 | return(ret); |
a87030a1 BM |
341 | } |
342 | ||
7999c65c BM |
343 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
344 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) | |
d02b48c6 | 345 | { |
e74231ed BM |
346 | if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ |
347 | return -1; | |
348 | if (BN_is_one(w)) | |
349 | return 0; /* probably prime */ | |
350 | if (BN_cmp(w, a1) == 0) | |
351 | return 0; /* w == -1 (mod a), 'a' is probably prime */ | |
352 | while (--k) | |
d02b48c6 | 353 | { |
e74231ed BM |
354 | if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ |
355 | return -1; | |
356 | if (BN_is_one(w)) | |
357 | return 1; /* 'a' is composite, otherwise a previous 'w' would | |
358 | * have been == -1 (mod 'a') */ | |
359 | if (BN_cmp(w, a1) == 0) | |
360 | return 0; /* w == -1 (mod a), 'a' is probably prime */ | |
d02b48c6 | 361 | } |
e74231ed BM |
362 | /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', |
363 | * and it is neither -1 nor +1 -- so 'a' cannot be prime */ | |
364 | return 1; | |
d02b48c6 RE |
365 | } |
366 | ||
6b691a5c | 367 | static int probable_prime(BIGNUM *rnd, int bits) |
d02b48c6 RE |
368 | { |
369 | int i; | |
a87030a1 | 370 | BN_ULONG mods[NUMPRIMES]; |
dfeab068 | 371 | BN_ULONG delta,d; |
d02b48c6 | 372 | |
dfeab068 | 373 | again: |
d02b48c6 RE |
374 | if (!BN_rand(rnd,bits,1,1)) return(0); |
375 | /* we now have a random number 'rand' to test. */ | |
376 | for (i=1; i<NUMPRIMES; i++) | |
377 | mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]); | |
378 | delta=0; | |
379 | loop: for (i=1; i<NUMPRIMES; i++) | |
380 | { | |
381 | /* check that rnd is not a prime and also | |
382 | * that gcd(rnd-1,primes) == 1 (except for 2) */ | |
383 | if (((mods[i]+delta)%primes[i]) <= 1) | |
384 | { | |
dfeab068 | 385 | d=delta; |
d02b48c6 RE |
386 | delta+=2; |
387 | /* perhaps need to check for overflow of | |
657e60fa | 388 | * delta (but delta can be up to 2^32) |
dfeab068 RE |
389 | * 21-May-98 eay - added overflow check */ |
390 | if (delta < d) goto again; | |
d02b48c6 RE |
391 | goto loop; |
392 | } | |
393 | } | |
394 | if (!BN_add_word(rnd,delta)) return(0); | |
395 | return(1); | |
396 | } | |
397 | ||
020fc820 RL |
398 | static int probable_prime_dh(BIGNUM *rnd, int bits, |
399 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) | |
d02b48c6 RE |
400 | { |
401 | int i,ret=0; | |
402 | BIGNUM *t1; | |
403 | ||
9b141126 UM |
404 | BN_CTX_start(ctx); |
405 | if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; | |
d02b48c6 RE |
406 | |
407 | if (!BN_rand(rnd,bits,0,1)) goto err; | |
408 | ||
409 | /* we need ((rnd-rem) % add) == 0 */ | |
410 | ||
411 | if (!BN_mod(t1,rnd,add,ctx)) goto err; | |
412 | if (!BN_sub(rnd,rnd,t1)) goto err; | |
413 | if (rem == NULL) | |
414 | { if (!BN_add_word(rnd,1)) goto err; } | |
415 | else | |
416 | { if (!BN_add(rnd,rnd,rem)) goto err; } | |
417 | ||
418 | /* we now have a random number 'rand' to test. */ | |
419 | ||
420 | loop: for (i=1; i<NUMPRIMES; i++) | |
421 | { | |
422 | /* check that rnd is a prime */ | |
e14d4443 | 423 | if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1) |
d02b48c6 RE |
424 | { |
425 | if (!BN_add(rnd,rnd,add)) goto err; | |
426 | goto loop; | |
427 | } | |
428 | } | |
429 | ret=1; | |
430 | err: | |
9b141126 | 431 | BN_CTX_end(ctx); |
d02b48c6 RE |
432 | return(ret); |
433 | } | |
434 | ||
020fc820 RL |
435 | static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, |
436 | const BIGNUM *rem, BN_CTX *ctx) | |
d02b48c6 RE |
437 | { |
438 | int i,ret=0; | |
9b141126 | 439 | BIGNUM *t1,*qadd,*q; |
d02b48c6 RE |
440 | |
441 | bits--; | |
9b141126 UM |
442 | BN_CTX_start(ctx); |
443 | t1 = BN_CTX_get(ctx); | |
444 | q = BN_CTX_get(ctx); | |
445 | qadd = BN_CTX_get(ctx); | |
446 | if (qadd == NULL) goto err; | |
d02b48c6 RE |
447 | |
448 | if (!BN_rshift1(qadd,padd)) goto err; | |
449 | ||
450 | if (!BN_rand(q,bits,0,1)) goto err; | |
451 | ||
452 | /* we need ((rnd-rem) % add) == 0 */ | |
453 | if (!BN_mod(t1,q,qadd,ctx)) goto err; | |
454 | if (!BN_sub(q,q,t1)) goto err; | |
455 | if (rem == NULL) | |
456 | { if (!BN_add_word(q,1)) goto err; } | |
457 | else | |
458 | { | |
459 | if (!BN_rshift1(t1,rem)) goto err; | |
460 | if (!BN_add(q,q,t1)) goto err; | |
461 | } | |
462 | ||
463 | /* we now have a random number 'rand' to test. */ | |
464 | if (!BN_lshift1(p,q)) goto err; | |
465 | if (!BN_add_word(p,1)) goto err; | |
466 | ||
467 | loop: for (i=1; i<NUMPRIMES; i++) | |
468 | { | |
469 | /* check that p and q are prime */ | |
470 | /* check that for p and q | |
471 | * gcd(p-1,primes) == 1 (except for 2) */ | |
e14d4443 UM |
472 | if ( (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) || |
473 | (BN_mod_word(q,(BN_ULONG)primes[i]) == 0)) | |
d02b48c6 RE |
474 | { |
475 | if (!BN_add(p,p,padd)) goto err; | |
476 | if (!BN_add(q,q,qadd)) goto err; | |
477 | goto loop; | |
478 | } | |
479 | } | |
480 | ret=1; | |
481 | err: | |
9b141126 | 482 | BN_CTX_end(ctx); |
d02b48c6 RE |
483 | return(ret); |
484 | } |