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