]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
35fd9953 | 2 | * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved. |
4f22f405 RS |
3 | * |
4 | * Licensed under the OpenSSL license (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 | |
bfe30e4d | 8 | */ |
d02b48c6 RE |
9 | |
10 | #include <stdio.h> | |
11 | #include <time.h> | |
b39fc560 | 12 | #include "internal/cryptlib.h" |
b5acbf91 | 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 | ||
7999c65c | 22 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
0f113f3e MC |
23 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, |
24 | BN_MONT_CTX *mont); | |
7eccef21 | 25 | static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods); |
0032bfea BE |
26 | static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
27 | const BIGNUM *add, const BIGNUM *rem, | |
28 | BN_CTX *ctx); | |
eb952088 | 29 | |
7eccef21 BE |
30 | #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x)) |
31 | ||
e9224c71 | 32 | int BN_GENCB_call(BN_GENCB *cb, int a, int b) |
0f113f3e MC |
33 | { |
34 | /* No callback means continue */ | |
35 | if (!cb) | |
36 | return 1; | |
37 | switch (cb->ver) { | |
38 | case 1: | |
39 | /* Deprecated-style callbacks */ | |
40 | if (!cb->cb.cb_1) | |
41 | return 1; | |
42 | cb->cb.cb_1(a, b, cb->arg); | |
43 | return 1; | |
44 | case 2: | |
45 | /* New-style callbacks */ | |
46 | return cb->cb.cb_2(a, b, cb); | |
47 | default: | |
48 | break; | |
49 | } | |
50 | /* Unrecognised callback type */ | |
51 | return 0; | |
52 | } | |
e9224c71 GT |
53 | |
54 | int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, | |
0f113f3e MC |
55 | const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) |
56 | { | |
57 | BIGNUM *t; | |
58 | int found = 0; | |
59 | int i, j, c1 = 0; | |
8e704858 RS |
60 | BN_CTX *ctx = NULL; |
61 | prime_t *mods = NULL; | |
0f113f3e MC |
62 | int checks = BN_prime_checks_for_size(bits); |
63 | ||
64 | if (bits < 2) { | |
65 | /* There are no prime numbers this small. */ | |
66 | BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); | |
67 | return 0; | |
9fd44200 BE |
68 | } else if (add == NULL && safe && bits < 6 && bits != 3) { |
69 | /* | |
70 | * The smallest safe prime (7) is three bits. | |
71 | * But the following two safe primes with less than 6 bits (11, 23) | |
72 | * are unreachable for BN_rand with BN_RAND_TOP_TWO. | |
73 | */ | |
0f113f3e MC |
74 | BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); |
75 | return 0; | |
76 | } | |
77 | ||
d71eb667 MC |
78 | mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); |
79 | if (mods == NULL) | |
80 | goto err; | |
81 | ||
0f113f3e MC |
82 | ctx = BN_CTX_new(); |
83 | if (ctx == NULL) | |
84 | goto err; | |
85 | BN_CTX_start(ctx); | |
86 | t = BN_CTX_get(ctx); | |
e8e55976 | 87 | if (t == NULL) |
0f113f3e MC |
88 | goto err; |
89 | loop: | |
90 | /* make a random number and set the top and bottom bits */ | |
91 | if (add == NULL) { | |
7eccef21 | 92 | if (!probable_prime(ret, bits, safe, mods)) |
0f113f3e MC |
93 | goto err; |
94 | } else { | |
0032bfea BE |
95 | if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx)) |
96 | goto err; | |
0f113f3e | 97 | } |
d70a5627 | 98 | |
0f113f3e MC |
99 | if (!BN_GENCB_call(cb, 0, c1++)) |
100 | /* aborted */ | |
101 | goto err; | |
102 | ||
103 | if (!safe) { | |
104 | i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); | |
105 | if (i == -1) | |
106 | goto err; | |
107 | if (i == 0) | |
108 | goto loop; | |
109 | } else { | |
110 | /* | |
111 | * for "safe prime" generation, check that (p-1)/2 is prime. Since a | |
112 | * prime is odd, We just need to divide by 2 | |
113 | */ | |
114 | if (!BN_rshift1(t, ret)) | |
115 | goto err; | |
116 | ||
117 | for (i = 0; i < checks; i++) { | |
118 | j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb); | |
119 | if (j == -1) | |
120 | goto err; | |
121 | if (j == 0) | |
122 | goto loop; | |
123 | ||
124 | j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb); | |
125 | if (j == -1) | |
126 | goto err; | |
127 | if (j == 0) | |
128 | goto loop; | |
129 | ||
130 | if (!BN_GENCB_call(cb, 2, c1 - 1)) | |
131 | goto err; | |
132 | /* We have a safe prime test pass */ | |
133 | } | |
134 | } | |
135 | /* we have a prime :-) */ | |
136 | found = 1; | |
137 | err: | |
8e704858 | 138 | OPENSSL_free(mods); |
c8a9fa69 | 139 | BN_CTX_end(ctx); |
23a1d5e9 | 140 | BN_CTX_free(ctx); |
0f113f3e MC |
141 | bn_check_top(ret); |
142 | return found; | |
143 | } | |
144 | ||
145 | int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, | |
146 | BN_GENCB *cb) | |
147 | { | |
148 | return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); | |
149 | } | |
e74231ed | 150 | |
e9224c71 | 151 | int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, |
0f113f3e MC |
152 | int do_trial_division, BN_GENCB *cb) |
153 | { | |
154 | int i, j, ret = -1; | |
155 | int k; | |
156 | BN_CTX *ctx = NULL; | |
7d79d13a | 157 | BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */ |
0f113f3e | 158 | BN_MONT_CTX *mont = NULL; |
0f113f3e | 159 | |
7d79d13a SL |
160 | /* Take care of the really small primes 2 & 3 */ |
161 | if (BN_is_word(a, 2) || BN_is_word(a, 3)) | |
162 | return 1; | |
163 | ||
164 | /* Check odd and bigger than 1 */ | |
165 | if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0) | |
0f113f3e MC |
166 | return 0; |
167 | ||
168 | if (checks == BN_prime_checks) | |
169 | checks = BN_prime_checks_for_size(BN_num_bits(a)); | |
170 | ||
171 | /* first look for small factors */ | |
0f113f3e | 172 | if (do_trial_division) { |
d70a5627 DB |
173 | for (i = 1; i < NUMPRIMES; i++) { |
174 | BN_ULONG mod = BN_mod_word(a, primes[i]); | |
175 | if (mod == (BN_ULONG)-1) | |
176 | goto err; | |
177 | if (mod == 0) | |
6e64c560 | 178 | return BN_is_word(a, primes[i]); |
d70a5627 | 179 | } |
0f113f3e MC |
180 | if (!BN_GENCB_call(cb, 1, -1)) |
181 | goto err; | |
182 | } | |
183 | ||
184 | if (ctx_passed != NULL) | |
185 | ctx = ctx_passed; | |
186 | else if ((ctx = BN_CTX_new()) == NULL) | |
187 | goto err; | |
188 | BN_CTX_start(ctx); | |
189 | ||
0f113f3e | 190 | A1 = BN_CTX_get(ctx); |
7d79d13a | 191 | A3 = BN_CTX_get(ctx); |
0f113f3e MC |
192 | A1_odd = BN_CTX_get(ctx); |
193 | check = BN_CTX_get(ctx); | |
194 | if (check == NULL) | |
195 | goto err; | |
196 | ||
8b24f942 | 197 | /* compute A1 := a - 1 */ |
7d79d13a | 198 | if (!BN_copy(A1, a) || !BN_sub_word(A1, 1)) |
0f113f3e | 199 | goto err; |
7d79d13a SL |
200 | /* compute A3 := a - 3 */ |
201 | if (!BN_copy(A3, a) || !BN_sub_word(A3, 3)) | |
0f113f3e | 202 | goto err; |
0f113f3e MC |
203 | |
204 | /* write A1 as A1_odd * 2^k */ | |
205 | k = 1; | |
206 | while (!BN_is_bit_set(A1, k)) | |
207 | k++; | |
208 | if (!BN_rshift(A1_odd, A1, k)) | |
209 | goto err; | |
210 | ||
8b24f942 | 211 | /* Montgomery setup for computations mod a */ |
0f113f3e MC |
212 | mont = BN_MONT_CTX_new(); |
213 | if (mont == NULL) | |
214 | goto err; | |
8b24f942 | 215 | if (!BN_MONT_CTX_set(mont, a, ctx)) |
0f113f3e MC |
216 | goto err; |
217 | ||
218 | for (i = 0; i < checks; i++) { | |
7d79d13a SL |
219 | /* 1 < check < a-1 */ |
220 | if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2)) | |
0f113f3e | 221 | goto err; |
0f113f3e | 222 | |
8b24f942 | 223 | j = witness(check, a, A1, A1_odd, k, ctx, mont); |
0f113f3e MC |
224 | if (j == -1) |
225 | goto err; | |
226 | if (j) { | |
227 | ret = 0; | |
228 | goto err; | |
229 | } | |
230 | if (!BN_GENCB_call(cb, 1, i)) | |
231 | goto err; | |
232 | } | |
233 | ret = 1; | |
234 | err: | |
235 | if (ctx != NULL) { | |
236 | BN_CTX_end(ctx); | |
237 | if (ctx_passed == NULL) | |
238 | BN_CTX_free(ctx); | |
239 | } | |
23a1d5e9 | 240 | BN_MONT_CTX_free(mont); |
0f113f3e | 241 | |
26a7d938 | 242 | return ret; |
0f113f3e | 243 | } |
a87030a1 | 244 | |
7999c65c | 245 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
0f113f3e MC |
246 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, |
247 | BN_MONT_CTX *mont) | |
248 | { | |
249 | if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ | |
250 | return -1; | |
251 | if (BN_is_one(w)) | |
252 | return 0; /* probably prime */ | |
253 | if (BN_cmp(w, a1) == 0) | |
254 | return 0; /* w == -1 (mod a), 'a' is probably prime */ | |
255 | while (--k) { | |
256 | if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ | |
257 | return -1; | |
258 | if (BN_is_one(w)) | |
259 | return 1; /* 'a' is composite, otherwise a previous 'w' | |
260 | * would have been == -1 (mod 'a') */ | |
261 | if (BN_cmp(w, a1) == 0) | |
262 | return 0; /* w == -1 (mod a), 'a' is probably prime */ | |
263 | } | |
264 | /* | |
265 | * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and | |
266 | * it is neither -1 nor +1 -- so 'a' cannot be prime | |
267 | */ | |
268 | bn_check_top(w); | |
269 | return 1; | |
270 | } | |
d02b48c6 | 271 | |
7eccef21 | 272 | static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods) |
0f113f3e MC |
273 | { |
274 | int i; | |
0f113f3e MC |
275 | BN_ULONG delta; |
276 | BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; | |
0f113f3e MC |
277 | |
278 | again: | |
4cffafe9 | 279 | /* TODO: Not all primes are private */ |
ddc6a5c8 | 280 | if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) |
26a7d938 | 281 | return 0; |
7eccef21 BE |
282 | if (safe && !BN_set_bit(rnd, 1)) |
283 | return 0; | |
0f113f3e | 284 | /* we now have a random number 'rnd' to test. */ |
d70a5627 DB |
285 | for (i = 1; i < NUMPRIMES; i++) { |
286 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); | |
287 | if (mod == (BN_ULONG)-1) | |
288 | return 0; | |
289 | mods[i] = (prime_t) mod; | |
290 | } | |
0f113f3e MC |
291 | delta = 0; |
292 | loop: | |
7eccef21 BE |
293 | for (i = 1; i < NUMPRIMES; i++) { |
294 | /* | |
295 | * check that rnd is a prime and also that | |
296 | * gcd(rnd-1,primes) == 1 (except for 2) | |
297 | * do the second check only if we are interested in safe primes | |
298 | * in the case that the candidate prime is a single word then | |
299 | * we check only the primes up to sqrt(rnd) | |
50e735f9 | 300 | */ |
7eccef21 BE |
301 | if (bits <= 31 && delta <= 0x7fffffff |
302 | && square(primes[i]) > BN_get_word(rnd) + delta) | |
303 | break; | |
304 | if (safe ? (mods[i] + delta) % primes[i] <= 1 | |
305 | : (mods[i] + delta) % primes[i] == 0) { | |
306 | delta += safe ? 4 : 2; | |
307 | if (delta > maxdelta) | |
308 | goto again; | |
309 | goto loop; | |
0f113f3e MC |
310 | } |
311 | } | |
312 | if (!BN_add_word(rnd, delta)) | |
26a7d938 | 313 | return 0; |
0f113f3e MC |
314 | if (BN_num_bits(rnd) != bits) |
315 | goto again; | |
316 | bn_check_top(rnd); | |
208fb891 | 317 | return 1; |
0f113f3e | 318 | } |
d02b48c6 | 319 | |
0032bfea BE |
320 | static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, |
321 | const BIGNUM *add, const BIGNUM *rem, | |
322 | BN_CTX *ctx) | |
0f113f3e MC |
323 | { |
324 | int i, ret = 0; | |
325 | BIGNUM *t1; | |
0032bfea BE |
326 | BN_ULONG delta; |
327 | BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; | |
0f113f3e MC |
328 | |
329 | BN_CTX_start(ctx); | |
330 | if ((t1 = BN_CTX_get(ctx)) == NULL) | |
331 | goto err; | |
332 | ||
0032bfea BE |
333 | if (maxdelta > BN_MASK2 - BN_get_word(add)) |
334 | maxdelta = BN_MASK2 - BN_get_word(add); | |
335 | ||
336 | again: | |
4cffafe9 | 337 | if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) |
0f113f3e MC |
338 | goto err; |
339 | ||
340 | /* we need ((rnd-rem) % add) == 0 */ | |
341 | ||
342 | if (!BN_mod(t1, rnd, add, ctx)) | |
343 | goto err; | |
344 | if (!BN_sub(rnd, rnd, t1)) | |
345 | goto err; | |
346 | if (rem == NULL) { | |
0032bfea | 347 | if (!BN_add_word(rnd, safe ? 3u : 1u)) |
0f113f3e MC |
348 | goto err; |
349 | } else { | |
350 | if (!BN_add(rnd, rnd, rem)) | |
351 | goto err; | |
352 | } | |
353 | ||
0032bfea BE |
354 | if (BN_num_bits(rnd) < bits |
355 | || BN_get_word(rnd) < (safe ? 5u : 3u)) { | |
356 | if (!BN_add(rnd, rnd, add)) | |
357 | goto err; | |
358 | } | |
0f113f3e | 359 | |
0032bfea | 360 | /* we now have a random number 'rnd' to test. */ |
0f113f3e | 361 | for (i = 1; i < NUMPRIMES; i++) { |
d70a5627 DB |
362 | BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); |
363 | if (mod == (BN_ULONG)-1) | |
364 | goto err; | |
0032bfea | 365 | mods[i] = (prime_t) mod; |
0f113f3e | 366 | } |
0032bfea | 367 | delta = 0; |
0f113f3e MC |
368 | loop: |
369 | for (i = 1; i < NUMPRIMES; i++) { | |
0032bfea BE |
370 | /* check that rnd is a prime */ |
371 | if (bits <= 31 && delta <= 0x7fffffff | |
372 | && square(primes[i]) > BN_get_word(rnd) + delta) | |
373 | break; | |
374 | /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */ | |
375 | if (safe ? (mods[i] + delta) % primes[i] <= 1 | |
376 | : (mods[i] + delta) % primes[i] == 0) { | |
377 | delta += BN_get_word(add); | |
378 | if (delta > maxdelta) | |
379 | goto again; | |
0f113f3e MC |
380 | goto loop; |
381 | } | |
382 | } | |
0032bfea BE |
383 | if (!BN_add_word(rnd, delta)) |
384 | goto err; | |
0f113f3e MC |
385 | ret = 1; |
386 | ||
387 | err: | |
388 | BN_CTX_end(ctx); | |
0032bfea | 389 | bn_check_top(rnd); |
26a7d938 | 390 | return ret; |
0f113f3e | 391 | } |