* primegen.c (gen_prime): Bail out if NBITS is less than 16.
[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 random, 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, random, NULL, NULL);
254
255       if (mode == 1)
256         q_factor = gen_prime (req_qbits, is_secret, random, 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, random, NULL, NULL);
304                     factors[i] = pool[i];
305                   }
306               }
307
308             if (err)
309               break;
310           }
311         else
312           {
313             m_out_of_n (perms, n, m);
314             for(i = j = 0; (i < m) && (j < n); i++)
315               if (perms[i])
316                 {
317                   if(! pool[i])
318                     pool[i] = gen_prime (fbits, 0, 1, NULL, NULL);
319                   factors[j++] = pool[i];
320                 }
321             if (i == n)
322               {
323                 gcry_free(perms);
324                 perms = NULL;
325                 progress('!');
326                 goto next_try;  /* Allocate new primes.  */
327               }
328           }
329
330         /* Generate next prime candidate:
331
332         p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.  */
333
334         mpi_set (prime, q);
335         mpi_mul_ui (prime, prime, 2);
336         if (mode == 1)
337           mpi_mul (prime, prime, q_factor);
338         for(i = 0; i < n; i++)
339           mpi_mul (prime, prime, factors[i]);
340         mpi_add_ui (prime, prime, 1);
341         nprime = mpi_get_nbits (prime);
342
343         if (nprime < pbits)
344           {
345             if (++count1 > 20)
346               {
347                 count1 = 0;
348                 qbits++;
349                 progress('>');
350                 mpi_free (q);
351                 q = gen_prime (qbits, 0, 0, NULL, NULL);
352                 goto next_try;
353               }
354           }
355         else
356           count1 = 0;
357       
358         if (nprime > pbits)
359           {
360             if (++count2 > 20)
361               {
362                 count2 = 0;
363                 qbits--;
364                 progress('<');
365                 mpi_free (q);
366                 q = gen_prime (qbits, 0, 0, NULL, NULL);
367                 goto next_try;
368               }
369           }
370         else
371           count2 = 0;
372       }
373     while (! ((nprime == pbits) && check_prime (prime, val_2)));
374
375   if (! err)
376     if (DBG_CIPHER)
377       {
378         progress ('\n');
379         log_mpidump ("prime    : ", prime);
380         log_mpidump ("factor  q: ", q);
381         if (mode == 1)
382           log_mpidump ("factor q0: ", q_factor);
383         for(i = 0; i < n; i++)
384           log_mpidump ("factor pi: ", factors[i]);
385         log_debug ("bit sizes: prime=%u, q=%u",
386                    mpi_get_nbits (prime), mpi_get_nbits (q));
387         if (mode == 1)
388           log_debug (", q0=%u", mpi_get_nbits (q_factor));
389         for (i = 0; i < n; i++)
390           log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
391         progress('\n');
392       }
393
394   if (! err)
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           err = GPG_ERR_INTERNAL;       /* FIXME.  */
401         else if (all_factors)
402           {
403             i = 0;
404             (factors_new)[i++] = gcry_mpi_set_ui (NULL, 2);
405             (factors_new)[i++] = mpi_copy (q);
406             if (mode == 1)
407               (factors_new)[i++] = mpi_copy (q_factor);
408             for(j=0; j < n; j++)
409               (factors_new)[i++] = mpi_copy (factors[j]);
410           }
411         else
412           {
413             i = 0;
414             if (mode == 1)
415               {
416                 (factors_new)[i++] = mpi_copy (q_factor);
417                 for(; i <= n; i++)
418                   (factors_new)[i] = mpi_copy (factors[i]);
419               }
420             else
421               for(; i < n; i++ )
422                 (factors_new)[i] = mpi_copy (factors[i]);
423           }
424       }
425
426   if (! err)
427     if (g)
428       {
429         /* Create a generator (start with 3).  */
430         gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
431         gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
432         gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
433
434         if (mode == 1)
435           err = GPG_ERR_NOT_IMPLEMENTED;
436         else
437           {
438             factors[n] = q;
439             factors[n + 1] = mpi_alloc_set_ui (2);
440             mpi_sub_ui (pmin1, prime, 1);
441             mpi_set_ui (g, 2);
442             do
443               {
444                 mpi_add_ui (g, g, 1);
445                 if (DBG_CIPHER)
446                   {
447                     log_debug ("checking g:");
448                     gcry_mpi_dump (g);
449                     log_debug ("\n");
450                   }
451                 else
452                   progress('^');
453                 for (i = 0; i < n + 2; i++)
454                   {
455                     mpi_fdiv_q (tmp, pmin1, factors[i]);
456                     /* No mpi_pow(), but it is okay to use this with mod
457                        prime.  */
458                     gcry_mpi_powm (b, g, tmp, prime);
459                     if (! mpi_cmp_ui (b, 1))
460                       break;
461                   }
462                 if (DBG_CIPHER)
463                   progress('\n');
464               } while (i < n + 2);
465             mpi_free (factors[n+1]);
466             mpi_free (tmp);
467             mpi_free (b);
468             mpi_free (pmin1);
469           }
470       }
471   
472   if (! err)
473     if (! DBG_CIPHER)
474       progress ('\n');
475
476   if (pool)
477     {
478       for(i = 0; i < m; i++)
479         mpi_free (pool[i]);
480       gcry_free (pool);
481     }
482   if (factors)
483     gcry_free (factors);  /* Factors are shallow copies.  */
484   if (perms)
485     gcry_free (perms);
486
487   mpi_free (val_2);
488   mpi_free (q);
489
490   if (! err)
491     {
492       *prime_generated = prime;
493       if (ret_factors)
494         *ret_factors = factors_new;
495     }
496   else
497     {
498       if (factors_new)
499         {
500           for (i = 0; factors_new[i]; i++)
501             mpi_free (factors_new[i]);
502           gcry_free (factors_new);
503         }
504     }
505
506   return err;
507 }
508
509 gcry_mpi_t
510 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
511                           gcry_mpi_t g, gcry_mpi_t **ret_factors)
512 {
513   gcry_err_code_t err = GPG_ERR_NO_ERROR;
514   gcry_mpi_t prime = NULL;
515   
516   err = prime_generate_internal (mode, &prime, pbits, qbits, g,
517                                  ret_factors, GCRY_WEAK_RANDOM, 0, 0);
518
519   return prime;
520 }
521
522 static gcry_mpi_t
523 gen_prime (unsigned int nbits, int secret, int randomlevel, 
524            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
525 {
526   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
527   int i;
528   unsigned x, step;
529   unsigned count1, count2;
530   int *mods;
531   
532   if( 0 && DBG_CIPHER )
533     log_debug ("generate a prime of %u bits ", nbits );
534
535   if (nbits < 16)
536     log_fatal ("can't generate a prime with less than %d bits\n", 16);
537
538   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
539   /* make nbits fit into gcry_mpi_t implementation */
540   val_2  = mpi_alloc_set_ui( 2 );
541   val_3 = mpi_alloc_set_ui( 3);
542   prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
543   result = mpi_alloc_like( prime );
544   pminus1= mpi_alloc_like( prime );
545   ptest  = mpi_alloc_like( prime );
546   count1 = count2 = 0;
547   for (;;)
548     {  /* try forvever */
549       int dotcount=0;
550       
551       /* generate a random number */
552       gcry_mpi_randomize( prime, nbits, randomlevel );
553       
554       /* Set high order bit to 1, set low order bit to 0.  If we are
555          generating a secret prime we are most probably doing that
556          for RSA, to make sure that the modulus does have the
557          requested keysize we set the 2 high order bits */
558       mpi_set_highbit (prime, nbits-1);
559       if (secret)
560         mpi_set_bit (prime, nbits-2);
561       mpi_set_bit(prime, 0);
562       
563       /* calculate all remainders */
564       for (i=0; (x = small_prime_numbers[i]); i++ )
565         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
566       
567       /* now try some primes starting with prime */
568       for(step=0; step < 20000; step += 2 ) 
569         {
570           /* check against all the small primes we have in mods */
571           count1++;
572           for (i=0; (x = small_prime_numbers[i]); i++ ) 
573             {
574               while ( mods[i] + step >= x )
575                 mods[i] -= x;
576               if ( !(mods[i] + step) )
577                 break;
578             }
579           if ( x )
580             continue;   /* found a multiple of an already known prime */
581
582           mpi_add_ui( ptest, prime, step );
583
584           /* do a faster Fermat test */
585           count2++;
586           mpi_sub_ui( pminus1, ptest, 1);
587           gcry_mpi_powm( result, val_2, pminus1, ptest );
588           if ( !mpi_cmp_ui( result, 1 ) )
589             { /* not composite, perform stronger tests */
590                 if (is_prime(ptest, 5, &count2 ))
591                   {
592                     if (!mpi_test_bit( ptest, nbits-1-secret ))
593                       {
594                         progress('\n');
595                         log_debug("overflow in prime generation\n");
596                         break; /* stop loop, continue with a new prime */
597                       }
598
599                     if (extra_check && extra_check (extra_check_arg, ptest))
600                       { /* The extra check told us that this prime is
601                            not of the caller's taste. */
602                         progress ('/');
603                       }
604                     else
605                       { /* got it */
606                         mpi_free(val_2);
607                         mpi_free(val_3);
608                         mpi_free(result);
609                         mpi_free(pminus1);
610                         mpi_free(prime);
611                         gcry_free(mods);
612                         return ptest; 
613                       }
614                   }
615             }
616           if (++dotcount == 10 )
617             {
618               progress('.');
619               dotcount = 0;
620             }
621         }
622       progress(':'); /* restart with a new random value */
623     }
624 }
625
626 /****************
627  * Returns: true if this may be a prime
628  */
629 static int
630 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2 )
631 {
632     int i;
633     unsigned x;
634     int count=0;
635
636     /* check against small primes */
637     for(i=0; (x = small_prime_numbers[i]); i++ ) {
638         if( mpi_divisible_ui( prime, x ) )
639             return 0;
640     }
641
642     /* a quick fermat test */
643     {
644         gcry_mpi_t result = mpi_alloc_like( prime );
645         gcry_mpi_t pminus1 = mpi_alloc_like( prime );
646         mpi_sub_ui( pminus1, prime, 1);
647         gcry_mpi_powm( result, val_2, pminus1, prime );
648         mpi_free( pminus1 );
649         if( mpi_cmp_ui( result, 1 ) ) { /* if composite */
650             mpi_free( result );
651             progress('.');
652             return 0;
653         }
654         mpi_free( result );
655     }
656
657     /* perform stronger tests */
658     if( is_prime(prime, 5, &count ) )
659         return 1; /* is probably a prime */
660     progress('.');
661     return 0;
662 }
663
664
665 /****************
666  * Return true if n is probably a prime
667  */
668 static int
669 is_prime( gcry_mpi_t n, int steps, int *count )
670 {
671     gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
672     gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
673     gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
674     gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
675     gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
676     gcry_mpi_t q;
677     unsigned i, j, k;
678     int rc = 0;
679     unsigned nbits = mpi_get_nbits( n );
680
681     mpi_sub_ui( nminus1, n, 1 );
682
683     /* find q and k, so that n = 1 + 2^k * q */
684     q = mpi_copy( nminus1 );
685     k = mpi_trailing_zeros( q );
686     mpi_tdiv_q_2exp(q, q, k);
687
688     for(i=0 ; i < steps; i++ ) {
689         ++*count;
690         if( !i ) {
691             mpi_set_ui( x, 2 );
692         }
693         else {
694             gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
695
696             /* make sure that the number is smaller than the prime
697              * and keep the randomness of the high bit */
698             if( mpi_test_bit( x, nbits-2 ) ) {
699                 mpi_set_highbit( x, nbits-2 ); /* clear all higher bits */
700             }
701             else {
702                 mpi_set_highbit( x, nbits-2 );
703                 mpi_clear_bit( x, nbits-2 );
704             }
705             assert( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
706         }
707         gcry_mpi_powm( y, x, q, n);
708         if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
709             for( j=1; j < k && mpi_cmp( y, nminus1 ); j++ ) {
710                 gcry_mpi_powm(y, y, a2, n);
711                 if( !mpi_cmp_ui( y, 1 ) )
712                     goto leave; /* not a prime */
713             }
714             if( mpi_cmp( y, nminus1 ) )
715                 goto leave; /* not a prime */
716         }
717         progress('+');
718     }
719     rc = 1; /* may be a prime */
720
721   leave:
722     mpi_free( x );
723     mpi_free( y );
724     mpi_free( z );
725     mpi_free( nminus1 );
726     mpi_free( q );
727
728     return rc;
729 }
730
731
732 static void
733 m_out_of_n( char *array, int m, int n )
734 {
735     int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
736
737     if( !m || m >= n )
738         return;
739
740     if( m == 1 ) { /* special case */
741         for(i=0; i < n; i++ )
742             if( array[i] ) {
743                 array[i++] = 0;
744                 if( i >= n )
745                     i = 0;
746                 array[i] = 1;
747                 return;
748             }
749         BUG();
750     }
751
752     for(j=1; j < n; j++ ) {
753         if( array[n-1] == array[n-j-1] )
754             continue;
755         j1 = j;
756         break;
757     }
758
759     if( m & 1 ) { /* m is odd */
760         if( array[n-1] ) {
761             if( j1 & 1 ) {
762                 k1 = n - j1;
763                 k2 = k1+2;
764                 if( k2 > n )
765                     k2 = n;
766                 goto leave;
767             }
768             goto scan;
769         }
770         k2 = n - j1 - 1;
771         if( k2 == 0 ) {
772             k1 = i;
773             k2 = n - j1;
774         }
775         else if( array[k2] && array[k2-1] )
776             k1 = n;
777         else
778             k1 = k2 + 1;
779     }
780     else { /* m is even */
781         if( !array[n-1] ) {
782             k1 = n - j1;
783             k2 = k1 + 1;
784             goto leave;
785         }
786
787         if( !(j1 & 1) ) {
788             k1 = n - j1;
789             k2 = k1+2;
790             if( k2 > n )
791                 k2 = n;
792             goto leave;
793         }
794       scan:
795         jp = n - j1 - 1;
796         for(i=1; i <= jp; i++ ) {
797             i1 = jp + 2 - i;
798             if( array[i1-1]  ) {
799                 if( array[i1-2] ) {
800                     k1 = i1 - 1;
801                     k2 = n - j1;
802                 }
803                 else {
804                     k1 = i1 - 1;
805                     k2 = n + 1 - j1;
806                 }
807                 goto leave;
808             }
809         }
810         k1 = 1;
811         k2 = n + 1 - m;
812     }
813   leave:
814     array[k1-1] = !array[k1-1];
815     array[k2-1] = !array[k2-1];
816 }
817
818
819 /* Generate a new prime number of PRIME_BITS bits and store it in
820    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
821    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
822    non-zero, allocate a new, NULL-terminated array holding the prime
823    factors and store it in FACTORS.  FLAGS might be used to influence
824    the prime number generation process.  */
825 gcry_error_t
826 gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
827                      unsigned int factor_bits, gcry_mpi_t **factors,
828                      gcry_prime_check_func_t cb_func, void *cb_arg,
829                      gcry_random_level_t random_level,
830                      unsigned int flags)
831 {
832   gcry_err_code_t err = GPG_ERR_NO_ERROR;
833   gcry_mpi_t *factors_generated = NULL;
834   gcry_mpi_t prime_generated = NULL;
835   unsigned int mode = 0;
836
837   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
838     mode = 1;
839
840   /* Generate.  */
841   err = prime_generate_internal (mode, &prime_generated, prime_bits,
842                                  factor_bits, NULL,
843                                  factors? &factors_generated : NULL,
844                                  random_level, flags, 1);
845
846   if (! err)
847     if (cb_func)
848       {
849         /* Additional check */
850         if (! (*cb_func) (cb_arg, 0, prime_generated))
851           {
852             /* Failed, deallocate resources.  */
853
854             unsigned int i;
855
856             mpi_free (prime_generated);
857             if (factors)
858               {
859                 for (i = 0; factors_generated[i]; i++)
860                   mpi_free (factors_generated[i]);
861                 gcry_free (factors_generated);
862               }
863             err = GPG_ERR_INTERNAL; /* FIXME.  */
864           }
865       }
866
867   if (! err)
868     {
869       if (factors)
870         *factors = factors_generated;
871       *prime = prime_generated;
872     }
873
874   return gcry_error (err);
875 }
876
877 /* Check wether the number X is prime.  */
878 gcry_error_t
879 gcry_prime_check (gcry_mpi_t x, unsigned int flags)
880 {
881   gcry_err_code_t err = GPG_ERR_NO_ERROR;
882   gcry_mpi_t test_value = mpi_alloc_set_ui (2); /* ? */
883
884   if (! check_prime (x, test_value))
885     err = GPG_ERR_NO_PRIME;
886
887   mpi_free (test_value);
888
889   return gcry_error (err);
890 }
891
892 /* Find a generator for PRIME where the factorization of (prime-1) is
893    in the NULL terminated array FACTORS. Return the generator as a
894    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
895    atart for the search. Returns 0 on success.*/
896 gcry_error_t
897 gcry_prime_group_generator (gcry_mpi_t *r_g,
898                             gcry_mpi_t prime, gcry_mpi_t *factors,
899                             gcry_mpi_t start_g)
900 {
901   gcry_mpi_t tmp = gcry_mpi_new (0);
902   gcry_mpi_t b = gcry_mpi_new (0);
903   gcry_mpi_t pmin1 = gcry_mpi_new (0);
904   gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
905   int first = 1;
906   int i, n;
907
908   if (!factors || !r_g || !prime)
909     return gpg_error (GPG_ERR_INV_ARG);
910
911   for (n=0; factors[n]; n++)
912     ;
913   if (n < 2)
914     return gpg_error (GPG_ERR_INV_ARG);
915
916 #if 1 /* Extra sanity check - usually disabled. */  
917   {
918     mpi_set (tmp, factors[0]);
919     for(i = 1; i < n; i++)
920         mpi_mul (tmp, tmp, factors[i]);
921     mpi_add_ui (tmp, tmp, 1);
922     if (mpi_cmp (prime, tmp))
923       return gpg_error (GPG_ERR_INV_ARG);
924   }
925 #endif /* Extra sanity check. */
926   
927   gcry_mpi_sub_ui (pmin1, prime, 1);      
928   do         
929     {
930       if (first)
931         first = 0;
932       else
933         gcry_mpi_add_ui (g, g, 1);
934       
935       if (DBG_CIPHER)
936         {
937           log_debug ("checking g:");
938           gcry_mpi_dump (g);
939           log_debug ("\n");
940         }
941       else
942         progress('^');
943       
944       for (i = 0; i < n; i++)
945         {
946           mpi_fdiv_q (tmp, pmin1, factors[i]);
947           gcry_mpi_powm (b, g, tmp, prime);
948           if (! mpi_cmp_ui (b, 1))
949             break;
950         }
951       if (DBG_CIPHER)
952         progress('\n');
953     }
954   while (i < n);
955   
956   gcry_mpi_release (tmp);
957   gcry_mpi_release (b); 
958   gcry_mpi_release (pmin1); 
959   *r_g = g; 
960
961   return 0; 
962 }
963
964 /* Convenience function to release the factors array. */
965 void
966 gcry_prime_release_factors (gcry_mpi_t *factors)
967 {
968   if (factors)
969     {
970       int i;
971       
972       for (i=0; factors[i]; i++)
973         mpi_free (factors[i]);
974       gcry_free (factors);
975     }
976 }