Completed switch to a simpler thread model.
[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_debug (", q0=%u", mpi_get_nbits (q_factor));
599       for (i = 0; i < n; i++)
600         log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
601       progress('\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                 {
659                   log_debug ("checking g:");
660                   gcry_mpi_dump (g);
661                   log_printf ("\n");
662                 }
663               else
664                 progress('^');
665               for (i = 0; i < n + 2; i++)
666                 {
667                   mpi_fdiv_q (tmp, pmin1, factors[i]);
668                   /* No mpi_pow(), but it is okay to use this with mod
669                      prime.  */
670                   gcry_mpi_powm (b, g, tmp, prime);
671                   if (! mpi_cmp_ui (b, 1))
672                     break;
673                 }
674               if (DBG_CIPHER)
675                 progress('\n');
676             }
677           while (i < n + 2);
678
679           mpi_free (factors[n+1]);
680           mpi_free (tmp);
681           mpi_free (b);
682           mpi_free (pmin1);
683         }
684     }
685
686   if (! DBG_CIPHER)
687     progress ('\n');
688
689
690  leave:
691   if (pool)
692     {
693       is_locked = !ath_mutex_lock (&primepool_lock);
694       for(i = 0; i < m; i++)
695         {
696           if (pool[i])
697             {
698               for (j=0; j < n; j++)
699                 if (pool_in_use[j] == i)
700                   break;
701               if (j == n && is_locked)
702                 {
703                   /* This pooled subprime has not been used. */
704                   save_pool_prime (pool[i], poolrandomlevel);
705                 }
706               else
707                 mpi_free (pool[i]);
708             }
709         }
710       if (is_locked && ath_mutex_unlock (&primepool_lock))
711         err = GPG_ERR_INTERNAL;
712       is_locked = 0;
713       gcry_free (pool);
714     }
715   gcry_free (pool_in_use);
716   if (factors)
717     gcry_free (factors);  /* Factors are shallow copies.  */
718   if (perms)
719     gcry_free (perms);
720
721   mpi_free (val_2);
722   mpi_free (q);
723   mpi_free (q_factor);
724
725   if (! err)
726     {
727       *prime_generated = prime;
728       if (ret_factors)
729         *ret_factors = factors_new;
730     }
731   else
732     {
733       if (factors_new)
734         {
735           for (i = 0; factors_new[i]; i++)
736             mpi_free (factors_new[i]);
737           gcry_free (factors_new);
738         }
739       mpi_free (prime);
740     }
741
742   return err;
743 }
744
745
746 /* Generate a prime used for discrete logarithm algorithms; i.e. this
747    prime will be public and no strong random is required.  */
748 gcry_mpi_t
749 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
750                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
751 {
752   gcry_mpi_t prime = NULL;
753
754   if (prime_generate_internal ((mode == 1), &prime, pbits, qbits, g,
755                                ret_factors, GCRY_WEAK_RANDOM, 0, 0,
756                                NULL, NULL))
757     prime = NULL; /* (Should be NULL in the error case anyway.)  */
758
759   return prime;
760 }
761
762
763 static gcry_mpi_t
764 gen_prime (unsigned int nbits, int secret, int randomlevel,
765            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
766 {
767   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
768   int i;
769   unsigned int x, step;
770   unsigned int count1, count2;
771   int *mods;
772
773 /*   if (  DBG_CIPHER ) */
774 /*     log_debug ("generate a prime of %u bits ", nbits ); */
775
776   if (nbits < 16)
777     log_fatal ("can't generate a prime with less than %d bits\n", 16);
778
779   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
780   /* Make nbits fit into gcry_mpi_t implementation. */
781   val_2  = mpi_alloc_set_ui( 2 );
782   val_3 = mpi_alloc_set_ui( 3);
783   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
784   result = mpi_alloc_like( prime );
785   pminus1= mpi_alloc_like( prime );
786   ptest  = mpi_alloc_like( prime );
787   count1 = count2 = 0;
788   for (;;)
789     {  /* try forvever */
790       int dotcount=0;
791
792       /* generate a random number */
793       gcry_mpi_randomize( prime, nbits, randomlevel );
794
795       /* Set high order bit to 1, set low order bit to 1.  If we are
796          generating a secret prime we are most probably doing that
797          for RSA, to make sure that the modulus does have the
798          requested key size we set the 2 high order bits. */
799       mpi_set_highbit (prime, nbits-1);
800       if (secret)
801         mpi_set_bit (prime, nbits-2);
802       mpi_set_bit(prime, 0);
803
804       /* Calculate all remainders. */
805       for (i=0; (x = small_prime_numbers[i]); i++ )
806         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
807
808       /* Now try some primes starting with prime. */
809       for(step=0; step < 20000; step += 2 )
810         {
811           /* Check against all the small primes we have in mods. */
812           count1++;
813           for (i=0; (x = small_prime_numbers[i]); i++ )
814             {
815               while ( mods[i] + step >= x )
816                 mods[i] -= x;
817               if ( !(mods[i] + step) )
818                 break;
819             }
820           if ( x )
821             continue;   /* Found a multiple of an already known prime. */
822
823           mpi_add_ui( ptest, prime, step );
824
825           /* Do a fast Fermat test now. */
826           count2++;
827           mpi_sub_ui( pminus1, ptest, 1);
828           gcry_mpi_powm( result, val_2, pminus1, ptest );
829           if ( !mpi_cmp_ui( result, 1 ) )
830             {
831               /* Not composite, perform stronger tests */
832               if (is_prime(ptest, 5, &count2 ))
833                 {
834                   if (!mpi_test_bit( ptest, nbits-1-secret ))
835                     {
836                       progress('\n');
837                       log_debug ("overflow in prime generation\n");
838                       break; /* Stop loop, continue with a new prime. */
839                     }
840
841                   if (extra_check && extra_check (extra_check_arg, ptest))
842                     {
843                       /* The extra check told us that this prime is
844                          not of the caller's taste. */
845                       progress ('/');
846                     }
847                   else
848                     {
849                       /* Got it. */
850                       mpi_free(val_2);
851                       mpi_free(val_3);
852                       mpi_free(result);
853                       mpi_free(pminus1);
854                       mpi_free(prime);
855                       gcry_free(mods);
856                       return ptest;
857                     }
858                 }
859             }
860           if (++dotcount == 10 )
861             {
862               progress('.');
863               dotcount = 0;
864             }
865         }
866       progress(':'); /* restart with a new random value */
867     }
868 }
869
870 /****************
871  * Returns: true if this may be a prime
872  * RM_ROUNDS gives the number of Rabin-Miller tests to run.
873  */
874 static int
875 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
876              gcry_prime_check_func_t cb_func, void *cb_arg)
877 {
878   int i;
879   unsigned int x;
880   unsigned int count=0;
881
882   /* Check against small primes. */
883   for (i=0; (x = small_prime_numbers[i]); i++ )
884     {
885       if ( mpi_divisible_ui( prime, x ) )
886         return 0;
887     }
888
889   /* A quick Fermat test. */
890   {
891     gcry_mpi_t result = mpi_alloc_like( prime );
892     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
893     mpi_sub_ui( pminus1, prime, 1);
894     gcry_mpi_powm( result, val_2, pminus1, prime );
895     mpi_free( pminus1 );
896     if ( mpi_cmp_ui( result, 1 ) )
897       {
898         /* Is composite. */
899         mpi_free( result );
900         progress('.');
901         return 0;
902       }
903     mpi_free( result );
904   }
905
906   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
907     {
908       /* Perform stronger tests. */
909       if ( is_prime( prime, rm_rounds, &count ) )
910         {
911           if (!cb_func
912               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
913             return 1; /* Probably a prime. */
914         }
915     }
916   progress('.');
917   return 0;
918 }
919
920
921 /*
922  * Return true if n is probably a prime
923  */
924 static int
925 is_prime (gcry_mpi_t n, int steps, unsigned int *count)
926 {
927   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
928   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
929   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
930   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
931   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
932   gcry_mpi_t q;
933   unsigned i, j, k;
934   int rc = 0;
935   unsigned nbits = mpi_get_nbits( n );
936
937   if (steps < 5) /* Make sure that we do at least 5 rounds. */
938     steps = 5;
939
940   mpi_sub_ui( nminus1, n, 1 );
941
942   /* Find q and k, so that n = 1 + 2^k * q . */
943   q = mpi_copy ( nminus1 );
944   k = mpi_trailing_zeros ( q );
945   mpi_tdiv_q_2exp (q, q, k);
946
947   for (i=0 ; i < steps; i++ )
948     {
949       ++*count;
950       if( !i )
951         {
952           mpi_set_ui( x, 2 );
953         }
954       else
955         {
956           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
957
958           /* Make sure that the number is smaller than the prime and
959              keep the randomness of the high bit. */
960           if ( mpi_test_bit ( x, nbits-2) )
961             {
962               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
963             }
964           else
965             {
966               mpi_set_highbit( x, nbits-2 );
967               mpi_clear_bit( x, nbits-2 );
968             }
969           gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
970         }
971       gcry_mpi_powm ( y, x, q, n);
972       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
973         {
974           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
975             {
976               gcry_mpi_powm(y, y, a2, n);
977               if( !mpi_cmp_ui( y, 1 ) )
978                 goto leave; /* Not a prime. */
979             }
980           if (mpi_cmp( y, nminus1 ) )
981             goto leave; /* Not a prime. */
982         }
983       progress('+');
984     }
985   rc = 1; /* May be a prime. */
986
987  leave:
988   mpi_free( x );
989   mpi_free( y );
990   mpi_free( z );
991   mpi_free( nminus1 );
992   mpi_free( q );
993   mpi_free( a2 );
994
995   return rc;
996 }
997
998
999 /* Given ARRAY of size N with M elements set to true produce a
1000    modified array with the next permutation of M elements.  Note, that
1001    ARRAY is used in a one-bit-per-byte approach.  To detected the last
1002    permutation it is useful to initialize the array with the first M
1003    element set to true and use this test:
1004        m_out_of_n (array, m, n);
1005        for (i = j = 0; i < n && j < m; i++)
1006          if (array[i])
1007            j++;
1008        if (j == m)
1009          goto ready;
1010
1011    This code is based on the algorithm 452 from the "Collected
1012    Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
1013 */
1014 static void
1015 m_out_of_n ( char *array, int m, int n )
1016 {
1017   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
1018
1019   if( !m || m >= n )
1020     return;
1021
1022   /* Need to handle this simple case separately. */
1023   if( m == 1 )
1024     {
1025       for (i=0; i < n; i++ )
1026         {
1027           if ( array[i] )
1028             {
1029               array[i++] = 0;
1030               if( i >= n )
1031                 i = 0;
1032               array[i] = 1;
1033               return;
1034             }
1035         }
1036       BUG();
1037     }
1038
1039
1040   for (j=1; j < n; j++ )
1041     {
1042       if ( array[n-1] == array[n-j-1])
1043         continue;
1044       j1 = j;
1045       break;
1046     }
1047
1048   if ( (m & 1) )
1049     {
1050       /* M is odd. */
1051       if( array[n-1] )
1052         {
1053           if( j1 & 1 )
1054             {
1055               k1 = n - j1;
1056               k2 = k1+2;
1057               if( k2 > n )
1058                 k2 = n;
1059               goto leave;
1060             }
1061           goto scan;
1062         }
1063       k2 = n - j1 - 1;
1064       if( k2 == 0 )
1065         {
1066           k1 = i;
1067           k2 = n - j1;
1068         }
1069       else if( array[k2] && array[k2-1] )
1070         k1 = n;
1071       else
1072         k1 = k2 + 1;
1073     }
1074   else
1075     {
1076       /* M is even. */
1077       if( !array[n-1] )
1078         {
1079           k1 = n - j1;
1080           k2 = k1 + 1;
1081           goto leave;
1082         }
1083
1084       if( !(j1 & 1) )
1085         {
1086           k1 = n - j1;
1087           k2 = k1+2;
1088           if( k2 > n )
1089             k2 = n;
1090           goto leave;
1091         }
1092     scan:
1093       jp = n - j1 - 1;
1094       for (i=1; i <= jp; i++ )
1095         {
1096           i1 = jp + 2 - i;
1097           if( array[i1-1]  )
1098             {
1099               if( array[i1-2] )
1100                 {
1101                   k1 = i1 - 1;
1102                   k2 = n - j1;
1103                 }
1104               else
1105                 {
1106                   k1 = i1 - 1;
1107                   k2 = n + 1 - j1;
1108                 }
1109               goto leave;
1110             }
1111         }
1112       k1 = 1;
1113       k2 = n + 1 - m;
1114     }
1115  leave:
1116   /* Now complement the two selected bits. */
1117   array[k1-1] = !array[k1-1];
1118   array[k2-1] = !array[k2-1];
1119 }
1120
1121
1122 /* Generate a new prime number of PRIME_BITS bits and store it in
1123    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
1124    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
1125    non-zero, allocate a new, NULL-terminated array holding the prime
1126    factors and store it in FACTORS.  FLAGS might be used to influence
1127    the prime number generation process.  */
1128 gcry_error_t
1129 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1130                      unsigned int factor_bits, gcry_mpi_t **factors,
1131                      gcry_prime_check_func_t cb_func, void *cb_arg,
1132                      gcry_random_level_t random_level,
1133                      unsigned int flags)
1134 {
1135   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1136   gcry_mpi_t *factors_generated = NULL;
1137   gcry_mpi_t prime_generated = NULL;
1138   unsigned int mode = 0;
1139
1140   if (!prime)
1141     return gpg_error (GPG_ERR_INV_ARG);
1142   *prime = NULL;
1143
1144   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1145     mode = 1;
1146
1147   /* Generate.  */
1148   err = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1149                                  factor_bits, NULL,
1150                                  factors? &factors_generated : NULL,
1151                                  random_level, flags, 1,
1152                                  cb_func, cb_arg);
1153
1154   if (! err)
1155     if (cb_func)
1156       {
1157         /* Additional check. */
1158         if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1159           {
1160             /* Failed, deallocate resources.  */
1161             unsigned int i;
1162
1163             mpi_free (prime_generated);
1164             if (factors)
1165               {
1166                 for (i = 0; factors_generated[i]; i++)
1167                   mpi_free (factors_generated[i]);
1168                 gcry_free (factors_generated);
1169               }
1170             err = GPG_ERR_GENERAL;
1171           }
1172       }
1173
1174   if (! err)
1175     {
1176       if (factors)
1177         *factors = factors_generated;
1178       *prime = prime_generated;
1179     }
1180
1181   return gcry_error (err);
1182 }
1183
1184 /* Check whether the number X is prime.  */
1185 gcry_error_t
1186 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1187 {
1188   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1189   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
1190
1191   (void)flags;
1192
1193   /* We use 64 rounds because the prime we are going to test is not
1194      guaranteed to be a random one. */
1195   if (! check_prime (x, val_2, 64, NULL, NULL))
1196     err = GPG_ERR_NO_PRIME;
1197
1198   mpi_free (val_2);
1199
1200   return gcry_error (err);
1201 }
1202
1203 /* Find a generator for PRIME where the factorization of (prime-1) is
1204    in the NULL terminated array FACTORS. Return the generator as a
1205    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1206    atart for the search. Returns 0 on success.*/
1207 gcry_error_t
1208 gcry_prime_group_generator (gcry_mpi_t *r_g,
1209                             gcry_mpi_t prime, gcry_mpi_t *factors,
1210                             gcry_mpi_t start_g)
1211 {
1212   gcry_mpi_t tmp = gcry_mpi_new (0);
1213   gcry_mpi_t b = gcry_mpi_new (0);
1214   gcry_mpi_t pmin1 = gcry_mpi_new (0);
1215   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
1216   int first = 1;
1217   int i, n;
1218
1219   if (!factors || !r_g || !prime)
1220     return gpg_error (GPG_ERR_INV_ARG);
1221   *r_g = NULL;
1222
1223   for (n=0; factors[n]; n++)
1224     ;
1225   if (n < 2)
1226     return gpg_error (GPG_ERR_INV_ARG);
1227
1228   /* Extra sanity check - usually disabled. */
1229 /*   mpi_set (tmp, factors[0]); */
1230 /*   for(i = 1; i < n; i++) */
1231 /*     mpi_mul (tmp, tmp, factors[i]); */
1232 /*   mpi_add_ui (tmp, tmp, 1); */
1233 /*   if (mpi_cmp (prime, tmp)) */
1234 /*     return gpg_error (GPG_ERR_INV_ARG); */
1235
1236   gcry_mpi_sub_ui (pmin1, prime, 1);
1237   do
1238     {
1239       if (first)
1240         first = 0;
1241       else
1242         gcry_mpi_add_ui (g, g, 1);
1243
1244       if (DBG_CIPHER)
1245         {
1246           log_debug ("checking g:");
1247           gcry_mpi_dump (g);
1248           log_debug ("\n");
1249         }
1250       else
1251         progress('^');
1252
1253       for (i = 0; i < n; i++)
1254         {
1255           mpi_fdiv_q (tmp, pmin1, factors[i]);
1256           gcry_mpi_powm (b, g, tmp, prime);
1257           if (! mpi_cmp_ui (b, 1))
1258             break;
1259         }
1260       if (DBG_CIPHER)
1261         progress('\n');
1262     }
1263   while (i < n);
1264
1265   gcry_mpi_release (tmp);
1266   gcry_mpi_release (b);
1267   gcry_mpi_release (pmin1);
1268   *r_g = g;
1269
1270   return 0;
1271 }
1272
1273 /* Convenience function to release the factors array. */
1274 void
1275 gcry_prime_release_factors (gcry_mpi_t *factors)
1276 {
1277   if (factors)
1278     {
1279       int i;
1280
1281       for (i=0; factors[i]; i++)
1282         mpi_free (factors[i]);
1283       gcry_free (factors);
1284     }
1285 }
1286
1287
1288 \f
1289 /* Helper for _gcry_derive_x931_prime.  */
1290 static gcry_mpi_t
1291 find_x931_prime (const gcry_mpi_t pfirst)
1292 {
1293   gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1294   gcry_mpi_t prime;
1295
1296   prime = gcry_mpi_copy (pfirst);
1297   /* If P is even add 1.  */
1298   mpi_set_bit (prime, 0);
1299
1300   /* We use 64 Rabin-Miller rounds which is better and thus
1301      sufficient.  We do not have a Lucas test implementaion thus we
1302      can't do it in the X9.31 preferred way of running a few
1303      Rabin-Miller followed by one Lucas test.  */
1304   while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1305     mpi_add_ui (prime, prime, 2);
1306
1307   mpi_free (val_2);
1308
1309   return prime;
1310 }
1311
1312
1313 /* Generate a prime using the algorithm from X9.31 appendix B.4.
1314
1315    This function requires that the provided public exponent E is odd.
1316    XP, XP1 and XP2 are the seed values.  All values are mandatory.
1317
1318    On success the prime is returned.  If R_P1 or R_P2 are given the
1319    internal values P1 and P2 are saved at these addresses.  On error
1320    NULL is returned.  */
1321 gcry_mpi_t
1322 _gcry_derive_x931_prime (const gcry_mpi_t xp,
1323                          const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1324                          const gcry_mpi_t e,
1325                          gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1326 {
1327   gcry_mpi_t p1, p2, p1p2, yp0;
1328
1329   if (!xp || !xp1 || !xp2)
1330     return NULL;
1331   if (!e || !mpi_test_bit (e, 0))
1332     return NULL;  /* We support only odd values for E.  */
1333
1334   p1 = find_x931_prime (xp1);
1335   p2 = find_x931_prime (xp2);
1336   p1p2 = mpi_alloc_like (xp);
1337   mpi_mul (p1p2, p1, p2);
1338
1339   {
1340     gcry_mpi_t r1, tmp;
1341
1342     /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1343     tmp = mpi_alloc_like (p1);
1344     mpi_invm (tmp, p2, p1);
1345     mpi_mul (tmp, tmp, p2);
1346     r1 = tmp;
1347
1348     tmp = mpi_alloc_like (p2);
1349     mpi_invm (tmp, p1, p2);
1350     mpi_mul (tmp, tmp, p1);
1351     mpi_sub (r1, r1, tmp);
1352
1353     /* Fixup a negative value.  */
1354     if (mpi_is_neg (r1))
1355       mpi_add (r1, r1, p1p2);
1356
1357     /* yp0 = xp + (r1 - xp mod p1*p2)  */
1358     yp0 = tmp; tmp = NULL;
1359     mpi_subm (yp0, r1, xp, p1p2);
1360     mpi_add (yp0, yp0, xp);
1361     mpi_free (r1);
1362
1363     /* Fixup a negative value.  */
1364     if (mpi_cmp (yp0, xp) < 0 )
1365       mpi_add (yp0, yp0, p1p2);
1366   }
1367
1368   /* yp0 is now the first integer greater than xp with p1 being a
1369      large prime factor of yp0-1 and p2 a large prime factor of yp0+1.  */
1370
1371   /* Note that the first example from X9.31 (D.1.1) which uses
1372        (Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1373        (Xq2 #134E4CAA16D2350A21D775C404#)
1374        (Xq  #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1375              7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1376              6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1377              321DE34A#))))
1378      returns an yp0 of
1379             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1380              7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1381              BF20CB896EE37E098A906313271422162CB6C642
1382              75C1201F#
1383      and not
1384             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1385              7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1386              C88FE299D52D78BE405A97E01FD71DD7819ECB91
1387              FA85A076#
1388      as stated in the standard.  This seems to be a bug in X9.31.
1389    */
1390
1391   {
1392     gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1393     gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1394     int gcdres;
1395
1396     mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body.  */
1397     mpi_sub_ui (yp0, yp0, 1);   /* Ditto.  */
1398     for (;;)
1399       {
1400         gcdres = gcry_mpi_gcd (gcdtmp, e, yp0);
1401         mpi_add_ui (yp0, yp0, 1);
1402         if (!gcdres)
1403           progress ('/');  /* gcd (e, yp0-1) != 1  */
1404         else if (check_prime (yp0, val_2, 64, NULL, NULL))
1405           break; /* Found.  */
1406         /* We add p1p2-1 because yp0 is incremented after the gcd test.  */
1407         mpi_add (yp0, yp0, p1p2);
1408       }
1409     mpi_free (gcdtmp);
1410     mpi_free (val_2);
1411   }
1412
1413   mpi_free (p1p2);
1414
1415   progress('\n');
1416   if (r_p1)
1417     *r_p1 = p1;
1418   else
1419     mpi_free (p1);
1420   if (r_p2)
1421     *r_p2 = p2;
1422   else
1423     mpi_free (p2);
1424   return yp0;
1425 }
1426
1427
1428 \f
1429 /* Generate the two prime used for DSA using the algorithm specified
1430    in FIPS 186-2.  PBITS is the desired length of the prime P and a
1431    QBITS the length of the prime Q.  If SEED is not supplied and
1432    SEEDLEN is 0 the function generates an appropriate SEED.  On
1433    success the generated primes are stored at R_Q and R_P, the counter
1434    value is stored at R_COUNTER and the seed actually used for
1435    generation is stored at R_SEED and R_SEEDVALUE.  */
1436 gpg_err_code_t
1437 _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1438                                 const void *seed, size_t seedlen,
1439                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1440                                 int *r_counter,
1441                                 void **r_seed, size_t *r_seedlen)
1442 {
1443   gpg_err_code_t ec;
1444   unsigned char seed_help_buffer[160/8];  /* Used to hold a generated SEED. */
1445   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1446   unsigned char digest[160/8];  /* Helper buffer for SHA-1 digest.  */
1447   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1448   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1449   int i;
1450
1451   unsigned char value_u[160/8];
1452   int value_n, value_b, value_k;
1453   int counter;
1454   gcry_mpi_t value_w = NULL;
1455   gcry_mpi_t value_x = NULL;
1456   gcry_mpi_t prime_q = NULL;
1457   gcry_mpi_t prime_p = NULL;
1458
1459   /* FIPS 186-2 allows only for 1024/160 bit.  */
1460   if (pbits != 1024 || qbits != 160)
1461     return GPG_ERR_INV_KEYLEN;
1462
1463   if (!seed && !seedlen)
1464     ; /* No seed value given:  We are asked to generate it.  */
1465   else if (!seed || seedlen < qbits/8)
1466     return GPG_ERR_INV_ARG;
1467
1468   /* Allocate a buffer to later compute SEED+some_increment. */
1469   seed_plus = gcry_malloc (seedlen < 20? 20:seedlen);
1470   if (!seed_plus)
1471     {
1472       ec = gpg_err_code_from_syserror ();
1473       goto leave;
1474     }
1475
1476   val_2   = mpi_alloc_set_ui (2);
1477   value_n = (pbits - 1) / qbits;
1478   value_b = (pbits - 1) - value_n * qbits;
1479   value_w = gcry_mpi_new (pbits);
1480   value_x = gcry_mpi_new (pbits);
1481
1482  restart:
1483   /* Generate Q.  */
1484   for (;;)
1485     {
1486       /* Step 1: Generate a (new) seed unless one has been supplied.  */
1487       if (!seed)
1488         {
1489           seedlen = sizeof seed_help_buffer;
1490           gcry_create_nonce (seed_help_buffer, seedlen);
1491           seed = seed_help_buffer;
1492         }
1493
1494       /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits})  */
1495       memcpy (seed_plus, seed, seedlen);
1496       for (i=seedlen-1; i >= 0; i--)
1497         {
1498           seed_plus[i]++;
1499           if (seed_plus[i])
1500             break;
1501         }
1502       gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1503       gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1504       for (i=0; i < sizeof value_u; i++)
1505         value_u[i] ^= digest[i];
1506
1507       /* Step 3:  Form q from U  */
1508       gcry_mpi_release (prime_q); prime_q = NULL;
1509       ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1510                                         value_u, sizeof value_u, NULL));
1511       if (ec)
1512         goto leave;
1513       mpi_set_highbit (prime_q, qbits-1 );
1514       mpi_set_bit (prime_q, 0);
1515
1516       /* Step 4:  Test whether Q is prime using 64 round of Rabin-Miller.  */
1517       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1518         break; /* Yes, Q is prime.  */
1519
1520       /* Step 5.  */
1521       seed = NULL;  /* Force a new seed at Step 1.  */
1522     }
1523
1524   /* Step 6.  Note that we do no use an explicit offset but increment
1525      SEED_PLUS accordingly.  SEED_PLUS is currently SEED+1.  */
1526   counter = 0;
1527
1528   /* Generate P. */
1529   prime_p = gcry_mpi_new (pbits);
1530   for (;;)
1531     {
1532       /* Step 7: For k = 0,...n let
1533                    V_k = sha1(seed+offset+k) mod 2^{qbits}
1534          Step 8: W = V_0 + V_1*2^160 +
1535                          ...
1536                          + V_{n-1}*2^{(n-1)*160}
1537                          + (V_{n} mod 2^b)*2^{n*160}
1538        */
1539       mpi_set_ui (value_w, 0);
1540       for (value_k=0; value_k <= value_n; value_k++)
1541         {
1542           /* There is no need to have an explicit offset variable:  In
1543              the first round we shall have an offset of 2, this is
1544              achieved by using SEED_PLUS which is already at SEED+1,
1545              thus we just need to increment it once again.  The
1546              requirement for the next round is to update offset by N,
1547              which we implictly did at the end of this loop, and then
1548              to add one; this one is the same as in the first round.  */
1549           for (i=seedlen-1; i >= 0; i--)
1550             {
1551               seed_plus[i]++;
1552               if (seed_plus[i])
1553                 break;
1554             }
1555           gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1556
1557           gcry_mpi_release (tmpval); tmpval = NULL;
1558           ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1559                                             digest, sizeof digest, NULL));
1560           if (ec)
1561             goto leave;
1562           if (value_k == value_n)
1563             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1564           mpi_lshift (tmpval, tmpval, value_k*qbits);
1565           mpi_add (value_w, value_w, tmpval);
1566         }
1567
1568       /* Step 8 continued: X = W + 2^{L-1}  */
1569       mpi_set_ui (value_x, 0);
1570       mpi_set_highbit (value_x, pbits-1);
1571       mpi_add (value_x, value_x, value_w);
1572
1573       /* Step 9:  c = X mod 2q,  p = X - (c - 1)  */
1574       mpi_mul_2exp (tmpval, prime_q, 1);
1575       mpi_mod (tmpval, value_x, tmpval);
1576       mpi_sub_ui (tmpval, tmpval, 1);
1577       mpi_sub (prime_p, value_x, tmpval);
1578
1579       /* Step 10: If  p < 2^{L-1}  skip the primality test.  */
1580       /* Step 11 and 12: Primality test.  */
1581       if (mpi_get_nbits (prime_p) >= pbits-1
1582           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1583         break; /* Yes, P is prime, continue with Step 15.  */
1584
1585       /* Step 13: counter = counter + 1, offset = offset + n + 1. */
1586       counter++;
1587
1588       /* Step 14: If counter >= 2^12  goto Step 1.  */
1589       if (counter >= 4096)
1590         goto restart;
1591     }
1592
1593   /* Step 15:  Save p, q, counter and seed.  */
1594 /*   log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1595 /*              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1596 /*   log_printhex("fips186-2 seed:", seed, seedlen); */
1597 /*   log_mpidump ("fips186-2 prime p", prime_p); */
1598 /*   log_mpidump ("fips186-2 prime q", prime_q); */
1599   if (r_q)
1600     {
1601       *r_q = prime_q;
1602       prime_q = NULL;
1603     }
1604   if (r_p)
1605     {
1606       *r_p = prime_p;
1607       prime_p = NULL;
1608     }
1609   if (r_counter)
1610     *r_counter = counter;
1611   if (r_seed && r_seedlen)
1612     {
1613       memcpy (seed_plus, seed, seedlen);
1614       *r_seed = seed_plus;
1615       seed_plus = NULL;
1616       *r_seedlen = seedlen;
1617     }
1618
1619
1620  leave:
1621   gcry_mpi_release (tmpval);
1622   gcry_mpi_release (value_x);
1623   gcry_mpi_release (value_w);
1624   gcry_mpi_release (prime_p);
1625   gcry_mpi_release (prime_q);
1626   gcry_free (seed_plus);
1627   gcry_mpi_release (val_2);
1628   return ec;
1629 }
1630
1631
1632 \f
1633 /* WARNING: The code below has not yet been tested!  However, it is
1634    not yet used.  We need to wait for FIPS 186-3 final and for test
1635    vectors.
1636
1637    Generate the two prime used for DSA using the algorithm specified
1638    in FIPS 186-3, A.1.1.2.  PBITS is the desired length of the prime P
1639    and a QBITS the length of the prime Q.  If SEED is not supplied and
1640    SEEDLEN is 0 the function generates an appropriate SEED.  On
1641    success the generated primes are stored at R_Q and R_P, the counter
1642    value is stored at R_COUNTER and the seed actually used for
1643    generation is stored at R_SEED and R_SEEDVALUE.  The hash algorithm
1644    used is stored at R_HASHALGO.
1645
1646    Note that this function is very similar to the fips186_2 code.  Due
1647    to the minor differences, other buffer sizes and for documentarion,
1648    we use a separate function.
1649 */
1650 gpg_err_code_t
1651 _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1652                                 const void *seed, size_t seedlen,
1653                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1654                                 int *r_counter,
1655                                 void **r_seed, size_t *r_seedlen,
1656                                 int *r_hashalgo)
1657 {
1658   gpg_err_code_t ec;
1659   unsigned char seed_help_buffer[256/8];  /* Used to hold a generated SEED. */
1660   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1661   unsigned char digest[256/8];  /* Helper buffer for SHA-1 digest.  */
1662   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1663   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1664   int hashalgo;                 /* The id of the Approved Hash Function.  */
1665   int i;
1666
1667   unsigned char value_u[256/8];
1668   int value_n, value_b, value_j;
1669   int counter;
1670   gcry_mpi_t value_w = NULL;
1671   gcry_mpi_t value_x = NULL;
1672   gcry_mpi_t prime_q = NULL;
1673   gcry_mpi_t prime_p = NULL;
1674
1675   gcry_assert (sizeof seed_help_buffer == sizeof digest
1676                && sizeof seed_help_buffer == sizeof value_u);
1677
1678   /* Step 1:  Check the requested prime lengths.  */
1679   /* Note that due to the size of our buffers QBITS is limited to 256.  */
1680   if (pbits == 1024 && qbits == 160)
1681     hashalgo = GCRY_MD_SHA1;
1682   else if (pbits == 2048 && qbits == 224)
1683     hashalgo = GCRY_MD_SHA224;
1684   else if (pbits == 2048 && qbits == 256)
1685     hashalgo = GCRY_MD_SHA256;
1686   else if (pbits == 3072 && qbits == 256)
1687     hashalgo = GCRY_MD_SHA256;
1688   else
1689     return GPG_ERR_INV_KEYLEN;
1690
1691   /* Also check that the hash algorithm is available.  */
1692   ec = gpg_err_code (gcry_md_test_algo (hashalgo));
1693   if (ec)
1694     return ec;
1695   gcry_assert (qbits/8 <= sizeof digest);
1696   gcry_assert (gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1697
1698
1699   /* Step 2:  Check seedlen.  */
1700   if (!seed && !seedlen)
1701     ; /* No seed value given:  We are asked to generate it.  */
1702   else if (!seed || seedlen < qbits/8)
1703     return GPG_ERR_INV_ARG;
1704
1705   /* Allocate a buffer to later compute SEED+some_increment and a few
1706      helper variables.  */
1707   seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer?
1708                            sizeof seed_help_buffer : seedlen);
1709   if (!seed_plus)
1710     {
1711       ec = gpg_err_code_from_syserror ();
1712       goto leave;
1713     }
1714   val_2   = mpi_alloc_set_ui (2);
1715   value_w = gcry_mpi_new (pbits);
1716   value_x = gcry_mpi_new (pbits);
1717
1718   /* Step 3: n = \lceil L / outlen \rceil - 1  */
1719   value_n = (pbits + qbits - 1) / qbits - 1;
1720   /* Step 4: b = L - 1 - (n * outlen)  */
1721   value_b = pbits - 1 - (value_n * qbits);
1722
1723  restart:
1724   /* Generate Q.  */
1725   for (;;)
1726     {
1727       /* Step 5:  Generate a (new) seed unless one has been supplied.  */
1728       if (!seed)
1729         {
1730           seedlen = qbits/8;
1731           gcry_assert (seedlen <= sizeof seed_help_buffer);
1732           gcry_create_nonce (seed_help_buffer, seedlen);
1733           seed = seed_help_buffer;
1734         }
1735
1736       /* Step 6:  U = hash(seed)  */
1737       gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1738
1739       /* Step 7:  q = 2^{N-1} + U + 1 - (U mod 2)  */
1740       if ( !(value_u[qbits/8-1] & 0x01) )
1741         {
1742           for (i=qbits/8-1; i >= 0; i--)
1743             {
1744               value_u[i]++;
1745               if (value_u[i])
1746                 break;
1747             }
1748         }
1749       gcry_mpi_release (prime_q); prime_q = NULL;
1750       ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1751                                         value_u, sizeof value_u, NULL));
1752       if (ec)
1753         goto leave;
1754       mpi_set_highbit (prime_q, qbits-1 );
1755
1756       /* Step 8:  Test whether Q is prime using 64 round of Rabin-Miller.
1757                   According to table C.1 this is sufficient for all
1758                   supported prime sizes (i.e. up 3072/256).  */
1759       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1760         break; /* Yes, Q is prime.  */
1761
1762       /* Step 8.  */
1763       seed = NULL;  /* Force a new seed at Step 5.  */
1764     }
1765
1766   /* Step 11.  Note that we do no use an explicit offset but increment
1767      SEED_PLUS accordingly.  */
1768   memcpy (seed_plus, seed, seedlen);
1769   counter = 0;
1770
1771   /* Generate P. */
1772   prime_p = gcry_mpi_new (pbits);
1773   for (;;)
1774     {
1775       /* Step 11.1: For j = 0,...n let
1776                       V_j = hash(seed+offset+j)
1777          Step 11.2: W = V_0 + V_1*2^outlen +
1778                             ...
1779                             + V_{n-1}*2^{(n-1)*outlen}
1780                             + (V_{n} mod 2^b)*2^{n*outlen}
1781        */
1782       mpi_set_ui (value_w, 0);
1783       for (value_j=0; value_j <= value_n; value_j++)
1784         {
1785           /* There is no need to have an explicit offset variable: In
1786              the first round we shall have an offset of 1 and a j of
1787              0.  This is achieved by incrementing SEED_PLUS here.  For
1788              the next round offset is implicitly updated by using
1789              SEED_PLUS again.  */
1790           for (i=seedlen-1; i >= 0; i--)
1791             {
1792               seed_plus[i]++;
1793               if (seed_plus[i])
1794                 break;
1795             }
1796           gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1797
1798           gcry_mpi_release (tmpval); tmpval = NULL;
1799           ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1800                                             digest, sizeof digest, NULL));
1801           if (ec)
1802             goto leave;
1803           if (value_j == value_n)
1804             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1805           mpi_lshift (tmpval, tmpval, value_j*qbits);
1806           mpi_add (value_w, value_w, tmpval);
1807         }
1808
1809       /* Step 11.3: X = W + 2^{L-1}  */
1810       mpi_set_ui (value_x, 0);
1811       mpi_set_highbit (value_x, pbits-1);
1812       mpi_add (value_x, value_x, value_w);
1813
1814       /* Step 11.4:  c = X mod 2q  */
1815       mpi_mul_2exp (tmpval, prime_q, 1);
1816       mpi_mod (tmpval, value_x, tmpval);
1817
1818       /* Step 11.5:  p = X - (c - 1)  */
1819       mpi_sub_ui (tmpval, tmpval, 1);
1820       mpi_sub (prime_p, value_x, tmpval);
1821
1822       /* Step 11.6: If  p < 2^{L-1}  skip the primality test.  */
1823       /* Step 11.7 and 11.8: Primality test.  */
1824       if (mpi_get_nbits (prime_p) >= pbits-1
1825           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1826         break; /* Yes, P is prime, continue with Step 15.  */
1827
1828       /* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1829                     If counter >= 4L  goto Step 5.  */
1830       counter++;
1831       if (counter >= 4*pbits)
1832         goto restart;
1833     }
1834
1835   /* Step 12:  Save p, q, counter and seed.  */
1836   log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n",
1837              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter);
1838   log_printhex("fips186-3 seed:", seed, seedlen);
1839   log_mpidump ("fips186-3 prime p", prime_p);
1840   log_mpidump ("fips186-3 prime q", prime_q);
1841   if (r_q)
1842     {
1843       *r_q = prime_q;
1844       prime_q = NULL;
1845     }
1846   if (r_p)
1847     {
1848       *r_p = prime_p;
1849       prime_p = NULL;
1850     }
1851   if (r_counter)
1852     *r_counter = counter;
1853   if (r_seed && r_seedlen)
1854     {
1855       memcpy (seed_plus, seed, seedlen);
1856       *r_seed = seed_plus;
1857       seed_plus = NULL;
1858       *r_seedlen = seedlen;
1859     }
1860   if (r_hashalgo)
1861     *r_hashalgo = hashalgo;
1862
1863  leave:
1864   gcry_mpi_release (tmpval);
1865   gcry_mpi_release (value_x);
1866   gcry_mpi_release (value_w);
1867   gcry_mpi_release (prime_p);
1868   gcry_mpi_release (prime_q);
1869   gcry_free (seed_plus);
1870   gcry_mpi_release (val_2);
1871   return ec;
1872 }