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