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