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