Beautify debug output of the prime generator.
[libgcrypt.git] / cipher / primegen.c
1 /* primegen.c - prime number generator
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003
3  *               2004, 2008 Free Software Foundation, Inc.
4  *
5  * This file is part of Libgcrypt.
6  *
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.
11  *
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.
16  *
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
20  */
21
22 #include <config.h>
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <errno.h>
28
29 #include "g10lib.h"
30 #include "mpi.h"
31 #include "cipher.h"
32 #include "ath.h"
33
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 );
41
42 static void (*progress_cb) (void *,const char*,int,int, int );
43 static void *progress_cb_data;
44
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,
127     0
128 };
129 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
130
131
132 \f
133 /* An object and a list to build up a global pool of primes.  See
134    save_pool_prime and get_pool_prime. */
135 struct primepool_s
136 {
137   struct primepool_s *next;
138   gcry_mpi_t prime;      /* If this is NULL the entry is not used. */
139   unsigned int nbits;
140   gcry_random_level_t randomlevel;
141 };
142 struct primepool_s *primepool;
143 /* Mutex used to protect access to the primepool.  */
144 static ath_mutex_t primepool_lock;
145
146
147 gcry_err_code_t
148 _gcry_primegen_init (void)
149 {
150   gcry_err_code_t ec;
151
152   ec = ath_mutex_init (&primepool_lock);
153   if (ec)
154     return gpg_err_code_from_errno (ec);
155   return ec;
156 }
157
158
159 /* Save PRIME which has been generated at RANDOMLEVEL for later
160    use. Needs to be called while primepool_lock is being hold.  Note
161    that PRIME should be considered released after calling this
162    function. */
163 static void
164 save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel)
165 {
166   struct primepool_s *item, *item2;
167   size_t n;
168
169   for (n=0, item = primepool; item; item = item->next, n++)
170     if (!item->prime)
171       break;
172   if (!item && n > 100)
173     {
174       /* Remove some of the entries.  Our strategy is removing
175          the last third from the list. */
176       int i;
177
178       for (i=0, item2 = primepool; item2; item2 = item2->next)
179         {
180           if (i >= n/3*2)
181             {
182               gcry_mpi_release (item2->prime);
183               item2->prime = NULL;
184               if (!item)
185                 item = item2;
186             }
187         }
188     }
189   if (!item)
190     {
191       item = gcry_calloc (1, sizeof *item);
192       if (!item)
193         {
194           /* Out of memory.  Silently giving up. */
195           gcry_mpi_release (prime);
196           return;
197         }
198       item->next = primepool;
199       primepool = item;
200     }
201   item->prime = prime;
202   item->nbits = mpi_get_nbits (prime);
203   item->randomlevel = randomlevel;
204 }
205
206
207 /* Return a prime for the prime pool or NULL if none has been found.
208    The prime needs to match NBITS and randomlevel. This function needs
209    to be called with the primepool_look is being hold. */
210 static gcry_mpi_t
211 get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel)
212 {
213   struct primepool_s *item;
214
215   for (item = primepool; item; item = item->next)
216     if (item->prime
217         && item->nbits == nbits && item->randomlevel == randomlevel)
218       {
219         gcry_mpi_t prime = item->prime;
220         item->prime = NULL;
221         gcry_assert (nbits == mpi_get_nbits (prime));
222         return prime;
223       }
224   return NULL;
225 }
226
227
228
229
230
231 \f
232 void
233 _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
234                                    void *cb_data )
235 {
236   progress_cb = cb;
237   progress_cb_data = cb_data;
238 }
239
240
241 static void
242 progress( int c )
243 {
244   if ( progress_cb )
245     progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
246 }
247
248
249 /****************
250  * Generate a prime number (stored in secure memory)
251  */
252 gcry_mpi_t
253 _gcry_generate_secret_prime (unsigned int nbits,
254                              gcry_random_level_t random_level,
255                              int (*extra_check)(void*, gcry_mpi_t),
256                              void *extra_check_arg)
257 {
258   gcry_mpi_t prime;
259
260   prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg);
261   progress('\n');
262   return prime;
263 }
264
265
266 /* Generate a prime number which may be public, i.e. not allocated in
267    secure memory.  */
268 gcry_mpi_t
269 _gcry_generate_public_prime (unsigned int nbits,
270                              gcry_random_level_t random_level,
271                              int (*extra_check)(void*, gcry_mpi_t),
272                              void *extra_check_arg)
273 {
274   gcry_mpi_t prime;
275
276   prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg);
277   progress('\n');
278   return prime;
279 }
280
281
282 /* Core prime generation function.  The algorithm used to generate
283    practically save primes is due to Lim and Lee as described in the
284    CRYPTO '97 proceedings (ISBN3540633847) page 260.
285
286    NEED_Q_FACTOR: If true make sure that at least one factor is of
287                   size qbits.  This is for example required for DSA.
288    PRIME_GENERATED: Adresss of a variable where the resulting prime
289                     number will be stored.
290    PBITS: Requested size of the prime number.  At least 48.
291    QBITS: One factor of the prime needs to be of this size.  Maybe 0
292           if this is not required.  See also MODE.
293    G: If not NULL an MPI which will receive a generator for the prime
294       for use with Elgamal.
295    RET_FACTORS: if not NULL, an array with all factors are stored at
296                 that address.
297    ALL_FACTORS: If set to true all factors of prime-1 are returned.
298    RANDOMLEVEL:  How strong should the random numers be.
299    FLAGS: Prime generation bit flags. Currently supported:
300           GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret.
301    CB_FUNC, CB_ARG:  Callback to be used for extra checks.
302
303  */
304 static gcry_err_code_t
305 prime_generate_internal (int need_q_factor,
306                          gcry_mpi_t *prime_generated, unsigned int pbits,
307                          unsigned int qbits, gcry_mpi_t g,
308                          gcry_mpi_t **ret_factors,
309                          gcry_random_level_t randomlevel, unsigned int flags,
310                          int all_factors,
311                          gcry_prime_check_func_t cb_func, void *cb_arg)
312 {
313   gcry_err_code_t err = 0;
314   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
315                                      caller.  */
316   gcry_mpi_t *factors = NULL;   /* Current factors.  */
317   gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */
318   gcry_mpi_t *pool = NULL;      /* Pool of primes.  */
319   int *pool_in_use = NULL;      /* Array with currently used POOL elements. */
320   unsigned char *perms = NULL;  /* Permutations of POOL.  */
321   gcry_mpi_t q_factor = NULL;   /* Used if QBITS is non-zero.  */
322   unsigned int fbits = 0;       /* Length of prime factors.  */
323   unsigned int n = 0;           /* Number of factors.  */
324   unsigned int m = 0;           /* Number of primes in pool.  */
325   gcry_mpi_t q = NULL;          /* First prime factor.  */
326   gcry_mpi_t prime = NULL;      /* Prime candidate.  */
327   unsigned int nprime = 0;      /* Bits of PRIME.  */
328   unsigned int req_qbits;       /* The original QBITS value.  */
329   gcry_mpi_t val_2;             /* For check_prime().  */
330   int is_locked = 0;            /* Flag to help unlocking the primepool. */
331   unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
332   unsigned int count1 = 0, count2 = 0;
333   unsigned int i = 0, j = 0;
334
335   if (pbits < 48)
336     return GPG_ERR_INV_ARG;
337
338   /* We won't use a too strong random elvel for the pooled subprimes. */
339   poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM?
340                      GCRY_STRONG_RANDOM : randomlevel);
341
342
343   /* If QBITS is not given, assume a reasonable value. */
344   if (!qbits)
345     qbits = pbits / 3;
346
347   req_qbits = qbits;
348
349   /* Find number of needed prime factors N.  */
350   for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++)
351     ;
352   n--;
353
354   val_2 = mpi_alloc_set_ui (2);
355
356   if ((! n) || ((need_q_factor) && (n < 2)))
357     {
358       err = GPG_ERR_INV_ARG;
359       goto leave;
360     }
361
362   if (need_q_factor)
363     {
364       n--;  /* Need one factor less because we want a specific Q-FACTOR. */
365       fbits = (pbits - 2 * req_qbits -1) / n;
366       qbits =  pbits - req_qbits - n * fbits;
367     }
368   else
369     {
370       fbits = (pbits - req_qbits -1) / n;
371       qbits = pbits - n * fbits;
372     }
373
374   if (DBG_CIPHER)
375     log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
376                pbits, req_qbits, qbits, fbits, n);
377
378   /* Allocate an integer to old the new prime. */
379   prime = gcry_mpi_new (pbits);
380
381   /* Generate first prime factor.  */
382   q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
383
384   /* Generate a specific Q-Factor if requested. */
385   if (need_q_factor)
386     q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
387
388   /* Allocate an array to hold all factors + 2 for later usage.  */
389   factors = gcry_calloc (n + 2, sizeof (*factors));
390   if (!factors)
391     {
392       err = gpg_err_code_from_errno (errno);
393       goto leave;
394     }
395
396   /* Allocate an array to track pool usage. */
397   pool_in_use = gcry_malloc (n * sizeof *pool_in_use);
398   if (!pool_in_use)
399     {
400       err = gpg_err_code_from_errno (errno);
401       goto leave;
402     }
403   for (i=0; i < n; i++)
404     pool_in_use[i] = -1;
405
406   /* Make a pool of 3n+5 primes (this is an arbitrary value).  We
407      require at least 30 primes for are useful selection process.
408
409      Fixme: We need to research the best formula for sizing the pool.
410   */
411   m = n * 3 + 5;
412   if (need_q_factor) /* Need some more in this case. */
413     m += 5;
414   if (m < 30)
415     m = 30;
416   pool = gcry_calloc (m , sizeof (*pool));
417   if (! pool)
418     {
419       err = gpg_err_code_from_errno (errno);
420       goto leave;
421     }
422
423   /* Permutate over the pool of primes until we find a prime of the
424      requested length.  */
425   do
426     {
427     next_try:
428       for (i=0; i < n; i++)
429         pool_in_use[i] = -1;
430
431       if (!perms)
432         {
433           /* Allocate new primes.  This is done right at the beginning
434              of the loop and if we have later run out of primes. */
435           for (i = 0; i < m; i++)
436             {
437               mpi_free (pool[i]);
438               pool[i] = NULL;
439             }
440
441           /* Init m_out_of_n().  */
442           perms = gcry_calloc (1, m);
443           if (!perms)
444             {
445               err = gpg_err_code_from_errno (errno);
446               goto leave;
447             }
448
449           if (ath_mutex_lock (&primepool_lock))
450             {
451               err = GPG_ERR_INTERNAL;
452               goto leave;
453             }
454           is_locked = 1;
455           for (i = 0; i < n; i++)
456             {
457               perms[i] = 1;
458               /* At a maximum we use strong random for the factors.
459                  This saves us a lot of entropy. Given that Q and
460                  possible Q-factor are also used in the final prime
461                  this should be acceptable.  We also don't allocate in
462                  secure memory to save on that scare resource too.  If
463                  Q has been allocated in secure memory, the final
464                  prime will be saved there anyway.  This is because
465                  our MPI routines take care of that.  GnuPG has worked
466                  this way ever since.  */
467               pool[i] = NULL;
468               if (is_locked)
469                 {
470                   pool[i] = get_pool_prime (fbits, poolrandomlevel);
471                   if (!pool[i])
472                     {
473                       if (ath_mutex_unlock (&primepool_lock))
474                         {
475                           err = GPG_ERR_INTERNAL;
476                           goto leave;
477                         }
478                       is_locked = 0;
479                     }
480                 }
481               if (!pool[i])
482                 pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
483               pool_in_use[i] = i;
484               factors[i] = pool[i];
485             }
486           if (is_locked && ath_mutex_unlock (&primepool_lock))
487             {
488               err = GPG_ERR_INTERNAL;
489               goto leave;
490             }
491           is_locked = 0;
492         }
493       else
494         {
495           /* Get next permutation. */
496           m_out_of_n ( (char*)perms, n, m);
497           if (ath_mutex_lock (&primepool_lock))
498             {
499               err = GPG_ERR_INTERNAL;
500               goto leave;
501             }
502           is_locked = 1;
503           for (i = j = 0; (i < m) && (j < n); i++)
504             if (perms[i])
505               {
506                 /* If the subprime has not yet beed generated do it now. */
507                 if (!pool[i] && is_locked)
508                   {
509                     pool[i] = get_pool_prime (fbits, poolrandomlevel);
510                     if (!pool[i])
511                       {
512                         if (ath_mutex_unlock (&primepool_lock))
513                           {
514                             err = GPG_ERR_INTERNAL;
515                             goto leave;
516                           }
517                         is_locked = 0;
518                       }
519                   }
520                 if (!pool[i])
521                   pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
522                 pool_in_use[j] = i;
523                 factors[j++] = pool[i];
524               }
525           if (is_locked && ath_mutex_unlock (&primepool_lock))
526             {
527               err = GPG_ERR_INTERNAL;
528               goto leave;
529             }
530           is_locked = 0;
531           if (i == n)
532             {
533               /* Ran out of permutations: Allocate new primes.  */
534               gcry_free (perms);
535               perms = NULL;
536               progress ('!');
537               goto next_try;
538             }
539         }
540
541         /* Generate next prime candidate:
542            p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.
543          */
544         mpi_set (prime, q);
545         mpi_mul_ui (prime, prime, 2);
546         if (need_q_factor)
547           mpi_mul (prime, prime, q_factor);
548         for(i = 0; i < n; i++)
549           mpi_mul (prime, prime, factors[i]);
550         mpi_add_ui (prime, prime, 1);
551         nprime = mpi_get_nbits (prime);
552
553         if (nprime < pbits)
554           {
555             if (++count1 > 20)
556               {
557                 count1 = 0;
558                 qbits++;
559                 progress('>');
560                 mpi_free (q);
561                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
562                 goto next_try;
563               }
564           }
565         else
566           count1 = 0;
567
568         if (nprime > pbits)
569           {
570             if (++count2 > 20)
571               {
572                 count2 = 0;
573                 qbits--;
574                 progress('<');
575                 mpi_free (q);
576                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
577                 goto next_try;
578               }
579           }
580         else
581           count2 = 0;
582     }
583   while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
584                                               cb_func, cb_arg)));
585
586   if (DBG_CIPHER)
587     {
588       progress ('\n');
589       log_mpidump ("prime    ", prime);
590       log_mpidump ("factor  q", q);
591       if (need_q_factor)
592         log_mpidump ("factor q0", q_factor);
593       for (i = 0; i < n; i++)
594         log_mpidump ("factor pi", factors[i]);
595       log_debug ("bit sizes: prime=%u, q=%u",
596                  mpi_get_nbits (prime), mpi_get_nbits (q));
597       if (need_q_factor)
598         log_printf (", q0=%u", mpi_get_nbits (q_factor));
599       for (i = 0; i < n; i++)
600         log_printf (", p%d=%u", i, mpi_get_nbits (factors[i]));
601       log_printf ("\n");
602     }
603
604   if (ret_factors)
605     {
606       /* Caller wants the factors.  */
607       factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
608       if (! factors_new)
609         {
610           err = gpg_err_code_from_errno (errno);
611           goto leave;
612         }
613
614       if (all_factors)
615         {
616           i = 0;
617           factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
618           factors_new[i++] = mpi_copy (q);
619           if (need_q_factor)
620             factors_new[i++] = mpi_copy (q_factor);
621           for(j=0; j < n; j++)
622             factors_new[i++] = mpi_copy (factors[j]);
623         }
624       else
625         {
626           i = 0;
627           if (need_q_factor)
628             {
629               factors_new[i++] = mpi_copy (q_factor);
630               for (; i <= n; i++)
631                 factors_new[i] = mpi_copy (factors[i]);
632             }
633           else
634             for (; i < n; i++ )
635               factors_new[i] = mpi_copy (factors[i]);
636         }
637     }
638
639   if (g)
640     {
641       /* Create a generator (start with 3).  */
642       gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
643       gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
644       gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
645
646       if (need_q_factor)
647         err = GPG_ERR_NOT_IMPLEMENTED;
648       else
649         {
650           factors[n] = q;
651           factors[n + 1] = mpi_alloc_set_ui (2);
652           mpi_sub_ui (pmin1, prime, 1);
653           mpi_set_ui (g, 2);
654           do
655             {
656               mpi_add_ui (g, g, 1);
657               if (DBG_CIPHER)
658                 log_printmpi ("checking g", g);
659               else
660                 progress('^');
661               for (i = 0; i < n + 2; i++)
662                 {
663                   mpi_fdiv_q (tmp, pmin1, factors[i]);
664                   /* No mpi_pow(), but it is okay to use this with mod
665                      prime.  */
666                   gcry_mpi_powm (b, g, tmp, prime);
667                   if (! mpi_cmp_ui (b, 1))
668                     break;
669                 }
670               if (DBG_CIPHER)
671                 progress('\n');
672             }
673           while (i < n + 2);
674
675           mpi_free (factors[n+1]);
676           mpi_free (tmp);
677           mpi_free (b);
678           mpi_free (pmin1);
679         }
680     }
681
682   if (! DBG_CIPHER)
683     progress ('\n');
684
685
686  leave:
687   if (pool)
688     {
689       is_locked = !ath_mutex_lock (&primepool_lock);
690       for(i = 0; i < m; i++)
691         {
692           if (pool[i])
693             {
694               for (j=0; j < n; j++)
695                 if (pool_in_use[j] == i)
696                   break;
697               if (j == n && is_locked)
698                 {
699                   /* This pooled subprime has not been used. */
700                   save_pool_prime (pool[i], poolrandomlevel);
701                 }
702               else
703                 mpi_free (pool[i]);
704             }
705         }
706       if (is_locked && ath_mutex_unlock (&primepool_lock))
707         err = GPG_ERR_INTERNAL;
708       is_locked = 0;
709       gcry_free (pool);
710     }
711   gcry_free (pool_in_use);
712   if (factors)
713     gcry_free (factors);  /* Factors are shallow copies.  */
714   if (perms)
715     gcry_free (perms);
716
717   mpi_free (val_2);
718   mpi_free (q);
719   mpi_free (q_factor);
720
721   if (! err)
722     {
723       *prime_generated = prime;
724       if (ret_factors)
725         *ret_factors = factors_new;
726     }
727   else
728     {
729       if (factors_new)
730         {
731           for (i = 0; factors_new[i]; i++)
732             mpi_free (factors_new[i]);
733           gcry_free (factors_new);
734         }
735       mpi_free (prime);
736     }
737
738   return err;
739 }
740
741
742 /* Generate a prime used for discrete logarithm algorithms; i.e. this
743    prime will be public and no strong random is required.  */
744 gcry_mpi_t
745 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
746                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
747 {
748   gcry_mpi_t prime = NULL;
749
750   if (prime_generate_internal ((mode == 1), &prime, pbits, qbits, g,
751                                ret_factors, GCRY_WEAK_RANDOM, 0, 0,
752                                NULL, NULL))
753     prime = NULL; /* (Should be NULL in the error case anyway.)  */
754
755   return prime;
756 }
757
758
759 static gcry_mpi_t
760 gen_prime (unsigned int nbits, int secret, int randomlevel,
761            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
762 {
763   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
764   int i;
765   unsigned int x, step;
766   unsigned int count1, count2;
767   int *mods;
768
769 /*   if (  DBG_CIPHER ) */
770 /*     log_debug ("generate a prime of %u bits ", nbits ); */
771
772   if (nbits < 16)
773     log_fatal ("can't generate a prime with less than %d bits\n", 16);
774
775   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
776   /* Make nbits fit into gcry_mpi_t implementation. */
777   val_2  = mpi_alloc_set_ui( 2 );
778   val_3 = mpi_alloc_set_ui( 3);
779   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
780   result = mpi_alloc_like( prime );
781   pminus1= mpi_alloc_like( prime );
782   ptest  = mpi_alloc_like( prime );
783   count1 = count2 = 0;
784   for (;;)
785     {  /* try forvever */
786       int dotcount=0;
787
788       /* generate a random number */
789       gcry_mpi_randomize( prime, nbits, randomlevel );
790
791       /* Set high order bit to 1, set low order bit to 1.  If we are
792          generating a secret prime we are most probably doing that
793          for RSA, to make sure that the modulus does have the
794          requested key size we set the 2 high order bits. */
795       mpi_set_highbit (prime, nbits-1);
796       if (secret)
797         mpi_set_bit (prime, nbits-2);
798       mpi_set_bit(prime, 0);
799
800       /* Calculate all remainders. */
801       for (i=0; (x = small_prime_numbers[i]); i++ )
802         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
803
804       /* Now try some primes starting with prime. */
805       for(step=0; step < 20000; step += 2 )
806         {
807           /* Check against all the small primes we have in mods. */
808           count1++;
809           for (i=0; (x = small_prime_numbers[i]); i++ )
810             {
811               while ( mods[i] + step >= x )
812                 mods[i] -= x;
813               if ( !(mods[i] + step) )
814                 break;
815             }
816           if ( x )
817             continue;   /* Found a multiple of an already known prime. */
818
819           mpi_add_ui( ptest, prime, step );
820
821           /* Do a fast Fermat test now. */
822           count2++;
823           mpi_sub_ui( pminus1, ptest, 1);
824           gcry_mpi_powm( result, val_2, pminus1, ptest );
825           if ( !mpi_cmp_ui( result, 1 ) )
826             {
827               /* Not composite, perform stronger tests */
828               if (is_prime(ptest, 5, &count2 ))
829                 {
830                   if (!mpi_test_bit( ptest, nbits-1-secret ))
831                     {
832                       progress('\n');
833                       log_debug ("overflow in prime generation\n");
834                       break; /* Stop loop, continue with a new prime. */
835                     }
836
837                   if (extra_check && extra_check (extra_check_arg, ptest))
838                     {
839                       /* The extra check told us that this prime is
840                          not of the caller's taste. */
841                       progress ('/');
842                     }
843                   else
844                     {
845                       /* Got it. */
846                       mpi_free(val_2);
847                       mpi_free(val_3);
848                       mpi_free(result);
849                       mpi_free(pminus1);
850                       mpi_free(prime);
851                       gcry_free(mods);
852                       return ptest;
853                     }
854                 }
855             }
856           if (++dotcount == 10 )
857             {
858               progress('.');
859               dotcount = 0;
860             }
861         }
862       progress(':'); /* restart with a new random value */
863     }
864 }
865
866 /****************
867  * Returns: true if this may be a prime
868  * RM_ROUNDS gives the number of Rabin-Miller tests to run.
869  */
870 static int
871 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
872              gcry_prime_check_func_t cb_func, void *cb_arg)
873 {
874   int i;
875   unsigned int x;
876   unsigned int count=0;
877
878   /* Check against small primes. */
879   for (i=0; (x = small_prime_numbers[i]); i++ )
880     {
881       if ( mpi_divisible_ui( prime, x ) )
882         return 0;
883     }
884
885   /* A quick Fermat test. */
886   {
887     gcry_mpi_t result = mpi_alloc_like( prime );
888     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
889     mpi_sub_ui( pminus1, prime, 1);
890     gcry_mpi_powm( result, val_2, pminus1, prime );
891     mpi_free( pminus1 );
892     if ( mpi_cmp_ui( result, 1 ) )
893       {
894         /* Is composite. */
895         mpi_free( result );
896         progress('.');
897         return 0;
898       }
899     mpi_free( result );
900   }
901
902   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
903     {
904       /* Perform stronger tests. */
905       if ( is_prime( prime, rm_rounds, &count ) )
906         {
907           if (!cb_func
908               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
909             return 1; /* Probably a prime. */
910         }
911     }
912   progress('.');
913   return 0;
914 }
915
916
917 /*
918  * Return true if n is probably a prime
919  */
920 static int
921 is_prime (gcry_mpi_t n, int steps, unsigned int *count)
922 {
923   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
924   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
925   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
926   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
927   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
928   gcry_mpi_t q;
929   unsigned i, j, k;
930   int rc = 0;
931   unsigned nbits = mpi_get_nbits( n );
932
933   if (steps < 5) /* Make sure that we do at least 5 rounds. */
934     steps = 5;
935
936   mpi_sub_ui( nminus1, n, 1 );
937
938   /* Find q and k, so that n = 1 + 2^k * q . */
939   q = mpi_copy ( nminus1 );
940   k = mpi_trailing_zeros ( q );
941   mpi_tdiv_q_2exp (q, q, k);
942
943   for (i=0 ; i < steps; i++ )
944     {
945       ++*count;
946       if( !i )
947         {
948           mpi_set_ui( x, 2 );
949         }
950       else
951         {
952           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
953
954           /* Make sure that the number is smaller than the prime and
955              keep the randomness of the high bit. */
956           if ( mpi_test_bit ( x, nbits-2) )
957             {
958               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
959             }
960           else
961             {
962               mpi_set_highbit( x, nbits-2 );
963               mpi_clear_bit( x, nbits-2 );
964             }
965           gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
966         }
967       gcry_mpi_powm ( y, x, q, n);
968       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
969         {
970           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
971             {
972               gcry_mpi_powm(y, y, a2, n);
973               if( !mpi_cmp_ui( y, 1 ) )
974                 goto leave; /* Not a prime. */
975             }
976           if (mpi_cmp( y, nminus1 ) )
977             goto leave; /* Not a prime. */
978         }
979       progress('+');
980     }
981   rc = 1; /* May be a prime. */
982
983  leave:
984   mpi_free( x );
985   mpi_free( y );
986   mpi_free( z );
987   mpi_free( nminus1 );
988   mpi_free( q );
989   mpi_free( a2 );
990
991   return rc;
992 }
993
994
995 /* Given ARRAY of size N with M elements set to true produce a
996    modified array with the next permutation of M elements.  Note, that
997    ARRAY is used in a one-bit-per-byte approach.  To detected the last
998    permutation it is useful to initialize the array with the first M
999    element set to true and use this test:
1000        m_out_of_n (array, m, n);
1001        for (i = j = 0; i < n && j < m; i++)
1002          if (array[i])
1003            j++;
1004        if (j == m)
1005          goto ready;
1006
1007    This code is based on the algorithm 452 from the "Collected
1008    Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
1009 */
1010 static void
1011 m_out_of_n ( char *array, int m, int n )
1012 {
1013   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
1014
1015   if( !m || m >= n )
1016     return;
1017
1018   /* Need to handle this simple case separately. */
1019   if( m == 1 )
1020     {
1021       for (i=0; i < n; i++ )
1022         {
1023           if ( array[i] )
1024             {
1025               array[i++] = 0;
1026               if( i >= n )
1027                 i = 0;
1028               array[i] = 1;
1029               return;
1030             }
1031         }
1032       BUG();
1033     }
1034
1035
1036   for (j=1; j < n; j++ )
1037     {
1038       if ( array[n-1] == array[n-j-1])
1039         continue;
1040       j1 = j;
1041       break;
1042     }
1043
1044   if ( (m & 1) )
1045     {
1046       /* M is odd. */
1047       if( array[n-1] )
1048         {
1049           if( j1 & 1 )
1050             {
1051               k1 = n - j1;
1052               k2 = k1+2;
1053               if( k2 > n )
1054                 k2 = n;
1055               goto leave;
1056             }
1057           goto scan;
1058         }
1059       k2 = n - j1 - 1;
1060       if( k2 == 0 )
1061         {
1062           k1 = i;
1063           k2 = n - j1;
1064         }
1065       else if( array[k2] && array[k2-1] )
1066         k1 = n;
1067       else
1068         k1 = k2 + 1;
1069     }
1070   else
1071     {
1072       /* M is even. */
1073       if( !array[n-1] )
1074         {
1075           k1 = n - j1;
1076           k2 = k1 + 1;
1077           goto leave;
1078         }
1079
1080       if( !(j1 & 1) )
1081         {
1082           k1 = n - j1;
1083           k2 = k1+2;
1084           if( k2 > n )
1085             k2 = n;
1086           goto leave;
1087         }
1088     scan:
1089       jp = n - j1 - 1;
1090       for (i=1; i <= jp; i++ )
1091         {
1092           i1 = jp + 2 - i;
1093           if( array[i1-1]  )
1094             {
1095               if( array[i1-2] )
1096                 {
1097                   k1 = i1 - 1;
1098                   k2 = n - j1;
1099                 }
1100               else
1101                 {
1102                   k1 = i1 - 1;
1103                   k2 = n + 1 - j1;
1104                 }
1105               goto leave;
1106             }
1107         }
1108       k1 = 1;
1109       k2 = n + 1 - m;
1110     }
1111  leave:
1112   /* Now complement the two selected bits. */
1113   array[k1-1] = !array[k1-1];
1114   array[k2-1] = !array[k2-1];
1115 }
1116
1117
1118 /* Generate a new prime number of PRIME_BITS bits and store it in
1119    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
1120    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
1121    non-zero, allocate a new, NULL-terminated array holding the prime
1122    factors and store it in FACTORS.  FLAGS might be used to influence
1123    the prime number generation process.  */
1124 gcry_error_t
1125 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1126                      unsigned int factor_bits, gcry_mpi_t **factors,
1127                      gcry_prime_check_func_t cb_func, void *cb_arg,
1128                      gcry_random_level_t random_level,
1129                      unsigned int flags)
1130 {
1131   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1132   gcry_mpi_t *factors_generated = NULL;
1133   gcry_mpi_t prime_generated = NULL;
1134   unsigned int mode = 0;
1135
1136   if (!prime)
1137     return gpg_error (GPG_ERR_INV_ARG);
1138   *prime = NULL;
1139
1140   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1141     mode = 1;
1142
1143   /* Generate.  */
1144   err = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1145                                  factor_bits, NULL,
1146                                  factors? &factors_generated : NULL,
1147                                  random_level, flags, 1,
1148                                  cb_func, cb_arg);
1149
1150   if (! err)
1151     if (cb_func)
1152       {
1153         /* Additional check. */
1154         if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1155           {
1156             /* Failed, deallocate resources.  */
1157             unsigned int i;
1158
1159             mpi_free (prime_generated);
1160             if (factors)
1161               {
1162                 for (i = 0; factors_generated[i]; i++)
1163                   mpi_free (factors_generated[i]);
1164                 gcry_free (factors_generated);
1165               }
1166             err = GPG_ERR_GENERAL;
1167           }
1168       }
1169
1170   if (! err)
1171     {
1172       if (factors)
1173         *factors = factors_generated;
1174       *prime = prime_generated;
1175     }
1176
1177   return gcry_error (err);
1178 }
1179
1180 /* Check whether the number X is prime.  */
1181 gcry_error_t
1182 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1183 {
1184   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1185   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
1186
1187   (void)flags;
1188
1189   /* We use 64 rounds because the prime we are going to test is not
1190      guaranteed to be a random one. */
1191   if (! check_prime (x, val_2, 64, NULL, NULL))
1192     err = GPG_ERR_NO_PRIME;
1193
1194   mpi_free (val_2);
1195
1196   return gcry_error (err);
1197 }
1198
1199 /* Find a generator for PRIME where the factorization of (prime-1) is
1200    in the NULL terminated array FACTORS. Return the generator as a
1201    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1202    atart for the search. Returns 0 on success.*/
1203 gcry_error_t
1204 gcry_prime_group_generator (gcry_mpi_t *r_g,
1205                             gcry_mpi_t prime, gcry_mpi_t *factors,
1206                             gcry_mpi_t start_g)
1207 {
1208   gcry_mpi_t tmp = gcry_mpi_new (0);
1209   gcry_mpi_t b = gcry_mpi_new (0);
1210   gcry_mpi_t pmin1 = gcry_mpi_new (0);
1211   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
1212   int first = 1;
1213   int i, n;
1214
1215   if (!factors || !r_g || !prime)
1216     return gpg_error (GPG_ERR_INV_ARG);
1217   *r_g = NULL;
1218
1219   for (n=0; factors[n]; n++)
1220     ;
1221   if (n < 2)
1222     return gpg_error (GPG_ERR_INV_ARG);
1223
1224   /* Extra sanity check - usually disabled. */
1225 /*   mpi_set (tmp, factors[0]); */
1226 /*   for(i = 1; i < n; i++) */
1227 /*     mpi_mul (tmp, tmp, factors[i]); */
1228 /*   mpi_add_ui (tmp, tmp, 1); */
1229 /*   if (mpi_cmp (prime, tmp)) */
1230 /*     return gpg_error (GPG_ERR_INV_ARG); */
1231
1232   gcry_mpi_sub_ui (pmin1, prime, 1);
1233   do
1234     {
1235       if (first)
1236         first = 0;
1237       else
1238         gcry_mpi_add_ui (g, g, 1);
1239
1240       if (DBG_CIPHER)
1241         log_printmpi ("checking g", g);
1242       else
1243         progress('^');
1244
1245       for (i = 0; i < n; i++)
1246         {
1247           mpi_fdiv_q (tmp, pmin1, factors[i]);
1248           gcry_mpi_powm (b, g, tmp, prime);
1249           if (! mpi_cmp_ui (b, 1))
1250             break;
1251         }
1252       if (DBG_CIPHER)
1253         progress('\n');
1254     }
1255   while (i < n);
1256
1257   gcry_mpi_release (tmp);
1258   gcry_mpi_release (b);
1259   gcry_mpi_release (pmin1);
1260   *r_g = g;
1261
1262   return 0;
1263 }
1264
1265 /* Convenience function to release the factors array. */
1266 void
1267 gcry_prime_release_factors (gcry_mpi_t *factors)
1268 {
1269   if (factors)
1270     {
1271       int i;
1272
1273       for (i=0; factors[i]; i++)
1274         mpi_free (factors[i]);
1275       gcry_free (factors);
1276     }
1277 }
1278
1279
1280 \f
1281 /* Helper for _gcry_derive_x931_prime.  */
1282 static gcry_mpi_t
1283 find_x931_prime (const gcry_mpi_t pfirst)
1284 {
1285   gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1286   gcry_mpi_t prime;
1287
1288   prime = gcry_mpi_copy (pfirst);
1289   /* If P is even add 1.  */
1290   mpi_set_bit (prime, 0);
1291
1292   /* We use 64 Rabin-Miller rounds which is better and thus
1293      sufficient.  We do not have a Lucas test implementaion thus we
1294      can't do it in the X9.31 preferred way of running a few
1295      Rabin-Miller followed by one Lucas test.  */
1296   while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1297     mpi_add_ui (prime, prime, 2);
1298
1299   mpi_free (val_2);
1300
1301   return prime;
1302 }
1303
1304
1305 /* Generate a prime using the algorithm from X9.31 appendix B.4.
1306
1307    This function requires that the provided public exponent E is odd.
1308    XP, XP1 and XP2 are the seed values.  All values are mandatory.
1309
1310    On success the prime is returned.  If R_P1 or R_P2 are given the
1311    internal values P1 and P2 are saved at these addresses.  On error
1312    NULL is returned.  */
1313 gcry_mpi_t
1314 _gcry_derive_x931_prime (const gcry_mpi_t xp,
1315                          const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1316                          const gcry_mpi_t e,
1317                          gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1318 {
1319   gcry_mpi_t p1, p2, p1p2, yp0;
1320
1321   if (!xp || !xp1 || !xp2)
1322     return NULL;
1323   if (!e || !mpi_test_bit (e, 0))
1324     return NULL;  /* We support only odd values for E.  */
1325
1326   p1 = find_x931_prime (xp1);
1327   p2 = find_x931_prime (xp2);
1328   p1p2 = mpi_alloc_like (xp);
1329   mpi_mul (p1p2, p1, p2);
1330
1331   {
1332     gcry_mpi_t r1, tmp;
1333
1334     /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1335     tmp = mpi_alloc_like (p1);
1336     mpi_invm (tmp, p2, p1);
1337     mpi_mul (tmp, tmp, p2);
1338     r1 = tmp;
1339
1340     tmp = mpi_alloc_like (p2);
1341     mpi_invm (tmp, p1, p2);
1342     mpi_mul (tmp, tmp, p1);
1343     mpi_sub (r1, r1, tmp);
1344
1345     /* Fixup a negative value.  */
1346     if (mpi_has_sign (r1))
1347       mpi_add (r1, r1, p1p2);
1348
1349     /* yp0 = xp + (r1 - xp mod p1*p2)  */
1350     yp0 = tmp; tmp = NULL;
1351     mpi_subm (yp0, r1, xp, p1p2);
1352     mpi_add (yp0, yp0, xp);
1353     mpi_free (r1);
1354
1355     /* Fixup a negative value.  */
1356     if (mpi_cmp (yp0, xp) < 0 )
1357       mpi_add (yp0, yp0, p1p2);
1358   }
1359
1360   /* yp0 is now the first integer greater than xp with p1 being a
1361      large prime factor of yp0-1 and p2 a large prime factor of yp0+1.  */
1362
1363   /* Note that the first example from X9.31 (D.1.1) which uses
1364        (Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1365        (Xq2 #134E4CAA16D2350A21D775C404#)
1366        (Xq  #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1367              7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1368              6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1369              321DE34A#))))
1370      returns an yp0 of
1371             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1372              7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1373              BF20CB896EE37E098A906313271422162CB6C642
1374              75C1201F#
1375      and not
1376             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1377              7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1378              C88FE299D52D78BE405A97E01FD71DD7819ECB91
1379              FA85A076#
1380      as stated in the standard.  This seems to be a bug in X9.31.
1381    */
1382
1383   {
1384     gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1385     gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1386     int gcdres;
1387
1388     mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body.  */
1389     mpi_sub_ui (yp0, yp0, 1);   /* Ditto.  */
1390     for (;;)
1391       {
1392         gcdres = gcry_mpi_gcd (gcdtmp, e, yp0);
1393         mpi_add_ui (yp0, yp0, 1);
1394         if (!gcdres)
1395           progress ('/');  /* gcd (e, yp0-1) != 1  */
1396         else if (check_prime (yp0, val_2, 64, NULL, NULL))
1397           break; /* Found.  */
1398         /* We add p1p2-1 because yp0 is incremented after the gcd test.  */
1399         mpi_add (yp0, yp0, p1p2);
1400       }
1401     mpi_free (gcdtmp);
1402     mpi_free (val_2);
1403   }
1404
1405   mpi_free (p1p2);
1406
1407   progress('\n');
1408   if (r_p1)
1409     *r_p1 = p1;
1410   else
1411     mpi_free (p1);
1412   if (r_p2)
1413     *r_p2 = p2;
1414   else
1415     mpi_free (p2);
1416   return yp0;
1417 }
1418
1419
1420 \f
1421 /* Generate the two prime used for DSA using the algorithm specified
1422    in FIPS 186-2.  PBITS is the desired length of the prime P and a
1423    QBITS the length of the prime Q.  If SEED is not supplied and
1424    SEEDLEN is 0 the function generates an appropriate SEED.  On
1425    success the generated primes are stored at R_Q and R_P, the counter
1426    value is stored at R_COUNTER and the seed actually used for
1427    generation is stored at R_SEED and R_SEEDVALUE.  */
1428 gpg_err_code_t
1429 _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1430                                 const void *seed, size_t seedlen,
1431                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1432                                 int *r_counter,
1433                                 void **r_seed, size_t *r_seedlen)
1434 {
1435   gpg_err_code_t ec;
1436   unsigned char seed_help_buffer[160/8];  /* Used to hold a generated SEED. */
1437   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1438   unsigned char digest[160/8];  /* Helper buffer for SHA-1 digest.  */
1439   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1440   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1441   int i;
1442
1443   unsigned char value_u[160/8];
1444   int value_n, value_b, value_k;
1445   int counter;
1446   gcry_mpi_t value_w = NULL;
1447   gcry_mpi_t value_x = NULL;
1448   gcry_mpi_t prime_q = NULL;
1449   gcry_mpi_t prime_p = NULL;
1450
1451   /* FIPS 186-2 allows only for 1024/160 bit.  */
1452   if (pbits != 1024 || qbits != 160)
1453     return GPG_ERR_INV_KEYLEN;
1454
1455   if (!seed && !seedlen)
1456     ; /* No seed value given:  We are asked to generate it.  */
1457   else if (!seed || seedlen < qbits/8)
1458     return GPG_ERR_INV_ARG;
1459
1460   /* Allocate a buffer to later compute SEED+some_increment. */
1461   seed_plus = gcry_malloc (seedlen < 20? 20:seedlen);
1462   if (!seed_plus)
1463     {
1464       ec = gpg_err_code_from_syserror ();
1465       goto leave;
1466     }
1467
1468   val_2   = mpi_alloc_set_ui (2);
1469   value_n = (pbits - 1) / qbits;
1470   value_b = (pbits - 1) - value_n * qbits;
1471   value_w = gcry_mpi_new (pbits);
1472   value_x = gcry_mpi_new (pbits);
1473
1474  restart:
1475   /* Generate Q.  */
1476   for (;;)
1477     {
1478       /* Step 1: Generate a (new) seed unless one has been supplied.  */
1479       if (!seed)
1480         {
1481           seedlen = sizeof seed_help_buffer;
1482           gcry_create_nonce (seed_help_buffer, seedlen);
1483           seed = seed_help_buffer;
1484         }
1485
1486       /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits})  */
1487       memcpy (seed_plus, seed, seedlen);
1488       for (i=seedlen-1; i >= 0; i--)
1489         {
1490           seed_plus[i]++;
1491           if (seed_plus[i])
1492             break;
1493         }
1494       gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1495       gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1496       for (i=0; i < sizeof value_u; i++)
1497         value_u[i] ^= digest[i];
1498
1499       /* Step 3:  Form q from U  */
1500       gcry_mpi_release (prime_q); prime_q = NULL;
1501       ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1502                                         value_u, sizeof value_u, NULL));
1503       if (ec)
1504         goto leave;
1505       mpi_set_highbit (prime_q, qbits-1 );
1506       mpi_set_bit (prime_q, 0);
1507
1508       /* Step 4:  Test whether Q is prime using 64 round of Rabin-Miller.  */
1509       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1510         break; /* Yes, Q is prime.  */
1511
1512       /* Step 5.  */
1513       seed = NULL;  /* Force a new seed at Step 1.  */
1514     }
1515
1516   /* Step 6.  Note that we do no use an explicit offset but increment
1517      SEED_PLUS accordingly.  SEED_PLUS is currently SEED+1.  */
1518   counter = 0;
1519
1520   /* Generate P. */
1521   prime_p = gcry_mpi_new (pbits);
1522   for (;;)
1523     {
1524       /* Step 7: For k = 0,...n let
1525                    V_k = sha1(seed+offset+k) mod 2^{qbits}
1526          Step 8: W = V_0 + V_1*2^160 +
1527                          ...
1528                          + V_{n-1}*2^{(n-1)*160}
1529                          + (V_{n} mod 2^b)*2^{n*160}
1530        */
1531       mpi_set_ui (value_w, 0);
1532       for (value_k=0; value_k <= value_n; value_k++)
1533         {
1534           /* There is no need to have an explicit offset variable:  In
1535              the first round we shall have an offset of 2, this is
1536              achieved by using SEED_PLUS which is already at SEED+1,
1537              thus we just need to increment it once again.  The
1538              requirement for the next round is to update offset by N,
1539              which we implictly did at the end of this loop, and then
1540              to add one; this one is the same as in the first round.  */
1541           for (i=seedlen-1; i >= 0; i--)
1542             {
1543               seed_plus[i]++;
1544               if (seed_plus[i])
1545                 break;
1546             }
1547           gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1548
1549           gcry_mpi_release (tmpval); tmpval = NULL;
1550           ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1551                                             digest, sizeof digest, NULL));
1552           if (ec)
1553             goto leave;
1554           if (value_k == value_n)
1555             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1556           mpi_lshift (tmpval, tmpval, value_k*qbits);
1557           mpi_add (value_w, value_w, tmpval);
1558         }
1559
1560       /* Step 8 continued: X = W + 2^{L-1}  */
1561       mpi_set_ui (value_x, 0);
1562       mpi_set_highbit (value_x, pbits-1);
1563       mpi_add (value_x, value_x, value_w);
1564
1565       /* Step 9:  c = X mod 2q,  p = X - (c - 1)  */
1566       mpi_mul_2exp (tmpval, prime_q, 1);
1567       mpi_mod (tmpval, value_x, tmpval);
1568       mpi_sub_ui (tmpval, tmpval, 1);
1569       mpi_sub (prime_p, value_x, tmpval);
1570
1571       /* Step 10: If  p < 2^{L-1}  skip the primality test.  */
1572       /* Step 11 and 12: Primality test.  */
1573       if (mpi_get_nbits (prime_p) >= pbits-1
1574           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1575         break; /* Yes, P is prime, continue with Step 15.  */
1576
1577       /* Step 13: counter = counter + 1, offset = offset + n + 1. */
1578       counter++;
1579
1580       /* Step 14: If counter >= 2^12  goto Step 1.  */
1581       if (counter >= 4096)
1582         goto restart;
1583     }
1584
1585   /* Step 15:  Save p, q, counter and seed.  */
1586 /*   log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1587 /*              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1588 /*   log_printhex("fips186-2 seed:", seed, seedlen); */
1589 /*   log_mpidump ("fips186-2 prime p", prime_p); */
1590 /*   log_mpidump ("fips186-2 prime q", prime_q); */
1591   if (r_q)
1592     {
1593       *r_q = prime_q;
1594       prime_q = NULL;
1595     }
1596   if (r_p)
1597     {
1598       *r_p = prime_p;
1599       prime_p = NULL;
1600     }
1601   if (r_counter)
1602     *r_counter = counter;
1603   if (r_seed && r_seedlen)
1604     {
1605       memcpy (seed_plus, seed, seedlen);
1606       *r_seed = seed_plus;
1607       seed_plus = NULL;
1608       *r_seedlen = seedlen;
1609     }
1610
1611
1612  leave:
1613   gcry_mpi_release (tmpval);
1614   gcry_mpi_release (value_x);
1615   gcry_mpi_release (value_w);
1616   gcry_mpi_release (prime_p);
1617   gcry_mpi_release (prime_q);
1618   gcry_free (seed_plus);
1619   gcry_mpi_release (val_2);
1620   return ec;
1621 }
1622
1623
1624 \f
1625 /* WARNING: The code below has not yet been tested!  However, it is
1626    not yet used.  We need to wait for FIPS 186-3 final and for test
1627    vectors.
1628
1629    Generate the two prime used for DSA using the algorithm specified
1630    in FIPS 186-3, A.1.1.2.  PBITS is the desired length of the prime P
1631    and a QBITS the length of the prime Q.  If SEED is not supplied and
1632    SEEDLEN is 0 the function generates an appropriate SEED.  On
1633    success the generated primes are stored at R_Q and R_P, the counter
1634    value is stored at R_COUNTER and the seed actually used for
1635    generation is stored at R_SEED and R_SEEDVALUE.  The hash algorithm
1636    used is stored at R_HASHALGO.
1637
1638    Note that this function is very similar to the fips186_2 code.  Due
1639    to the minor differences, other buffer sizes and for documentarion,
1640    we use a separate function.
1641 */
1642 gpg_err_code_t
1643 _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1644                                 const void *seed, size_t seedlen,
1645                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1646                                 int *r_counter,
1647                                 void **r_seed, size_t *r_seedlen,
1648                                 int *r_hashalgo)
1649 {
1650   gpg_err_code_t ec;
1651   unsigned char seed_help_buffer[256/8];  /* Used to hold a generated SEED. */
1652   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1653   unsigned char digest[256/8];  /* Helper buffer for SHA-1 digest.  */
1654   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1655   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1656   int hashalgo;                 /* The id of the Approved Hash Function.  */
1657   int i;
1658
1659   unsigned char value_u[256/8];
1660   int value_n, value_b, value_j;
1661   int counter;
1662   gcry_mpi_t value_w = NULL;
1663   gcry_mpi_t value_x = NULL;
1664   gcry_mpi_t prime_q = NULL;
1665   gcry_mpi_t prime_p = NULL;
1666
1667   gcry_assert (sizeof seed_help_buffer == sizeof digest
1668                && sizeof seed_help_buffer == sizeof value_u);
1669
1670   /* Step 1:  Check the requested prime lengths.  */
1671   /* Note that due to the size of our buffers QBITS is limited to 256.  */
1672   if (pbits == 1024 && qbits == 160)
1673     hashalgo = GCRY_MD_SHA1;
1674   else if (pbits == 2048 && qbits == 224)
1675     hashalgo = GCRY_MD_SHA224;
1676   else if (pbits == 2048 && qbits == 256)
1677     hashalgo = GCRY_MD_SHA256;
1678   else if (pbits == 3072 && qbits == 256)
1679     hashalgo = GCRY_MD_SHA256;
1680   else
1681     return GPG_ERR_INV_KEYLEN;
1682
1683   /* Also check that the hash algorithm is available.  */
1684   ec = gpg_err_code (gcry_md_test_algo (hashalgo));
1685   if (ec)
1686     return ec;
1687   gcry_assert (qbits/8 <= sizeof digest);
1688   gcry_assert (gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1689
1690
1691   /* Step 2:  Check seedlen.  */
1692   if (!seed && !seedlen)
1693     ; /* No seed value given:  We are asked to generate it.  */
1694   else if (!seed || seedlen < qbits/8)
1695     return GPG_ERR_INV_ARG;
1696
1697   /* Allocate a buffer to later compute SEED+some_increment and a few
1698      helper variables.  */
1699   seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer?
1700                            sizeof seed_help_buffer : seedlen);
1701   if (!seed_plus)
1702     {
1703       ec = gpg_err_code_from_syserror ();
1704       goto leave;
1705     }
1706   val_2   = mpi_alloc_set_ui (2);
1707   value_w = gcry_mpi_new (pbits);
1708   value_x = gcry_mpi_new (pbits);
1709
1710   /* Step 3: n = \lceil L / outlen \rceil - 1  */
1711   value_n = (pbits + qbits - 1) / qbits - 1;
1712   /* Step 4: b = L - 1 - (n * outlen)  */
1713   value_b = pbits - 1 - (value_n * qbits);
1714
1715  restart:
1716   /* Generate Q.  */
1717   for (;;)
1718     {
1719       /* Step 5:  Generate a (new) seed unless one has been supplied.  */
1720       if (!seed)
1721         {
1722           seedlen = qbits/8;
1723           gcry_assert (seedlen <= sizeof seed_help_buffer);
1724           gcry_create_nonce (seed_help_buffer, seedlen);
1725           seed = seed_help_buffer;
1726         }
1727
1728       /* Step 6:  U = hash(seed)  */
1729       gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1730
1731       /* Step 7:  q = 2^{N-1} + U + 1 - (U mod 2)  */
1732       if ( !(value_u[qbits/8-1] & 0x01) )
1733         {
1734           for (i=qbits/8-1; i >= 0; i--)
1735             {
1736               value_u[i]++;
1737               if (value_u[i])
1738                 break;
1739             }
1740         }
1741       gcry_mpi_release (prime_q); prime_q = NULL;
1742       ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1743                                         value_u, sizeof value_u, NULL));
1744       if (ec)
1745         goto leave;
1746       mpi_set_highbit (prime_q, qbits-1 );
1747
1748       /* Step 8:  Test whether Q is prime using 64 round of Rabin-Miller.
1749                   According to table C.1 this is sufficient for all
1750                   supported prime sizes (i.e. up 3072/256).  */
1751       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1752         break; /* Yes, Q is prime.  */
1753
1754       /* Step 8.  */
1755       seed = NULL;  /* Force a new seed at Step 5.  */
1756     }
1757
1758   /* Step 11.  Note that we do no use an explicit offset but increment
1759      SEED_PLUS accordingly.  */
1760   memcpy (seed_plus, seed, seedlen);
1761   counter = 0;
1762
1763   /* Generate P. */
1764   prime_p = gcry_mpi_new (pbits);
1765   for (;;)
1766     {
1767       /* Step 11.1: For j = 0,...n let
1768                       V_j = hash(seed+offset+j)
1769          Step 11.2: W = V_0 + V_1*2^outlen +
1770                             ...
1771                             + V_{n-1}*2^{(n-1)*outlen}
1772                             + (V_{n} mod 2^b)*2^{n*outlen}
1773        */
1774       mpi_set_ui (value_w, 0);
1775       for (value_j=0; value_j <= value_n; value_j++)
1776         {
1777           /* There is no need to have an explicit offset variable: In
1778              the first round we shall have an offset of 1 and a j of
1779              0.  This is achieved by incrementing SEED_PLUS here.  For
1780              the next round offset is implicitly updated by using
1781              SEED_PLUS again.  */
1782           for (i=seedlen-1; i >= 0; i--)
1783             {
1784               seed_plus[i]++;
1785               if (seed_plus[i])
1786                 break;
1787             }
1788           gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1789
1790           gcry_mpi_release (tmpval); tmpval = NULL;
1791           ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1792                                             digest, sizeof digest, NULL));
1793           if (ec)
1794             goto leave;
1795           if (value_j == value_n)
1796             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1797           mpi_lshift (tmpval, tmpval, value_j*qbits);
1798           mpi_add (value_w, value_w, tmpval);
1799         }
1800
1801       /* Step 11.3: X = W + 2^{L-1}  */
1802       mpi_set_ui (value_x, 0);
1803       mpi_set_highbit (value_x, pbits-1);
1804       mpi_add (value_x, value_x, value_w);
1805
1806       /* Step 11.4:  c = X mod 2q  */
1807       mpi_mul_2exp (tmpval, prime_q, 1);
1808       mpi_mod (tmpval, value_x, tmpval);
1809
1810       /* Step 11.5:  p = X - (c - 1)  */
1811       mpi_sub_ui (tmpval, tmpval, 1);
1812       mpi_sub (prime_p, value_x, tmpval);
1813
1814       /* Step 11.6: If  p < 2^{L-1}  skip the primality test.  */
1815       /* Step 11.7 and 11.8: Primality test.  */
1816       if (mpi_get_nbits (prime_p) >= pbits-1
1817           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1818         break; /* Yes, P is prime, continue with Step 15.  */
1819
1820       /* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1821                     If counter >= 4L  goto Step 5.  */
1822       counter++;
1823       if (counter >= 4*pbits)
1824         goto restart;
1825     }
1826
1827   /* Step 12:  Save p, q, counter and seed.  */
1828   log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n",
1829              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter);
1830   log_printhex ("fips186-3 seed", seed, seedlen);
1831   log_printmpi ("fips186-3    p", prime_p);
1832   log_printmpi ("fips186-3    q", prime_q);
1833   if (r_q)
1834     {
1835       *r_q = prime_q;
1836       prime_q = NULL;
1837     }
1838   if (r_p)
1839     {
1840       *r_p = prime_p;
1841       prime_p = NULL;
1842     }
1843   if (r_counter)
1844     *r_counter = counter;
1845   if (r_seed && r_seedlen)
1846     {
1847       memcpy (seed_plus, seed, seedlen);
1848       *r_seed = seed_plus;
1849       seed_plus = NULL;
1850       *r_seedlen = seedlen;
1851     }
1852   if (r_hashalgo)
1853     *r_hashalgo = hashalgo;
1854
1855  leave:
1856   gcry_mpi_release (tmpval);
1857   gcry_mpi_release (value_x);
1858   gcry_mpi_release (value_w);
1859   gcry_mpi_release (prime_p);
1860   gcry_mpi_release (prime_q);
1861   gcry_free (seed_plus);
1862   gcry_mpi_release (val_2);
1863   return ec;
1864 }