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