pkgconfig: Fix libgcrypt.pc.
[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 = (secret? xmalloc_secure (no_of_small_prime_numbers * sizeof *mods)
762           /* */ : xmalloc (no_of_small_prime_numbers * sizeof *mods));
763   /* Make nbits fit into gcry_mpi_t implementation. */
764   val_2  = mpi_alloc_set_ui( 2 );
765   val_3 = mpi_alloc_set_ui( 3);
766   prime  = secret? mpi_snew (nbits): mpi_new (nbits);
767   result = mpi_alloc_like( prime );
768   pminus1= mpi_alloc_like( prime );
769   ptest  = mpi_alloc_like( prime );
770   count1 = count2 = 0;
771   for (;;)
772     {  /* try forvever */
773       int dotcount=0;
774
775       /* generate a random number */
776       _gcry_mpi_randomize( prime, nbits, randomlevel );
777
778       /* Set high order bit to 1, set low order bit to 1.  If we are
779          generating a secret prime we are most probably doing that
780          for RSA, to make sure that the modulus does have the
781          requested key size we set the 2 high order bits. */
782       mpi_set_highbit (prime, nbits-1);
783       if (secret)
784         mpi_set_bit (prime, nbits-2);
785       mpi_set_bit(prime, 0);
786
787       /* Calculate all remainders. */
788       for (i=0; (x = small_prime_numbers[i]); i++ )
789         mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
790
791       /* Now try some primes starting with prime. */
792       for(step=0; step < 20000; step += 2 )
793         {
794           /* Check against all the small primes we have in mods. */
795           count1++;
796           for (i=0; (x = small_prime_numbers[i]); i++ )
797             {
798               while ( mods[i] + step >= x )
799                 mods[i] -= x;
800               if ( !(mods[i] + step) )
801                 break;
802             }
803           if ( x )
804             continue;   /* Found a multiple of an already known prime. */
805
806           mpi_add_ui( ptest, prime, step );
807
808           /* Do a fast Fermat test now. */
809           count2++;
810           mpi_sub_ui( pminus1, ptest, 1);
811           mpi_powm( result, val_2, pminus1, ptest );
812           if ( !mpi_cmp_ui( result, 1 ) )
813             {
814               /* Not composite, perform stronger tests */
815               if (is_prime(ptest, 5, &count2 ))
816                 {
817                   if (!mpi_test_bit( ptest, nbits-1-secret ))
818                     {
819                       progress('\n');
820                       log_debug ("overflow in prime generation\n");
821                       break; /* Stop loop, continue with a new prime. */
822                     }
823
824                   if (extra_check && extra_check (extra_check_arg, ptest))
825                     {
826                       /* The extra check told us that this prime is
827                          not of the caller's taste. */
828                       progress ('/');
829                     }
830                   else
831                     {
832                       /* Got it. */
833                       mpi_free(val_2);
834                       mpi_free(val_3);
835                       mpi_free(result);
836                       mpi_free(pminus1);
837                       mpi_free(prime);
838                       xfree(mods);
839                       return ptest;
840                     }
841                 }
842             }
843           if (++dotcount == 10 )
844             {
845               progress('.');
846               dotcount = 0;
847             }
848         }
849       progress(':'); /* restart with a new random value */
850     }
851 }
852
853 /****************
854  * Returns: true if this may be a prime
855  * RM_ROUNDS gives the number of Rabin-Miller tests to run.
856  */
857 static int
858 check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
859              gcry_prime_check_func_t cb_func, void *cb_arg)
860 {
861   int i;
862   unsigned int x;
863   unsigned int count=0;
864
865   /* Check against small primes. */
866   for (i=0; (x = small_prime_numbers[i]); i++ )
867     {
868       if ( mpi_divisible_ui( prime, x ) )
869         return !mpi_cmp_ui (prime, x);
870     }
871
872   /* A quick Fermat test. */
873   {
874     gcry_mpi_t result = mpi_alloc_like( prime );
875     gcry_mpi_t pminus1 = mpi_alloc_like( prime );
876     mpi_sub_ui( pminus1, prime, 1);
877     mpi_powm( result, val_2, pminus1, prime );
878     mpi_free( pminus1 );
879     if ( mpi_cmp_ui( result, 1 ) )
880       {
881         /* Is composite. */
882         mpi_free( result );
883         progress('.');
884         return 0;
885       }
886     mpi_free( result );
887   }
888
889   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
890     {
891       /* Perform stronger tests. */
892       if ( is_prime( prime, rm_rounds, &count ) )
893         {
894           if (!cb_func
895               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
896             return 1; /* Probably a prime. */
897         }
898     }
899   progress('.');
900   return 0;
901 }
902
903
904 /*
905  * Return true if n is probably a prime
906  */
907 static int
908 is_prime (gcry_mpi_t n, int steps, unsigned int *count)
909 {
910   gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
911   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
912   gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
913   gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
914   gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
915   gcry_mpi_t q;
916   unsigned i, j, k;
917   int rc = 0;
918   unsigned nbits = mpi_get_nbits( n );
919
920   if (steps < 5) /* Make sure that we do at least 5 rounds. */
921     steps = 5;
922
923   mpi_sub_ui( nminus1, n, 1 );
924
925   /* Find q and k, so that n = 1 + 2^k * q . */
926   q = mpi_copy ( nminus1 );
927   k = mpi_trailing_zeros ( q );
928   mpi_tdiv_q_2exp (q, q, k);
929
930   for (i=0 ; i < steps; i++ )
931     {
932       ++*count;
933       if( !i )
934         {
935           mpi_set_ui( x, 2 );
936         }
937       else
938         {
939           /* We need to loop to avoid an X with value 0 or 1.  */
940           do
941             {
942               _gcry_mpi_randomize (x, nbits, GCRY_WEAK_RANDOM);
943
944               /* Make sure that the number is smaller than the prime
945                * and keep the randomness of the high bit. */
946               if (mpi_test_bit (x, nbits-2))
947                 {
948                   mpi_set_highbit (x, nbits-2); /* Clear all higher bits. */
949                 }
950               else
951                 {
952                   mpi_set_highbit (x, nbits-2);
953                   mpi_clear_bit (x, nbits-2);
954                 }
955             }
956           while (mpi_cmp_ui (x, 1) <= 0);
957           gcry_assert (mpi_cmp (x, nminus1) < 0);
958         }
959       mpi_powm ( y, x, q, n);
960       if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
961         {
962           for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
963             {
964               mpi_powm(y, y, a2, n);
965               if( !mpi_cmp_ui( y, 1 ) )
966                 goto leave; /* Not a prime. */
967             }
968           if (mpi_cmp( y, nminus1 ) )
969             goto leave; /* Not a prime. */
970         }
971       progress('+');
972     }
973   rc = 1; /* May be a prime. */
974
975  leave:
976   mpi_free( x );
977   mpi_free( y );
978   mpi_free( z );
979   mpi_free( nminus1 );
980   mpi_free( q );
981   mpi_free( a2 );
982
983   return rc;
984 }
985
986
987 /* Given ARRAY of size N with M elements set to true produce a
988    modified array with the next permutation of M elements.  Note, that
989    ARRAY is used in a one-bit-per-byte approach.  To detected the last
990    permutation it is useful to initialize the array with the first M
991    element set to true and use this test:
992        m_out_of_n (array, m, n);
993        for (i = j = 0; i < n && j < m; i++)
994          if (array[i])
995            j++;
996        if (j == m)
997          goto ready;
998
999    This code is based on the algorithm 452 from the "Collected
1000    Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang.
1001 */
1002 static void
1003 m_out_of_n ( char *array, int m, int n )
1004 {
1005   int i=0, i1=0, j=0, jp=0,  j1=0, k1=0, k2=0;
1006
1007   if( !m || m >= n )
1008     return;
1009
1010   /* Need to handle this simple case separately. */
1011   if( m == 1 )
1012     {
1013       for (i=0; i < n; i++ )
1014         {
1015           if ( array[i] )
1016             {
1017               array[i++] = 0;
1018               if( i >= n )
1019                 i = 0;
1020               array[i] = 1;
1021               return;
1022             }
1023         }
1024       BUG();
1025     }
1026
1027
1028   for (j=1; j < n; j++ )
1029     {
1030       if ( array[n-1] == array[n-j-1])
1031         continue;
1032       j1 = j;
1033       break;
1034     }
1035
1036   if ( (m & 1) )
1037     {
1038       /* M is odd. */
1039       if( array[n-1] )
1040         {
1041           if( j1 & 1 )
1042             {
1043               k1 = n - j1;
1044               k2 = k1+2;
1045               if( k2 > n )
1046                 k2 = n;
1047               goto leave;
1048             }
1049           goto scan;
1050         }
1051       k2 = n - j1 - 1;
1052       if( k2 == 0 )
1053         {
1054           k1 = i;
1055           k2 = n - j1;
1056         }
1057       else if( array[k2] && array[k2-1] )
1058         k1 = n;
1059       else
1060         k1 = k2 + 1;
1061     }
1062   else
1063     {
1064       /* M is even. */
1065       if( !array[n-1] )
1066         {
1067           k1 = n - j1;
1068           k2 = k1 + 1;
1069           goto leave;
1070         }
1071
1072       if( !(j1 & 1) )
1073         {
1074           k1 = n - j1;
1075           k2 = k1+2;
1076           if( k2 > n )
1077             k2 = n;
1078           goto leave;
1079         }
1080     scan:
1081       jp = n - j1 - 1;
1082       for (i=1; i <= jp; i++ )
1083         {
1084           i1 = jp + 2 - i;
1085           if( array[i1-1]  )
1086             {
1087               if( array[i1-2] )
1088                 {
1089                   k1 = i1 - 1;
1090                   k2 = n - j1;
1091                 }
1092               else
1093                 {
1094                   k1 = i1 - 1;
1095                   k2 = n + 1 - j1;
1096                 }
1097               goto leave;
1098             }
1099         }
1100       k1 = 1;
1101       k2 = n + 1 - m;
1102     }
1103  leave:
1104   /* Now complement the two selected bits. */
1105   array[k1-1] = !array[k1-1];
1106   array[k2-1] = !array[k2-1];
1107 }
1108
1109
1110 /* Generate a new prime number of PRIME_BITS bits and store it in
1111    PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
1112    (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
1113    non-zero, allocate a new, NULL-terminated array holding the prime
1114    factors and store it in FACTORS.  FLAGS might be used to influence
1115    the prime number generation process.  */
1116 gcry_err_code_t
1117 _gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
1118                       unsigned int factor_bits, gcry_mpi_t **factors,
1119                       gcry_prime_check_func_t cb_func, void *cb_arg,
1120                       gcry_random_level_t random_level,
1121                       unsigned int flags)
1122 {
1123   gcry_err_code_t rc = 0;
1124   gcry_mpi_t *factors_generated = NULL;
1125   gcry_mpi_t prime_generated = NULL;
1126   unsigned int mode = 0;
1127
1128   if (!prime)
1129     return GPG_ERR_INV_ARG;
1130   *prime = NULL;
1131
1132   if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
1133     mode = 1;
1134
1135   /* Generate.  */
1136   rc = prime_generate_internal ((mode==1), &prime_generated, prime_bits,
1137                                 factor_bits, NULL,
1138                                 factors? &factors_generated : NULL,
1139                                 random_level, flags, 1,
1140                                 cb_func, cb_arg);
1141
1142   if (!rc && cb_func)
1143     {
1144       /* Additional check. */
1145       if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
1146         {
1147           /* Failed, deallocate resources.  */
1148           unsigned int i;
1149
1150           mpi_free (prime_generated);
1151           if (factors)
1152             {
1153               for (i = 0; factors_generated[i]; i++)
1154                 mpi_free (factors_generated[i]);
1155               xfree (factors_generated);
1156             }
1157           rc = GPG_ERR_GENERAL;
1158         }
1159     }
1160
1161   if (!rc)
1162     {
1163       if (factors)
1164         *factors = factors_generated;
1165       *prime = prime_generated;
1166     }
1167
1168   return rc;
1169 }
1170
1171 /* Check whether the number X is prime.  */
1172 gcry_err_code_t
1173 _gcry_prime_check (gcry_mpi_t x, unsigned int flags)
1174 {
1175   (void)flags;
1176
1177   switch (mpi_cmp_ui (x, 2))
1178     {
1179     case 0:  return 0;                /* 2 is a prime */
1180     case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes.  */
1181     }
1182
1183   /* We use 64 rounds because the prime we are going to test is not
1184      guaranteed to be a random one. */
1185   if (check_prime (x, mpi_const (MPI_C_TWO), 64, NULL, NULL))
1186     return 0;
1187
1188   return GPG_ERR_NO_PRIME;
1189 }
1190
1191
1192 /* Check whether the number X is prime according to FIPS 186-4 table C.2.  */
1193 gcry_err_code_t
1194 _gcry_fips186_4_prime_check (gcry_mpi_t x, unsigned int bits)
1195 {
1196   gcry_err_code_t ec = GPG_ERR_NO_ERROR;
1197
1198   switch (mpi_cmp_ui (x, 2))
1199     {
1200     case 0:  return ec;               /* 2 is a prime */
1201     case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes.  */
1202     }
1203
1204   /* We use 5 or 4 rounds as specified in table C.2 */
1205   if (! check_prime (x, mpi_const (MPI_C_TWO), bits > 1024 ? 4 : 5, NULL, NULL))
1206     ec = GPG_ERR_NO_PRIME;
1207
1208   return ec;
1209 }
1210
1211
1212 /* Find a generator for PRIME where the factorization of (prime-1) is
1213    in the NULL terminated array FACTORS. Return the generator as a
1214    newly allocated MPI in R_G.  If START_G is not NULL, use this as s
1215    atart for the search. Returns 0 on success.*/
1216 gcry_err_code_t
1217 _gcry_prime_group_generator (gcry_mpi_t *r_g,
1218                              gcry_mpi_t prime, gcry_mpi_t *factors,
1219                              gcry_mpi_t start_g)
1220 {
1221   gcry_mpi_t tmp, b, pmin1, g;
1222   int first, i, n;
1223
1224   if (!r_g)
1225     return GPG_ERR_INV_ARG;
1226   *r_g = NULL;
1227   if (!factors || !prime)
1228     return GPG_ERR_INV_ARG;
1229
1230   for (n=0; factors[n]; n++)
1231     ;
1232   if (n < 2)
1233     return GPG_ERR_INV_ARG;
1234
1235   tmp   = mpi_new (0);
1236   b     = mpi_new (0);
1237   pmin1 = mpi_new (0);
1238   g     = start_g? mpi_copy (start_g) : mpi_set_ui (NULL, 3);
1239
1240   /* Extra sanity check - usually disabled. */
1241 /*   mpi_set (tmp, factors[0]); */
1242 /*   for(i = 1; i < n; i++) */
1243 /*     mpi_mul (tmp, tmp, factors[i]); */
1244 /*   mpi_add_ui (tmp, tmp, 1); */
1245 /*   if (mpi_cmp (prime, tmp)) */
1246 /*     return gpg_error (GPG_ERR_INV_ARG); */
1247
1248   mpi_sub_ui (pmin1, prime, 1);
1249   first = 1;
1250   do
1251     {
1252       if (first)
1253         first = 0;
1254       else
1255         mpi_add_ui (g, g, 1);
1256
1257       if (DBG_CIPHER)
1258         log_printmpi ("checking g", g);
1259       else
1260         progress('^');
1261
1262       for (i = 0; i < n; i++)
1263         {
1264           mpi_fdiv_q (tmp, pmin1, factors[i]);
1265           mpi_powm (b, g, tmp, prime);
1266           if (! mpi_cmp_ui (b, 1))
1267             break;
1268         }
1269       if (DBG_CIPHER)
1270         progress('\n');
1271     }
1272   while (i < n);
1273
1274   _gcry_mpi_release (tmp);
1275   _gcry_mpi_release (b);
1276   _gcry_mpi_release (pmin1);
1277   *r_g = g;
1278
1279   return 0;
1280 }
1281
1282 /* Convenience function to release the factors array. */
1283 void
1284 _gcry_prime_release_factors (gcry_mpi_t *factors)
1285 {
1286   if (factors)
1287     {
1288       int i;
1289
1290       for (i=0; factors[i]; i++)
1291         mpi_free (factors[i]);
1292       xfree (factors);
1293     }
1294 }
1295
1296
1297 \f
1298 /* Helper for _gcry_derive_x931_prime.  */
1299 static gcry_mpi_t
1300 find_x931_prime (const gcry_mpi_t pfirst)
1301 {
1302   gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1303   gcry_mpi_t prime;
1304
1305   prime = mpi_copy (pfirst);
1306   /* If P is even add 1.  */
1307   mpi_set_bit (prime, 0);
1308
1309   /* We use 64 Rabin-Miller rounds which is better and thus
1310      sufficient.  We do not have a Lucas test implementation thus we
1311      can't do it in the X9.31 preferred way of running a few
1312      Rabin-Miller followed by one Lucas test.  */
1313   while ( !check_prime (prime, val_2, 64, NULL, NULL) )
1314     mpi_add_ui (prime, prime, 2);
1315
1316   mpi_free (val_2);
1317
1318   return prime;
1319 }
1320
1321
1322 /* Generate a prime using the algorithm from X9.31 appendix B.4.
1323
1324    This function requires that the provided public exponent E is odd.
1325    XP, XP1 and XP2 are the seed values.  All values are mandatory.
1326
1327    On success the prime is returned.  If R_P1 or R_P2 are given the
1328    internal values P1 and P2 are saved at these addresses.  On error
1329    NULL is returned.  */
1330 gcry_mpi_t
1331 _gcry_derive_x931_prime (const gcry_mpi_t xp,
1332                          const gcry_mpi_t xp1, const gcry_mpi_t xp2,
1333                          const gcry_mpi_t e,
1334                          gcry_mpi_t *r_p1, gcry_mpi_t *r_p2)
1335 {
1336   gcry_mpi_t p1, p2, p1p2, yp0;
1337
1338   if (!xp || !xp1 || !xp2)
1339     return NULL;
1340   if (!e || !mpi_test_bit (e, 0))
1341     return NULL;  /* We support only odd values for E.  */
1342
1343   p1 = find_x931_prime (xp1);
1344   p2 = find_x931_prime (xp2);
1345   p1p2 = mpi_alloc_like (xp);
1346   mpi_mul (p1p2, p1, p2);
1347
1348   {
1349     gcry_mpi_t r1, tmp;
1350
1351     /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */
1352     tmp = mpi_alloc_like (p1);
1353     mpi_invm (tmp, p2, p1);
1354     mpi_mul (tmp, tmp, p2);
1355     r1 = tmp;
1356
1357     tmp = mpi_alloc_like (p2);
1358     mpi_invm (tmp, p1, p2);
1359     mpi_mul (tmp, tmp, p1);
1360     mpi_sub (r1, r1, tmp);
1361
1362     /* Fixup a negative value.  */
1363     if (mpi_has_sign (r1))
1364       mpi_add (r1, r1, p1p2);
1365
1366     /* yp0 = xp + (r1 - xp mod p1*p2)  */
1367     yp0 = tmp; tmp = NULL;
1368     mpi_subm (yp0, r1, xp, p1p2);
1369     mpi_add (yp0, yp0, xp);
1370     mpi_free (r1);
1371
1372     /* Fixup a negative value.  */
1373     if (mpi_cmp (yp0, xp) < 0 )
1374       mpi_add (yp0, yp0, p1p2);
1375   }
1376
1377   /* yp0 is now the first integer greater than xp with p1 being a
1378      large prime factor of yp0-1 and p2 a large prime factor of yp0+1.  */
1379
1380   /* Note that the first example from X9.31 (D.1.1) which uses
1381        (Xq1 #1A5CF72EE770DE50CB09ACCEA9#)
1382        (Xq2 #134E4CAA16D2350A21D775C404#)
1383        (Xq  #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1384              7C9953388F97DDDC3E1CA19C35CA659EDC2FC325
1385              6D29C2627479C086A699A49C4C9CEE7EF7BD1B34
1386              321DE34A#))))
1387      returns an yp0 of
1388             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1389              7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3
1390              BF20CB896EE37E098A906313271422162CB6C642
1391              75C1201F#
1392      and not
1393             #CC1092495D867E64065DEE3E7955F2EBC7D47A2D
1394              7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6
1395              C88FE299D52D78BE405A97E01FD71DD7819ECB91
1396              FA85A076#
1397      as stated in the standard.  This seems to be a bug in X9.31.
1398    */
1399
1400   {
1401     gcry_mpi_t val_2 = mpi_alloc_set_ui (2);
1402     gcry_mpi_t gcdtmp = mpi_alloc_like (yp0);
1403     int gcdres;
1404
1405     mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body.  */
1406     mpi_sub_ui (yp0, yp0, 1);   /* Ditto.  */
1407     for (;;)
1408       {
1409         gcdres = mpi_gcd (gcdtmp, e, yp0);
1410         mpi_add_ui (yp0, yp0, 1);
1411         if (!gcdres)
1412           progress ('/');  /* gcd (e, yp0-1) != 1  */
1413         else if (check_prime (yp0, val_2, 64, NULL, NULL))
1414           break; /* Found.  */
1415         /* We add p1p2-1 because yp0 is incremented after the gcd test.  */
1416         mpi_add (yp0, yp0, p1p2);
1417       }
1418     mpi_free (gcdtmp);
1419     mpi_free (val_2);
1420   }
1421
1422   mpi_free (p1p2);
1423
1424   progress('\n');
1425   if (r_p1)
1426     *r_p1 = p1;
1427   else
1428     mpi_free (p1);
1429   if (r_p2)
1430     *r_p2 = p2;
1431   else
1432     mpi_free (p2);
1433   return yp0;
1434 }
1435
1436
1437 \f
1438 /* Generate the two prime used for DSA using the algorithm specified
1439    in FIPS 186-2.  PBITS is the desired length of the prime P and a
1440    QBITS the length of the prime Q.  If SEED is not supplied and
1441    SEEDLEN is 0 the function generates an appropriate SEED.  On
1442    success the generated primes are stored at R_Q and R_P, the counter
1443    value is stored at R_COUNTER and the seed actually used for
1444    generation is stored at R_SEED and R_SEEDVALUE.  */
1445 gpg_err_code_t
1446 _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
1447                                 const void *seed, size_t seedlen,
1448                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1449                                 int *r_counter,
1450                                 void **r_seed, size_t *r_seedlen)
1451 {
1452   gpg_err_code_t ec;
1453   unsigned char seed_help_buffer[160/8];  /* Used to hold a generated SEED. */
1454   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1455   unsigned char digest[160/8];  /* Helper buffer for SHA-1 digest.  */
1456   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1457   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1458   int i;
1459
1460   unsigned char value_u[160/8];
1461   int value_n, value_b, value_k;
1462   int counter;
1463   gcry_mpi_t value_w = NULL;
1464   gcry_mpi_t value_x = NULL;
1465   gcry_mpi_t prime_q = NULL;
1466   gcry_mpi_t prime_p = NULL;
1467
1468   /* FIPS 186-2 allows only for 1024/160 bit.  */
1469   if (pbits != 1024 || qbits != 160)
1470     return GPG_ERR_INV_KEYLEN;
1471
1472   if (!seed && !seedlen)
1473     ; /* No seed value given:  We are asked to generate it.  */
1474   else if (!seed || seedlen < qbits/8)
1475     return GPG_ERR_INV_ARG;
1476
1477   /* Allocate a buffer to later compute SEED+some_increment. */
1478   seed_plus = xtrymalloc (seedlen < 20? 20:seedlen);
1479   if (!seed_plus)
1480     {
1481       ec = gpg_err_code_from_syserror ();
1482       goto leave;
1483     }
1484
1485   val_2   = mpi_alloc_set_ui (2);
1486   value_n = (pbits - 1) / qbits;
1487   value_b = (pbits - 1) - value_n * qbits;
1488   value_w = mpi_new (pbits);
1489   value_x = mpi_new (pbits);
1490
1491  restart:
1492   /* Generate Q.  */
1493   for (;;)
1494     {
1495       /* Step 1: Generate a (new) seed unless one has been supplied.  */
1496       if (!seed)
1497         {
1498           seedlen = sizeof seed_help_buffer;
1499           _gcry_create_nonce (seed_help_buffer, seedlen);
1500           seed = seed_help_buffer;
1501         }
1502
1503       /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits})  */
1504       memcpy (seed_plus, seed, seedlen);
1505       for (i=seedlen-1; i >= 0; i--)
1506         {
1507           seed_plus[i]++;
1508           if (seed_plus[i])
1509             break;
1510         }
1511       _gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen);
1512       _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1513       for (i=0; i < sizeof value_u; i++)
1514         value_u[i] ^= digest[i];
1515
1516       /* Step 3:  Form q from U  */
1517       _gcry_mpi_release (prime_q); prime_q = NULL;
1518       ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1519                            value_u, sizeof value_u, NULL);
1520       if (ec)
1521         goto leave;
1522       mpi_set_highbit (prime_q, qbits-1 );
1523       mpi_set_bit (prime_q, 0);
1524
1525       /* Step 4:  Test whether Q is prime using 64 round of Rabin-Miller.  */
1526       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1527         break; /* Yes, Q is prime.  */
1528
1529       /* Step 5.  */
1530       seed = NULL;  /* Force a new seed at Step 1.  */
1531     }
1532
1533   /* Step 6.  Note that we do no use an explicit offset but increment
1534      SEED_PLUS accordingly.  SEED_PLUS is currently SEED+1.  */
1535   counter = 0;
1536
1537   /* Generate P. */
1538   prime_p = mpi_new (pbits);
1539   for (;;)
1540     {
1541       /* Step 7: For k = 0,...n let
1542                    V_k = sha1(seed+offset+k) mod 2^{qbits}
1543          Step 8: W = V_0 + V_1*2^160 +
1544                          ...
1545                          + V_{n-1}*2^{(n-1)*160}
1546                          + (V_{n} mod 2^b)*2^{n*160}
1547        */
1548       mpi_set_ui (value_w, 0);
1549       for (value_k=0; value_k <= value_n; value_k++)
1550         {
1551           /* There is no need to have an explicit offset variable:  In
1552              the first round we shall have an offset of 2, this is
1553              achieved by using SEED_PLUS which is already at SEED+1,
1554              thus we just need to increment it once again.  The
1555              requirement for the next round is to update offset by N,
1556              which we implictly did at the end of this loop, and then
1557              to add one; this one is the same as in the first round.  */
1558           for (i=seedlen-1; i >= 0; i--)
1559             {
1560               seed_plus[i]++;
1561               if (seed_plus[i])
1562                 break;
1563             }
1564           _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
1565
1566           _gcry_mpi_release (tmpval); tmpval = NULL;
1567           ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1568                                digest, sizeof digest, NULL);
1569           if (ec)
1570             goto leave;
1571           if (value_k == value_n)
1572             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1573           mpi_lshift (tmpval, tmpval, value_k*qbits);
1574           mpi_add (value_w, value_w, tmpval);
1575         }
1576
1577       /* Step 8 continued: X = W + 2^{L-1}  */
1578       mpi_set_ui (value_x, 0);
1579       mpi_set_highbit (value_x, pbits-1);
1580       mpi_add (value_x, value_x, value_w);
1581
1582       /* Step 9:  c = X mod 2q,  p = X - (c - 1)  */
1583       mpi_mul_2exp (tmpval, prime_q, 1);
1584       mpi_mod (tmpval, value_x, tmpval);
1585       mpi_sub_ui (tmpval, tmpval, 1);
1586       mpi_sub (prime_p, value_x, tmpval);
1587
1588       /* Step 10: If  p < 2^{L-1}  skip the primality test.  */
1589       /* Step 11 and 12: Primality test.  */
1590       if (mpi_get_nbits (prime_p) >= pbits-1
1591           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1592         break; /* Yes, P is prime, continue with Step 15.  */
1593
1594       /* Step 13: counter = counter + 1, offset = offset + n + 1. */
1595       counter++;
1596
1597       /* Step 14: If counter >= 2^12  goto Step 1.  */
1598       if (counter >= 4096)
1599         goto restart;
1600     }
1601
1602   /* Step 15:  Save p, q, counter and seed.  */
1603 /*   log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
1604 /*              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1605 /*   log_printhex("fips186-2 seed:", seed, seedlen); */
1606 /*   log_mpidump ("fips186-2 prime p", prime_p); */
1607 /*   log_mpidump ("fips186-2 prime q", prime_q); */
1608   if (r_q)
1609     {
1610       *r_q = prime_q;
1611       prime_q = NULL;
1612     }
1613   if (r_p)
1614     {
1615       *r_p = prime_p;
1616       prime_p = NULL;
1617     }
1618   if (r_counter)
1619     *r_counter = counter;
1620   if (r_seed && r_seedlen)
1621     {
1622       memcpy (seed_plus, seed, seedlen);
1623       *r_seed = seed_plus;
1624       seed_plus = NULL;
1625       *r_seedlen = seedlen;
1626     }
1627
1628
1629  leave:
1630   _gcry_mpi_release (tmpval);
1631   _gcry_mpi_release (value_x);
1632   _gcry_mpi_release (value_w);
1633   _gcry_mpi_release (prime_p);
1634   _gcry_mpi_release (prime_q);
1635   xfree (seed_plus);
1636   _gcry_mpi_release (val_2);
1637   return ec;
1638 }
1639
1640
1641 \f
1642 /* WARNING: The code below has not yet been tested!
1643  *
1644  * Generate the two prime used for DSA using the algorithm specified
1645  * in FIPS 186-3, A.1.1.2.  PBITS is the desired length of the prime P
1646  * and a QBITS the length of the prime Q.  If SEED is not supplied and
1647  * SEEDLEN is 0 the function generates an appropriate SEED.  On
1648  * success the generated primes are stored at R_Q and R_P, the counter
1649  * value is stored at R_COUNTER and the seed actually used for
1650  * generation is stored at R_SEED and R_SEEDVALUE.  The hash algorithm
1651  * used is stored at R_HASHALGO.
1652  *
1653  * Note that this function is very similar to the fips186_2 code.  Due
1654  * to the minor differences, other buffer sizes and for documentarion,
1655  * we use a separate function.
1656  */
1657 gpg_err_code_t
1658 _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
1659                                 const void *seed, size_t seedlen,
1660                                 gcry_mpi_t *r_q, gcry_mpi_t *r_p,
1661                                 int *r_counter,
1662                                 void **r_seed, size_t *r_seedlen,
1663                                 int *r_hashalgo)
1664 {
1665   gpg_err_code_t ec;
1666   unsigned char seed_help_buffer[256/8];  /* Used to hold a generated SEED. */
1667   unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
1668   unsigned char digest[256/8];  /* Helper buffer for SHA-2 digest.  */
1669   gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
1670   gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
1671   int hashalgo;                 /* The id of the Approved Hash Function.  */
1672   int i;
1673
1674   unsigned char value_u[256/8];
1675   int value_n, value_b, value_j;
1676   int counter;
1677   gcry_mpi_t value_w = NULL;
1678   gcry_mpi_t value_x = NULL;
1679   gcry_mpi_t prime_q = NULL;
1680   gcry_mpi_t prime_p = NULL;
1681
1682   gcry_assert (sizeof seed_help_buffer == sizeof digest
1683                && sizeof seed_help_buffer == sizeof value_u);
1684
1685   /* Step 1:  Check the requested prime lengths.  */
1686   /* Note that due to the size of our buffers QBITS is limited to 256.  */
1687   if (pbits == 2048 && qbits == 224)
1688     hashalgo = GCRY_MD_SHA224;
1689   else if (pbits == 2048 && qbits == 256)
1690     hashalgo = GCRY_MD_SHA256;
1691   else if (pbits == 3072 && qbits == 256)
1692     hashalgo = GCRY_MD_SHA256;
1693   else
1694     return GPG_ERR_INV_KEYLEN;
1695
1696   /* Also check that the hash algorithm is available.  */
1697   ec = _gcry_md_test_algo (hashalgo);
1698   if (ec)
1699     return ec;
1700   gcry_assert (qbits/8 <= sizeof digest);
1701   gcry_assert (_gcry_md_get_algo_dlen (hashalgo) == qbits/8);
1702
1703
1704   /* Step 2:  Check seedlen.  */
1705   if (!seed && !seedlen)
1706     ; /* No seed value given:  We are asked to generate it.  */
1707   else if (!seed || seedlen < qbits/8)
1708     return GPG_ERR_INV_ARG;
1709
1710   /* Allocate a buffer to later compute SEED+some_increment and a few
1711      helper variables.  */
1712   seed_plus = xtrymalloc (seedlen < sizeof seed_help_buffer?
1713                           sizeof seed_help_buffer : seedlen);
1714   if (!seed_plus)
1715     {
1716       ec = gpg_err_code_from_syserror ();
1717       goto leave;
1718     }
1719   val_2   = mpi_alloc_set_ui (2);
1720   value_w = mpi_new (pbits);
1721   value_x = mpi_new (pbits);
1722
1723   /* Step 3: n = \lceil L / outlen \rceil - 1  */
1724   value_n = (pbits + qbits - 1) / qbits - 1;
1725   /* Step 4: b = L - 1 - (n * outlen)  */
1726   value_b = pbits - 1 - (value_n * qbits);
1727
1728  restart:
1729   /* Generate Q.  */
1730   for (;;)
1731     {
1732       /* Step 5:  Generate a (new) seed unless one has been supplied.  */
1733       if (!seed)
1734         {
1735           seedlen = qbits/8;
1736           gcry_assert (seedlen <= sizeof seed_help_buffer);
1737           _gcry_create_nonce (seed_help_buffer, seedlen);
1738           seed = seed_help_buffer;
1739         }
1740
1741       /* Step 6:  U = hash(seed)  */
1742       _gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
1743
1744       /* Step 7:  q = 2^{N-1} + U + 1 - (U mod 2)  */
1745       if ( !(value_u[qbits/8-1] & 0x01) )
1746         {
1747           for (i=qbits/8-1; i >= 0; i--)
1748             {
1749               value_u[i]++;
1750               if (value_u[i])
1751                 break;
1752             }
1753         }
1754       _gcry_mpi_release (prime_q); prime_q = NULL;
1755       ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG,
1756                            value_u, qbits/8, NULL);
1757       if (ec)
1758         goto leave;
1759       mpi_set_highbit (prime_q, qbits-1 );
1760
1761       /* Step 8:  Test whether Q is prime using 64 round of Rabin-Miller.
1762                   According to table C.1 this is sufficient for all
1763                   supported prime sizes (i.e. up 3072/256).  */
1764       if (check_prime (prime_q, val_2, 64, NULL, NULL))
1765         break; /* Yes, Q is prime.  */
1766
1767       /* Step 8.  */
1768       seed = NULL;  /* Force a new seed at Step 5.  */
1769     }
1770
1771   /* Step 11.  Note that we do no use an explicit offset but increment
1772      SEED_PLUS accordingly.  */
1773   memcpy (seed_plus, seed, seedlen);
1774   counter = 0;
1775
1776   /* Generate P. */
1777   prime_p = mpi_new (pbits);
1778   for (;;)
1779     {
1780       /* Step 11.1: For j = 0,...n let
1781                       V_j = hash(seed+offset+j)
1782          Step 11.2: W = V_0 + V_1*2^outlen +
1783                             ...
1784                             + V_{n-1}*2^{(n-1)*outlen}
1785                             + (V_{n} mod 2^b)*2^{n*outlen}
1786        */
1787       mpi_set_ui (value_w, 0);
1788       for (value_j=0; value_j <= value_n; value_j++)
1789         {
1790           /* There is no need to have an explicit offset variable: In
1791              the first round we shall have an offset of 1 and a j of
1792              0.  This is achieved by incrementing SEED_PLUS here.  For
1793              the next round offset is implicitly updated by using
1794              SEED_PLUS again.  */
1795           for (i=seedlen-1; i >= 0; i--)
1796             {
1797               seed_plus[i]++;
1798               if (seed_plus[i])
1799                 break;
1800             }
1801           _gcry_md_hash_buffer (hashalgo, digest, seed_plus, seedlen);
1802
1803           _gcry_mpi_release (tmpval); tmpval = NULL;
1804           ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
1805                                digest, qbits/8, NULL);
1806           if (ec)
1807             goto leave;
1808           if (value_j == value_n)
1809             mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */
1810           mpi_lshift (tmpval, tmpval, value_j*qbits);
1811           mpi_add (value_w, value_w, tmpval);
1812         }
1813
1814       /* Step 11.3: X = W + 2^{L-1}  */
1815       mpi_set_ui (value_x, 0);
1816       mpi_set_highbit (value_x, pbits-1);
1817       mpi_add (value_x, value_x, value_w);
1818
1819       /* Step 11.4:  c = X mod 2q  */
1820       mpi_mul_2exp (tmpval, prime_q, 1);
1821       mpi_mod (tmpval, value_x, tmpval);
1822
1823       /* Step 11.5:  p = X - (c - 1)  */
1824       mpi_sub_ui (tmpval, tmpval, 1);
1825       mpi_sub (prime_p, value_x, tmpval);
1826
1827       /* Step 11.6: If  p < 2^{L-1}  skip the primality test.  */
1828       /* Step 11.7 and 11.8: Primality test.  */
1829       if (mpi_get_nbits (prime_p) >= pbits-1
1830           && check_prime (prime_p, val_2, 64, NULL, NULL) )
1831         break; /* Yes, P is prime, continue with Step 15.  */
1832
1833       /* Step 11.9: counter = counter + 1, offset = offset + n + 1.
1834                     If counter >= 4L  goto Step 5.  */
1835       counter++;
1836       if (counter >= 4*pbits)
1837         goto restart;
1838     }
1839
1840   /* Step 12:  Save p, q, counter and seed.  */
1841   /* log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n", */
1842   /*            mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
1843   /* log_printhex ("fips186-3 seed", seed, seedlen); */
1844   /* log_printmpi ("fips186-3    p", prime_p); */
1845   /* log_printmpi ("fips186-3    q", prime_q); */
1846
1847   if (r_q)
1848     {
1849       *r_q = prime_q;
1850       prime_q = NULL;
1851     }
1852   if (r_p)
1853     {
1854       *r_p = prime_p;
1855       prime_p = NULL;
1856     }
1857   if (r_counter)
1858     *r_counter = counter;
1859   if (r_seed && r_seedlen)
1860     {
1861       memcpy (seed_plus, seed, seedlen);
1862       *r_seed = seed_plus;
1863       seed_plus = NULL;
1864       *r_seedlen = seedlen;
1865     }
1866   if (r_hashalgo)
1867     *r_hashalgo = hashalgo;
1868
1869  leave:
1870   _gcry_mpi_release (tmpval);
1871   _gcry_mpi_release (value_x);
1872   _gcry_mpi_release (value_w);
1873   _gcry_mpi_release (prime_p);
1874   _gcry_mpi_release (prime_q);
1875   xfree (seed_plus);
1876   _gcry_mpi_release (val_2);
1877   return ec;
1878 }