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