1
/* primegen.c - prime number generator
2
* Copyright (C) 1998, 2000, 2001, 2002, 2003
3
* 2004, 2008 Free Software Foundation, Inc.
5
* This file is part of Libgcrypt.
7
* Libgcrypt is free software; you can redistribute it and/or modify
8
* it under the terms of the GNU Lesser general Public License as
9
* published by the Free Software Foundation; either version 2.1 of
10
* the License, or (at your option) any later version.
12
* Libgcrypt is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
* GNU Lesser General Public License for more details.
17
* You should have received a copy of the GNU Lesser General Public
18
* License along with this program; if not, write to the Free Software
19
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
34
static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel,
35
int (*extra_check)(void *, gcry_mpi_t),
36
void *extra_check_arg);
37
static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
38
gcry_prime_check_func_t cb_func, void *cb_arg );
39
static int is_prime (gcry_mpi_t n, int steps, unsigned int *count);
40
static void m_out_of_n( char *array, int m, int n );
42
static void (*progress_cb) (void *,const char*,int,int, int );
43
static void *progress_cb_data;
45
/* Note: 2 is not included because it can be tested more easily by
46
looking at bit 0. The last entry in this list is marked by a zero */
47
static ushort small_prime_numbers[] = {
48
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
49
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
50
103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
51
157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
52
211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
53
269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
54
331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
55
389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
56
449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
57
509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
58
587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
59
643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
60
709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
61
773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
62
853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
63
919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
64
991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
65
1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
66
1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
67
1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
68
1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
69
1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
70
1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
71
1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
72
1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
73
1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
74
1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
75
1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
76
1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
77
1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
78
1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
79
1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
80
1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
81
1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
82
2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
83
2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
84
2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
85
2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
86
2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
87
2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
88
2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
89
2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
90
2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
91
2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
92
2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
93
2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
94
2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
95
2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
96
2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
97
3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
98
3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
99
3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
100
3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
101
3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
102
3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
103
3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
104
3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
105
3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
106
3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
107
3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
108
3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
109
3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
110
3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
111
3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
112
4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
113
4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
114
4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
115
4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
116
4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
117
4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
118
4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
119
4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
120
4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
121
4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
122
4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
123
4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
124
4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
125
4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
126
4957, 4967, 4969, 4973, 4987, 4993, 4999,
129
static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
133
/* An object and a list to build up a global pool of primes. See
134
save_pool_prime and get_pool_prime. */
137
struct primepool_s *next;
138
gcry_mpi_t prime; /* If this is NULL the entry is not used. */
140
gcry_random_level_t randomlevel;
142
struct primepool_s *primepool;
143
/* Mutex used to protect access to the primepool. */
144
static ath_mutex_t primepool_lock = ATH_MUTEX_INITIALIZER;
148
/* Save PRIME which has been generated at RANDOMLEVEL for later
149
use. Needs to be called while primepool_lock is being hold. Note
150
that PRIME should be considered released after calling this
153
save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel)
155
struct primepool_s *item, *item2;
158
for (n=0, item = primepool; item; item = item->next, n++)
161
if (!item && n > 100)
163
/* Remove some of the entries. Our strategy is removing
164
the last third from the list. */
167
for (i=0, item2 = primepool; item2; item2 = item2->next)
171
gcry_mpi_release (item2->prime);
180
item = gcry_calloc (1, sizeof *item);
183
/* Out of memory. Silently giving up. */
184
gcry_mpi_release (prime);
187
item->next = primepool;
191
item->nbits = mpi_get_nbits (prime);
192
item->randomlevel = randomlevel;
196
/* Return a prime for the prime pool or NULL if none has been found.
197
The prime needs to match NBITS and randomlevel. This function needs
198
to be called why the primepool_look is being hold. */
200
get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel)
202
struct primepool_s *item;
204
for (item = primepool; item; item = item->next)
206
&& item->nbits == nbits && item->randomlevel == randomlevel)
208
gcry_mpi_t prime = item->prime;
210
gcry_assert (nbits == mpi_get_nbits (prime));
222
_gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
226
progress_cb_data = cb_data;
234
progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
239
* Generate a prime number (stored in secure memory)
242
_gcry_generate_secret_prime (unsigned int nbits,
243
gcry_random_level_t random_level,
244
int (*extra_check)(void*, gcry_mpi_t),
245
void *extra_check_arg)
249
prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg);
255
/* Generate a prime number which may be public, i.e. not allocated in
258
_gcry_generate_public_prime (unsigned int nbits,
259
gcry_random_level_t random_level,
260
int (*extra_check)(void*, gcry_mpi_t),
261
void *extra_check_arg)
265
prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg);
271
/* Core prime generation function. The algorithm used to generate
272
practically save primes is due to Lim and Lee as described in the
273
CRYPTO '97 proceedings (ISBN3540633847) page 260.
275
NEED_Q_FACTOR: If true make sure that at least one factor is of
276
size qbits. This is for example required for DSA.
277
PRIME_GENERATED: Adresss of a variable where the resulting prime
278
number will be stored.
279
PBITS: Requested size of the prime number. At least 48.
280
QBITS: One factor of the prime needs to be of this size. Maybe 0
281
if this is not required. See also MODE.
282
G: If not NULL an MPI which will receive a generator for the prime
283
for use with Elgamal.
284
RET_FACTORS: if not NULL, an array with all factors are stored at
286
ALL_FACTORS: If set to true all factors of prime-1 are returned.
287
RANDOMLEVEL: How strong should the random numers be.
288
FLAGS: Prime generation bit flags. Currently supported:
289
GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret.
290
CB_FUNC, CB_ARG: Callback to be used for extra checks.
293
static gcry_err_code_t
294
prime_generate_internal (int need_q_factor,
295
gcry_mpi_t *prime_generated, unsigned int pbits,
296
unsigned int qbits, gcry_mpi_t g,
297
gcry_mpi_t **ret_factors,
298
gcry_random_level_t randomlevel, unsigned int flags,
300
gcry_prime_check_func_t cb_func, void *cb_arg)
302
gcry_err_code_t err = 0;
303
gcry_mpi_t *factors_new = NULL; /* Factors to return to the
305
gcry_mpi_t *factors = NULL; /* Current factors. */
306
gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */
307
gcry_mpi_t *pool = NULL; /* Pool of primes. */
308
int *pool_in_use = NULL; /* Array with currently used POOL elements. */
309
unsigned char *perms = NULL; /* Permutations of POOL. */
310
gcry_mpi_t q_factor = NULL; /* Used if QBITS is non-zero. */
311
unsigned int fbits = 0; /* Length of prime factors. */
312
unsigned int n = 0; /* Number of factors. */
313
unsigned int m = 0; /* Number of primes in pool. */
314
gcry_mpi_t q = NULL; /* First prime factor. */
315
gcry_mpi_t prime = NULL; /* Prime candidate. */
316
unsigned int nprime = 0; /* Bits of PRIME. */
317
unsigned int req_qbits; /* The original QBITS value. */
318
gcry_mpi_t val_2; /* For check_prime(). */
319
int is_locked = 0; /* Flag to help unlocking the primepool. */
320
unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
321
unsigned int count1 = 0, count2 = 0;
322
unsigned int i = 0, j = 0;
325
return GPG_ERR_INV_ARG;
327
/* We won't use a too strong random elvel for the pooled subprimes. */
328
poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM?
329
GCRY_STRONG_RANDOM : randomlevel);
332
/* If QBITS is not given, assume a reasonable value. */
338
/* Find number of needed prime factors N. */
339
for (n = 1; (pbits - qbits - 1) / n >= qbits; n++)
343
val_2 = mpi_alloc_set_ui (2);
345
if ((! n) || ((need_q_factor) && (n < 2)))
347
err = GPG_ERR_INV_ARG;
353
n--; /* Need one factor less because we want a specific Q-FACTOR. */
354
fbits = (pbits - 2 * req_qbits -1) / n;
355
qbits = pbits - req_qbits - n * fbits;
359
fbits = (pbits - req_qbits -1) / n;
360
qbits = pbits - n * fbits;
364
log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
365
pbits, req_qbits, qbits, fbits, n);
367
/* Allocate an integer to old the new prime. */
368
prime = gcry_mpi_new (pbits);
370
/* Generate first prime factor. */
371
q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
373
/* Generate a specific Q-Factor if requested. */
375
q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
377
/* Allocate an array to hold all factors + 2 for later usage. */
378
factors = gcry_calloc (n + 2, sizeof (*factors));
381
err = gpg_err_code_from_errno (errno);
385
/* Allocate an array to track pool usage. */
386
pool_in_use = gcry_malloc (n * sizeof *pool_in_use);
389
err = gpg_err_code_from_errno (errno);
392
for (i=0; i < n; i++)
395
/* Make a pool of 3n+5 primes (this is an arbitrary value). We
396
require at least 30 primes for are useful selection process.
398
Fixme: We need to research the best formula for sizing the pool.
401
if (need_q_factor) /* Need some more in this case. */
405
pool = gcry_calloc (m , sizeof (*pool));
408
err = gpg_err_code_from_errno (errno);
412
/* Permutate over the pool of primes until we find a prime of the
417
for (i=0; i < n; i++)
422
/* Allocate new primes. This is done right at the beginning
423
of the loop and if we have later run out of primes. */
424
for (i = 0; i < m; i++)
430
/* Init m_out_of_n(). */
431
perms = gcry_calloc (1, m);
434
err = gpg_err_code_from_errno (errno);
438
if (ath_mutex_lock (&primepool_lock))
440
err = GPG_ERR_INTERNAL;
444
for (i = 0; i < n; i++)
447
/* At a maximum we use strong random for the factors.
448
This saves us a lot of entropy. Given that Q and
449
possible Q-factor are also used in the final prime
450
this should be acceptable. We also don't allocate in
451
secure memory to save on that scare resource too. If
452
Q has been allocated in secure memory, the final
453
prime will be saved there anyway. This is because
454
our MPI routines take care of that. GnuPG has worked
455
this way ever since. */
459
pool[i] = get_pool_prime (fbits, poolrandomlevel);
462
if (ath_mutex_unlock (&primepool_lock))
464
err = GPG_ERR_INTERNAL;
471
pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
473
factors[i] = pool[i];
475
if (is_locked && ath_mutex_unlock (&primepool_lock))
477
err = GPG_ERR_INTERNAL;
484
/* Get next permutation. */
485
m_out_of_n ( (char*)perms, n, m);
486
if (ath_mutex_lock (&primepool_lock))
488
err = GPG_ERR_INTERNAL;
492
for (i = j = 0; (i < m) && (j < n); i++)
495
/* If the subprime has not yet beed generated do it now. */
496
if (!pool[i] && is_locked)
498
pool[i] = get_pool_prime (fbits, poolrandomlevel);
501
if (ath_mutex_unlock (&primepool_lock))
503
err = GPG_ERR_INTERNAL;
510
pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
512
factors[j++] = pool[i];
514
if (is_locked && ath_mutex_unlock (&primepool_lock))
516
err = GPG_ERR_INTERNAL;
522
/* Ran out of permutations: Allocate new primes. */
530
/* Generate next prime candidate:
531
p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.
534
mpi_mul_ui (prime, prime, 2);
536
mpi_mul (prime, prime, q_factor);
537
for(i = 0; i < n; i++)
538
mpi_mul (prime, prime, factors[i]);
539
mpi_add_ui (prime, prime, 1);
540
nprime = mpi_get_nbits (prime);
550
q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
565
q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
572
while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
578
log_mpidump ("prime : ", prime);
579
log_mpidump ("factor q: ", q);
581
log_mpidump ("factor q0: ", q_factor);
582
for (i = 0; i < n; i++)
583
log_mpidump ("factor pi: ", factors[i]);
584
log_debug ("bit sizes: prime=%u, q=%u",
585
mpi_get_nbits (prime), mpi_get_nbits (q));
587
log_debug (", q0=%u", mpi_get_nbits (q_factor));
588
for (i = 0; i < n; i++)
589
log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
595
/* Caller wants the factors. */
596
factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
599
err = gpg_err_code_from_errno (errno);
606
factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
607
factors_new[i++] = mpi_copy (q);
609
factors_new[i++] = mpi_copy (q_factor);
611
factors_new[i++] = mpi_copy (factors[j]);
618
factors_new[i++] = mpi_copy (q_factor);
620
factors_new[i] = mpi_copy (factors[i]);
624
factors_new[i] = mpi_copy (factors[i]);
630
/* Create a generator (start with 3). */
631
gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
632
gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
633
gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
636
err = GPG_ERR_NOT_IMPLEMENTED;
640
factors[n + 1] = mpi_alloc_set_ui (2);
641
mpi_sub_ui (pmin1, prime, 1);
645
mpi_add_ui (g, g, 1);
648
log_debug ("checking g:");
654
for (i = 0; i < n + 2; i++)
656
mpi_fdiv_q (tmp, pmin1, factors[i]);
657
/* No mpi_pow(), but it is okay to use this with mod
659
gcry_mpi_powm (b, g, tmp, prime);
660
if (! mpi_cmp_ui (b, 1))
668
mpi_free (factors[n+1]);
682
is_locked = !ath_mutex_lock (&primepool_lock);
683
for(i = 0; i < m; i++)
687
for (j=0; j < n; j++)
688
if (pool_in_use[j] == i)
690
if (j == n && is_locked)
692
/* This pooled subprime has not been used. */
693
save_pool_prime (pool[i], poolrandomlevel);
699
if (is_locked && ath_mutex_unlock (&primepool_lock))
700
err = GPG_ERR_INTERNAL;
704
gcry_free (pool_in_use);
706
gcry_free (factors); /* Factors are shallow copies. */
716
*prime_generated = prime;
718
*ret_factors = factors_new;
724
for (i = 0; factors_new[i]; i++)
725
mpi_free (factors_new[i]);
726
gcry_free (factors_new);
735
/* Generate a prime used for discrete logarithm algorithms; i.e. this
736
prime will be public and no strong random is required. */
738
_gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
739
gcry_mpi_t g, gcry_mpi_t **ret_factors)
741
gcry_err_code_t err = GPG_ERR_NO_ERROR;
742
gcry_mpi_t prime = NULL;
744
err = prime_generate_internal ((mode == 1), &prime, pbits, qbits, g,
745
ret_factors, GCRY_WEAK_RANDOM, 0, 0,
753
gen_prime (unsigned int nbits, int secret, int randomlevel,
754
int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
756
gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
758
unsigned int x, step;
759
unsigned int count1, count2;
762
/* if ( DBG_CIPHER ) */
763
/* log_debug ("generate a prime of %u bits ", nbits ); */
766
log_fatal ("can't generate a prime with less than %d bits\n", 16);
768
mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
769
/* Make nbits fit into gcry_mpi_t implementation. */
770
val_2 = mpi_alloc_set_ui( 2 );
771
val_3 = mpi_alloc_set_ui( 3);
772
prime = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
773
result = mpi_alloc_like( prime );
774
pminus1= mpi_alloc_like( prime );
775
ptest = mpi_alloc_like( prime );
781
/* generate a random number */
782
gcry_mpi_randomize( prime, nbits, randomlevel );
784
/* Set high order bit to 1, set low order bit to 1. If we are
785
generating a secret prime we are most probably doing that
786
for RSA, to make sure that the modulus does have the
787
requested key size we set the 2 high order bits. */
788
mpi_set_highbit (prime, nbits-1);
790
mpi_set_bit (prime, nbits-2);
791
mpi_set_bit(prime, 0);
793
/* Calculate all remainders. */
794
for (i=0; (x = small_prime_numbers[i]); i++ )
795
mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
797
/* Now try some primes starting with prime. */
798
for(step=0; step < 20000; step += 2 )
800
/* Check against all the small primes we have in mods. */
802
for (i=0; (x = small_prime_numbers[i]); i++ )
804
while ( mods[i] + step >= x )
806
if ( !(mods[i] + step) )
810
continue; /* Found a multiple of an already known prime. */
812
mpi_add_ui( ptest, prime, step );
814
/* Do a fast Fermat test now. */
816
mpi_sub_ui( pminus1, ptest, 1);
817
gcry_mpi_powm( result, val_2, pminus1, ptest );
818
if ( !mpi_cmp_ui( result, 1 ) )
820
/* Not composite, perform stronger tests */
821
if (is_prime(ptest, 5, &count2 ))
823
if (!mpi_test_bit( ptest, nbits-1-secret ))
826
log_debug ("overflow in prime generation\n");
827
break; /* Stop loop, continue with a new prime. */
830
if (extra_check && extra_check (extra_check_arg, ptest))
832
/* The extra check told us that this prime is
833
not of the caller's taste. */
849
if (++dotcount == 10 )
855
progress(':'); /* restart with a new random value */
860
* Returns: true if this may be a prime
861
* RM_ROUNDS gives the number of Rabin-Miller tests to run.
864
check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
865
gcry_prime_check_func_t cb_func, void *cb_arg)
869
unsigned int count=0;
871
/* Check against small primes. */
872
for (i=0; (x = small_prime_numbers[i]); i++ )
874
if ( mpi_divisible_ui( prime, x ) )
878
/* A quick Fermat test. */
880
gcry_mpi_t result = mpi_alloc_like( prime );
881
gcry_mpi_t pminus1 = mpi_alloc_like( prime );
882
mpi_sub_ui( pminus1, prime, 1);
883
gcry_mpi_powm( result, val_2, pminus1, prime );
885
if ( mpi_cmp_ui( result, 1 ) )
895
if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
897
/* Perform stronger tests. */
898
if ( is_prime( prime, rm_rounds, &count ) )
901
|| cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
902
return 1; /* Probably a prime. */
911
* Return true if n is probably a prime
914
is_prime (gcry_mpi_t n, int steps, unsigned int *count)
916
gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
917
gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
918
gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
919
gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
920
gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
924
unsigned nbits = mpi_get_nbits( n );
926
if (steps < 5) /* Make sure that we do at least 5 rounds. */
929
mpi_sub_ui( nminus1, n, 1 );
931
/* Find q and k, so that n = 1 + 2^k * q . */
932
q = mpi_copy ( nminus1 );
933
k = mpi_trailing_zeros ( q );
934
mpi_tdiv_q_2exp (q, q, k);
936
for (i=0 ; i < steps; i++ )
945
gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
947
/* Make sure that the number is smaller than the prime and
948
keep the randomness of the high bit. */
949
if ( mpi_test_bit ( x, nbits-2) )
951
mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
955
mpi_set_highbit( x, nbits-2 );
956
mpi_clear_bit( x, nbits-2 );
958
gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
960
gcry_mpi_powm ( y, x, q, n);
961
if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
963
for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
965
gcry_mpi_powm(y, y, a2, n);
966
if( !mpi_cmp_ui( y, 1 ) )
967
goto leave; /* Not a prime. */
969
if (mpi_cmp( y, nminus1 ) )
970
goto leave; /* Not a prime. */
974
rc = 1; /* May be a prime. */
988
/* Given ARRAY of size N with M elements set to true produce a
989
modified array with the next permutation of M elements. Note, that
990
ARRAY is used in a one-bit-per-byte approach. To detected the last
991
permutation it is useful to intialize the array with the first M
992
element set to true and use this test:
993
m_out_of_n (array, m, n);
994
for (i = j = 0; i < n && j < m; i++)
1000
This code is based on the algorithm 452 from the "Collected
1001
Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
1004
m_out_of_n ( char *array, int m, int n )
1006
int i=0, i1=0, j=0, jp=0, j1=0, k1=0, k2=0;
1011
/* Need to handle this simple case separately. */
1014
for (i=0; i < n; i++ )
1029
for (j=1; j < n; j++ )
1031
if ( array[n-1] == array[n-j-1])
1058
else if( array[k2] && array[k2-1] )
1083
for (i=1; i <= jp; i++ )
1105
/* Now complement the two selected bits. */
1106
array[k1-1] = !array[k1-1];
1107
array[k2-1] = !array[k2-1];
1111
/* Generate a new prime number of PRIME_BITS bits and store it in
1112
PRIME. If FACTOR_BITS is non-zero, one of the prime factors of
1113
(prime - 1) / 2 must be FACTOR_BITS bits long. If FACTORS is
1114
non-zero, allocate a new, NULL-terminated array holding the prime
1115
factors and store it in FACTORS. FLAGS might be used to influence
1116
the prime number generation process. */
1118
gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1119
unsigned int factor_bits, gcry_mpi_t **factors,
1120
gcry_prime_check_func_t cb_func, void *cb_arg,
1121
gcry_random_level_t random_level,
1124
gcry_err_code_t err = GPG_ERR_NO_ERROR;
1125
gcry_mpi_t *factors_generated = NULL;
1126
gcry_mpi_t prime_generated = NULL;
1127
unsigned int mode = 0;
1130
return gpg_error (GPG_ERR_INV_ARG);
1133
if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1137
err = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1139
factors? &factors_generated : NULL,
1140
random_level, flags, 1,
1146
/* Additional check. */
1147
if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1149
/* Failed, deallocate resources. */
1152
mpi_free (prime_generated);
1155
for (i = 0; factors_generated[i]; i++)
1156
mpi_free (factors_generated[i]);
1157
gcry_free (factors_generated);
1159
err = GPG_ERR_GENERAL;
1166
*factors = factors_generated;
1167
*prime = prime_generated;
1170
return gcry_error (err);
1173
/* Check wether the number X is prime. */
1175
gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1177
gcry_err_code_t err = GPG_ERR_NO_ERROR;
1178
gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
1182
/* We use 64 rounds because the prime we are going to test is not
1183
guaranteed to be a random one. */
1184
if (! check_prime (x, val_2, 64, NULL, NULL))
1185
err = GPG_ERR_NO_PRIME;
1189
return gcry_error (err);
1192
/* Find a generator for PRIME where the factorization of (prime-1) is
1193
in the NULL terminated array FACTORS. Return the generator as a
1194
newly allocated MPI in R_G. If START_G is not NULL, use this as s
1195
atart for the search. Returns 0 on success.*/
1197
gcry_prime_group_generator (gcry_mpi_t *r_g,
1198
gcry_mpi_t prime, gcry_mpi_t *factors,
1201
gcry_mpi_t tmp = gcry_mpi_new (0);
1202
gcry_mpi_t b = gcry_mpi_new (0);
1203
gcry_mpi_t pmin1 = gcry_mpi_new (0);
1204
gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
1208
if (!factors || !r_g || !prime)
1209
return gpg_error (GPG_ERR_INV_ARG);
1212
for (n=0; factors[n]; n++)
1215
return gpg_error (GPG_ERR_INV_ARG);
1217
/* Extra sanity check - usually disabled. */
1218
/* mpi_set (tmp, factors[0]); */
1219
/* for(i = 1; i < n; i++) */
1220
/* mpi_mul (tmp, tmp, factors[i]); */
1221
/* mpi_add_ui (tmp, tmp, 1); */
1222
/* if (mpi_cmp (prime, tmp)) */
1223
/* return gpg_error (GPG_ERR_INV_ARG); */
1225
gcry_mpi_sub_ui (pmin1, prime, 1);
1231
gcry_mpi_add_ui (g, g, 1);
1235
log_debug ("checking g:");
1242
for (i = 0; i < n; i++)
1244
mpi_fdiv_q (tmp, pmin1, factors[i]);
1245
gcry_mpi_powm (b, g, tmp, prime);
1246
if (! mpi_cmp_ui (b, 1))
1254
gcry_mpi_release (tmp);
1255
gcry_mpi_release (b);
1256
gcry_mpi_release (pmin1);
1262
/* Convenience function to release the factors array. */
1264
gcry_prime_release_factors (gcry_mpi_t *factors)
1270
for (i=0; factors[i]; i++)
1271
mpi_free (factors[i]);
1272
gcry_free (factors);
1278
/* Helper for _gcry_derive_x931_prime. */
1280
find_x931_prime (const gcry_mpi_t pfirst)
1282
gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1285
prime = gcry_mpi_copy (pfirst);
1286
/* If P is even add 1. */
1287
mpi_set_bit (prime, 0);
1289
/* We use 64 Rabin-Miller rounds which is better and thus
1290
sufficient. We do not have a Lucas test implementaion thus we
1291
can't do it in the X9.31 preferred way of running a few
1292
Rabin-Miller followed by one Lucas test. */
1293
while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1294
mpi_add_ui (prime, prime, 2);
1302
/* Generate a prime using the algorithm from X9.31 appendix B.4.
1304
This function requires that the provided public exponent E is odd.
1305
XP, XP1 and XP2 are the seed values. All values are mandatory.
1307
On success the prime is returned. If R_P1 or R_P2 are given the
1308
internal values P1 and P2 are saved at these addresses. On error
1309
NULL is returned. */
1311
_gcry_derive_x931_prime (const gcry_mpi_t xp,
1312
const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1314
gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1316
gcry_mpi_t p1, p2, p1p2, yp0;
1318
if (!xp || !xp1 || !xp2)
1320
if (!e || !mpi_test_bit (e, 0))
1321
return NULL; /* We support only odd values for E. */
1323
p1 = find_x931_prime (xp1);
1324
p2 = find_x931_prime (xp2);
1325
p1p2 = mpi_alloc_like (xp);
1326
mpi_mul (p1p2, p1, p2);
1331
/* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1332
tmp = mpi_alloc_like (p1);
1333
mpi_invm (tmp, p2, p1);
1334
mpi_mul (tmp, tmp, p2);
1337
tmp = mpi_alloc_like (p2);
1338
mpi_invm (tmp, p1, p2);
1339
mpi_mul (tmp, tmp, p1);
1340
mpi_sub (r1, r1, tmp);
1342
/* Fixup a negative value. */
1343
if (mpi_is_neg (r1))
1344
mpi_add (r1, r1, p1p2);
1346
/* yp0 = xp + (r1 - xp mod p1*p2) */
1347
yp0 = tmp; tmp = NULL;
1348
mpi_subm (yp0, r1, xp, p1p2);
1349
mpi_add (yp0, yp0, xp);
1352
/* Fixup a negative value. */
1353
if (mpi_cmp (yp0, xp) < 0 )
1354
mpi_add (yp0, yp0, p1p2);
1357
/* yp0 is now the first integer greater than xp with p1 being a
1358
large prime factor of yp0-1 and p2 a large prime factor of yp0+1. */
1360
/* Note that the first example from X9.31 (D.1.1) which uses
1361
(Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1362
(Xq2 #134E4CAA16D2350A21D775C404#)
1363
(Xq #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1364
7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1365
6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1368
#CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1369
7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1370
BF20CB896EE37E098A906313271422162CB6C642
1373
#CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1374
7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1375
C88FE299D52D78BE405A97E01FD71DD7819ECB91
1377
as stated in the standard. This seems to be a bug in X9.31.
1381
gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1382
gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1385
mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body. */
1386
mpi_sub_ui (yp0, yp0, 1); /* Ditto. */
1389
gcdres = gcry_mpi_gcd (gcdtmp, e, yp0);
1390
mpi_add_ui (yp0, yp0, 1);
1392
progress ('/'); /* gcd (e, yp0-1) != 1 */
1393
else if (check_prime (yp0, val_2, 64, NULL, NULL))
1395
/* We add p1p2-1 because yp0 is incremented after the gcd test. */
1396
mpi_add (yp0, yp0, p1p2);
1418
/* Generate the two prime used for DSA using the algorithm specified
1419
in FIPS 186-2. PBITS is the desired length of the prime P and a
1420
QBITS the length of the prime Q. If SEED is not supplied and
1421
SEEDLEN is 0 the function generates an appropriate SEED. On
1422
success the generated primes are stored at R_Q and R_P, the counter
1423
value is stored at R_COUNTER and the seed actually used for
1424
generation is stored at R_SEED and R_SEEDVALUE. */
1426
_gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1427
const void *seed, size_t seedlen,
1428
gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1430
void **r_seed, size_t *r_seedlen)
1433
unsigned char seed_help_buffer[160/8]; /* Used to hold a generated SEED. */
1434
unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */
1435
unsigned char digest[160/8]; /* Helper buffer for SHA-1 digest. */
1436
gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */
1437
gcry_mpi_t tmpval = NULL; /* Helper variable. */
1440
unsigned char value_u[160/8];
1441
int value_n, value_b, value_k;
1443
gcry_mpi_t value_w = NULL;
1444
gcry_mpi_t value_x = NULL;
1445
gcry_mpi_t prime_q = NULL;
1446
gcry_mpi_t prime_p = NULL;
1448
/* FIPS 186-2 allows only for 1024/160 bit. */
1449
if (pbits != 1024 || qbits != 160)
1450
return GPG_ERR_INV_KEYLEN;
1452
if (!seed && !seedlen)
1453
; /* No seed value given: We are asked to generate it. */
1454
else if (!seed || seedlen < qbits/8)
1455
return GPG_ERR_INV_ARG;
1457
/* Allocate a buffer to later compute SEED+some_increment. */
1458
seed_plus = gcry_malloc (seedlen < 20? 20:seedlen);
1461
ec = gpg_err_code_from_syserror ();
1465
val_2 = mpi_alloc_set_ui (2);
1466
value_n = (pbits - 1) / qbits;
1467
value_b = (pbits - 1) - value_n * qbits;
1468
value_w = gcry_mpi_new (pbits);
1469
value_x = gcry_mpi_new (pbits);
1475
/* Step 1: Generate a (new) seed unless one has been supplied. */
1478
seedlen = sizeof seed_help_buffer;
1479
gcry_create_nonce (seed_help_buffer, seedlen);
1480
seed = seed_help_buffer;
1483
/* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits}) */
1484
memcpy (seed_plus, seed, seedlen);
1485
for (i=seedlen-1; i >= 0; i--)
1491
gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1492
gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1493
for (i=0; i < sizeof value_u; i++)
1494
value_u[i] ^= digest[i];
1496
/* Step 3: Form q from U */
1497
gcry_mpi_release (prime_q); prime_q = NULL;
1498
ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1499
value_u, sizeof value_u, NULL));
1502
mpi_set_highbit (prime_q, qbits-1 );
1503
mpi_set_bit (prime_q, 0);
1505
/* Step 4: Test whether Q is prime using 64 round of Rabin-Miller. */
1506
if (check_prime (prime_q, val_2, 64, NULL, NULL))
1507
break; /* Yes, Q is prime. */
1510
seed = NULL; /* Force a new seed at Step 1. */
1513
/* Step 6. Note that we do no use an explicit offset but increment
1514
SEED_PLUS accordingly. SEED_PLUS is currently SEED+1. */
1518
prime_p = gcry_mpi_new (pbits);
1521
/* Step 7: For k = 0,...n let
1522
V_k = sha1(seed+offset+k) mod 2^{qbits}
1523
Step 8: W = V_0 + V_1*2^160 +
1525
+ V_{n-1}*2^{(n-1)*160}
1526
+ (V_{n} mod 2^b)*2^{n*160}
1528
mpi_set_ui (value_w, 0);
1529
for (value_k=0; value_k <= value_n; value_k++)
1531
/* There is no need to have an explicit offset variable: In
1532
the first round we shall have an offset of 2, this is
1533
achieved by using SEED_PLUS which is already at SEED+1,
1534
thus we just need to increment it once again. The
1535
requirement for the next round is to update offset by N,
1536
which we implictly did at the end of this loop, and then
1537
to add one; this one is the same as in the first round. */
1538
for (i=seedlen-1; i >= 0; i--)
1544
gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1546
gcry_mpi_release (tmpval); tmpval = NULL;
1547
ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1548
digest, sizeof digest, NULL));
1551
if (value_k == value_n)
1552
mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1553
mpi_lshift (tmpval, tmpval, value_k*qbits);
1554
mpi_add (value_w, value_w, tmpval);
1557
/* Step 8 continued: X = W + 2^{L-1} */
1558
mpi_set_ui (value_x, 0);
1559
mpi_set_highbit (value_x, pbits-1);
1560
mpi_add (value_x, value_x, value_w);
1562
/* Step 9: c = X mod 2q, p = X - (c - 1) */
1563
mpi_mul_2exp (tmpval, prime_q, 1);
1564
mpi_mod (tmpval, value_x, tmpval);
1565
mpi_sub_ui (tmpval, tmpval, 1);
1566
mpi_sub (prime_p, value_x, tmpval);
1568
/* Step 10: If p < 2^{L-1} skip the primality test. */
1569
/* Step 11 and 12: Primality test. */
1570
if (mpi_get_nbits (prime_p) >= pbits-1
1571
&& check_prime (prime_p, val_2, 64, NULL, NULL) )
1572
break; /* Yes, P is prime, continue with Step 15. */
1574
/* Step 13: counter = counter + 1, offset = offset + n + 1. */
1577
/* Step 14: If counter >= 2^12 goto Step 1. */
1578
if (counter >= 4096)
1582
/* Step 15: Save p, q, counter and seed. */
1583
/* log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1584
/* mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1585
/* log_printhex("fips186-2 seed:", seed, seedlen); */
1586
/* log_mpidump ("fips186-2 prime p", prime_p); */
1587
/* log_mpidump ("fips186-2 prime q", prime_q); */
1599
*r_counter = counter;
1600
if (r_seed && r_seedlen)
1602
memcpy (seed_plus, seed, seedlen);
1603
*r_seed = seed_plus;
1605
*r_seedlen = seedlen;
1610
gcry_mpi_release (tmpval);
1611
gcry_mpi_release (value_x);
1612
gcry_mpi_release (value_w);
1613
gcry_mpi_release (prime_p);
1614
gcry_mpi_release (prime_q);
1615
gcry_free (seed_plus);
1616
gcry_mpi_release (val_2);
1622
/* WARNING: The code below has not yet been tested! However, it is
1623
not yet used. We need to wait for FIPS 186-3 final and for test
1626
Generate the two prime used for DSA using the algorithm specified
1627
in FIPS 186-3, A.1.1.2. PBITS is the desired length of the prime P
1628
and a QBITS the length of the prime Q. If SEED is not supplied and
1629
SEEDLEN is 0 the function generates an appropriate SEED. On
1630
success the generated primes are stored at R_Q and R_P, the counter
1631
value is stored at R_COUNTER and the seed actually used for
1632
generation is stored at R_SEED and R_SEEDVALUE. The hash algorithm
1633
used is stored at R_HASHALGO.
1635
Note that this function is very similar to the fips186_2 code. Due
1636
to the minor differences, other buffer sizes and for documentarion,
1637
we use a separate function.
1640
_gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1641
const void *seed, size_t seedlen,
1642
gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1644
void **r_seed, size_t *r_seedlen,
1648
unsigned char seed_help_buffer[256/8]; /* Used to hold a generated SEED. */
1649
unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */
1650
unsigned char digest[256/8]; /* Helper buffer for SHA-1 digest. */
1651
gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */
1652
gcry_mpi_t tmpval = NULL; /* Helper variable. */
1653
int hashalgo; /* The id of the Approved Hash Function. */
1656
unsigned char value_u[256/8];
1657
int value_n, value_b, value_j;
1659
gcry_mpi_t value_w = NULL;
1660
gcry_mpi_t value_x = NULL;
1661
gcry_mpi_t prime_q = NULL;
1662
gcry_mpi_t prime_p = NULL;
1664
gcry_assert (sizeof seed_help_buffer == sizeof digest
1665
&& sizeof seed_help_buffer == sizeof value_u);
1667
/* Step 1: Check the requested prime lengths. */
1668
/* Note that due to the size of our buffers QBITS is limited to 256. */
1669
if (pbits == 1024 && qbits == 160)
1670
hashalgo = GCRY_MD_SHA1;
1671
else if (pbits == 2048 && qbits == 224)
1672
hashalgo = GCRY_MD_SHA224;
1673
else if (pbits == 2048 && qbits == 256)
1674
hashalgo = GCRY_MD_SHA256;
1675
else if (pbits == 3072 && qbits == 256)
1676
hashalgo = GCRY_MD_SHA256;
1678
return GPG_ERR_INV_KEYLEN;
1680
/* Also check that the hash algorithm is available. */
1681
ec = gpg_err_code (gcry_md_test_algo (hashalgo));
1684
gcry_assert (qbits/8 <= sizeof digest);
1685
gcry_assert (gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1688
/* Step 2: Check seedlen. */
1689
if (!seed && !seedlen)
1690
; /* No seed value given: We are asked to generate it. */
1691
else if (!seed || seedlen < qbits/8)
1692
return GPG_ERR_INV_ARG;
1694
/* Allocate a buffer to later compute SEED+some_increment and a few
1695
helper variables. */
1696
seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer?
1697
sizeof seed_help_buffer : seedlen);
1700
ec = gpg_err_code_from_syserror ();
1703
val_2 = mpi_alloc_set_ui (2);
1704
value_w = gcry_mpi_new (pbits);
1705
value_x = gcry_mpi_new (pbits);
1707
/* Step 3: n = \lceil L / outlen \rceil - 1 */
1708
value_n = (pbits + qbits - 1) / qbits - 1;
1709
/* Step 4: b = L - 1 - (n * outlen) */
1710
value_b = pbits - 1 - (value_n * qbits);
1716
/* Step 5: Generate a (new) seed unless one has been supplied. */
1720
gcry_assert (seedlen <= sizeof seed_help_buffer);
1721
gcry_create_nonce (seed_help_buffer, seedlen);
1722
seed = seed_help_buffer;
1725
/* Step 6: U = hash(seed) */
1726
gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1728
/* Step 7: q = 2^{N-1} + U + 1 - (U mod 2) */
1729
if ( !(value_u[qbits/8-1] & 0x01) )
1731
for (i=qbits/8-1; i >= 0; i--)
1738
gcry_mpi_release (prime_q); prime_q = NULL;
1739
ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1740
value_u, sizeof value_u, NULL));
1743
mpi_set_highbit (prime_q, qbits-1 );
1745
/* Step 8: Test whether Q is prime using 64 round of Rabin-Miller.
1746
According to table C.1 this is sufficient for all
1747
supported prime sizes (i.e. up 3072/256). */
1748
if (check_prime (prime_q, val_2, 64, NULL, NULL))
1749
break; /* Yes, Q is prime. */
1752
seed = NULL; /* Force a new seed at Step 5. */
1755
/* Step 11. Note that we do no use an explicit offset but increment
1756
SEED_PLUS accordingly. */
1757
memcpy (seed_plus, seed, seedlen);
1761
prime_p = gcry_mpi_new (pbits);
1764
/* Step 11.1: For j = 0,...n let
1765
V_j = hash(seed+offset+j)
1766
Step 11.2: W = V_0 + V_1*2^outlen +
1768
+ V_{n-1}*2^{(n-1)*outlen}
1769
+ (V_{n} mod 2^b)*2^{n*outlen}
1771
mpi_set_ui (value_w, 0);
1772
for (value_j=0; value_j <= value_n; value_j++)
1774
/* There is no need to have an explicit offset variable: In
1775
the first round we shall have an offset of 1 and a j of
1776
0. This is achieved by incrementing SEED_PLUS here. For
1777
the next round offset is implicitly updated by using
1779
for (i=seedlen-1; i >= 0; i--)
1785
gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1787
gcry_mpi_release (tmpval); tmpval = NULL;
1788
ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1789
digest, sizeof digest, NULL));
1792
if (value_j == value_n)
1793
mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1794
mpi_lshift (tmpval, tmpval, value_j*qbits);
1795
mpi_add (value_w, value_w, tmpval);
1798
/* Step 11.3: X = W + 2^{L-1} */
1799
mpi_set_ui (value_x, 0);
1800
mpi_set_highbit (value_x, pbits-1);
1801
mpi_add (value_x, value_x, value_w);
1803
/* Step 11.4: c = X mod 2q */
1804
mpi_mul_2exp (tmpval, prime_q, 1);
1805
mpi_mod (tmpval, value_x, tmpval);
1807
/* Step 11.5: p = X - (c - 1) */
1808
mpi_sub_ui (tmpval, tmpval, 1);
1809
mpi_sub (prime_p, value_x, tmpval);
1811
/* Step 11.6: If p < 2^{L-1} skip the primality test. */
1812
/* Step 11.7 and 11.8: Primality test. */
1813
if (mpi_get_nbits (prime_p) >= pbits-1
1814
&& check_prime (prime_p, val_2, 64, NULL, NULL) )
1815
break; /* Yes, P is prime, continue with Step 15. */
1817
/* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1818
If counter >= 4L goto Step 5. */
1820
if (counter >= 4*pbits)
1824
/* Step 12: Save p, q, counter and seed. */
1825
log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n",
1826
mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter);
1827
log_printhex("fips186-3 seed:", seed, seedlen);
1828
log_mpidump ("fips186-3 prime p", prime_p);
1829
log_mpidump ("fips186-3 prime q", prime_q);
1841
*r_counter = counter;
1842
if (r_seed && r_seedlen)
1844
memcpy (seed_plus, seed, seedlen);
1845
*r_seed = seed_plus;
1847
*r_seedlen = seedlen;
1850
*r_hashalgo = hashalgo;
1853
gcry_mpi_release (tmpval);
1854
gcry_mpi_release (value_x);
1855
gcry_mpi_release (value_w);
1856
gcry_mpi_release (prime_p);
1857
gcry_mpi_release (prime_q);
1858
gcry_free (seed_plus);
1859
gcry_mpi_release (val_2);
added
removed
lib/libgcrypt/cipher/primegen.c
