(wipememory, wipememory2): New; taken from gnupg.
[libgcrypt.git] / cipher / primegen.c
1 /* primegen.c - prime number generator
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser general Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  *
20  * ***********************************************************************
21  * The algorithm used to generate practically save primes is due to
22  * Lim and Lee as described in the CRYPTO '97 proceedings (ISBN3540633847)
23  * page 260.
24  */
25
26 #include <config.h>
27
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <assert.h>
32 #include <errno.h>
33
34 #include "g10lib.h"
35 #include "mpi.h"
36 #include "cipher.h"
37
38 static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, 
39                              int (*extra_check)(void *, gcry_mpi_t),
40                              void *extra_check_arg);
41 static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2 );
42 static int is_prime( gcry_mpi_t n, int steps, int *count );
43 static void m_out_of_n( char *array, int m, int n );
44
45 static void (*progress_cb) (void *,const char*,int,int, int );
46 static void *progress_cb_data;
47
48 /* Note: 2 is not included because it can be tested more easily by
49    looking at bit 0. The last entry in this list is marked by a zero */
50 static ushort small_prime_numbers[] = {
51     3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
52     47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
53     103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
54     157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
55     211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
56     269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
57     331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
58     389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
59     449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
60     509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
61     587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
62     643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
63     709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
64     773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
65     853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
66     919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
67     991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
68     1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
69     1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
70     1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
71     1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
72     1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
73     1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
74     1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
75     1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
76     1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
77     1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
78     1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
79     1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
80     1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
81     1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
82     1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
83     1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
84     1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
85     2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
86     2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
87     2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
88     2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
89     2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
90     2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
91     2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
92     2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
93     2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
94     2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
95     2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
96     2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
97     2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
98     2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
99     2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
100     3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
101     3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
102     3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
103     3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
104     3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
105     3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
106     3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
107     3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
108     3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
109     3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
110     3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
111     3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
112     3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
113     3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
114     3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
115     4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
116     4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
117     4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
118     4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
119     4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
120     4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
121     4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
122     4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
123     4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
124     4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
125     4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
126     4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
127     4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
128     4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
129     4957, 4967, 4969, 4973, 4987, 4993, 4999,
130     0
131 };
132 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
133
134 void
135 _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
136                                    void *cb_data )
137 {
138   progress_cb = cb;
139   progress_cb_data = cb_data;
140 }
141
142
143 static void
144 progress( int c )
145 {
146   if ( progress_cb )
147     progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
148 }
149
150
151 /****************
152  * Generate a prime number (stored in secure memory)
153  */
154 gcry_mpi_t
155 _gcry_generate_secret_prime (unsigned int nbits,
156                              int (*extra_check)(void*, gcry_mpi_t),
157                              void *extra_check_arg)
158 {
159   gcry_mpi_t prime;
160
161   prime = gen_prime( nbits, 1, 2, extra_check, extra_check_arg);
162   progress('\n');
163   return prime;
164 }
165
166 gcry_mpi_t
167 _gcry_generate_public_prime( unsigned int nbits,
168                              int (*extra_check)(void*, gcry_mpi_t),
169                              void *extra_check_arg)
170 {
171   gcry_mpi_t prime;
172
173   prime = gen_prime( nbits, 0, 2, extra_check, extra_check_arg );
174   progress('\n');
175   return prime;
176 }
177
178
179 /****************
180  * We do not need to use the strongest RNG because we gain no extra
181  * security from it - The prime number is public and we could also
182  * offer the factors for those who are willing to check that it is
183  * indeed a strong prime.  With ALL_FACTORS set to true all afcors of
184  * prime-1 are returned in FACTORS.
185  *
186  * mode 0: Standard
187  *      1: Make sure that at least one factor is of size qbits.
188  */
189 static gcry_err_code_t
190 prime_generate_internal (int mode,
191                          gcry_mpi_t *prime_generated, unsigned int pbits,
192                          unsigned int qbits, gcry_mpi_t g,
193                          gcry_mpi_t **ret_factors,
194                          gcry_random_level_t randomlevel, unsigned int flags,
195                          int all_factors)
196 {
197   gcry_err_code_t err = 0;
198   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
199                                      caller.  */
200   gcry_mpi_t *factors = NULL;   /* Current factors.  */
201   gcry_mpi_t *pool = NULL;      /* Pool of primes.  */
202   unsigned char *perms = NULL;  /* Permutations of POOL.  */
203   gcry_mpi_t q_factor = NULL;   /* Used if QBITS is non-zero.  */
204   unsigned int fbits = 0;       /* Length of prime factors.  */
205   unsigned int n = 0;           /* Number of factors.  */
206   unsigned int m = 0;           /* Number of primes in pool.  */
207   gcry_mpi_t q = NULL;          /* First prime factor.  */
208   gcry_mpi_t prime = NULL;      /* Prime candidate.  */
209   unsigned int nprime = 0;      /* Bits of PRIME.  */
210   unsigned int req_qbits;       /* The original QBITS value.  */
211   gcry_mpi_t val_2;             /* For check_prime().  */
212   unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
213   unsigned int count1 = 0, count2 = 0;
214   unsigned int i = 0, j = 0;
215
216   if (pbits < 48)
217     return GPG_ERR_INV_ARG;
218
219   /* If QBITS is not given, assume a reasonable value. */
220   if (!qbits)
221     qbits = pbits / 3;
222
223   req_qbits = qbits;
224
225   /* Find number of needed prime factors.  */
226   for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++)
227     ;
228   n--;
229
230   val_2 = mpi_alloc_set_ui (2);
231
232   if ((! n) || ((mode == 1) && (n < 2)))
233     {
234       err = GPG_ERR_INV_ARG;
235       goto leave;
236     }
237
238   if (mode == 1)
239     {
240       n--;
241       fbits = (pbits - 2 * req_qbits -1) / n;
242       qbits =  pbits - req_qbits - n * fbits;
243     }
244   else
245     {
246       fbits = (pbits - req_qbits -1) / n;
247       qbits = pbits - n * fbits;
248     }
249   
250   if (DBG_CIPHER)
251     log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
252                pbits, req_qbits, qbits, fbits, n);
253
254   prime = gcry_mpi_new (pbits);
255
256   /* Generate first prime factor.  */
257   q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
258   
259   if (mode == 1)
260     q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
261   
262   /* Allocate an array to hold the factors + 2 for later usage.  */
263   factors = gcry_calloc (n + 2, sizeof (*factors));
264   if (!factors)
265     {
266       err = gpg_err_code_from_errno (errno);
267       goto leave;
268     }
269       
270   /* Make a pool of 3n+5 primes (this is an arbitrary value).  */
271   m = n * 3 + 5;
272   if (mode == 1) /* Need some more (for e.g. DSA).  */
273     m += 5;
274   if (m < 25)
275     m = 25;
276   pool = gcry_calloc (m , sizeof (*pool));
277   if (! pool)
278     {
279       err = gpg_err_code_from_errno (errno);
280       goto leave;
281     }
282
283   /* Permutate over the pool of primes.  */
284   do
285     {
286     next_try:
287       if (! perms)
288         {
289           /* Allocate new primes.  */
290           for(i = 0; i < m; i++)
291             {
292               mpi_free (pool[i]);
293               pool[i] = NULL;
294             }
295
296           /* Init m_out_of_n().  */
297           perms = gcry_calloc (1, m);
298           if (! perms)
299             {
300               err = gpg_err_code_from_errno (errno);
301               goto leave;
302             }
303           for(i = 0; i < n; i++)
304             {
305               perms[i] = 1;
306               pool[i] = gen_prime (fbits, is_secret,
307                                    randomlevel, NULL, NULL);
308               factors[i] = pool[i];
309             }
310         }
311       else
312         {
313           m_out_of_n (perms, n, m);
314           for (i = j = 0; (i < m) && (j < n); i++)
315             if (perms[i])
316               {
317                 if(! pool[i])
318                   pool[i] = gen_prime (fbits, 0, 1, NULL, NULL);
319                 factors[j++] = pool[i];
320               }
321           if (i == n)
322             {
323               gcry_free (perms);
324               perms = NULL;
325               progress ('!');
326               goto next_try;    /* Allocate new primes.  */
327             }
328         }
329
330         /* Generate next prime candidate:
331            p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. 
332         */
333         mpi_set (prime, q);
334         mpi_mul_ui (prime, prime, 2);
335         if (mode == 1)
336           mpi_mul (prime, prime, q_factor);
337         for(i = 0; i < n; i++)
338           mpi_mul (prime, prime, factors[i]);
339         mpi_add_ui (prime, prime, 1);
340         nprime = mpi_get_nbits (prime);
341
342         if (nprime < pbits)
343           {
344             if (++count1 > 20)
345               {
346                 count1 = 0;
347                 qbits++;
348                 progress('>');
349                 mpi_free (q);
350                 q = gen_prime (qbits, 0, 0, NULL, NULL);
351                 goto next_try;
352               }
353           }
354         else
355           count1 = 0;
356         
357         if (nprime > pbits)
358           {
359             if (++count2 > 20)
360               {
361                 count2 = 0;
362                 qbits--;
363                 progress('<');
364                 mpi_free (q);
365                 q = gen_prime (qbits, 0, 0, NULL, NULL);
366                 goto next_try;
367               }
368           }
369         else
370           count2 = 0;
371     }
372   while (! ((nprime == pbits) && check_prime (prime, val_2)));
373
374   if (DBG_CIPHER)
375     {
376       progress ('\n');
377       log_mpidump ("prime    : ", prime);
378       log_mpidump ("factor  q: ", q);
379       if (mode == 1)
380         log_mpidump ("factor q0: ", q_factor);
381       for (i = 0; i < n; i++)
382         log_mpidump ("factor pi: ", factors[i]);
383       log_debug ("bit sizes: prime=%u, q=%u",
384                  mpi_get_nbits (prime), mpi_get_nbits (q));
385       if (mode == 1)
386         log_debug (", q0=%u", mpi_get_nbits (q_factor));
387       for (i = 0; i < n; i++)
388         log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
389       progress('\n');
390     }
391
392   if (ret_factors)
393     {
394       /* Caller wants the factors.  */
395       factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
396       if (! factors_new)
397         {
398           err = gpg_err_code_from_errno (errno);
399           goto leave;
400         }
401
402       if (all_factors)
403         {
404           i = 0;
405           factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
406           factors_new[i++] = mpi_copy (q);
407           if (mode == 1)
408             factors_new[i++] = mpi_copy (q_factor);
409           for(j=0; j < n; j++)
410             factors_new[i++] = mpi_copy (factors[j]);
411         }
412       else
413         {
414           i = 0;
415           if (mode == 1)
416             {
417               factors_new[i++] = mpi_copy (q_factor);
418               for (; i <= n; i++)
419                 factors_new[i] = mpi_copy (factors[i]);
420             }
421           else
422             for (; i < n; i++ )
423               factors_new[i] = mpi_copy (factors[i]);
424         }
425     }
426   
427   if (g)
428     {
429       /* Create a generator (start with 3).  */
430       gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
431       gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
432       gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
433       
434       if (mode == 1)
435         err = GPG_ERR_NOT_IMPLEMENTED;
436       else
437         {
438           factors[n] = q;
439           factors[n + 1] = mpi_alloc_set_ui (2);
440           mpi_sub_ui (pmin1, prime, 1);
441           mpi_set_ui (g, 2);
442           do
443             {
444               mpi_add_ui (g, g, 1);
445               if (DBG_CIPHER)
446                 {
447                   log_debug ("checking g:");
448                   gcry_mpi_dump (g);
449                   log_printf ("\n");
450                 }
451               else
452                 progress('^');
453               for (i = 0; i < n + 2; i++)
454                 {
455                   mpi_fdiv_q (tmp, pmin1, factors[i]);
456                   /* No mpi_pow(), but it is okay to use this with mod
457                      prime.  */
458                   gcry_mpi_powm (b, g, tmp, prime);
459                   if (! mpi_cmp_ui (b, 1))
460                     break;
461                 }
462               if (DBG_CIPHER)
463                 progress('\n');
464             } 
465           while (i < n + 2);
466
467           mpi_free (factors[n+1]);
468           mpi_free (tmp);
469           mpi_free (b);
470           mpi_free (pmin1);
471         }
472     }
473   
474   if (! DBG_CIPHER)
475     progress ('\n');
476
477
478  leave:
479   if (pool)
480     {
481       for(i = 0; i < m; i++)
482         mpi_free (pool[i]);
483       gcry_free (pool);
484     }
485   if (factors)
486     gcry_free (factors);  /* Factors are shallow copies.  */
487   if (perms)
488     gcry_free (perms);
489
490   mpi_free (val_2);
491   mpi_free (q);
492
493   if (! err)
494     {
495       *prime_generated = prime;
496       if (ret_factors)
497         *ret_factors = factors_new;
498     }
499   else
500     {
501       if (factors_new)
502         {
503           for (i = 0; factors_new[i]; i++)
504             mpi_free (factors_new[i]);
505           gcry_free (factors_new);
506         }
507     }
508
509   return err;
510 }
511
512 gcry_mpi_t
513 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
514                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
515 {
516   gcry_err_code_t err = GPG_ERR_NO_ERROR;
517   gcry_mpi_t prime = NULL;
518   
519   err = prime_generate_internal (mode, &prime, pbits, qbits, g,
520                                  ret_factors, GCRY_WEAK_RANDOM, 0, 0);
521
522   return prime;
523 }
524
525 static gcry_mpi_t
526 gen_prime (unsigned int nbits, int secret, int randomlevel, 
527            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
528 {
529   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
530   int i;
531   unsigned x, step;
532   unsigned count1, count2;
533   int *mods;
534   
535 /*   if (  DBG_CIPHER ) */
536 /*     log_debug ("generate a prime of %u bits ", nbits ); */
537
538   if (nbits < 16)
539     log_fatal ("can't generate a prime with less than %d bits\n", 16);
540
541   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
542   /* Make nbits fit into gcry_mpi_t implementation. */
543   val_2  = mpi_alloc_set_ui( 2 );
544   val_3 = mpi_alloc_set_ui( 3);
545   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
546   result = mpi_alloc_like( prime );
547   pminus1= mpi_alloc_like( prime );
548   ptest  = mpi_alloc_like( prime );
549   count1 = count2 = 0;
550   for (;;)
551     {  /* try forvever */
552       int dotcount=0;
553       
554       /* generate a random number */
555       gcry_mpi_randomize( prime, nbits, randomlevel );
556       
557       /* Set high order bit to 1, set low order bit to 1.  If we are
558          generating a secret prime we are most probably doing that
559          for RSA, to make sure that the modulus does have the
560          requested key size we set the 2 high order bits. */
561       mpi_set_highbit (prime, nbits-1);
562       if (secret)
563         mpi_set_bit (prime, nbits-2);
564       mpi_set_bit(prime, 0);
565       
566       /* Calculate all remainders. */
567       for (i=0; (x = small_prime_numbers[i]); i++ )
568         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
569       
570       /* Now try some primes starting with prime. */
571       for(step=0; step < 20000; step += 2 ) 
572         {
573           /* Check against all the small primes we have in mods. */
574           count1++;
575           for (i=0; (x = small_prime_numbers[i]); i++ ) 
576             {
577               while ( mods[i] + step >= x )
578                 mods[i] -= x;
579               if ( !(mods[i] + step) )
580                 break;
581             }
582           if ( x )
583             continue;   /* Found a multiple of an already known prime. */
584           
585           mpi_add_ui( ptest, prime, step );
586
587           /* Do a fast Fermat test now. */
588           count2++;
589           mpi_sub_ui( pminus1, ptest, 1);
590           gcry_mpi_powm( result, val_2, pminus1, ptest );
591           if ( !mpi_cmp_ui( result, 1 ) )
592             { 
593               /* Not composite, perform stronger tests */
594               if (is_prime(ptest, 5, &count2 ))
595                 {
596                   if (!mpi_test_bit( ptest, nbits-1-secret ))
597                     {
598                       progress('\n');
599                       log_debug ("overflow in prime generation\n");
600                       break; /* Stop loop, continue with a new prime. */
601                     }
602
603                   if (extra_check && extra_check (extra_check_arg, ptest))
604                     { 
605                       /* The extra check told us that this prime is
606                          not of the caller's taste. */
607                       progress ('/');
608                     }
609                   else
610                     { 
611                       /* Got it. */
612                       mpi_free(val_2);
613                       mpi_free(val_3);
614                       mpi_free(result);
615                       mpi_free(pminus1);
616                       mpi_free(prime);
617                       gcry_free(mods);
618                       return ptest; 
619                     }
620                 }
621             }
622           if (++dotcount == 10 )
623             {
624               progress('.');
625               dotcount = 0;
626             }
627         }
628       progress(':'); /* restart with a new random value */
629     }
630 }
631
632 /****************
633  * Returns: true if this may be a prime
634  */
635 static int
636 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2 )
637 {
638   int i;
639   unsigned x;
640   int count=0;
641
642   /* Check against small primes. */
643   for (i=0; (x = small_prime_numbers[i]); i++ )
644     {
645       if ( mpi_divisible_ui( prime, x ) )
646         return 0;
647     }
648
649   /* A quick Fermat test. */
650   {
651     gcry_mpi_t result = mpi_alloc_like( prime );
652     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
653     mpi_sub_ui( pminus1, prime, 1);
654     gcry_mpi_powm( result, val_2, pminus1, prime );
655     mpi_free( pminus1 );
656     if ( mpi_cmp_ui( result, 1 ) )
657       { 
658         /* Is composite. */
659         mpi_free( result );
660         progress('.');
661         return 0;
662       }
663     mpi_free( result );
664   }
665
666   /* perform stronger tests */
667   if ( is_prime(prime, 5, &count ) )
668     return 1; /* Probably a prime. */
669   progress('.');
670   return 0;
671 }
672
673
674 /*
675  * Return true if n is probably a prime
676  */
677 static int
678 is_prime (gcry_mpi_t n, int steps, int *count)
679 {
680   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
681   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
682   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
683   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
684   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
685   gcry_mpi_t q;
686   unsigned i, j, k;
687   int rc = 0;
688   unsigned nbits = mpi_get_nbits( n );
689
690   mpi_sub_ui( nminus1, n, 1 );
691
692   /* Find q and k, so that n = 1 + 2^k * q . */
693   q = mpi_copy ( nminus1 );
694   k = mpi_trailing_zeros ( q );
695   mpi_tdiv_q_2exp (q, q, k);
696
697   for (i=0 ; i < steps; i++ )
698     {
699       ++*count;
700       if( !i )
701         {
702           mpi_set_ui( x, 2 );
703         }
704       else
705         {
706           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
707
708           /* Make sure that the number is smaller than the prime and
709              keep the randomness of the high bit. */
710           if ( mpi_test_bit ( x, nbits-2) )
711             {
712               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
713             }
714           else
715             {
716               mpi_set_highbit( x, nbits-2 );
717               mpi_clear_bit( x, nbits-2 );
718             }
719           assert ( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
720         }
721       gcry_mpi_powm ( y, x, q, n);
722       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
723         {
724           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
725             {
726               gcry_mpi_powm(y, y, a2, n);
727               if( !mpi_cmp_ui( y, 1 ) )
728                 goto leave; /* Not a prime. */
729             }
730           if (mpi_cmp( y, nminus1 ) )
731             goto leave; /* Not a prime. */
732         }
733       progress('+');
734     }
735   rc = 1; /* May be a prime. */
736
737  leave:
738   mpi_free( x );
739   mpi_free( y );
740   mpi_free( z );
741   mpi_free( nminus1 );
742   mpi_free( q );
743
744   return rc;
745 }
746
747
748 static void
749 m_out_of_n ( char *array, int m, int n )
750 {
751   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
752
753   if( !m || m >= n )
754     return;
755
756   if( m == 1 )
757     { 
758       /* Special case. */
759       for (i=0; i < n; i++ )
760         {
761           if( array[i] )
762             {
763               array[i++] = 0;
764               if( i >= n )
765                 i = 0;
766               array[i] = 1;
767               return;
768             }
769         }
770       BUG();
771     }
772
773   for (j=1; j < n; j++ )
774     {
775       if ( array[n-1] == array[n-j-1])
776         continue;
777       j1 = j;
778       break;
779     }
780
781   if ( (m & 1) )
782     {
783       /* M is odd. */
784       if( array[n-1] )
785         {
786           if( j1 & 1 )
787             {
788               k1 = n - j1;
789               k2 = k1+2;
790               if( k2 > n )
791                 k2 = n;
792               goto leave;
793             }
794           goto scan;
795         }
796       k2 = n - j1 - 1;
797       if( k2 == 0 )
798         {
799           k1 = i;
800           k2 = n - j1;
801         }
802       else if( array[k2] && array[k2-1] )
803         k1 = n;
804       else
805         k1 = k2 + 1;
806     }
807   else 
808     {
809       /* M is even. */
810       if( !array[n-1] )
811         {
812           k1 = n - j1;
813           k2 = k1 + 1;
814           goto leave;
815         }
816         
817       if( !(j1 & 1) )
818         {
819           k1 = n - j1;
820           k2 = k1+2;
821           if( k2 > n )
822             k2 = n;
823           goto leave;
824         }
825     scan:
826       jp = n - j1 - 1;
827       for (i=1; i <= jp; i++ ) 
828         {
829           i1 = jp + 2 - i;
830           if( array[i1-1]  )
831             {
832               if( array[i1-2] )
833                 {
834                   k1 = i1 - 1;
835                   k2 = n - j1;
836                 }
837               else
838                 {
839                   k1 = i1 - 1;
840                   k2 = n + 1 - j1;
841                 }
842               goto leave;
843             }
844         }
845       k1 = 1;
846       k2 = n + 1 - m;
847     }
848  leave:
849   array[k1-1] = !array[k1-1];
850   array[k2-1] = !array[k2-1];
851 }
852
853
854 /* Generate a new prime number of PRIME_BITS bits and store it in
855    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
856    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
857    non-zero, allocate a new, NULL-terminated array holding the prime
858    factors and store it in FACTORS.  FLAGS might be used to influence
859    the prime number generation process.  */
860 gcry_error_t
861 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
862                      unsigned int factor_bits, gcry_mpi_t **factors,
863                      gcry_prime_check_func_t cb_func, void *cb_arg,
864                      gcry_random_level_t random_level,
865                      unsigned int flags)
866 {
867   gcry_err_code_t err = GPG_ERR_NO_ERROR;
868   gcry_mpi_t *factors_generated = NULL;
869   gcry_mpi_t prime_generated = NULL;
870   unsigned int mode = 0;
871
872   if (!prime)
873     return gpg_error (GPG_ERR_INV_ARG);
874   *prime = NULL; 
875
876   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
877     mode = 1;
878
879   /* Generate.  */
880   err = prime_generate_internal (mode, &prime_generated, prime_bits,
881                                  factor_bits, NULL,
882                                  factors? &factors_generated : NULL,
883                                  random_level, flags, 1);
884
885   if (! err)
886     if (cb_func)
887       {
888         /* Additional check. */
889         if (! (*cb_func) (cb_arg, 0, prime_generated))
890           {
891             /* Failed, deallocate resources.  */
892             unsigned int i;
893
894             mpi_free (prime_generated);
895             if (factors)
896               {
897                 for (i = 0; factors_generated[i]; i++)
898                   mpi_free (factors_generated[i]);
899                 gcry_free (factors_generated);
900               }
901             err = GPG_ERR_GENERAL; 
902           }
903       }
904
905   if (! err)
906     {
907       if (factors)
908         *factors = factors_generated;
909       *prime = prime_generated;
910     }
911
912   return gcry_error (err);
913 }
914
915 /* Check wether the number X is prime.  */
916 gcry_error_t
917 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
918 {
919   gcry_err_code_t err = GPG_ERR_NO_ERROR;
920   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
921
922   if (! check_prime (x, val_2))
923     err = GPG_ERR_NO_PRIME;
924
925   mpi_free (val_2);
926
927   return gcry_error (err);
928 }
929
930 /* Find a generator for PRIME where the factorization of (prime-1) is
931    in the NULL terminated array FACTORS. Return the generator as a
932    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
933    atart for the search. Returns 0 on success.*/
934 gcry_error_t
935 gcry_prime_group_generator (gcry_mpi_t *r_g,
936                             gcry_mpi_t prime, gcry_mpi_t *factors,
937                             gcry_mpi_t start_g)
938 {
939   gcry_mpi_t tmp = gcry_mpi_new (0);
940   gcry_mpi_t b = gcry_mpi_new (0);
941   gcry_mpi_t pmin1 = gcry_mpi_new (0);
942   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
943   int first = 1;
944   int i, n;
945
946   if (!factors || !r_g || !prime)
947     return gpg_error (GPG_ERR_INV_ARG);
948   *r_g = NULL; 
949
950   for (n=0; factors[n]; n++)
951     ;
952   if (n < 2)
953     return gpg_error (GPG_ERR_INV_ARG);
954
955   /* Extra sanity check - usually disabled. */  
956 /*   mpi_set (tmp, factors[0]); */
957 /*   for(i = 1; i < n; i++) */
958 /*     mpi_mul (tmp, tmp, factors[i]); */
959 /*   mpi_add_ui (tmp, tmp, 1); */
960 /*   if (mpi_cmp (prime, tmp)) */
961 /*     return gpg_error (GPG_ERR_INV_ARG); */
962   
963   gcry_mpi_sub_ui (pmin1, prime, 1);      
964   do         
965     {
966       if (first)
967         first = 0;
968       else
969         gcry_mpi_add_ui (g, g, 1);
970       
971       if (DBG_CIPHER)
972         {
973           log_debug ("checking g:");
974           gcry_mpi_dump (g);
975           log_debug ("\n");
976         }
977       else
978         progress('^');
979       
980       for (i = 0; i < n; i++)
981         {
982           mpi_fdiv_q (tmp, pmin1, factors[i]);
983           gcry_mpi_powm (b, g, tmp, prime);
984           if (! mpi_cmp_ui (b, 1))
985             break;
986         }
987       if (DBG_CIPHER)
988         progress('\n');
989     }
990   while (i < n);
991   
992   gcry_mpi_release (tmp);
993   gcry_mpi_release (b); 
994   gcry_mpi_release (pmin1); 
995   *r_g = g; 
996
997   return 0; 
998 }
999
1000 /* Convenience function to release the factors array. */
1001 void
1002 gcry_prime_release_factors (gcry_mpi_t *factors)
1003 {
1004   if (factors)
1005     {
1006       int i;
1007       
1008       for (i=0; factors[i]; i++)
1009         mpi_free (factors[i]);
1010       gcry_free (factors);
1011     }
1012 }