/* primegen.c - prime number generator * Copyright (C) 1998, 2000, 2001, 2002, 2003 * 2004, 2008 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser general Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "ath.h" static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg); static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds, gcry_prime_check_func_t cb_func, void *cb_arg ); static int is_prime (gcry_mpi_t n, int steps, unsigned int *count); static void m_out_of_n( char *array, int m, int n ); static void (*progress_cb) (void *,const char*,int,int, int ); static void *progress_cb_data; /* Note: 2 is not included because it can be tested more easily by looking at bit 0. The last entry in this list is marked by a zero */ static ushort small_prime_numbers[] = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 0 }; static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1; /* An object and a list to build up a global pool of primes. See save_pool_prime and get_pool_prime. */ struct primepool_s { struct primepool_s *next; gcry_mpi_t prime; /* If this is NULL the entry is not used. */ unsigned int nbits; gcry_random_level_t randomlevel; }; struct primepool_s *primepool; /* Mutex used to protect access to the primepool. */ static ath_mutex_t primepool_lock; gcry_err_code_t _gcry_primegen_init (void) { gcry_err_code_t ec; ec = ath_mutex_init (&primepool_lock); if (ec) return gpg_err_code_from_errno (ec); return ec; } /* Save PRIME which has been generated at RANDOMLEVEL for later use. Needs to be called while primepool_lock is being hold. Note that PRIME should be considered released after calling this function. */ static void save_pool_prime (gcry_mpi_t prime, gcry_random_level_t randomlevel) { struct primepool_s *item, *item2; size_t n; for (n=0, item = primepool; item; item = item->next, n++) if (!item->prime) break; if (!item && n > 100) { /* Remove some of the entries. Our strategy is removing the last third from the list. */ int i; for (i=0, item2 = primepool; item2; item2 = item2->next) { if (i >= n/3*2) { _gcry_mpi_release (item2->prime); item2->prime = NULL; if (!item) item = item2; } } } if (!item) { item = xtrycalloc (1, sizeof *item); if (!item) { /* Out of memory. Silently giving up. */ _gcry_mpi_release (prime); return; } item->next = primepool; primepool = item; } item->prime = prime; item->nbits = mpi_get_nbits (prime); item->randomlevel = randomlevel; } /* Return a prime for the prime pool or NULL if none has been found. The prime needs to match NBITS and randomlevel. This function needs to be called with the primepool_look is being hold. */ static gcry_mpi_t get_pool_prime (unsigned int nbits, gcry_random_level_t randomlevel) { struct primepool_s *item; for (item = primepool; item; item = item->next) if (item->prime && item->nbits == nbits && item->randomlevel == randomlevel) { gcry_mpi_t prime = item->prime; item->prime = NULL; gcry_assert (nbits == mpi_get_nbits (prime)); return prime; } return NULL; } void _gcry_register_primegen_progress ( void (*cb)(void *,const char*,int,int,int), void *cb_data ) { progress_cb = cb; progress_cb_data = cb_data; } static void progress( int c ) { if ( progress_cb ) progress_cb ( progress_cb_data, "primegen", c, 0, 0 ); } /**************** * Generate a prime number (stored in secure memory) */ gcry_mpi_t _gcry_generate_secret_prime (unsigned int nbits, gcry_random_level_t random_level, int (*extra_check)(void*, gcry_mpi_t), void *extra_check_arg) { gcry_mpi_t prime; prime = gen_prime (nbits, 1, random_level, extra_check, extra_check_arg); progress('\n'); return prime; } /* Generate a prime number which may be public, i.e. not allocated in secure memory. */ gcry_mpi_t _gcry_generate_public_prime (unsigned int nbits, gcry_random_level_t random_level, int (*extra_check)(void*, gcry_mpi_t), void *extra_check_arg) { gcry_mpi_t prime; prime = gen_prime (nbits, 0, random_level, extra_check, extra_check_arg); progress('\n'); return prime; } /* Core prime generation function. The algorithm used to generate practically save primes is due to Lim and Lee as described in the CRYPTO '97 proceedings (ISBN3540633847) page 260. NEED_Q_FACTOR: If true make sure that at least one factor is of size qbits. This is for example required for DSA. PRIME_GENERATED: Adresss of a variable where the resulting prime number will be stored. PBITS: Requested size of the prime number. At least 48. QBITS: One factor of the prime needs to be of this size. Maybe 0 if this is not required. See also MODE. G: If not NULL an MPI which will receive a generator for the prime for use with Elgamal. RET_FACTORS: if not NULL, an array with all factors are stored at that address. ALL_FACTORS: If set to true all factors of prime-1 are returned. RANDOMLEVEL: How strong should the random numers be. FLAGS: Prime generation bit flags. Currently supported: GCRY_PRIME_FLAG_SECRET - The prime needs to be kept secret. CB_FUNC, CB_ARG: Callback to be used for extra checks. */ static gcry_err_code_t prime_generate_internal (int need_q_factor, gcry_mpi_t *prime_generated, unsigned int pbits, unsigned int qbits, gcry_mpi_t g, gcry_mpi_t **ret_factors, gcry_random_level_t randomlevel, unsigned int flags, int all_factors, gcry_prime_check_func_t cb_func, void *cb_arg) { gcry_err_code_t err = 0; gcry_mpi_t *factors_new = NULL; /* Factors to return to the caller. */ gcry_mpi_t *factors = NULL; /* Current factors. */ gcry_random_level_t poolrandomlevel; /* Random level used for pool primes. */ gcry_mpi_t *pool = NULL; /* Pool of primes. */ int *pool_in_use = NULL; /* Array with currently used POOL elements. */ unsigned char *perms = NULL; /* Permutations of POOL. */ gcry_mpi_t q_factor = NULL; /* Used if QBITS is non-zero. */ unsigned int fbits = 0; /* Length of prime factors. */ unsigned int n = 0; /* Number of factors. */ unsigned int m = 0; /* Number of primes in pool. */ gcry_mpi_t q = NULL; /* First prime factor. */ gcry_mpi_t prime = NULL; /* Prime candidate. */ unsigned int nprime = 0; /* Bits of PRIME. */ unsigned int req_qbits; /* The original QBITS value. */ gcry_mpi_t val_2; /* For check_prime(). */ int is_locked = 0; /* Flag to help unlocking the primepool. */ unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET); unsigned int count1 = 0, count2 = 0; unsigned int i = 0, j = 0; if (pbits < 48) return GPG_ERR_INV_ARG; /* We won't use a too strong random elvel for the pooled subprimes. */ poolrandomlevel = (randomlevel > GCRY_STRONG_RANDOM? GCRY_STRONG_RANDOM : randomlevel); /* If QBITS is not given, assume a reasonable value. */ if (!qbits) qbits = pbits / 3; req_qbits = qbits; /* Find number of needed prime factors N. */ for (n = 1; (pbits - qbits - 1) / n >= qbits; n++) ; n--; val_2 = mpi_alloc_set_ui (2); if ((! n) || ((need_q_factor) && (n < 2))) { err = GPG_ERR_INV_ARG; goto leave; } if (need_q_factor) { n--; /* Need one factor less because we want a specific Q-FACTOR. */ fbits = (pbits - 2 * req_qbits -1) / n; qbits = pbits - req_qbits - n * fbits; } else { fbits = (pbits - req_qbits -1) / n; qbits = pbits - n * fbits; } if (DBG_CIPHER) log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n", pbits, req_qbits, qbits, fbits, n); /* Allocate an integer to old the new prime. */ prime = mpi_new (pbits); /* Generate first prime factor. */ q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); /* Generate a specific Q-Factor if requested. */ if (need_q_factor) q_factor = gen_prime (req_qbits, is_secret, randomlevel, NULL, NULL); /* Allocate an array to hold all factors + 2 for later usage. */ factors = xtrycalloc (n + 2, sizeof (*factors)); if (!factors) { err = gpg_err_code_from_errno (errno); goto leave; } /* Allocate an array to track pool usage. */ pool_in_use = xtrymalloc (n * sizeof *pool_in_use); if (!pool_in_use) { err = gpg_err_code_from_errno (errno); goto leave; } for (i=0; i < n; i++) pool_in_use[i] = -1; /* Make a pool of 3n+5 primes (this is an arbitrary value). We require at least 30 primes for are useful selection process. Fixme: We need to research the best formula for sizing the pool. */ m = n * 3 + 5; if (need_q_factor) /* Need some more in this case. */ m += 5; if (m < 30) m = 30; pool = xtrycalloc (m , sizeof (*pool)); if (! pool) { err = gpg_err_code_from_errno (errno); goto leave; } /* Permutate over the pool of primes until we find a prime of the requested length. */ do { next_try: for (i=0; i < n; i++) pool_in_use[i] = -1; if (!perms) { /* Allocate new primes. This is done right at the beginning of the loop and if we have later run out of primes. */ for (i = 0; i < m; i++) { mpi_free (pool[i]); pool[i] = NULL; } /* Init m_out_of_n(). */ perms = xtrycalloc (1, m); if (!perms) { err = gpg_err_code_from_errno (errno); goto leave; } if (ath_mutex_lock (&primepool_lock)) { err = GPG_ERR_INTERNAL; goto leave; } is_locked = 1; for (i = 0; i < n; i++) { perms[i] = 1; /* At a maximum we use strong random for the factors. This saves us a lot of entropy. Given that Q and possible Q-factor are also used in the final prime this should be acceptable. We also don't allocate in secure memory to save on that scare resource too. If Q has been allocated in secure memory, the final prime will be saved there anyway. This is because our MPI routines take care of that. GnuPG has worked this way ever since. */ pool[i] = NULL; if (is_locked) { pool[i] = get_pool_prime (fbits, poolrandomlevel); if (!pool[i]) { if (ath_mutex_unlock (&primepool_lock)) { err = GPG_ERR_INTERNAL; goto leave; } is_locked = 0; } } if (!pool[i]) pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL); pool_in_use[i] = i; factors[i] = pool[i]; } if (is_locked && ath_mutex_unlock (&primepool_lock)) { err = GPG_ERR_INTERNAL; goto leave; } is_locked = 0; } else { /* Get next permutation. */ m_out_of_n ( (char*)perms, n, m); if (ath_mutex_lock (&primepool_lock)) { err = GPG_ERR_INTERNAL; goto leave; } is_locked = 1; for (i = j = 0; (i < m) && (j < n); i++) if (perms[i]) { /* If the subprime has not yet beed generated do it now. */ if (!pool[i] && is_locked) { pool[i] = get_pool_prime (fbits, poolrandomlevel); if (!pool[i]) { if (ath_mutex_unlock (&primepool_lock)) { err = GPG_ERR_INTERNAL; goto leave; } is_locked = 0; } } if (!pool[i]) pool[i] = gen_prime (fbits, 0, poolrandomlevel, NULL, NULL); pool_in_use[j] = i; factors[j++] = pool[i]; } if (is_locked && ath_mutex_unlock (&primepool_lock)) { err = GPG_ERR_INTERNAL; goto leave; } is_locked = 0; if (i == n) { /* Ran out of permutations: Allocate new primes. */ xfree (perms); perms = NULL; progress ('!'); goto next_try; } } /* Generate next prime candidate: p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1. */ mpi_set (prime, q); mpi_mul_ui (prime, prime, 2); if (need_q_factor) mpi_mul (prime, prime, q_factor); for(i = 0; i < n; i++) mpi_mul (prime, prime, factors[i]); mpi_add_ui (prime, prime, 1); nprime = mpi_get_nbits (prime); if (nprime < pbits) { if (++count1 > 20) { count1 = 0; qbits++; progress('>'); mpi_free (q); q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); goto next_try; } } else count1 = 0; if (nprime > pbits) { if (++count2 > 20) { count2 = 0; qbits--; progress('<'); mpi_free (q); q = gen_prime (qbits, is_secret, randomlevel, NULL, NULL); goto next_try; } } else count2 = 0; } while (! ((nprime == pbits) && check_prime (prime, val_2, 5, cb_func, cb_arg))); if (DBG_CIPHER) { progress ('\n'); log_mpidump ("prime ", prime); log_mpidump ("factor q", q); if (need_q_factor) log_mpidump ("factor q0", q_factor); for (i = 0; i < n; i++) log_mpidump ("factor pi", factors[i]); log_debug ("bit sizes: prime=%u, q=%u", mpi_get_nbits (prime), mpi_get_nbits (q)); if (need_q_factor) log_printf (", q0=%u", mpi_get_nbits (q_factor)); for (i = 0; i < n; i++) log_printf (", p%d=%u", i, mpi_get_nbits (factors[i])); log_printf ("\n"); } if (ret_factors) { /* Caller wants the factors. */ factors_new = xtrycalloc (n + 4, sizeof (*factors_new)); if (! factors_new) { err = gpg_err_code_from_errno (errno); goto leave; } if (all_factors) { i = 0; factors_new[i++] = mpi_set_ui (NULL, 2); factors_new[i++] = mpi_copy (q); if (need_q_factor) factors_new[i++] = mpi_copy (q_factor); for(j=0; j < n; j++) factors_new[i++] = mpi_copy (factors[j]); } else { i = 0; if (need_q_factor) { factors_new[i++] = mpi_copy (q_factor); for (; i <= n; i++) factors_new[i] = mpi_copy (factors[i]); } else for (; i < n; i++ ) factors_new[i] = mpi_copy (factors[i]); } } if (g) { /* Create a generator (start with 3). */ gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime)); gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime)); gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime)); if (need_q_factor) err = GPG_ERR_NOT_IMPLEMENTED; else { factors[n] = q; factors[n + 1] = mpi_alloc_set_ui (2); mpi_sub_ui (pmin1, prime, 1); mpi_set_ui (g, 2); do { mpi_add_ui (g, g, 1); if (DBG_CIPHER) log_printmpi ("checking g", g); else progress('^'); for (i = 0; i < n + 2; i++) { mpi_fdiv_q (tmp, pmin1, factors[i]); /* No mpi_pow(), but it is okay to use this with mod prime. */ mpi_powm (b, g, tmp, prime); if (! mpi_cmp_ui (b, 1)) break; } if (DBG_CIPHER) progress('\n'); } while (i < n + 2); mpi_free (factors[n+1]); mpi_free (tmp); mpi_free (b); mpi_free (pmin1); } } if (! DBG_CIPHER) progress ('\n'); leave: if (pool) { is_locked = !ath_mutex_lock (&primepool_lock); for(i = 0; i < m; i++) { if (pool[i]) { for (j=0; j < n; j++) if (pool_in_use[j] == i) break; if (j == n && is_locked) { /* This pooled subprime has not been used. */ save_pool_prime (pool[i], poolrandomlevel); } else mpi_free (pool[i]); } } if (is_locked && ath_mutex_unlock (&primepool_lock)) err = GPG_ERR_INTERNAL; is_locked = 0; xfree (pool); } xfree (pool_in_use); if (factors) xfree (factors); /* Factors are shallow copies. */ if (perms) xfree (perms); mpi_free (val_2); mpi_free (q); mpi_free (q_factor); if (! err) { *prime_generated = prime; if (ret_factors) *ret_factors = factors_new; } else { if (factors_new) { for (i = 0; factors_new[i]; i++) mpi_free (factors_new[i]); xfree (factors_new); } mpi_free (prime); } return err; } /* Generate a prime used for discrete logarithm algorithms; i.e. this prime will be public and no strong random is required. On success R_PRIME receives a new MPI with the prime. On error R_PRIME is set to NULL and an error code is returned. If RET_FACTORS is not NULL it is set to an allocated array of factors on success or to NULL on error. */ gcry_err_code_t _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits, gcry_mpi_t g, gcry_mpi_t *r_prime, gcry_mpi_t **ret_factors) { *r_prime = NULL; if (ret_factors) *ret_factors = NULL; return prime_generate_internal ((mode == 1), r_prime, pbits, qbits, g, ret_factors, GCRY_WEAK_RANDOM, 0, 0, NULL, NULL); } static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, int (*extra_check)(void *, gcry_mpi_t), void *extra_check_arg) { gcry_mpi_t prime, ptest, pminus1, val_2, val_3, result; int i; unsigned int x, step; unsigned int count1, count2; int *mods; /* if ( DBG_CIPHER ) */ /* log_debug ("generate a prime of %u bits ", nbits ); */ if (nbits < 16) log_fatal ("can't generate a prime with less than %d bits\n", 16); mods = xmalloc (no_of_small_prime_numbers * sizeof *mods); /* Make nbits fit into gcry_mpi_t implementation. */ val_2 = mpi_alloc_set_ui( 2 ); val_3 = mpi_alloc_set_ui( 3); prime = secret? mpi_snew (nbits): mpi_new (nbits); result = mpi_alloc_like( prime ); pminus1= mpi_alloc_like( prime ); ptest = mpi_alloc_like( prime ); count1 = count2 = 0; for (;;) { /* try forvever */ int dotcount=0; /* generate a random number */ _gcry_mpi_randomize( prime, nbits, randomlevel ); /* Set high order bit to 1, set low order bit to 1. If we are generating a secret prime we are most probably doing that for RSA, to make sure that the modulus does have the requested key size we set the 2 high order bits. */ mpi_set_highbit (prime, nbits-1); if (secret) mpi_set_bit (prime, nbits-2); mpi_set_bit(prime, 0); /* Calculate all remainders. */ for (i=0; (x = small_prime_numbers[i]); i++ ) mods[i] = mpi_fdiv_r_ui(NULL, prime, x); /* Now try some primes starting with prime. */ for(step=0; step < 20000; step += 2 ) { /* Check against all the small primes we have in mods. */ count1++; for (i=0; (x = small_prime_numbers[i]); i++ ) { while ( mods[i] + step >= x ) mods[i] -= x; if ( !(mods[i] + step) ) break; } if ( x ) continue; /* Found a multiple of an already known prime. */ mpi_add_ui( ptest, prime, step ); /* Do a fast Fermat test now. */ count2++; mpi_sub_ui( pminus1, ptest, 1); mpi_powm( result, val_2, pminus1, ptest ); if ( !mpi_cmp_ui( result, 1 ) ) { /* Not composite, perform stronger tests */ if (is_prime(ptest, 5, &count2 )) { if (!mpi_test_bit( ptest, nbits-1-secret )) { progress('\n'); log_debug ("overflow in prime generation\n"); break; /* Stop loop, continue with a new prime. */ } if (extra_check && extra_check (extra_check_arg, ptest)) { /* The extra check told us that this prime is not of the caller's taste. */ progress ('/'); } else { /* Got it. */ mpi_free(val_2); mpi_free(val_3); mpi_free(result); mpi_free(pminus1); mpi_free(prime); xfree(mods); return ptest; } } } if (++dotcount == 10 ) { progress('.'); dotcount = 0; } } progress(':'); /* restart with a new random value */ } } /**************** * Returns: true if this may be a prime * RM_ROUNDS gives the number of Rabin-Miller tests to run. */ static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds, gcry_prime_check_func_t cb_func, void *cb_arg) { int i; unsigned int x; unsigned int count=0; /* Check against small primes. */ for (i=0; (x = small_prime_numbers[i]); i++ ) { if ( mpi_divisible_ui( prime, x ) ) return !mpi_cmp_ui (prime, x); } /* A quick Fermat test. */ { gcry_mpi_t result = mpi_alloc_like( prime ); gcry_mpi_t pminus1 = mpi_alloc_like( prime ); mpi_sub_ui( pminus1, prime, 1); mpi_powm( result, val_2, pminus1, prime ); mpi_free( pminus1 ); if ( mpi_cmp_ui( result, 1 ) ) { /* Is composite. */ mpi_free( result ); progress('.'); return 0; } mpi_free( result ); } if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime)) { /* Perform stronger tests. */ if ( is_prime( prime, rm_rounds, &count ) ) { if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime)) return 1; /* Probably a prime. */ } } progress('.'); return 0; } /* * Return true if n is probably a prime */ static int is_prime (gcry_mpi_t n, int steps, unsigned int *count) { gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t z = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t nminus1 = mpi_alloc( mpi_get_nlimbs( n ) ); gcry_mpi_t a2 = mpi_alloc_set_ui( 2 ); gcry_mpi_t q; unsigned i, j, k; int rc = 0; unsigned nbits = mpi_get_nbits( n ); if (steps < 5) /* Make sure that we do at least 5 rounds. */ steps = 5; mpi_sub_ui( nminus1, n, 1 ); /* Find q and k, so that n = 1 + 2^k * q . */ q = mpi_copy ( nminus1 ); k = mpi_trailing_zeros ( q ); mpi_tdiv_q_2exp (q, q, k); for (i=0 ; i < steps; i++ ) { ++*count; if( !i ) { mpi_set_ui( x, 2 ); } else { _gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM ); /* Make sure that the number is smaller than the prime and keep the randomness of the high bit. */ if ( mpi_test_bit ( x, nbits-2) ) { mpi_set_highbit ( x, nbits-2); /* Clear all higher bits. */ } else { mpi_set_highbit( x, nbits-2 ); mpi_clear_bit( x, nbits-2 ); } gcry_assert (mpi_cmp (x, nminus1) < 0 && mpi_cmp_ui (x, 1) > 0); } mpi_powm ( y, x, q, n); if ( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) { for ( j=1; j < k && mpi_cmp( y, nminus1 ); j++ ) { mpi_powm(y, y, a2, n); if( !mpi_cmp_ui( y, 1 ) ) goto leave; /* Not a prime. */ } if (mpi_cmp( y, nminus1 ) ) goto leave; /* Not a prime. */ } progress('+'); } rc = 1; /* May be a prime. */ leave: mpi_free( x ); mpi_free( y ); mpi_free( z ); mpi_free( nminus1 ); mpi_free( q ); mpi_free( a2 ); return rc; } /* Given ARRAY of size N with M elements set to true produce a modified array with the next permutation of M elements. Note, that ARRAY is used in a one-bit-per-byte approach. To detected the last permutation it is useful to initialize the array with the first M element set to true and use this test: m_out_of_n (array, m, n); for (i = j = 0; i < n && j < m; i++) if (array[i]) j++; if (j == m) goto ready; This code is based on the algorithm 452 from the "Collected Algorithms From ACM, Volume II" by C. N. Liu and D. T. Tang. */ static void m_out_of_n ( char *array, int m, int n ) { int i=0, i1=0, j=0, jp=0, j1=0, k1=0, k2=0; if( !m || m >= n ) return; /* Need to handle this simple case separately. */ if( m == 1 ) { for (i=0; i < n; i++ ) { if ( array[i] ) { array[i++] = 0; if( i >= n ) i = 0; array[i] = 1; return; } } BUG(); } for (j=1; j < n; j++ ) { if ( array[n-1] == array[n-j-1]) continue; j1 = j; break; } if ( (m & 1) ) { /* M is odd. */ if( array[n-1] ) { if( j1 & 1 ) { k1 = n - j1; k2 = k1+2; if( k2 > n ) k2 = n; goto leave; } goto scan; } k2 = n - j1 - 1; if( k2 == 0 ) { k1 = i; k2 = n - j1; } else if( array[k2] && array[k2-1] ) k1 = n; else k1 = k2 + 1; } else { /* M is even. */ if( !array[n-1] ) { k1 = n - j1; k2 = k1 + 1; goto leave; } if( !(j1 & 1) ) { k1 = n - j1; k2 = k1+2; if( k2 > n ) k2 = n; goto leave; } scan: jp = n - j1 - 1; for (i=1; i <= jp; i++ ) { i1 = jp + 2 - i; if( array[i1-1] ) { if( array[i1-2] ) { k1 = i1 - 1; k2 = n - j1; } else { k1 = i1 - 1; k2 = n + 1 - j1; } goto leave; } } k1 = 1; k2 = n + 1 - m; } leave: /* Now complement the two selected bits. */ array[k1-1] = !array[k1-1]; array[k2-1] = !array[k2-1]; } /* Generate a new prime number of PRIME_BITS bits and store it in PRIME. If FACTOR_BITS is non-zero, one of the prime factors of (prime - 1) / 2 must be FACTOR_BITS bits long. If FACTORS is non-zero, allocate a new, NULL-terminated array holding the prime factors and store it in FACTORS. FLAGS might be used to influence the prime number generation process. */ gcry_err_code_t _gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits, unsigned int factor_bits, gcry_mpi_t **factors, gcry_prime_check_func_t cb_func, void *cb_arg, gcry_random_level_t random_level, unsigned int flags) { gcry_err_code_t rc = 0; gcry_mpi_t *factors_generated = NULL; gcry_mpi_t prime_generated = NULL; unsigned int mode = 0; if (!prime) return GPG_ERR_INV_ARG; *prime = NULL; if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR) mode = 1; /* Generate. */ rc = prime_generate_internal ((mode==1), &prime_generated, prime_bits, factor_bits, NULL, factors? &factors_generated : NULL, random_level, flags, 1, cb_func, cb_arg); if (!rc && cb_func) { /* Additional check. */ if ( !cb_func (cb_arg, GCRY_PRIME_CHECK_AT_FINISH, prime_generated)) { /* Failed, deallocate resources. */ unsigned int i; mpi_free (prime_generated); if (factors) { for (i = 0; factors_generated[i]; i++) mpi_free (factors_generated[i]); xfree (factors_generated); } rc = GPG_ERR_GENERAL; } } if (!rc) { if (factors) *factors = factors_generated; *prime = prime_generated; } return rc; } /* Check whether the number X is prime. */ gcry_err_code_t _gcry_prime_check (gcry_mpi_t x, unsigned int flags) { (void)flags; switch (mpi_cmp_ui (x, 2)) { case 0: return 0; /* 2 is a prime */ case -1: return GPG_ERR_NO_PRIME; /* Only numbers > 1 are primes. */ } /* We use 64 rounds because the prime we are going to test is not guaranteed to be a random one. */ if (check_prime (x, mpi_const (MPI_C_TWO), 64, NULL, NULL)) return 0; return GPG_ERR_NO_PRIME; } /* Find a generator for PRIME where the factorization of (prime-1) is in the NULL terminated array FACTORS. Return the generator as a newly allocated MPI in R_G. If START_G is not NULL, use this as s atart for the search. Returns 0 on success.*/ gcry_err_code_t _gcry_prime_group_generator (gcry_mpi_t *r_g, gcry_mpi_t prime, gcry_mpi_t *factors, gcry_mpi_t start_g) { gcry_mpi_t tmp = mpi_new (0); gcry_mpi_t b = mpi_new (0); gcry_mpi_t pmin1 = mpi_new (0); gcry_mpi_t g = start_g? mpi_copy (start_g) : mpi_set_ui (NULL, 3); int first = 1; int i, n; if (!factors || !r_g || !prime) return GPG_ERR_INV_ARG; *r_g = NULL; for (n=0; factors[n]; n++) ; if (n < 2) return GPG_ERR_INV_ARG; /* Extra sanity check - usually disabled. */ /* mpi_set (tmp, factors[0]); */ /* for(i = 1; i < n; i++) */ /* mpi_mul (tmp, tmp, factors[i]); */ /* mpi_add_ui (tmp, tmp, 1); */ /* if (mpi_cmp (prime, tmp)) */ /* return gpg_error (GPG_ERR_INV_ARG); */ mpi_sub_ui (pmin1, prime, 1); do { if (first) first = 0; else mpi_add_ui (g, g, 1); if (DBG_CIPHER) log_printmpi ("checking g", g); else progress('^'); for (i = 0; i < n; i++) { mpi_fdiv_q (tmp, pmin1, factors[i]); mpi_powm (b, g, tmp, prime); if (! mpi_cmp_ui (b, 1)) break; } if (DBG_CIPHER) progress('\n'); } while (i < n); _gcry_mpi_release (tmp); _gcry_mpi_release (b); _gcry_mpi_release (pmin1); *r_g = g; return 0; } /* Convenience function to release the factors array. */ void _gcry_prime_release_factors (gcry_mpi_t *factors) { if (factors) { int i; for (i=0; factors[i]; i++) mpi_free (factors[i]); xfree (factors); } } /* Helper for _gcry_derive_x931_prime. */ static gcry_mpi_t find_x931_prime (const gcry_mpi_t pfirst) { gcry_mpi_t val_2 = mpi_alloc_set_ui (2); gcry_mpi_t prime; prime = mpi_copy (pfirst); /* If P is even add 1. */ mpi_set_bit (prime, 0); /* We use 64 Rabin-Miller rounds which is better and thus sufficient. We do not have a Lucas test implementaion thus we can't do it in the X9.31 preferred way of running a few Rabin-Miller followed by one Lucas test. */ while ( !check_prime (prime, val_2, 64, NULL, NULL) ) mpi_add_ui (prime, prime, 2); mpi_free (val_2); return prime; } /* Generate a prime using the algorithm from X9.31 appendix B.4. This function requires that the provided public exponent E is odd. XP, XP1 and XP2 are the seed values. All values are mandatory. On success the prime is returned. If R_P1 or R_P2 are given the internal values P1 and P2 are saved at these addresses. On error NULL is returned. */ gcry_mpi_t _gcry_derive_x931_prime (const gcry_mpi_t xp, const gcry_mpi_t xp1, const gcry_mpi_t xp2, const gcry_mpi_t e, gcry_mpi_t *r_p1, gcry_mpi_t *r_p2) { gcry_mpi_t p1, p2, p1p2, yp0; if (!xp || !xp1 || !xp2) return NULL; if (!e || !mpi_test_bit (e, 0)) return NULL; /* We support only odd values for E. */ p1 = find_x931_prime (xp1); p2 = find_x931_prime (xp2); p1p2 = mpi_alloc_like (xp); mpi_mul (p1p2, p1, p2); { gcry_mpi_t r1, tmp; /* r1 = (p2^{-1} mod p1)p2 - (p1^{-1} mod p2) */ tmp = mpi_alloc_like (p1); mpi_invm (tmp, p2, p1); mpi_mul (tmp, tmp, p2); r1 = tmp; tmp = mpi_alloc_like (p2); mpi_invm (tmp, p1, p2); mpi_mul (tmp, tmp, p1); mpi_sub (r1, r1, tmp); /* Fixup a negative value. */ if (mpi_has_sign (r1)) mpi_add (r1, r1, p1p2); /* yp0 = xp + (r1 - xp mod p1*p2) */ yp0 = tmp; tmp = NULL; mpi_subm (yp0, r1, xp, p1p2); mpi_add (yp0, yp0, xp); mpi_free (r1); /* Fixup a negative value. */ if (mpi_cmp (yp0, xp) < 0 ) mpi_add (yp0, yp0, p1p2); } /* yp0 is now the first integer greater than xp with p1 being a large prime factor of yp0-1 and p2 a large prime factor of yp0+1. */ /* Note that the first example from X9.31 (D.1.1) which uses (Xq1 #1A5CF72EE770DE50CB09ACCEA9#) (Xq2 #134E4CAA16D2350A21D775C404#) (Xq #CC1092495D867E64065DEE3E7955F2EBC7D47A2D 7C9953388F97DDDC3E1CA19C35CA659EDC2FC325 6D29C2627479C086A699A49C4C9CEE7EF7BD1B34 321DE34A#)))) returns an yp0 of #CC1092495D867E64065DEE3E7955F2EBC7D47A2D 7C9953388F97DDDC3E1CA19C35CA659EDC2FC4E3 BF20CB896EE37E098A906313271422162CB6C642 75C1201F# and not #CC1092495D867E64065DEE3E7955F2EBC7D47A2D 7C9953388F97DDDC3E1CA19C35CA659EDC2FC2E6 C88FE299D52D78BE405A97E01FD71DD7819ECB91 FA85A076# as stated in the standard. This seems to be a bug in X9.31. */ { gcry_mpi_t val_2 = mpi_alloc_set_ui (2); gcry_mpi_t gcdtmp = mpi_alloc_like (yp0); int gcdres; mpi_sub_ui (p1p2, p1p2, 1); /* Adjust for loop body. */ mpi_sub_ui (yp0, yp0, 1); /* Ditto. */ for (;;) { gcdres = mpi_gcd (gcdtmp, e, yp0); mpi_add_ui (yp0, yp0, 1); if (!gcdres) progress ('/'); /* gcd (e, yp0-1) != 1 */ else if (check_prime (yp0, val_2, 64, NULL, NULL)) break; /* Found. */ /* We add p1p2-1 because yp0 is incremented after the gcd test. */ mpi_add (yp0, yp0, p1p2); } mpi_free (gcdtmp); mpi_free (val_2); } mpi_free (p1p2); progress('\n'); if (r_p1) *r_p1 = p1; else mpi_free (p1); if (r_p2) *r_p2 = p2; else mpi_free (p2); return yp0; } /* Generate the two prime used for DSA using the algorithm specified in FIPS 186-2. PBITS is the desired length of the prime P and a QBITS the length of the prime Q. If SEED is not supplied and SEEDLEN is 0 the function generates an appropriate SEED. On success the generated primes are stored at R_Q and R_P, the counter value is stored at R_COUNTER and the seed actually used for generation is stored at R_SEED and R_SEEDVALUE. */ gpg_err_code_t _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits, const void *seed, size_t seedlen, gcry_mpi_t *r_q, gcry_mpi_t *r_p, int *r_counter, void **r_seed, size_t *r_seedlen) { gpg_err_code_t ec; unsigned char seed_help_buffer[160/8]; /* Used to hold a generated SEED. */ unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */ unsigned char digest[160/8]; /* Helper buffer for SHA-1 digest. */ gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */ gcry_mpi_t tmpval = NULL; /* Helper variable. */ int i; unsigned char value_u[160/8]; int value_n, value_b, value_k; int counter; gcry_mpi_t value_w = NULL; gcry_mpi_t value_x = NULL; gcry_mpi_t prime_q = NULL; gcry_mpi_t prime_p = NULL; /* FIPS 186-2 allows only for 1024/160 bit. */ if (pbits != 1024 || qbits != 160) return GPG_ERR_INV_KEYLEN; if (!seed && !seedlen) ; /* No seed value given: We are asked to generate it. */ else if (!seed || seedlen < qbits/8) return GPG_ERR_INV_ARG; /* Allocate a buffer to later compute SEED+some_increment. */ seed_plus = xtrymalloc (seedlen < 20? 20:seedlen); if (!seed_plus) { ec = gpg_err_code_from_syserror (); goto leave; } val_2 = mpi_alloc_set_ui (2); value_n = (pbits - 1) / qbits; value_b = (pbits - 1) - value_n * qbits; value_w = mpi_new (pbits); value_x = mpi_new (pbits); restart: /* Generate Q. */ for (;;) { /* Step 1: Generate a (new) seed unless one has been supplied. */ if (!seed) { seedlen = sizeof seed_help_buffer; _gcry_create_nonce (seed_help_buffer, seedlen); seed = seed_help_buffer; } /* Step 2: U = sha1(seed) ^ sha1((seed+1) mod 2^{qbits}) */ memcpy (seed_plus, seed, seedlen); for (i=seedlen-1; i >= 0; i--) { seed_plus[i]++; if (seed_plus[i]) break; } _gcry_md_hash_buffer (GCRY_MD_SHA1, value_u, seed, seedlen); _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); for (i=0; i < sizeof value_u; i++) value_u[i] ^= digest[i]; /* Step 3: Form q from U */ _gcry_mpi_release (prime_q); prime_q = NULL; ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, value_u, sizeof value_u, NULL); if (ec) goto leave; mpi_set_highbit (prime_q, qbits-1 ); mpi_set_bit (prime_q, 0); /* Step 4: Test whether Q is prime using 64 round of Rabin-Miller. */ if (check_prime (prime_q, val_2, 64, NULL, NULL)) break; /* Yes, Q is prime. */ /* Step 5. */ seed = NULL; /* Force a new seed at Step 1. */ } /* Step 6. Note that we do no use an explicit offset but increment SEED_PLUS accordingly. SEED_PLUS is currently SEED+1. */ counter = 0; /* Generate P. */ prime_p = mpi_new (pbits); for (;;) { /* Step 7: For k = 0,...n let V_k = sha1(seed+offset+k) mod 2^{qbits} Step 8: W = V_0 + V_1*2^160 + ... + V_{n-1}*2^{(n-1)*160} + (V_{n} mod 2^b)*2^{n*160} */ mpi_set_ui (value_w, 0); for (value_k=0; value_k <= value_n; value_k++) { /* There is no need to have an explicit offset variable: In the first round we shall have an offset of 2, this is achieved by using SEED_PLUS which is already at SEED+1, thus we just need to increment it once again. The requirement for the next round is to update offset by N, which we implictly did at the end of this loop, and then to add one; this one is the same as in the first round. */ for (i=seedlen-1; i >= 0; i--) { seed_plus[i]++; if (seed_plus[i]) break; } _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); _gcry_mpi_release (tmpval); tmpval = NULL; ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG, digest, sizeof digest, NULL); if (ec) goto leave; if (value_k == value_n) mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */ mpi_lshift (tmpval, tmpval, value_k*qbits); mpi_add (value_w, value_w, tmpval); } /* Step 8 continued: X = W + 2^{L-1} */ mpi_set_ui (value_x, 0); mpi_set_highbit (value_x, pbits-1); mpi_add (value_x, value_x, value_w); /* Step 9: c = X mod 2q, p = X - (c - 1) */ mpi_mul_2exp (tmpval, prime_q, 1); mpi_mod (tmpval, value_x, tmpval); mpi_sub_ui (tmpval, tmpval, 1); mpi_sub (prime_p, value_x, tmpval); /* Step 10: If p < 2^{L-1} skip the primality test. */ /* Step 11 and 12: Primality test. */ if (mpi_get_nbits (prime_p) >= pbits-1 && check_prime (prime_p, val_2, 64, NULL, NULL) ) break; /* Yes, P is prime, continue with Step 15. */ /* Step 13: counter = counter + 1, offset = offset + n + 1. */ counter++; /* Step 14: If counter >= 2^12 goto Step 1. */ if (counter >= 4096) goto restart; } /* Step 15: Save p, q, counter and seed. */ /* log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */ /* mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */ /* log_printhex("fips186-2 seed:", seed, seedlen); */ /* log_mpidump ("fips186-2 prime p", prime_p); */ /* log_mpidump ("fips186-2 prime q", prime_q); */ if (r_q) { *r_q = prime_q; prime_q = NULL; } if (r_p) { *r_p = prime_p; prime_p = NULL; } if (r_counter) *r_counter = counter; if (r_seed && r_seedlen) { memcpy (seed_plus, seed, seedlen); *r_seed = seed_plus; seed_plus = NULL; *r_seedlen = seedlen; } leave: _gcry_mpi_release (tmpval); _gcry_mpi_release (value_x); _gcry_mpi_release (value_w); _gcry_mpi_release (prime_p); _gcry_mpi_release (prime_q); xfree (seed_plus); _gcry_mpi_release (val_2); return ec; } /* WARNING: The code below has not yet been tested! However, it is not yet used. We need to wait for FIPS 186-3 final and for test vectors. Generate the two prime used for DSA using the algorithm specified in FIPS 186-3, A.1.1.2. PBITS is the desired length of the prime P and a QBITS the length of the prime Q. If SEED is not supplied and SEEDLEN is 0 the function generates an appropriate SEED. On success the generated primes are stored at R_Q and R_P, the counter value is stored at R_COUNTER and the seed actually used for generation is stored at R_SEED and R_SEEDVALUE. The hash algorithm used is stored at R_HASHALGO. Note that this function is very similar to the fips186_2 code. Due to the minor differences, other buffer sizes and for documentarion, we use a separate function. */ gpg_err_code_t _gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits, const void *seed, size_t seedlen, gcry_mpi_t *r_q, gcry_mpi_t *r_p, int *r_counter, void **r_seed, size_t *r_seedlen, int *r_hashalgo) { gpg_err_code_t ec; unsigned char seed_help_buffer[256/8]; /* Used to hold a generated SEED. */ unsigned char *seed_plus; /* Malloced buffer to hold SEED+x. */ unsigned char digest[256/8]; /* Helper buffer for SHA-1 digest. */ gcry_mpi_t val_2 = NULL; /* Helper for the prime test. */ gcry_mpi_t tmpval = NULL; /* Helper variable. */ int hashalgo; /* The id of the Approved Hash Function. */ int i; unsigned char value_u[256/8]; int value_n, value_b, value_j; int counter; gcry_mpi_t value_w = NULL; gcry_mpi_t value_x = NULL; gcry_mpi_t prime_q = NULL; gcry_mpi_t prime_p = NULL; gcry_assert (sizeof seed_help_buffer == sizeof digest && sizeof seed_help_buffer == sizeof value_u); /* Step 1: Check the requested prime lengths. */ /* Note that due to the size of our buffers QBITS is limited to 256. */ if (pbits == 1024 && qbits == 160) hashalgo = GCRY_MD_SHA1; else if (pbits == 2048 && qbits == 224) hashalgo = GCRY_MD_SHA224; else if (pbits == 2048 && qbits == 256) hashalgo = GCRY_MD_SHA256; else if (pbits == 3072 && qbits == 256) hashalgo = GCRY_MD_SHA256; else return GPG_ERR_INV_KEYLEN; /* Also check that the hash algorithm is available. */ ec = _gcry_md_test_algo (hashalgo); if (ec) return ec; gcry_assert (qbits/8 <= sizeof digest); gcry_assert (_gcry_md_get_algo_dlen (hashalgo) == qbits/8); /* Step 2: Check seedlen. */ if (!seed && !seedlen) ; /* No seed value given: We are asked to generate it. */ else if (!seed || seedlen < qbits/8) return GPG_ERR_INV_ARG; /* Allocate a buffer to later compute SEED+some_increment and a few helper variables. */ seed_plus = xtrymalloc (seedlen < sizeof seed_help_buffer? sizeof seed_help_buffer : seedlen); if (!seed_plus) { ec = gpg_err_code_from_syserror (); goto leave; } val_2 = mpi_alloc_set_ui (2); value_w = mpi_new (pbits); value_x = mpi_new (pbits); /* Step 3: n = \lceil L / outlen \rceil - 1 */ value_n = (pbits + qbits - 1) / qbits - 1; /* Step 4: b = L - 1 - (n * outlen) */ value_b = pbits - 1 - (value_n * qbits); restart: /* Generate Q. */ for (;;) { /* Step 5: Generate a (new) seed unless one has been supplied. */ if (!seed) { seedlen = qbits/8; gcry_assert (seedlen <= sizeof seed_help_buffer); _gcry_create_nonce (seed_help_buffer, seedlen); seed = seed_help_buffer; } /* Step 6: U = hash(seed) */ _gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen); /* Step 7: q = 2^{N-1} + U + 1 - (U mod 2) */ if ( !(value_u[qbits/8-1] & 0x01) ) { for (i=qbits/8-1; i >= 0; i--) { value_u[i]++; if (value_u[i]) break; } } _gcry_mpi_release (prime_q); prime_q = NULL; ec = _gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, value_u, sizeof value_u, NULL); if (ec) goto leave; mpi_set_highbit (prime_q, qbits-1 ); /* Step 8: Test whether Q is prime using 64 round of Rabin-Miller. According to table C.1 this is sufficient for all supported prime sizes (i.e. up 3072/256). */ if (check_prime (prime_q, val_2, 64, NULL, NULL)) break; /* Yes, Q is prime. */ /* Step 8. */ seed = NULL; /* Force a new seed at Step 5. */ } /* Step 11. Note that we do no use an explicit offset but increment SEED_PLUS accordingly. */ memcpy (seed_plus, seed, seedlen); counter = 0; /* Generate P. */ prime_p = mpi_new (pbits); for (;;) { /* Step 11.1: For j = 0,...n let V_j = hash(seed+offset+j) Step 11.2: W = V_0 + V_1*2^outlen + ... + V_{n-1}*2^{(n-1)*outlen} + (V_{n} mod 2^b)*2^{n*outlen} */ mpi_set_ui (value_w, 0); for (value_j=0; value_j <= value_n; value_j++) { /* There is no need to have an explicit offset variable: In the first round we shall have an offset of 1 and a j of 0. This is achieved by incrementing SEED_PLUS here. For the next round offset is implicitly updated by using SEED_PLUS again. */ for (i=seedlen-1; i >= 0; i--) { seed_plus[i]++; if (seed_plus[i]) break; } _gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen); _gcry_mpi_release (tmpval); tmpval = NULL; ec = _gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG, digest, sizeof digest, NULL); if (ec) goto leave; if (value_j == value_n) mpi_clear_highbit (tmpval, value_b); /* (V_n mod 2^b) */ mpi_lshift (tmpval, tmpval, value_j*qbits); mpi_add (value_w, value_w, tmpval); } /* Step 11.3: X = W + 2^{L-1} */ mpi_set_ui (value_x, 0); mpi_set_highbit (value_x, pbits-1); mpi_add (value_x, value_x, value_w); /* Step 11.4: c = X mod 2q */ mpi_mul_2exp (tmpval, prime_q, 1); mpi_mod (tmpval, value_x, tmpval); /* Step 11.5: p = X - (c - 1) */ mpi_sub_ui (tmpval, tmpval, 1); mpi_sub (prime_p, value_x, tmpval); /* Step 11.6: If p < 2^{L-1} skip the primality test. */ /* Step 11.7 and 11.8: Primality test. */ if (mpi_get_nbits (prime_p) >= pbits-1 && check_prime (prime_p, val_2, 64, NULL, NULL) ) break; /* Yes, P is prime, continue with Step 15. */ /* Step 11.9: counter = counter + 1, offset = offset + n + 1. If counter >= 4L goto Step 5. */ counter++; if (counter >= 4*pbits) goto restart; } /* Step 12: Save p, q, counter and seed. */ log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n", mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); log_printhex ("fips186-3 seed", seed, seedlen); log_printmpi ("fips186-3 p", prime_p); log_printmpi ("fips186-3 q", prime_q); if (r_q) { *r_q = prime_q; prime_q = NULL; } if (r_p) { *r_p = prime_p; prime_p = NULL; } if (r_counter) *r_counter = counter; if (r_seed && r_seedlen) { memcpy (seed_plus, seed, seedlen); *r_seed = seed_plus; seed_plus = NULL; *r_seedlen = seedlen; } if (r_hashalgo) *r_hashalgo = hashalgo; leave: _gcry_mpi_release (tmpval); _gcry_mpi_release (value_x); _gcry_mpi_release (value_w); _gcry_mpi_release (prime_p); _gcry_mpi_release (prime_q); xfree (seed_plus); _gcry_mpi_release (val_2); return ec; }