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"
42 * Log an error message at log-level 'level' that indicates
43 * a failure of the command 'cmd' with the message given
44 * by gcry_strerror(rc).
46 #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);
51 mpz_t n; /* public modulus */
52 mpz_t e; /* public exponent */
53 mpz_t d; /* exponent */
54 mpz_t p; /* prime p. */
55 mpz_t q; /* prime q. */
56 mpz_t u; /* inverse of p mod q. */
60 * The private information of an RSA key pair.
61 * NOTE: this must match the definition in crypto_rsa.c
63 struct GNUNET_CRYPTO_RsaPrivateKey
69 /* Note: 2 is not included because it can be tested more easily by
70 looking at bit 0. The last entry in this list is marked by a zero */
71 static uint16_t small_prime_numbers[] = {
72 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
73 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
74 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
75 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
76 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
77 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
78 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
79 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
80 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
81 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
82 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
83 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
84 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
85 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
86 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
87 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
88 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
89 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
90 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
91 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
92 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
93 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
94 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
95 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
96 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
97 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
98 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
99 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
100 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
101 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
102 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
103 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
104 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
105 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
106 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
107 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
108 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
109 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
110 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
111 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
112 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
113 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
114 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
115 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
116 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
117 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
118 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
119 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
120 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
121 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
122 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
123 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
124 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
125 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
126 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
127 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
128 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
129 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
130 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
131 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
132 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
133 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
134 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
135 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
136 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
137 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
138 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
139 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
140 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
141 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
142 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
143 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
144 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
145 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
146 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
147 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
148 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
149 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
150 4957, 4967, 4969, 4973, 4987, 4993, 4999,
154 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
155 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
161 return mpz_sizeinbase (a, 2);
165 * Count the number of zerobits at the low end of A
168 get_trailing_zeros (mpz_t a)
170 unsigned int count = 0;
171 unsigned int nbits = get_nbits (a);
173 while ((mpz_tstbit (a, count)) && (count < nbits))
179 * Set bit N of A. and clear all bits above
182 set_highbit (mpz_t a, unsigned int n)
186 nbits = get_nbits (a);
188 mpz_clrbit (a, nbits--);
193 mpz_randomize (mpz_t n, unsigned int nbits, GNUNET_HashCode * rnd)
195 GNUNET_HashCode *tmp;
199 cnt = (nbits / sizeof (GNUNET_HashCode) / 8) + 1;
200 tmp = GNUNET_malloc (sizeof (GNUNET_HashCode) * cnt);
203 for (i = 0; i < cnt - 1; i++)
205 GNUNET_CRYPTO_hash (&tmp[i], sizeof (GNUNET_HashCode), &tmp[i + 1]);
208 mpz_import (n, cnt * sizeof (GNUNET_HashCode) / sizeof (unsigned int),
209 1, sizeof (unsigned int), 1, 0, tmp);
217 * Return true if n is probably a prime
220 is_prime (mpz_t n, int steps, GNUNET_HashCode * hc)
228 unsigned int i, j, k;
236 mpz_init_set_ui (a2, 2);
237 nbits = get_nbits (n);
238 mpz_sub_ui (nminus1, n, 1);
240 /* Find q and k, so that n = 1 + 2^k * q . */
241 mpz_init_set (q, nminus1);
242 k = get_trailing_zeros (q);
243 mpz_tdiv_q_2exp (q, q, k);
245 for (i = 0; i < steps; i++)
253 mpz_randomize (x, nbits, hc);
255 /* Make sure that the number is smaller than the prime and
256 keep the randomness of the high bit. */
257 if (mpz_tstbit (x, nbits - 2))
259 set_highbit (x, nbits - 2); /* Clear all higher bits. */
263 set_highbit (x, nbits - 2);
264 mpz_clrbit (x, nbits - 2);
266 GNUNET_assert (mpz_cmp (x, nminus1) < 0 && mpz_cmp_ui (x, 1) > 0);
268 mpz_powm (y, x, q, n);
269 if (mpz_cmp_ui (y, 1) && mpz_cmp (y, nminus1))
271 for (j = 1; j < k && mpz_cmp (y, nminus1); j++)
273 mpz_powm (y, y, a2, n);
274 if (!mpz_cmp_ui (y, 1))
275 goto leave; /* Not a prime. */
277 if (mpz_cmp (y, nminus1))
278 goto leave; /* Not a prime. */
281 rc = 1; /* May be a prime. */
295 gen_prime (mpz_t ptest, unsigned int nbits, GNUNET_HashCode * hc)
297 mpz_t prime, pminus1, val_2, val_3, result;
303 GNUNET_assert (nbits >= 16);
305 mods = GNUNET_malloc (no_of_small_prime_numbers * sizeof (*mods));
306 /* Make nbits fit into mpz_t implementation. */
307 mpz_init_set_ui (val_2, 2);
308 mpz_init_set_ui (val_3, 3);
315 /* generate a random number */
316 mpz_randomize (prime, nbits, hc);
317 /* Set high order bit to 1, set low order bit to 1. If we are
318 generating a secret prime we are most probably doing that
319 for RSA, to make sure that the modulus does have the
320 requested key size we set the 2 high order bits. */
321 set_highbit (prime, nbits - 1);
322 mpz_setbit (prime, nbits - 2);
323 mpz_setbit (prime, 0);
325 /* Calculate all remainders. */
327 for (i = 0; (x = small_prime_numbers[i]); i++)
328 mods[i] = mpz_fdiv_r_ui (tmp, prime, x);
330 /* Now try some primes starting with prime. */
331 for (step = 0; step < 20000; step += 2)
333 /* Check against all the small primes we have in mods. */
334 for (i = 0; (x = small_prime_numbers[i]); i++)
336 while (mods[i] + step >= x)
338 if (!(mods[i] + step))
342 continue; /* Found a multiple of an already known prime. */
344 mpz_add_ui (ptest, prime, step);
345 if (!mpz_tstbit (ptest, nbits - 2))
348 /* Do a fast Fermat test now. */
349 mpz_sub_ui (pminus1, ptest, 1);
350 mpz_powm (result, val_2, pminus1, ptest);
351 if ((!mpz_cmp_ui (result, 1)) && (is_prime (ptest, 5, hc)))
367 * Find the greatest common divisor G of A and B.
368 * Return: 1 if this 1, 0 in all other cases
371 test_gcd (mpz_t g, mpz_t xa, mpz_t xb)
375 mpz_init_set (a, xa);
376 mpz_init_set (b, xb);
378 /* TAOCP Vol II, 4.5.2, Algorithm A */
379 while (mpz_cmp_ui (b, 0))
381 mpz_fdiv_r (g, a, b); /* g used as temorary variable */
389 return (0 == mpz_cmp_ui (g, 1));
393 * Generate a key pair with a key of size NBITS.
394 * @param sk where to store the key
395 * @param nbits the number of bits to use
396 * @param hc the HC to use for PRNG (modified!)
399 generate_kblock_key (KBlock_secret_key * sk,
400 unsigned int nbits, GNUNET_HashCode * hc)
403 mpz_t phi; /* helper: (p-1)(q-1) */
407 /* make sure that nbits is even so that we generate p, q of equal size */
411 mpz_init_set_ui (sk->e, 257);
430 gen_prime (sk->p, nbits / 2, hc);
431 gen_prime (sk->q, nbits / 2, hc);
433 if (mpz_cmp (sk->p, sk->q) > 0) /* p shall be smaller than q (for calc of u) */
434 mpz_swap (sk->p, sk->q);
435 /* calculate the modulus */
436 mpz_mul (sk->n, sk->p, sk->q);
438 while (get_nbits (sk->n) != nbits);
440 /* calculate Euler totient: phi = (p-1)(q-1) */
441 mpz_sub_ui (t1, sk->p, 1);
442 mpz_sub_ui (t2, sk->q, 1);
443 mpz_mul (phi, t1, t2);
445 mpz_fdiv_q (f, phi, g);
447 while (0 == test_gcd (t1, sk->e, phi))
448 { /* (while gcd is not 1) */
449 mpz_add_ui (sk->e, sk->e, 2);
452 /* calculate the secret key d = e^1 mod phi */
454 while ((0 == mpz_invert (sk->d, sk->e, f)) ||
455 (0 == mpz_invert (sk->u, sk->p, sk->q)));
466 * Internal representation of the private key.
468 struct KskRsaPrivateKeyBinaryEncoded
471 * Total size of the structure, in bytes, in big-endian!
473 uint16_t len GNUNET_PACKED;
474 uint16_t sizen GNUNET_PACKED; /* in big-endian! */
475 uint16_t sizee GNUNET_PACKED; /* in big-endian! */
476 uint16_t sized GNUNET_PACKED; /* in big-endian! */
477 uint16_t sizep GNUNET_PACKED; /* in big-endian! */
478 uint16_t sizeq GNUNET_PACKED; /* in big-endian! */
479 uint16_t sizedmp1 GNUNET_PACKED; /* in big-endian! */
480 uint16_t sizedmq1 GNUNET_PACKED; /* in big-endian! */
481 /* followed by the actual values */
486 * Deterministically (!) create a hostkey using only the
487 * given HashCode as input to the PRNG.
489 static struct KskRsaPrivateKeyBinaryEncoded *
490 makeKblockKeyInternal (const GNUNET_HashCode * hc)
492 KBlock_secret_key sk;
497 struct KskRsaPrivateKeyBinaryEncoded *retval;
502 generate_kblock_key (&sk, 1024, /* at least 10x as fast than 2048 bits
503 -- we simply cannot afford 2048 bits
504 even on modern hardware, and especially
505 not since clearly a dictionary attack
506 will still be much cheaper
507 than breaking a 1024 bit RSA key.
508 If an adversary can spend the time to
509 break a 1024 bit RSA key just to forge
510 a signature -- SO BE IT. [ CG, 6/2005 ] */
518 size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
519 for (i = 0; i < 6; i++)
521 pbu[i] = mpz_export (NULL, &sizes[i], 1, /* most significant word first */
522 1, /* unit is bytes */
528 GNUNET_assert (size < 65536);
529 retval = GNUNET_malloc (size);
530 retval->len = htons (size);
532 retval->sizen = htons (sizes[0]);
533 memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
535 retval->sizee = htons (sizes[1]);
536 memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
538 retval->sized = htons (sizes[2]);
539 memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
542 retval->sizep = htons (sizes[4]);
543 memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
545 retval->sizeq = htons (sizes[3]);
546 memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
548 retval->sizedmp1 = htons (0);
549 retval->sizedmq1 = htons (0);
550 memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
551 for (i = 0; i < 6; i++)
561 * Decode the internal format into the format used
564 static struct GNUNET_CRYPTO_RsaPrivateKey *
565 ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
567 struct GNUNET_CRYPTO_RsaPrivateKey *ret;
569 gcry_mpi_t n, e, d, p, q, u;
575 size = ntohs (encoding->sizen);
576 rc = gcry_mpi_scan (&n,
578 &((const unsigned char *) (&encoding[1]))[pos],
580 pos += ntohs (encoding->sizen);
583 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
586 size = ntohs (encoding->sizee);
587 rc = gcry_mpi_scan (&e,
589 &((const unsigned char *) (&encoding[1]))[pos],
591 pos += ntohs (encoding->sizee);
594 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
595 gcry_mpi_release (n);
598 size = ntohs (encoding->sized);
599 rc = gcry_mpi_scan (&d,
601 &((const unsigned char *) (&encoding[1]))[pos],
603 pos += ntohs (encoding->sized);
606 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
607 gcry_mpi_release (n);
608 gcry_mpi_release (e);
612 size = ntohs (encoding->sizep);
615 rc = gcry_mpi_scan (&q,
617 &((const unsigned char *) (&encoding[1]))[pos],
619 pos += ntohs (encoding->sizep);
622 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
623 gcry_mpi_release (n);
624 gcry_mpi_release (e);
625 gcry_mpi_release (d);
631 size = ntohs (encoding->sizeq);
634 rc = gcry_mpi_scan (&p,
636 &((const unsigned char *) (&encoding[1]))[pos],
638 pos += ntohs (encoding->sizeq);
641 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
642 gcry_mpi_release (n);
643 gcry_mpi_release (e);
644 gcry_mpi_release (d);
646 gcry_mpi_release (q);
652 pos += ntohs (encoding->sizedmp1);
653 pos += ntohs (encoding->sizedmq1);
655 ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
659 rc = gcry_mpi_scan (&u,
661 &((const unsigned char *) (&encoding[1]))[pos],
665 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
666 gcry_mpi_release (n);
667 gcry_mpi_release (e);
668 gcry_mpi_release (d);
670 gcry_mpi_release (p);
672 gcry_mpi_release (q);
679 if ((p != NULL) && (q != NULL) && (u != NULL))
681 rc = gcry_sexp_build (&res, &size, /* erroff */
682 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
687 if ((p != NULL) && (q != NULL))
689 rc = gcry_sexp_build (&res, &size, /* erroff */
690 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
695 rc = gcry_sexp_build (&res, &size, /* erroff */
696 "(private-key(rsa(n %m)(e %m)(d %m)))",
700 gcry_mpi_release (n);
701 gcry_mpi_release (e);
702 gcry_mpi_release (d);
704 gcry_mpi_release (p);
706 gcry_mpi_release (q);
708 gcry_mpi_release (u);
711 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
713 if (gcry_pk_testkey (res))
715 LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
719 ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
730 struct KskRsaPrivateKeyBinaryEncoded *pke;
731 } KBlockKeyCacheLine;
733 static KBlockKeyCacheLine **cache;
734 static unsigned int cacheSize;
737 * Deterministically (!) create a hostkey using only the
738 * given HashCode as input to the PRNG.
740 struct GNUNET_CRYPTO_RsaPrivateKey *
741 GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
743 struct GNUNET_CRYPTO_RsaPrivateKey *ret;
744 KBlockKeyCacheLine *line;
747 for (i = 0; i < cacheSize; i++)
749 if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
751 ret = ksk_decode_key (cache[i]->pke);
756 line = GNUNET_malloc (sizeof (KBlockKeyCacheLine));
758 line->pke = makeKblockKeyInternal (hc);
759 GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
760 cache[cacheSize - 1] = line;
761 return ksk_decode_key (line->pke);
764 void __attribute__ ((constructor)) GNUNET_CRYPTO_ksk_init ()
766 gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
767 if (!gcry_check_version (GCRYPT_VERSION))
771 ("libgcrypt has not the expected version (version %s is required).\n"),
775 #ifdef gcry_fast_random_poll
776 gcry_fast_random_poll ();
780 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
783 for (i = 0; i < cacheSize; i++)
785 GNUNET_free (cache[i]->pke);
786 GNUNET_free (cache[i]);
788 GNUNET_array_grow (cache, cacheSize, 0);
791 /* end of kblockkey.c */