summaryrefslogtreecommitdiffabout
path: root/pwmanager/libcrypt/cipher/primegen.c
Unidiff
Diffstat (limited to 'pwmanager/libcrypt/cipher/primegen.c') (more/less context) (ignore whitespace changes)
-rw-r--r--pwmanager/libcrypt/cipher/primegen.c1028
1 files changed, 1028 insertions, 0 deletions
diff --git a/pwmanager/libcrypt/cipher/primegen.c b/pwmanager/libcrypt/cipher/primegen.c
new file mode 100644
index 0000000..afd435e
--- a/dev/null
+++ b/pwmanager/libcrypt/cipher/primegen.c
@@ -0,0 +1,1028 @@
1/* primegen.c - prime number generator
2 * Copyright (C) 1998, 2000, 2001, 2002, 2003
3 * 2004 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 * The algorithm used to generate practically save primes is due to
23 * Lim and Lee as described in the CRYPTO '97 proceedings (ISBN3540633847)
24 * page 260.
25 */
26
27#include <config.h>
28
29#include <stdio.h>
30#include <stdlib.h>
31#include <string.h>
32#include <assert.h>
33#include <errno.h>
34
35#include "g10lib.h"
36#include "mpi.h"
37#include "cipher.h"
38
39static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel,
40 int (*extra_check)(void *, gcry_mpi_t),
41 void *extra_check_arg);
42static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2,
43 gcry_prime_check_func_t cb_func, void *cb_arg );
44static int is_prime( gcry_mpi_t n, int steps, int *count );
45static void m_out_of_n( char *array, int m, int n );
46
47static void (*progress_cb) (void *,const char*,int,int, int );
48static void *progress_cb_data;
49
50/* Note: 2 is not included because it can be tested more easily by
51 looking at bit 0. The last entry in this list is marked by a zero */
52static ushort small_prime_numbers[] = {
53 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
54 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
55 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
56 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
57 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
58 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
59 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
60 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
61 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
62 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
63 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
64 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
65 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
66 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
67 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
68 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
69 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
70 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
71 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
72 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
73 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
74 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
75 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
76 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
77 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
78 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
79 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
80 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
81 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
82 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
83 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
84 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
85 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
86 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
87 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
88 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
89 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
90 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
91 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
92 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
93 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
94 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
95 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
96 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
97 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
98 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
99 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
100 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
101 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
102 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
103 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
104 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
105 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
106 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
107 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
108 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
109 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
110 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
111 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
112 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
113 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
114 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
115 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
116 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
117 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
118 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
119 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
120 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
121 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
122 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
123 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
124 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
125 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
126 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
127 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
128 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
129 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
130 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
131 4957, 4967, 4969, 4973, 4987, 4993, 4999,
132 0
133};
134static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
135
136void
137_gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int),
138 void *cb_data )
139{
140 progress_cb = cb;
141 progress_cb_data = cb_data;
142}
143
144
145static void
146progress( int c )
147{
148 if ( progress_cb )
149 progress_cb ( progress_cb_data, "primegen", c, 0, 0 );
150}
151
152
153/****************
154 * Generate a prime number (stored in secure memory)
155 */
156gcry_mpi_t
157_gcry_generate_secret_prime (unsigned int nbits,
158 int (*extra_check)(void*, gcry_mpi_t),
159 void *extra_check_arg)
160{
161 gcry_mpi_t prime;
162
163 prime = gen_prime( nbits, 1, 2, extra_check, extra_check_arg);
164 progress('\n');
165 return prime;
166}
167
168gcry_mpi_t
169_gcry_generate_public_prime( unsigned int nbits,
170 int (*extra_check)(void*, gcry_mpi_t),
171 void *extra_check_arg)
172{
173 gcry_mpi_t prime;
174
175 prime = gen_prime( nbits, 0, 2, extra_check, extra_check_arg );
176 progress('\n');
177 return prime;
178}
179
180
181/****************
182 * We do not need to use the strongest RNG because we gain no extra
183 * security from it - The prime number is public and we could also
184 * offer the factors for those who are willing to check that it is
185 * indeed a strong prime. With ALL_FACTORS set to true all afcors of
186 * prime-1 are returned in FACTORS.
187 *
188 * mode 0: Standard
189 *1: Make sure that at least one factor is of size qbits.
190 */
191static gcry_err_code_t
192prime_generate_internal (int mode,
193 gcry_mpi_t *prime_generated, unsigned int pbits,
194 unsigned int qbits, gcry_mpi_t g,
195 gcry_mpi_t **ret_factors,
196 gcry_random_level_t randomlevel, unsigned int flags,
197 int all_factors,
198 gcry_prime_check_func_t cb_func, void *cb_arg)
199{
200 gcry_err_code_t err = 0;
201 gcry_mpi_t *factors_new = NULL; /* Factors to return to the
202 caller. */
203 gcry_mpi_t *factors = NULL;/* Current factors. */
204 gcry_mpi_t *pool = NULL;/* Pool of primes. */
205 unsigned char *perms = NULL;/* Permutations of POOL. */
206 gcry_mpi_t q_factor = NULL;/* Used if QBITS is non-zero. */
207 unsigned int fbits = 0;/* Length of prime factors. */
208 unsigned int n = 0; /* Number of factors. */
209 unsigned int m = 0; /* Number of primes in pool. */
210 gcry_mpi_t q = NULL; /* First prime factor. */
211 gcry_mpi_t prime = NULL;/* Prime candidate. */
212 unsigned int nprime = 0;/* Bits of PRIME. */
213 unsigned int req_qbits; /* The original QBITS value. */
214 gcry_mpi_t val_2; /* For check_prime(). */
215 unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
216 unsigned int count1 = 0, count2 = 0;
217 unsigned int i = 0, j = 0;
218
219 if (pbits < 48)
220 return GPG_ERR_INV_ARG;
221
222 /* If QBITS is not given, assume a reasonable value. */
223 if (!qbits)
224 qbits = pbits / 3;
225
226 req_qbits = qbits;
227
228 /* Find number of needed prime factors. */
229 for (n = 1; (pbits - qbits - 1) / n >= qbits; n++)
230 ;
231 n--;
232
233 val_2 = mpi_alloc_set_ui (2);
234
235 if ((! n) || ((mode == 1) && (n < 2)))
236 {
237 err = GPG_ERR_INV_ARG;
238 goto leave;
239 }
240
241 if (mode == 1)
242 {
243 n--;
244 fbits = (pbits - 2 * req_qbits -1) / n;
245 qbits = pbits - req_qbits - n * fbits;
246 }
247 else
248 {
249 fbits = (pbits - req_qbits -1) / n;
250 qbits = pbits - n * fbits;
251 }
252
253 if (DBG_CIPHER)
254 log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
255 pbits, req_qbits, qbits, fbits, n);
256
257 prime = gcry_mpi_new (pbits);
258
259 /* Generate first prime factor. */
260 q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL);
261
262 if (mode == 1)
263 q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL);
264
265 /* Allocate an array to hold the factors + 2 for later usage. */
266 factors = gcry_calloc (n + 2, sizeof (*factors));
267 if (!factors)
268 {
269 err = gpg_err_code_from_errno (errno);
270 goto leave;
271 }
272
273 /* Make a pool of 3n+5 primes (this is an arbitrary value). */
274 m = n * 3 + 5;
275 if (mode == 1) /* Need some more (for e.g. DSA). */
276 m += 5;
277 if (m < 25)
278 m = 25;
279 pool = gcry_calloc (m , sizeof (*pool));
280 if (! pool)
281 {
282 err = gpg_err_code_from_errno (errno);
283 goto leave;
284 }
285
286 /* Permutate over the pool of primes. */
287 do
288 {
289 next_try:
290 if (! perms)
291 {
292 /* Allocate new primes. */
293 for(i = 0; i < m; i++)
294 {
295 mpi_free (pool[i]);
296 pool[i] = NULL;
297 }
298
299 /* Init m_out_of_n(). */
300 perms = gcry_calloc (1, m);
301 if (! perms)
302 {
303 err = gpg_err_code_from_errno (errno);
304 goto leave;
305 }
306 for(i = 0; i < n; i++)
307 {
308 perms[i] = 1;
309 pool[i] = gen_prime (fbits, is_secret,
310 randomlevel, NULL, NULL);
311 factors[i] = pool[i];
312 }
313 }
314 else
315 {
316 m_out_of_n (perms, n, m);
317 for (i = j = 0; (i < m) && (j < n); i++)
318 if (perms[i])
319 {
320 if(! pool[i])
321 pool[i] = gen_prime (fbits, 0, 1, NULL, NULL);
322 factors[j++] = pool[i];
323 }
324 if (i == n)
325 {
326 gcry_free (perms);
327 perms = NULL;
328 progress ('!');
329 goto next_try;/* Allocate new primes. */
330 }
331 }
332
333 /* Generate next prime candidate:
334 p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.
335 */
336 mpi_set (prime, q);
337 mpi_mul_ui (prime, prime, 2);
338 if (mode == 1)
339 mpi_mul (prime, prime, q_factor);
340 for(i = 0; i < n; i++)
341 mpi_mul (prime, prime, factors[i]);
342 mpi_add_ui (prime, prime, 1);
343 nprime = mpi_get_nbits (prime);
344
345 if (nprime < pbits)
346 {
347 if (++count1 > 20)
348 {
349 count1 = 0;
350 qbits++;
351 progress('>');
352 mpi_free (q);
353 q = gen_prime (qbits, 0, 0, NULL, NULL);
354 goto next_try;
355 }
356 }
357 else
358 count1 = 0;
359
360 if (nprime > pbits)
361 {
362 if (++count2 > 20)
363 {
364 count2 = 0;
365 qbits--;
366 progress('<');
367 mpi_free (q);
368 q = gen_prime (qbits, 0, 0, NULL, NULL);
369 goto next_try;
370 }
371 }
372 else
373 count2 = 0;
374 }
375 while (! ((nprime == pbits) && check_prime (prime, val_2, cb_func, cb_arg)));
376
377 if (DBG_CIPHER)
378 {
379 progress ('\n');
380 log_mpidump ("prime : ", prime);
381 log_mpidump ("factor q: ", q);
382 if (mode == 1)
383 log_mpidump ("factor q0: ", q_factor);
384 for (i = 0; i < n; i++)
385 log_mpidump ("factor pi: ", factors[i]);
386 log_debug ("bit sizes: prime=%u, q=%u",
387 mpi_get_nbits (prime), mpi_get_nbits (q));
388 if (mode == 1)
389 log_debug (", q0=%u", mpi_get_nbits (q_factor));
390 for (i = 0; i < n; i++)
391 log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
392 progress('\n');
393 }
394
395 if (ret_factors)
396 {
397 /* Caller wants the factors. */
398 factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
399 if (! factors_new)
400 {
401 err = gpg_err_code_from_errno (errno);
402 goto leave;
403 }
404
405 if (all_factors)
406 {
407 i = 0;
408 factors_new[i++] = gcry_mpi_set_ui (NULL, 2);
409 factors_new[i++] = mpi_copy (q);
410 if (mode == 1)
411 factors_new[i++] = mpi_copy (q_factor);
412 for(j=0; j < n; j++)
413 factors_new[i++] = mpi_copy (factors[j]);
414 }
415 else
416 {
417 i = 0;
418 if (mode == 1)
419 {
420 factors_new[i++] = mpi_copy (q_factor);
421 for (; i <= n; i++)
422 factors_new[i] = mpi_copy (factors[i]);
423 }
424 else
425 for (; i < n; i++ )
426 factors_new[i] = mpi_copy (factors[i]);
427 }
428 }
429
430 if (g)
431 {
432 /* Create a generator (start with 3). */
433 gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
434 gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
435 gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
436
437 if (mode == 1)
438 err = GPG_ERR_NOT_IMPLEMENTED;
439 else
440 {
441 factors[n] = q;
442 factors[n + 1] = mpi_alloc_set_ui (2);
443 mpi_sub_ui (pmin1, prime, 1);
444 mpi_set_ui (g, 2);
445 do
446 {
447 mpi_add_ui (g, g, 1);
448 if (DBG_CIPHER)
449 {
450 log_debug ("checking g:");
451 gcry_mpi_dump (g);
452 log_printf ("\n");
453 }
454 else
455 progress('^');
456 for (i = 0; i < n + 2; i++)
457 {
458 mpi_fdiv_q (tmp, pmin1, factors[i]);
459 /* No mpi_pow(), but it is okay to use this with mod
460 prime. */
461 gcry_mpi_powm (b, g, tmp, prime);
462 if (! mpi_cmp_ui (b, 1))
463 break;
464 }
465 if (DBG_CIPHER)
466 progress('\n');
467 }
468 while (i < n + 2);
469
470 mpi_free (factors[n+1]);
471 mpi_free (tmp);
472 mpi_free (b);
473 mpi_free (pmin1);
474 }
475 }
476
477 if (! DBG_CIPHER)
478 progress ('\n');
479
480
481 leave:
482 if (pool)
483 {
484 for(i = 0; i < m; i++)
485 mpi_free (pool[i]);
486 gcry_free (pool);
487 }
488 if (factors)
489 gcry_free (factors); /* Factors are shallow copies. */
490 if (perms)
491 gcry_free (perms);
492
493 mpi_free (val_2);
494 mpi_free (q);
495 mpi_free (q_factor);
496
497 if (! err)
498 {
499 *prime_generated = prime;
500 if (ret_factors)
501 *ret_factors = factors_new;
502 }
503 else
504 {
505 if (factors_new)
506 {
507 for (i = 0; factors_new[i]; i++)
508 mpi_free (factors_new[i]);
509 gcry_free (factors_new);
510 }
511 mpi_free (prime);
512 }
513
514 return err;
515}
516
517gcry_mpi_t
518_gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
519 gcry_mpi_t g, gcry_mpi_t **ret_factors)
520{
521 gcry_err_code_t err = GPG_ERR_NO_ERROR;
522 gcry_mpi_t prime = NULL;
523
524 err = prime_generate_internal (mode, &prime, pbits, qbits, g,
525 ret_factors, GCRY_WEAK_RANDOM, 0, 0,
526 NULL, NULL);
527
528 return prime;
529}
530
531static gcry_mpi_t
532gen_prime (unsigned int nbits, int secret, int randomlevel,
533 int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg)
534{
535 gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result;
536 int i;
537 unsigned x, step;
538 unsigned count1, count2;
539 int *mods;
540
541/* if ( DBG_CIPHER ) */
542/* log_debug ("generate a prime of %u bits ", nbits ); */
543
544 if (nbits < 16)
545 log_fatal ("can't generate a prime with less than %d bits\n", 16);
546
547 mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
548 /* Make nbits fit into gcry_mpi_t implementation. */
549 val_2 = mpi_alloc_set_ui( 2 );
550 val_3 = mpi_alloc_set_ui( 3);
551 prime = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
552 result = mpi_alloc_like( prime );
553 pminus1= mpi_alloc_like( prime );
554 ptest = mpi_alloc_like( prime );
555 count1 = count2 = 0;
556 for (;;)
557 { /* try forvever */
558 int dotcount=0;
559
560 /* generate a random number */
561 gcry_mpi_randomize( prime, nbits, randomlevel );
562
563 /* Set high order bit to 1, set low order bit to 1. If we are
564 generating a secret prime we are most probably doing that
565 for RSA, to make sure that the modulus does have the
566 requested key size we set the 2 high order bits. */
567 mpi_set_highbit (prime, nbits-1);
568 if (secret)
569 mpi_set_bit (prime, nbits-2);
570 mpi_set_bit(prime, 0);
571
572 /* Calculate all remainders. */
573 for (i=0; (x = small_prime_numbers[i]); i++ )
574 mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
575
576 /* Now try some primes starting with prime. */
577 for(step=0; step < 20000; step += 2 )
578 {
579 /* Check against all the small primes we have in mods. */
580 count1++;
581 for (i=0; (x = small_prime_numbers[i]); i++ )
582 {
583 while ( mods[i] + step >= x )
584 mods[i] -= x;
585 if ( !(mods[i] + step) )
586 break;
587 }
588 if ( x )
589 continue; /* Found a multiple of an already known prime. */
590
591 mpi_add_ui( ptest, prime, step );
592
593 /* Do a fast Fermat test now. */
594 count2++;
595 mpi_sub_ui( pminus1, ptest, 1);
596 gcry_mpi_powm( result, val_2, pminus1, ptest );
597 if ( !mpi_cmp_ui( result, 1 ) )
598 {
599 /* Not composite, perform stronger tests */
600 if (is_prime(ptest, 5, &count2 ))
601 {
602 if (!mpi_test_bit( ptest, nbits-1-secret ))
603 {
604 progress('\n');
605 log_debug ("overflow in prime generation\n");
606 break; /* Stop loop, continue with a new prime. */
607 }
608
609 if (extra_check && extra_check (extra_check_arg, ptest))
610 {
611 /* The extra check told us that this prime is
612 not of the caller's taste. */
613 progress ('/');
614 }
615 else
616 {
617 /* Got it. */
618 mpi_free(val_2);
619 mpi_free(val_3);
620 mpi_free(result);
621 mpi_free(pminus1);
622 mpi_free(prime);
623 gcry_free(mods);
624 return ptest;
625 }
626 }
627 }
628 if (++dotcount == 10 )
629 {
630 progress('.');
631 dotcount = 0;
632 }
633 }
634 progress(':'); /* restart with a new random value */
635 }
636}
637
638/****************
639 * Returns: true if this may be a prime
640 */
641static int
642check_prime( gcry_mpi_t prime, gcry_mpi_t val_2,
643 gcry_prime_check_func_t cb_func, void *cb_arg)
644{
645 int i;
646 unsigned int x;
647 int count=0;
648
649 /* Check against small primes. */
650 for (i=0; (x = small_prime_numbers[i]); i++ )
651 {
652 if ( mpi_divisible_ui( prime, x ) )
653 return 0;
654 }
655
656 /* A quick Fermat test. */
657 {
658 gcry_mpi_t result = mpi_alloc_like( prime );
659 gcry_mpi_t pminus1 = mpi_alloc_like( prime );
660 mpi_sub_ui( pminus1, prime, 1);
661 gcry_mpi_powm( result, val_2, pminus1, prime );
662 mpi_free( pminus1 );
663 if ( mpi_cmp_ui( result, 1 ) )
664 {
665 /* Is composite. */
666 mpi_free( result );
667 progress('.');
668 return 0;
669 }
670 mpi_free( result );
671 }
672
673 if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
674 {
675 /* Perform stronger tests. */
676 if ( is_prime( prime, 5, &count ) )
677 {
678 if (!cb_func
679 || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
680 return 1; /* Probably a prime. */
681 }
682 }
683 progress('.');
684 return 0;
685}
686
687
688/*
689 * Return true if n is probably a prime
690 */
691static int
692is_prime (gcry_mpi_t n, int steps, int *count)
693{
694 gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) );
695 gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) );
696 gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) );
697 gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
698 gcry_mpi_t a2 = mpi_alloc_set_ui( 2 );
699 gcry_mpi_t q;
700 unsigned i, j, k;
701 int rc = 0;
702 unsigned nbits = mpi_get_nbits( n );
703
704 mpi_sub_ui( nminus1, n, 1 );
705
706 /* Find q and k, so that n = 1 + 2^k * q . */
707 q = mpi_copy ( nminus1 );
708 k = mpi_trailing_zeros ( q );
709 mpi_tdiv_q_2exp (q, q, k);
710
711 for (i=0 ; i < steps; i++ )
712 {
713 ++*count;
714 if( !i )
715 {
716 mpi_set_ui( x, 2 );
717 }
718 else
719 {
720 gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
721
722 /* Make sure that the number is smaller than the prime and
723 keep the randomness of the high bit. */
724 if ( mpi_test_bit ( x, nbits-2) )
725 {
726 mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */
727 }
728 else
729 {
730 mpi_set_highbit( x, nbits-2 );
731 mpi_clear_bit( x, nbits-2 );
732 }
733 assert ( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
734 }
735 gcry_mpi_powm ( y, x, q, n);
736 if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) )
737 {
738 for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ )
739 {
740 gcry_mpi_powm(y, y, a2, n);
741 if( !mpi_cmp_ui( y, 1 ) )
742 goto leave; /* Not a prime. */
743 }
744 if (mpi_cmp( y, nminus1 ) )
745 goto leave; /* Not a prime. */
746 }
747 progress('+');
748 }
749 rc = 1; /* May be a prime. */
750
751 leave:
752 mpi_free( x );
753 mpi_free( y );
754 mpi_free( z );
755 mpi_free( nminus1 );
756 mpi_free( q );
757 mpi_free( a2 );
758
759 return rc;
760}
761
762
763static void
764m_out_of_n ( char *array, int m, int n )
765{
766 int i=0, i1=0, j=0, jp=0, j1=0, k1=0, k2=0;
767
768 if( !m || m >= n )
769 return;
770
771 if( m == 1 )
772 {
773 /* Special case. */
774 for (i=0; i < n; i++ )
775 {
776 if( array[i] )
777 {
778 array[i++] = 0;
779 if( i >= n )
780 i = 0;
781 array[i] = 1;
782 return;
783 }
784 }
785 BUG();
786 }
787
788 for (j=1; j < n; j++ )
789 {
790 if ( array[n-1] == array[n-j-1])
791 continue;
792 j1 = j;
793 break;
794 }
795
796 if ( (m & 1) )
797 {
798 /* M is odd. */
799 if( array[n-1] )
800 {
801 if( j1 & 1 )
802 {
803 k1 = n - j1;
804 k2 = k1+2;
805 if( k2 > n )
806 k2 = n;
807 goto leave;
808 }
809 goto scan;
810 }
811 k2 = n - j1 - 1;
812 if( k2 == 0 )
813 {
814 k1 = i;
815 k2 = n - j1;
816 }
817 else if( array[k2] && array[k2-1] )
818 k1 = n;
819 else
820 k1 = k2 + 1;
821 }
822 else
823 {
824 /* M is even. */
825 if( !array[n-1] )
826 {
827 k1 = n - j1;
828 k2 = k1 + 1;
829 goto leave;
830 }
831
832 if( !(j1 & 1) )
833 {
834 k1 = n - j1;
835 k2 = k1+2;
836 if( k2 > n )
837 k2 = n;
838 goto leave;
839 }
840 scan:
841 jp = n - j1 - 1;
842 for (i=1; i <= jp; i++ )
843 {
844 i1 = jp + 2 - i;
845 if( array[i1-1] )
846 {
847 if( array[i1-2] )
848 {
849 k1 = i1 - 1;
850 k2 = n - j1;
851 }
852 else
853 {
854 k1 = i1 - 1;
855 k2 = n + 1 - j1;
856 }
857 goto leave;
858 }
859 }
860 k1 = 1;
861 k2 = n + 1 - m;
862 }
863 leave:
864 array[k1-1] = !array[k1-1];
865 array[k2-1] = !array[k2-1];
866}
867
868
869/* Generate a new prime number of PRIME_BITS bits and store it in
870 PRIME. If FACTOR_BITS is non-zero, one of the prime factors of
871 (prime - 1) / 2 must be FACTOR_BITS bits long. If FACTORS is
872 non-zero, allocate a new, NULL-terminated array holding the prime
873 factors and store it in FACTORS. FLAGS might be used to influence
874 the prime number generation process. */
875gcry_error_t
876gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
877 unsigned int factor_bits, gcry_mpi_t **factors,
878 gcry_prime_check_func_t cb_func, void *cb_arg,
879 gcry_random_level_t random_level,
880 unsigned int flags)
881{
882 gcry_err_code_t err = GPG_ERR_NO_ERROR;
883 gcry_mpi_t *factors_generated = NULL;
884 gcry_mpi_t prime_generated = NULL;
885 unsigned int mode = 0;
886
887 if (!prime)
888 return gpg_error (GPG_ERR_INV_ARG);
889 *prime = NULL;
890
891 if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
892 mode = 1;
893
894 /* Generate. */
895 err = prime_generate_internal (mode, &prime_generated, prime_bits,
896 factor_bits, NULL,
897 factors? &factors_generated : NULL,
898 random_level, flags, 1,
899 cb_func, cb_arg);
900
901 if (! err)
902 if (cb_func)
903 {
904 /* Additional check. */
905 if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated))
906 {
907 /* Failed, deallocate resources. */
908 unsigned int i;
909
910 mpi_free (prime_generated);
911 if (factors)
912 {
913 for (i = 0; factors_generated[i]; i++)
914 mpi_free (factors_generated[i]);
915 gcry_free (factors_generated);
916 }
917 err = GPG_ERR_GENERAL;
918 }
919 }
920
921 if (! err)
922 {
923 if (factors)
924 *factors = factors_generated;
925 *prime = prime_generated;
926 }
927
928 return gcry_error (err);
929}
930
931/* Check wether the number X is prime. */
932gcry_error_t
933gcry_prime_check (gcry_mpi_t x, unsigned int flags)
934{
935 gcry_err_code_t err = GPG_ERR_NO_ERROR;
936 gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
937
938 if (! check_prime (x, val_2, NULL, NULL))
939 err = GPG_ERR_NO_PRIME;
940
941 mpi_free (val_2);
942
943 return gcry_error (err);
944}
945
946/* Find a generator for PRIME where the factorization of (prime-1) is
947 in the NULL terminated array FACTORS. Return the generator as a
948 newly allocated MPI in R_G. If START_G is not NULL, use this as s
949 atart for the search. Returns 0 on success.*/
950gcry_error_t
951gcry_prime_group_generator (gcry_mpi_t *r_g,
952 gcry_mpi_t prime, gcry_mpi_t *factors,
953 gcry_mpi_t start_g)
954{
955 gcry_mpi_t tmp = gcry_mpi_new (0);
956 gcry_mpi_t b = gcry_mpi_new (0);
957 gcry_mpi_t pmin1 = gcry_mpi_new (0);
958 gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
959 int first = 1;
960 int i, n;
961
962 if (!factors || !r_g || !prime)
963 return gpg_error (GPG_ERR_INV_ARG);
964 *r_g = NULL;
965
966 for (n=0; factors[n]; n++)
967 ;
968 if (n < 2)
969 return gpg_error (GPG_ERR_INV_ARG);
970
971 /* Extra sanity check - usually disabled. */
972/* mpi_set (tmp, factors[0]); */
973/* for(i = 1; i < n; i++) */
974/* mpi_mul (tmp, tmp, factors[i]); */
975/* mpi_add_ui (tmp, tmp, 1); */
976/* if (mpi_cmp (prime, tmp)) */
977/* return gpg_error (GPG_ERR_INV_ARG); */
978
979 gcry_mpi_sub_ui (pmin1, prime, 1);
980 do
981 {
982 if (first)
983 first = 0;
984 else
985 gcry_mpi_add_ui (g, g, 1);
986
987 if (DBG_CIPHER)
988 {
989 log_debug ("checking g:");
990 gcry_mpi_dump (g);
991 log_debug ("\n");
992 }
993 else
994 progress('^');
995
996 for (i = 0; i < n; i++)
997 {
998 mpi_fdiv_q (tmp, pmin1, factors[i]);
999 gcry_mpi_powm (b, g, tmp, prime);
1000 if (! mpi_cmp_ui (b, 1))
1001 break;
1002 }
1003 if (DBG_CIPHER)
1004 progress('\n');
1005 }
1006 while (i < n);
1007
1008 gcry_mpi_release (tmp);
1009 gcry_mpi_release (b);
1010 gcry_mpi_release (pmin1);
1011 *r_g = g;
1012
1013 return 0;
1014}
1015
1016/* Convenience function to release the factors array. */
1017void
1018gcry_prime_release_factors (gcry_mpi_t *factors)
1019{
1020 if (factors)
1021 {
1022 int i;
1023
1024 for (i=0; factors[i]; i++)
1025 mpi_free (factors[i]);
1026 gcry_free (factors);
1027 }
1028}