Implemented transient-key flag as requested by the GNUNet folks.
[libgcrypt.git] / cipher / primegen.c
1 /* primegen.c - prime number generator
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003
3  *               2004 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 = ATH_MUTEX_INITIALIZER;
145
146
147
148 /* Save PRIME which has been generated at RANDOMLEVEL for later
149    use. Needs to be called while primepool_lock is being hold.  Note
150    that PRIME should be considered released after calling this
151    function. */
152 static void
153 save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel)
154 {
155   struct primepool_s *item, *item2;
156   size_t n;
157
158   for (n=0, item = primepool; item; item = item->next, n++)
159     if (!item->prime)
160       break;
161   if (!item && n > 100)
162     {
163       /* Remove some of the entries.  Our strategy is removing
164          the last third from the list. */
165       int i;
166       
167       for (i=0, item2 = primepool; item2; item2 = item2->next)
168         {
169           if (i >= n/3*2)
170             {
171               gcry_mpi_release (item2->prime);
172               item2->prime = NULL;
173               if (!item)
174                 item = item2;
175             }
176         }
177     }
178   if (!item)
179     {
180       item = gcry_calloc (1, sizeof *item);
181       if (!item)
182         {
183           /* Out of memory.  Silently giving up. */
184           gcry_mpi_release (prime);
185           return; 
186         }
187       item->next = primepool;
188       primepool = item;
189     }
190   item->prime = prime;
191   item->nbits = mpi_get_nbits (prime);
192   item->randomlevel = randomlevel;
193 }
194
195
196 /* Return a prime for the prime pool or NULL if none has been found.
197    The prime needs to match NBITS and randomlevel. This function needs
198    to be called why the primepool_look is being hold. */
199 static gcry_mpi_t
200 get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel)
201 {
202   struct primepool_s *item;
203
204   for (item = primepool; item; item = item->next)
205     if (item->prime
206         && item->nbits == nbits && item->randomlevel == randomlevel)
207       {
208         gcry_mpi_t prime = item->prime;
209         item->prime = NULL;
210         gcry_assert (nbits == mpi_get_nbits (prime));
211         return prime;
212       }
213   return NULL;
214 }
215
216
217
218
219
220 \f
221 void
222 _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
223                                    void *cb_data )
224 {
225   progress_cb = cb;
226   progress_cb_data = cb_data;
227 }
228
229
230 static void
231 progress( int c )
232 {
233   if ( progress_cb )
234     progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
235 }
236
237
238 /****************
239  * Generate a prime number (stored in secure memory)
240  */
241 gcry_mpi_t
242 _gcry_generate_secret_prime (unsigned int nbits,
243                              gcry_random_level_t random_level,
244                              int (*extra_check)(void*, gcry_mpi_t),
245                              void *extra_check_arg)
246 {
247   gcry_mpi_t prime;
248
249   prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg);
250   progress('\n');
251   return prime;
252 }
253
254
255 /* Generate a prime number which may be public, i.e. not allocated in
256    secure memory.  */
257 gcry_mpi_t
258 _gcry_generate_public_prime (unsigned int nbits,
259                              gcry_random_level_t random_level,
260                              int (*extra_check)(void*, gcry_mpi_t),
261                              void *extra_check_arg)
262 {
263   gcry_mpi_t prime;
264
265   prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg);
266   progress('\n');
267   return prime;
268 }
269
270
271 /* Core prime generation function.  The algorithm used to generate
272    practically save primes is due to Lim and Lee as described in the
273    CRYPTO '97 proceedings (ISBN3540633847) page 260.
274
275    NEED_Q_FACTOR: If true make sure that at least one factor is of
276                   size qbits.  This is for example required for DSA.
277    PRIME_GENERATED: Adresss of a variable where the resulting prime
278                     number will be stored.
279    PBITS: Requested size of the prime number.  At least 48.
280    QBITS: One factor of the prime needs to be of this size.  Maybe 0
281           if this is not required.  See also MODE.
282    G: If not NULL an MPI which will receive a generator for the prime
283       for use with Elgamal.
284    RET_FACTORS: if not NULL, an array with all factors are stored at
285                 that address.
286    ALL_FACTORS: If set to true all factors of prime-1 are returned.
287    RANDOMLEVEL:  How strong should the random numers be.
288    FLAGS: Prime generation bit flags. Currently supported:
289           GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret.
290    CB_FUNC, CB_ARG:  Callback to be used for extra checks.
291
292  */
293 static gcry_err_code_t
294 prime_generate_internal (int need_q_factor,
295                          gcry_mpi_t *prime_generated, unsigned int pbits,
296                          unsigned int qbits, gcry_mpi_t g,
297                          gcry_mpi_t **ret_factors,
298                          gcry_random_level_t randomlevel, unsigned int flags,
299                          int all_factors,
300                          gcry_prime_check_func_t cb_func, void *cb_arg)
301 {
302   gcry_err_code_t err = 0;
303   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
304                                      caller.  */
305   gcry_mpi_t *factors = NULL;   /* Current factors.  */
306   gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */
307   gcry_mpi_t *pool = NULL;      /* Pool of primes.  */
308   int *pool_in_use = NULL;      /* Array with currently used POOL elements. */
309   unsigned char *perms = NULL;  /* Permutations of POOL.  */
310   gcry_mpi_t q_factor = NULL;   /* Used if QBITS is non-zero.  */
311   unsigned int fbits = 0;       /* Length of prime factors.  */
312   unsigned int n = 0;           /* Number of factors.  */
313   unsigned int m = 0;           /* Number of primes in pool.  */
314   gcry_mpi_t q = NULL;          /* First prime factor.  */
315   gcry_mpi_t prime = NULL;      /* Prime candidate.  */
316   unsigned int nprime = 0;      /* Bits of PRIME.  */
317   unsigned int req_qbits;       /* The original QBITS value.  */
318   gcry_mpi_t val_2;             /* For check_prime().  */
319   int is_locked = 0;            /* Flag to help unlocking the primepool. */
320   unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
321   unsigned int count1 = 0, count2 = 0;
322   unsigned int i = 0, j = 0;
323
324   if (pbits < 48)
325     return GPG_ERR_INV_ARG;
326
327   /* We won't use a too strong random elvel for the pooled subprimes. */
328   poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM?
329                      GCRY_STRONG_RANDOM : randomlevel);
330
331
332   /* If QBITS is not given, assume a reasonable value. */
333   if (!qbits)
334     qbits = pbits / 3;
335
336   req_qbits = qbits;
337
338   /* Find number of needed prime factors N.  */
339   for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++)
340     ;
341   n--;
342
343   val_2 = mpi_alloc_set_ui (2);
344
345   if ((! n) || ((need_q_factor) && (n < 2)))
346     {
347       err = GPG_ERR_INV_ARG;
348       goto leave;
349     }
350
351   if (need_q_factor)
352     {
353       n--;  /* Need one factor less because we want a specific Q-FACTOR. */
354       fbits = (pbits - 2 * req_qbits -1) / n;
355       qbits =  pbits - req_qbits - n * fbits;
356     }
357   else
358     {
359       fbits = (pbits - req_qbits -1) / n;
360       qbits = pbits - n * fbits;
361     }
362   
363   if (DBG_CIPHER)
364     log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
365                pbits, req_qbits, qbits, fbits, n);
366
367   /* Allocate an integer to old the new prime. */
368   prime = gcry_mpi_new (pbits);
369
370   /* Generate first prime factor.  */
371   q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
372
373   /* Generate a specific Q-Factor if requested. */
374   if (need_q_factor)
375     q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
376   
377   /* Allocate an array to hold all factors + 2 for later usage.  */
378   factors = gcry_calloc (n + 2, sizeof (*factors));
379   if (!factors)
380     {
381       err = gpg_err_code_from_errno (errno);
382       goto leave;
383     }
384
385   /* Allocate an array to track pool usage. */
386   pool_in_use = gcry_malloc (n * sizeof *pool_in_use);
387   if (!pool_in_use)
388     {
389       err = gpg_err_code_from_errno (errno);
390       goto leave;
391     }
392   for (i=0; i < n; i++)
393     pool_in_use[i] = -1;
394       
395   /* Make a pool of 3n+5 primes (this is an arbitrary value).  We
396      require at least 30 primes for are useful selection process. 
397      
398      FIXME: We need to do some reseacrh on the best formula for sizing
399      the pool.
400   */
401   m = n * 3 + 5;
402   if (need_q_factor) /* Need some more in this case. */
403     m += 5;
404   if (m < 30)
405     m = 30;
406   pool = gcry_calloc (m , sizeof (*pool));
407   if (! pool)
408     {
409       err = gpg_err_code_from_errno (errno);
410       goto leave;
411     }
412
413   /* Permutate over the pool of primes until we find a prime of the
414      requested length.  */
415   do
416     {
417     next_try:
418       for (i=0; i < n; i++)
419         pool_in_use[i] = -1;
420
421       if (!perms)
422         {
423           /* Allocate new primes.  This is done right at the beginning
424              of the loop and if we have later run out of primes. */
425           for (i = 0; i < m; i++)
426             {
427               mpi_free (pool[i]);
428               pool[i] = NULL;
429             }
430
431           /* Init m_out_of_n().  */
432           perms = gcry_calloc (1, m);
433           if (!perms)
434             {
435               err = gpg_err_code_from_errno (errno);
436               goto leave;
437             }
438
439           if (ath_mutex_lock (&primepool_lock))
440             {
441               err = GPG_ERR_INTERNAL;
442               goto leave;
443             }
444           is_locked = 1;
445           for (i = 0; i < n; i++)
446             {
447               perms[i] = 1; 
448               /* At a maximum we use strong random for the factors.
449                  This saves us a lot of entropy. Given that Q and
450                  possible Q-factor are also used in the final prime
451                  this should be acceptable.  We also don't allocate in
452                  secure memory to save on that scare resource too.  If
453                  Q has been allocated in secure memory, the final
454                  prime will be saved there anyway.  This is because
455                  our MPI routines take care of that.  GnuPG has worked
456                  this way ever since.  */
457               pool[i] = NULL;
458               if (is_locked)
459                 {
460                   pool[i] = get_pool_prime (fbits, poolrandomlevel);
461                   if (!pool[i])
462                     {
463                       if (ath_mutex_unlock (&primepool_lock))
464                         {
465                           err = GPG_ERR_INTERNAL;
466                           goto leave;
467                         }
468                       is_locked = 0;
469                     }
470                 }
471               if (!pool[i])
472                 pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
473               pool_in_use[i] = i;
474               factors[i] = pool[i];
475             }
476           if (is_locked && ath_mutex_unlock (&primepool_lock))
477             {
478               err = GPG_ERR_INTERNAL;
479               goto leave;
480             }
481           is_locked = 0;
482         }
483       else
484         {
485           /* Get next permutation. */
486           m_out_of_n ( (char*)perms, n, m);
487           if (ath_mutex_lock (&primepool_lock))
488             {
489               err = GPG_ERR_INTERNAL;
490               goto leave;
491             }
492           is_locked = 1;
493           for (i = j = 0; (i < m) && (j < n); i++)
494             if (perms[i])
495               {
496                 /* If the subprime has not yet beed generated do it now. */
497                 if (!pool[i] && is_locked)
498                   {
499                     pool[i] = get_pool_prime (fbits, poolrandomlevel);
500                     if (!pool[i])
501                       {
502                         if (ath_mutex_unlock (&primepool_lock))
503                           {
504                             err = GPG_ERR_INTERNAL;
505                             goto leave;
506                           }
507                         is_locked = 0;
508                       }
509                   }
510                 if (!pool[i])
511                   pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
512                 pool_in_use[j] = i;
513                 factors[j++] = pool[i];
514               }
515           if (is_locked && ath_mutex_unlock (&primepool_lock))
516             {
517               err = GPG_ERR_INTERNAL;
518               goto leave;
519             }
520           is_locked = 0;
521           if (i == n)
522             {
523               /* Ran out of permutations: Allocate new primes.  */
524               gcry_free (perms);
525               perms = NULL;
526               progress ('!');
527               goto next_try;    
528             }
529         }
530
531         /* Generate next prime candidate:
532            p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. 
533          */
534         mpi_set (prime, q);
535         mpi_mul_ui (prime, prime, 2);
536         if (need_q_factor)
537           mpi_mul (prime, prime, q_factor);
538         for(i = 0; i < n; i++)
539           mpi_mul (prime, prime, factors[i]);
540         mpi_add_ui (prime, prime, 1);
541         nprime = mpi_get_nbits (prime);
542
543         if (nprime < pbits)
544           {
545             if (++count1 > 20)
546               {
547                 count1 = 0;
548                 qbits++;
549                 progress('>');
550                 mpi_free (q);
551                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
552                 goto next_try;
553               }
554           }
555         else
556           count1 = 0;
557         
558         if (nprime > pbits)
559           {
560             if (++count2 > 20)
561               {
562                 count2 = 0;
563                 qbits--;
564                 progress('<');
565                 mpi_free (q);
566                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
567                 goto next_try;
568               }
569           }
570         else
571           count2 = 0;
572     }
573   while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
574                                               cb_func, cb_arg)));
575
576   if (DBG_CIPHER)
577     {
578       progress ('\n');
579       log_mpidump ("prime    : ", prime);
580       log_mpidump ("factor  q: ", q);
581       if (need_q_factor)
582         log_mpidump ("factor q0: ", q_factor);
583       for (i = 0; i < n; i++)
584         log_mpidump ("factor pi: ", factors[i]);
585       log_debug ("bit sizes: prime=%u, q=%u",
586                  mpi_get_nbits (prime), mpi_get_nbits (q));
587       if (need_q_factor)
588         log_debug (", q0=%u", mpi_get_nbits (q_factor));
589       for (i = 0; i < n; i++)
590         log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
591       progress('\n');
592     }
593
594   if (ret_factors)
595     {
596       /* Caller wants the factors.  */
597       factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
598       if (! factors_new)
599         {
600           err = gpg_err_code_from_errno (errno);
601           goto leave;
602         }
603
604       if (all_factors)
605         {
606           i = 0;
607           factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
608           factors_new[i++] = mpi_copy (q);
609           if (need_q_factor)
610             factors_new[i++] = mpi_copy (q_factor);
611           for(j=0; j < n; j++)
612             factors_new[i++] = mpi_copy (factors[j]);
613         }
614       else
615         {
616           i = 0;
617           if (need_q_factor)
618             {
619               factors_new[i++] = mpi_copy (q_factor);
620               for (; i <= n; i++)
621                 factors_new[i] = mpi_copy (factors[i]);
622             }
623           else
624             for (; i < n; i++ )
625               factors_new[i] = mpi_copy (factors[i]);
626         }
627     }
628   
629   if (g)
630     {
631       /* Create a generator (start with 3).  */
632       gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
633       gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
634       gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
635       
636       if (need_q_factor)
637         err = GPG_ERR_NOT_IMPLEMENTED;
638       else
639         {
640           factors[n] = q;
641           factors[n + 1] = mpi_alloc_set_ui (2);
642           mpi_sub_ui (pmin1, prime, 1);
643           mpi_set_ui (g, 2);
644           do
645             {
646               mpi_add_ui (g, g, 1);
647               if (DBG_CIPHER)
648                 {
649                   log_debug ("checking g:");
650                   gcry_mpi_dump (g);
651                   log_printf ("\n");
652                 }
653               else
654                 progress('^');
655               for (i = 0; i < n + 2; i++)
656                 {
657                   mpi_fdiv_q (tmp, pmin1, factors[i]);
658                   /* No mpi_pow(), but it is okay to use this with mod
659                      prime.  */
660                   gcry_mpi_powm (b, g, tmp, prime);
661                   if (! mpi_cmp_ui (b, 1))
662                     break;
663                 }
664               if (DBG_CIPHER)
665                 progress('\n');
666             } 
667           while (i < n + 2);
668
669           mpi_free (factors[n+1]);
670           mpi_free (tmp);
671           mpi_free (b);
672           mpi_free (pmin1);
673         }
674     }
675   
676   if (! DBG_CIPHER)
677     progress ('\n');
678
679
680  leave:
681   if (pool)
682     {
683       is_locked = !ath_mutex_lock (&primepool_lock);
684       for(i = 0; i < m; i++)
685         {
686           if (pool[i])
687             {
688               for (j=0; j < n; j++)
689                 if (pool_in_use[j] == i)
690                   break;
691               if (j == n && is_locked)
692                 {
693                   /* This pooled subprime has not been used. */
694                   save_pool_prime (pool[i], poolrandomlevel);
695                 }
696               else
697                 mpi_free (pool[i]);
698             }
699         }
700       if (is_locked && ath_mutex_unlock (&primepool_lock))
701         err = GPG_ERR_INTERNAL;
702       is_locked = 0;
703       gcry_free (pool);
704     }
705   gcry_free (pool_in_use);
706   if (factors)
707     gcry_free (factors);  /* Factors are shallow copies.  */
708   if (perms)
709     gcry_free (perms);
710
711   mpi_free (val_2);
712   mpi_free (q);
713   mpi_free (q_factor);
714
715   if (! err)
716     {
717       *prime_generated = prime;
718       if (ret_factors)
719         *ret_factors = factors_new;
720     }
721   else
722     {
723       if (factors_new)
724         {
725           for (i = 0; factors_new[i]; i++)
726             mpi_free (factors_new[i]);
727           gcry_free (factors_new);
728         }
729       mpi_free (prime);
730     }
731
732   return err;
733 }
734
735
736 /* Generate a prime used for discrete logarithm algorithms; i.e. this
737    prime will be public and no strong random is required.  */
738 gcry_mpi_t
739 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
740                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
741 {
742   gcry_err_code_t err = GPG_ERR_NO_ERROR;
743   gcry_mpi_t prime = NULL;
744   
745   err = prime_generate_internal ((mode == 1), &prime, pbits, qbits, g,
746                                  ret_factors, GCRY_WEAK_RANDOM, 0, 0,
747                                  NULL, NULL);
748
749   return prime;
750 }
751
752
753 static gcry_mpi_t
754 gen_prime (unsigned int nbits, int secret, int randomlevel, 
755            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
756 {
757   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
758   int i;
759   unsigned int x, step;
760   unsigned int count1, count2;
761   int *mods;
762   
763 /*   if (  DBG_CIPHER ) */
764 /*     log_debug ("generate a prime of %u bits ", nbits ); */
765
766   if (nbits < 16)
767     log_fatal ("can't generate a prime with less than %d bits\n", 16);
768
769   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
770   /* Make nbits fit into gcry_mpi_t implementation. */
771   val_2  = mpi_alloc_set_ui( 2 );
772   val_3 = mpi_alloc_set_ui( 3);
773   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
774   result = mpi_alloc_like( prime );
775   pminus1= mpi_alloc_like( prime );
776   ptest  = mpi_alloc_like( prime );
777   count1 = count2 = 0;
778   for (;;)
779     {  /* try forvever */
780       int dotcount=0;
781       
782       /* generate a random number */
783       gcry_mpi_randomize( prime, nbits, randomlevel );
784       
785       /* Set high order bit to 1, set low order bit to 1.  If we are
786          generating a secret prime we are most probably doing that
787          for RSA, to make sure that the modulus does have the
788          requested key size we set the 2 high order bits. */
789       mpi_set_highbit (prime, nbits-1);
790       if (secret)
791         mpi_set_bit (prime, nbits-2);
792       mpi_set_bit(prime, 0);
793       
794       /* Calculate all remainders. */
795       for (i=0; (x = small_prime_numbers[i]); i++ )
796         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
797       
798       /* Now try some primes starting with prime. */
799       for(step=0; step < 20000; step += 2 ) 
800         {
801           /* Check against all the small primes we have in mods. */
802           count1++;
803           for (i=0; (x = small_prime_numbers[i]); i++ ) 
804             {
805               while ( mods[i] + step >= x )
806                 mods[i] -= x;
807               if ( !(mods[i] + step) )
808                 break;
809             }
810           if ( x )
811             continue;   /* Found a multiple of an already known prime. */
812           
813           mpi_add_ui( ptest, prime, step );
814
815           /* Do a fast Fermat test now. */
816           count2++;
817           mpi_sub_ui( pminus1, ptest, 1);
818           gcry_mpi_powm( result, val_2, pminus1, ptest );
819           if ( !mpi_cmp_ui( result, 1 ) )
820             { 
821               /* Not composite, perform stronger tests */
822               if (is_prime(ptest, 5, &count2 ))
823                 {
824                   if (!mpi_test_bit( ptest, nbits-1-secret ))
825                     {
826                       progress('\n');
827                       log_debug ("overflow in prime generation\n");
828                       break; /* Stop loop, continue with a new prime. */
829                     }
830
831                   if (extra_check && extra_check (extra_check_arg, ptest))
832                     { 
833                       /* The extra check told us that this prime is
834                          not of the caller's taste. */
835                       progress ('/');
836                     }
837                   else
838                     { 
839                       /* Got it. */
840                       mpi_free(val_2);
841                       mpi_free(val_3);
842                       mpi_free(result);
843                       mpi_free(pminus1);
844                       mpi_free(prime);
845                       gcry_free(mods);
846                       return ptest; 
847                     }
848                 }
849             }
850           if (++dotcount == 10 )
851             {
852               progress('.');
853               dotcount = 0;
854             }
855         }
856       progress(':'); /* restart with a new random value */
857     }
858 }
859
860 /****************
861  * Returns: true if this may be a prime
862  * RM_ROUNDS gives the number of Rabin-Miller tests to run.
863  */
864 static int
865 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
866              gcry_prime_check_func_t cb_func, void *cb_arg)
867 {
868   int i;
869   unsigned int x;
870   unsigned int count=0;
871
872   /* Check against small primes. */
873   for (i=0; (x = small_prime_numbers[i]); i++ )
874     {
875       if ( mpi_divisible_ui( prime, x ) )
876         return 0;
877     }
878
879   /* A quick Fermat test. */
880   {
881     gcry_mpi_t result = mpi_alloc_like( prime );
882     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
883     mpi_sub_ui( pminus1, prime, 1);
884     gcry_mpi_powm( result, val_2, pminus1, prime );
885     mpi_free( pminus1 );
886     if ( mpi_cmp_ui( result, 1 ) )
887       { 
888         /* Is composite. */
889         mpi_free( result );
890         progress('.');
891         return 0;
892       }
893     mpi_free( result );
894   }
895
896   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
897     {
898       /* Perform stronger tests. */
899       if ( is_prime( prime, rm_rounds, &count ) )
900         {
901           if (!cb_func
902               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
903             return 1; /* Probably a prime. */
904         }
905     }
906   progress('.');
907   return 0;
908 }
909
910
911 /*
912  * Return true if n is probably a prime
913  */
914 static int
915 is_prime (gcry_mpi_t n, int steps, unsigned int *count)
916 {
917   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
918   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
919   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
920   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
921   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
922   gcry_mpi_t q;
923   unsigned i, j, k;
924   int rc = 0;
925   unsigned nbits = mpi_get_nbits( n );
926
927   if (steps < 5) /* Make sure that we do at least 5 rounds. */
928     steps = 5; 
929
930   mpi_sub_ui( nminus1, n, 1 );
931
932   /* Find q and k, so that n = 1 + 2^k * q . */
933   q = mpi_copy ( nminus1 );
934   k = mpi_trailing_zeros ( q );
935   mpi_tdiv_q_2exp (q, q, k);
936
937   for (i=0 ; i < steps; i++ )
938     {
939       ++*count;
940       if( !i )
941         {
942           mpi_set_ui( x, 2 );
943         }
944       else
945         {
946           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
947
948           /* Make sure that the number is smaller than the prime and
949              keep the randomness of the high bit. */
950           if ( mpi_test_bit ( x, nbits-2) )
951             {
952               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
953             }
954           else
955             {
956               mpi_set_highbit( x, nbits-2 );
957               mpi_clear_bit( x, nbits-2 );
958             }
959           gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
960         }
961       gcry_mpi_powm ( y, x, q, n);
962       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
963         {
964           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
965             {
966               gcry_mpi_powm(y, y, a2, n);
967               if( !mpi_cmp_ui( y, 1 ) )
968                 goto leave; /* Not a prime. */
969             }
970           if (mpi_cmp( y, nminus1 ) )
971             goto leave; /* Not a prime. */
972         }
973       progress('+');
974     }
975   rc = 1; /* May be a prime. */
976
977  leave:
978   mpi_free( x );
979   mpi_free( y );
980   mpi_free( z );
981   mpi_free( nminus1 );
982   mpi_free( q );
983   mpi_free( a2 );
984
985   return rc;
986 }
987
988
989 /* Given ARRAY of size N with M elements set to true produce a
990    modified array with the next permutation of M elements.  Note, that
991    ARRAY is used in a one-bit-per-byte approach.  To detected the last
992    permutation it is useful to intialize the array with the first M
993    element set to true and use this test:
994        m_out_of_n (array, m, n);
995        for (i = j = 0; i < n && j < m; i++)
996          if (array[i])
997            j++;
998        if (j == m)
999          goto ready;
1000      
1001    This code is based on the algorithm 452 from the "Collected
1002    Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
1003 */
1004 static void
1005 m_out_of_n ( char *array, int m, int n )
1006 {
1007   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
1008
1009   if( !m || m >= n )
1010     return;
1011
1012   /* Need to handle this simple case separately. */
1013   if( m == 1 )
1014     { 
1015       for (i=0; i < n; i++ )
1016         {
1017           if ( array[i] )
1018             {
1019               array[i++] = 0;
1020               if( i >= n )
1021                 i = 0;
1022               array[i] = 1;
1023               return;
1024             }
1025         }
1026       BUG();
1027     }
1028
1029
1030   for (j=1; j < n; j++ )
1031     {
1032       if ( array[n-1] == array[n-j-1])
1033         continue;
1034       j1 = j;
1035       break;
1036     }
1037
1038   if ( (m & 1) )
1039     {
1040       /* M is odd. */
1041       if( array[n-1] )
1042         {
1043           if( j1 & 1 )
1044             {
1045               k1 = n - j1;
1046               k2 = k1+2;
1047               if( k2 > n )
1048                 k2 = n;
1049               goto leave;
1050             }
1051           goto scan;
1052         }
1053       k2 = n - j1 - 1;
1054       if( k2 == 0 )
1055         {
1056           k1 = i;
1057           k2 = n - j1;
1058         }
1059       else if( array[k2] && array[k2-1] )
1060         k1 = n;
1061       else
1062         k1 = k2 + 1;
1063     }
1064   else 
1065     {
1066       /* M is even. */
1067       if( !array[n-1] )
1068         {
1069           k1 = n - j1;
1070           k2 = k1 + 1;
1071           goto leave;
1072         }
1073         
1074       if( !(j1 & 1) )
1075         {
1076           k1 = n - j1;
1077           k2 = k1+2;
1078           if( k2 > n )
1079             k2 = n;
1080           goto leave;
1081         }
1082     scan:
1083       jp = n - j1 - 1;
1084       for (i=1; i <= jp; i++ ) 
1085         {
1086           i1 = jp + 2 - i;
1087           if( array[i1-1]  )
1088             {
1089               if( array[i1-2] )
1090                 {
1091                   k1 = i1 - 1;
1092                   k2 = n - j1;
1093                 }
1094               else
1095                 {
1096                   k1 = i1 - 1;
1097                   k2 = n + 1 - j1;
1098                 }
1099               goto leave;
1100             }
1101         }
1102       k1 = 1;
1103       k2 = n + 1 - m;
1104     }
1105  leave:
1106   /* Now complement the two selected bits. */
1107   array[k1-1] = !array[k1-1];
1108   array[k2-1] = !array[k2-1];
1109 }
1110
1111
1112 /* Generate a new prime number of PRIME_BITS bits and store it in
1113    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
1114    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
1115    non-zero, allocate a new, NULL-terminated array holding the prime
1116    factors and store it in FACTORS.  FLAGS might be used to influence
1117    the prime number generation process.  */
1118 gcry_error_t
1119 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1120                      unsigned int factor_bits, gcry_mpi_t **factors,
1121                      gcry_prime_check_func_t cb_func, void *cb_arg,
1122                      gcry_random_level_t random_level,
1123                      unsigned int flags)
1124 {
1125   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1126   gcry_mpi_t *factors_generated = NULL;
1127   gcry_mpi_t prime_generated = NULL;
1128   unsigned int mode = 0;
1129
1130   if (!prime)
1131     return gpg_error (GPG_ERR_INV_ARG);
1132   *prime = NULL; 
1133
1134   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1135     mode = 1;
1136
1137   /* Generate.  */
1138   err = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1139                                  factor_bits, NULL,
1140                                  factors? &factors_generated : NULL,
1141                                  random_level, flags, 1,
1142                                  cb_func, cb_arg);
1143
1144   if (! err)
1145     if (cb_func)
1146       {
1147         /* Additional check. */
1148         if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1149           {
1150             /* Failed, deallocate resources.  */
1151             unsigned int i;
1152
1153             mpi_free (prime_generated);
1154             if (factors)
1155               {
1156                 for (i = 0; factors_generated[i]; i++)
1157                   mpi_free (factors_generated[i]);
1158                 gcry_free (factors_generated);
1159               }
1160             err = GPG_ERR_GENERAL; 
1161           }
1162       }
1163
1164   if (! err)
1165     {
1166       if (factors)
1167         *factors = factors_generated;
1168       *prime = prime_generated;
1169     }
1170
1171   return gcry_error (err);
1172 }
1173
1174 /* Check wether the number X is prime.  */
1175 gcry_error_t
1176 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1177 {
1178   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1179   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
1180
1181   (void)flags;
1182
1183   /* We use 64 rounds because the prime we are going to test is not
1184      guaranteed to be a random one. */
1185   if (! check_prime (x, val_2, 64, NULL, NULL))
1186     err = GPG_ERR_NO_PRIME;
1187
1188   mpi_free (val_2);
1189
1190   return gcry_error (err);
1191 }
1192
1193 /* Find a generator for PRIME where the factorization of (prime-1) is
1194    in the NULL terminated array FACTORS. Return the generator as a
1195    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1196    atart for the search. Returns 0 on success.*/
1197 gcry_error_t
1198 gcry_prime_group_generator (gcry_mpi_t *r_g,
1199                             gcry_mpi_t prime, gcry_mpi_t *factors,
1200                             gcry_mpi_t start_g)
1201 {
1202   gcry_mpi_t tmp = gcry_mpi_new (0);
1203   gcry_mpi_t b = gcry_mpi_new (0);
1204   gcry_mpi_t pmin1 = gcry_mpi_new (0);
1205   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
1206   int first = 1;
1207   int i, n;
1208
1209   if (!factors || !r_g || !prime)
1210     return gpg_error (GPG_ERR_INV_ARG);
1211   *r_g = NULL; 
1212
1213   for (n=0; factors[n]; n++)
1214     ;
1215   if (n < 2)
1216     return gpg_error (GPG_ERR_INV_ARG);
1217
1218   /* Extra sanity check - usually disabled. */  
1219 /*   mpi_set (tmp, factors[0]); */
1220 /*   for(i = 1; i < n; i++) */
1221 /*     mpi_mul (tmp, tmp, factors[i]); */
1222 /*   mpi_add_ui (tmp, tmp, 1); */
1223 /*   if (mpi_cmp (prime, tmp)) */
1224 /*     return gpg_error (GPG_ERR_INV_ARG); */
1225   
1226   gcry_mpi_sub_ui (pmin1, prime, 1);      
1227   do         
1228     {
1229       if (first)
1230         first = 0;
1231       else
1232         gcry_mpi_add_ui (g, g, 1);
1233       
1234       if (DBG_CIPHER)
1235         {
1236           log_debug ("checking g:");
1237           gcry_mpi_dump (g);
1238           log_debug ("\n");
1239         }
1240       else
1241         progress('^');
1242       
1243       for (i = 0; i < n; i++)
1244         {
1245           mpi_fdiv_q (tmp, pmin1, factors[i]);
1246           gcry_mpi_powm (b, g, tmp, prime);
1247           if (! mpi_cmp_ui (b, 1))
1248             break;
1249         }
1250       if (DBG_CIPHER)
1251         progress('\n');
1252     }
1253   while (i < n);
1254   
1255   gcry_mpi_release (tmp);
1256   gcry_mpi_release (b); 
1257   gcry_mpi_release (pmin1); 
1258   *r_g = g; 
1259
1260   return 0; 
1261 }
1262
1263 /* Convenience function to release the factors array. */
1264 void
1265 gcry_prime_release_factors (gcry_mpi_t *factors)
1266 {
1267   if (factors)
1268     {
1269       int i;
1270       
1271       for (i=0; factors[i]; i++)
1272         mpi_free (factors[i]);
1273       gcry_free (factors);
1274     }
1275 }