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