1 | /* |
2 | * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy |
6 | * in the file LICENSE in the source distribution or at |
7 | * https://www.openssl.org/source/license.html |
8 | */ |
9 | |
10 | #include <stdio.h> |
11 | #include <time.h> |
12 | #include "internal/cryptlib.h" |
13 | #include "bn_local.h" |
14 | |
15 | /* |
16 | * The quick sieve algorithm approach to weeding out primes is Philip |
17 | * Zimmermann's, as implemented in PGP. I have had a read of his comments |
18 | * and implemented my own version. |
19 | */ |
20 | #include "bn_prime.h" |
21 | |
22 | static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
23 | BN_CTX *ctx); |
24 | static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
25 | const BIGNUM *add, const BIGNUM *rem, |
26 | BN_CTX *ctx); |
27 | static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, |
28 | int do_trial_division, BN_GENCB *cb); |
29 | |
30 | #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x)) |
31 | |
32 | #if BN_BITS2 == 64 |
33 | # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo |
34 | #else |
35 | # define BN_DEF(lo, hi) lo, hi |
36 | #endif |
37 | |
38 | /* |
39 | * See SP800 89 5.3.3 (Step f) |
40 | * The product of the set of primes ranging from 3 to 751 |
41 | * Generated using process in test/bn_internal_test.c test_bn_small_factors(). |
42 | * This includes 751 (which is not currently included in SP 800-89). |
43 | */ |
44 | static const BN_ULONG small_prime_factors[] = { |
45 | BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6), |
46 | BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3), |
47 | BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817), |
48 | BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2), |
49 | BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3), |
50 | BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28), |
51 | BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112), |
52 | BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460), |
53 | (BN_ULONG)0x000017b1 |
54 | }; |
55 | |
56 | #define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors) |
57 | static const BIGNUM _bignum_small_prime_factors = { |
58 | (BN_ULONG *)small_prime_factors, |
59 | BN_SMALL_PRIME_FACTORS_TOP, |
60 | BN_SMALL_PRIME_FACTORS_TOP, |
61 | 0, |
62 | BN_FLG_STATIC_DATA |
63 | }; |
64 | |
65 | const BIGNUM *bn_get0_small_factors(void) |
66 | { |
67 | return &_bignum_small_prime_factors; |
68 | } |
69 | |
70 | /* |
71 | * Calculate the number of trial divisions that gives the best speed in |
72 | * combination with Miller-Rabin prime test, based on the sized of the prime. |
73 | */ |
74 | static int calc_trial_divisions(int bits) |
75 | { |
76 | if (bits <= 512) |
77 | return 64; |
78 | else if (bits <= 1024) |
79 | return 128; |
80 | else if (bits <= 2048) |
81 | return 384; |
82 | else if (bits <= 4096) |
83 | return 1024; |
84 | return NUMPRIMES; |
85 | } |
86 | |
87 | /* |
88 | * Use a minimum of 64 rounds of Miller-Rabin, which should give a false |
89 | * positive rate of 2^-128. If the size of the prime is larger than 2048 |
90 | * the user probably wants a higher security level than 128, so switch |
91 | * to 128 rounds giving a false positive rate of 2^-256. |
92 | * Returns the number of rounds. |
93 | */ |
94 | static int bn_mr_min_checks(int bits) |
95 | { |
96 | if (bits > 2048) |
97 | return 128; |
98 | return 64; |
99 | } |
100 | |
101 | int BN_GENCB_call(BN_GENCB *cb, int a, int b) |
102 | { |
103 | /* No callback means continue */ |
104 | if (!cb) |
105 | return 1; |
106 | switch (cb->ver) { |
107 | case 1: |
108 | /* Deprecated-style callbacks */ |
109 | if (!cb->cb.cb_1) |
110 | return 1; |
111 | cb->cb.cb_1(a, b, cb->arg); |
112 | return 1; |
113 | case 2: |
114 | /* New-style callbacks */ |
115 | return cb->cb.cb_2(a, b, cb); |
116 | default: |
117 | break; |
118 | } |
119 | /* Unrecognised callback type */ |
120 | return 0; |
121 | } |
122 | |
123 | int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe, |
124 | const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb, |
125 | BN_CTX *ctx) |
126 | { |
127 | BIGNUM *t; |
128 | int found = 0; |
129 | int i, j, c1 = 0; |
130 | prime_t *mods = NULL; |
131 | int checks = bn_mr_min_checks(bits); |
132 | |
133 | if (bits < 2) { |
134 | /* There are no prime numbers this small. */ |
135 | BNerr(BN_F_BN_GENERATE_PRIME_EX2, BN_R_BITS_TOO_SMALL); |
136 | return 0; |
137 | } else if (add == NULL && safe && bits < 6 && bits != 3) { |
138 | /* |
139 | * The smallest safe prime (7) is three bits. |
140 | * But the following two safe primes with less than 6 bits (11, 23) |
141 | * are unreachable for BN_rand with BN_RAND_TOP_TWO. |
142 | */ |
143 | BNerr(BN_F_BN_GENERATE_PRIME_EX2, BN_R_BITS_TOO_SMALL); |
144 | return 0; |
145 | } |
146 | |
147 | mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); |
148 | if (mods == NULL) |
149 | goto err; |
150 | |
151 | BN_CTX_start(ctx); |
152 | t = BN_CTX_get(ctx); |
153 | if (t == NULL) |
154 | goto err; |
155 | loop: |
156 | /* make a random number and set the top and bottom bits */ |
157 | if (add == NULL) { |
158 | if (!probable_prime(ret, bits, safe, mods, ctx)) |
159 | goto err; |
160 | } else { |
161 | if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx)) |
162 | goto err; |
163 | } |
164 | |
165 | if (!BN_GENCB_call(cb, 0, c1++)) |
166 | /* aborted */ |
167 | goto err; |
168 | |
169 | if (!safe) { |
170 | i = bn_is_prime_int(ret, checks, ctx, 0, cb); |
171 | if (i == -1) |
172 | goto err; |
173 | if (i == 0) |
174 | goto loop; |
175 | } else { |
176 | /* |
177 | * for "safe prime" generation, check that (p-1)/2 is prime. Since a |
178 | * prime is odd, We just need to divide by 2 |
179 | */ |
180 | if (!BN_rshift1(t, ret)) |
181 | goto err; |
182 | |
183 | for (i = 0; i < checks; i++) { |
184 | j = bn_is_prime_int(ret, 1, ctx, 0, cb); |
185 | if (j == -1) |
186 | goto err; |
187 | if (j == 0) |
188 | goto loop; |
189 | |
190 | j = bn_is_prime_int(t, 1, ctx, 0, cb); |
191 | if (j == -1) |
192 | goto err; |
193 | if (j == 0) |
194 | goto loop; |
195 | |
196 | if (!BN_GENCB_call(cb, 2, c1 - 1)) |
197 | goto err; |
198 | /* We have a safe prime test pass */ |
199 | } |
200 | } |
201 | /* we have a prime :-) */ |
202 | found = 1; |
203 | err: |
204 | OPENSSL_free(mods); |
205 | BN_CTX_end(ctx); |
206 | bn_check_top(ret); |
207 | return found; |
208 | } |
209 | |
210 | #ifndef FIPS_MODE |
211 | int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, |
212 | const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) |
213 | { |
214 | BN_CTX *ctx = BN_CTX_new(); |
215 | int retval; |
216 | |
217 | if (ctx == NULL) |
218 | return 0; |
219 | |
220 | retval = BN_generate_prime_ex2(ret, bits, safe, add, rem, cb, ctx); |
221 | |
222 | BN_CTX_free(ctx); |
223 | return retval; |
224 | } |
225 | #endif |
226 | |
227 | #ifndef OPENSSL_NO_DEPRECATED_3_0 |
228 | int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, |
229 | BN_GENCB *cb) |
230 | { |
231 | return bn_check_prime_int(a, checks, ctx_passed, 0, cb); |
232 | } |
233 | |
234 | int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx, |
235 | int do_trial_division, BN_GENCB *cb) |
236 | { |
237 | return bn_check_prime_int(w, checks, ctx, do_trial_division, cb); |
238 | } |
239 | #endif |
240 | |
241 | /* Wrapper around bn_is_prime_int that sets the minimum number of checks */ |
242 | int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, |
243 | int do_trial_division, BN_GENCB *cb) |
244 | { |
245 | int min_checks = bn_mr_min_checks(BN_num_bits(w)); |
246 | |
247 | if (checks < min_checks) |
248 | checks = min_checks; |
249 | |
250 | return bn_is_prime_int(w, checks, ctx, do_trial_division, cb); |
251 | } |
252 | |
253 | int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb) |
254 | { |
255 | return bn_check_prime_int(p, 0, ctx, 1, cb); |
256 | } |
257 | |
258 | /* |
259 | * Tests that |w| is probably prime |
260 | * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. |
261 | * |
262 | * Returns 0 when composite, 1 when probable prime, -1 on error. |
263 | */ |
264 | static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, |
265 | int do_trial_division, BN_GENCB *cb) |
266 | { |
267 | int i, status, ret = -1; |
268 | #ifndef FIPS_MODE |
269 | BN_CTX *ctxlocal = NULL; |
270 | #else |
271 | |
272 | if (ctx == NULL) |
273 | return -1; |
274 | #endif |
275 | |
276 | /* w must be bigger than 1 */ |
277 | if (BN_cmp(w, BN_value_one()) <= 0) |
278 | return 0; |
279 | |
280 | /* w must be odd */ |
281 | if (BN_is_odd(w)) { |
282 | /* Take care of the really small prime 3 */ |
283 | if (BN_is_word(w, 3)) |
284 | return 1; |
285 | } else { |
286 | /* 2 is the only even prime */ |
287 | return BN_is_word(w, 2); |
288 | } |
289 | |
290 | /* first look for small factors */ |
291 | if (do_trial_division) { |
292 | int trial_divisions = calc_trial_divisions(BN_num_bits(w)); |
293 | |
294 | for (i = 1; i < trial_divisions; i++) { |
295 | BN_ULONG mod = BN_mod_word(w, primes[i]); |
296 | if (mod == (BN_ULONG)-1) |
297 | return -1; |
298 | if (mod == 0) |
299 | return BN_is_word(w, primes[i]); |
300 | } |
301 | if (!BN_GENCB_call(cb, 1, -1)) |
302 | return -1; |
303 | } |
304 | #ifndef FIPS_MODE |
305 | if (ctx == NULL && (ctxlocal = ctx = BN_CTX_new()) == NULL) |
306 | goto err; |
307 | #endif |
308 | |
309 | ret = bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status); |
310 | if (!ret) |
311 | goto err; |
312 | ret = (status == BN_PRIMETEST_PROBABLY_PRIME); |
313 | err: |
314 | #ifndef FIPS_MODE |
315 | BN_CTX_free(ctxlocal); |
316 | #endif |
317 | return ret; |
318 | } |
319 | |
320 | /* |
321 | * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test. |
322 | * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero). |
323 | * The Step numbers listed in the code refer to the enhanced case. |
324 | * |
325 | * if enhanced is set, then status returns one of the following: |
326 | * BN_PRIMETEST_PROBABLY_PRIME |
327 | * BN_PRIMETEST_COMPOSITE_WITH_FACTOR |
328 | * BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME |
329 | * if enhanced is zero, then status returns either |
330 | * BN_PRIMETEST_PROBABLY_PRIME or |
331 | * BN_PRIMETEST_COMPOSITE |
332 | * |
333 | * returns 0 if there was an error, otherwise it returns 1. |
334 | */ |
335 | int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx, |
336 | BN_GENCB *cb, int enhanced, int *status) |
337 | { |
338 | int i, j, a, ret = 0; |
339 | BIGNUM *g, *w1, *w3, *x, *m, *z, *b; |
340 | BN_MONT_CTX *mont = NULL; |
341 | |
342 | /* w must be odd */ |
343 | if (!BN_is_odd(w)) |
344 | return 0; |
345 | |
346 | BN_CTX_start(ctx); |
347 | g = BN_CTX_get(ctx); |
348 | w1 = BN_CTX_get(ctx); |
349 | w3 = BN_CTX_get(ctx); |
350 | x = BN_CTX_get(ctx); |
351 | m = BN_CTX_get(ctx); |
352 | z = BN_CTX_get(ctx); |
353 | b = BN_CTX_get(ctx); |
354 | |
355 | if (!(b != NULL |
356 | /* w1 := w - 1 */ |
357 | && BN_copy(w1, w) |
358 | && BN_sub_word(w1, 1) |
359 | /* w3 := w - 3 */ |
360 | && BN_copy(w3, w) |
361 | && BN_sub_word(w3, 3))) |
362 | goto err; |
363 | |
364 | /* check w is larger than 3, otherwise the random b will be too small */ |
365 | if (BN_is_zero(w3) || BN_is_negative(w3)) |
366 | goto err; |
367 | |
368 | /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */ |
369 | a = 1; |
370 | while (!BN_is_bit_set(w1, a)) |
371 | a++; |
372 | /* (Step 2) m = (w-1) / 2^a */ |
373 | if (!BN_rshift(m, w1, a)) |
374 | goto err; |
375 | |
376 | /* Montgomery setup for computations mod a */ |
377 | mont = BN_MONT_CTX_new(); |
378 | if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx)) |
379 | goto err; |
380 | |
381 | if (iterations == 0) |
382 | iterations = bn_mr_min_checks(BN_num_bits(w)); |
383 | |
384 | /* (Step 4) */ |
385 | for (i = 0; i < iterations; ++i) { |
386 | /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */ |
387 | if (!BN_priv_rand_range_ex(b, w3, ctx) |
388 | || !BN_add_word(b, 2)) /* 1 < b < w-1 */ |
389 | goto err; |
390 | |
391 | if (enhanced) { |
392 | /* (Step 4.3) */ |
393 | if (!BN_gcd(g, b, w, ctx)) |
394 | goto err; |
395 | /* (Step 4.4) */ |
396 | if (!BN_is_one(g)) { |
397 | *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; |
398 | ret = 1; |
399 | goto err; |
400 | } |
401 | } |
402 | /* (Step 4.5) z = b^m mod w */ |
403 | if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) |
404 | goto err; |
405 | /* (Step 4.6) if (z = 1 or z = w-1) */ |
406 | if (BN_is_one(z) || BN_cmp(z, w1) == 0) |
407 | goto outer_loop; |
408 | /* (Step 4.7) for j = 1 to a-1 */ |
409 | for (j = 1; j < a ; ++j) { |
410 | /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */ |
411 | if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) |
412 | goto err; |
413 | /* (Step 4.7.3) */ |
414 | if (BN_cmp(z, w1) == 0) |
415 | goto outer_loop; |
416 | /* (Step 4.7.4) */ |
417 | if (BN_is_one(z)) |
418 | goto composite; |
419 | } |
420 | /* At this point z = b^((w-1)/2) mod w */ |
421 | /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */ |
422 | if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) |
423 | goto err; |
424 | /* (Step 4.10) */ |
425 | if (BN_is_one(z)) |
426 | goto composite; |
427 | /* (Step 4.11) x = b^(w-1) mod w */ |
428 | if (!BN_copy(x, z)) |
429 | goto err; |
430 | composite: |
431 | if (enhanced) { |
432 | /* (Step 4.1.2) g = GCD(x-1, w) */ |
433 | if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx)) |
434 | goto err; |
435 | /* (Steps 4.1.3 - 4.1.4) */ |
436 | if (BN_is_one(g)) |
437 | *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME; |
438 | else |
439 | *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; |
440 | } else { |
441 | *status = BN_PRIMETEST_COMPOSITE; |
442 | } |
443 | ret = 1; |
444 | goto err; |
445 | outer_loop: ; |
446 | /* (Step 4.1.5) */ |
447 | if (!BN_GENCB_call(cb, 1, i)) |
448 | goto err; |
449 | } |
450 | /* (Step 5) */ |
451 | *status = BN_PRIMETEST_PROBABLY_PRIME; |
452 | ret = 1; |
453 | err: |
454 | BN_clear(g); |
455 | BN_clear(w1); |
456 | BN_clear(w3); |
457 | BN_clear(x); |
458 | BN_clear(m); |
459 | BN_clear(z); |
460 | BN_clear(b); |
461 | BN_CTX_end(ctx); |
462 | BN_MONT_CTX_free(mont); |
463 | return ret; |
464 | } |
465 | |
466 | /* |
467 | * Generate a random number of |bits| bits that is probably prime by sieving. |
468 | * If |safe| != 0, it generates a safe prime. |
469 | * |mods| is a preallocated array that gets reused when called again. |
470 | * |
471 | * The probably prime is saved in |rnd|. |
472 | * |
473 | * Returns 1 on success and 0 on error. |
474 | */ |
475 | static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
476 | BN_CTX *ctx) |
477 | { |
478 | int i; |
479 | BN_ULONG delta; |
480 | int trial_divisions = calc_trial_divisions(bits); |
481 | BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1]; |
482 | |
483 | again: |
484 | /* TODO: Not all primes are private */ |
485 | if (!BN_priv_rand_ex(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD, ctx)) |
486 | return 0; |
487 | if (safe && !BN_set_bit(rnd, 1)) |
488 | return 0; |
489 | /* we now have a random number 'rnd' to test. */ |
490 | for (i = 1; i < trial_divisions; i++) { |
491 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); |
492 | if (mod == (BN_ULONG)-1) |
493 | return 0; |
494 | mods[i] = (prime_t) mod; |
495 | } |
496 | delta = 0; |
497 | loop: |
498 | for (i = 1; i < trial_divisions; i++) { |
499 | /* |
500 | * check that rnd is a prime and also that |
501 | * gcd(rnd-1,primes) == 1 (except for 2) |
502 | * do the second check only if we are interested in safe primes |
503 | * in the case that the candidate prime is a single word then |
504 | * we check only the primes up to sqrt(rnd) |
505 | */ |
506 | if (bits <= 31 && delta <= 0x7fffffff |
507 | && square(primes[i]) > BN_get_word(rnd) + delta) |
508 | break; |
509 | if (safe ? (mods[i] + delta) % primes[i] <= 1 |
510 | : (mods[i] + delta) % primes[i] == 0) { |
511 | delta += safe ? 4 : 2; |
512 | if (delta > maxdelta) |
513 | goto again; |
514 | goto loop; |
515 | } |
516 | } |
517 | if (!BN_add_word(rnd, delta)) |
518 | return 0; |
519 | if (BN_num_bits(rnd) != bits) |
520 | goto again; |
521 | bn_check_top(rnd); |
522 | return 1; |
523 | } |
524 | |
525 | /* |
526 | * Generate a random number |rnd| of |bits| bits that is probably prime |
527 | * and satisfies |rnd| % |add| == |rem| by sieving. |
528 | * If |safe| != 0, it generates a safe prime. |
529 | * |mods| is a preallocated array that gets reused when called again. |
530 | * |
531 | * Returns 1 on success and 0 on error. |
532 | */ |
533 | static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
534 | const BIGNUM *add, const BIGNUM *rem, |
535 | BN_CTX *ctx) |
536 | { |
537 | int i, ret = 0; |
538 | BIGNUM *t1; |
539 | BN_ULONG delta; |
540 | int trial_divisions = calc_trial_divisions(bits); |
541 | BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1]; |
542 | |
543 | BN_CTX_start(ctx); |
544 | if ((t1 = BN_CTX_get(ctx)) == NULL) |
545 | goto err; |
546 | |
547 | if (maxdelta > BN_MASK2 - BN_get_word(add)) |
548 | maxdelta = BN_MASK2 - BN_get_word(add); |
549 | |
550 | again: |
551 | if (!BN_rand_ex(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, ctx)) |
552 | goto err; |
553 | |
554 | /* we need ((rnd-rem) % add) == 0 */ |
555 | |
556 | if (!BN_mod(t1, rnd, add, ctx)) |
557 | goto err; |
558 | if (!BN_sub(rnd, rnd, t1)) |
559 | goto err; |
560 | if (rem == NULL) { |
561 | if (!BN_add_word(rnd, safe ? 3u : 1u)) |
562 | goto err; |
563 | } else { |
564 | if (!BN_add(rnd, rnd, rem)) |
565 | goto err; |
566 | } |
567 | |
568 | if (BN_num_bits(rnd) < bits |
569 | || BN_get_word(rnd) < (safe ? 5u : 3u)) { |
570 | if (!BN_add(rnd, rnd, add)) |
571 | goto err; |
572 | } |
573 | |
574 | /* we now have a random number 'rnd' to test. */ |
575 | for (i = 1; i < trial_divisions; i++) { |
576 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); |
577 | if (mod == (BN_ULONG)-1) |
578 | goto err; |
579 | mods[i] = (prime_t) mod; |
580 | } |
581 | delta = 0; |
582 | loop: |
583 | for (i = 1; i < trial_divisions; i++) { |
584 | /* check that rnd is a prime */ |
585 | if (bits <= 31 && delta <= 0x7fffffff |
586 | && square(primes[i]) > BN_get_word(rnd) + delta) |
587 | break; |
588 | /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */ |
589 | if (safe ? (mods[i] + delta) % primes[i] <= 1 |
590 | : (mods[i] + delta) % primes[i] == 0) { |
591 | delta += BN_get_word(add); |
592 | if (delta > maxdelta) |
593 | goto again; |
594 | goto loop; |
595 | } |
596 | } |
597 | if (!BN_add_word(rnd, delta)) |
598 | goto err; |
599 | ret = 1; |
600 | |
601 | err: |
602 | BN_CTX_end(ctx); |
603 | bn_check_top(rnd); |
604 | return ret; |
605 | } |
606 | |