]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
8240d5fa | 2 | * Copyright 1995-2019 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" |
d02b48c6 | 13 | #include "bn_lcl.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 | ||
8e704858 | 22 | static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods); |
76aa0ddc | 23 | static int probable_prime_dh_safe(BIGNUM *rnd, int bits, |
0f113f3e MC |
24 | const BIGNUM *add, const BIGNUM *rem, |
25 | BN_CTX *ctx); | |
eb952088 | 26 | |
8240d5fa SL |
27 | #if BN_BITS2 == 64 |
28 | # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo | |
29 | #else | |
30 | # define BN_DEF(lo, hi) lo, hi | |
31 | #endif | |
32 | ||
33 | /* | |
34 | * See SP800 89 5.3.3 (Step f) | |
35 | * The product of the set of primes ranging from 3 to 751 | |
36 | * Generated using process in test/bn_internal_test.c test_bn_small_factors(). | |
37 | * This includes 751 (which is not currently included in SP 800-89). | |
38 | */ | |
39 | static const BN_ULONG small_prime_factors[] = { | |
40 | BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6), | |
41 | BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3), | |
42 | BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817), | |
43 | BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2), | |
44 | BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3), | |
45 | BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28), | |
46 | BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112), | |
47 | BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460), | |
48 | (BN_ULONG)0x000017b1 | |
49 | }; | |
50 | ||
51 | #define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors) | |
52 | static const BIGNUM _bignum_small_prime_factors = { | |
53 | (BN_ULONG *)small_prime_factors, | |
54 | BN_SMALL_PRIME_FACTORS_TOP, | |
55 | BN_SMALL_PRIME_FACTORS_TOP, | |
56 | 0, | |
57 | BN_FLG_STATIC_DATA | |
58 | }; | |
59 | ||
60 | const BIGNUM *bn_get0_small_factors(void) | |
61 | { | |
62 | return &_bignum_small_prime_factors; | |
63 | } | |
64 | ||
e9224c71 | 65 | int BN_GENCB_call(BN_GENCB *cb, int a, int b) |
0f113f3e MC |
66 | { |
67 | /* No callback means continue */ | |
68 | if (!cb) | |
69 | return 1; | |
70 | switch (cb->ver) { | |
71 | case 1: | |
72 | /* Deprecated-style callbacks */ | |
73 | if (!cb->cb.cb_1) | |
74 | return 1; | |
75 | cb->cb.cb_1(a, b, cb->arg); | |
76 | return 1; | |
77 | case 2: | |
78 | /* New-style callbacks */ | |
79 | return cb->cb.cb_2(a, b, cb); | |
80 | default: | |
81 | break; | |
82 | } | |
83 | /* Unrecognised callback type */ | |
84 | return 0; | |
85 | } | |
e9224c71 GT |
86 | |
87 | int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, | |
0f113f3e MC |
88 | const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) |
89 | { | |
90 | BIGNUM *t; | |
91 | int found = 0; | |
92 | int i, j, c1 = 0; | |
8e704858 RS |
93 | BN_CTX *ctx = NULL; |
94 | prime_t *mods = NULL; | |
0f113f3e MC |
95 | int checks = BN_prime_checks_for_size(bits); |
96 | ||
97 | if (bits < 2) { | |
98 | /* There are no prime numbers this small. */ | |
99 | BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); | |
100 | return 0; | |
291f616c BE |
101 | } else if (add == NULL && safe && bits < 6 && bits != 3) { |
102 | /* | |
103 | * The smallest safe prime (7) is three bits. | |
104 | * But the following two safe primes with less than 6 bits (11, 23) | |
105 | * are unreachable for BN_rand with BN_RAND_TOP_TWO. | |
106 | */ | |
0f113f3e MC |
107 | BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); |
108 | return 0; | |
109 | } | |
110 | ||
d71eb667 MC |
111 | mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); |
112 | if (mods == NULL) | |
113 | goto err; | |
114 | ||
0f113f3e MC |
115 | ctx = BN_CTX_new(); |
116 | if (ctx == NULL) | |
117 | goto err; | |
118 | BN_CTX_start(ctx); | |
119 | t = BN_CTX_get(ctx); | |
e8e55976 | 120 | if (t == NULL) |
0f113f3e MC |
121 | goto err; |
122 | loop: | |
123 | /* make a random number and set the top and bottom bits */ | |
124 | if (add == NULL) { | |
8e704858 | 125 | if (!probable_prime(ret, bits, mods)) |
0f113f3e MC |
126 | goto err; |
127 | } else { | |
128 | if (safe) { | |
129 | if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) | |
130 | goto err; | |
131 | } else { | |
132 | if (!bn_probable_prime_dh(ret, bits, add, rem, ctx)) | |
133 | goto err; | |
134 | } | |
135 | } | |
d70a5627 | 136 | |
0f113f3e MC |
137 | if (!BN_GENCB_call(cb, 0, c1++)) |
138 | /* aborted */ | |
139 | goto err; | |
140 | ||
141 | if (!safe) { | |
142 | i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); | |
143 | if (i == -1) | |
144 | goto err; | |
145 | if (i == 0) | |
146 | goto loop; | |
147 | } else { | |
148 | /* | |
149 | * for "safe prime" generation, check that (p-1)/2 is prime. Since a | |
150 | * prime is odd, We just need to divide by 2 | |
151 | */ | |
152 | if (!BN_rshift1(t, ret)) | |
153 | goto err; | |
154 | ||
155 | for (i = 0; i < checks; i++) { | |
156 | j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb); | |
157 | if (j == -1) | |
158 | goto err; | |
159 | if (j == 0) | |
160 | goto loop; | |
161 | ||
162 | j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb); | |
163 | if (j == -1) | |
164 | goto err; | |
165 | if (j == 0) | |
166 | goto loop; | |
167 | ||
168 | if (!BN_GENCB_call(cb, 2, c1 - 1)) | |
169 | goto err; | |
170 | /* We have a safe prime test pass */ | |
171 | } | |
172 | } | |
173 | /* we have a prime :-) */ | |
174 | found = 1; | |
175 | err: | |
8e704858 | 176 | OPENSSL_free(mods); |
ce1415ed | 177 | BN_CTX_end(ctx); |
23a1d5e9 | 178 | BN_CTX_free(ctx); |
0f113f3e MC |
179 | bn_check_top(ret); |
180 | return found; | |
181 | } | |
182 | ||
183 | int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, | |
184 | BN_GENCB *cb) | |
185 | { | |
186 | return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); | |
187 | } | |
e74231ed | 188 | |
8240d5fa SL |
189 | /* See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. */ |
190 | int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx_passed, | |
0f113f3e MC |
191 | int do_trial_division, BN_GENCB *cb) |
192 | { | |
8240d5fa | 193 | int i, status, ret = -1; |
0f113f3e | 194 | BN_CTX *ctx = NULL; |
7d79d13a | 195 | |
8240d5fa SL |
196 | /* w must be bigger than 1 */ |
197 | if (BN_cmp(w, BN_value_one()) <= 0) | |
0f113f3e MC |
198 | return 0; |
199 | ||
8240d5fa SL |
200 | /* w must be odd */ |
201 | if (BN_is_odd(w)) { | |
202 | /* Take care of the really small prime 3 */ | |
203 | if (BN_is_word(w, 3)) | |
204 | return 1; | |
205 | } else { | |
206 | /* 2 is the only even prime */ | |
207 | return BN_is_word(w, 2); | |
208 | } | |
0f113f3e MC |
209 | |
210 | /* first look for small factors */ | |
0f113f3e | 211 | if (do_trial_division) { |
d70a5627 | 212 | for (i = 1; i < NUMPRIMES; i++) { |
8240d5fa | 213 | BN_ULONG mod = BN_mod_word(w, primes[i]); |
d70a5627 | 214 | if (mod == (BN_ULONG)-1) |
8240d5fa | 215 | return -1; |
d70a5627 | 216 | if (mod == 0) |
8240d5fa | 217 | return BN_is_word(w, primes[i]); |
d70a5627 | 218 | } |
0f113f3e | 219 | if (!BN_GENCB_call(cb, 1, -1)) |
8240d5fa | 220 | return -1; |
0f113f3e | 221 | } |
0f113f3e MC |
222 | if (ctx_passed != NULL) |
223 | ctx = ctx_passed; | |
224 | else if ((ctx = BN_CTX_new()) == NULL) | |
225 | goto err; | |
0f113f3e | 226 | |
8240d5fa SL |
227 | ret = bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status); |
228 | if (!ret) | |
0f113f3e | 229 | goto err; |
8240d5fa SL |
230 | ret = (status == BN_PRIMETEST_PROBABLY_PRIME); |
231 | err: | |
232 | if (ctx_passed == NULL) | |
233 | BN_CTX_free(ctx); | |
234 | return ret; | |
235 | } | |
236 | ||
237 | /* | |
238 | * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test. | |
239 | * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero). | |
240 | * The Step numbers listed in the code refer to the enhanced case. | |
241 | * | |
242 | * if enhanced is set, then status returns one of the following: | |
243 | * BN_PRIMETEST_PROBABLY_PRIME | |
244 | * BN_PRIMETEST_COMPOSITE_WITH_FACTOR | |
245 | * BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME | |
246 | * if enhanced is zero, then status returns either | |
247 | * BN_PRIMETEST_PROBABLY_PRIME or | |
248 | * BN_PRIMETEST_COMPOSITE | |
249 | * | |
250 | * returns 0 if there was an error, otherwise it returns 1. | |
251 | */ | |
252 | int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx, | |
253 | BN_GENCB *cb, int enhanced, int *status) | |
254 | { | |
255 | int i, j, a, ret = 0; | |
256 | BIGNUM *g, *w1, *w3, *x, *m, *z, *b; | |
257 | BN_MONT_CTX *mont = NULL; | |
0f113f3e | 258 | |
8240d5fa SL |
259 | /* w must be odd */ |
260 | if (!BN_is_odd(w)) | |
261 | return 0; | |
262 | ||
263 | BN_CTX_start(ctx); | |
264 | g = BN_CTX_get(ctx); | |
265 | w1 = BN_CTX_get(ctx); | |
266 | w3 = BN_CTX_get(ctx); | |
267 | x = BN_CTX_get(ctx); | |
268 | m = BN_CTX_get(ctx); | |
269 | z = BN_CTX_get(ctx); | |
270 | b = BN_CTX_get(ctx); | |
271 | ||
272 | if (!(b != NULL | |
273 | /* w1 := w - 1 */ | |
274 | && BN_copy(w1, w) | |
275 | && BN_sub_word(w1, 1) | |
276 | /* w3 := w - 3 */ | |
277 | && BN_copy(w3, w) | |
278 | && BN_sub_word(w3, 3))) | |
0f113f3e | 279 | goto err; |
8240d5fa SL |
280 | |
281 | /* check w is larger than 3, otherwise the random b will be too small */ | |
282 | if (BN_is_zero(w3) || BN_is_negative(w3)) | |
0f113f3e | 283 | goto err; |
0f113f3e | 284 | |
8240d5fa SL |
285 | /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */ |
286 | a = 1; | |
287 | while (!BN_is_bit_set(w1, a)) | |
288 | a++; | |
289 | /* (Step 2) m = (w-1) / 2^a */ | |
290 | if (!BN_rshift(m, w1, a)) | |
0f113f3e MC |
291 | goto err; |
292 | ||
8b24f942 | 293 | /* Montgomery setup for computations mod a */ |
0f113f3e | 294 | mont = BN_MONT_CTX_new(); |
8240d5fa | 295 | if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx)) |
0f113f3e MC |
296 | goto err; |
297 | ||
8240d5fa SL |
298 | if (iterations == BN_prime_checks) |
299 | iterations = BN_prime_checks_for_size(BN_num_bits(w)); | |
0f113f3e | 300 | |
8240d5fa SL |
301 | /* (Step 4) */ |
302 | for (i = 0; i < iterations; ++i) { | |
303 | /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */ | |
304 | if (!BN_priv_rand_range(b, w3) || !BN_add_word(b, 2)) /* 1 < b < w-1 */ | |
0f113f3e | 305 | goto err; |
8240d5fa SL |
306 | |
307 | if (enhanced) { | |
308 | /* (Step 4.3) */ | |
309 | if (!BN_gcd(g, b, w, ctx)) | |
310 | goto err; | |
311 | /* (Step 4.4) */ | |
312 | if (!BN_is_one(g)) { | |
313 | *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; | |
314 | ret = 1; | |
315 | goto err; | |
316 | } | |
317 | } | |
318 | /* (Step 4.5) z = b^m mod w */ | |
319 | if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) | |
0f113f3e | 320 | goto err; |
8240d5fa SL |
321 | /* (Step 4.6) if (z = 1 or z = w-1) */ |
322 | if (BN_is_one(z) || BN_cmp(z, w1) == 0) | |
323 | goto outer_loop; | |
324 | /* (Step 4.7) for j = 1 to a-1 */ | |
325 | for (j = 1; j < a ; ++j) { | |
326 | /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */ | |
327 | if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) | |
328 | goto err; | |
329 | /* (Step 4.7.3) */ | |
330 | if (BN_cmp(z, w1) == 0) | |
331 | goto outer_loop; | |
332 | /* (Step 4.7.4) */ | |
333 | if (BN_is_one(z)) | |
334 | goto composite; | |
0f113f3e | 335 | } |
8240d5fa SL |
336 | /* At this point z = b^((w-1)/2) mod w */ |
337 | /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */ | |
338 | if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) | |
339 | goto err; | |
340 | /* (Step 4.10) */ | |
341 | if (BN_is_one(z)) | |
342 | goto composite; | |
343 | /* (Step 4.11) x = b^(w-1) mod w */ | |
344 | if (!BN_copy(x, z)) | |
345 | goto err; | |
346 | composite: | |
347 | if (enhanced) { | |
348 | /* (Step 4.1.2) g = GCD(x-1, w) */ | |
349 | if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx)) | |
350 | goto err; | |
351 | /* (Steps 4.1.3 - 4.1.4) */ | |
352 | if (BN_is_one(g)) | |
353 | *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME; | |
354 | else | |
355 | *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; | |
356 | } else { | |
357 | *status = BN_PRIMETEST_COMPOSITE; | |
358 | } | |
359 | ret = 1; | |
360 | goto err; | |
361 | outer_loop: ; | |
362 | /* (Step 4.1.5) */ | |
3e3dcf9a KR |
363 | if (!BN_GENCB_call(cb, 1, i)) |
364 | goto err; | |
0f113f3e | 365 | } |
8240d5fa SL |
366 | /* (Step 5) */ |
367 | *status = BN_PRIMETEST_PROBABLY_PRIME; | |
0f113f3e | 368 | ret = 1; |
8240d5fa SL |
369 | err: |
370 | BN_clear(g); | |
371 | BN_clear(w1); | |
372 | BN_clear(w3); | |
373 | BN_clear(x); | |
374 | BN_clear(m); | |
375 | BN_clear(z); | |
376 | BN_clear(b); | |
377 | BN_CTX_end(ctx); | |
23a1d5e9 | 378 | BN_MONT_CTX_free(mont); |
26a7d938 | 379 | return ret; |
0f113f3e | 380 | } |
a87030a1 | 381 | |
8e704858 | 382 | static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods) |
0f113f3e MC |
383 | { |
384 | int i; | |
0f113f3e MC |
385 | BN_ULONG delta; |
386 | BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; | |
387 | char is_single_word = bits <= BN_BITS2; | |
388 | ||
389 | again: | |
4cffafe9 | 390 | /* TODO: Not all primes are private */ |
ddc6a5c8 | 391 | if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) |
26a7d938 | 392 | return 0; |
0f113f3e | 393 | /* we now have a random number 'rnd' to test. */ |
d70a5627 DB |
394 | for (i = 1; i < NUMPRIMES; i++) { |
395 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); | |
396 | if (mod == (BN_ULONG)-1) | |
397 | return 0; | |
398 | mods[i] = (prime_t) mod; | |
399 | } | |
0f113f3e MC |
400 | /* |
401 | * If bits is so small that it fits into a single word then we | |
402 | * additionally don't want to exceed that many bits. | |
403 | */ | |
404 | if (is_single_word) { | |
e4676e90 | 405 | BN_ULONG size_limit; |
02e112a8 | 406 | |
e4676e90 MC |
407 | if (bits == BN_BITS2) { |
408 | /* | |
409 | * Shifting by this much has undefined behaviour so we do it a | |
410 | * different way | |
411 | */ | |
412 | size_limit = ~((BN_ULONG)0) - BN_get_word(rnd); | |
413 | } else { | |
414 | size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1; | |
415 | } | |
0f113f3e MC |
416 | if (size_limit < maxdelta) |
417 | maxdelta = size_limit; | |
418 | } | |
419 | delta = 0; | |
420 | loop: | |
421 | if (is_single_word) { | |
422 | BN_ULONG rnd_word = BN_get_word(rnd); | |
423 | ||
50e735f9 MC |
424 | /*- |
425 | * In the case that the candidate prime is a single word then | |
426 | * we check that: | |
427 | * 1) It's greater than primes[i] because we shouldn't reject | |
428 | * 3 as being a prime number because it's a multiple of | |
429 | * three. | |
430 | * 2) That it's not a multiple of a known prime. We don't | |
431 | * check that rnd-1 is also coprime to all the known | |
432 | * primes because there aren't many small primes where | |
433 | * that's true. | |
434 | */ | |
0f113f3e MC |
435 | for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { |
436 | if ((mods[i] + delta) % primes[i] == 0) { | |
437 | delta += 2; | |
438 | if (delta > maxdelta) | |
439 | goto again; | |
440 | goto loop; | |
441 | } | |
442 | } | |
443 | } else { | |
444 | for (i = 1; i < NUMPRIMES; i++) { | |
445 | /* | |
446 | * check that rnd is not a prime and also that gcd(rnd-1,primes) | |
447 | * == 1 (except for 2) | |
448 | */ | |
449 | if (((mods[i] + delta) % primes[i]) <= 1) { | |
450 | delta += 2; | |
451 | if (delta > maxdelta) | |
452 | goto again; | |
453 | goto loop; | |
454 | } | |
455 | } | |
456 | } | |
457 | if (!BN_add_word(rnd, delta)) | |
26a7d938 | 458 | return 0; |
0f113f3e MC |
459 | if (BN_num_bits(rnd) != bits) |
460 | goto again; | |
461 | bn_check_top(rnd); | |
208fb891 | 462 | return 1; |
0f113f3e | 463 | } |
d02b48c6 | 464 | |
982c42cb | 465 | int bn_probable_prime_dh(BIGNUM *rnd, int bits, |
0f113f3e MC |
466 | const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) |
467 | { | |
468 | int i, ret = 0; | |
469 | BIGNUM *t1; | |
470 | ||
471 | BN_CTX_start(ctx); | |
472 | if ((t1 = BN_CTX_get(ctx)) == NULL) | |
473 | goto err; | |
474 | ||
4cffafe9 | 475 | if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) |
0f113f3e MC |
476 | goto err; |
477 | ||
478 | /* we need ((rnd-rem) % add) == 0 */ | |
479 | ||
480 | if (!BN_mod(t1, rnd, add, ctx)) | |
481 | goto err; | |
482 | if (!BN_sub(rnd, rnd, t1)) | |
483 | goto err; | |
484 | if (rem == NULL) { | |
485 | if (!BN_add_word(rnd, 1)) | |
486 | goto err; | |
487 | } else { | |
488 | if (!BN_add(rnd, rnd, rem)) | |
489 | goto err; | |
490 | } | |
491 | ||
492 | /* we now have a random number 'rand' to test. */ | |
493 | ||
494 | loop: | |
495 | for (i = 1; i < NUMPRIMES; i++) { | |
496 | /* check that rnd is a prime */ | |
d70a5627 DB |
497 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); |
498 | if (mod == (BN_ULONG)-1) | |
499 | goto err; | |
500 | if (mod <= 1) { | |
0f113f3e MC |
501 | if (!BN_add(rnd, rnd, add)) |
502 | goto err; | |
503 | goto loop; | |
504 | } | |
505 | } | |
506 | ret = 1; | |
507 | ||
508 | err: | |
509 | BN_CTX_end(ctx); | |
510 | bn_check_top(rnd); | |
26a7d938 | 511 | return ret; |
0f113f3e | 512 | } |
b0513819 | 513 | |
020fc820 | 514 | static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, |
0f113f3e MC |
515 | const BIGNUM *rem, BN_CTX *ctx) |
516 | { | |
517 | int i, ret = 0; | |
518 | BIGNUM *t1, *qadd, *q; | |
519 | ||
520 | bits--; | |
521 | BN_CTX_start(ctx); | |
522 | t1 = BN_CTX_get(ctx); | |
523 | q = BN_CTX_get(ctx); | |
524 | qadd = BN_CTX_get(ctx); | |
525 | if (qadd == NULL) | |
526 | goto err; | |
527 | ||
528 | if (!BN_rshift1(qadd, padd)) | |
529 | goto err; | |
530 | ||
4cffafe9 | 531 | if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) |
0f113f3e MC |
532 | goto err; |
533 | ||
534 | /* we need ((rnd-rem) % add) == 0 */ | |
535 | if (!BN_mod(t1, q, qadd, ctx)) | |
536 | goto err; | |
537 | if (!BN_sub(q, q, t1)) | |
538 | goto err; | |
539 | if (rem == NULL) { | |
540 | if (!BN_add_word(q, 1)) | |
541 | goto err; | |
542 | } else { | |
543 | if (!BN_rshift1(t1, rem)) | |
544 | goto err; | |
545 | if (!BN_add(q, q, t1)) | |
546 | goto err; | |
547 | } | |
548 | ||
549 | /* we now have a random number 'rand' to test. */ | |
550 | if (!BN_lshift1(p, q)) | |
551 | goto err; | |
552 | if (!BN_add_word(p, 1)) | |
553 | goto err; | |
554 | ||
555 | loop: | |
556 | for (i = 1; i < NUMPRIMES; i++) { | |
557 | /* check that p and q are prime */ | |
558 | /* | |
559 | * check that for p and q gcd(p-1,primes) == 1 (except for 2) | |
560 | */ | |
d70a5627 DB |
561 | BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); |
562 | BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); | |
563 | if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) | |
564 | goto err; | |
565 | if (pmod == 0 || qmod == 0) { | |
0f113f3e MC |
566 | if (!BN_add(p, p, padd)) |
567 | goto err; | |
568 | if (!BN_add(q, q, qadd)) | |
569 | goto err; | |
570 | goto loop; | |
571 | } | |
572 | } | |
573 | ret = 1; | |
574 | ||
575 | err: | |
576 | BN_CTX_end(ctx); | |
577 | bn_check_top(p); | |
26a7d938 | 578 | return ret; |
0f113f3e | 579 | } |