doc: Fix typo.
[libgcrypt.git] / cipher / primegen.c
1 /* primegen.c - prime number generator
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003
3  *               2004, 2008 Free Software Foundation, Inc.
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser general Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
20  */
21
22 #include <config.h>
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <errno.h>
28
29 #include "g10lib.h"
30 #include "mpi.h"
31 #include "cipher.h"
32
33 static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel,
34                              int (*extra_check)(void *, gcry_mpi_t),
35                              void *extra_check_arg);
36 static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
37                         gcry_prime_check_func_t cb_func, void *cb_arg );
38 static int is_prime (gcry_mpi_t n, int steps, unsigned int *count);
39 static void m_out_of_n( char *array, int m, int n );
40
41 static void (*progress_cb) (void *,const char*,int,int, int );
42 static void *progress_cb_data;
43
44 /* Note: 2 is not included because it can be tested more easily by
45    looking at bit 0. The last entry in this list is marked by a zero */
46 static ushort small_prime_numbers[] = {
47     3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
48     47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
49     103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
50     157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
51     211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
52     269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
53     331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
54     389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
55     449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
56     509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
57     587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
58     643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
59     709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
60     773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
61     853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
62     919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
63     991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
64     1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
65     1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
66     1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
67     1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
68     1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
69     1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
70     1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
71     1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
72     1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
73     1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
74     1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
75     1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
76     1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
77     1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
78     1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
79     1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
80     1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
81     2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
82     2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
83     2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
84     2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
85     2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
86     2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
87     2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
88     2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
89     2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
90     2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
91     2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
92     2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
93     2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
94     2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
95     2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
96     3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
97     3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
98     3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
99     3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
100     3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
101     3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
102     3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
103     3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
104     3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
105     3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
106     3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
107     3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
108     3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
109     3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
110     3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
111     4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
112     4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
113     4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
114     4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
115     4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
116     4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
117     4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
118     4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
119     4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
120     4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
121     4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
122     4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
123     4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
124     4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
125     4957, 4967, 4969, 4973, 4987, 4993, 4999,
126     0
127 };
128 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
129
130
131 \f
132 /* An object and a list to build up a global pool of primes.  See
133    save_pool_prime and get_pool_prime. */
134 struct primepool_s
135 {
136   struct primepool_s *next;
137   gcry_mpi_t prime;      /* If this is NULL the entry is not used. */
138   unsigned int nbits;
139   gcry_random_level_t randomlevel;
140 };
141 struct primepool_s *primepool;
142 /* Mutex used to protect access to the primepool.  */
143 GPGRT_LOCK_DEFINE (primepool_lock);
144
145
146 gcry_err_code_t
147 _gcry_primegen_init (void)
148 {
149   /* This function was formerly used to initialize the primepool
150      Mutex. This has been replace by a static initialization.  */
151   return 0;
152 }
153
154
155 /* Save PRIME which has been generated at RANDOMLEVEL for later
156    use. Needs to be called while primepool_lock is being hold.  Note
157    that PRIME should be considered released after calling this
158    function. */
159 static void
160 save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel)
161 {
162   struct primepool_s *item, *item2;
163   size_t n;
164
165   for (n=0, item = primepool; item; item = item->next, n++)
166     if (!item->prime)
167       break;
168   if (!item && n > 100)
169     {
170       /* Remove some of the entries.  Our strategy is removing
171          the last third from the list. */
172       int i;
173
174       for (i=0, item2 = primepool; item2; item2 = item2->next)
175         {
176           if (i >= n/3*2)
177             {
178               _gcry_mpi_release (item2->prime);
179               item2->prime = NULL;
180               if (!item)
181                 item = item2;
182             }
183         }
184     }
185   if (!item)
186     {
187       item = xtrycalloc (1, sizeof *item);
188       if (!item)
189         {
190           /* Out of memory.  Silently giving up. */
191           _gcry_mpi_release (prime);
192           return;
193         }
194       item->next = primepool;
195       primepool = item;
196     }
197   item->prime = prime;
198   item->nbits = mpi_get_nbits (prime);
199   item->randomlevel = randomlevel;
200 }
201
202
203 /* Return a prime for the prime pool or NULL if none has been found.
204    The prime needs to match NBITS and randomlevel. This function needs
205    to be called with the primepool_look is being hold. */
206 static gcry_mpi_t
207 get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel)
208 {
209   struct primepool_s *item;
210
211   for (item = primepool; item; item = item->next)
212     if (item->prime
213         && item->nbits == nbits && item->randomlevel == randomlevel)
214       {
215         gcry_mpi_t prime = item->prime;
216         item->prime = NULL;
217         gcry_assert (nbits == mpi_get_nbits (prime));
218         return prime;
219       }
220   return NULL;
221 }
222
223
224
225
226
227 \f
228 void
229 _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
230                                    void *cb_data )
231 {
232   progress_cb = cb;
233   progress_cb_data = cb_data;
234 }
235
236
237 static void
238 progress( int c )
239 {
240   if ( progress_cb )
241     progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
242 }
243
244
245 /****************
246  * Generate a prime number (stored in secure memory)
247  */
248 gcry_mpi_t
249 _gcry_generate_secret_prime (unsigned int nbits,
250                              gcry_random_level_t random_level,
251                              int (*extra_check)(void*, gcry_mpi_t),
252                              void *extra_check_arg)
253 {
254   gcry_mpi_t prime;
255
256   prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg);
257   progress('\n');
258   return prime;
259 }
260
261
262 /* Generate a prime number which may be public, i.e. not allocated in
263    secure memory.  */
264 gcry_mpi_t
265 _gcry_generate_public_prime (unsigned int nbits,
266                              gcry_random_level_t random_level,
267                              int (*extra_check)(void*, gcry_mpi_t),
268                              void *extra_check_arg)
269 {
270   gcry_mpi_t prime;
271
272   prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg);
273   progress('\n');
274   return prime;
275 }
276
277
278 /* Core prime generation function.  The algorithm used to generate
279    practically save primes is due to Lim and Lee as described in the
280    CRYPTO '97 proceedings (ISBN3540633847) page 260.
281
282    NEED_Q_FACTOR: If true make sure that at least one factor is of
283                   size qbits.  This is for example required for DSA.
284    PRIME_GENERATED: Adresss of a variable where the resulting prime
285                     number will be stored.
286    PBITS: Requested size of the prime number.  At least 48.
287    QBITS: One factor of the prime needs to be of this size.  Maybe 0
288           if this is not required.  See also MODE.
289    G: If not NULL an MPI which will receive a generator for the prime
290       for use with Elgamal.
291    RET_FACTORS: if not NULL, an array with all factors are stored at
292                 that address.
293    ALL_FACTORS: If set to true all factors of prime-1 are returned.
294    RANDOMLEVEL:  How strong should the random numers be.
295    FLAGS: Prime generation bit flags. Currently supported:
296           GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret.
297    CB_FUNC, CB_ARG:  Callback to be used for extra checks.
298
299  */
300 static gcry_err_code_t
301 prime_generate_internal (int need_q_factor,
302                          gcry_mpi_t *prime_generated, unsigned int pbits,
303                          unsigned int qbits, gcry_mpi_t g,
304                          gcry_mpi_t **ret_factors,
305                          gcry_random_level_t randomlevel, unsigned int flags,
306                          int all_factors,
307                          gcry_prime_check_func_t cb_func, void *cb_arg)
308 {
309   gcry_err_code_t err = 0;
310   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
311                                      caller.  */
312   gcry_mpi_t *factors = NULL;   /* Current factors.  */
313   gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */
314   gcry_mpi_t *pool = NULL;      /* Pool of primes.  */
315   int *pool_in_use = NULL;      /* Array with currently used POOL elements. */
316   unsigned char *perms = NULL;  /* Permutations of POOL.  */
317   gcry_mpi_t q_factor = NULL;   /* Used if QBITS is non-zero.  */
318   unsigned int fbits = 0;       /* Length of prime factors.  */
319   unsigned int n = 0;           /* Number of factors.  */
320   unsigned int m = 0;           /* Number of primes in pool.  */
321   gcry_mpi_t q = NULL;          /* First prime factor.  */
322   gcry_mpi_t prime = NULL;      /* Prime candidate.  */
323   unsigned int nprime = 0;      /* Bits of PRIME.  */
324   unsigned int req_qbits;       /* The original QBITS value.  */
325   gcry_mpi_t val_2;             /* For check_prime().  */
326   int is_locked = 0;            /* Flag to help unlocking the primepool. */
327   unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
328   unsigned int count1 = 0, count2 = 0;
329   unsigned int i = 0, j = 0;
330
331   if (pbits < 48)
332     return GPG_ERR_INV_ARG;
333
334   /* We won't use a too strong random elvel for the pooled subprimes. */
335   poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM?
336                      GCRY_STRONG_RANDOM : randomlevel);
337
338
339   /* If QBITS is not given, assume a reasonable value. */
340   if (!qbits)
341     qbits = pbits / 3;
342
343   req_qbits = qbits;
344
345   /* Find number of needed prime factors N.  */
346   for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++)
347     ;
348   n--;
349
350   val_2 = mpi_alloc_set_ui (2);
351
352   if ((! n) || ((need_q_factor) && (n < 2)))
353     {
354       err = GPG_ERR_INV_ARG;
355       goto leave;
356     }
357
358   if (need_q_factor)
359     {
360       n--;  /* Need one factor less because we want a specific Q-FACTOR. */
361       fbits = (pbits - 2 * req_qbits -1) / n;
362       qbits =  pbits - req_qbits - n * fbits;
363     }
364   else
365     {
366       fbits = (pbits - req_qbits -1) / n;
367       qbits = pbits - n * fbits;
368     }
369
370   if (DBG_CIPHER)
371     log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
372                pbits, req_qbits, qbits, fbits, n);
373
374   /* Allocate an integer to old the new prime. */
375   prime = mpi_new (pbits);
376
377   /* Generate first prime factor.  */
378   q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
379
380   /* Generate a specific Q-Factor if requested. */
381   if (need_q_factor)
382     q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
383
384   /* Allocate an array to hold all factors + 2 for later usage.  */
385   factors = xtrycalloc (n + 2, sizeof (*factors));
386   if (!factors)
387     {
388       err = gpg_err_code_from_errno (errno);
389       goto leave;
390     }
391
392   /* Allocate an array to track pool usage. */
393   pool_in_use = xtrymalloc (n * sizeof *pool_in_use);
394   if (!pool_in_use)
395     {
396       err = gpg_err_code_from_errno (errno);
397       goto leave;
398     }
399   for (i=0; i < n; i++)
400     pool_in_use[i] = -1;
401
402   /* Make a pool of 3n+5 primes (this is an arbitrary value).  We
403      require at least 30 primes for are useful selection process.
404
405      Fixme: We need to research the best formula for sizing the pool.
406   */
407   m = n * 3 + 5;
408   if (need_q_factor) /* Need some more in this case. */
409     m += 5;
410   if (m < 30)
411     m = 30;
412   pool = xtrycalloc (m , sizeof (*pool));
413   if (! pool)
414     {
415       err = gpg_err_code_from_errno (errno);
416       goto leave;
417     }
418
419   /* Permutate over the pool of primes until we find a prime of the
420      requested length.  */
421   do
422     {
423     next_try:
424       for (i=0; i < n; i++)
425         pool_in_use[i] = -1;
426
427       if (!perms)
428         {
429           /* Allocate new primes.  This is done right at the beginning
430              of the loop and if we have later run out of primes. */
431           for (i = 0; i < m; i++)
432             {
433               mpi_free (pool[i]);
434               pool[i] = NULL;
435             }
436
437           /* Init m_out_of_n().  */
438           perms = xtrycalloc (1, m);
439           if (!perms)
440             {
441               err = gpg_err_code_from_errno (errno);
442               goto leave;
443             }
444
445           err = gpgrt_lock_lock (&primepool_lock);
446           if (err)
447             goto leave;
448           is_locked = 1;
449
450           for (i = 0; i < n; i++)
451             {
452               perms[i] = 1;
453               /* At a maximum we use strong random for the factors.
454                  This saves us a lot of entropy. Given that Q and
455                  possible Q-factor are also used in the final prime
456                  this should be acceptable.  We also don't allocate in
457                  secure memory to save on that scare resource too.  If
458                  Q has been allocated in secure memory, the final
459                  prime will be saved there anyway.  This is because
460                  our MPI routines take care of that.  GnuPG has worked
461                  this way ever since.  */
462               pool[i] = NULL;
463               if (is_locked)
464                 {
465                   pool[i] = get_pool_prime (fbits, poolrandomlevel);
466                   if (!pool[i])
467                     {
468                       err = gpgrt_lock_unlock (&primepool_lock);
469                       if (err)
470                         goto leave;
471                       is_locked = 0;
472                     }
473                 }
474               if (!pool[i])
475                 pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
476               pool_in_use[i] = i;
477               factors[i] = pool[i];
478             }
479
480           if (is_locked && (err = gpgrt_lock_unlock (&primepool_lock)))
481             goto leave;
482           is_locked = 0;
483         }
484       else
485         {
486           /* Get next permutation. */
487           m_out_of_n ( (char*)perms, n, m);
488
489           if ((err = gpgrt_lock_lock (&primepool_lock)))
490             goto leave;
491           is_locked = 1;
492
493           for (i = j = 0; (i < m) && (j < n); i++)
494             if (perms[i])
495               {
496                 /* If the subprime has not yet beed generated do it now. */
497                 if (!pool[i] && is_locked)
498                   {
499                     pool[i] = get_pool_prime (fbits, poolrandomlevel);
500                     if (!pool[i])
501                       {
502                         if ((err = gpgrt_lock_unlock (&primepool_lock)))
503                           goto leave;
504                         is_locked = 0;
505                       }
506                   }
507                 if (!pool[i])
508                   pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL);
509                 pool_in_use[j] = i;
510                 factors[j++] = pool[i];
511               }
512
513           if (is_locked && (err = gpgrt_lock_unlock (&primepool_lock)))
514             goto leave;
515           is_locked = 0;
516
517           if (i == n)
518             {
519               /* Ran out of permutations: Allocate new primes.  */
520               xfree (perms);
521               perms = NULL;
522               progress ('!');
523               goto next_try;
524             }
525         }
526
527         /* Generate next prime candidate:
528            p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.
529          */
530         mpi_set (prime, q);
531         mpi_mul_ui (prime, prime, 2);
532         if (need_q_factor)
533           mpi_mul (prime, prime, q_factor);
534         for(i = 0; i < n; i++)
535           mpi_mul (prime, prime, factors[i]);
536         mpi_add_ui (prime, prime, 1);
537         nprime = mpi_get_nbits (prime);
538
539         if (nprime < pbits)
540           {
541             if (++count1 > 20)
542               {
543                 count1 = 0;
544                 qbits++;
545                 progress('>');
546                 mpi_free (q);
547                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
548                 goto next_try;
549               }
550           }
551         else
552           count1 = 0;
553
554         if (nprime > pbits)
555           {
556             if (++count2 > 20)
557               {
558                 count2 = 0;
559                 qbits--;
560                 progress('<');
561                 mpi_free (q);
562                 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
563                 goto next_try;
564               }
565           }
566         else
567           count2 = 0;
568     }
569   while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
570                                               cb_func, cb_arg)));
571
572   if (DBG_CIPHER)
573     {
574       progress ('\n');
575       log_mpidump ("prime    ", prime);
576       log_mpidump ("factor  q", q);
577       if (need_q_factor)
578         log_mpidump ("factor q0", q_factor);
579       for (i = 0; i < n; i++)
580         log_mpidump ("factor pi", factors[i]);
581       log_debug ("bit sizes: prime=%u, q=%u",
582                  mpi_get_nbits (prime), mpi_get_nbits (q));
583       if (need_q_factor)
584         log_printf (", q0=%u", mpi_get_nbits (q_factor));
585       for (i = 0; i < n; i++)
586         log_printf (", p%d=%u", i, mpi_get_nbits (factors[i]));
587       log_printf ("\n");
588     }
589
590   if (ret_factors)
591     {
592       /* Caller wants the factors.  */
593       factors_new = xtrycalloc (n + 4, sizeof (*factors_new));
594       if (! factors_new)
595         {
596           err = gpg_err_code_from_errno (errno);
597           goto leave;
598         }
599
600       if (all_factors)
601         {
602           i = 0;
603           factors_new[i++] = mpi_set_ui (NULL, 2);
604           factors_new[i++] = mpi_copy (q);
605           if (need_q_factor)
606             factors_new[i++] = mpi_copy (q_factor);
607           for(j=0; j < n; j++)
608             factors_new[i++] = mpi_copy (factors[j]);
609         }
610       else
611         {
612           i = 0;
613           if (need_q_factor)
614             {
615               factors_new[i++] = mpi_copy (q_factor);
616               for (; i <= n; i++)
617                 factors_new[i] = mpi_copy (factors[i]);
618             }
619           else
620             for (; i < n; i++ )
621               factors_new[i] = mpi_copy (factors[i]);
622         }
623     }
624
625   if (g && need_q_factor)
626     err = GPG_ERR_NOT_IMPLEMENTED;
627   else if (g)
628     {
629       /* Create a generator (start with 3).  */
630       gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
631       gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
632       gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
633
634       factors[n] = q;
635       factors[n + 1] = mpi_alloc_set_ui (2);
636       mpi_sub_ui (pmin1, prime, 1);
637       mpi_set_ui (g, 2);
638       do
639         {
640           mpi_add_ui (g, g, 1);
641           if (DBG_CIPHER)
642             log_printmpi ("checking g", g);
643           else
644             progress('^');
645           for (i = 0; i < n + 2; i++)
646             {
647               mpi_fdiv_q (tmp, pmin1, factors[i]);
648               /* No mpi_pow(), but it is okay to use this with mod
649                  prime.  */
650               mpi_powm (b, g, tmp, prime);
651               if (! mpi_cmp_ui (b, 1))
652                 break;
653             }
654           if (DBG_CIPHER)
655             progress('\n');
656         }
657       while (i < n + 2);
658
659       mpi_free (factors[n+1]);
660       mpi_free (tmp);
661       mpi_free (b);
662       mpi_free (pmin1);
663     }
664
665   if (! DBG_CIPHER)
666     progress ('\n');
667
668
669  leave:
670   if (pool)
671     {
672       is_locked = !gpgrt_lock_lock (&primepool_lock);
673       for(i = 0; i < m; i++)
674         {
675           if (pool[i])
676             {
677               for (j=0; j < n; j++)
678                 if (pool_in_use[j] == i)
679                   break;
680               if (j == n && is_locked)
681                 {
682                   /* This pooled subprime has not been used. */
683                   save_pool_prime (pool[i], poolrandomlevel);
684                 }
685               else
686                 mpi_free (pool[i]);
687             }
688         }
689       if (is_locked)
690         err = gpgrt_lock_unlock (&primepool_lock);
691       is_locked = 0;
692       xfree (pool);
693     }
694   xfree (pool_in_use);
695   if (factors)
696     xfree (factors);  /* Factors are shallow copies.  */
697   if (perms)
698     xfree (perms);
699
700   mpi_free (val_2);
701   mpi_free (q);
702   mpi_free (q_factor);
703
704   if (! err)
705     {
706       *prime_generated = prime;
707       if (ret_factors)
708         *ret_factors = factors_new;
709     }
710   else
711     {
712       if (factors_new)
713         {
714           for (i = 0; factors_new[i]; i++)
715             mpi_free (factors_new[i]);
716           xfree (factors_new);
717         }
718       mpi_free (prime);
719     }
720
721   return err;
722 }
723
724
725 /* Generate a prime used for discrete logarithm algorithms; i.e. this
726    prime will be public and no strong random is required.  On success
727    R_PRIME receives a new MPI with the prime.  On error R_PRIME is set
728    to NULL and an error code is returned.  If RET_FACTORS is not NULL
729    it is set to an allocated array of factors on success or to NULL on
730    error.  */
731 gcry_err_code_t
732 _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
733                           gcry_mpi_t g,
734                           gcry_mpi_t *r_prime, gcry_mpi_t **ret_factors)
735 {
736   *r_prime = NULL;
737   if (ret_factors)
738     *ret_factors = NULL;
739   return prime_generate_internal ((mode == 1), r_prime, pbits, qbits, g,
740                                   ret_factors, GCRY_WEAK_RANDOM, 0, 0,
741                                   NULL, NULL);
742 }
743
744
745 static gcry_mpi_t
746 gen_prime (unsigned int nbits, int secret, int randomlevel,
747            int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
748 {
749   gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
750   int i;
751   unsigned int x, step;
752   unsigned int count1, count2;
753   int *mods;
754
755 /*   if (  DBG_CIPHER ) */
756 /*     log_debug ("generate a prime of %u bits ", nbits ); */
757
758   if (nbits < 16)
759     log_fatal ("can't generate a prime with less than %d bits\n", 16);
760
761   mods = xmalloc (no_of_small_prime_numbers * sizeof *mods);
762   /* Make nbits fit into gcry_mpi_t implementation. */
763   val_2  = mpi_alloc_set_ui( 2 );
764   val_3 = mpi_alloc_set_ui( 3);
765   prime  = secret? mpi_snew (nbits): mpi_new (nbits);
766   result = mpi_alloc_like( prime );
767   pminus1= mpi_alloc_like( prime );
768   ptest  = mpi_alloc_like( prime );
769   count1 = count2 = 0;
770   for (;;)
771     {  /* try forvever */
772       int dotcount=0;
773
774       /* generate a random number */
775       _gcry_mpi_randomize( prime, nbits, randomlevel );
776
777       /* Set high order bit to 1, set low order bit to 1.  If we are
778          generating a secret prime we are most probably doing that
779          for RSA, to make sure that the modulus does have the
780          requested key size we set the 2 high order bits. */
781       mpi_set_highbit (prime, nbits-1);
782       if (secret)
783         mpi_set_bit (prime, nbits-2);
784       mpi_set_bit(prime, 0);
785
786       /* Calculate all remainders. */
787       for (i=0; (x = small_prime_numbers[i]); i++ )
788         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
789
790       /* Now try some primes starting with prime. */
791       for(step=0; step < 20000; step += 2 )
792         {
793           /* Check against all the small primes we have in mods. */
794           count1++;
795           for (i=0; (x = small_prime_numbers[i]); i++ )
796             {
797               while ( mods[i] + step >= x )
798                 mods[i] -= x;
799               if ( !(mods[i] + step) )
800                 break;
801             }
802           if ( x )
803             continue;   /* Found a multiple of an already known prime. */
804
805           mpi_add_ui( ptest, prime, step );
806
807           /* Do a fast Fermat test now. */
808           count2++;
809           mpi_sub_ui( pminus1, ptest, 1);
810           mpi_powm( result, val_2, pminus1, ptest );
811           if ( !mpi_cmp_ui( result, 1 ) )
812             {
813               /* Not composite, perform stronger tests */
814               if (is_prime(ptest, 5, &count2 ))
815                 {
816                   if (!mpi_test_bit( ptest, nbits-1-secret ))
817                     {
818                       progress('\n');
819                       log_debug ("overflow in prime generation\n");
820                       break; /* Stop loop, continue with a new prime. */
821                     }
822
823                   if (extra_check && extra_check (extra_check_arg, ptest))
824                     {
825                       /* The extra check told us that this prime is
826                          not of the caller's taste. */
827                       progress ('/');
828                     }
829                   else
830                     {
831                       /* Got it. */
832                       mpi_free(val_2);
833                       mpi_free(val_3);
834                       mpi_free(result);
835                       mpi_free(pminus1);
836                       mpi_free(prime);
837                       xfree(mods);
838                       return ptest;
839                     }
840                 }
841             }
842           if (++dotcount == 10 )
843             {
844               progress('.');
845               dotcount = 0;
846             }
847         }
848       progress(':'); /* restart with a new random value */
849     }
850 }
851
852 /****************
853  * Returns: true if this may be a prime
854  * RM_ROUNDS gives the number of Rabin-Miller tests to run.
855  */
856 static int
857 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
858              gcry_prime_check_func_t cb_func, void *cb_arg)
859 {
860   int i;
861   unsigned int x;
862   unsigned int count=0;
863
864   /* Check against small primes. */
865   for (i=0; (x = small_prime_numbers[i]); i++ )
866     {
867       if ( mpi_divisible_ui( prime, x ) )
868         return !mpi_cmp_ui (prime, x);
869     }
870
871   /* A quick Fermat test. */
872   {
873     gcry_mpi_t result = mpi_alloc_like( prime );
874     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
875     mpi_sub_ui( pminus1, prime, 1);
876     mpi_powm( result, val_2, pminus1, prime );
877     mpi_free( pminus1 );
878     if ( mpi_cmp_ui( result, 1 ) )
879       {
880         /* Is composite. */
881         mpi_free( result );
882         progress('.');
883         return 0;
884       }
885     mpi_free( result );
886   }
887
888   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
889     {
890       /* Perform stronger tests. */
891       if ( is_prime( prime, rm_rounds, &count ) )
892         {
893           if (!cb_func
894               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
895             return 1; /* Probably a prime. */
896         }
897     }
898   progress('.');
899   return 0;
900 }
901
902
903 /*
904  * Return true if n is probably a prime
905  */
906 static int
907 is_prime (gcry_mpi_t n, int steps, unsigned int *count)
908 {
909   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
910   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
911   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
912   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
913   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
914   gcry_mpi_t q;
915   unsigned i, j, k;
916   int rc = 0;
917   unsigned nbits = mpi_get_nbits( n );
918
919   if (steps < 5) /* Make sure that we do at least 5 rounds. */
920     steps = 5;
921
922   mpi_sub_ui( nminus1, n, 1 );
923
924   /* Find q and k, so that n = 1 + 2^k * q . */
925   q = mpi_copy ( nminus1 );
926   k = mpi_trailing_zeros ( q );
927   mpi_tdiv_q_2exp (q, q, k);
928
929   for (i=0 ; i < steps; i++ )
930     {
931       ++*count;
932       if( !i )
933         {
934           mpi_set_ui( x, 2 );
935         }
936       else
937         {
938           _gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
939
940           /* Make sure that the number is smaller than the prime and
941              keep the randomness of the high bit. */
942           if ( mpi_test_bit ( x, nbits-2) )
943             {
944               mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
945             }
946           else
947             {
948               mpi_set_highbit( x, nbits-2 );
949               mpi_clear_bit( x, nbits-2 );
950             }
951           gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0);
952         }
953       mpi_powm ( y, x, q, n);
954       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
955         {
956           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
957             {
958               mpi_powm(y, y, a2, n);
959               if( !mpi_cmp_ui( y, 1 ) )
960                 goto leave; /* Not a prime. */
961             }
962           if (mpi_cmp( y, nminus1 ) )
963             goto leave; /* Not a prime. */
964         }
965       progress('+');
966     }
967   rc = 1; /* May be a prime. */
968
969  leave:
970   mpi_free( x );
971   mpi_free( y );
972   mpi_free( z );
973   mpi_free( nminus1 );
974   mpi_free( q );
975   mpi_free( a2 );
976
977   return rc;
978 }
979
980
981 /* Given ARRAY of size N with M elements set to true produce a
982    modified array with the next permutation of M elements.  Note, that
983    ARRAY is used in a one-bit-per-byte approach.  To detected the last
984    permutation it is useful to initialize the array with the first M
985    element set to true and use this test:
986        m_out_of_n (array, m, n);
987        for (i = j = 0; i < n && j < m; i++)
988          if (array[i])
989            j++;
990        if (j == m)
991          goto ready;
992
993    This code is based on the algorithm 452 from the "Collected
994    Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
995 */
996 static void
997 m_out_of_n ( char *array, int m, int n )
998 {
999   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
1000
1001   if( !m || m >= n )
1002     return;
1003
1004   /* Need to handle this simple case separately. */
1005   if( m == 1 )
1006     {
1007       for (i=0; i < n; i++ )
1008         {
1009           if ( array[i] )
1010             {
1011               array[i++] = 0;
1012               if( i >= n )
1013                 i = 0;
1014               array[i] = 1;
1015               return;
1016             }
1017         }
1018       BUG();
1019     }
1020
1021
1022   for (j=1; j < n; j++ )
1023     {
1024       if ( array[n-1] == array[n-j-1])
1025         continue;
1026       j1 = j;
1027       break;
1028     }
1029
1030   if ( (m & 1) )
1031     {
1032       /* M is odd. */
1033       if( array[n-1] )
1034         {
1035           if( j1 & 1 )
1036             {
1037               k1 = n - j1;
1038               k2 = k1+2;
1039               if( k2 > n )
1040                 k2 = n;
1041               goto leave;
1042             }
1043           goto scan;
1044         }
1045       k2 = n - j1 - 1;
1046       if( k2 == 0 )
1047         {
1048           k1 = i;
1049           k2 = n - j1;
1050         }
1051       else if( array[k2] && array[k2-1] )
1052         k1 = n;
1053       else
1054         k1 = k2 + 1;
1055     }
1056   else
1057     {
1058       /* M is even. */
1059       if( !array[n-1] )
1060         {
1061           k1 = n - j1;
1062           k2 = k1 + 1;
1063           goto leave;
1064         }
1065
1066       if( !(j1 & 1) )
1067         {
1068           k1 = n - j1;
1069           k2 = k1+2;
1070           if( k2 > n )
1071             k2 = n;
1072           goto leave;
1073         }
1074     scan:
1075       jp = n - j1 - 1;
1076       for (i=1; i <= jp; i++ )
1077         {
1078           i1 = jp + 2 - i;
1079           if( array[i1-1]  )
1080             {
1081               if( array[i1-2] )
1082                 {
1083                   k1 = i1 - 1;
1084                   k2 = n - j1;
1085                 }
1086               else
1087                 {
1088                   k1 = i1 - 1;
1089                   k2 = n + 1 - j1;
1090                 }
1091               goto leave;
1092             }
1093         }
1094       k1 = 1;
1095       k2 = n + 1 - m;
1096     }
1097  leave:
1098   /* Now complement the two selected bits. */
1099   array[k1-1] = !array[k1-1];
1100   array[k2-1] = !array[k2-1];
1101 }
1102
1103
1104 /* Generate a new prime number of PRIME_BITS bits and store it in
1105    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
1106    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
1107    non-zero, allocate a new, NULL-terminated array holding the prime
1108    factors and store it in FACTORS.  FLAGS might be used to influence
1109    the prime number generation process.  */
1110 gcry_err_code_t
1111 _gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1112                       unsigned int factor_bits, gcry_mpi_t **factors,
1113                       gcry_prime_check_func_t cb_func, void *cb_arg,
1114                       gcry_random_level_t random_level,
1115                       unsigned int flags)
1116 {
1117   gcry_err_code_t rc = 0;
1118   gcry_mpi_t *factors_generated = NULL;
1119   gcry_mpi_t prime_generated = NULL;
1120   unsigned int mode = 0;
1121
1122   if (!prime)
1123     return GPG_ERR_INV_ARG;
1124   *prime = NULL;
1125
1126   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1127     mode = 1;
1128
1129   /* Generate.  */
1130   rc = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1131                                 factor_bits, NULL,
1132                                 factors? &factors_generated : NULL,
1133                                 random_level, flags, 1,
1134                                 cb_func, cb_arg);
1135
1136   if (!rc && cb_func)
1137     {
1138       /* Additional check. */
1139       if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1140         {
1141           /* Failed, deallocate resources.  */
1142           unsigned int i;
1143
1144           mpi_free (prime_generated);
1145           if (factors)
1146             {
1147               for (i = 0; factors_generated[i]; i++)
1148                 mpi_free (factors_generated[i]);
1149               xfree (factors_generated);
1150             }
1151           rc = GPG_ERR_GENERAL;
1152         }
1153     }
1154
1155   if (!rc)
1156     {
1157       if (factors)
1158         *factors = factors_generated;
1159       *prime = prime_generated;
1160     }
1161
1162   return rc;
1163 }
1164
1165 /* Check whether the number X is prime.  */
1166 gcry_err_code_t
1167 _gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1168 {
1169   (void)flags;
1170
1171   switch (mpi_cmp_ui (x, 2))
1172     {
1173     case 0:  return 0;                /* 2 is a prime */
1174     case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes.  */
1175     }
1176
1177   /* We use 64 rounds because the prime we are going to test is not
1178      guaranteed to be a random one. */
1179   if (check_prime (x, mpi_const (MPI_C_TWO), 64, NULL, NULL))
1180     return 0;
1181
1182   return GPG_ERR_NO_PRIME;
1183 }
1184
1185 /* Find a generator for PRIME where the factorization of (prime-1) is
1186    in the NULL terminated array FACTORS. Return the generator as a
1187    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1188    atart for the search. Returns 0 on success.*/
1189 gcry_err_code_t
1190 _gcry_prime_group_generator (gcry_mpi_t *r_g,
1191                              gcry_mpi_t prime, gcry_mpi_t *factors,
1192                              gcry_mpi_t start_g)
1193 {
1194   gcry_mpi_t tmp, b, pmin1, g;
1195   int first, i, n;
1196
1197   if (!r_g)
1198     return GPG_ERR_INV_ARG;
1199   *r_g = NULL;
1200   if (!factors || !prime)
1201     return GPG_ERR_INV_ARG;
1202
1203   for (n=0; factors[n]; n++)
1204     ;
1205   if (n < 2)
1206     return GPG_ERR_INV_ARG;
1207
1208   tmp   = mpi_new (0);
1209   b     = mpi_new (0);
1210   pmin1 = mpi_new (0);
1211   g     = start_g? mpi_copy (start_g) : mpi_set_ui (NULL, 3);
1212
1213   /* Extra sanity check - usually disabled. */
1214 /*   mpi_set (tmp, factors[0]); */
1215 /*   for(i = 1; i < n; i++) */
1216 /*     mpi_mul (tmp, tmp, factors[i]); */
1217 /*   mpi_add_ui (tmp, tmp, 1); */
1218 /*   if (mpi_cmp (prime, tmp)) */
1219 /*     return gpg_error (GPG_ERR_INV_ARG); */
1220
1221   mpi_sub_ui (pmin1, prime, 1);
1222   first = 1;
1223   do
1224     {
1225       if (first)
1226         first = 0;
1227       else
1228         mpi_add_ui (g, g, 1);
1229
1230       if (DBG_CIPHER)
1231         log_printmpi ("checking g", g);
1232       else
1233         progress('^');
1234
1235       for (i = 0; i < n; i++)
1236         {
1237           mpi_fdiv_q (tmp, pmin1, factors[i]);
1238           mpi_powm (b, g, tmp, prime);
1239           if (! mpi_cmp_ui (b, 1))
1240             break;
1241         }
1242       if (DBG_CIPHER)
1243         progress('\n');
1244     }
1245   while (i < n);
1246
1247   _gcry_mpi_release (tmp);
1248   _gcry_mpi_release (b);
1249   _gcry_mpi_release (pmin1);
1250   *r_g = g;
1251
1252   return 0;
1253 }
1254
1255 /* Convenience function to release the factors array. */
1256 void
1257 _gcry_prime_release_factors (gcry_mpi_t *factors)
1258 {
1259   if (factors)
1260     {
1261       int i;
1262
1263       for (i=0; factors[i]; i++)
1264         mpi_free (factors[i]);
1265       xfree (factors);
1266     }
1267 }
1268
1269
1270 \f
1271 /* Helper for _gcry_derive_x931_prime.  */
1272 static gcry_mpi_t
1273 find_x931_prime (const gcry_mpi_t pfirst)
1274 {
1275   gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1276   gcry_mpi_t prime;
1277
1278   prime = mpi_copy (pfirst);
1279   /* If P is even add 1.  */
1280   mpi_set_bit (prime, 0);
1281
1282   /* We use 64 Rabin-Miller rounds which is better and thus
1283      sufficient.  We do not have a Lucas test implementaion thus we
1284      can't do it in the X9.31 preferred way of running a few
1285      Rabin-Miller followed by one Lucas test.  */
1286   while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1287     mpi_add_ui (prime, prime, 2);
1288
1289   mpi_free (val_2);
1290
1291   return prime;
1292 }
1293
1294
1295 /* Generate a prime using the algorithm from X9.31 appendix B.4.
1296
1297    This function requires that the provided public exponent E is odd.
1298    XP, XP1 and XP2 are the seed values.  All values are mandatory.
1299
1300    On success the prime is returned.  If R_P1 or R_P2 are given the
1301    internal values P1 and P2 are saved at these addresses.  On error
1302    NULL is returned.  */
1303 gcry_mpi_t
1304 _gcry_derive_x931_prime (const gcry_mpi_t xp,
1305                          const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1306                          const gcry_mpi_t e,
1307                          gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1308 {
1309   gcry_mpi_t p1, p2, p1p2, yp0;
1310
1311   if (!xp || !xp1 || !xp2)
1312     return NULL;
1313   if (!e || !mpi_test_bit (e, 0))
1314     return NULL;  /* We support only odd values for E.  */
1315
1316   p1 = find_x931_prime (xp1);
1317   p2 = find_x931_prime (xp2);
1318   p1p2 = mpi_alloc_like (xp);
1319   mpi_mul (p1p2, p1, p2);
1320
1321   {
1322     gcry_mpi_t r1, tmp;
1323
1324     /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1325     tmp = mpi_alloc_like (p1);
1326     mpi_invm (tmp, p2, p1);
1327     mpi_mul (tmp, tmp, p2);
1328     r1 = tmp;
1329
1330     tmp = mpi_alloc_like (p2);
1331     mpi_invm (tmp, p1, p2);
1332     mpi_mul (tmp, tmp, p1);
1333     mpi_sub (r1, r1, tmp);
1334
1335     /* Fixup a negative value.  */
1336     if (mpi_has_sign (r1))
1337       mpi_add (r1, r1, p1p2);
1338
1339     /* yp0 = xp + (r1 - xp mod p1*p2)  */
1340     yp0 = tmp; tmp = NULL;
1341     mpi_subm (yp0, r1, xp, p1p2);
1342     mpi_add (yp0, yp0, xp);
1343     mpi_free (r1);
1344
1345     /* Fixup a negative value.  */
1346     if (mpi_cmp (yp0, xp) < 0 )
1347       mpi_add (yp0, yp0, p1p2);
1348   }
1349
1350   /* yp0 is now the first integer greater than xp with p1 being a
1351      large prime factor of yp0-1 and p2 a large prime factor of yp0+1.  */
1352
1353   /* Note that the first example from X9.31 (D.1.1) which uses
1354        (Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1355        (Xq2 #134E4CAA16D2350A21D775C404#)
1356        (Xq  #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1357              7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1358              6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1359              321DE34A#))))
1360      returns an yp0 of
1361             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1362              7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1363              BF20CB896EE37E098A906313271422162CB6C642
1364              75C1201F#
1365      and not
1366             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1367              7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1368              C88FE299D52D78BE405A97E01FD71DD7819ECB91
1369              FA85A076#
1370      as stated in the standard.  This seems to be a bug in X9.31.
1371    */
1372
1373   {
1374     gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1375     gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1376     int gcdres;
1377
1378     mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body.  */
1379     mpi_sub_ui (yp0, yp0, 1);   /* Ditto.  */
1380     for (;;)
1381       {
1382         gcdres = mpi_gcd (gcdtmp, e, yp0);
1383         mpi_add_ui (yp0, yp0, 1);
1384         if (!gcdres)
1385           progress ('/');  /* gcd (e, yp0-1) != 1  */
1386         else if (check_prime (yp0, val_2, 64, NULL, NULL))
1387           break; /* Found.  */
1388         /* We add p1p2-1 because yp0 is incremented after the gcd test.  */
1389         mpi_add (yp0, yp0, p1p2);
1390       }
1391     mpi_free (gcdtmp);
1392     mpi_free (val_2);
1393   }
1394
1395   mpi_free (p1p2);
1396
1397   progress('\n');
1398   if (r_p1)
1399     *r_p1 = p1;
1400   else
1401     mpi_free (p1);
1402   if (r_p2)
1403     *r_p2 = p2;
1404   else
1405     mpi_free (p2);
1406   return yp0;
1407 }
1408
1409
1410 \f
1411 /* Generate the two prime used for DSA using the algorithm specified
1412    in FIPS 186-2.  PBITS is the desired length of the prime P and a
1413    QBITS the length of the prime Q.  If SEED is not supplied and
1414    SEEDLEN is 0 the function generates an appropriate SEED.  On
1415    success the generated primes are stored at R_Q and R_P, the counter
1416    value is stored at R_COUNTER and the seed actually used for
1417    generation is stored at R_SEED and R_SEEDVALUE.  */
1418 gpg_err_code_t
1419 _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1420                                 const void *seed, size_t seedlen,
1421                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1422                                 int *r_counter,
1423                                 void **r_seed, size_t *r_seedlen)
1424 {
1425   gpg_err_code_t ec;
1426   unsigned char seed_help_buffer[160/8];  /* Used to hold a generated SEED. */
1427   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1428   unsigned char digest[160/8];  /* Helper buffer for SHA-1 digest.  */
1429   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1430   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1431   int i;
1432
1433   unsigned char value_u[160/8];
1434   int value_n, value_b, value_k;
1435   int counter;
1436   gcry_mpi_t value_w = NULL;
1437   gcry_mpi_t value_x = NULL;
1438   gcry_mpi_t prime_q = NULL;
1439   gcry_mpi_t prime_p = NULL;
1440
1441   /* FIPS 186-2 allows only for 1024/160 bit.  */
1442   if (pbits != 1024 || qbits != 160)
1443     return GPG_ERR_INV_KEYLEN;
1444
1445   if (!seed && !seedlen)
1446     ; /* No seed value given:  We are asked to generate it.  */
1447   else if (!seed || seedlen < qbits/8)
1448     return GPG_ERR_INV_ARG;
1449
1450   /* Allocate a buffer to later compute SEED+some_increment. */
1451   seed_plus = xtrymalloc (seedlen < 20? 20:seedlen);
1452   if (!seed_plus)
1453     {
1454       ec = gpg_err_code_from_syserror ();
1455       goto leave;
1456     }
1457
1458   val_2   = mpi_alloc_set_ui (2);
1459   value_n = (pbits - 1) / qbits;
1460   value_b = (pbits - 1) - value_n * qbits;
1461   value_w = mpi_new (pbits);
1462   value_x = mpi_new (pbits);
1463
1464  restart:
1465   /* Generate Q.  */
1466   for (;;)
1467     {
1468       /* Step 1: Generate a (new) seed unless one has been supplied.  */
1469       if (!seed)
1470         {
1471           seedlen = sizeof seed_help_buffer;
1472           _gcry_create_nonce (seed_help_buffer, seedlen);
1473           seed = seed_help_buffer;
1474         }
1475
1476       /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits})  */
1477       memcpy (seed_plus, seed, seedlen);
1478       for (i=seedlen-1; i >= 0; i--)
1479         {
1480           seed_plus[i]++;
1481           if (seed_plus[i])
1482             break;
1483         }
1484       _gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1485       _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1486       for (i=0; i < sizeof value_u; i++)
1487         value_u[i] ^= digest[i];
1488
1489       /* Step 3:  Form q from U  */
1490       _gcry_mpi_release (prime_q); prime_q = NULL;
1491       ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1492                            value_u, sizeof value_u, NULL);
1493       if (ec)
1494         goto leave;
1495       mpi_set_highbit (prime_q, qbits-1 );
1496       mpi_set_bit (prime_q, 0);
1497
1498       /* Step 4:  Test whether Q is prime using 64 round of Rabin-Miller.  */
1499       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1500         break; /* Yes, Q is prime.  */
1501
1502       /* Step 5.  */
1503       seed = NULL;  /* Force a new seed at Step 1.  */
1504     }
1505
1506   /* Step 6.  Note that we do no use an explicit offset but increment
1507      SEED_PLUS accordingly.  SEED_PLUS is currently SEED+1.  */
1508   counter = 0;
1509
1510   /* Generate P. */
1511   prime_p = mpi_new (pbits);
1512   for (;;)
1513     {
1514       /* Step 7: For k = 0,...n let
1515                    V_k = sha1(seed+offset+k) mod 2^{qbits}
1516          Step 8: W = V_0 + V_1*2^160 +
1517                          ...
1518                          + V_{n-1}*2^{(n-1)*160}
1519                          + (V_{n} mod 2^b)*2^{n*160}
1520        */
1521       mpi_set_ui (value_w, 0);
1522       for (value_k=0; value_k <= value_n; value_k++)
1523         {
1524           /* There is no need to have an explicit offset variable:  In
1525              the first round we shall have an offset of 2, this is
1526              achieved by using SEED_PLUS which is already at SEED+1,
1527              thus we just need to increment it once again.  The
1528              requirement for the next round is to update offset by N,
1529              which we implictly did at the end of this loop, and then
1530              to add one; this one is the same as in the first round.  */
1531           for (i=seedlen-1; i >= 0; i--)
1532             {
1533               seed_plus[i]++;
1534               if (seed_plus[i])
1535                 break;
1536             }
1537           _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1538
1539           _gcry_mpi_release (tmpval); tmpval = NULL;
1540           ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1541                                digest, sizeof digest, NULL);
1542           if (ec)
1543             goto leave;
1544           if (value_k == value_n)
1545             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1546           mpi_lshift (tmpval, tmpval, value_k*qbits);
1547           mpi_add (value_w, value_w, tmpval);
1548         }
1549
1550       /* Step 8 continued: X = W + 2^{L-1}  */
1551       mpi_set_ui (value_x, 0);
1552       mpi_set_highbit (value_x, pbits-1);
1553       mpi_add (value_x, value_x, value_w);
1554
1555       /* Step 9:  c = X mod 2q,  p = X - (c - 1)  */
1556       mpi_mul_2exp (tmpval, prime_q, 1);
1557       mpi_mod (tmpval, value_x, tmpval);
1558       mpi_sub_ui (tmpval, tmpval, 1);
1559       mpi_sub (prime_p, value_x, tmpval);
1560
1561       /* Step 10: If  p < 2^{L-1}  skip the primality test.  */
1562       /* Step 11 and 12: Primality test.  */
1563       if (mpi_get_nbits (prime_p) >= pbits-1
1564           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1565         break; /* Yes, P is prime, continue with Step 15.  */
1566
1567       /* Step 13: counter = counter + 1, offset = offset + n + 1. */
1568       counter++;
1569
1570       /* Step 14: If counter >= 2^12  goto Step 1.  */
1571       if (counter >= 4096)
1572         goto restart;
1573     }
1574
1575   /* Step 15:  Save p, q, counter and seed.  */
1576 /*   log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1577 /*              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1578 /*   log_printhex("fips186-2 seed:", seed, seedlen); */
1579 /*   log_mpidump ("fips186-2 prime p", prime_p); */
1580 /*   log_mpidump ("fips186-2 prime q", prime_q); */
1581   if (r_q)
1582     {
1583       *r_q = prime_q;
1584       prime_q = NULL;
1585     }
1586   if (r_p)
1587     {
1588       *r_p = prime_p;
1589       prime_p = NULL;
1590     }
1591   if (r_counter)
1592     *r_counter = counter;
1593   if (r_seed && r_seedlen)
1594     {
1595       memcpy (seed_plus, seed, seedlen);
1596       *r_seed = seed_plus;
1597       seed_plus = NULL;
1598       *r_seedlen = seedlen;
1599     }
1600
1601
1602  leave:
1603   _gcry_mpi_release (tmpval);
1604   _gcry_mpi_release (value_x);
1605   _gcry_mpi_release (value_w);
1606   _gcry_mpi_release (prime_p);
1607   _gcry_mpi_release (prime_q);
1608   xfree (seed_plus);
1609   _gcry_mpi_release (val_2);
1610   return ec;
1611 }
1612
1613
1614 \f
1615 /* WARNING: The code below has not yet been tested!  However, it is
1616    not yet used.  We need to wait for FIPS 186-3 final and for test
1617    vectors.
1618
1619    Generate the two prime used for DSA using the algorithm specified
1620    in FIPS 186-3, A.1.1.2.  PBITS is the desired length of the prime P
1621    and a QBITS the length of the prime Q.  If SEED is not supplied and
1622    SEEDLEN is 0 the function generates an appropriate SEED.  On
1623    success the generated primes are stored at R_Q and R_P, the counter
1624    value is stored at R_COUNTER and the seed actually used for
1625    generation is stored at R_SEED and R_SEEDVALUE.  The hash algorithm
1626    used is stored at R_HASHALGO.
1627
1628    Note that this function is very similar to the fips186_2 code.  Due
1629    to the minor differences, other buffer sizes and for documentarion,
1630    we use a separate function.
1631 */
1632 gpg_err_code_t
1633 _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1634                                 const void *seed, size_t seedlen,
1635                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1636                                 int *r_counter,
1637                                 void **r_seed, size_t *r_seedlen,
1638                                 int *r_hashalgo)
1639 {
1640   gpg_err_code_t ec;
1641   unsigned char seed_help_buffer[256/8];  /* Used to hold a generated SEED. */
1642   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1643   unsigned char digest[256/8];  /* Helper buffer for SHA-1 digest.  */
1644   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1645   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1646   int hashalgo;                 /* The id of the Approved Hash Function.  */
1647   int i;
1648
1649   unsigned char value_u[256/8];
1650   int value_n, value_b, value_j;
1651   int counter;
1652   gcry_mpi_t value_w = NULL;
1653   gcry_mpi_t value_x = NULL;
1654   gcry_mpi_t prime_q = NULL;
1655   gcry_mpi_t prime_p = NULL;
1656
1657   gcry_assert (sizeof seed_help_buffer == sizeof digest
1658                && sizeof seed_help_buffer == sizeof value_u);
1659
1660   /* Step 1:  Check the requested prime lengths.  */
1661   /* Note that due to the size of our buffers QBITS is limited to 256.  */
1662   if (pbits == 1024 && qbits == 160)
1663     hashalgo = GCRY_MD_SHA1;
1664   else if (pbits == 2048 && qbits == 224)
1665     hashalgo = GCRY_MD_SHA224;
1666   else if (pbits == 2048 && qbits == 256)
1667     hashalgo = GCRY_MD_SHA256;
1668   else if (pbits == 3072 && qbits == 256)
1669     hashalgo = GCRY_MD_SHA256;
1670   else
1671     return GPG_ERR_INV_KEYLEN;
1672
1673   /* Also check that the hash algorithm is available.  */
1674   ec = _gcry_md_test_algo (hashalgo);
1675   if (ec)
1676     return ec;
1677   gcry_assert (qbits/8 <= sizeof digest);
1678   gcry_assert (_gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1679
1680
1681   /* Step 2:  Check seedlen.  */
1682   if (!seed && !seedlen)
1683     ; /* No seed value given:  We are asked to generate it.  */
1684   else if (!seed || seedlen < qbits/8)
1685     return GPG_ERR_INV_ARG;
1686
1687   /* Allocate a buffer to later compute SEED+some_increment and a few
1688      helper variables.  */
1689   seed_plus = xtrymalloc (seedlen < sizeof seed_help_buffer?
1690                           sizeof seed_help_buffer : seedlen);
1691   if (!seed_plus)
1692     {
1693       ec = gpg_err_code_from_syserror ();
1694       goto leave;
1695     }
1696   val_2   = mpi_alloc_set_ui (2);
1697   value_w = mpi_new (pbits);
1698   value_x = mpi_new (pbits);
1699
1700   /* Step 3: n = \lceil L / outlen \rceil - 1  */
1701   value_n = (pbits + qbits - 1) / qbits - 1;
1702   /* Step 4: b = L - 1 - (n * outlen)  */
1703   value_b = pbits - 1 - (value_n * qbits);
1704
1705  restart:
1706   /* Generate Q.  */
1707   for (;;)
1708     {
1709       /* Step 5:  Generate a (new) seed unless one has been supplied.  */
1710       if (!seed)
1711         {
1712           seedlen = qbits/8;
1713           gcry_assert (seedlen <= sizeof seed_help_buffer);
1714           _gcry_create_nonce (seed_help_buffer, seedlen);
1715           seed = seed_help_buffer;
1716         }
1717
1718       /* Step 6:  U = hash(seed)  */
1719       _gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1720
1721       /* Step 7:  q = 2^{N-1} + U + 1 - (U mod 2)  */
1722       if ( !(value_u[qbits/8-1] & 0x01) )
1723         {
1724           for (i=qbits/8-1; i >= 0; i--)
1725             {
1726               value_u[i]++;
1727               if (value_u[i])
1728                 break;
1729             }
1730         }
1731       _gcry_mpi_release (prime_q); prime_q = NULL;
1732       ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1733                            value_u, sizeof value_u, NULL);
1734       if (ec)
1735         goto leave;
1736       mpi_set_highbit (prime_q, qbits-1 );
1737
1738       /* Step 8:  Test whether Q is prime using 64 round of Rabin-Miller.
1739                   According to table C.1 this is sufficient for all
1740                   supported prime sizes (i.e. up 3072/256).  */
1741       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1742         break; /* Yes, Q is prime.  */
1743
1744       /* Step 8.  */
1745       seed = NULL;  /* Force a new seed at Step 5.  */
1746     }
1747
1748   /* Step 11.  Note that we do no use an explicit offset but increment
1749      SEED_PLUS accordingly.  */
1750   memcpy (seed_plus, seed, seedlen);
1751   counter = 0;
1752
1753   /* Generate P. */
1754   prime_p = mpi_new (pbits);
1755   for (;;)
1756     {
1757       /* Step 11.1: For j = 0,...n let
1758                       V_j = hash(seed+offset+j)
1759          Step 11.2: W = V_0 + V_1*2^outlen +
1760                             ...
1761                             + V_{n-1}*2^{(n-1)*outlen}
1762                             + (V_{n} mod 2^b)*2^{n*outlen}
1763        */
1764       mpi_set_ui (value_w, 0);
1765       for (value_j=0; value_j <= value_n; value_j++)
1766         {
1767           /* There is no need to have an explicit offset variable: In
1768              the first round we shall have an offset of 1 and a j of
1769              0.  This is achieved by incrementing SEED_PLUS here.  For
1770              the next round offset is implicitly updated by using
1771              SEED_PLUS again.  */
1772           for (i=seedlen-1; i >= 0; i--)
1773             {
1774               seed_plus[i]++;
1775               if (seed_plus[i])
1776                 break;
1777             }
1778           _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1779
1780           _gcry_mpi_release (tmpval); tmpval = NULL;
1781           ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1782                                digest, sizeof digest, NULL);
1783           if (ec)
1784             goto leave;
1785           if (value_j == value_n)
1786             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1787           mpi_lshift (tmpval, tmpval, value_j*qbits);
1788           mpi_add (value_w, value_w, tmpval);
1789         }
1790
1791       /* Step 11.3: X = W + 2^{L-1}  */
1792       mpi_set_ui (value_x, 0);
1793       mpi_set_highbit (value_x, pbits-1);
1794       mpi_add (value_x, value_x, value_w);
1795
1796       /* Step 11.4:  c = X mod 2q  */
1797       mpi_mul_2exp (tmpval, prime_q, 1);
1798       mpi_mod (tmpval, value_x, tmpval);
1799
1800       /* Step 11.5:  p = X - (c - 1)  */
1801       mpi_sub_ui (tmpval, tmpval, 1);
1802       mpi_sub (prime_p, value_x, tmpval);
1803
1804       /* Step 11.6: If  p < 2^{L-1}  skip the primality test.  */
1805       /* Step 11.7 and 11.8: Primality test.  */
1806       if (mpi_get_nbits (prime_p) >= pbits-1
1807           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1808         break; /* Yes, P is prime, continue with Step 15.  */
1809
1810       /* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1811                     If counter >= 4L  goto Step 5.  */
1812       counter++;
1813       if (counter >= 4*pbits)
1814         goto restart;
1815     }
1816
1817   /* Step 12:  Save p, q, counter and seed.  */
1818   log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n",
1819              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter);
1820   log_printhex ("fips186-3 seed", seed, seedlen);
1821   log_printmpi ("fips186-3    p", prime_p);
1822   log_printmpi ("fips186-3    q", prime_q);
1823   if (r_q)
1824     {
1825       *r_q = prime_q;
1826       prime_q = NULL;
1827     }
1828   if (r_p)
1829     {
1830       *r_p = prime_p;
1831       prime_p = NULL;
1832     }
1833   if (r_counter)
1834     *r_counter = counter;
1835   if (r_seed && r_seedlen)
1836     {
1837       memcpy (seed_plus, seed, seedlen);
1838       *r_seed = seed_plus;
1839       seed_plus = NULL;
1840       *r_seedlen = seedlen;
1841     }
1842   if (r_hashalgo)
1843     *r_hashalgo = hashalgo;
1844
1845  leave:
1846   _gcry_mpi_release (tmpval);
1847   _gcry_mpi_release (value_x);
1848   _gcry_mpi_release (value_w);
1849   _gcry_mpi_release (prime_p);
1850   _gcry_mpi_release (prime_q);
1851   xfree (seed_plus);
1852   _gcry_mpi_release (val_2);
1853   return ec;
1854 }