2 This file is part of GNUnet.
3 Copyright (C) 1994, 1996, 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
4 Copyright (C) 2004, 2005, 2006 Christian Grothoff (and other contributing authors)
6 GNUnet is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published
8 by the Free Software Foundation; either version 2, or (at your
9 option) any later version.
11 GNUnet is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNUnet; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.
21 Note: This code is based on code from libgcrypt
22 The code was adapted for GNUnet to support RSA-key generation
23 based on weak, pseudo-random keys. Do NOT use to generate
29 * @file util/crypto_ksk.c
30 * @brief implementation of RSA-Key generation for KBlocks
31 * (do NOT use for pseudonyms or hostkeys!)
32 * @author Christian Grothoff
36 #include "gnunet_common.h"
37 #include "gnunet_crypto_lib.h"
38 #include "gnunet_os_lib.h"
43 * Log an error message at log-level 'level' that indicates
44 * a failure of the command 'cmd' with the message given
45 * by gcry_strerror(rc).
47 #define LOG_GCRY(level, cmd, rc) do { GNUNET_log(level, _("`%s' failed at %s:%d with error: %s\n"), cmd, __FILE__, __LINE__, gcry_strerror(rc)); } while(0);
52 mpz_t n; /* public modulus */
53 mpz_t e; /* public exponent */
54 mpz_t d; /* exponent */
55 mpz_t p; /* prime p. */
56 mpz_t q; /* prime q. */
57 mpz_t u; /* inverse of p mod q. */
61 * The private information of an RSA key pair.
62 * NOTE: this must match the definition in crypto_rsa.c
64 struct GNUNET_CRYPTO_RsaPrivateKey
73 return mpz_sizeinbase (a, 2);
78 mpz_randomize (mpz_t n, unsigned int nbits, GNUNET_HashCode * rnd)
81 int bits_per_hc = sizeof (GNUNET_HashCode) * 8;
85 GNUNET_assert (nbits > 0);
86 cnt = (nbits + bits_per_hc - 1) / bits_per_hc;
87 tmp = GNUNET_malloc (sizeof (GNUNET_HashCode) * cnt);
90 for (i = 0; i < cnt - 1; i++)
92 GNUNET_CRYPTO_hash (&tmp[i], sizeof (GNUNET_HashCode), &tmp[i + 1]);
94 GNUNET_CRYPTO_hash (&tmp[i], sizeof (GNUNET_HashCode), rnd);
95 mpz_import (n, cnt * sizeof (GNUNET_HashCode) / sizeof (unsigned int),
96 1, sizeof (unsigned int), 1, 0, tmp);
104 * Return true if n is probably a prime
107 is_prime (mpz_t n, int steps, GNUNET_HashCode * hc)
115 unsigned int i, j, k;
123 mpz_init_set_ui (a2, 2);
124 nbits = get_nbits (n);
125 mpz_sub_ui (nminus1, n, 1);
127 /* Find q and k, so that n = 1 + 2^k * q . */
128 mpz_init_set (q, nminus1);
129 k = mpz_scan1 (q, 0);
130 mpz_tdiv_q_2exp (q, q, k);
132 for (i = 0; i < steps; i++)
140 mpz_randomize (x, nbits - 1, hc);
141 GNUNET_assert (mpz_cmp (x, nminus1) < 0 && mpz_cmp_ui (x, 1) > 0);
143 mpz_powm (y, x, q, n);
144 if (mpz_cmp_ui (y, 1) && mpz_cmp (y, nminus1))
146 for (j = 1; j < k && mpz_cmp (y, nminus1); j++)
148 mpz_powm (y, y, a2, n);
149 if (!mpz_cmp_ui (y, 1))
150 goto leave; /* Not a prime. */
152 if (mpz_cmp (y, nminus1))
153 goto leave; /* Not a prime. */
156 rc = 1; /* May be a prime. */
170 gen_prime (mpz_t ptest, unsigned int nbits, GNUNET_HashCode * hc)
172 /* Note: 2 is not included because it can be tested more easily by
173 looking at bit 0. The last entry in this list is marked by a zero */
174 static const uint16_t small_prime_numbers[] = {
175 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
176 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
177 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
178 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
179 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
180 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
181 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
182 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
183 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
184 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
185 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
186 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
187 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
188 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
189 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
190 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
191 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
192 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
193 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
194 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
195 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
196 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
197 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
198 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
199 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
200 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
201 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
202 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
203 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
204 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
205 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
206 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
207 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
208 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
209 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
210 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
211 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
212 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
213 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
214 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
215 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
216 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
217 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
218 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
219 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
220 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
221 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
222 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
223 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
224 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
225 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
226 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
227 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
228 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
229 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
230 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
231 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
232 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
233 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
234 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
235 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
236 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
237 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
238 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
239 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
240 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
241 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
242 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
243 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
244 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
245 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
246 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
247 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
248 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
249 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
250 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
251 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
252 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
253 4957, 4967, 4969, 4973, 4987, 4993, 4999,
256 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
257 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
259 mpz_t prime, pminus1, val_2, val_3, result;
265 GNUNET_assert (nbits >= 16);
267 mods = GNUNET_malloc (no_of_small_prime_numbers * sizeof (*mods));
268 /* Make nbits fit into mpz_t implementation. */
269 mpz_init_set_ui (val_2, 2);
270 mpz_init_set_ui (val_3, 3);
277 /* generate a random number */
278 mpz_randomize (prime, nbits, hc);
279 /* Set high order bit to 1, set low order bit to 1. If we are
280 generating a secret prime we are most probably doing that
281 for RSA, to make sure that the modulus does have the
282 requested key size we set the 2 high order bits. */
283 mpz_setbit (prime, nbits - 1);
284 mpz_setbit (prime, nbits - 2);
285 mpz_setbit (prime, 0);
287 /* Calculate all remainders. */
289 for (i = 0; (x = small_prime_numbers[i]); i++)
290 mods[i] = mpz_fdiv_r_ui (tmp, prime, x);
292 /* Now try some primes starting with prime. */
293 for (step = 0; step < 20000; step += 2)
295 /* Check against all the small primes we have in mods. */
296 for (i = 0; (x = small_prime_numbers[i]); i++)
298 while (mods[i] + step >= x)
300 if (!(mods[i] + step))
304 continue; /* Found a multiple of an already known prime. */
306 mpz_add_ui (ptest, prime, step);
307 if (!mpz_tstbit (ptest, nbits - 2))
310 /* Do a fast Fermat test now. */
311 mpz_sub_ui (pminus1, ptest, 1);
312 mpz_powm (result, val_2, pminus1, ptest);
313 if ((!mpz_cmp_ui (result, 1)) && (is_prime (ptest, 5, hc)))
329 * Find the greatest common divisor G of A and B.
330 * Return: 1 if this 1, 0 in all other cases
333 test_gcd (mpz_t g, mpz_t xa, mpz_t xb)
337 mpz_init_set (a, xa);
338 mpz_init_set (b, xb);
340 /* TAOCP Vol II, 4.5.2, Algorithm A */
341 while (mpz_cmp_ui (b, 0))
343 mpz_fdiv_r (g, a, b); /* g used as temorary variable */
351 return (0 == mpz_cmp_ui (g, 1));
355 * Generate a key pair with a key of size NBITS.
356 * @param sk where to store the key
357 * @param nbits the number of bits to use
358 * @param hc the HC to use for PRNG (modified!)
361 generate_kblock_key (KBlock_secret_key * sk,
362 unsigned int nbits, GNUNET_HashCode * hc)
365 mpz_t phi; /* helper: (p-1)(q-1) */
369 /* make sure that nbits is even so that we generate p, q of equal size */
373 mpz_init_set_ui (sk->e, 257);
392 gen_prime (sk->p, nbits / 2, hc);
393 gen_prime (sk->q, nbits / 2, hc);
395 if (mpz_cmp (sk->p, sk->q) > 0) /* p shall be smaller than q (for calc of u) */
396 mpz_swap (sk->p, sk->q);
397 /* calculate the modulus */
398 mpz_mul (sk->n, sk->p, sk->q);
400 while (get_nbits (sk->n) != nbits);
402 /* calculate Euler totient: phi = (p-1)(q-1) */
403 mpz_sub_ui (t1, sk->p, 1);
404 mpz_sub_ui (t2, sk->q, 1);
405 mpz_mul (phi, t1, t2);
407 mpz_fdiv_q (f, phi, g);
409 while (0 == test_gcd (t1, sk->e, phi))
410 { /* (while gcd is not 1) */
411 mpz_add_ui (sk->e, sk->e, 2);
414 /* calculate the secret key d = e^1 mod phi */
416 while ((0 == mpz_invert (sk->d, sk->e, f)) ||
417 (0 == mpz_invert (sk->u, sk->p, sk->q)));
428 * Internal representation of the private key.
430 struct KskRsaPrivateKeyBinaryEncoded
433 * Total size of the structure, in bytes, in big-endian!
435 uint16_t len GNUNET_PACKED;
436 uint16_t sizen GNUNET_PACKED; /* in big-endian! */
437 uint16_t sizee GNUNET_PACKED; /* in big-endian! */
438 uint16_t sized GNUNET_PACKED; /* in big-endian! */
439 uint16_t sizep GNUNET_PACKED; /* in big-endian! */
440 uint16_t sizeq GNUNET_PACKED; /* in big-endian! */
441 uint16_t sizedmp1 GNUNET_PACKED; /* in big-endian! */
442 uint16_t sizedmq1 GNUNET_PACKED; /* in big-endian! */
443 /* followed by the actual values */
448 * Deterministically (!) create a hostkey using only the
449 * given HashCode as input to the PRNG.
451 static struct KskRsaPrivateKeyBinaryEncoded *
452 makeKblockKeyInternal (const GNUNET_HashCode * hc)
454 KBlock_secret_key sk;
459 struct KskRsaPrivateKeyBinaryEncoded *retval;
464 generate_kblock_key (&sk, 1024, /* at least 10x as fast than 2048 bits
465 -- we simply cannot afford 2048 bits
466 even on modern hardware, and especially
467 not since clearly a dictionary attack
468 will still be much cheaper
469 than breaking a 1024 bit RSA key.
470 If an adversary can spend the time to
471 break a 1024 bit RSA key just to forge
472 a signature -- SO BE IT. [ CG, 6/2005 ] */
480 size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
481 for (i = 0; i < 6; i++)
483 pbu[i] = mpz_export (NULL, &sizes[i], 1, /* most significant word first */
484 1, /* unit is bytes */
490 GNUNET_assert (size < 65536);
491 retval = GNUNET_malloc (size);
492 retval->len = htons (size);
494 retval->sizen = htons (sizes[0]);
495 memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
497 retval->sizee = htons (sizes[1]);
498 memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
500 retval->sized = htons (sizes[2]);
501 memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
504 retval->sizep = htons (sizes[4]);
505 memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
507 retval->sizeq = htons (sizes[3]);
508 memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
510 retval->sizedmp1 = htons (0);
511 retval->sizedmq1 = htons (0);
512 memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
513 for (i = 0; i < 6; i++)
523 * Decode the internal format into the format used
526 static struct GNUNET_CRYPTO_RsaPrivateKey *
527 ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
529 struct GNUNET_CRYPTO_RsaPrivateKey *ret;
531 gcry_mpi_t n, e, d, p, q, u;
537 size = ntohs (encoding->sizen);
538 rc = gcry_mpi_scan (&n,
540 &((const unsigned char *) (&encoding[1]))[pos],
542 pos += ntohs (encoding->sizen);
545 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
548 size = ntohs (encoding->sizee);
549 rc = gcry_mpi_scan (&e,
551 &((const unsigned char *) (&encoding[1]))[pos],
553 pos += ntohs (encoding->sizee);
556 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
557 gcry_mpi_release (n);
560 size = ntohs (encoding->sized);
561 rc = gcry_mpi_scan (&d,
563 &((const unsigned char *) (&encoding[1]))[pos],
565 pos += ntohs (encoding->sized);
568 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
569 gcry_mpi_release (n);
570 gcry_mpi_release (e);
574 size = ntohs (encoding->sizep);
577 rc = gcry_mpi_scan (&q,
579 &((const unsigned char *) (&encoding[1]))[pos],
581 pos += ntohs (encoding->sizep);
584 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
585 gcry_mpi_release (n);
586 gcry_mpi_release (e);
587 gcry_mpi_release (d);
593 size = ntohs (encoding->sizeq);
596 rc = gcry_mpi_scan (&p,
598 &((const unsigned char *) (&encoding[1]))[pos],
600 pos += ntohs (encoding->sizeq);
603 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
604 gcry_mpi_release (n);
605 gcry_mpi_release (e);
606 gcry_mpi_release (d);
608 gcry_mpi_release (q);
614 pos += ntohs (encoding->sizedmp1);
615 pos += ntohs (encoding->sizedmq1);
617 ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
621 rc = gcry_mpi_scan (&u,
623 &((const unsigned char *) (&encoding[1]))[pos],
627 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
628 gcry_mpi_release (n);
629 gcry_mpi_release (e);
630 gcry_mpi_release (d);
632 gcry_mpi_release (p);
634 gcry_mpi_release (q);
641 if ((p != NULL) && (q != NULL) && (u != NULL))
643 rc = gcry_sexp_build (&res, &size, /* erroff */
644 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
649 if ((p != NULL) && (q != NULL))
651 rc = gcry_sexp_build (&res, &size, /* erroff */
652 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
657 rc = gcry_sexp_build (&res, &size, /* erroff */
658 "(private-key(rsa(n %m)(e %m)(d %m)))",
662 gcry_mpi_release (n);
663 gcry_mpi_release (e);
664 gcry_mpi_release (d);
666 gcry_mpi_release (p);
668 gcry_mpi_release (q);
670 gcry_mpi_release (u);
673 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
675 if (gcry_pk_testkey (res))
677 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
681 ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
690 struct KskRsaPrivateKeyBinaryEncoded *pke;
691 } KBlockKeyCacheLine;
693 static KBlockKeyCacheLine **cache;
695 static unsigned int cacheSize;
698 * Deterministically (!) create a hostkey using only the
699 * given HashCode as input to the PRNG.
701 struct GNUNET_CRYPTO_RsaPrivateKey *
702 GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
704 struct GNUNET_CRYPTO_RsaPrivateKey *ret;
705 KBlockKeyCacheLine *line;
708 for (i = 0; i < cacheSize; i++)
710 if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
712 ret = ksk_decode_key (cache[i]->pke);
717 line = GNUNET_malloc (sizeof (KBlockKeyCacheLine));
719 line->pke = makeKblockKeyInternal (hc);
720 GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
721 cache[cacheSize - 1] = line;
722 return ksk_decode_key (line->pke);
726 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
730 for (i = 0; i < cacheSize; i++)
732 GNUNET_free (cache[i]->pke);
733 GNUNET_free (cache[i]);
735 GNUNET_array_grow (cache, cacheSize, 0);
739 /* end of crypto_ksk.c */