See ChangeLog. There are still problems in ac.c.
[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 <assert.h>
28 #include <errno.h>
29
30 #include "g10lib.h"
31 #include "mpi.h"
32 #include "cipher.h"
33 #include "ath.h"
34
35 static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, 
36                              int (*extra_check)(void *, gcry_mpi_t),
37                              void *extra_check_arg);
38 static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
39                         gcry_prime_check_func_t cb_func, void *cb_arg );
40 static int is_prime (gcry_mpi_t n, int steps, unsigned int *count);
41 static void m_out_of_n( char *array, int m, int n );
42
43 static void (*progress_cb) (void *,const char*,int,int, int );
44 static void *progress_cb_data;
45
46 /* Note: 2 is not included because it can be tested more easily by
47    looking at bit 0. The last entry in this list is marked by a zero */
48 static ushort small_prime_numbers[] = {
49     3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
50     47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
51     103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
52     157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
53     211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
54     269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
55     331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
56     389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
57     449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
58     509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
59     587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
60     643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
61     709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
62     773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
63     853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
64     919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
65     991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
66     1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
67     1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
68     1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
69     1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
70     1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
71     1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
72     1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
73     1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
74     1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
75     1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
76     1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
77     1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
78     1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
79     1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
80     1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
81     1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
82     1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
83     2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
84     2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
85     2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
86     2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
87     2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
88     2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
89     2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
90     2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
91     2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
92     2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
93     2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
94     2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
95     2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
96     2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
97     2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
98     3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
99     3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
100     3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
101     3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
102     3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
103     3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
104     3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
105     3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
106     3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
107     3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
108     3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
109     3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
110     3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
111     3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
112     3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
113     4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
114     4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
115     4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
116     4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
117     4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
118     4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
119     4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
120     4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
121     4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
122     4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
123     4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
124     4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
125     4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
126     4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
127     4957, 4967, 4969, 4973, 4987, 4993, 4999,
128     0
129 };
130 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
131
132
133 \f
134 /* An object and a list to build up a global pool of primes.  See
135    save_pool_prime and get_pool_prime. */
136 struct primepool_s 
137 {
138   struct primepool_s *next;
139   gcry_mpi_t prime;      /* If this is NULL the entry is not used. */
140   unsigned int nbits;
141   gcry_random_level_t randomlevel;
142 };
143 struct primepool_s *primepool;
144 /* Mutex used to protect access to the primepool.  */
145 static ath_mutex_t primepool_lock = ATH_MUTEX_INITIALIZER;
146
147
148
149 /* Save PRIME which has been generated at RANDOMLEVEL for later
150    use. Needs to be called while primepool_lock is being hold.  Note
151    that PRIME should be considered released after calling this
152    function. */
153 static void
154 save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel)
155 {
156   struct primepool_s *item, *item2;
157   size_t n;
158
159   for (n=0, item = primepool; item; item = item->next, n++)
160     if (!item->prime)
161       break;
162   if (!item && n > 100)
163     {
164       /* Remove some of the entries.  Our strategy is removing
165          the last third from the list. */
166       int i;
167       
168       for (i=0, item2 = primepool; item2; item2 = item2->next)
169         {
170           if (i >= n/3*2)
171             {
172               gcry_mpi_release (item2->prime);
173               item2->prime = NULL;
174               if (!item)
175                 item = item2;
176             }
177         }
178     }
179   if (!item)
180     {
181       item = gcry_calloc (1, sizeof *item);
182       if (!item)
183         {
184           /* Out of memory.  Silently giving up. */
185           gcry_mpi_release (prime);
186           return; 
187         }
188       item->next = primepool;
189       primepool = item;
190     }
191   item->prime = prime;
192   item->nbits = mpi_get_nbits (prime);
193   item->randomlevel = randomlevel;
194 }
195
196
197 /* Return a prime for the prime pool or NULL if none has been found.
198    The prime needs to match NBITS and randomlevel. This function needs
199    to be called why the primepool_look is being hold. */
200 static gcry_mpi_t
201 get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel)
202 {
203   struct primepool_s *item;
204
205   for (item = primepool; item; item = item->next)
206     if (item->prime
207         && item->nbits == nbits && item->randomlevel == randomlevel)
208       {
209         gcry_mpi_t prime = item->prime;
210         item->prime = NULL;
211         assert (nbits == mpi_get_nbits (prime));
212         return prime;
213       }
214   return NULL;
215 }
216
217
218
219
220
221 \f
222 void
223 _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
224                                    void *cb_data )
225 {
226   progress_cb = cb;
227   progress_cb_data = cb_data;
228 }
229
230
231 static void
232 progress( int c )
233 {
234   if ( progress_cb )
235     progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
236 }
237
238
239 /****************
240  * Generate a prime number (stored in secure memory)
241  */
242 gcry_mpi_t
243 _gcry_generate_secret_prime (unsigned int nbits,
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, 2, extra_check, extra_check_arg);
250   progress('\n');
251   return prime;
252 }
253
254 gcry_mpi_t
255 _gcry_generate_public_prime( unsigned int nbits,
256                              int (*extra_check)(void*, gcry_mpi_t),
257                              void *extra_check_arg)
258 {
259   gcry_mpi_t prime;
260
261   prime = gen_prime( nbits, 0, 2, extra_check, extra_check_arg );
262   progress('\n');
263   return prime;
264 }
265
266
267 /* Core prime generation function.  The algorithm used to generate
268    practically save primes is due to Lim and Lee as described in the
269    CRYPTO '97 proceedings (ISBN3540633847) page 260.
270
271    NEED_Q_FACTOR: If true make sure that at least one factor is of
272                   size qbits.  This is for example required for DSA.
273    PRIME_GENERATED: Adresss of a variable where the resulting prime
274                     number will be stored.
275    PBITS: Requested size of the prime number.  At least 48.
276    QBITS: One factor of the prime needs to be of this size.  Maybe 0
277           if this is not required.  See also MODE.
278    G: If not NULL an MPI which will receive a generator for the prime
279       for use with Elgamal.
280    RET_FACTORS: if not NULL, an array with all factors are stored at
281                 that address.
282    ALL_FACTORS: If set to true all factors of prime-1 are returned.
283    RANDOMLEVEL:  How strong should the random numers be.
284    FLAGS: Prime generation bit flags. Currently supported:
285           GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret.
286    CB_FUNC, CB_ARG:  Callback to be used for extra checks.
287
288  */
289 static gcry_err_code_t
290 prime_generate_internal (int need_q_factor,
291                          gcry_mpi_t *prime_generated, unsigned int pbits,
292                          unsigned int qbits, gcry_mpi_t g,
293                          gcry_mpi_t **ret_factors,
294                          gcry_random_level_t randomlevel, unsigned int flags,
295                          int all_factors,
296                          gcry_prime_check_func_t cb_func, void *cb_arg)
297 {
298   gcry_err_code_t err = 0;
299   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
300                                      caller.  */
301   gcry_mpi_t *factors = NULL;   /* Current factors.  */
302   gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */
303   gcry_mpi_t *pool = NULL;      /* Pool of primes.  */
304   int *pool_in_use = NULL;      /* Array with currently used POOL elements. */
305   unsigned char *perms = NULL;  /* Permutations of POOL.  */
306   gcry_mpi_t q_factor = NULL;   /* Used if QBITS is non-zero.  */
307   unsigned int fbits = 0;       /* Length of prime factors.  */
308   unsigned int n = 0;           /* Number of factors.  */
309   unsigned int m = 0;           /* Number of primes in pool.  */
310   gcry_mpi_t q = NULL;          /* First prime factor.  */
311   gcry_mpi_t prime = NULL;      /* Prime candidate.  */
312   unsigned int nprime = 0;      /* Bits of PRIME.  */
313   unsigned int req_qbits;       /* The original QBITS value.  */
314   gcry_mpi_t val_2;             /* For check_prime().  */
315   int is_locked = 0;            /* Flag to help unlocking the primepool. */
316   unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
317   unsigned int count1 = 0, count2 = 0;
318   unsigned int i = 0, j = 0;
319
320   if (pbits < 48)
321     return GPG_ERR_INV_ARG;
322
323   /* We won't use a too strong random elvel for the pooled subprimes. */
324   poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM?
325                      GCRY_STRONG_RANDOM : randomlevel);
326
327
328   /* If QBITS is not given, assume a reasonable value. */
329   if (!qbits)
330     qbits = pbits / 3;
331
332   req_qbits = qbits;
333
334   /* Find number of needed prime factors N.  */
335   for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++)
336     ;
337   n--;
338
339   val_2 = mpi_alloc_set_ui (2);
340
341   if ((! n) || ((need_q_factor) && (n < 2)))
342     {
343       err = GPG_ERR_INV_ARG;
344       goto leave;
345     }
346
347   if (need_q_factor)
348     {
349       n--;  /* Need one factor less because we want a specific Q-FACTOR. */
350       fbits = (pbits - 2 * req_qbits -1) / n;
351       qbits =  pbits - req_qbits - n * fbits;
352     }
353   else
354     {
355       fbits = (pbits - req_qbits -1) / n;
356       qbits = pbits - n * fbits;
357     }
358   
359   if (DBG_CIPHER)
360     log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
361                pbits, req_qbits, qbits, fbits, n);
362
363   /* Allocate an integer to old the new prime. */
364   prime = gcry_mpi_new (pbits);
365
366   /* Generate first prime factor.  */
367   q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
368
369   /* Generate a specific Q-Factor if requested. */
370   if (need_q_factor)
371     q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
372   
373   /* Allocate an array to hold all factors + 2 for later usage.  */
374   factors = gcry_calloc (n + 2, sizeof (*factors));
375   if (!factors)
376     {
377       err = gpg_err_code_from_errno (errno);
378       goto leave;
379     }
380
381   /* Allocate an array to track pool usage. */
382   pool_in_use = gcry_malloc (n * sizeof *pool_in_use);
383   if (!pool_in_use)
384     {
385       err = gpg_err_code_from_errno (errno);
386       goto leave;
387     }
388   for (i=0; i < n; i++)
389     pool_in_use[i] = -1;
390       
391   /* Make a pool of 3n+5 primes (this is an arbitrary value).  We
392      require at least 30 primes for are useful selection process. 
393      
394      FIXME: We need to do some reseacrh on the best formula for sizing
395      the pool.
396   */
397   m = n * 3 + 5;
398   if (need_q_factor) /* Need some more in this case. */
399     m += 5;
400   if (m < 30)
401     m = 30;
402   pool = gcry_calloc (m , sizeof (*pool));
403   if (! pool)
404     {
405       err = gpg_err_code_from_errno (errno);
406       goto leave;
407     }
408
409   /* Permutate over the pool of primes until we find a prime of the
410      requested length.  */
411   do
412     {
413     next_try:
414       for (i=0; i < n; i++)
415         pool_in_use[i] = -1;
416
417       if (!perms)
418         {
419           /* Allocate new primes.  This is done right at the beginning
420              of the loop and if we have later run out of primes. */
421           for (i = 0; i < m; i++)
422             {
423               mpi_free (pool[i]);
424               pool[i] = NULL;
425             }
426
427           /* Init m_out_of_n().  */
428           perms = gcry_calloc (1, m);
429           if (!perms)
430             {
431               err = gpg_err_code_from_errno (errno);
432               goto leave;
433             }
434
435           if (ath_mutex_lock (&primepool_lock))
436             {
437               err = GPG_ERR_INTERNAL;
438               goto leave;
439             }
440           is_locked = 1;
441           for (i = 0; i < n; i++)
442             {
443               perms[i] = 1; 
444               /* At a maximum we use strong random for the factors.
445                  This saves us a lot of entropy. Given that Q and
446                  possible Q-factor are also used in the final prime
447                  this should be acceptable.  We also don't allocate in
448                  secure memory to save on that scare resource too.  If
449                  Q has been allocated in secure memory, the final
450                  prime will be saved there anyway.  This is because
451                  our MPI routines take care of that.  GnuPG has worked
452                  this way ever since.  */
453               pool[i] = NULL;
454               if (is_locked)
455                 {
456                   pool[i] = get_pool_prime (fbits, poolrandomlevel);
457                   if (!pool[i])
458                     {
459                       if (ath_mutex_unlock (&primepool_lock))
460                         {
461                           err = GPG_ERR_INTERNAL;
462                           goto leave;
463                         }
464                       is_locked = 0;
465                     }
466                 }
467               if (!pool[i])
468                 pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
469               pool_in_use[i] = i;
470               factors[i] = pool[i];
471             }
472           if (is_locked && ath_mutex_unlock (&primepool_lock))
473             {
474               err = GPG_ERR_INTERNAL;
475               goto leave;
476             }
477           is_locked = 0;
478         }
479       else
480         {
481           /* Get next permutation. */
482           m_out_of_n ( (char*)perms, n, m);
483           if (ath_mutex_lock (&primepool_lock))
484             {
485               err = GPG_ERR_INTERNAL;
486               goto leave;
487             }
488           is_locked = 1;
489           for (i = j = 0; (i < m) && (j < n); i++)
490             if (perms[i])
491               {
492                 /* If the subprime has not yet beed generated do it now. */
493                 if (!pool[i] && is_locked)
494                   {
495                     pool[i] = get_pool_prime (fbits, poolrandomlevel);
496                     if (!pool[i])
497                       {
498                         if (ath_mutex_unlock (&primepool_lock))
499                           {
500                             err = GPG_ERR_INTERNAL;
501                             goto leave;
502                           }
503                         is_locked = 0;
504                       }
505                   }
506                 if (!pool[i])
507                   pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
508                 pool_in_use[j] = i;
509                 factors[j++] = pool[i];
510               }
511           if (is_locked && ath_mutex_unlock (&primepool_lock))
512             {
513               err = GPG_ERR_INTERNAL;
514               goto leave;
515             }
516           is_locked = 0;
517           if (i == n)
518             {
519               /* Ran out of permutations: Allocate new primes.  */
520               gcry_free (perms);
521               perms = NULL;
522               progress ('!');
523               goto next_try;    
524             }
525         }
526
527         /* Generate next prime candidate:
528            p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. 
529          */
530         mpi_set (prime, q);
531         mpi_mul_ui (prime, prime, 2);
532         if (need_q_factor)
533           mpi_mul (prime, prime, q_factor);
534         for(i = 0; i < n; i++)
535           mpi_mul (prime, prime, factors[i]);
536         mpi_add_ui (prime, prime, 1);
537         nprime = mpi_get_nbits (prime);
538
539         if (nprime < pbits)
540           {
541             if (++count1 > 20)
542               {
543                 count1 = 0;
544                 qbits++;
545                 progress('>');
546                 mpi_free (q);
547                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
548                 goto next_try;
549               }
550           }
551         else
552           count1 = 0;
553         
554         if (nprime > pbits)
555           {
556             if (++count2 > 20)
557               {
558                 count2 = 0;
559                 qbits--;
560                 progress('<');
561                 mpi_free (q);
562                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
563                 goto next_try;
564               }
565           }
566         else
567           count2 = 0;
568     }
569   while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
570                                               cb_func, cb_arg)));
571
572   if (DBG_CIPHER)
573     {
574       progress ('\n');
575       log_mpidump ("prime    : ", prime);
576       log_mpidump ("factor  q: ", q);
577       if (need_q_factor)
578         log_mpidump ("factor q0: ", q_factor);
579       for (i = 0; i < n; i++)
580         log_mpidump ("factor pi: ", factors[i]);
581       log_debug ("bit sizes: prime=%u, q=%u",
582                  mpi_get_nbits (prime), mpi_get_nbits (q));
583       if (need_q_factor)
584         log_debug (", q0=%u", mpi_get_nbits (q_factor));
585       for (i = 0; i < n; i++)
586         log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
587       progress('\n');
588     }
589
590   if (ret_factors)
591     {
592       /* Caller wants the factors.  */
593       factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
594       if (! factors_new)
595         {
596           err = gpg_err_code_from_errno (errno);
597           goto leave;
598         }
599
600       if (all_factors)
601         {
602           i = 0;
603           factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
604           factors_new[i++] = mpi_copy (q);
605           if (need_q_factor)
606             factors_new[i++] = mpi_copy (q_factor);
607           for(j=0; j < n; j++)
608             factors_new[i++] = mpi_copy (factors[j]);
609         }
610       else
611         {
612           i = 0;
613           if (need_q_factor)
614             {
615               factors_new[i++] = mpi_copy (q_factor);
616               for (; i <= n; i++)
617                 factors_new[i] = mpi_copy (factors[i]);
618             }
619           else
620             for (; i < n; i++ )
621               factors_new[i] = mpi_copy (factors[i]);
622         }
623     }
624   
625   if (g)
626     {
627       /* Create a generator (start with 3).  */
628       gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
629       gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
630       gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
631       
632       if (need_q_factor)
633         err = GPG_ERR_NOT_IMPLEMENTED;
634       else
635         {
636           factors[n] = q;
637           factors[n + 1] = mpi_alloc_set_ui (2);
638           mpi_sub_ui (pmin1, prime, 1);
639           mpi_set_ui (g, 2);
640           do
641             {
642               mpi_add_ui (g, g, 1);
643               if (DBG_CIPHER)
644                 {
645                   log_debug ("checking g:");
646                   gcry_mpi_dump (g);
647                   log_printf ("\n");
648                 }
649               else
650                 progress('^');
651               for (i = 0; i < n + 2; i++)
652                 {
653                   mpi_fdiv_q (tmp, pmin1, factors[i]);
654                   /* No mpi_pow(), but it is okay to use this with mod
655                      prime.  */
656                   gcry_mpi_powm (b, g, tmp, prime);
657                   if (! mpi_cmp_ui (b, 1))
658                     break;
659                 }
660               if (DBG_CIPHER)
661                 progress('\n');
662             } 
663           while (i < n + 2);
664
665           mpi_free (factors[n+1]);
666           mpi_free (tmp);
667           mpi_free (b);
668           mpi_free (pmin1);
669         }
670     }
671   
672   if (! DBG_CIPHER)
673     progress ('\n');
674
675
676  leave:
677   if (pool)
678     {
679       is_locked = !ath_mutex_lock (&primepool_lock);
680       for(i = 0; i < m; i++)
681         {
682           if (pool[i])
683             {
684               for (j=0; j < n; j++)
685                 if (pool_in_use[j] == i)
686                   break;
687               if (j == n && is_locked)
688                 {
689                   /* This pooled subprime has not been used. */
690                   save_pool_prime (pool[i], poolrandomlevel);
691                 }
692               else
693                 mpi_free (pool[i]);
694             }
695         }
696       if (is_locked && ath_mutex_unlock (&primepool_lock))
697         err = GPG_ERR_INTERNAL;
698       is_locked = 0;
699       gcry_free (pool);
700     }
701   gcry_free (pool_in_use);
702   if (factors)
703     gcry_free (factors);  /* Factors are shallow copies.  */
704   if (perms)
705     gcry_free (perms);
706
707   mpi_free (val_2);
708   mpi_free (q);
709   mpi_free (q_factor);
710
711   if (! err)
712     {
713       *prime_generated = prime;
714       if (ret_factors)
715         *ret_factors = factors_new;
716     }
717   else
718     {
719       if (factors_new)
720         {
721           for (i = 0; factors_new[i]; i++)
722             mpi_free (factors_new[i]);
723           gcry_free (factors_new);
724         }
725       mpi_free (prime);
726     }
727
728   return err;
729 }
730
731
732
733 gcry_mpi_t
734 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
735                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
736 {
737   gcry_err_code_t err = GPG_ERR_NO_ERROR;
738   gcry_mpi_t prime = NULL;
739   
740   err = prime_generate_internal ((mode == 1), &prime, pbits, qbits, g,
741                                  ret_factors, GCRY_WEAK_RANDOM, 0, 0,
742                                  NULL, NULL);
743
744   return prime;
745 }
746
747 static gcry_mpi_t
748 gen_prime (unsigned int nbits, int secret, int randomlevel, 
749            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
750 {
751   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
752   int i;
753   unsigned int x, step;
754   unsigned int count1, count2;
755   int *mods;
756   
757 /*   if (  DBG_CIPHER ) */
758 /*     log_debug ("generate a prime of %u bits ", nbits ); */
759
760   if (nbits < 16)
761     log_fatal ("can't generate a prime with less than %d bits\n", 16);
762
763   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
764   /* Make nbits fit into gcry_mpi_t implementation. */
765   val_2  = mpi_alloc_set_ui( 2 );
766   val_3 = mpi_alloc_set_ui( 3);
767   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
768   result = mpi_alloc_like( prime );
769   pminus1= mpi_alloc_like( prime );
770   ptest  = mpi_alloc_like( prime );
771   count1 = count2 = 0;
772   for (;;)
773     {  /* try forvever */
774       int dotcount=0;
775       
776       /* generate a random number */
777       gcry_mpi_randomize( prime, nbits, randomlevel );
778       
779       /* Set high order bit to 1, set low order bit to 1.  If we are
780          generating a secret prime we are most probably doing that
781          for RSA, to make sure that the modulus does have the
782          requested key size we set the 2 high order bits. */
783       mpi_set_highbit (prime, nbits-1);
784       if (secret)
785         mpi_set_bit (prime, nbits-2);
786       mpi_set_bit(prime, 0);
787       
788       /* Calculate all remainders. */
789       for (i=0; (x = small_prime_numbers[i]); i++ )
790         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
791       
792       /* Now try some primes starting with prime. */
793       for(step=0; step < 20000; step += 2 ) 
794         {
795           /* Check against all the small primes we have in mods. */
796           count1++;
797           for (i=0; (x = small_prime_numbers[i]); i++ ) 
798             {
799               while ( mods[i] + step >= x )
800                 mods[i] -= x;
801               if ( !(mods[i] + step) )
802                 break;
803             }
804           if ( x )
805             continue;   /* Found a multiple of an already known prime. */
806           
807           mpi_add_ui( ptest, prime, step );
808
809           /* Do a fast Fermat test now. */
810           count2++;
811           mpi_sub_ui( pminus1, ptest, 1);
812           gcry_mpi_powm( result, val_2, pminus1, ptest );
813           if ( !mpi_cmp_ui( result, 1 ) )
814             { 
815               /* Not composite, perform stronger tests */
816               if (is_prime(ptest, 5, &count2 ))
817                 {
818                   if (!mpi_test_bit( ptest, nbits-1-secret ))
819                     {
820                       progress('\n');
821                       log_debug ("overflow in prime generation\n");
822                       break; /* Stop loop, continue with a new prime. */
823                     }
824
825                   if (extra_check && extra_check (extra_check_arg, ptest))
826                     { 
827                       /* The extra check told us that this prime is
828                          not of the caller's taste. */
829                       progress ('/');
830                     }
831                   else
832                     { 
833                       /* Got it. */
834                       mpi_free(val_2);
835                       mpi_free(val_3);
836                       mpi_free(result);
837                       mpi_free(pminus1);
838                       mpi_free(prime);
839                       gcry_free(mods);
840                       return ptest; 
841                     }
842                 }
843             }
844           if (++dotcount == 10 )
845             {
846               progress('.');
847               dotcount = 0;
848             }
849         }
850       progress(':'); /* restart with a new random value */
851     }
852 }
853
854 /****************
855  * Returns: true if this may be a prime
856  * RM_ROUNDS gives the number of Rabin-Miller tests to run.
857  */
858 static int
859 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
860              gcry_prime_check_func_t cb_func, void *cb_arg)
861 {
862   int i;
863   unsigned int x;
864   unsigned int count=0;
865
866   /* Check against small primes. */
867   for (i=0; (x = small_prime_numbers[i]); i++ )
868     {
869       if ( mpi_divisible_ui( prime, x ) )
870         return 0;
871     }
872
873   /* A quick Fermat test. */
874   {
875     gcry_mpi_t result = mpi_alloc_like( prime );
876     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
877     mpi_sub_ui( pminus1, prime, 1);
878     gcry_mpi_powm( result, val_2, pminus1, prime );
879     mpi_free( pminus1 );
880     if ( mpi_cmp_ui( result, 1 ) )
881       { 
882         /* Is composite. */
883         mpi_free( result );
884         progress('.');
885         return 0;
886       }
887     mpi_free( result );
888   }
889
890   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
891     {
892       /* Perform stronger tests. */
893       if ( is_prime( prime, rm_rounds, &count ) )
894         {
895           if (!cb_func
896               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
897             return 1; /* Probably a prime. */
898         }
899     }
900   progress('.');
901   return 0;
902 }
903
904
905 /*
906  * Return true if n is probably a prime
907  */
908 static int
909 is_prime (gcry_mpi_t n, int steps, unsigned int *count)
910 {
911   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
912   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
913   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
914   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
915   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
916   gcry_mpi_t q;
917   unsigned i, j, k;
918   int rc = 0;
919   unsigned nbits = mpi_get_nbits( n );
920
921   if (steps < 5) /* Make sure that we do at least 5 rounds. */
922     steps = 5; 
923
924   mpi_sub_ui( nminus1, n, 1 );
925
926   /* Find q and k, so that n = 1 + 2^k * q . */
927   q = mpi_copy ( nminus1 );
928   k = mpi_trailing_zeros ( q );
929   mpi_tdiv_q_2exp (q, q, k);
930
931   for (i=0 ; i < steps; i++ )
932     {
933       ++*count;
934       if( !i )
935         {
936           mpi_set_ui( x, 2 );
937         }
938       else
939         {
940           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
941
942           /* Make sure that the number is smaller than the prime and
943              keep the randomness of the high bit. */
944           if ( mpi_test_bit ( x, nbits-2) )
945             {
946               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
947             }
948           else
949             {
950               mpi_set_highbit( x, nbits-2 );
951               mpi_clear_bit( x, nbits-2 );
952             }
953           assert ( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
954         }
955       gcry_mpi_powm ( y, x, q, n);
956       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
957         {
958           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
959             {
960               gcry_mpi_powm(y, y, a2, n);
961               if( !mpi_cmp_ui( y, 1 ) )
962                 goto leave; /* Not a prime. */
963             }
964           if (mpi_cmp( y, nminus1 ) )
965             goto leave; /* Not a prime. */
966         }
967       progress('+');
968     }
969   rc = 1; /* May be a prime. */
970
971  leave:
972   mpi_free( x );
973   mpi_free( y );
974   mpi_free( z );
975   mpi_free( nminus1 );
976   mpi_free( q );
977   mpi_free( a2 );
978
979   return rc;
980 }
981
982
983 /* Given ARRAY of size N with M elements set to true produce a
984    modified array with the next permutation of M elements.  Note, that
985    ARRAY is used in a one-bit-per-byte approach.  To detected the last
986    permutation it is useful to intialize the array with the first M
987    element set to true and use this test:
988        m_out_of_n (array, m, n);
989        for (i = j = 0; i < n && j < m; i++)
990          if (array[i])
991            j++;
992        if (j == m)
993          goto ready;
994      
995    This code is based on the algorithm 452 from the "Collected
996    Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
997 */
998 static void
999 m_out_of_n ( char *array, int m, int n )
1000 {
1001   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
1002
1003   if( !m || m >= n )
1004     return;
1005
1006   /* Need to handle this simple case separately. */
1007   if( m == 1 )
1008     { 
1009       for (i=0; i < n; i++ )
1010         {
1011           if ( array[i] )
1012             {
1013               array[i++] = 0;
1014               if( i >= n )
1015                 i = 0;
1016               array[i] = 1;
1017               return;
1018             }
1019         }
1020       BUG();
1021     }
1022
1023
1024   for (j=1; j < n; j++ )
1025     {
1026       if ( array[n-1] == array[n-j-1])
1027         continue;
1028       j1 = j;
1029       break;
1030     }
1031
1032   if ( (m & 1) )
1033     {
1034       /* M is odd. */
1035       if( array[n-1] )
1036         {
1037           if( j1 & 1 )
1038             {
1039               k1 = n - j1;
1040               k2 = k1+2;
1041               if( k2 > n )
1042                 k2 = n;
1043               goto leave;
1044             }
1045           goto scan;
1046         }
1047       k2 = n - j1 - 1;
1048       if( k2 == 0 )
1049         {
1050           k1 = i;
1051           k2 = n - j1;
1052         }
1053       else if( array[k2] && array[k2-1] )
1054         k1 = n;
1055       else
1056         k1 = k2 + 1;
1057     }
1058   else 
1059     {
1060       /* M is even. */
1061       if( !array[n-1] )
1062         {
1063           k1 = n - j1;
1064           k2 = k1 + 1;
1065           goto leave;
1066         }
1067         
1068       if( !(j1 & 1) )
1069         {
1070           k1 = n - j1;
1071           k2 = k1+2;
1072           if( k2 > n )
1073             k2 = n;
1074           goto leave;
1075         }
1076     scan:
1077       jp = n - j1 - 1;
1078       for (i=1; i <= jp; i++ ) 
1079         {
1080           i1 = jp + 2 - i;
1081           if( array[i1-1]  )
1082             {
1083               if( array[i1-2] )
1084                 {
1085                   k1 = i1 - 1;
1086                   k2 = n - j1;
1087                 }
1088               else
1089                 {
1090                   k1 = i1 - 1;
1091                   k2 = n + 1 - j1;
1092                 }
1093               goto leave;
1094             }
1095         }
1096       k1 = 1;
1097       k2 = n + 1 - m;
1098     }
1099  leave:
1100   /* Now complement the two selected bits. */
1101   array[k1-1] = !array[k1-1];
1102   array[k2-1] = !array[k2-1];
1103 }
1104
1105
1106 /* Generate a new prime number of PRIME_BITS bits and store it in
1107    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
1108    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
1109    non-zero, allocate a new, NULL-terminated array holding the prime
1110    factors and store it in FACTORS.  FLAGS might be used to influence
1111    the prime number generation process.  */
1112 gcry_error_t
1113 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1114                      unsigned int factor_bits, gcry_mpi_t **factors,
1115                      gcry_prime_check_func_t cb_func, void *cb_arg,
1116                      gcry_random_level_t random_level,
1117                      unsigned int flags)
1118 {
1119   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1120   gcry_mpi_t *factors_generated = NULL;
1121   gcry_mpi_t prime_generated = NULL;
1122   unsigned int mode = 0;
1123
1124   if (!prime)
1125     return gpg_error (GPG_ERR_INV_ARG);
1126   *prime = NULL; 
1127
1128   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1129     mode = 1;
1130
1131   /* Generate.  */
1132   err = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1133                                  factor_bits, NULL,
1134                                  factors? &factors_generated : NULL,
1135                                  random_level, flags, 1,
1136                                  cb_func, cb_arg);
1137
1138   if (! err)
1139     if (cb_func)
1140       {
1141         /* Additional check. */
1142         if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1143           {
1144             /* Failed, deallocate resources.  */
1145             unsigned int i;
1146
1147             mpi_free (prime_generated);
1148             if (factors)
1149               {
1150                 for (i = 0; factors_generated[i]; i++)
1151                   mpi_free (factors_generated[i]);
1152                 gcry_free (factors_generated);
1153               }
1154             err = GPG_ERR_GENERAL; 
1155           }
1156       }
1157
1158   if (! err)
1159     {
1160       if (factors)
1161         *factors = factors_generated;
1162       *prime = prime_generated;
1163     }
1164
1165   return gcry_error (err);
1166 }
1167
1168 /* Check wether the number X is prime.  */
1169 gcry_error_t
1170 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1171 {
1172   gcry_err_code_t err = GPG_ERR_NO_ERROR;
1173   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
1174
1175   /* We use 64 rounds because the prime we are going to test is not
1176      guaranteed to be a random one. */
1177   if (! check_prime (x, val_2, 64, NULL, NULL))
1178     err = GPG_ERR_NO_PRIME;
1179
1180   mpi_free (val_2);
1181
1182   return gcry_error (err);
1183 }
1184
1185 /* Find a generator for PRIME where the factorization of (prime-1) is
1186    in the NULL terminated array FACTORS. Return the generator as a
1187    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1188    atart for the search. Returns 0 on success.*/
1189 gcry_error_t
1190 gcry_prime_group_generator (gcry_mpi_t *r_g,
1191                             gcry_mpi_t prime, gcry_mpi_t *factors,
1192                             gcry_mpi_t start_g)
1193 {
1194   gcry_mpi_t tmp = gcry_mpi_new (0);
1195   gcry_mpi_t b = gcry_mpi_new (0);
1196   gcry_mpi_t pmin1 = gcry_mpi_new (0);
1197   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
1198   int first = 1;
1199   int i, n;
1200
1201   if (!factors || !r_g || !prime)
1202     return gpg_error (GPG_ERR_INV_ARG);
1203   *r_g = NULL; 
1204
1205   for (n=0; factors[n]; n++)
1206     ;
1207   if (n < 2)
1208     return gpg_error (GPG_ERR_INV_ARG);
1209
1210   /* Extra sanity check - usually disabled. */  
1211 /*   mpi_set (tmp, factors[0]); */
1212 /*   for(i = 1; i < n; i++) */
1213 /*     mpi_mul (tmp, tmp, factors[i]); */
1214 /*   mpi_add_ui (tmp, tmp, 1); */
1215 /*   if (mpi_cmp (prime, tmp)) */
1216 /*     return gpg_error (GPG_ERR_INV_ARG); */
1217   
1218   gcry_mpi_sub_ui (pmin1, prime, 1);      
1219   do         
1220     {
1221       if (first)
1222         first = 0;
1223       else
1224         gcry_mpi_add_ui (g, g, 1);
1225       
1226       if (DBG_CIPHER)
1227         {
1228           log_debug ("checking g:");
1229           gcry_mpi_dump (g);
1230           log_debug ("\n");
1231         }
1232       else
1233         progress('^');
1234       
1235       for (i = 0; i < n; i++)
1236         {
1237           mpi_fdiv_q (tmp, pmin1, factors[i]);
1238           gcry_mpi_powm (b, g, tmp, prime);
1239           if (! mpi_cmp_ui (b, 1))
1240             break;
1241         }
1242       if (DBG_CIPHER)
1243         progress('\n');
1244     }
1245   while (i < n);
1246   
1247   gcry_mpi_release (tmp);
1248   gcry_mpi_release (b); 
1249   gcry_mpi_release (pmin1); 
1250   *r_g = g; 
1251
1252   return 0; 
1253 }
1254
1255 /* Convenience function to release the factors array. */
1256 void
1257 gcry_prime_release_factors (gcry_mpi_t *factors)
1258 {
1259   if (factors)
1260     {
1261       int i;
1262       
1263       for (i=0; factors[i]; i++)
1264         mpi_free (factors[i]);
1265       gcry_free (factors);
1266     }
1267 }