]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
4333b89f | 2 | * Copyright 1995-2021 The OpenSSL Project Authors. All Rights Reserved. |
4f22f405 | 3 | * |
367ace68 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
4f22f405 RS |
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 | |
bfe30e4d | 8 | */ |
d02b48c6 RE |
9 | |
10 | #include <stdio.h> | |
11 | #include <time.h> | |
b39fc560 | 12 | #include "internal/cryptlib.h" |
706457b7 | 13 | #include "bn_local.h" |
d02b48c6 | 14 | |
0f113f3e MC |
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. | |
d02b48c6 RE |
19 | */ |
20 | #include "bn_prime.h" | |
21 | ||
3ce0566d BE |
22 | static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
23 | BN_CTX *ctx); | |
28b4880b BE |
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); | |
42619397 KR |
27 | static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, |
28 | int do_trial_division, BN_GENCB *cb); | |
eb952088 | 29 | |
3ce0566d BE |
30 | #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x)) |
31 | ||
8240d5fa SL |
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 | ||
94553e85 | 65 | const BIGNUM *ossl_bn_get0_small_factors(void) |
8240d5fa SL |
66 | { |
67 | return &_bignum_small_prime_factors; | |
68 | } | |
69 | ||
6c4ae41f KR |
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 | ||
42619397 KR |
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 | ||
e9224c71 | 101 | int BN_GENCB_call(BN_GENCB *cb, int a, int b) |
0f113f3e MC |
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 | } | |
e9224c71 | 122 | |
2934be91 MC |
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) | |
0f113f3e MC |
126 | { |
127 | BIGNUM *t; | |
128 | int found = 0; | |
129 | int i, j, c1 = 0; | |
8e704858 | 130 | prime_t *mods = NULL; |
42619397 | 131 | int checks = bn_mr_min_checks(bits); |
0f113f3e MC |
132 | |
133 | if (bits < 2) { | |
134 | /* There are no prime numbers this small. */ | |
9311d0c4 | 135 | ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); |
0f113f3e | 136 | return 0; |
291f616c BE |
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 | */ | |
9311d0c4 | 143 | ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); |
0f113f3e MC |
144 | return 0; |
145 | } | |
146 | ||
d71eb667 | 147 | mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); |
48116c2d AG |
148 | if (mods == NULL) { |
149 | ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); | |
150 | return 0; | |
151 | } | |
d71eb667 | 152 | |
0f113f3e MC |
153 | BN_CTX_start(ctx); |
154 | t = BN_CTX_get(ctx); | |
e8e55976 | 155 | if (t == NULL) |
0f113f3e MC |
156 | goto err; |
157 | loop: | |
158 | /* make a random number and set the top and bottom bits */ | |
159 | if (add == NULL) { | |
3ce0566d | 160 | if (!probable_prime(ret, bits, safe, mods, ctx)) |
0f113f3e MC |
161 | goto err; |
162 | } else { | |
28b4880b BE |
163 | if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx)) |
164 | goto err; | |
0f113f3e | 165 | } |
d70a5627 | 166 | |
0f113f3e MC |
167 | if (!BN_GENCB_call(cb, 0, c1++)) |
168 | /* aborted */ | |
169 | goto err; | |
170 | ||
171 | if (!safe) { | |
42619397 | 172 | i = bn_is_prime_int(ret, checks, ctx, 0, cb); |
0f113f3e MC |
173 | if (i == -1) |
174 | goto err; | |
175 | if (i == 0) | |
176 | goto loop; | |
177 | } else { | |
178 | /* | |
179 | * for "safe prime" generation, check that (p-1)/2 is prime. Since a | |
180 | * prime is odd, We just need to divide by 2 | |
181 | */ | |
182 | if (!BN_rshift1(t, ret)) | |
183 | goto err; | |
184 | ||
185 | for (i = 0; i < checks; i++) { | |
42619397 | 186 | j = bn_is_prime_int(ret, 1, ctx, 0, cb); |
0f113f3e MC |
187 | if (j == -1) |
188 | goto err; | |
189 | if (j == 0) | |
190 | goto loop; | |
191 | ||
42619397 | 192 | j = bn_is_prime_int(t, 1, ctx, 0, cb); |
0f113f3e MC |
193 | if (j == -1) |
194 | goto err; | |
195 | if (j == 0) | |
196 | goto loop; | |
197 | ||
198 | if (!BN_GENCB_call(cb, 2, c1 - 1)) | |
199 | goto err; | |
200 | /* We have a safe prime test pass */ | |
201 | } | |
202 | } | |
203 | /* we have a prime :-) */ | |
204 | found = 1; | |
205 | err: | |
8e704858 | 206 | OPENSSL_free(mods); |
ce1415ed | 207 | BN_CTX_end(ctx); |
0f113f3e MC |
208 | bn_check_top(ret); |
209 | return found; | |
210 | } | |
211 | ||
f844f9eb | 212 | #ifndef FIPS_MODULE |
2934be91 MC |
213 | int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, |
214 | const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) | |
215 | { | |
216 | BN_CTX *ctx = BN_CTX_new(); | |
217 | int retval; | |
218 | ||
219 | if (ctx == NULL) | |
220 | return 0; | |
221 | ||
222 | retval = BN_generate_prime_ex2(ret, bits, safe, add, rem, cb, ctx); | |
223 | ||
224 | BN_CTX_free(ctx); | |
225 | return retval; | |
226 | } | |
227 | #endif | |
228 | ||
936c2b9e | 229 | #ifndef OPENSSL_NO_DEPRECATED_3_0 |
0f113f3e MC |
230 | int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, |
231 | BN_GENCB *cb) | |
232 | { | |
36ec749f | 233 | return ossl_bn_check_prime(a, checks, ctx_passed, 0, cb); |
0f113f3e | 234 | } |
e74231ed | 235 | |
2934be91 | 236 | int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx, |
0f113f3e | 237 | int do_trial_division, BN_GENCB *cb) |
42619397 | 238 | { |
36ec749f | 239 | return ossl_bn_check_prime(w, checks, ctx, do_trial_division, cb); |
42619397 KR |
240 | } |
241 | #endif | |
242 | ||
243 | /* Wrapper around bn_is_prime_int that sets the minimum number of checks */ | |
36ec749f P |
244 | int ossl_bn_check_prime(const BIGNUM *w, int checks, BN_CTX *ctx, |
245 | int do_trial_division, BN_GENCB *cb) | |
42619397 KR |
246 | { |
247 | int min_checks = bn_mr_min_checks(BN_num_bits(w)); | |
248 | ||
249 | if (checks < min_checks) | |
250 | checks = min_checks; | |
251 | ||
252 | return bn_is_prime_int(w, checks, ctx, do_trial_division, cb); | |
253 | } | |
254 | ||
255 | int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb) | |
256 | { | |
36ec749f | 257 | return ossl_bn_check_prime(p, 0, ctx, 1, cb); |
42619397 KR |
258 | } |
259 | ||
260 | /* | |
261 | * Tests that |w| is probably prime | |
262 | * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. | |
263 | * | |
264 | * Returns 0 when composite, 1 when probable prime, -1 on error. | |
265 | */ | |
266 | static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, | |
267 | int do_trial_division, BN_GENCB *cb) | |
0f113f3e | 268 | { |
8240d5fa | 269 | int i, status, ret = -1; |
f844f9eb | 270 | #ifndef FIPS_MODULE |
2934be91 MC |
271 | BN_CTX *ctxlocal = NULL; |
272 | #else | |
273 | ||
274 | if (ctx == NULL) | |
275 | return -1; | |
276 | #endif | |
7d79d13a | 277 | |
8240d5fa SL |
278 | /* w must be bigger than 1 */ |
279 | if (BN_cmp(w, BN_value_one()) <= 0) | |
0f113f3e MC |
280 | return 0; |
281 | ||
8240d5fa SL |
282 | /* w must be odd */ |
283 | if (BN_is_odd(w)) { | |
284 | /* Take care of the really small prime 3 */ | |
285 | if (BN_is_word(w, 3)) | |
286 | return 1; | |
287 | } else { | |
288 | /* 2 is the only even prime */ | |
289 | return BN_is_word(w, 2); | |
290 | } | |
0f113f3e MC |
291 | |
292 | /* first look for small factors */ | |
0f113f3e | 293 | if (do_trial_division) { |
6c4ae41f KR |
294 | int trial_divisions = calc_trial_divisions(BN_num_bits(w)); |
295 | ||
296 | for (i = 1; i < trial_divisions; i++) { | |
8240d5fa | 297 | BN_ULONG mod = BN_mod_word(w, primes[i]); |
d70a5627 | 298 | if (mod == (BN_ULONG)-1) |
8240d5fa | 299 | return -1; |
d70a5627 | 300 | if (mod == 0) |
8240d5fa | 301 | return BN_is_word(w, primes[i]); |
d70a5627 | 302 | } |
0f113f3e | 303 | if (!BN_GENCB_call(cb, 1, -1)) |
8240d5fa | 304 | return -1; |
0f113f3e | 305 | } |
f844f9eb | 306 | #ifndef FIPS_MODULE |
2934be91 | 307 | if (ctx == NULL && (ctxlocal = ctx = BN_CTX_new()) == NULL) |
0f113f3e | 308 | goto err; |
2934be91 | 309 | #endif |
0f113f3e | 310 | |
94553e85 | 311 | ret = ossl_bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status); |
8240d5fa | 312 | if (!ret) |
0f113f3e | 313 | goto err; |
8240d5fa SL |
314 | ret = (status == BN_PRIMETEST_PROBABLY_PRIME); |
315 | err: | |
f844f9eb | 316 | #ifndef FIPS_MODULE |
2934be91 MC |
317 | BN_CTX_free(ctxlocal); |
318 | #endif | |
8240d5fa SL |
319 | return ret; |
320 | } | |
321 | ||
322 | /* | |
323 | * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test. | |
324 | * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero). | |
325 | * The Step numbers listed in the code refer to the enhanced case. | |
326 | * | |
327 | * if enhanced is set, then status returns one of the following: | |
328 | * BN_PRIMETEST_PROBABLY_PRIME | |
329 | * BN_PRIMETEST_COMPOSITE_WITH_FACTOR | |
330 | * BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME | |
331 | * if enhanced is zero, then status returns either | |
332 | * BN_PRIMETEST_PROBABLY_PRIME or | |
333 | * BN_PRIMETEST_COMPOSITE | |
334 | * | |
335 | * returns 0 if there was an error, otherwise it returns 1. | |
336 | */ | |
94553e85 SL |
337 | int ossl_bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx, |
338 | BN_GENCB *cb, int enhanced, int *status) | |
8240d5fa SL |
339 | { |
340 | int i, j, a, ret = 0; | |
341 | BIGNUM *g, *w1, *w3, *x, *m, *z, *b; | |
342 | BN_MONT_CTX *mont = NULL; | |
0f113f3e | 343 | |
8240d5fa SL |
344 | /* w must be odd */ |
345 | if (!BN_is_odd(w)) | |
346 | return 0; | |
347 | ||
348 | BN_CTX_start(ctx); | |
349 | g = BN_CTX_get(ctx); | |
350 | w1 = BN_CTX_get(ctx); | |
351 | w3 = BN_CTX_get(ctx); | |
352 | x = BN_CTX_get(ctx); | |
353 | m = BN_CTX_get(ctx); | |
354 | z = BN_CTX_get(ctx); | |
355 | b = BN_CTX_get(ctx); | |
356 | ||
357 | if (!(b != NULL | |
358 | /* w1 := w - 1 */ | |
359 | && BN_copy(w1, w) | |
360 | && BN_sub_word(w1, 1) | |
361 | /* w3 := w - 3 */ | |
362 | && BN_copy(w3, w) | |
363 | && BN_sub_word(w3, 3))) | |
0f113f3e | 364 | goto err; |
8240d5fa SL |
365 | |
366 | /* check w is larger than 3, otherwise the random b will be too small */ | |
367 | if (BN_is_zero(w3) || BN_is_negative(w3)) | |
0f113f3e | 368 | goto err; |
0f113f3e | 369 | |
8240d5fa SL |
370 | /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */ |
371 | a = 1; | |
372 | while (!BN_is_bit_set(w1, a)) | |
373 | a++; | |
374 | /* (Step 2) m = (w-1) / 2^a */ | |
375 | if (!BN_rshift(m, w1, a)) | |
0f113f3e MC |
376 | goto err; |
377 | ||
8b24f942 | 378 | /* Montgomery setup for computations mod a */ |
0f113f3e | 379 | mont = BN_MONT_CTX_new(); |
8240d5fa | 380 | if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx)) |
0f113f3e MC |
381 | goto err; |
382 | ||
42619397 KR |
383 | if (iterations == 0) |
384 | iterations = bn_mr_min_checks(BN_num_bits(w)); | |
0f113f3e | 385 | |
8240d5fa SL |
386 | /* (Step 4) */ |
387 | for (i = 0; i < iterations; ++i) { | |
388 | /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */ | |
5cbd2ea3 | 389 | if (!BN_priv_rand_range_ex(b, w3, 0, ctx) |
2934be91 | 390 | || !BN_add_word(b, 2)) /* 1 < b < w-1 */ |
0f113f3e | 391 | goto err; |
8240d5fa SL |
392 | |
393 | if (enhanced) { | |
394 | /* (Step 4.3) */ | |
395 | if (!BN_gcd(g, b, w, ctx)) | |
396 | goto err; | |
397 | /* (Step 4.4) */ | |
398 | if (!BN_is_one(g)) { | |
399 | *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; | |
400 | ret = 1; | |
401 | goto err; | |
402 | } | |
403 | } | |
404 | /* (Step 4.5) z = b^m mod w */ | |
405 | if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) | |
0f113f3e | 406 | goto err; |
8240d5fa SL |
407 | /* (Step 4.6) if (z = 1 or z = w-1) */ |
408 | if (BN_is_one(z) || BN_cmp(z, w1) == 0) | |
409 | goto outer_loop; | |
410 | /* (Step 4.7) for j = 1 to a-1 */ | |
411 | for (j = 1; j < a ; ++j) { | |
412 | /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */ | |
413 | if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) | |
414 | goto err; | |
415 | /* (Step 4.7.3) */ | |
416 | if (BN_cmp(z, w1) == 0) | |
417 | goto outer_loop; | |
418 | /* (Step 4.7.4) */ | |
419 | if (BN_is_one(z)) | |
420 | goto composite; | |
0f113f3e | 421 | } |
8240d5fa SL |
422 | /* At this point z = b^((w-1)/2) mod w */ |
423 | /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */ | |
424 | if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) | |
425 | goto err; | |
426 | /* (Step 4.10) */ | |
427 | if (BN_is_one(z)) | |
428 | goto composite; | |
429 | /* (Step 4.11) x = b^(w-1) mod w */ | |
430 | if (!BN_copy(x, z)) | |
431 | goto err; | |
432 | composite: | |
433 | if (enhanced) { | |
434 | /* (Step 4.1.2) g = GCD(x-1, w) */ | |
435 | if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx)) | |
436 | goto err; | |
437 | /* (Steps 4.1.3 - 4.1.4) */ | |
438 | if (BN_is_one(g)) | |
439 | *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME; | |
440 | else | |
441 | *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; | |
442 | } else { | |
443 | *status = BN_PRIMETEST_COMPOSITE; | |
444 | } | |
445 | ret = 1; | |
446 | goto err; | |
447 | outer_loop: ; | |
448 | /* (Step 4.1.5) */ | |
3e3dcf9a KR |
449 | if (!BN_GENCB_call(cb, 1, i)) |
450 | goto err; | |
0f113f3e | 451 | } |
8240d5fa SL |
452 | /* (Step 5) */ |
453 | *status = BN_PRIMETEST_PROBABLY_PRIME; | |
0f113f3e | 454 | ret = 1; |
8240d5fa SL |
455 | err: |
456 | BN_clear(g); | |
457 | BN_clear(w1); | |
458 | BN_clear(w3); | |
459 | BN_clear(x); | |
460 | BN_clear(m); | |
461 | BN_clear(z); | |
462 | BN_clear(b); | |
463 | BN_CTX_end(ctx); | |
23a1d5e9 | 464 | BN_MONT_CTX_free(mont); |
26a7d938 | 465 | return ret; |
0f113f3e | 466 | } |
a87030a1 | 467 | |
6c4ae41f KR |
468 | /* |
469 | * Generate a random number of |bits| bits that is probably prime by sieving. | |
470 | * If |safe| != 0, it generates a safe prime. | |
471 | * |mods| is a preallocated array that gets reused when called again. | |
472 | * | |
473 | * The probably prime is saved in |rnd|. | |
474 | * | |
475 | * Returns 1 on success and 0 on error. | |
476 | */ | |
3ce0566d BE |
477 | static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
478 | BN_CTX *ctx) | |
0f113f3e MC |
479 | { |
480 | int i; | |
0f113f3e | 481 | BN_ULONG delta; |
6c4ae41f KR |
482 | int trial_divisions = calc_trial_divisions(bits); |
483 | BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1]; | |
0f113f3e MC |
484 | |
485 | again: | |
5cbd2ea3 P |
486 | if (!BN_priv_rand_ex(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD, 0, |
487 | ctx)) | |
26a7d938 | 488 | return 0; |
3ce0566d BE |
489 | if (safe && !BN_set_bit(rnd, 1)) |
490 | return 0; | |
0f113f3e | 491 | /* we now have a random number 'rnd' to test. */ |
6c4ae41f | 492 | for (i = 1; i < trial_divisions; i++) { |
d70a5627 DB |
493 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); |
494 | if (mod == (BN_ULONG)-1) | |
495 | return 0; | |
496 | mods[i] = (prime_t) mod; | |
497 | } | |
0f113f3e MC |
498 | delta = 0; |
499 | loop: | |
6c4ae41f | 500 | for (i = 1; i < trial_divisions; i++) { |
3ce0566d BE |
501 | /* |
502 | * check that rnd is a prime and also that | |
503 | * gcd(rnd-1,primes) == 1 (except for 2) | |
504 | * do the second check only if we are interested in safe primes | |
505 | * in the case that the candidate prime is a single word then | |
506 | * we check only the primes up to sqrt(rnd) | |
50e735f9 | 507 | */ |
3ce0566d BE |
508 | if (bits <= 31 && delta <= 0x7fffffff |
509 | && square(primes[i]) > BN_get_word(rnd) + delta) | |
510 | break; | |
511 | if (safe ? (mods[i] + delta) % primes[i] <= 1 | |
512 | : (mods[i] + delta) % primes[i] == 0) { | |
513 | delta += safe ? 4 : 2; | |
514 | if (delta > maxdelta) | |
515 | goto again; | |
516 | goto loop; | |
0f113f3e MC |
517 | } |
518 | } | |
519 | if (!BN_add_word(rnd, delta)) | |
26a7d938 | 520 | return 0; |
0f113f3e MC |
521 | if (BN_num_bits(rnd) != bits) |
522 | goto again; | |
523 | bn_check_top(rnd); | |
208fb891 | 524 | return 1; |
0f113f3e | 525 | } |
d02b48c6 | 526 | |
6c4ae41f KR |
527 | /* |
528 | * Generate a random number |rnd| of |bits| bits that is probably prime | |
529 | * and satisfies |rnd| % |add| == |rem| by sieving. | |
530 | * If |safe| != 0, it generates a safe prime. | |
531 | * |mods| is a preallocated array that gets reused when called again. | |
532 | * | |
533 | * Returns 1 on success and 0 on error. | |
534 | */ | |
28b4880b BE |
535 | static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
536 | const BIGNUM *add, const BIGNUM *rem, | |
537 | BN_CTX *ctx) | |
0f113f3e MC |
538 | { |
539 | int i, ret = 0; | |
540 | BIGNUM *t1; | |
28b4880b | 541 | BN_ULONG delta; |
6c4ae41f KR |
542 | int trial_divisions = calc_trial_divisions(bits); |
543 | BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1]; | |
0f113f3e MC |
544 | |
545 | BN_CTX_start(ctx); | |
546 | if ((t1 = BN_CTX_get(ctx)) == NULL) | |
547 | goto err; | |
548 | ||
28b4880b BE |
549 | if (maxdelta > BN_MASK2 - BN_get_word(add)) |
550 | maxdelta = BN_MASK2 - BN_get_word(add); | |
551 | ||
552 | again: | |
5cbd2ea3 | 553 | if (!BN_rand_ex(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, 0, ctx)) |
0f113f3e MC |
554 | goto err; |
555 | ||
556 | /* we need ((rnd-rem) % add) == 0 */ | |
557 | ||
558 | if (!BN_mod(t1, rnd, add, ctx)) | |
559 | goto err; | |
560 | if (!BN_sub(rnd, rnd, t1)) | |
561 | goto err; | |
562 | if (rem == NULL) { | |
28b4880b | 563 | if (!BN_add_word(rnd, safe ? 3u : 1u)) |
0f113f3e MC |
564 | goto err; |
565 | } else { | |
566 | if (!BN_add(rnd, rnd, rem)) | |
567 | goto err; | |
568 | } | |
569 | ||
28b4880b BE |
570 | if (BN_num_bits(rnd) < bits |
571 | || BN_get_word(rnd) < (safe ? 5u : 3u)) { | |
572 | if (!BN_add(rnd, rnd, add)) | |
573 | goto err; | |
574 | } | |
0f113f3e | 575 | |
28b4880b | 576 | /* we now have a random number 'rnd' to test. */ |
6c4ae41f | 577 | for (i = 1; i < trial_divisions; i++) { |
d70a5627 DB |
578 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); |
579 | if (mod == (BN_ULONG)-1) | |
580 | goto err; | |
28b4880b | 581 | mods[i] = (prime_t) mod; |
0f113f3e | 582 | } |
28b4880b | 583 | delta = 0; |
0f113f3e | 584 | loop: |
6c4ae41f | 585 | for (i = 1; i < trial_divisions; i++) { |
28b4880b BE |
586 | /* check that rnd is a prime */ |
587 | if (bits <= 31 && delta <= 0x7fffffff | |
588 | && square(primes[i]) > BN_get_word(rnd) + delta) | |
589 | break; | |
590 | /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */ | |
591 | if (safe ? (mods[i] + delta) % primes[i] <= 1 | |
592 | : (mods[i] + delta) % primes[i] == 0) { | |
593 | delta += BN_get_word(add); | |
594 | if (delta > maxdelta) | |
595 | goto again; | |
0f113f3e MC |
596 | goto loop; |
597 | } | |
598 | } | |
28b4880b BE |
599 | if (!BN_add_word(rnd, delta)) |
600 | goto err; | |
0f113f3e MC |
601 | ret = 1; |
602 | ||
603 | err: | |
604 | BN_CTX_end(ctx); | |
28b4880b | 605 | bn_check_top(rnd); |
26a7d938 | 606 | return ret; |
0f113f3e | 607 | } |