GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/bn/bn_prime.c Lines: 162 190 85.3 %
Date: 2017-11-13 Branches: 174 265 65.7 %

Line Branch Exec Source
1
/* $OpenBSD: bn_prime.c,v 1.18 2017/01/29 17:49:22 beck 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_lcl.h"
118
119
/* NB: these functions have been "upgraded", the deprecated versions (which are
120
 * compatibility wrappers using these functions) are in bn_depr.c.
121
 * - Geoff
122
 */
123
124
/* The quick sieve algorithm approach to weeding out primes is
125
 * Philip Zimmermann's, as implemented in PGP.  I have had a read of
126
 * his comments and implemented my own version.
127
 */
128
#include "bn_prime.h"
129
130
static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
131
    const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
132
static int probable_prime(BIGNUM *rnd, int bits);
133
static int probable_prime_dh(BIGNUM *rnd, int bits,
134
    const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
135
static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
136
    const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
137
138
int
139
BN_GENCB_call(BN_GENCB *cb, int a, int b)
140
{
141
	/* No callback means continue */
142
58120
	if (!cb)
143
5024
		return 1;
144
24036
	switch (cb->ver) {
145
	case 1:
146
		/* Deprecated-style callbacks */
147
		if (!cb->cb.cb_1)
148
			return 1;
149
		cb->cb.cb_1(a, b, cb->arg);
150
		return 1;
151
	case 2:
152
		/* New-style callbacks */
153
24036
		return cb->cb.cb_2(a, b, cb);
154
	default:
155
		break;
156
	}
157
	/* Unrecognised callback type */
158
	return 0;
159
29060
}
160
161
int
162
BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
163
    const BIGNUM *rem, BN_GENCB *cb)
164
{
165
	BIGNUM *t;
166
	int found = 0;
167
	int i, j, c1 = 0;
168
	BN_CTX *ctx;
169
	int checks;
170
171

384
	if (bits < 2 || (bits == 2 && safe)) {
172
		/*
173
		 * There are no prime numbers smaller than 2, and the smallest
174
		 * safe prime (7) spans three bits.
175
		 */
176
		BNerror(BN_R_BITS_TOO_SMALL);
177
		return 0;
178
	}
179
180
128
	ctx = BN_CTX_new();
181
128
	if (ctx == NULL)
182
		goto err;
183
128
	BN_CTX_start(ctx);
184
128
	if ((t = BN_CTX_get(ctx)) == NULL)
185
		goto err;
186
187





1096
	checks = BN_prime_checks_for_size(bits);
188
189
loop:
190
	/* make a random number and set the top and bottom bits */
191
19450
	if (add == NULL) {
192
1485
		if (!probable_prime(ret, bits))
193
			goto err;
194
	} else {
195
17965
		if (safe) {
196
17707
			if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
197
				goto err;
198
		} else {
199
258
			if (!probable_prime_dh(ret, bits, add, rem, ctx))
200
				goto err;
201
		}
202
	}
203
	/* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
204
19450
	if (!BN_GENCB_call(cb, 0, c1++))
205
		/* aborted */
206
		goto err;
207
208
19450
	if (!safe) {
209
1723
		i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
210
1723
		if (i == -1)
211
			goto err;
212
1723
		if (i == 0)
213
1657
			goto loop;
214
	} else {
215
		/* for "safe prime" generation,
216
		 * check that (p-1)/2 is prime.
217
		 * Since a prime is odd, We just
218
		 * need to divide by 2 */
219
17727
		if (!BN_rshift1(t, ret))
220
			goto err;
221
222
38522
		for (i = 0; i < checks; i++) {
223
19199
			j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
224
19199
			if (j == -1)
225
				goto err;
226
19199
			if (j == 0)
227
17262
				goto loop;
228
229
1937
			j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
230
1937
			if (j == -1)
231
				goto err;
232
1937
			if (j == 0)
233
403
				goto loop;
234
235
1534
			if (!BN_GENCB_call(cb, 2, c1 - 1))
236
				goto err;
237
			/* We have a safe prime test pass */
238
		}
239
	}
240
	/* we have a prime :-) */
241
128
	found = 1;
242
243
err:
244
128
	if (ctx != NULL) {
245
128
		BN_CTX_end(ctx);
246
128
		BN_CTX_free(ctx);
247
128
	}
248
	bn_check_top(ret);
249
128
	return found;
250
128
}
251
252
int
253
BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
254
{
255
84
	return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
256
}
257
258
int
259
BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
260
    int do_trial_division, BN_GENCB *cb)
261
{
262
	int i, j, ret = -1;
263
	int k;
264
	BN_CTX *ctx = NULL;
265
	BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
266
	BN_MONT_CTX *mont = NULL;
267
	const BIGNUM *A = NULL;
268
269
49966
	if (BN_cmp(a, BN_value_one()) <= 0)
270
2
		return 0;
271
272
24981
	if (checks == BN_prime_checks)
273





317
		checks = BN_prime_checks_for_size(BN_num_bits(a));
274
275
	/* first look for small factors */
276

49962
	if (!BN_is_odd(a))
277
		/* a is even => a is prime if and only if a == 2 */
278

71
		return BN_is_word(a, 2);
279
24958
	if (do_trial_division) {
280
1050926
		for (i = 1; i < NUMPRIMES; i++) {
281
525240
			BN_ULONG mod = BN_mod_word(a, primes[i]);
282
525240
			if (mod == (BN_ULONG)-1)
283
				goto err;
284
525240
			if (mod == 0)
285
1853
				return 0;
286
523387
		}
287
223
		if (!BN_GENCB_call(cb, 1, -1))
288
			goto err;
289
	}
290
291
23105
	if (ctx_passed != NULL)
292
23101
		ctx = ctx_passed;
293
4
	else if ((ctx = BN_CTX_new()) == NULL)
294
		goto err;
295
23105
	BN_CTX_start(ctx);
296
297
	/* A := abs(a) */
298
23105
	if (a->neg) {
299
		BIGNUM *t;
300
		if ((t = BN_CTX_get(ctx)) == NULL)
301
			goto err;
302
		BN_copy(t, a);
303
		t->neg = 0;
304
		A = t;
305
	} else
306
		A = a;
307
23105
	if ((A1 = BN_CTX_get(ctx)) == NULL)
308
		goto err;
309
23105
	if ((A1_odd = BN_CTX_get(ctx)) == NULL)
310
		goto err;
311
23105
	if ((check = BN_CTX_get(ctx)) == NULL)
312
		goto err;
313
314
	/* compute A1 := A - 1 */
315
23105
	if (!BN_copy(A1, A))
316
		goto err;
317
23105
	if (!BN_sub_word(A1, 1))
318
		goto err;
319
23105
	if (BN_is_zero(A1)) {
320
		ret = 0;
321
		goto err;
322
	}
323
324
	/* write  A1  as  A1_odd * 2^k */
325
	k = 1;
326
57882
	while (!BN_is_bit_set(A1, k))
327
5836
		k++;
328
23105
	if (!BN_rshift(A1_odd, A1, k))
329
		goto err;
330
331
	/* Montgomery setup for computations mod A */
332
23105
	mont = BN_MONT_CTX_new();
333
23105
	if (mont == NULL)
334
		goto err;
335
23105
	if (!BN_MONT_CTX_set(mont, A, ctx))
336
		goto err;
337
338
57488
	for (i = 0; i < checks; i++) {
339
25145
		if (!BN_pseudo_rand_range(check, A1))
340
			goto err;
341
25145
		if (!BN_add_word(check, 1))
342
			goto err;
343
		/* now 1 <= check < A */
344
345
25145
		j = witness(check, A, A1, A1_odd, k, ctx, mont);
346
25145
		if (j == -1)
347
			goto err;
348
25145
		if (j) {
349
			ret = 0;
350
19506
			goto err;
351
		}
352
5639
		if (!BN_GENCB_call(cb, 1, i))
353
			goto err;
354
	}
355
3599
	ret = 1;
356
357
err:
358
23105
	if (ctx != NULL) {
359
23105
		BN_CTX_end(ctx);
360
23105
		if (ctx_passed == NULL)
361
4
			BN_CTX_free(ctx);
362
	}
363
23105
	BN_MONT_CTX_free(mont);
364
365
23105
	return (ret);
366
24983
}
367
368
static int
369
witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd,
370
    int k, BN_CTX *ctx, BN_MONT_CTX *mont)
371
{
372
50290
	if (!BN_mod_exp_mont_ct(w, w, a1_odd, a, ctx, mont))
373
		/* w := w^a1_odd mod a */
374
		return -1;
375

31247
	if (BN_is_one(w))
376
1906
		return 0; /* probably prime */
377
23239
	if (BN_cmp(w, a1) == 0)
378
1983
		return 0; /* w == -1 (mod a),  'a' is probably prime */
379
59340
	while (--k) {
380
10164
		if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
381
			return -1;
382

12136
		if (BN_is_one(w))
383
			return 1; /* 'a' is composite, otherwise a previous 'w' would
384
			           * have been == -1 (mod 'a') */
385
10164
		if (BN_cmp(w, a1) == 0)
386
1750
			return 0; /* w == -1 (mod a), 'a' is probably prime */
387
	}
388
	/* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
389
	 * and it is neither -1 nor +1 -- so 'a' cannot be prime */
390
	bn_check_top(w);
391
19506
	return 1;
392
25145
}
393
394
static int
395
probable_prime(BIGNUM *rnd, int bits)
396
{
397
	int i;
398
2970
	prime_t mods[NUMPRIMES];
399
1485
	BN_ULONG delta, maxdelta;
400
401
again:
402
1485
	if (!BN_rand(rnd, bits, 1, 1))
403
		return (0);
404
	/* we now have a random number 'rand' to test. */
405
6082560
	for (i = 1; i < NUMPRIMES; i++) {
406
3039795
		BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
407
3039795
		if (mod == (BN_ULONG)-1)
408
			return (0);
409
3039795
		mods[i] = (prime_t)mod;
410
3039795
	}
411
	maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
412
1485
	delta = 0;
413
loop:
414
8983750
	for (i = 1; i < NUMPRIMES; i++) {
415
		/* check that rnd is not a prime and also
416
		 * that gcd(rnd-1,primes) == 1 (except for 2) */
417
4490390
		if (((mods[i] + delta) % primes[i]) <= 1) {
418
161175
			delta += 2;
419
161175
			if (delta > maxdelta)
420
				goto again;
421
161175
			goto loop;
422
		}
423
	}
424
1485
	if (!BN_add_word(rnd, delta))
425
		return (0);
426
	bn_check_top(rnd);
427
1485
	return (1);
428
1485
}
429
430
static int
431
probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem,
432
    BN_CTX *ctx)
433
{
434
	int i, ret = 0;
435
	BIGNUM *t1;
436
437
516
	BN_CTX_start(ctx);
438
258
	if ((t1 = BN_CTX_get(ctx)) == NULL)
439
		goto err;
440
441
258
	if (!BN_rand(rnd, bits, 0, 1))
442
		goto err;
443
444
	/* we need ((rnd-rem) % add) == 0 */
445
446
258
	if (!BN_mod_ct(t1, rnd, add, ctx))
447
		goto err;
448
258
	if (!BN_sub(rnd, rnd, t1))
449
		goto err;
450
516
	if (rem == NULL) {
451
		if (!BN_add_word(rnd, 1))
452
			goto err;
453
	} else {
454
258
		if (!BN_add(rnd, rnd, rem))
455
			goto err;
456
	}
457
458
	/* we now have a random number 'rand' to test. */
459
460
loop:
461
1566996
	for (i = 1; i < NUMPRIMES; i++) {
462
		/* check that rnd is a prime */
463
783240
		BN_LONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
464
783240
		if (mod == (BN_ULONG)-1)
465
			goto err;
466
783240
		if (mod <= 1) {
467
28225
			if (!BN_add(rnd, rnd, add))
468
				goto err;
469
28225
			goto loop;
470
		}
471

755015
	}
472
258
	ret = 1;
473
474
err:
475
258
	BN_CTX_end(ctx);
476
	bn_check_top(rnd);
477
258
	return (ret);
478
258
}
479
480
static int
481
probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
482
    const BIGNUM *rem, BN_CTX *ctx)
483
{
484
	int i, ret = 0;
485
	BIGNUM *t1, *qadd, *q;
486
487
35414
	bits--;
488
17707
	BN_CTX_start(ctx);
489
17707
	if ((t1 = BN_CTX_get(ctx)) == NULL)
490
		goto err;
491
17707
	if ((q = BN_CTX_get(ctx)) == NULL)
492
		goto err;
493
17707
	if ((qadd = BN_CTX_get(ctx)) == NULL)
494
		goto err;
495
496
17707
	if (!BN_rshift1(qadd, padd))
497
		goto err;
498
499
17707
	if (!BN_rand(q, bits, 0, 1))
500
		goto err;
501
502
	/* we need ((rnd-rem) % add) == 0 */
503
17707
	if (!BN_mod_ct(t1, q,qadd, ctx))
504
		goto err;
505
17707
	if (!BN_sub(q, q, t1))
506
		goto err;
507
17707
	if (rem == NULL) {
508
		if (!BN_add_word(q, 1))
509
			goto err;
510
	} else {
511
17707
		if (!BN_rshift1(t1, rem))
512
			goto err;
513
17707
		if (!BN_add(q, q, t1))
514
			goto err;
515
	}
516
517
	/* we now have a random number 'rand' to test. */
518
17707
	if (!BN_lshift1(p, q))
519
		goto err;
520
35414
	if (!BN_add_word(p, 1))
521
		goto err;
522
523
loop:
524
103954358
	for (i = 1; i < NUMPRIMES; i++) {
525
		/* check that p and q are prime */
526
		/* check that for p and q
527
		 * gcd(p-1,primes) == 1 (except for 2) */
528
51959472
		BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
529
51959472
		BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
530
51959472
		if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1)
531
			goto err;
532
51959472
		if (pmod == 0 || qmod == 0) {
533
633064
			if (!BN_add(p, p, padd))
534
				goto err;
535
633064
			if (!BN_add(q, q, qadd))
536
				goto err;
537
633064
			goto loop;
538
		}
539

51326408
	}
540
17707
	ret = 1;
541
542
err:
543
17707
	BN_CTX_end(ctx);
544
	bn_check_top(p);
545
17707
	return (ret);
546
17707
}