ecc: Fix ec_mulm_25519.
[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
1186 /* Check whether the number X is prime according to FIPS 186-4 table C.2.  */
1187 gcry_err_code_t
1188 _gcry_fips186_4_prime_check (gcry_mpi_t x, unsigned int bits)
1189 {
1190   gcry_err_code_t ec = GPG_ERR_NO_ERROR;
1191
1192   switch (mpi_cmp_ui (x, 2))
1193     {
1194     case 0:  return ec;               /* 2 is a prime */
1195     case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes.  */
1196     }
1197
1198   /* We use 5 or 4 rounds as specified in table C.2 */
1199   if (! check_prime (x, mpi_const (MPI_C_TWO), bits > 1024 ? 4 : 5, NULL, NULL))
1200     ec = GPG_ERR_NO_PRIME;
1201
1202   return ec;
1203 }
1204
1205
1206 /* Find a generator for PRIME where the factorization of (prime-1) is
1207    in the NULL terminated array FACTORS. Return the generator as a
1208    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1209    atart for the search. Returns 0 on success.*/
1210 gcry_err_code_t
1211 _gcry_prime_group_generator (gcry_mpi_t *r_g,
1212                              gcry_mpi_t prime, gcry_mpi_t *factors,
1213                              gcry_mpi_t start_g)
1214 {
1215   gcry_mpi_t tmp, b, pmin1, g;
1216   int first, i, n;
1217
1218   if (!r_g)
1219     return GPG_ERR_INV_ARG;
1220   *r_g = NULL;
1221   if (!factors || !prime)
1222     return GPG_ERR_INV_ARG;
1223
1224   for (n=0; factors[n]; n++)
1225     ;
1226   if (n < 2)
1227     return GPG_ERR_INV_ARG;
1228
1229   tmp   = mpi_new (0);
1230   b     = mpi_new (0);
1231   pmin1 = mpi_new (0);
1232   g     = start_g? mpi_copy (start_g) : mpi_set_ui (NULL, 3);
1233
1234   /* Extra sanity check - usually disabled. */
1235 /*   mpi_set (tmp, factors[0]); */
1236 /*   for(i = 1; i < n; i++) */
1237 /*     mpi_mul (tmp, tmp, factors[i]); */
1238 /*   mpi_add_ui (tmp, tmp, 1); */
1239 /*   if (mpi_cmp (prime, tmp)) */
1240 /*     return gpg_error (GPG_ERR_INV_ARG); */
1241
1242   mpi_sub_ui (pmin1, prime, 1);
1243   first = 1;
1244   do
1245     {
1246       if (first)
1247         first = 0;
1248       else
1249         mpi_add_ui (g, g, 1);
1250
1251       if (DBG_CIPHER)
1252         log_printmpi ("checking g", g);
1253       else
1254         progress('^');
1255
1256       for (i = 0; i < n; i++)
1257         {
1258           mpi_fdiv_q (tmp, pmin1, factors[i]);
1259           mpi_powm (b, g, tmp, prime);
1260           if (! mpi_cmp_ui (b, 1))
1261             break;
1262         }
1263       if (DBG_CIPHER)
1264         progress('\n');
1265     }
1266   while (i < n);
1267
1268   _gcry_mpi_release (tmp);
1269   _gcry_mpi_release (b);
1270   _gcry_mpi_release (pmin1);
1271   *r_g = g;
1272
1273   return 0;
1274 }
1275
1276 /* Convenience function to release the factors array. */
1277 void
1278 _gcry_prime_release_factors (gcry_mpi_t *factors)
1279 {
1280   if (factors)
1281     {
1282       int i;
1283
1284       for (i=0; factors[i]; i++)
1285         mpi_free (factors[i]);
1286       xfree (factors);
1287     }
1288 }
1289
1290
1291 \f
1292 /* Helper for _gcry_derive_x931_prime.  */
1293 static gcry_mpi_t
1294 find_x931_prime (const gcry_mpi_t pfirst)
1295 {
1296   gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1297   gcry_mpi_t prime;
1298
1299   prime = mpi_copy (pfirst);
1300   /* If P is even add 1.  */
1301   mpi_set_bit (prime, 0);
1302
1303   /* We use 64 Rabin-Miller rounds which is better and thus
1304      sufficient.  We do not have a Lucas test implementation thus we
1305      can't do it in the X9.31 preferred way of running a few
1306      Rabin-Miller followed by one Lucas test.  */
1307   while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1308     mpi_add_ui (prime, prime, 2);
1309
1310   mpi_free (val_2);
1311
1312   return prime;
1313 }
1314
1315
1316 /* Generate a prime using the algorithm from X9.31 appendix B.4.
1317
1318    This function requires that the provided public exponent E is odd.
1319    XP, XP1 and XP2 are the seed values.  All values are mandatory.
1320
1321    On success the prime is returned.  If R_P1 or R_P2 are given the
1322    internal values P1 and P2 are saved at these addresses.  On error
1323    NULL is returned.  */
1324 gcry_mpi_t
1325 _gcry_derive_x931_prime (const gcry_mpi_t xp,
1326                          const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1327                          const gcry_mpi_t e,
1328                          gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1329 {
1330   gcry_mpi_t p1, p2, p1p2, yp0;
1331
1332   if (!xp || !xp1 || !xp2)
1333     return NULL;
1334   if (!e || !mpi_test_bit (e, 0))
1335     return NULL;  /* We support only odd values for E.  */
1336
1337   p1 = find_x931_prime (xp1);
1338   p2 = find_x931_prime (xp2);
1339   p1p2 = mpi_alloc_like (xp);
1340   mpi_mul (p1p2, p1, p2);
1341
1342   {
1343     gcry_mpi_t r1, tmp;
1344
1345     /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1346     tmp = mpi_alloc_like (p1);
1347     mpi_invm (tmp, p2, p1);
1348     mpi_mul (tmp, tmp, p2);
1349     r1 = tmp;
1350
1351     tmp = mpi_alloc_like (p2);
1352     mpi_invm (tmp, p1, p2);
1353     mpi_mul (tmp, tmp, p1);
1354     mpi_sub (r1, r1, tmp);
1355
1356     /* Fixup a negative value.  */
1357     if (mpi_has_sign (r1))
1358       mpi_add (r1, r1, p1p2);
1359
1360     /* yp0 = xp + (r1 - xp mod p1*p2)  */
1361     yp0 = tmp; tmp = NULL;
1362     mpi_subm (yp0, r1, xp, p1p2);
1363     mpi_add (yp0, yp0, xp);
1364     mpi_free (r1);
1365
1366     /* Fixup a negative value.  */
1367     if (mpi_cmp (yp0, xp) < 0 )
1368       mpi_add (yp0, yp0, p1p2);
1369   }
1370
1371   /* yp0 is now the first integer greater than xp with p1 being a
1372      large prime factor of yp0-1 and p2 a large prime factor of yp0+1.  */
1373
1374   /* Note that the first example from X9.31 (D.1.1) which uses
1375        (Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1376        (Xq2 #134E4CAA16D2350A21D775C404#)
1377        (Xq  #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1378              7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1379              6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1380              321DE34A#))))
1381      returns an yp0 of
1382             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1383              7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1384              BF20CB896EE37E098A906313271422162CB6C642
1385              75C1201F#
1386      and not
1387             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1388              7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1389              C88FE299D52D78BE405A97E01FD71DD7819ECB91
1390              FA85A076#
1391      as stated in the standard.  This seems to be a bug in X9.31.
1392    */
1393
1394   {
1395     gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1396     gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1397     int gcdres;
1398
1399     mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body.  */
1400     mpi_sub_ui (yp0, yp0, 1);   /* Ditto.  */
1401     for (;;)
1402       {
1403         gcdres = mpi_gcd (gcdtmp, e, yp0);
1404         mpi_add_ui (yp0, yp0, 1);
1405         if (!gcdres)
1406           progress ('/');  /* gcd (e, yp0-1) != 1  */
1407         else if (check_prime (yp0, val_2, 64, NULL, NULL))
1408           break; /* Found.  */
1409         /* We add p1p2-1 because yp0 is incremented after the gcd test.  */
1410         mpi_add (yp0, yp0, p1p2);
1411       }
1412     mpi_free (gcdtmp);
1413     mpi_free (val_2);
1414   }
1415
1416   mpi_free (p1p2);
1417
1418   progress('\n');
1419   if (r_p1)
1420     *r_p1 = p1;
1421   else
1422     mpi_free (p1);
1423   if (r_p2)
1424     *r_p2 = p2;
1425   else
1426     mpi_free (p2);
1427   return yp0;
1428 }
1429
1430
1431 \f
1432 /* Generate the two prime used for DSA using the algorithm specified
1433    in FIPS 186-2.  PBITS is the desired length of the prime P and a
1434    QBITS the length of the prime Q.  If SEED is not supplied and
1435    SEEDLEN is 0 the function generates an appropriate SEED.  On
1436    success the generated primes are stored at R_Q and R_P, the counter
1437    value is stored at R_COUNTER and the seed actually used for
1438    generation is stored at R_SEED and R_SEEDVALUE.  */
1439 gpg_err_code_t
1440 _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1441                                 const void *seed, size_t seedlen,
1442                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1443                                 int *r_counter,
1444                                 void **r_seed, size_t *r_seedlen)
1445 {
1446   gpg_err_code_t ec;
1447   unsigned char seed_help_buffer[160/8];  /* Used to hold a generated SEED. */
1448   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1449   unsigned char digest[160/8];  /* Helper buffer for SHA-1 digest.  */
1450   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1451   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1452   int i;
1453
1454   unsigned char value_u[160/8];
1455   int value_n, value_b, value_k;
1456   int counter;
1457   gcry_mpi_t value_w = NULL;
1458   gcry_mpi_t value_x = NULL;
1459   gcry_mpi_t prime_q = NULL;
1460   gcry_mpi_t prime_p = NULL;
1461
1462   /* FIPS 186-2 allows only for 1024/160 bit.  */
1463   if (pbits != 1024 || qbits != 160)
1464     return GPG_ERR_INV_KEYLEN;
1465
1466   if (!seed && !seedlen)
1467     ; /* No seed value given:  We are asked to generate it.  */
1468   else if (!seed || seedlen < qbits/8)
1469     return GPG_ERR_INV_ARG;
1470
1471   /* Allocate a buffer to later compute SEED+some_increment. */
1472   seed_plus = xtrymalloc (seedlen < 20? 20:seedlen);
1473   if (!seed_plus)
1474     {
1475       ec = gpg_err_code_from_syserror ();
1476       goto leave;
1477     }
1478
1479   val_2   = mpi_alloc_set_ui (2);
1480   value_n = (pbits - 1) / qbits;
1481   value_b = (pbits - 1) - value_n * qbits;
1482   value_w = mpi_new (pbits);
1483   value_x = mpi_new (pbits);
1484
1485  restart:
1486   /* Generate Q.  */
1487   for (;;)
1488     {
1489       /* Step 1: Generate a (new) seed unless one has been supplied.  */
1490       if (!seed)
1491         {
1492           seedlen = sizeof seed_help_buffer;
1493           _gcry_create_nonce (seed_help_buffer, seedlen);
1494           seed = seed_help_buffer;
1495         }
1496
1497       /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits})  */
1498       memcpy (seed_plus, seed, seedlen);
1499       for (i=seedlen-1; i >= 0; i--)
1500         {
1501           seed_plus[i]++;
1502           if (seed_plus[i])
1503             break;
1504         }
1505       _gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1506       _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1507       for (i=0; i < sizeof value_u; i++)
1508         value_u[i] ^= digest[i];
1509
1510       /* Step 3:  Form q from U  */
1511       _gcry_mpi_release (prime_q); prime_q = NULL;
1512       ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1513                            value_u, sizeof value_u, NULL);
1514       if (ec)
1515         goto leave;
1516       mpi_set_highbit (prime_q, qbits-1 );
1517       mpi_set_bit (prime_q, 0);
1518
1519       /* Step 4:  Test whether Q is prime using 64 round of Rabin-Miller.  */
1520       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1521         break; /* Yes, Q is prime.  */
1522
1523       /* Step 5.  */
1524       seed = NULL;  /* Force a new seed at Step 1.  */
1525     }
1526
1527   /* Step 6.  Note that we do no use an explicit offset but increment
1528      SEED_PLUS accordingly.  SEED_PLUS is currently SEED+1.  */
1529   counter = 0;
1530
1531   /* Generate P. */
1532   prime_p = mpi_new (pbits);
1533   for (;;)
1534     {
1535       /* Step 7: For k = 0,...n let
1536                    V_k = sha1(seed+offset+k) mod 2^{qbits}
1537          Step 8: W = V_0 + V_1*2^160 +
1538                          ...
1539                          + V_{n-1}*2^{(n-1)*160}
1540                          + (V_{n} mod 2^b)*2^{n*160}
1541        */
1542       mpi_set_ui (value_w, 0);
1543       for (value_k=0; value_k <= value_n; value_k++)
1544         {
1545           /* There is no need to have an explicit offset variable:  In
1546              the first round we shall have an offset of 2, this is
1547              achieved by using SEED_PLUS which is already at SEED+1,
1548              thus we just need to increment it once again.  The
1549              requirement for the next round is to update offset by N,
1550              which we implictly did at the end of this loop, and then
1551              to add one; this one is the same as in the first round.  */
1552           for (i=seedlen-1; i >= 0; i--)
1553             {
1554               seed_plus[i]++;
1555               if (seed_plus[i])
1556                 break;
1557             }
1558           _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1559
1560           _gcry_mpi_release (tmpval); tmpval = NULL;
1561           ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1562                                digest, sizeof digest, NULL);
1563           if (ec)
1564             goto leave;
1565           if (value_k == value_n)
1566             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1567           mpi_lshift (tmpval, tmpval, value_k*qbits);
1568           mpi_add (value_w, value_w, tmpval);
1569         }
1570
1571       /* Step 8 continued: X = W + 2^{L-1}  */
1572       mpi_set_ui (value_x, 0);
1573       mpi_set_highbit (value_x, pbits-1);
1574       mpi_add (value_x, value_x, value_w);
1575
1576       /* Step 9:  c = X mod 2q,  p = X - (c - 1)  */
1577       mpi_mul_2exp (tmpval, prime_q, 1);
1578       mpi_mod (tmpval, value_x, tmpval);
1579       mpi_sub_ui (tmpval, tmpval, 1);
1580       mpi_sub (prime_p, value_x, tmpval);
1581
1582       /* Step 10: If  p < 2^{L-1}  skip the primality test.  */
1583       /* Step 11 and 12: Primality test.  */
1584       if (mpi_get_nbits (prime_p) >= pbits-1
1585           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1586         break; /* Yes, P is prime, continue with Step 15.  */
1587
1588       /* Step 13: counter = counter + 1, offset = offset + n + 1. */
1589       counter++;
1590
1591       /* Step 14: If counter >= 2^12  goto Step 1.  */
1592       if (counter >= 4096)
1593         goto restart;
1594     }
1595
1596   /* Step 15:  Save p, q, counter and seed.  */
1597 /*   log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1598 /*              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1599 /*   log_printhex("fips186-2 seed:", seed, seedlen); */
1600 /*   log_mpidump ("fips186-2 prime p", prime_p); */
1601 /*   log_mpidump ("fips186-2 prime q", prime_q); */
1602   if (r_q)
1603     {
1604       *r_q = prime_q;
1605       prime_q = NULL;
1606     }
1607   if (r_p)
1608     {
1609       *r_p = prime_p;
1610       prime_p = NULL;
1611     }
1612   if (r_counter)
1613     *r_counter = counter;
1614   if (r_seed && r_seedlen)
1615     {
1616       memcpy (seed_plus, seed, seedlen);
1617       *r_seed = seed_plus;
1618       seed_plus = NULL;
1619       *r_seedlen = seedlen;
1620     }
1621
1622
1623  leave:
1624   _gcry_mpi_release (tmpval);
1625   _gcry_mpi_release (value_x);
1626   _gcry_mpi_release (value_w);
1627   _gcry_mpi_release (prime_p);
1628   _gcry_mpi_release (prime_q);
1629   xfree (seed_plus);
1630   _gcry_mpi_release (val_2);
1631   return ec;
1632 }
1633
1634
1635 \f
1636 /* WARNING: The code below has not yet been tested!
1637  *
1638  * Generate the two prime used for DSA using the algorithm specified
1639  * in FIPS 186-3, A.1.1.2.  PBITS is the desired length of the prime P
1640  * and a QBITS the length of the prime Q.  If SEED is not supplied and
1641  * SEEDLEN is 0 the function generates an appropriate SEED.  On
1642  * success the generated primes are stored at R_Q and R_P, the counter
1643  * value is stored at R_COUNTER and the seed actually used for
1644  * generation is stored at R_SEED and R_SEEDVALUE.  The hash algorithm
1645  * used is stored at R_HASHALGO.
1646  *
1647  * Note that this function is very similar to the fips186_2 code.  Due
1648  * to the minor differences, other buffer sizes and for documentarion,
1649  * we use a separate function.
1650  */
1651 gpg_err_code_t
1652 _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1653                                 const void *seed, size_t seedlen,
1654                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1655                                 int *r_counter,
1656                                 void **r_seed, size_t *r_seedlen,
1657                                 int *r_hashalgo)
1658 {
1659   gpg_err_code_t ec;
1660   unsigned char seed_help_buffer[256/8];  /* Used to hold a generated SEED. */
1661   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1662   unsigned char digest[256/8];  /* Helper buffer for SHA-2 digest.  */
1663   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1664   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1665   int hashalgo;                 /* The id of the Approved Hash Function.  */
1666   int i;
1667
1668   unsigned char value_u[256/8];
1669   int value_n, value_b, value_j;
1670   int counter;
1671   gcry_mpi_t value_w = NULL;
1672   gcry_mpi_t value_x = NULL;
1673   gcry_mpi_t prime_q = NULL;
1674   gcry_mpi_t prime_p = NULL;
1675
1676   gcry_assert (sizeof seed_help_buffer == sizeof digest
1677                && sizeof seed_help_buffer == sizeof value_u);
1678
1679   /* Step 1:  Check the requested prime lengths.  */
1680   /* Note that due to the size of our buffers QBITS is limited to 256.  */
1681   if (pbits == 2048 && qbits == 224)
1682     hashalgo = GCRY_MD_SHA224;
1683   else if (pbits == 2048 && qbits == 256)
1684     hashalgo = GCRY_MD_SHA256;
1685   else if (pbits == 3072 && qbits == 256)
1686     hashalgo = GCRY_MD_SHA256;
1687   else
1688     return GPG_ERR_INV_KEYLEN;
1689
1690   /* Also check that the hash algorithm is available.  */
1691   ec = _gcry_md_test_algo (hashalgo);
1692   if (ec)
1693     return ec;
1694   gcry_assert (qbits/8 <= sizeof digest);
1695   gcry_assert (_gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1696
1697
1698   /* Step 2:  Check seedlen.  */
1699   if (!seed && !seedlen)
1700     ; /* No seed value given:  We are asked to generate it.  */
1701   else if (!seed || seedlen < qbits/8)
1702     return GPG_ERR_INV_ARG;
1703
1704   /* Allocate a buffer to later compute SEED+some_increment and a few
1705      helper variables.  */
1706   seed_plus = xtrymalloc (seedlen < sizeof seed_help_buffer?
1707                           sizeof seed_help_buffer : seedlen);
1708   if (!seed_plus)
1709     {
1710       ec = gpg_err_code_from_syserror ();
1711       goto leave;
1712     }
1713   val_2   = mpi_alloc_set_ui (2);
1714   value_w = mpi_new (pbits);
1715   value_x = mpi_new (pbits);
1716
1717   /* Step 3: n = \lceil L / outlen \rceil - 1  */
1718   value_n = (pbits + qbits - 1) / qbits - 1;
1719   /* Step 4: b = L - 1 - (n * outlen)  */
1720   value_b = pbits - 1 - (value_n * qbits);
1721
1722  restart:
1723   /* Generate Q.  */
1724   for (;;)
1725     {
1726       /* Step 5:  Generate a (new) seed unless one has been supplied.  */
1727       if (!seed)
1728         {
1729           seedlen = qbits/8;
1730           gcry_assert (seedlen <= sizeof seed_help_buffer);
1731           _gcry_create_nonce (seed_help_buffer, seedlen);
1732           seed = seed_help_buffer;
1733         }
1734
1735       /* Step 6:  U = hash(seed)  */
1736       _gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1737
1738       /* Step 7:  q = 2^{N-1} + U + 1 - (U mod 2)  */
1739       if ( !(value_u[qbits/8-1] & 0x01) )
1740         {
1741           for (i=qbits/8-1; i >= 0; i--)
1742             {
1743               value_u[i]++;
1744               if (value_u[i])
1745                 break;
1746             }
1747         }
1748       _gcry_mpi_release (prime_q); prime_q = NULL;
1749       ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1750                            value_u, qbits/8, NULL);
1751       if (ec)
1752         goto leave;
1753       mpi_set_highbit (prime_q, qbits-1 );
1754
1755       /* Step 8:  Test whether Q is prime using 64 round of Rabin-Miller.
1756                   According to table C.1 this is sufficient for all
1757                   supported prime sizes (i.e. up 3072/256).  */
1758       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1759         break; /* Yes, Q is prime.  */
1760
1761       /* Step 8.  */
1762       seed = NULL;  /* Force a new seed at Step 5.  */
1763     }
1764
1765   /* Step 11.  Note that we do no use an explicit offset but increment
1766      SEED_PLUS accordingly.  */
1767   memcpy (seed_plus, seed, seedlen);
1768   counter = 0;
1769
1770   /* Generate P. */
1771   prime_p = mpi_new (pbits);
1772   for (;;)
1773     {
1774       /* Step 11.1: For j = 0,...n let
1775                       V_j = hash(seed+offset+j)
1776          Step 11.2: W = V_0 + V_1*2^outlen +
1777                             ...
1778                             + V_{n-1}*2^{(n-1)*outlen}
1779                             + (V_{n} mod 2^b)*2^{n*outlen}
1780        */
1781       mpi_set_ui (value_w, 0);
1782       for (value_j=0; value_j <= value_n; value_j++)
1783         {
1784           /* There is no need to have an explicit offset variable: In
1785              the first round we shall have an offset of 1 and a j of
1786              0.  This is achieved by incrementing SEED_PLUS here.  For
1787              the next round offset is implicitly updated by using
1788              SEED_PLUS again.  */
1789           for (i=seedlen-1; i >= 0; i--)
1790             {
1791               seed_plus[i]++;
1792               if (seed_plus[i])
1793                 break;
1794             }
1795           _gcry_md_hash_buffer (hashalgo, digest, seed_plus, seedlen);
1796
1797           _gcry_mpi_release (tmpval); tmpval = NULL;
1798           ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1799                                digest, qbits/8, NULL);
1800           if (ec)
1801             goto leave;
1802           if (value_j == value_n)
1803             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1804           mpi_lshift (tmpval, tmpval, value_j*qbits);
1805           mpi_add (value_w, value_w, tmpval);
1806         }
1807
1808       /* Step 11.3: X = W + 2^{L-1}  */
1809       mpi_set_ui (value_x, 0);
1810       mpi_set_highbit (value_x, pbits-1);
1811       mpi_add (value_x, value_x, value_w);
1812
1813       /* Step 11.4:  c = X mod 2q  */
1814       mpi_mul_2exp (tmpval, prime_q, 1);
1815       mpi_mod (tmpval, value_x, tmpval);
1816
1817       /* Step 11.5:  p = X - (c - 1)  */
1818       mpi_sub_ui (tmpval, tmpval, 1);
1819       mpi_sub (prime_p, value_x, tmpval);
1820
1821       /* Step 11.6: If  p < 2^{L-1}  skip the primality test.  */
1822       /* Step 11.7 and 11.8: Primality test.  */
1823       if (mpi_get_nbits (prime_p) >= pbits-1
1824           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1825         break; /* Yes, P is prime, continue with Step 15.  */
1826
1827       /* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1828                     If counter >= 4L  goto Step 5.  */
1829       counter++;
1830       if (counter >= 4*pbits)
1831         goto restart;
1832     }
1833
1834   /* Step 12:  Save p, q, counter and seed.  */
1835   /* log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n", */
1836   /*            mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1837   /* log_printhex ("fips186-3 seed", seed, seedlen); */
1838   /* log_printmpi ("fips186-3    p", prime_p); */
1839   /* log_printmpi ("fips186-3    q", prime_q); */
1840
1841   if (r_q)
1842     {
1843       *r_q = prime_q;
1844       prime_q = NULL;
1845     }
1846   if (r_p)
1847     {
1848       *r_p = prime_p;
1849       prime_p = NULL;
1850     }
1851   if (r_counter)
1852     *r_counter = counter;
1853   if (r_seed && r_seedlen)
1854     {
1855       memcpy (seed_plus, seed, seedlen);
1856       *r_seed = seed_plus;
1857       seed_plus = NULL;
1858       *r_seedlen = seedlen;
1859     }
1860   if (r_hashalgo)
1861     *r_hashalgo = hashalgo;
1862
1863  leave:
1864   _gcry_mpi_release (tmpval);
1865   _gcry_mpi_release (value_x);
1866   _gcry_mpi_release (value_w);
1867   _gcry_mpi_release (prime_p);
1868   _gcry_mpi_release (prime_q);
1869   xfree (seed_plus);
1870   _gcry_mpi_release (val_2);
1871   return ec;
1872 }