1 /* $OpenBSD: bn_prime.c,v 1.34 2023/07/20 06:26:27 tb Exp $ */
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
115 #include <openssl/err.h>
116
117 #include "bn_local.h"
118
119 /* The quick sieve algorithm approach to weeding out primes is
120 * Philip Zimmermann's, as implemented in PGP. I have had a read of
121 * his comments and implemented my own version.
122 */
123 #include "bn_prime.h"
124
125 static int probable_prime(BIGNUM *rnd, int bits);
126 static int probable_prime_dh(BIGNUM *rnd, int bits,
127 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
128 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
129 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
130
131 int
BN_GENCB_call(BN_GENCB * cb,int a,int b)132 BN_GENCB_call(BN_GENCB *cb, int a, int b)
133 {
134 /* No callback means continue */
135 if (!cb)
136 return 1;
137 switch (cb->ver) {
138 case 1:
139 /* Deprecated-style callbacks */
140 if (!cb->cb.cb_1)
141 return 1;
142 cb->cb.cb_1(a, b, cb->arg);
143 return 1;
144 case 2:
145 /* New-style callbacks */
146 return cb->cb.cb_2(a, b, cb);
147 default:
148 break;
149 }
150 /* Unrecognised callback type */
151 return 0;
152 }
153 LCRYPTO_ALIAS(BN_GENCB_call);
154
155 int
BN_generate_prime_ex(BIGNUM * ret,int bits,int safe,const BIGNUM * add,const BIGNUM * rem,BN_GENCB * cb)156 BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
157 const BIGNUM *rem, BN_GENCB *cb)
158 {
159 BN_CTX *ctx;
160 BIGNUM *p;
161 int is_prime;
162 int loops = 0;
163 int found = 0;
164
165 if (bits < 2 || (bits == 2 && safe)) {
166 /*
167 * There are no prime numbers smaller than 2, and the smallest
168 * safe prime (7) spans three bits.
169 */
170 BNerror(BN_R_BITS_TOO_SMALL);
171 return 0;
172 }
173
174 if ((ctx = BN_CTX_new()) == NULL)
175 goto err;
176 BN_CTX_start(ctx);
177 if ((p = BN_CTX_get(ctx)) == NULL)
178 goto err;
179
180 loop:
181 /* Make a random number and set the top and bottom bits. */
182 if (add == NULL) {
183 if (!probable_prime(ret, bits))
184 goto err;
185 } else {
186 if (safe) {
187 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
188 goto err;
189 } else {
190 if (!probable_prime_dh(ret, bits, add, rem, ctx))
191 goto err;
192 }
193 }
194
195 if (!BN_GENCB_call(cb, 0, loops++))
196 goto err;
197
198 if (!safe) {
199 if (!bn_is_prime_bpsw(&is_prime, ret, ctx, 1))
200 goto err;
201 if (!is_prime)
202 goto loop;
203 } else {
204 if (!bn_is_prime_bpsw(&is_prime, ret, ctx, 1))
205 goto err;
206 if (!is_prime)
207 goto loop;
208
209 /*
210 * For safe prime generation, check that p = (ret-1)/2 is prime.
211 * Since this prime has >= 3 bits, it is odd, and we can simply
212 * divide by 2.
213 */
214 if (!BN_rshift1(p, ret))
215 goto err;
216
217 if (!bn_is_prime_bpsw(&is_prime, p, ctx, 1))
218 goto err;
219 if (!is_prime)
220 goto loop;
221
222 if (!BN_GENCB_call(cb, 2, loops - 1))
223 goto err;
224 }
225
226 found = 1;
227
228 err:
229 BN_CTX_end(ctx);
230 BN_CTX_free(ctx);
231
232 return found;
233 }
234 LCRYPTO_ALIAS(BN_generate_prime_ex);
235
236 int
BN_is_prime_ex(const BIGNUM * a,int checks,BN_CTX * ctx_passed,BN_GENCB * cb)237 BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
238 {
239 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
240 }
241 LCRYPTO_ALIAS(BN_is_prime_ex);
242
243 #define BN_PRIME_MAXIMUM_BITS (32 * 1024)
244
245 int
BN_is_prime_fasttest_ex(const BIGNUM * a,int checks,BN_CTX * ctx_passed,int do_trial_division,BN_GENCB * cb)246 BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
247 int do_trial_division, BN_GENCB *cb)
248 {
249 int is_prime;
250
251 if (checks < 0)
252 return -1;
253
254 /*
255 * Prime numbers this large do not appear in everyday cryptography
256 * and checking such numbers for primality is very expensive.
257 */
258 if (BN_num_bits(a) > BN_PRIME_MAXIMUM_BITS) {
259 BNerror(BN_R_BIGNUM_TOO_LONG);
260 return -1;
261 }
262
263 if (checks == BN_prime_checks)
264 checks = BN_prime_checks_for_size(BN_num_bits(a));
265
266 /* XXX - tickle BN_GENCB in bn_is_prime_bpsw(). */
267 if (!bn_is_prime_bpsw(&is_prime, a, ctx_passed, checks))
268 return -1;
269
270 return is_prime;
271 }
272 LCRYPTO_ALIAS(BN_is_prime_fasttest_ex);
273
274 static int
probable_prime(BIGNUM * rnd,int bits)275 probable_prime(BIGNUM *rnd, int bits)
276 {
277 int i;
278 BN_ULONG mods[NUMPRIMES];
279 BN_ULONG delta, maxdelta;
280
281 again:
282 if (!BN_rand(rnd, bits, 1, 1))
283 return (0);
284 /* we now have a random number 'rand' to test. */
285 for (i = 1; i < NUMPRIMES; i++) {
286 BN_ULONG mod = BN_mod_word(rnd, primes[i]);
287 if (mod == (BN_ULONG)-1)
288 return (0);
289 mods[i] = mod;
290 }
291 maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
292 delta = 0;
293 loop:
294 for (i = 1; i < NUMPRIMES; i++) {
295 /* check that rnd is not a prime and also
296 * that gcd(rnd-1,primes) == 1 (except for 2) */
297 if (((mods[i] + delta) % primes[i]) <= 1) {
298 delta += 2;
299 if (delta > maxdelta)
300 goto again;
301 goto loop;
302 }
303 }
304 if (!BN_add_word(rnd, delta))
305 return (0);
306 return (1);
307 }
308
309 static int
probable_prime_dh(BIGNUM * rnd,int bits,const BIGNUM * add,const BIGNUM * rem,BN_CTX * ctx)310 probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem,
311 BN_CTX *ctx)
312 {
313 int i, ret = 0;
314 BIGNUM *t1;
315
316 BN_CTX_start(ctx);
317 if ((t1 = BN_CTX_get(ctx)) == NULL)
318 goto err;
319
320 if (!BN_rand(rnd, bits, 0, 1))
321 goto err;
322
323 /* we need ((rnd-rem) % add) == 0 */
324
325 if (!BN_mod_ct(t1, rnd, add, ctx))
326 goto err;
327 if (!BN_sub(rnd, rnd, t1))
328 goto err;
329 if (rem == NULL) {
330 if (!BN_add_word(rnd, 1))
331 goto err;
332 } else {
333 if (!BN_add(rnd, rnd, rem))
334 goto err;
335 }
336
337 /* we now have a random number 'rand' to test. */
338
339 loop:
340 for (i = 1; i < NUMPRIMES; i++) {
341 /* check that rnd is a prime */
342 BN_LONG mod = BN_mod_word(rnd, primes[i]);
343 if (mod == (BN_ULONG)-1)
344 goto err;
345 if (mod <= 1) {
346 if (!BN_add(rnd, rnd, add))
347 goto err;
348 goto loop;
349 }
350 }
351 ret = 1;
352
353 err:
354 BN_CTX_end(ctx);
355 return (ret);
356 }
357
358 static int
probable_prime_dh_safe(BIGNUM * p,int bits,const BIGNUM * padd,const BIGNUM * rem,BN_CTX * ctx)359 probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
360 const BIGNUM *rem, BN_CTX *ctx)
361 {
362 int i, ret = 0;
363 BIGNUM *t1, *qadd, *q;
364
365 bits--;
366 BN_CTX_start(ctx);
367 if ((t1 = BN_CTX_get(ctx)) == NULL)
368 goto err;
369 if ((q = BN_CTX_get(ctx)) == NULL)
370 goto err;
371 if ((qadd = BN_CTX_get(ctx)) == NULL)
372 goto err;
373
374 if (!BN_rshift1(qadd, padd))
375 goto err;
376
377 if (!BN_rand(q, bits, 0, 1))
378 goto err;
379
380 /* we need ((rnd-rem) % add) == 0 */
381 if (!BN_mod_ct(t1, q,qadd, ctx))
382 goto err;
383 if (!BN_sub(q, q, t1))
384 goto err;
385 if (rem == NULL) {
386 if (!BN_add_word(q, 1))
387 goto err;
388 } else {
389 if (!BN_rshift1(t1, rem))
390 goto err;
391 if (!BN_add(q, q, t1))
392 goto err;
393 }
394
395 /* we now have a random number 'rand' to test. */
396 if (!BN_lshift1(p, q))
397 goto err;
398 if (!BN_add_word(p, 1))
399 goto err;
400
401 loop:
402 for (i = 1; i < NUMPRIMES; i++) {
403 /* check that p and q are prime */
404 /* check that for p and q
405 * gcd(p-1,primes) == 1 (except for 2) */
406 BN_ULONG pmod = BN_mod_word(p, primes[i]);
407 BN_ULONG qmod = BN_mod_word(q, primes[i]);
408 if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1)
409 goto err;
410 if (pmod == 0 || qmod == 0) {
411 if (!BN_add(p, p, padd))
412 goto err;
413 if (!BN_add(q, q, qadd))
414 goto err;
415 goto loop;
416 }
417 }
418 ret = 1;
419
420 err:
421 BN_CTX_end(ctx);
422 return (ret);
423 }
424