2004-01-25 Moritz Schulte <mo@g10code.com>
[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   mpi_free (q_factor);
493
494   if (! err)
495     {
496       *prime_generated = prime;
497       if (ret_factors)
498         *ret_factors = factors_new;
499     }
500   else
501     {
502       if (factors_new)
503         {
504           for (i = 0; factors_new[i]; i++)
505             mpi_free (factors_new[i]);
506           gcry_free (factors_new);
507         }
508       mpi_free (prime);
509     }
510
511   return err;
512 }
513
514 gcry_mpi_t
515 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
516                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
517 {
518   gcry_err_code_t err = GPG_ERR_NO_ERROR;
519   gcry_mpi_t prime = NULL;
520   
521   err = prime_generate_internal (mode, &prime, pbits, qbits, g,
522                                  ret_factors, GCRY_WEAK_RANDOM, 0, 0);
523
524   return prime;
525 }
526
527 static gcry_mpi_t
528 gen_prime (unsigned int nbits, int secret, int randomlevel, 
529            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
530 {
531   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
532   int i;
533   unsigned x, step;
534   unsigned count1, count2;
535   int *mods;
536   
537 /*   if (  DBG_CIPHER ) */
538 /*     log_debug ("generate a prime of %u bits ", nbits ); */
539
540   if (nbits < 16)
541     log_fatal ("can't generate a prime with less than %d bits\n", 16);
542
543   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
544   /* Make nbits fit into gcry_mpi_t implementation. */
545   val_2  = mpi_alloc_set_ui( 2 );
546   val_3 = mpi_alloc_set_ui( 3);
547   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
548   result = mpi_alloc_like( prime );
549   pminus1= mpi_alloc_like( prime );
550   ptest  = mpi_alloc_like( prime );
551   count1 = count2 = 0;
552   for (;;)
553     {  /* try forvever */
554       int dotcount=0;
555       
556       /* generate a random number */
557       gcry_mpi_randomize( prime, nbits, randomlevel );
558       
559       /* Set high order bit to 1, set low order bit to 1.  If we are
560          generating a secret prime we are most probably doing that
561          for RSA, to make sure that the modulus does have the
562          requested key size we set the 2 high order bits. */
563       mpi_set_highbit (prime, nbits-1);
564       if (secret)
565         mpi_set_bit (prime, nbits-2);
566       mpi_set_bit(prime, 0);
567       
568       /* Calculate all remainders. */
569       for (i=0; (x = small_prime_numbers[i]); i++ )
570         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
571       
572       /* Now try some primes starting with prime. */
573       for(step=0; step < 20000; step += 2 ) 
574         {
575           /* Check against all the small primes we have in mods. */
576           count1++;
577           for (i=0; (x = small_prime_numbers[i]); i++ ) 
578             {
579               while ( mods[i] + step >= x )
580                 mods[i] -= x;
581               if ( !(mods[i] + step) )
582                 break;
583             }
584           if ( x )
585             continue;   /* Found a multiple of an already known prime. */
586           
587           mpi_add_ui( ptest, prime, step );
588
589           /* Do a fast Fermat test now. */
590           count2++;
591           mpi_sub_ui( pminus1, ptest, 1);
592           gcry_mpi_powm( result, val_2, pminus1, ptest );
593           if ( !mpi_cmp_ui( result, 1 ) )
594             { 
595               /* Not composite, perform stronger tests */
596               if (is_prime(ptest, 5, &count2 ))
597                 {
598                   if (!mpi_test_bit( ptest, nbits-1-secret ))
599                     {
600                       progress('\n');
601                       log_debug ("overflow in prime generation\n");
602                       break; /* Stop loop, continue with a new prime. */
603                     }
604
605                   if (extra_check && extra_check (extra_check_arg, ptest))
606                     { 
607                       /* The extra check told us that this prime is
608                          not of the caller's taste. */
609                       progress ('/');
610                     }
611                   else
612                     { 
613                       /* Got it. */
614                       mpi_free(val_2);
615                       mpi_free(val_3);
616                       mpi_free(result);
617                       mpi_free(pminus1);
618                       mpi_free(prime);
619                       gcry_free(mods);
620                       return ptest; 
621                     }
622                 }
623             }
624           if (++dotcount == 10 )
625             {
626               progress('.');
627               dotcount = 0;
628             }
629         }
630       progress(':'); /* restart with a new random value */
631     }
632 }
633
634 /****************
635  * Returns: true if this may be a prime
636  */
637 static int
638 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2 )
639 {
640   int i;
641   unsigned x;
642   int count=0;
643
644   /* Check against small primes. */
645   for (i=0; (x = small_prime_numbers[i]); i++ )
646     {
647       if ( mpi_divisible_ui( prime, x ) )
648         return 0;
649     }
650
651   /* A quick Fermat test. */
652   {
653     gcry_mpi_t result = mpi_alloc_like( prime );
654     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
655     mpi_sub_ui( pminus1, prime, 1);
656     gcry_mpi_powm( result, val_2, pminus1, prime );
657     mpi_free( pminus1 );
658     if ( mpi_cmp_ui( result, 1 ) )
659       { 
660         /* Is composite. */
661         mpi_free( result );
662         progress('.');
663         return 0;
664       }
665     mpi_free( result );
666   }
667
668   /* perform stronger tests */
669   if ( is_prime(prime, 5, &count ) )
670     return 1; /* Probably a prime. */
671   progress('.');
672   return 0;
673 }
674
675
676 /*
677  * Return true if n is probably a prime
678  */
679 static int
680 is_prime (gcry_mpi_t n, int steps, int *count)
681 {
682   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
683   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
684   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
685   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
686   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
687   gcry_mpi_t q;
688   unsigned i, j, k;
689   int rc = 0;
690   unsigned nbits = mpi_get_nbits( n );
691
692   mpi_sub_ui( nminus1, n, 1 );
693
694   /* Find q and k, so that n = 1 + 2^k * q . */
695   q = mpi_copy ( nminus1 );
696   k = mpi_trailing_zeros ( q );
697   mpi_tdiv_q_2exp (q, q, k);
698
699   for (i=0 ; i < steps; i++ )
700     {
701       ++*count;
702       if( !i )
703         {
704           mpi_set_ui( x, 2 );
705         }
706       else
707         {
708           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
709
710           /* Make sure that the number is smaller than the prime and
711              keep the randomness of the high bit. */
712           if ( mpi_test_bit ( x, nbits-2) )
713             {
714               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
715             }
716           else
717             {
718               mpi_set_highbit( x, nbits-2 );
719               mpi_clear_bit( x, nbits-2 );
720             }
721           assert ( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
722         }
723       gcry_mpi_powm ( y, x, q, n);
724       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
725         {
726           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
727             {
728               gcry_mpi_powm(y, y, a2, n);
729               if( !mpi_cmp_ui( y, 1 ) )
730                 goto leave; /* Not a prime. */
731             }
732           if (mpi_cmp( y, nminus1 ) )
733             goto leave; /* Not a prime. */
734         }
735       progress('+');
736     }
737   rc = 1; /* May be a prime. */
738
739  leave:
740   mpi_free( x );
741   mpi_free( y );
742   mpi_free( z );
743   mpi_free( nminus1 );
744   mpi_free( q );
745   mpi_free( a2 );
746
747   return rc;
748 }
749
750
751 static void
752 m_out_of_n ( char *array, int m, int n )
753 {
754   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
755
756   if( !m || m >= n )
757     return;
758
759   if( m == 1 )
760     { 
761       /* Special case. */
762       for (i=0; i < n; i++ )
763         {
764           if( array[i] )
765             {
766               array[i++] = 0;
767               if( i >= n )
768                 i = 0;
769               array[i] = 1;
770               return;
771             }
772         }
773       BUG();
774     }
775
776   for (j=1; j < n; j++ )
777     {
778       if ( array[n-1] == array[n-j-1])
779         continue;
780       j1 = j;
781       break;
782     }
783
784   if ( (m & 1) )
785     {
786       /* M is odd. */
787       if( array[n-1] )
788         {
789           if( j1 & 1 )
790             {
791               k1 = n - j1;
792               k2 = k1+2;
793               if( k2 > n )
794                 k2 = n;
795               goto leave;
796             }
797           goto scan;
798         }
799       k2 = n - j1 - 1;
800       if( k2 == 0 )
801         {
802           k1 = i;
803           k2 = n - j1;
804         }
805       else if( array[k2] && array[k2-1] )
806         k1 = n;
807       else
808         k1 = k2 + 1;
809     }
810   else 
811     {
812       /* M is even. */
813       if( !array[n-1] )
814         {
815           k1 = n - j1;
816           k2 = k1 + 1;
817           goto leave;
818         }
819         
820       if( !(j1 & 1) )
821         {
822           k1 = n - j1;
823           k2 = k1+2;
824           if( k2 > n )
825             k2 = n;
826           goto leave;
827         }
828     scan:
829       jp = n - j1 - 1;
830       for (i=1; i <= jp; i++ ) 
831         {
832           i1 = jp + 2 - i;
833           if( array[i1-1]  )
834             {
835               if( array[i1-2] )
836                 {
837                   k1 = i1 - 1;
838                   k2 = n - j1;
839                 }
840               else
841                 {
842                   k1 = i1 - 1;
843                   k2 = n + 1 - j1;
844                 }
845               goto leave;
846             }
847         }
848       k1 = 1;
849       k2 = n + 1 - m;
850     }
851  leave:
852   array[k1-1] = !array[k1-1];
853   array[k2-1] = !array[k2-1];
854 }
855
856
857 /* Generate a new prime number of PRIME_BITS bits and store it in
858    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
859    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
860    non-zero, allocate a new, NULL-terminated array holding the prime
861    factors and store it in FACTORS.  FLAGS might be used to influence
862    the prime number generation process.  */
863 gcry_error_t
864 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
865                      unsigned int factor_bits, gcry_mpi_t **factors,
866                      gcry_prime_check_func_t cb_func, void *cb_arg,
867                      gcry_random_level_t random_level,
868                      unsigned int flags)
869 {
870   gcry_err_code_t err = GPG_ERR_NO_ERROR;
871   gcry_mpi_t *factors_generated = NULL;
872   gcry_mpi_t prime_generated = NULL;
873   unsigned int mode = 0;
874
875   if (!prime)
876     return gpg_error (GPG_ERR_INV_ARG);
877   *prime = NULL; 
878
879   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
880     mode = 1;
881
882   /* Generate.  */
883   err = prime_generate_internal (mode, &prime_generated, prime_bits,
884                                  factor_bits, NULL,
885                                  factors? &factors_generated : NULL,
886                                  random_level, flags, 1);
887
888   if (! err)
889     if (cb_func)
890       {
891         /* Additional check. */
892         if (! (*cb_func) (cb_arg, 0, prime_generated))
893           {
894             /* Failed, deallocate resources.  */
895             unsigned int i;
896
897             mpi_free (prime_generated);
898             if (factors)
899               {
900                 for (i = 0; factors_generated[i]; i++)
901                   mpi_free (factors_generated[i]);
902                 gcry_free (factors_generated);
903               }
904             err = GPG_ERR_GENERAL; 
905           }
906       }
907
908   if (! err)
909     {
910       if (factors)
911         *factors = factors_generated;
912       *prime = prime_generated;
913     }
914
915   return gcry_error (err);
916 }
917
918 /* Check wether the number X is prime.  */
919 gcry_error_t
920 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
921 {
922   gcry_err_code_t err = GPG_ERR_NO_ERROR;
923   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
924
925   if (! check_prime (x, val_2))
926     err = GPG_ERR_NO_PRIME;
927
928   mpi_free (val_2);
929
930   return gcry_error (err);
931 }
932
933 /* Find a generator for PRIME where the factorization of (prime-1) is
934    in the NULL terminated array FACTORS. Return the generator as a
935    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
936    atart for the search. Returns 0 on success.*/
937 gcry_error_t
938 gcry_prime_group_generator (gcry_mpi_t *r_g,
939                             gcry_mpi_t prime, gcry_mpi_t *factors,
940                             gcry_mpi_t start_g)
941 {
942   gcry_mpi_t tmp = gcry_mpi_new (0);
943   gcry_mpi_t b = gcry_mpi_new (0);
944   gcry_mpi_t pmin1 = gcry_mpi_new (0);
945   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
946   int first = 1;
947   int i, n;
948
949   if (!factors || !r_g || !prime)
950     return gpg_error (GPG_ERR_INV_ARG);
951   *r_g = NULL; 
952
953   for (n=0; factors[n]; n++)
954     ;
955   if (n < 2)
956     return gpg_error (GPG_ERR_INV_ARG);
957
958   /* Extra sanity check - usually disabled. */  
959 /*   mpi_set (tmp, factors[0]); */
960 /*   for(i = 1; i < n; i++) */
961 /*     mpi_mul (tmp, tmp, factors[i]); */
962 /*   mpi_add_ui (tmp, tmp, 1); */
963 /*   if (mpi_cmp (prime, tmp)) */
964 /*     return gpg_error (GPG_ERR_INV_ARG); */
965   
966   gcry_mpi_sub_ui (pmin1, prime, 1);      
967   do         
968     {
969       if (first)
970         first = 0;
971       else
972         gcry_mpi_add_ui (g, g, 1);
973       
974       if (DBG_CIPHER)
975         {
976           log_debug ("checking g:");
977           gcry_mpi_dump (g);
978           log_debug ("\n");
979         }
980       else
981         progress('^');
982       
983       for (i = 0; i < n; i++)
984         {
985           mpi_fdiv_q (tmp, pmin1, factors[i]);
986           gcry_mpi_powm (b, g, tmp, prime);
987           if (! mpi_cmp_ui (b, 1))
988             break;
989         }
990       if (DBG_CIPHER)
991         progress('\n');
992     }
993   while (i < n);
994   
995   gcry_mpi_release (tmp);
996   gcry_mpi_release (b); 
997   gcry_mpi_release (pmin1); 
998   *r_g = g; 
999
1000   return 0; 
1001 }
1002
1003 /* Convenience function to release the factors array. */
1004 void
1005 gcry_prime_release_factors (gcry_mpi_t *factors)
1006 {
1007   if (factors)
1008     {
1009       int i;
1010       
1011       for (i=0; factors[i]; i++)
1012         mpi_free (factors[i]);
1013       gcry_free (factors);
1014     }
1015 }