Line data Source code
1 : /* crypto/bn/bn_prime.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
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 : */
58 : /* ====================================================================
59 : * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
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 : */
111 :
112 : #include <stdio.h>
113 : #include <time.h>
114 : #include "cryptlib.h"
115 : #include "bn_lcl.h"
116 : #include <openssl/rand.h>
117 :
118 : /*
119 : * NB: these functions have been "upgraded", the deprecated versions (which
120 : * are compatibility wrappers using these functions) are in bn_depr.c. -
121 : * Geoff
122 : */
123 :
124 : /*
125 : * The quick sieve algorithm approach to weeding out primes is Philip
126 : * Zimmermann's, as implemented in PGP. I have had a read of his comments
127 : * and implemented my own version.
128 : */
129 : #include "bn_prime.h"
130 :
131 : static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
132 : const BIGNUM *a1_odd, int k, BN_CTX *ctx,
133 : BN_MONT_CTX *mont);
134 : static int probable_prime(BIGNUM *rnd, int bits);
135 : static int probable_prime_dh(BIGNUM *rnd, int bits,
136 : const BIGNUM *add, const BIGNUM *rem,
137 : BN_CTX *ctx);
138 : static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add,
139 : const BIGNUM *rem, BN_CTX *ctx);
140 :
141 36 : int BN_GENCB_call(BN_GENCB *cb, int a, int b)
142 : {
143 : /* No callback means continue */
144 36 : if (!cb)
145 : return 1;
146 0 : switch (cb->ver) {
147 : case 1:
148 : /* Deprecated-style callbacks */
149 0 : if (!cb->cb.cb_1)
150 : return 1;
151 0 : cb->cb.cb_1(a, b, cb->arg);
152 0 : return 1;
153 : case 2:
154 : /* New-style callbacks */
155 0 : return cb->cb.cb_2(a, b, cb);
156 : default:
157 : break;
158 : }
159 : /* Unrecognised callback type */
160 : return 0;
161 : }
162 :
163 0 : int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
164 : const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
165 : {
166 : BIGNUM *t;
167 : int found = 0;
168 : int i, j, c1 = 0;
169 : BN_CTX *ctx;
170 0 : int checks = BN_prime_checks_for_size(bits);
171 :
172 0 : ctx = BN_CTX_new();
173 0 : if (ctx == NULL)
174 : goto err;
175 0 : BN_CTX_start(ctx);
176 0 : t = BN_CTX_get(ctx);
177 0 : if (!t)
178 : goto err;
179 : loop:
180 : /* make a random number and set the top and bottom bits */
181 0 : if (add == NULL) {
182 0 : if (!probable_prime(ret, bits))
183 : goto err;
184 : } else {
185 0 : if (safe) {
186 0 : if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
187 : goto err;
188 : } else {
189 0 : if (!probable_prime_dh(ret, bits, add, rem, ctx))
190 : goto err;
191 : }
192 : }
193 : /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
194 0 : if (!BN_GENCB_call(cb, 0, c1++))
195 : /* aborted */
196 : goto err;
197 :
198 0 : if (!safe) {
199 0 : i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
200 0 : if (i == -1)
201 : goto err;
202 0 : if (i == 0)
203 : goto loop;
204 : } else {
205 : /*
206 : * for "safe prime" generation, check that (p-1)/2 is prime. Since a
207 : * prime is odd, We just need to divide by 2
208 : */
209 0 : if (!BN_rshift1(t, ret))
210 : goto err;
211 :
212 0 : for (i = 0; i < checks; i++) {
213 0 : j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
214 0 : if (j == -1)
215 : goto err;
216 0 : if (j == 0)
217 : goto loop;
218 :
219 0 : j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
220 0 : if (j == -1)
221 : goto err;
222 0 : if (j == 0)
223 : goto loop;
224 :
225 0 : if (!BN_GENCB_call(cb, 2, c1 - 1))
226 : goto err;
227 : /* We have a safe prime test pass */
228 : }
229 : }
230 : /* we have a prime :-) */
231 : found = 1;
232 : err:
233 0 : if (ctx != NULL) {
234 0 : BN_CTX_end(ctx);
235 0 : BN_CTX_free(ctx);
236 : }
237 : bn_check_top(ret);
238 0 : return found;
239 : }
240 :
241 6 : int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
242 : BN_GENCB *cb)
243 : {
244 6 : return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
245 : }
246 :
247 6 : int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
248 : int do_trial_division, BN_GENCB *cb)
249 : {
250 : int i, j, ret = -1;
251 : int k;
252 : BN_CTX *ctx = NULL;
253 : BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
254 : BN_MONT_CTX *mont = NULL;
255 : const BIGNUM *A = NULL;
256 :
257 6 : if (BN_cmp(a, BN_value_one()) <= 0)
258 : return 0;
259 :
260 6 : if (checks == BN_prime_checks)
261 6 : checks = BN_prime_checks_for_size(BN_num_bits(a));
262 :
263 : /* first look for small factors */
264 6 : if (!BN_is_odd(a))
265 : /* a is even => a is prime if and only if a == 2 */
266 0 : return BN_is_word(a, 2);
267 6 : if (do_trial_division) {
268 0 : for (i = 1; i < NUMPRIMES; i++)
269 0 : if (BN_mod_word(a, primes[i]) == 0)
270 : return 0;
271 0 : if (!BN_GENCB_call(cb, 1, -1))
272 : goto err;
273 : }
274 :
275 6 : if (ctx_passed != NULL)
276 : ctx = ctx_passed;
277 6 : else if ((ctx = BN_CTX_new()) == NULL)
278 : goto err;
279 6 : BN_CTX_start(ctx);
280 :
281 : /* A := abs(a) */
282 6 : if (a->neg) {
283 : BIGNUM *t;
284 0 : if ((t = BN_CTX_get(ctx)) == NULL)
285 : goto err;
286 0 : BN_copy(t, a);
287 0 : t->neg = 0;
288 : A = t;
289 : } else
290 : A = a;
291 6 : A1 = BN_CTX_get(ctx);
292 6 : A1_odd = BN_CTX_get(ctx);
293 6 : check = BN_CTX_get(ctx);
294 6 : if (check == NULL)
295 : goto err;
296 :
297 : /* compute A1 := A - 1 */
298 6 : if (!BN_copy(A1, A))
299 : goto err;
300 6 : if (!BN_sub_word(A1, 1))
301 : goto err;
302 6 : if (BN_is_zero(A1)) {
303 : ret = 0;
304 : goto err;
305 : }
306 :
307 : /* write A1 as A1_odd * 2^k */
308 : k = 1;
309 15 : while (!BN_is_bit_set(A1, k))
310 9 : k++;
311 6 : if (!BN_rshift(A1_odd, A1, k))
312 : goto err;
313 :
314 : /* Montgomery setup for computations mod A */
315 6 : mont = BN_MONT_CTX_new();
316 6 : if (mont == NULL)
317 : goto err;
318 6 : if (!BN_MONT_CTX_set(mont, A, ctx))
319 : goto err;
320 :
321 36 : for (i = 0; i < checks; i++) {
322 36 : if (!BN_pseudo_rand_range(check, A1))
323 : goto err;
324 36 : if (!BN_add_word(check, 1))
325 : goto err;
326 : /* now 1 <= check < A */
327 :
328 36 : j = witness(check, A, A1, A1_odd, k, ctx, mont);
329 36 : if (j == -1)
330 : goto err;
331 36 : if (j) {
332 : ret = 0;
333 : goto err;
334 : }
335 36 : if (!BN_GENCB_call(cb, 1, i))
336 : goto err;
337 : }
338 : ret = 1;
339 : err:
340 6 : if (ctx != NULL) {
341 6 : BN_CTX_end(ctx);
342 6 : if (ctx_passed == NULL)
343 6 : BN_CTX_free(ctx);
344 : }
345 6 : if (mont != NULL)
346 6 : BN_MONT_CTX_free(mont);
347 :
348 6 : return (ret);
349 : }
350 :
351 36 : static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
352 : const BIGNUM *a1_odd, int k, BN_CTX *ctx,
353 : BN_MONT_CTX *mont)
354 : {
355 36 : if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
356 : return -1;
357 36 : if (BN_is_one(w))
358 : return 0; /* probably prime */
359 25 : if (BN_cmp(w, a1) == 0)
360 : return 0; /* w == -1 (mod a), 'a' is probably prime */
361 22 : while (--k) {
362 22 : if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
363 : return -1;
364 22 : if (BN_is_one(w))
365 : return 1; /* 'a' is composite, otherwise a previous 'w'
366 : * would have been == -1 (mod 'a') */
367 22 : if (BN_cmp(w, a1) == 0)
368 : return 0; /* w == -1 (mod a), 'a' is probably prime */
369 : }
370 : /*
371 : * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
372 : * it is neither -1 nor +1 -- so 'a' cannot be prime
373 : */
374 : bn_check_top(w);
375 : return 1;
376 : }
377 :
378 0 : static int probable_prime(BIGNUM *rnd, int bits)
379 : {
380 : int i;
381 : prime_t mods[NUMPRIMES];
382 : BN_ULONG delta, maxdelta;
383 :
384 : again:
385 0 : if (!BN_rand(rnd, bits, 1, 1))
386 : return (0);
387 : /* we now have a random number 'rand' to test. */
388 0 : for (i = 1; i < NUMPRIMES; i++)
389 0 : mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
390 : maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
391 : delta = 0;
392 0 : loop:for (i = 1; i < NUMPRIMES; i++) {
393 : /*
394 : * check that rnd is not a prime and also that gcd(rnd-1,primes) == 1
395 : * (except for 2)
396 : */
397 0 : if (((mods[i] + delta) % primes[i]) <= 1) {
398 0 : delta += 2;
399 0 : if (delta > maxdelta)
400 : goto again;
401 : goto loop;
402 : }
403 : }
404 0 : if (!BN_add_word(rnd, delta))
405 : return (0);
406 : bn_check_top(rnd);
407 0 : return (1);
408 : }
409 :
410 0 : static int probable_prime_dh(BIGNUM *rnd, int bits,
411 : const BIGNUM *add, const BIGNUM *rem,
412 : BN_CTX *ctx)
413 : {
414 : int i, ret = 0;
415 : BIGNUM *t1;
416 :
417 0 : BN_CTX_start(ctx);
418 0 : if ((t1 = BN_CTX_get(ctx)) == NULL)
419 : goto err;
420 :
421 0 : if (!BN_rand(rnd, bits, 0, 1))
422 : goto err;
423 :
424 : /* we need ((rnd-rem) % add) == 0 */
425 :
426 0 : if (!BN_mod(t1, rnd, add, ctx))
427 : goto err;
428 0 : if (!BN_sub(rnd, rnd, t1))
429 : goto err;
430 0 : if (rem == NULL) {
431 0 : if (!BN_add_word(rnd, 1))
432 : goto err;
433 : } else {
434 0 : if (!BN_add(rnd, rnd, rem))
435 : goto err;
436 : }
437 :
438 : /* we now have a random number 'rand' to test. */
439 :
440 0 : loop:for (i = 1; i < NUMPRIMES; i++) {
441 : /* check that rnd is a prime */
442 0 : if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
443 0 : if (!BN_add(rnd, rnd, add))
444 : goto err;
445 : goto loop;
446 : }
447 : }
448 : ret = 1;
449 : err:
450 0 : BN_CTX_end(ctx);
451 : bn_check_top(rnd);
452 0 : return (ret);
453 : }
454 :
455 0 : static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
456 : const BIGNUM *rem, BN_CTX *ctx)
457 : {
458 : int i, ret = 0;
459 : BIGNUM *t1, *qadd, *q;
460 :
461 0 : bits--;
462 0 : BN_CTX_start(ctx);
463 0 : t1 = BN_CTX_get(ctx);
464 0 : q = BN_CTX_get(ctx);
465 0 : qadd = BN_CTX_get(ctx);
466 0 : if (qadd == NULL)
467 : goto err;
468 :
469 0 : if (!BN_rshift1(qadd, padd))
470 : goto err;
471 :
472 0 : if (!BN_rand(q, bits, 0, 1))
473 : goto err;
474 :
475 : /* we need ((rnd-rem) % add) == 0 */
476 0 : if (!BN_mod(t1, q, qadd, ctx))
477 : goto err;
478 0 : if (!BN_sub(q, q, t1))
479 : goto err;
480 0 : if (rem == NULL) {
481 0 : if (!BN_add_word(q, 1))
482 : goto err;
483 : } else {
484 0 : if (!BN_rshift1(t1, rem))
485 : goto err;
486 0 : if (!BN_add(q, q, t1))
487 : goto err;
488 : }
489 :
490 : /* we now have a random number 'rand' to test. */
491 0 : if (!BN_lshift1(p, q))
492 : goto err;
493 0 : if (!BN_add_word(p, 1))
494 : goto err;
495 :
496 0 : loop:for (i = 1; i < NUMPRIMES; i++) {
497 : /* check that p and q are prime */
498 : /*
499 : * check that for p and q gcd(p-1,primes) == 1 (except for 2)
500 : */
501 0 : if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
502 0 : (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
503 0 : if (!BN_add(p, p, padd))
504 : goto err;
505 0 : if (!BN_add(q, q, qadd))
506 : goto err;
507 : goto loop;
508 : }
509 : }
510 : ret = 1;
511 : err:
512 0 : BN_CTX_end(ctx);
513 : bn_check_top(p);
514 0 : return (ret);
515 : }
|
