(gen_prime): Assert that NBITS is never zero, it
[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.
181  *
182  * mode 0: Standard
183  *      1: Make sure that at least one factor is of size qbits.
184  */
185 static gcry_err_code_t
186 prime_generate_internal (int mode,
187                          gcry_mpi_t *prime_generated, unsigned int pbits,
188                          unsigned int qbits, gcry_mpi_t g,
189                          gcry_mpi_t **ret_factors,
190                          gcry_random_level_t random, unsigned int flags)
191 {
192   gcry_err_code_t err = GPG_ERR_NO_ERROR;
193   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
194                                      caller.  */
195   gcry_mpi_t *factors = NULL;   /* Current factors.  */
196   gcry_mpi_t *pool = NULL;      /* Pool of primes.  */
197   unsigned char *perms = NULL;  /* Permutations of POOL.  */
198   gcry_mpi_t q_factor = NULL;   /* Used if QBITS is non-zero.  */
199   unsigned int fbits = 0;       /* Length of prime factors.  */
200   unsigned int n = 0;           /* Number of factors.  */
201   unsigned int m = 0;           /* Number of primes in pool.  */
202   gcry_mpi_t q = NULL;          /* First prime factor.  */
203   gcry_mpi_t prime;             /* Prime candidate.  */
204   unsigned int nprime = 0;      /* Bits of PRIME.  */
205   unsigned int req_qbits = qbits; /* The original QBITS value.  */
206   gcry_mpi_t val_2  = mpi_alloc_set_ui (2); /* For check_prime().  */
207   unsigned int is_secret = flags & GCRY_PRIME_FLAG_SECRET;
208   unsigned int count1 = 0, count2 = 0;
209   unsigned int i = 0, j = 0;
210   
211   /* Find number of needed prime factors.  */
212   for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++);
213   n--;
214
215   if ((! n) || ((mode == 1) && (n < 2)))
216     err = GPG_ERR_INV_ARG;
217
218   if (! err)
219     {
220       if (mode == 1)
221         {
222           n--;
223           fbits = (pbits - 2 * req_qbits -1) / n;
224           qbits =  pbits - req_qbits - n * fbits;
225         }
226       else
227         {
228           fbits = (pbits - req_qbits -1) / n;
229           qbits = pbits - n * fbits;
230         }
231       
232       if (DBG_CIPHER)
233         log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
234                    pbits, req_qbits, qbits, fbits, n);
235
236       prime = gcry_mpi_new (pbits);
237
238       /* Generate first prime factor.  */
239       q = gen_prime (qbits, is_secret, random, NULL, NULL);
240
241       if (mode == 1)
242         q_factor = gen_prime (req_qbits, is_secret, random, NULL, NULL);
243
244       /* Allocate an array to hold the factors + 2 for later
245          usage.  */
246       factors = gcry_calloc (n + 2, sizeof (*factors));
247       if (! factors)
248         err = GPG_ERR_INTERNAL; /* FIXME.  */
249     }
250
251   if (! err)
252     {
253       /* Make a pool of 3n+5 primes (this is an arbitrary value).  */
254
255       m = n * 3 + 5;
256       if (mode == 1)
257         /* Need some more (for e.g. DSA).  */
258         m += 5;
259       if (m < 25)
260         m = 25;
261       pool = gcry_calloc (m , sizeof (*pool));
262       if (! pool)
263         err = GPG_ERR_INTERNAL;
264     }
265
266   if (! err)
267     /* Permutate over the pool of primes.  */
268     do
269       {
270       next_try:
271         if (! perms)
272           {
273             /* Allocate new primes.  */
274             for(i = 0; i < m; i++)
275               {
276                 mpi_free (pool[i]);
277                 pool[i] = NULL;
278               }
279
280             /* Init m_out_of_n().  */
281             perms = gcry_calloc (1, m);
282             if (! perms)
283               err = GPG_ERR_INTERNAL; /* FIXME.  */
284             else
285               {
286                 for(i = 0; i < n; i++)
287                   {
288                     perms[i] = 1;
289                     pool[i] = gen_prime (fbits, is_secret, random, NULL, NULL);
290                     factors[i] = pool[i];
291                   }
292               }
293
294             if (err)
295               break;
296           }
297         else
298           {
299             m_out_of_n (perms, n, m);
300             for(i = j = 0; (i < m) && (j < n); i++)
301               if (perms[i])
302                 {
303                   if(! pool[i])
304                     pool[i] = gen_prime (fbits, 0, 1, NULL, NULL);
305                   factors[j++] = pool[i];
306                 }
307             if (i == n)
308               {
309                 gcry_free(perms);
310                 perms = NULL;
311                 progress('!');
312                 goto next_try;  /* Allocate new primes.  */
313               }
314           }
315
316         /* Generate next prime candidate:
317
318         p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.  */
319
320         mpi_set (prime, q);
321         mpi_mul_ui (prime, prime, 2);
322         if (mode == 1)
323           mpi_mul (prime, prime, q_factor);
324         for(i = 0; i < n; i++)
325           mpi_mul (prime, prime, factors[i]);
326         mpi_add_ui (prime, prime, 1);
327         nprime = mpi_get_nbits (prime);
328
329         if (nprime < pbits)
330           {
331             if (++count1 > 20)
332               {
333                 count1 = 0;
334                 qbits++;
335                 progress('>');
336                 mpi_free (q);
337                 q = gen_prime (qbits, 0, 0, NULL, NULL);
338                 goto next_try;
339               }
340           }
341         else
342           count1 = 0;
343       
344         if (nprime > pbits)
345           {
346             if (++count2 > 20)
347               {
348                 count2 = 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           count2 = 0;
358       }
359     while (! ((nprime == pbits) && check_prime (prime, val_2)));
360
361   if (! err)
362     if (DBG_CIPHER)
363       {
364         progress ('\n');
365         log_mpidump ("prime    : ", prime);
366         log_mpidump ("factor  q: ", q);
367         if (mode == 1)
368           log_mpidump ("factor q0: ", q_factor);
369         for(i = 0; i < n; i++)
370           log_mpidump ("factor pi: ", factors[i]);
371         log_debug ("bit sizes: prime=%u, q=%u",
372                    mpi_get_nbits (prime), mpi_get_nbits (q));
373         if (mode == 1)
374           log_debug (", q0=%u", mpi_get_nbits (q_factor));
375         for (i = 0; i < n; i++)
376           log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
377         progress('\n');
378       }
379
380   if (! err)
381     if (ret_factors)
382       {
383         /* Caller wants the factors.  */
384         factors_new = gcry_calloc (n + 2, sizeof (*factors_new));
385         if (! factors_new)
386           err = GPG_ERR_INTERNAL;       /* FIXME.  */
387         else
388           {
389             i = 0;
390             if (mode == 1)
391               {
392                 (factors_new)[i++] = mpi_copy (q_factor);
393                 for(; i <= n; i++)
394                   (factors_new)[i] = mpi_copy (factors[i]);
395               }
396             else
397               for(; i < n; i++ )
398                 (factors_new)[i] = mpi_copy (factors[i]);
399           }
400       }
401
402   if (! err)
403     if (g)
404       {
405         /* Create a generator (start with 3).  */
406         gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
407         gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
408         gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
409
410         if (mode == 1)
411           err = GPG_ERR_NOT_IMPLEMENTED;
412         else
413           {
414             factors[n] = q;
415             factors[n + 1] = mpi_alloc_set_ui (2);
416             mpi_sub_ui (pmin1, prime, 1);
417             mpi_set_ui (g, 2);
418             do
419               {
420                 mpi_add_ui (g, g, 1);
421                 if (DBG_CIPHER)
422                   {
423                     log_debug ("checking g:");
424                     gcry_mpi_dump (g);
425                     log_debug ("\n");
426                   }
427                 else
428                   progress('^');
429                 for (i = 0; i < n + 2; i++)
430                   {
431                     mpi_fdiv_q (tmp, pmin1, factors[i]);
432                     /* No mpi_pow(), but it is okay to use this with mod
433                        prime.  */
434                     gcry_mpi_powm (b, g, tmp, prime);
435                     if (! mpi_cmp_ui (b, 1))
436                       break;
437                   }
438                 if (DBG_CIPHER)
439                   progress('\n');
440               } while (i < n + 2);
441             mpi_free (factors[n+1]);
442             mpi_free (tmp);
443             mpi_free (b);
444             mpi_free (pmin1);
445           }
446       }
447   
448   if (! err)
449     if (! DBG_CIPHER)
450       progress ('\n');
451
452   if (pool)
453     {
454       for(i = 0; i < m; i++)
455         mpi_free (pool[i]);
456       gcry_free (pool);
457     }
458   if (factors)
459     gcry_free (factors);  /* Factors are shallow copies.  */
460   if (perms)
461     gcry_free (perms);
462
463   mpi_free (val_2);
464   mpi_free (q);
465
466   if (! err)
467     {
468       *prime_generated = prime;
469       if (ret_factors)
470         *ret_factors = factors_new;
471     }
472   else
473     {
474       if (factors_new)
475         {
476           for (i = 0; factors_new[i]; i++)
477             mpi_free (factors_new[i]);
478           gcry_free (factors_new);
479         }
480     }
481
482   return err;
483 }
484
485 gcry_mpi_t
486 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
487                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
488 {
489   gcry_err_code_t err = GPG_ERR_NO_ERROR;
490   gcry_mpi_t prime = NULL;
491   
492   err = prime_generate_internal (mode, &prime, pbits, qbits, g,
493                                  ret_factors, GCRY_WEAK_RANDOM, 0);
494
495   return prime;
496 }
497
498 static gcry_mpi_t
499 gen_prime (unsigned int nbits, int secret, int randomlevel, 
500            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
501 {
502   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
503   int i;
504   unsigned x, step;
505   unsigned count1, count2;
506   int *mods;
507   
508   if( 0 && DBG_CIPHER )
509     log_debug ("generate a prime of %u bits ", nbits );
510
511   if (!nbits)
512     log_fatal ("trying to generate a prime of zero bits\n");
513
514   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
515   /* make nbits fit into gcry_mpi_t implementation */
516   val_2  = mpi_alloc_set_ui( 2 );
517   val_3 = mpi_alloc_set_ui( 3);
518   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
519   result = mpi_alloc_like( prime );
520   pminus1= mpi_alloc_like( prime );
521   ptest  = mpi_alloc_like( prime );
522   count1 = count2 = 0;
523   for (;;)
524     {  /* try forvever */
525       int dotcount=0;
526       
527       /* generate a random number */
528       gcry_mpi_randomize( prime, nbits, randomlevel );
529       
530       /* Set high order bit to 1, set low order bit to 0.  If we are
531          generating a secret prime we are most probably doing that
532          for RSA, to make sure that the modulus does have the
533          requested keysize we set the 2 high order bits */
534       mpi_set_highbit (prime, nbits-1);
535       if (secret)
536         mpi_set_bit (prime, nbits-2);
537       mpi_set_bit(prime, 0);
538       
539       /* calculate all remainders */
540       for (i=0; (x = small_prime_numbers[i]); i++ )
541         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
542       
543       /* now try some primes starting with prime */
544       for(step=0; step < 20000; step += 2 ) 
545         {
546           /* check against all the small primes we have in mods */
547           count1++;
548           for (i=0; (x = small_prime_numbers[i]); i++ ) 
549             {
550               while ( mods[i] + step >= x )
551                 mods[i] -= x;
552               if ( !(mods[i] + step) )
553                 break;
554             }
555           if ( x )
556             continue;   /* found a multiple of an already known prime */
557
558           mpi_add_ui( ptest, prime, step );
559
560           /* do a faster Fermat test */
561           count2++;
562           mpi_sub_ui( pminus1, ptest, 1);
563           gcry_mpi_powm( result, val_2, pminus1, ptest );
564           if ( !mpi_cmp_ui( result, 1 ) )
565             { /* not composite, perform stronger tests */
566                 if (is_prime(ptest, 5, &count2 ))
567                   {
568                     if (!mpi_test_bit( ptest, nbits-1-secret ))
569                       {
570                         progress('\n');
571                         log_debug("overflow in prime generation\n");
572                         break; /* stop loop, continue with a new prime */
573                       }
574
575                     if (extra_check && extra_check (extra_check_arg, ptest))
576                       { /* The extra check told us that this prime is
577                            not of the caller's taste. */
578                         progress ('/');
579                       }
580                     else
581                       { /* got it */
582                         mpi_free(val_2);
583                         mpi_free(val_3);
584                         mpi_free(result);
585                         mpi_free(pminus1);
586                         mpi_free(prime);
587                         gcry_free(mods);
588                         return ptest; 
589                       }
590                   }
591             }
592           if (++dotcount == 10 )
593             {
594               progress('.');
595               dotcount = 0;
596             }
597         }
598       progress(':'); /* restart with a new random value */
599     }
600 }
601
602 /****************
603  * Returns: true if this may be a prime
604  */
605 static int
606 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2 )
607 {
608     int i;
609     unsigned x;
610     int count=0;
611
612     /* check against small primes */
613     for(i=0; (x = small_prime_numbers[i]); i++ ) {
614         if( mpi_divisible_ui( prime, x ) )
615             return 0;
616     }
617
618     /* a quick fermat test */
619     {
620         gcry_mpi_t result = mpi_alloc_like( prime );
621         gcry_mpi_t pminus1 = mpi_alloc_like( prime );
622         mpi_sub_ui( pminus1, prime, 1);
623         gcry_mpi_powm( result, val_2, pminus1, prime );
624         mpi_free( pminus1 );
625         if( mpi_cmp_ui( result, 1 ) ) { /* if composite */
626             mpi_free( result );
627             progress('.');
628             return 0;
629         }
630         mpi_free( result );
631     }
632
633     /* perform stronger tests */
634     if( is_prime(prime, 5, &count ) )
635         return 1; /* is probably a prime */
636     progress('.');
637     return 0;
638 }
639
640
641 /****************
642  * Return true if n is probably a prime
643  */
644 static int
645 is_prime( gcry_mpi_t n, int steps, int *count )
646 {
647     gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
648     gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
649     gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
650     gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
651     gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
652     gcry_mpi_t q;
653     unsigned i, j, k;
654     int rc = 0;
655     unsigned nbits = mpi_get_nbits( n );
656
657     mpi_sub_ui( nminus1, n, 1 );
658
659     /* find q and k, so that n = 1 + 2^k * q */
660     q = mpi_copy( nminus1 );
661     k = mpi_trailing_zeros( q );
662     mpi_tdiv_q_2exp(q, q, k);
663
664     for(i=0 ; i < steps; i++ ) {
665         ++*count;
666         if( !i ) {
667             mpi_set_ui( x, 2 );
668         }
669         else {
670             gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
671
672             /* make sure that the number is smaller than the prime
673              * and keep the randomness of the high bit */
674             if( mpi_test_bit( x, nbits-2 ) ) {
675                 mpi_set_highbit( x, nbits-2 ); /* clear all higher bits */
676             }
677             else {
678                 mpi_set_highbit( x, nbits-2 );
679                 mpi_clear_bit( x, nbits-2 );
680             }
681             assert( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
682         }
683         gcry_mpi_powm( y, x, q, n);
684         if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
685             for( j=1; j < k && mpi_cmp( y, nminus1 ); j++ ) {
686                 gcry_mpi_powm(y, y, a2, n);
687                 if( !mpi_cmp_ui( y, 1 ) )
688                     goto leave; /* not a prime */
689             }
690             if( mpi_cmp( y, nminus1 ) )
691                 goto leave; /* not a prime */
692         }
693         progress('+');
694     }
695     rc = 1; /* may be a prime */
696
697   leave:
698     mpi_free( x );
699     mpi_free( y );
700     mpi_free( z );
701     mpi_free( nminus1 );
702     mpi_free( q );
703
704     return rc;
705 }
706
707
708 static void
709 m_out_of_n( char *array, int m, int n )
710 {
711     int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
712
713     if( !m || m >= n )
714         return;
715
716     if( m == 1 ) { /* special case */
717         for(i=0; i < n; i++ )
718             if( array[i] ) {
719                 array[i++] = 0;
720                 if( i >= n )
721                     i = 0;
722                 array[i] = 1;
723                 return;
724             }
725         BUG();
726     }
727
728     for(j=1; j < n; j++ ) {
729         if( array[n-1] == array[n-j-1] )
730             continue;
731         j1 = j;
732         break;
733     }
734
735     if( m & 1 ) { /* m is odd */
736         if( array[n-1] ) {
737             if( j1 & 1 ) {
738                 k1 = n - j1;
739                 k2 = k1+2;
740                 if( k2 > n )
741                     k2 = n;
742                 goto leave;
743             }
744             goto scan;
745         }
746         k2 = n - j1 - 1;
747         if( k2 == 0 ) {
748             k1 = i;
749             k2 = n - j1;
750         }
751         else if( array[k2] && array[k2-1] )
752             k1 = n;
753         else
754             k1 = k2 + 1;
755     }
756     else { /* m is even */
757         if( !array[n-1] ) {
758             k1 = n - j1;
759             k2 = k1 + 1;
760             goto leave;
761         }
762
763         if( !(j1 & 1) ) {
764             k1 = n - j1;
765             k2 = k1+2;
766             if( k2 > n )
767                 k2 = n;
768             goto leave;
769         }
770       scan:
771         jp = n - j1 - 1;
772         for(i=1; i <= jp; i++ ) {
773             i1 = jp + 2 - i;
774             if( array[i1-1]  ) {
775                 if( array[i1-2] ) {
776                     k1 = i1 - 1;
777                     k2 = n - j1;
778                 }
779                 else {
780                     k1 = i1 - 1;
781                     k2 = n + 1 - j1;
782                 }
783                 goto leave;
784             }
785         }
786         k1 = 1;
787         k2 = n + 1 - m;
788     }
789   leave:
790     array[k1-1] = !array[k1-1];
791     array[k2-1] = !array[k2-1];
792 }
793
794
795 /* Generate a new prime number of PRIME_BITS bits and store it in
796    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
797    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
798    non-zero, allocate a new, NULL-terminated array holding the prime
799    factors and store it in FACTORS.  FLAGS might be used to influence
800    the prime number generation process.  */
801 gcry_error_t
802 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
803                      unsigned int factor_bits, gcry_mpi_t **factors,
804                      gcry_prime_check_func_t cb_func, void *cb_arg,
805                      gcry_random_level_t random_level,
806                      unsigned int flags)
807 {
808   gcry_err_code_t err = GPG_ERR_NO_ERROR;
809   gcry_mpi_t *factors_generated = NULL;
810   gcry_mpi_t prime_generated = NULL;
811   unsigned int mode = 0;
812
813   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
814     mode = 1;
815
816   /* Generate.  */
817   err = prime_generate_internal (mode, &prime_generated, prime_bits,
818                                  factor_bits, NULL, &factors_generated,
819                                  random_level, flags);
820
821   if (! err)
822     if (cb_func)
823       {
824         /* Additional check */
825         if (! (*cb_func) (cb_arg, 0, prime_generated))
826           {
827             /* Failed, deallocate resources.  */
828
829             unsigned int i;
830
831             mpi_free (prime_generated);
832             for (i = 0; factors_generated[i]; i++)
833               mpi_free (factors_generated[i]);
834             gcry_free (factors_generated);
835             err = GPG_ERR_INTERNAL; /* FIXME.  */
836           }
837       }
838
839   if (! err)
840     {
841       /* Done.  */
842       *prime = prime_generated;
843       *factors = factors_generated;
844     }
845
846   return gcry_error (err);
847 }
848
849 /* Check wether the number X is prime.  */
850 gcry_error_t
851 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
852 {
853   gcry_err_code_t err = GPG_ERR_NO_ERROR;
854   gcry_mpi_t test_value = mpi_alloc_set_ui (2); /* ? */
855
856   if (! check_prime (x, test_value))
857     err = GPG_ERR_NO_PRIME;
858
859   mpi_free (test_value);
860
861   return gcry_error (err);
862 }