1
/* This file was automatically imported with
2
import_gcry.py. Please don't modify it */
3
/* primegen.c - prime number generator
4
* Copyright (C) 1998, 2000, 2001, 2002, 2003
5
* 2004, 2008 Free Software Foundation, Inc.
7
* This file is part of Libgcrypt.
9
* Libgcrypt is free software; you can redistribute it and/or modify
10
* it under the terms of the GNU Lesser general Public License as
11
* published by the Free Software Foundation; either version 2.1 of
12
* the License, or (at your option) any later version.
14
* Libgcrypt is distributed in the hope that it will be useful,
15
* but WITHOUT ANY WARRANTY; without even the implied warranty of
16
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
* GNU Lesser General Public License for more details.
19
* You should have received a copy of the GNU Lesser General Public
20
* License along with this program; if not, write to the Free Software
21
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
31
static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel,
32
int (*extra_check)(void *, gcry_mpi_t),
33
void *extra_check_arg);
34
static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
35
gcry_prime_check_func_t cb_func, void *cb_arg );
36
static int is_prime (gcry_mpi_t n, int steps, unsigned int *count);
37
static void m_out_of_n( char *array, int m, int n );
39
static void (*progress_cb) (void *,const char*,int,int, int );
40
static void *progress_cb_data;
42
/* Note: 2 is not included because it can be tested more easily by
43
looking at bit 0. The last entry in this list is marked by a zero */
44
static ushort small_prime_numbers[] = {
45
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
46
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
47
103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
48
157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
49
211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
50
269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
51
331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
52
389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
53
449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
54
509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
55
587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
56
643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
57
709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
58
773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
59
853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
60
919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
61
991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
62
1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
63
1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
64
1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
65
1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
66
1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
67
1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
68
1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
69
1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
70
1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
71
1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
72
1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
73
1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
74
1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
75
1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
76
1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
77
1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
78
1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
79
2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
80
2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
81
2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
82
2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
83
2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
84
2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
85
2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
86
2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
87
2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
88
2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
89
2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
90
2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
91
2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
92
2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
93
2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
94
3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
95
3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
96
3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
97
3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
98
3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
99
3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
100
3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
101
3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
102
3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
103
3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
104
3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
105
3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
106
3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
107
3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
108
3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
109
4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
110
4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
111
4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
112
4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
113
4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
114
4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
115
4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
116
4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
117
4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
118
4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
119
4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
120
4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
121
4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
122
4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
123
4957, 4967, 4969, 4973, 4987, 4993, 4999,
126
static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
130
/* An object and a list to build up a global pool of primes. See
131
save_pool_prime and get_pool_prime. */
134
struct primepool_s *next;
135
gcry_mpi_t prime; /* If this is NULL the entry is not used. */
137
gcry_random_level_t randomlevel;
139
struct primepool_s *primepool;
140
/* Mutex used to protect access to the primepool. */
141
static ath_mutex_t primepool_lock = ATH_MUTEX_INITIALIZER;
145
/* Save PRIME which has been generated at RANDOMLEVEL for later
146
use. Needs to be called while primepool_lock is being hold. Note
147
that PRIME should be considered released after calling this
150
save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel)
152
struct primepool_s *item, *item2;
155
for (n=0, item = primepool; item; item = item->next, n++)
158
if (!item && n > 100)
160
/* Remove some of the entries. Our strategy is removing
161
the last third from the list. */
164
for (i=0, item2 = primepool; item2; item2 = item2->next)
168
gcry_mpi_release (item2->prime);
177
item = gcry_calloc (1, sizeof *item);
180
/* Out of memory. Silently giving up. */
181
gcry_mpi_release (prime);
184
item->next = primepool;
188
item->nbits = mpi_get_nbits (prime);
189
item->randomlevel = randomlevel;
193
/* Return a prime for the prime pool or NULL if none has been found.
194
The prime needs to match NBITS and randomlevel. This function needs
195
to be called why the primepool_look is being hold. */
197
get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel)
199
struct primepool_s *item;
201
for (item = primepool; item; item = item->next)
203
&& item->nbits == nbits && item->randomlevel == randomlevel)
205
gcry_mpi_t prime = item->prime;
207
gcry_assert (nbits == mpi_get_nbits (prime));
219
_gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
223
progress_cb_data = cb_data;
231
progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
236
* Generate a prime number (stored in secure memory)
239
_gcry_generate_secret_prime (unsigned int nbits,
240
gcry_random_level_t random_level,
241
int (*extra_check)(void*, gcry_mpi_t),
242
void *extra_check_arg)
246
prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg);
252
/* Generate a prime number which may be public, i.e. not allocated in
255
_gcry_generate_public_prime (unsigned int nbits,
256
gcry_random_level_t random_level,
257
int (*extra_check)(void*, gcry_mpi_t),
258
void *extra_check_arg)
262
prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg);
268
/* Core prime generation function. The algorithm used to generate
269
practically save primes is due to Lim and Lee as described in the
270
CRYPTO '97 proceedings (ISBN3540633847) page 260.
272
NEED_Q_FACTOR: If true make sure that at least one factor is of
273
size qbits. This is for example required for DSA.
274
PRIME_GENERATED: Adresss of a variable where the resulting prime
275
number will be stored.
276
PBITS: Requested size of the prime number. At least 48.
277
QBITS: One factor of the prime needs to be of this size. Maybe 0
278
if this is not required. See also MODE.
279
G: If not NULL an MPI which will receive a generator for the prime
280
for use with Elgamal.
281
RET_FACTORS: if not NULL, an array with all factors are stored at
283
ALL_FACTORS: If set to true all factors of prime-1 are returned.
284
RANDOMLEVEL: How strong should the random numers be.
285
FLAGS: Prime generation bit flags. Currently supported:
286
GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret.
287
CB_FUNC, CB_ARG: Callback to be used for extra checks.
290
static gcry_err_code_t
291
prime_generate_internal (int need_q_factor,
292
gcry_mpi_t *prime_generated, unsigned int pbits,
293
unsigned int qbits, gcry_mpi_t g,
294
gcry_mpi_t **ret_factors,
295
gcry_random_level_t randomlevel, unsigned int flags,
297
gcry_prime_check_func_t cb_func, void *cb_arg)
299
gcry_err_code_t err = 0;
300
gcry_mpi_t *factors_new = NULL; /* Factors to return to the
302
gcry_mpi_t *factors = NULL; /* Current factors. */
303
gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */
304
gcry_mpi_t *pool = NULL; /* Pool of primes. */
305
int *pool_in_use = NULL; /* Array with currently used POOL elements. */
306
unsigned char *perms = NULL; /* Permutations of POOL. */
307
gcry_mpi_t q_factor = NULL; /* Used if QBITS is non-zero. */
308
unsigned int fbits = 0; /* Length of prime factors. */
309
unsigned int n = 0; /* Number of factors. */
310
unsigned int m = 0; /* Number of primes in pool. */
311
gcry_mpi_t q = NULL; /* First prime factor. */
312
gcry_mpi_t prime = NULL; /* Prime candidate. */
313
unsigned int nprime = 0; /* Bits of PRIME. */
314
unsigned int req_qbits; /* The original QBITS value. */
315
gcry_mpi_t val_2; /* For check_prime(). */
316
int is_locked = 0; /* Flag to help unlocking the primepool. */
317
unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
318
unsigned int count1 = 0, count2 = 0;
319
unsigned int i = 0, j = 0;
322
return GPG_ERR_INV_ARG;
324
/* We won't use a too strong random elvel for the pooled subprimes. */
325
poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM?
326
GCRY_STRONG_RANDOM : randomlevel);
329
/* If QBITS is not given, assume a reasonable value. */
335
/* Find number of needed prime factors N. */
336
for (n = 1; (pbits - qbits - 1) / n >= qbits; n++)
340
val_2 = mpi_alloc_set_ui (2);
342
if ((! n) || ((need_q_factor) && (n < 2)))
344
err = GPG_ERR_INV_ARG;
350
n--; /* Need one factor less because we want a specific Q-FACTOR. */
351
fbits = (pbits - 2 * req_qbits -1) / n;
352
qbits = pbits - req_qbits - n * fbits;
356
fbits = (pbits - req_qbits -1) / n;
357
qbits = pbits - n * fbits;
361
log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
362
pbits, req_qbits, qbits, fbits, n);
364
/* Allocate an integer to old the new prime. */
365
prime = gcry_mpi_new (pbits);
367
/* Generate first prime factor. */
368
q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
370
/* Generate a specific Q-Factor if requested. */
372
q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
374
/* Allocate an array to hold all factors + 2 for later usage. */
375
factors = gcry_calloc (n + 2, sizeof (*factors));
378
err = gpg_err_code_from_errno (errno);
382
/* Allocate an array to track pool usage. */
383
pool_in_use = gcry_malloc (n * sizeof *pool_in_use);
386
err = gpg_err_code_from_errno (errno);
389
for (i=0; i < n; i++)
392
/* Make a pool of 3n+5 primes (this is an arbitrary value). We
393
require at least 30 primes for are useful selection process.
395
Fixme: We need to research the best formula for sizing the pool.
398
if (need_q_factor) /* Need some more in this case. */
402
pool = gcry_calloc (m , sizeof (*pool));
405
err = gpg_err_code_from_errno (errno);
409
/* Permutate over the pool of primes until we find a prime of the
414
for (i=0; i < n; i++)
419
/* Allocate new primes. This is done right at the beginning
420
of the loop and if we have later run out of primes. */
421
for (i = 0; i < m; i++)
427
/* Init m_out_of_n(). */
428
perms = gcry_calloc (1, m);
431
err = gpg_err_code_from_errno (errno);
435
if (ath_mutex_lock (&primepool_lock))
437
err = GPG_ERR_INTERNAL;
441
for (i = 0; i < n; i++)
444
/* At a maximum we use strong random for the factors.
445
This saves us a lot of entropy. Given that Q and
446
possible Q-factor are also used in the final prime
447
this should be acceptable. We also don't allocate in
448
secure memory to save on that scare resource too. If
449
Q has been allocated in secure memory, the final
450
prime will be saved there anyway. This is because
451
our MPI routines take care of that. GnuPG has worked
452
this way ever since. */
456
pool[i] = get_pool_prime (fbits, poolrandomlevel);
459
if (ath_mutex_unlock (&primepool_lock))
461
err = GPG_ERR_INTERNAL;
468
pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
470
factors[i] = pool[i];
472
if (is_locked && ath_mutex_unlock (&primepool_lock))
474
err = GPG_ERR_INTERNAL;
481
/* Get next permutation. */
482
m_out_of_n ( (char*)perms, n, m);
483
if (ath_mutex_lock (&primepool_lock))
485
err = GPG_ERR_INTERNAL;
489
for (i = j = 0; (i < m) && (j < n); i++)
492
/* If the subprime has not yet beed generated do it now. */
493
if (!pool[i] && is_locked)
495
pool[i] = get_pool_prime (fbits, poolrandomlevel);
498
if (ath_mutex_unlock (&primepool_lock))
500
err = GPG_ERR_INTERNAL;
507
pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
509
factors[j++] = pool[i];
511
if (is_locked && ath_mutex_unlock (&primepool_lock))
513
err = GPG_ERR_INTERNAL;
519
/* Ran out of permutations: Allocate new primes. */
527
/* Generate next prime candidate:
528
p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.
531
mpi_mul_ui (prime, prime, 2);
533
mpi_mul (prime, prime, q_factor);
534
for(i = 0; i < n; i++)
535
mpi_mul (prime, prime, factors[i]);
536
mpi_add_ui (prime, prime, 1);
537
nprime = mpi_get_nbits (prime);
547
q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
562
q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
569
while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
575
log_mpidump ("prime : ", prime);
576
log_mpidump ("factor q: ", q);
578
log_mpidump ("factor q0: ", q_factor);
579
for (i = 0; i < n; i++)
580
log_mpidump ("factor pi: ", factors[i]);
581
log_debug ("bit sizes: prime=%u, q=%u",
582
mpi_get_nbits (prime), mpi_get_nbits (q));
584
log_debug (", q0=%u", mpi_get_nbits (q_factor));
585
for (i = 0; i < n; i++)
586
log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
592
/* Caller wants the factors. */
593
factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
596
err = gpg_err_code_from_errno (errno);
603
factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
604
factors_new[i++] = mpi_copy (q);
606
factors_new[i++] = mpi_copy (q_factor);
608
factors_new[i++] = mpi_copy (factors[j]);
615
factors_new[i++] = mpi_copy (q_factor);
617
factors_new[i] = mpi_copy (factors[i]);
621
factors_new[i] = mpi_copy (factors[i]);
627
/* Create a generator (start with 3). */
628
gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
629
gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
630
gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
633
err = GPG_ERR_NOT_IMPLEMENTED;
637
factors[n + 1] = mpi_alloc_set_ui (2);
638
mpi_sub_ui (pmin1, prime, 1);
642
mpi_add_ui (g, g, 1);
645
log_debug ("checking g:");
651
for (i = 0; i < n + 2; i++)
653
mpi_fdiv_q (tmp, pmin1, factors[i]);
654
/* No mpi_pow(), but it is okay to use this with mod
656
gcry_mpi_powm (b, g, tmp, prime);
657
if (! mpi_cmp_ui (b, 1))
665
mpi_free (factors[n+1]);
679
is_locked = !ath_mutex_lock (&primepool_lock);
680
for(i = 0; i < m; i++)
684
for (j=0; j < n; j++)
685
if (pool_in_use[j] == i)
687
if (j == n && is_locked)
689
/* This pooled subprime has not been used. */
690
save_pool_prime (pool[i], poolrandomlevel);
696
if (is_locked && ath_mutex_unlock (&primepool_lock))
697
err = GPG_ERR_INTERNAL;
701
gcry_free (pool_in_use);
703
gcry_free (factors); /* Factors are shallow copies. */
713
*prime_generated = prime;
715
*ret_factors = factors_new;
721
for (i = 0; factors_new[i]; i++)
722
mpi_free (factors_new[i]);
723
gcry_free (factors_new);
732
/* Generate a prime used for discrete logarithm algorithms; i.e. this
733
prime will be public and no strong random is required. */
735
_gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
736
gcry_mpi_t g, gcry_mpi_t **ret_factors)
738
gcry_err_code_t err = GPG_ERR_NO_ERROR;
739
gcry_mpi_t prime = NULL;
741
err = prime_generate_internal ((mode == 1), &prime, pbits, qbits, g,
742
ret_factors, GCRY_WEAK_RANDOM, 0, 0,
750
gen_prime (unsigned int nbits, int secret, int randomlevel,
751
int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
753
gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
755
unsigned int x, step;
756
unsigned int count1, count2;
759
/* if ( DBG_CIPHER ) */
760
/* log_debug ("generate a prime of %u bits ", nbits ); */
763
log_fatal ("can't generate a prime with less than %d bits\n", 16);
765
mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
766
/* Make nbits fit into gcry_mpi_t implementation. */
767
val_2 = mpi_alloc_set_ui( 2 );
768
val_3 = mpi_alloc_set_ui( 3);
769
prime = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
770
result = mpi_alloc_like( prime );
771
pminus1= mpi_alloc_like( prime );
772
ptest = mpi_alloc_like( prime );
778
/* generate a random number */
779
gcry_mpi_randomize( prime, nbits, randomlevel );
781
/* Set high order bit to 1, set low order bit to 1. If we are
782
generating a secret prime we are most probably doing that
783
for RSA, to make sure that the modulus does have the
784
requested key size we set the 2 high order bits. */
785
mpi_set_highbit (prime, nbits-1);
787
mpi_set_bit (prime, nbits-2);
788
mpi_set_bit(prime, 0);
790
/* Calculate all remainders. */
791
for (i=0; (x = small_prime_numbers[i]); i++ )
792
mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
794
/* Now try some primes starting with prime. */
795
for(step=0; step < 20000; step += 2 )
797
/* Check against all the small primes we have in mods. */
799
for (i=0; (x = small_prime_numbers[i]); i++ )
801
while ( mods[i] + step >= x )
803
if ( !(mods[i] + step) )
807
continue; /* Found a multiple of an already known prime. */
809
mpi_add_ui( ptest, prime, step );
811
/* Do a fast Fermat test now. */
813
mpi_sub_ui( pminus1, ptest, 1);
814
gcry_mpi_powm( result, val_2, pminus1, ptest );
815
if ( !mpi_cmp_ui( result, 1 ) )
817
/* Not composite, perform stronger tests */
818
if (is_prime(ptest, 5, &count2 ))
820
if (!mpi_test_bit( ptest, nbits-1-secret ))
823
log_debug ("overflow in prime generation\n");
824
break; /* Stop loop, continue with a new prime. */
827
if (extra_check && extra_check (extra_check_arg, ptest))
829
/* The extra check told us that this prime is
830
not of the caller's taste. */
846
if (++dotcount == 10 )
852
progress(':'); /* restart with a new random value */
857
* Returns: true if this may be a prime
858
* RM_ROUNDS gives the number of Rabin-Miller tests to run.
861
check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
862
gcry_prime_check_func_t cb_func, void *cb_arg)
866
unsigned int count=0;
868
/* Check against small primes. */
869
for (i=0; (x = small_prime_numbers[i]); i++ )
871
if ( mpi_divisible_ui( prime, x ) )
875
/* A quick Fermat test. */
877
gcry_mpi_t result = mpi_alloc_like( prime );
878
gcry_mpi_t pminus1 = mpi_alloc_like( prime );
879
mpi_sub_ui( pminus1, prime, 1);
880
gcry_mpi_powm( result, val_2, pminus1, prime );
882
if ( mpi_cmp_ui( result, 1 ) )
892
if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
894
/* Perform stronger tests. */
895
if ( is_prime( prime, rm_rounds, &count ) )
898
|| cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
899
return 1; /* Probably a prime. */
908
* Return true if n is probably a prime
911
is_prime (gcry_mpi_t n, int steps, unsigned int *count)
913
gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
914
gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
915
gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
916
gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
917
gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
921
unsigned nbits = mpi_get_nbits( n );
923
if (steps < 5) /* Make sure that we do at least 5 rounds. */
926
mpi_sub_ui( nminus1, n, 1 );
928
/* Find q and k, so that n = 1 + 2^k * q . */
929
q = mpi_copy ( nminus1 );
930
k = mpi_trailing_zeros ( q );
931
mpi_tdiv_q_2exp (q, q, k);
933
for (i=0 ; i < steps; i++ )
942
gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
944
/* Make sure that the number is smaller than the prime and
945
keep the randomness of the high bit. */
946
if ( mpi_test_bit ( x, nbits-2) )
948
mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
952
mpi_set_highbit( x, nbits-2 );
953
mpi_clear_bit( x, nbits-2 );
955
gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
957
gcry_mpi_powm ( y, x, q, n);
958
if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
960
for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
962
gcry_mpi_powm(y, y, a2, n);
963
if( !mpi_cmp_ui( y, 1 ) )
964
goto leave; /* Not a prime. */
966
if (mpi_cmp( y, nminus1 ) )
967
goto leave; /* Not a prime. */
971
rc = 1; /* May be a prime. */
985
/* Given ARRAY of size N with M elements set to true produce a
986
modified array with the next permutation of M elements. Note, that
987
ARRAY is used in a one-bit-per-byte approach. To detected the last
988
permutation it is useful to intialize the array with the first M
989
element set to true and use this test:
990
m_out_of_n (array, m, n);
991
for (i = j = 0; i < n && j < m; i++)
997
This code is based on the algorithm 452 from the "Collected
998
Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
1001
m_out_of_n ( char *array, int m, int n )
1003
int i=0, i1=0, j=0, jp=0, j1=0, k1=0, k2=0;
1008
/* Need to handle this simple case separately. */
1011
for (i=0; i < n; i++ )
1026
for (j=1; j < n; j++ )
1028
if ( array[n-1] == array[n-j-1])
1055
else if( array[k2] && array[k2-1] )
1080
for (i=1; i <= jp; i++ )
1102
/* Now complement the two selected bits. */
1103
array[k1-1] = !array[k1-1];
1104
array[k2-1] = !array[k2-1];
1108
/* Generate a new prime number of PRIME_BITS bits and store it in
1109
PRIME. If FACTOR_BITS is non-zero, one of the prime factors of
1110
(prime - 1) / 2 must be FACTOR_BITS bits long. If FACTORS is
1111
non-zero, allocate a new, NULL-terminated array holding the prime
1112
factors and store it in FACTORS. FLAGS might be used to influence
1113
the prime number generation process. */
1115
gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1116
unsigned int factor_bits, gcry_mpi_t **factors,
1117
gcry_prime_check_func_t cb_func, void *cb_arg,
1118
gcry_random_level_t random_level,
1121
gcry_err_code_t err = GPG_ERR_NO_ERROR;
1122
gcry_mpi_t *factors_generated = NULL;
1123
gcry_mpi_t prime_generated = NULL;
1124
unsigned int mode = 0;
1127
return gpg_error (GPG_ERR_INV_ARG);
1130
if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1134
err = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1136
factors? &factors_generated : NULL,
1137
random_level, flags, 1,
1143
/* Additional check. */
1144
if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1146
/* Failed, deallocate resources. */
1149
mpi_free (prime_generated);
1152
for (i = 0; factors_generated[i]; i++)
1153
mpi_free (factors_generated[i]);
1154
gcry_free (factors_generated);
1156
err = GPG_ERR_GENERAL;
1163
*factors = factors_generated;
1164
*prime = prime_generated;
1167
return gcry_error (err);
1170
/* Check wether the number X is prime. */
1172
gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1174
gcry_err_code_t err = GPG_ERR_NO_ERROR;
1175
gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
1179
/* We use 64 rounds because the prime we are going to test is not
1180
guaranteed to be a random one. */
1181
if (! check_prime (x, val_2, 64, NULL, NULL))
1182
err = GPG_ERR_NO_PRIME;
1186
return gcry_error (err);
1189
/* Find a generator for PRIME where the factorization of (prime-1) is
1190
in the NULL terminated array FACTORS. Return the generator as a
1191
newly allocated MPI in R_G. If START_G is not NULL, use this as s
1192
atart for the search. Returns 0 on success.*/
1194
gcry_prime_group_generator (gcry_mpi_t *r_g,
1195
gcry_mpi_t prime, gcry_mpi_t *factors,
1198
gcry_mpi_t tmp = gcry_mpi_new (0);
1199
gcry_mpi_t b = gcry_mpi_new (0);
1200
gcry_mpi_t pmin1 = gcry_mpi_new (0);
1201
gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
1205
if (!factors || !r_g || !prime)
1206
return gpg_error (GPG_ERR_INV_ARG);
1209
for (n=0; factors[n]; n++)
1212
return gpg_error (GPG_ERR_INV_ARG);
1214
/* Extra sanity check - usually disabled. */
1215
/* mpi_set (tmp, factors[0]); */
1216
/* for(i = 1; i < n; i++) */
1217
/* mpi_mul (tmp, tmp, factors[i]); */
1218
/* mpi_add_ui (tmp, tmp, 1); */
1219
/* if (mpi_cmp (prime, tmp)) */
1220
/* return gpg_error (GPG_ERR_INV_ARG); */
1222
gcry_mpi_sub_ui (pmin1, prime, 1);
1228
gcry_mpi_add_ui (g, g, 1);
1232
log_debug ("checking g:");
1239
for (i = 0; i < n; i++)
1241
mpi_fdiv_q (tmp, pmin1, factors[i]);
1242
gcry_mpi_powm (b, g, tmp, prime);
1243
if (! mpi_cmp_ui (b, 1))
1251
gcry_mpi_release (tmp);
1252
gcry_mpi_release (b);
1253
gcry_mpi_release (pmin1);
1259
/* Convenience function to release the factors array. */
1261
gcry_prime_release_factors (gcry_mpi_t *factors)
1267
for (i=0; factors[i]; i++)
1268
mpi_free (factors[i]);
1269
gcry_free (factors);
1275
/* Helper for _gcry_derive_x931_prime. */
1277
find_x931_prime (const gcry_mpi_t pfirst)
1279
gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1282
prime = gcry_mpi_copy (pfirst);
1283
/* If P is even add 1. */
1284
mpi_set_bit (prime, 0);
1286
/* We use 64 Rabin-Miller rounds which is better and thus
1287
sufficient. We do not have a Lucas test implementaion thus we
1288
can't do it in the X9.31 preferred way of running a few
1289
Rabin-Miller followed by one Lucas test. */
1290
while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1291
mpi_add_ui (prime, prime, 2);
1299
/* Generate a prime using the algorithm from X9.31 appendix B.4.
1301
This function requires that the provided public exponent E is odd.
1302
XP, XP1 and XP2 are the seed values. All values are mandatory.
1304
On success the prime is returned. If R_P1 or R_P2 are given the
1305
internal values P1 and P2 are saved at these addresses. On error
1306
NULL is returned. */
1308
_gcry_derive_x931_prime (const gcry_mpi_t xp,
1309
const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1311
gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1313
gcry_mpi_t p1, p2, p1p2, yp0;
1315
if (!xp || !xp1 || !xp2)
1317
if (!e || !mpi_test_bit (e, 0))
1318
return NULL; /* We support only odd values for E. */
1320
p1 = find_x931_prime (xp1);
1321
p2 = find_x931_prime (xp2);
1322
p1p2 = mpi_alloc_like (xp);
1323
mpi_mul (p1p2, p1, p2);
1328
/* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1329
tmp = mpi_alloc_like (p1);
1330
mpi_invm (tmp, p2, p1);
1331
mpi_mul (tmp, tmp, p2);
1334
tmp = mpi_alloc_like (p2);
1335
mpi_invm (tmp, p1, p2);
1336
mpi_mul (tmp, tmp, p1);
1337
mpi_sub (r1, r1, tmp);
1339
/* Fixup a negative value. */
1340
if (mpi_is_neg (r1))
1341
mpi_add (r1, r1, p1p2);
1343
/* yp0 = xp + (r1 - xp mod p1*p2) */
1344
yp0 = tmp; tmp = NULL;
1345
mpi_subm (yp0, r1, xp, p1p2);
1346
mpi_add (yp0, yp0, xp);
1349
/* Fixup a negative value. */
1350
if (mpi_cmp (yp0, xp) < 0 )
1351
mpi_add (yp0, yp0, p1p2);
1354
/* yp0 is now the first integer greater than xp with p1 being a
1355
large prime factor of yp0-1 and p2 a large prime factor of yp0+1. */
1357
/* Note that the first example from X9.31 (D.1.1) which uses
1358
(Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1359
(Xq2 #134E4CAA16D2350A21D775C404#)
1360
(Xq #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1361
7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1362
6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1365
#CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1366
7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1367
BF20CB896EE37E098A906313271422162CB6C642
1370
#CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1371
7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1372
C88FE299D52D78BE405A97E01FD71DD7819ECB91
1374
as stated in the standard. This seems to be a bug in X9.31.
1378
gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1379
gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1382
mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body. */
1383
mpi_sub_ui (yp0, yp0, 1); /* Ditto. */
1386
gcdres = gcry_mpi_gcd (gcdtmp, e, yp0);
1387
mpi_add_ui (yp0, yp0, 1);
1389
progress ('/'); /* gcd (e, yp0-1) != 1 */
1390
else if (check_prime (yp0, val_2, 64, NULL, NULL))
1392
/* We add p1p2-1 because yp0 is incremented after the gcd test. */
1393
mpi_add (yp0, yp0, p1p2);
1415
/* Generate the two prime used for DSA using the algorithm specified
1416
in FIPS 186-2. PBITS is the desired length of the prime P and a
1417
QBITS the length of the prime Q. If SEED is not supplied and
1418
SEEDLEN is 0 the function generates an appropriate SEED. On
1419
success the generated primes are stored at R_Q and R_P, the counter
1420
value is stored at R_COUNTER and the seed actually used for
1421
generation is stored at R_SEED and R_SEEDVALUE. */
1423
_gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1424
const void *seed, size_t seedlen,
1425
gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1427
void **r_seed, size_t *r_seedlen)
1430
unsigned char seed_help_buffer[160/8]; /* Used to hold a generated SEED. */
1431
unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */
1432
unsigned char digest[160/8]; /* Helper buffer for SHA-1 digest. */
1433
gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */
1434
gcry_mpi_t tmpval = NULL; /* Helper variable. */
1437
unsigned char value_u[160/8];
1438
int value_n, value_b, value_k;
1440
gcry_mpi_t value_w = NULL;
1441
gcry_mpi_t value_x = NULL;
1442
gcry_mpi_t prime_q = NULL;
1443
gcry_mpi_t prime_p = NULL;
1445
/* FIPS 186-2 allows only for 1024/160 bit. */
1446
if (pbits != 1024 || qbits != 160)
1447
return GPG_ERR_INV_KEYLEN;
1449
if (!seed && !seedlen)
1450
; /* No seed value given: We are asked to generate it. */
1451
else if (!seed || seedlen < qbits/8)
1452
return GPG_ERR_INV_ARG;
1454
/* Allocate a buffer to later compute SEED+some_increment. */
1455
seed_plus = gcry_malloc (seedlen < 20? 20:seedlen);
1458
ec = gpg_err_code_from_syserror ();
1462
val_2 = mpi_alloc_set_ui (2);
1463
value_n = (pbits - 1) / qbits;
1464
value_b = (pbits - 1) - value_n * qbits;
1465
value_w = gcry_mpi_new (pbits);
1466
value_x = gcry_mpi_new (pbits);
1472
/* Step 1: Generate a (new) seed unless one has been supplied. */
1475
seedlen = sizeof seed_help_buffer;
1476
gcry_create_nonce (seed_help_buffer, seedlen);
1477
seed = seed_help_buffer;
1480
/* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits}) */
1481
memcpy (seed_plus, seed, seedlen);
1482
for (i=seedlen-1; i >= 0; i--)
1488
gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1489
gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1490
for (i=0; i < sizeof value_u; i++)
1491
value_u[i] ^= digest[i];
1493
/* Step 3: Form q from U */
1494
gcry_mpi_release (prime_q); prime_q = NULL;
1495
ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1496
value_u, sizeof value_u, NULL));
1499
mpi_set_highbit (prime_q, qbits-1 );
1500
mpi_set_bit (prime_q, 0);
1502
/* Step 4: Test whether Q is prime using 64 round of Rabin-Miller. */
1503
if (check_prime (prime_q, val_2, 64, NULL, NULL))
1504
break; /* Yes, Q is prime. */
1507
seed = NULL; /* Force a new seed at Step 1. */
1510
/* Step 6. Note that we do no use an explicit offset but increment
1511
SEED_PLUS accordingly. SEED_PLUS is currently SEED+1. */
1515
prime_p = gcry_mpi_new (pbits);
1518
/* Step 7: For k = 0,...n let
1519
V_k = sha1(seed+offset+k) mod 2^{qbits}
1520
Step 8: W = V_0 + V_1*2^160 +
1522
+ V_{n-1}*2^{(n-1)*160}
1523
+ (V_{n} mod 2^b)*2^{n*160}
1525
mpi_set_ui (value_w, 0);
1526
for (value_k=0; value_k <= value_n; value_k++)
1528
/* There is no need to have an explicit offset variable: In
1529
the first round we shall have an offset of 2, this is
1530
achieved by using SEED_PLUS which is already at SEED+1,
1531
thus we just need to increment it once again. The
1532
requirement for the next round is to update offset by N,
1533
which we implictly did at the end of this loop, and then
1534
to add one; this one is the same as in the first round. */
1535
for (i=seedlen-1; i >= 0; i--)
1541
gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1543
gcry_mpi_release (tmpval); tmpval = NULL;
1544
ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1545
digest, sizeof digest, NULL));
1548
if (value_k == value_n)
1549
mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1550
mpi_lshift (tmpval, tmpval, value_k*qbits);
1551
mpi_add (value_w, value_w, tmpval);
1554
/* Step 8 continued: X = W + 2^{L-1} */
1555
mpi_set_ui (value_x, 0);
1556
mpi_set_highbit (value_x, pbits-1);
1557
mpi_add (value_x, value_x, value_w);
1559
/* Step 9: c = X mod 2q, p = X - (c - 1) */
1560
mpi_mul_2exp (tmpval, prime_q, 1);
1561
mpi_mod (tmpval, value_x, tmpval);
1562
mpi_sub_ui (tmpval, tmpval, 1);
1563
mpi_sub (prime_p, value_x, tmpval);
1565
/* Step 10: If p < 2^{L-1} skip the primality test. */
1566
/* Step 11 and 12: Primality test. */
1567
if (mpi_get_nbits (prime_p) >= pbits-1
1568
&& check_prime (prime_p, val_2, 64, NULL, NULL) )
1569
break; /* Yes, P is prime, continue with Step 15. */
1571
/* Step 13: counter = counter + 1, offset = offset + n + 1. */
1574
/* Step 14: If counter >= 2^12 goto Step 1. */
1575
if (counter >= 4096)
1579
/* Step 15: Save p, q, counter and seed. */
1580
/* log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1581
/* mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1582
/* log_printhex("fips186-2 seed:", seed, seedlen); */
1583
/* log_mpidump ("fips186-2 prime p", prime_p); */
1584
/* log_mpidump ("fips186-2 prime q", prime_q); */
1596
*r_counter = counter;
1597
if (r_seed && r_seedlen)
1599
memcpy (seed_plus, seed, seedlen);
1600
*r_seed = seed_plus;
1602
*r_seedlen = seedlen;
1607
gcry_mpi_release (tmpval);
1608
gcry_mpi_release (value_x);
1609
gcry_mpi_release (value_w);
1610
gcry_mpi_release (prime_p);
1611
gcry_mpi_release (prime_q);
1612
gcry_free (seed_plus);
1613
gcry_mpi_release (val_2);
1619
/* WARNING: The code below has not yet been tested! However, it is
1620
not yet used. We need to wait for FIPS 186-3 final and for test
1623
Generate the two prime used for DSA using the algorithm specified
1624
in FIPS 186-3, A.1.1.2. PBITS is the desired length of the prime P
1625
and a QBITS the length of the prime Q. If SEED is not supplied and
1626
SEEDLEN is 0 the function generates an appropriate SEED. On
1627
success the generated primes are stored at R_Q and R_P, the counter
1628
value is stored at R_COUNTER and the seed actually used for
1629
generation is stored at R_SEED and R_SEEDVALUE. The hash algorithm
1630
used is stored at R_HASHALGO.
1632
Note that this function is very similar to the fips186_2 code. Due
1633
to the minor differences, other buffer sizes and for documentarion,
1634
we use a separate function.
1637
_gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1638
const void *seed, size_t seedlen,
1639
gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1641
void **r_seed, size_t *r_seedlen,
1645
unsigned char seed_help_buffer[256/8]; /* Used to hold a generated SEED. */
1646
unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */
1647
unsigned char digest[256/8]; /* Helper buffer for SHA-1 digest. */
1648
gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */
1649
gcry_mpi_t tmpval = NULL; /* Helper variable. */
1650
int hashalgo; /* The id of the Approved Hash Function. */
1653
unsigned char value_u[256/8];
1654
int value_n, value_b, value_j;
1656
gcry_mpi_t value_w = NULL;
1657
gcry_mpi_t value_x = NULL;
1658
gcry_mpi_t prime_q = NULL;
1659
gcry_mpi_t prime_p = NULL;
1661
gcry_assert (sizeof seed_help_buffer == sizeof digest
1662
&& sizeof seed_help_buffer == sizeof value_u);
1664
/* Step 1: Check the requested prime lengths. */
1665
/* Note that due to the size of our buffers QBITS is limited to 256. */
1666
if (pbits == 1024 && qbits == 160)
1667
hashalgo = GCRY_MD_SHA1;
1668
else if (pbits == 2048 && qbits == 224)
1669
hashalgo = GCRY_MD_SHA224;
1670
else if (pbits == 2048 && qbits == 256)
1671
hashalgo = GCRY_MD_SHA256;
1672
else if (pbits == 3072 && qbits == 256)
1673
hashalgo = GCRY_MD_SHA256;
1675
return GPG_ERR_INV_KEYLEN;
1677
/* Also check that the hash algorithm is available. */
1678
ec = gpg_err_code (gcry_md_test_algo (hashalgo));
1681
gcry_assert (qbits/8 <= sizeof digest);
1682
gcry_assert (gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1685
/* Step 2: Check seedlen. */
1686
if (!seed && !seedlen)
1687
; /* No seed value given: We are asked to generate it. */
1688
else if (!seed || seedlen < qbits/8)
1689
return GPG_ERR_INV_ARG;
1691
/* Allocate a buffer to later compute SEED+some_increment and a few
1692
helper variables. */
1693
seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer?
1694
sizeof seed_help_buffer : seedlen);
1697
ec = gpg_err_code_from_syserror ();
1700
val_2 = mpi_alloc_set_ui (2);
1701
value_w = gcry_mpi_new (pbits);
1702
value_x = gcry_mpi_new (pbits);
1704
/* Step 3: n = \lceil L / outlen \rceil - 1 */
1705
value_n = (pbits + qbits - 1) / qbits - 1;
1706
/* Step 4: b = L - 1 - (n * outlen) */
1707
value_b = pbits - 1 - (value_n * qbits);
1713
/* Step 5: Generate a (new) seed unless one has been supplied. */
1717
gcry_assert (seedlen <= sizeof seed_help_buffer);
1718
gcry_create_nonce (seed_help_buffer, seedlen);
1719
seed = seed_help_buffer;
1722
/* Step 6: U = hash(seed) */
1723
gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1725
/* Step 7: q = 2^{N-1} + U + 1 - (U mod 2) */
1726
if ( !(value_u[qbits/8-1] & 0x01) )
1728
for (i=qbits/8-1; i >= 0; i--)
1735
gcry_mpi_release (prime_q); prime_q = NULL;
1736
ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1737
value_u, sizeof value_u, NULL));
1740
mpi_set_highbit (prime_q, qbits-1 );
1742
/* Step 8: Test whether Q is prime using 64 round of Rabin-Miller.
1743
According to table C.1 this is sufficient for all
1744
supported prime sizes (i.e. up 3072/256). */
1745
if (check_prime (prime_q, val_2, 64, NULL, NULL))
1746
break; /* Yes, Q is prime. */
1749
seed = NULL; /* Force a new seed at Step 5. */
1752
/* Step 11. Note that we do no use an explicit offset but increment
1753
SEED_PLUS accordingly. */
1754
memcpy (seed_plus, seed, seedlen);
1758
prime_p = gcry_mpi_new (pbits);
1761
/* Step 11.1: For j = 0,...n let
1762
V_j = hash(seed+offset+j)
1763
Step 11.2: W = V_0 + V_1*2^outlen +
1765
+ V_{n-1}*2^{(n-1)*outlen}
1766
+ (V_{n} mod 2^b)*2^{n*outlen}
1768
mpi_set_ui (value_w, 0);
1769
for (value_j=0; value_j <= value_n; value_j++)
1771
/* There is no need to have an explicit offset variable: In
1772
the first round we shall have an offset of 1 and a j of
1773
0. This is achieved by incrementing SEED_PLUS here. For
1774
the next round offset is implicitly updated by using
1776
for (i=seedlen-1; i >= 0; i--)
1782
gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1784
gcry_mpi_release (tmpval); tmpval = NULL;
1785
ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1786
digest, sizeof digest, NULL));
1789
if (value_j == value_n)
1790
mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1791
mpi_lshift (tmpval, tmpval, value_j*qbits);
1792
mpi_add (value_w, value_w, tmpval);
1795
/* Step 11.3: X = W + 2^{L-1} */
1796
mpi_set_ui (value_x, 0);
1797
mpi_set_highbit (value_x, pbits-1);
1798
mpi_add (value_x, value_x, value_w);
1800
/* Step 11.4: c = X mod 2q */
1801
mpi_mul_2exp (tmpval, prime_q, 1);
1802
mpi_mod (tmpval, value_x, tmpval);
1804
/* Step 11.5: p = X - (c - 1) */
1805
mpi_sub_ui (tmpval, tmpval, 1);
1806
mpi_sub (prime_p, value_x, tmpval);
1808
/* Step 11.6: If p < 2^{L-1} skip the primality test. */
1809
/* Step 11.7 and 11.8: Primality test. */
1810
if (mpi_get_nbits (prime_p) >= pbits-1
1811
&& check_prime (prime_p, val_2, 64, NULL, NULL) )
1812
break; /* Yes, P is prime, continue with Step 15. */
1814
/* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1815
If counter >= 4L goto Step 5. */
1817
if (counter >= 4*pbits)
1821
/* Step 12: Save p, q, counter and seed. */
1822
log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n",
1823
mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter);
1824
log_printhex("fips186-3 seed:", seed, seedlen);
1825
log_mpidump ("fips186-3 prime p", prime_p);
1826
log_mpidump ("fips186-3 prime q", prime_q);
1838
*r_counter = counter;
1839
if (r_seed && r_seedlen)
1841
memcpy (seed_plus, seed, seedlen);
1842
*r_seed = seed_plus;
1844
*r_seedlen = seedlen;
1847
*r_hashalgo = hashalgo;
1850
gcry_mpi_release (tmpval);
1851
gcry_mpi_release (value_x);
1852
gcry_mpi_release (value_w);
1853
gcry_mpi_release (prime_p);
1854
gcry_mpi_release (prime_q);
1855
gcry_free (seed_plus);
1856
gcry_mpi_release (val_2);
added
removed
grub-core/lib/libgcrypt-grub/cipher/primegen.c
