src/util/crypto_ksk.c

   1 /*
   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)
   5
   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.
  10
  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.
  15
  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.
  20
  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
  24      ordinary RSA keys!
  25 */
  26
  27
  28 /**
  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
  33  */
  34
  35 #include "platform.h"
  36 #include "gnunet_common.h"
  37 #include "gnunet_crypto_lib.h"
  38 #include "gnunet_os_lib.h"
  39 #include <gmp.h>
  40 #include <gcrypt.h>
  41
  42 /**
  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).
  46  */
  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);
  48
  49
  50 typedef struct
  51 {
  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. */
  58 } KBlock_secret_key;
  59
  60 /**
  61  * The private information of an RSA key pair.
  62  * NOTE: this must match the definition in crypto_rsa.c
  63  */
  64 struct GNUNET_CRYPTO_RsaPrivateKey
  65 {
  66   gcry_sexp_t sexp;
  67 };
  68
  69
  70 /* Note: 2 is not included because it can be tested more easily by
  71    looking at bit 0. The last entry in this list is marked by a zero */
  72 static uint16_t small_prime_numbers[] = {
  73   3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
  74   47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
  75   103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
  76   157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
  77   211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
  78   269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
  79   331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
  80   389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
  81   449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
  82   509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
  83   587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
  84   643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
  85   709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
  86   773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
  87   853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
  88   919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
  89   991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
  90   1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
  91   1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
  92   1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
  93   1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
  94   1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
  95   1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
  96   1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
  97   1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
  98   1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
  99   1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
 100   1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
 101   1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
 102   1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
 103   1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
 104   1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
 105   1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
 106   1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
 107   2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
 108   2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
 109   2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
 110   2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
 111   2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
 112   2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
 113   2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
 114   2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
 115   2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
 116   2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
 117   2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
 118   2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
 119   2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
 120   2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
 121   2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
 122   3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
 123   3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
 124   3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
 125   3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
 126   3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
 127   3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
 128   3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
 129   3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
 130   3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
 131   3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
 132   3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
 133   3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
 134   3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
 135   3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
 136   3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
 137   4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
 138   4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
 139   4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
 140   4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
 141   4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
 142   4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
 143   4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
 144   4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
 145   4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
 146   4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
 147   4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
 148   4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
 149   4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
 150   4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
 151   4957, 4967, 4969, 4973, 4987, 4993, 4999,
 152   0
 153 };
 154
 155 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
 156 static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;
 157
 158
 159      static unsigned int
 160      get_nbits (mpz_t a)
 161 {
 162   return mpz_sizeinbase (a, 2);
 163 }
 164
 165
 166 /**
 167  * Set bit N of A. and clear all bits above
 168  */
 169 static void
 170 set_highbit (mpz_t a, unsigned int n)
 171 {
 172   unsigned int nbits;
 173
 174   nbits = get_nbits (a);
 175   while (nbits > n)
 176     mpz_clrbit (a, nbits--);
 177   mpz_setbit (a, n);
 178 }
 179
 180 static void
 181 mpz_randomize (mpz_t n, unsigned int nbits, GNUNET_HashCode * rnd)
 182 {
 183   GNUNET_HashCode *tmp;
 184   int cnt;
 185   int i;
 186
 187   cnt = (nbits / sizeof (GNUNET_HashCode) / 8) + 1;
 188   tmp = GNUNET_malloc (sizeof (GNUNET_HashCode) * cnt);
 189
 190   tmp[0] = *rnd;
 191   for (i = 0; i < cnt - 1; i++)
 192     {
 193       GNUNET_CRYPTO_hash (&tmp[i], sizeof (GNUNET_HashCode), &tmp[i + 1]);
 194     }
 195   *rnd = tmp[cnt - 1];
 196   mpz_import (n, cnt * sizeof (GNUNET_HashCode) / sizeof (unsigned int),
 197               1, sizeof (unsigned int), 1, 0, tmp);
 198   GNUNET_free (tmp);
 199   i = get_nbits (n);
 200   while (i > nbits)
 201     mpz_clrbit (n, i--);
 202 }
 203
 204 /**
 205  * Return true if n is probably a prime
 206  */
 207 static int
 208 is_prime (mpz_t n, int steps, GNUNET_HashCode * hc)
 209 {
 210   mpz_t x;
 211   mpz_t y;
 212   mpz_t z;
 213   mpz_t nminus1;
 214   mpz_t a2;
 215   mpz_t q;
 216   unsigned int i, j, k;
 217   int rc = 0;
 218   unsigned int nbits;
 219
 220   mpz_init (x);
 221   mpz_init (y);
 222   mpz_init (z);
 223   mpz_init (nminus1);
 224   mpz_init_set_ui (a2, 2);
 225   nbits = get_nbits (n);
 226   mpz_sub_ui (nminus1, n, 1);
 227
 228   /* Find q and k, so that n = 1 + 2^k * q . */
 229   mpz_init_set (q, nminus1);
 230   k = mpz_scan0 (q, 0);
 231   mpz_tdiv_q_2exp (q, q, k);
 232
 233   for (i = 0; i < steps; i++)
 234     {
 235       if (!i)
 236         {
 237           mpz_set_ui (x, 2);
 238         }
 239       else
 240         {
 241           mpz_randomize (x, nbits, hc);
 242
 243           /* Make sure that the number is smaller than the prime and
 244              keep the randomness of the high bit. */
 245           if (mpz_tstbit (x, nbits - 2))
 246             {
 247               set_highbit (x, nbits - 2);       /* Clear all higher bits. */
 248             }
 249           else
 250             {
 251               set_highbit (x, nbits - 2);
 252               mpz_clrbit (x, nbits - 2);
 253             }
 254           GNUNET_assert (mpz_cmp (x, nminus1) < 0 && mpz_cmp_ui (x, 1) > 0);
 255         }
 256       mpz_powm (y, x, q, n);
 257       if (mpz_cmp_ui (y, 1) && mpz_cmp (y, nminus1))
 258         {
 259           for (j = 1; j < k && mpz_cmp (y, nminus1); j++)
 260             {
 261               mpz_powm (y, y, a2, n);
 262               if (!mpz_cmp_ui (y, 1))
 263                 goto leave;     /* Not a prime. */
 264             }
 265           if (mpz_cmp (y, nminus1))
 266             goto leave;         /* Not a prime. */
 267         }
 268     }
 269   rc = 1;                       /* May be a prime. */
 270
 271 leave:
 272   mpz_clear (x);
 273   mpz_clear (y);
 274   mpz_clear (z);
 275   mpz_clear (nminus1);
 276   mpz_clear (q);
 277   mpz_clear (a2);
 278
 279   return rc;
 280 }
 281
 282 static void
 283 gen_prime (mpz_t ptest, unsigned int nbits, GNUNET_HashCode * hc)
 284 {
 285   mpz_t prime, pminus1, val_2, val_3, result;
 286   int i;
 287   unsigned x, step;
 288   int *mods;
 289   mpz_t tmp;
 290
 291   GNUNET_assert (nbits >= 16);
 292
 293   mods = GNUNET_malloc (no_of_small_prime_numbers * sizeof (*mods));
 294   /* Make nbits fit into mpz_t implementation. */
 295   mpz_init_set_ui (val_2, 2);
 296   mpz_init_set_ui (val_3, 3);
 297   mpz_init (prime);
 298   mpz_init (result);
 299   mpz_init (pminus1);
 300   mpz_init (ptest);
 301   while (1)
 302     {
 303       /* generate a random number */
 304       mpz_randomize (prime, nbits, hc);
 305       /* Set high order bit to 1, set low order bit to 1.  If we are
 306          generating a secret prime we are most probably doing that
 307          for RSA, to make sure that the modulus does have the
 308          requested key size we set the 2 high order bits. */
 309       set_highbit (prime, nbits - 1);
 310       mpz_setbit (prime, nbits - 2);
 311       mpz_setbit (prime, 0);
 312
 313       /* Calculate all remainders. */
 314       mpz_init (tmp);
 315       for (i = 0; (x = small_prime_numbers[i]); i++)
 316         mods[i] = mpz_fdiv_r_ui (tmp, prime, x);
 317       mpz_clear (tmp);
 318       /* Now try some primes starting with prime. */
 319       for (step = 0; step < 20000; step += 2)
 320         {
 321           /* Check against all the small primes we have in mods. */
 322           for (i = 0; (x = small_prime_numbers[i]); i++)
 323             {
 324               while (mods[i] + step >= x)
 325                 mods[i] -= x;
 326               if (!(mods[i] + step))
 327                 break;
 328             }
 329           if (x)
 330             continue;           /* Found a multiple of an already known prime. */
 331
 332           mpz_add_ui (ptest, prime, step);
 333           if (!mpz_tstbit (ptest, nbits - 2))
 334             break;
 335
 336           /* Do a fast Fermat test now. */
 337           mpz_sub_ui (pminus1, ptest, 1);
 338           mpz_powm (result, val_2, pminus1, ptest);
 339           if ((!mpz_cmp_ui (result, 1)) && (is_prime (ptest, 5, hc)))
 340             {
 341               /* Got it. */
 342               mpz_clear (val_2);
 343               mpz_clear (val_3);
 344               mpz_clear (result);
 345               mpz_clear (pminus1);
 346               mpz_clear (prime);
 347               GNUNET_free (mods);
 348               return;
 349             }
 350         }
 351     }
 352 }
 353
 354 /**
 355  * Find the greatest common divisor G of A and B.
 356  * Return: 1 if this 1, 0 in all other cases
 357  */
 358 static int
 359 test_gcd (mpz_t g, mpz_t xa, mpz_t xb)
 360 {
 361   mpz_t a, b;
 362
 363   mpz_init_set (a, xa);
 364   mpz_init_set (b, xb);
 365
 366   /* TAOCP Vol II, 4.5.2, Algorithm A */
 367   while (mpz_cmp_ui (b, 0))
 368     {
 369       mpz_fdiv_r (g, a, b);     /* g used as temorary variable */
 370       mpz_set (a, b);
 371       mpz_set (b, g);
 372     }
 373   mpz_set (g, a);
 374
 375   mpz_clear (a);
 376   mpz_clear (b);
 377   return (0 == mpz_cmp_ui (g, 1));
 378 }
 379
 380 /**
 381  * Generate a key pair with a key of size NBITS.
 382  * @param sk where to store the key
 383  * @param nbits the number of bits to use
 384  * @param hc the HC to use for PRNG (modified!)
 385  */
 386 static void
 387 generate_kblock_key (KBlock_secret_key * sk,
 388                      unsigned int nbits, GNUNET_HashCode * hc)
 389 {
 390   mpz_t t1, t2;
 391   mpz_t phi;                    /* helper: (p-1)(q-1) */
 392   mpz_t g;
 393   mpz_t f;
 394
 395   /* make sure that nbits is even so that we generate p, q of equal size */
 396   if ((nbits & 1))
 397     nbits++;
 398
 399   mpz_init_set_ui (sk->e, 257);
 400   mpz_init (sk->n);
 401   mpz_init (sk->p);
 402   mpz_init (sk->q);
 403   mpz_init (sk->d);
 404   mpz_init (sk->u);
 405
 406   mpz_init (t1);
 407   mpz_init (t2);
 408   mpz_init (phi);
 409   mpz_init (g);
 410   mpz_init (f);
 411
 412   do
 413     {
 414       do
 415         {
 416           mpz_clear (sk->p);
 417           mpz_clear (sk->q);
 418           gen_prime (sk->p, nbits / 2, hc);
 419           gen_prime (sk->q, nbits / 2, hc);
 420
 421           if (mpz_cmp (sk->p, sk->q) > 0)       /* p shall be smaller than q (for calc of u) */
 422             mpz_swap (sk->p, sk->q);
 423           /* calculate the modulus */
 424           mpz_mul (sk->n, sk->p, sk->q);
 425         }
 426       while (get_nbits (sk->n) != nbits);
 427
 428       /* calculate Euler totient: phi = (p-1)(q-1) */
 429       mpz_sub_ui (t1, sk->p, 1);
 430       mpz_sub_ui (t2, sk->q, 1);
 431       mpz_mul (phi, t1, t2);
 432       mpz_gcd (g, t1, t2);
 433       mpz_fdiv_q (f, phi, g);
 434
 435       while (0 == test_gcd (t1, sk->e, phi))
 436         {                       /* (while gcd is not 1) */
 437           mpz_add_ui (sk->e, sk->e, 2);
 438         }
 439
 440       /* calculate the secret key d = e^1 mod phi */
 441     }
 442   while ((0 == mpz_invert (sk->d, sk->e, f)) ||
 443          (0 == mpz_invert (sk->u, sk->p, sk->q)));
 444
 445   mpz_clear (t1);
 446   mpz_clear (t2);
 447   mpz_clear (phi);
 448   mpz_clear (f);
 449   mpz_clear (g);
 450 }
 451
 452
 453 /**
 454  * Internal representation of the private key.
 455  */
 456 struct KskRsaPrivateKeyBinaryEncoded
 457 {
 458   /**
 459    * Total size of the structure, in bytes, in big-endian!
 460    */
 461   uint16_t len GNUNET_PACKED;
 462   uint16_t sizen GNUNET_PACKED; /*  in big-endian! */
 463   uint16_t sizee GNUNET_PACKED; /*  in big-endian! */
 464   uint16_t sized GNUNET_PACKED; /*  in big-endian! */
 465   uint16_t sizep GNUNET_PACKED; /*  in big-endian! */
 466   uint16_t sizeq GNUNET_PACKED; /*  in big-endian! */
 467   uint16_t sizedmp1 GNUNET_PACKED;      /*  in big-endian! */
 468   uint16_t sizedmq1 GNUNET_PACKED;      /*  in big-endian! */
 469   /* followed by the actual values */
 470 };
 471
 472
 473 /**
 474  * Deterministically (!) create a hostkey using only the
 475  * given HashCode as input to the PRNG.
 476  */
 477 static struct KskRsaPrivateKeyBinaryEncoded *
 478 makeKblockKeyInternal (const GNUNET_HashCode * hc)
 479 {
 480   KBlock_secret_key sk;
 481   GNUNET_HashCode hx;
 482   void *pbu[6];
 483   mpz_t *pkv[6];
 484   size_t sizes[6];
 485   struct KskRsaPrivateKeyBinaryEncoded *retval;
 486   int i;
 487   size_t size;
 488
 489   hx = *hc;
 490   generate_kblock_key (&sk, 1024,       /* at least 10x as fast than 2048 bits
 491                                            -- we simply cannot afford 2048 bits
 492                                            even on modern hardware, and especially
 493                                            not since clearly a dictionary attack
 494                                            will still be much cheaper
 495                                            than breaking a 1024 bit RSA key.
 496                                            If an adversary can spend the time to
 497                                            break a 1024 bit RSA key just to forge
 498                                            a signature -- SO BE IT. [ CG, 6/2005 ] */
 499                        &hx);
 500   pkv[0] = &sk.n;
 501   pkv[1] = &sk.e;
 502   pkv[2] = &sk.d;
 503   pkv[3] = &sk.p;
 504   pkv[4] = &sk.q;
 505   pkv[5] = &sk.u;
 506   size = sizeof (struct KskRsaPrivateKeyBinaryEncoded);
 507   for (i = 0; i < 6; i++)
 508     {
 509       pbu[i] = mpz_export (NULL, &sizes[i], 1,  /* most significant word first */
 510                            1,   /* unit is bytes */
 511                            1,   /* big endian */
 512                            0,   /* nails */
 513                            *pkv[i]);
 514       size += sizes[i];
 515     }
 516   GNUNET_assert (size < 65536);
 517   retval = GNUNET_malloc (size);
 518   retval->len = htons (size);
 519   i = 0;
 520   retval->sizen = htons (sizes[0]);
 521   memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
 522   i += sizes[0];
 523   retval->sizee = htons (sizes[1]);
 524   memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
 525   i += sizes[1];
 526   retval->sized = htons (sizes[2]);
 527   memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
 528   i += sizes[2];
 529   /* swap p and q! */
 530   retval->sizep = htons (sizes[4]);
 531   memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
 532   i += sizes[4];
 533   retval->sizeq = htons (sizes[3]);
 534   memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
 535   i += sizes[3];
 536   retval->sizedmp1 = htons (0);
 537   retval->sizedmq1 = htons (0);
 538   memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
 539   for (i = 0; i < 6; i++)
 540     {
 541       mpz_clear (*pkv[i]);
 542       free (pbu[i]);
 543     }
 544   return retval;
 545 }
 546
 547
 548 /**
 549  * Decode the internal format into the format used
 550  * by libgcrypt.
 551  */
 552 static struct GNUNET_CRYPTO_RsaPrivateKey *
 553 ksk_decode_key (const struct KskRsaPrivateKeyBinaryEncoded *encoding)
 554 {
 555   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 556   gcry_sexp_t res;
 557   gcry_mpi_t n, e, d, p, q, u;
 558   int rc;
 559   size_t size;
 560   int pos;
 561
 562   pos = 0;
 563   size = ntohs (encoding->sizen);
 564   rc = gcry_mpi_scan (&n,
 565                       GCRYMPI_FMT_USG,
 566                       &((const unsigned char *) (&encoding[1]))[pos],
 567                       size, &size);
 568   pos += ntohs (encoding->sizen);
 569   if (rc)
 570     {
 571       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 572       return NULL;
 573     }
 574   size = ntohs (encoding->sizee);
 575   rc = gcry_mpi_scan (&e,
 576                       GCRYMPI_FMT_USG,
 577                       &((const unsigned char *) (&encoding[1]))[pos],
 578                       size, &size);
 579   pos += ntohs (encoding->sizee);
 580   if (rc)
 581     {
 582       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 583       gcry_mpi_release (n);
 584       return NULL;
 585     }
 586   size = ntohs (encoding->sized);
 587   rc = gcry_mpi_scan (&d,
 588                       GCRYMPI_FMT_USG,
 589                       &((const unsigned char *) (&encoding[1]))[pos],
 590                       size, &size);
 591   pos += ntohs (encoding->sized);
 592   if (rc)
 593     {
 594       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 595       gcry_mpi_release (n);
 596       gcry_mpi_release (e);
 597       return NULL;
 598     }
 599   /* swap p and q! */
 600   size = ntohs (encoding->sizep);
 601   if (size > 0)
 602     {
 603       rc = gcry_mpi_scan (&q,
 604                           GCRYMPI_FMT_USG,
 605                           &((const unsigned char *) (&encoding[1]))[pos],
 606                           size, &size);
 607       pos += ntohs (encoding->sizep);
 608       if (rc)
 609         {
 610           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 611           gcry_mpi_release (n);
 612           gcry_mpi_release (e);
 613           gcry_mpi_release (d);
 614           return NULL;
 615         }
 616     }
 617   else
 618     q = NULL;
 619   size = ntohs (encoding->sizeq);
 620   if (size > 0)
 621     {
 622       rc = gcry_mpi_scan (&p,
 623                           GCRYMPI_FMT_USG,
 624                           &((const unsigned char *) (&encoding[1]))[pos],
 625                           size, &size);
 626       pos += ntohs (encoding->sizeq);
 627       if (rc)
 628         {
 629           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 630           gcry_mpi_release (n);
 631           gcry_mpi_release (e);
 632           gcry_mpi_release (d);
 633           if (q != NULL)
 634             gcry_mpi_release (q);
 635           return NULL;
 636         }
 637     }
 638   else
 639     p = NULL;
 640   pos += ntohs (encoding->sizedmp1);
 641   pos += ntohs (encoding->sizedmq1);
 642   size =
 643     ntohs (encoding->len) - sizeof (struct KskRsaPrivateKeyBinaryEncoded) -
 644     pos;
 645   if (size > 0)
 646     {
 647       rc = gcry_mpi_scan (&u,
 648                           GCRYMPI_FMT_USG,
 649                           &((const unsigned char *) (&encoding[1]))[pos],
 650                           size, &size);
 651       if (rc)
 652         {
 653           LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_mpi_scan", rc);
 654           gcry_mpi_release (n);
 655           gcry_mpi_release (e);
 656           gcry_mpi_release (d);
 657           if (p != NULL)
 658             gcry_mpi_release (p);
 659           if (q != NULL)
 660             gcry_mpi_release (q);
 661           return NULL;
 662         }
 663     }
 664   else
 665     u = NULL;
 666
 667   if ((p != NULL) && (q != NULL) && (u != NULL))
 668     {
 669       rc = gcry_sexp_build (&res, &size,        /* erroff */
 670                             "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)(u %m)))",
 671                             n, e, d, p, q, u);
 672     }
 673   else
 674     {
 675       if ((p != NULL) && (q != NULL))
 676         {
 677           rc = gcry_sexp_build (&res, &size,    /* erroff */
 678                                 "(private-key(rsa(n %m)(e %m)(d %m)(p %m)(q %m)))",
 679                                 n, e, d, p, q);
 680         }
 681       else
 682         {
 683           rc = gcry_sexp_build (&res, &size,    /* erroff */
 684                                 "(private-key(rsa(n %m)(e %m)(d %m)))",
 685                                 n, e, d);
 686         }
 687     }
 688   gcry_mpi_release (n);
 689   gcry_mpi_release (e);
 690   gcry_mpi_release (d);
 691   if (p != NULL)
 692     gcry_mpi_release (p);
 693   if (q != NULL)
 694     gcry_mpi_release (q);
 695   if (u != NULL)
 696     gcry_mpi_release (u);
 697
 698   if (rc)
 699     LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
 700 #if EXTRA_CHECKS
 701   if (gcry_pk_testkey (res))
 702     {
 703       LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_testkey", rc);
 704       return NULL;
 705     }
 706 #endif
 707   ret = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_RsaPrivateKey));
 708   ret->sexp = res;
 709   return ret;
 710 }
 711
 712
 713
 714
 715 typedef struct
 716 {
 717   GNUNET_HashCode hc;
 718   struct KskRsaPrivateKeyBinaryEncoded *pke;
 719 } KBlockKeyCacheLine;
 720
 721 static KBlockKeyCacheLine **cache;
 722 static unsigned int cacheSize;
 723
 724 /**
 725  * Deterministically (!) create a hostkey using only the
 726  * given HashCode as input to the PRNG.
 727  */
 728 struct GNUNET_CRYPTO_RsaPrivateKey *
 729 GNUNET_CRYPTO_rsa_key_create_from_hash (const GNUNET_HashCode * hc)
 730 {
 731   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 732   KBlockKeyCacheLine *line;
 733   int i;
 734
 735   for (i = 0; i < cacheSize; i++)
 736     {
 737       if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
 738         {
 739           ret = ksk_decode_key (cache[i]->pke);
 740           return ret;
 741         }
 742     }
 743
 744   line = GNUNET_malloc (sizeof (KBlockKeyCacheLine));
 745   line->hc = *hc;
 746   line->pke = makeKblockKeyInternal (hc);
 747   GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
 748   cache[cacheSize - 1] = line;
 749   return ksk_decode_key (line->pke);
 750 }
 751
 752
 753 /**
 754  * Process ID of the "find" process that we use for
 755  * entropy gathering.
 756  */
 757 static pid_t genproc;
 758
 759 /**
 760  * Function called by libgcrypt whenever we are
 761  * blocked gathering entropy.
 762  */
 763 static void
 764 entropy_generator (void *cls,
 765                    const char *what, int printchar, int current, int total)
 766 {
 767   unsigned long code;
 768   enum GNUNET_OS_ProcessStatusType type;
 769   int ret;
 770
 771   if (0 != strcmp (what, "need_entropy"))
 772     return;
 773   if (current == total)
 774     {
 775       if (genproc != 0)
 776         {
 777           if (0 != PLIBC_KILL (genproc, SIGTERM))
 778             GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "kill");
 779           GNUNET_break (GNUNET_OK == GNUNET_OS_process_wait (genproc));
 780           genproc = 0;
 781         }
 782       return;
 783     }
 784   if (genproc != 0)
 785     {
 786       ret = GNUNET_OS_process_status (genproc, &type, &code);
 787       if (ret == GNUNET_NO)
 788         return;                 /* still running */
 789       if (ret == GNUNET_SYSERR)
 790         {
 791           GNUNET_break (0);
 792           return;
 793         }
 794       if (0 != PLIBC_KILL (genproc, SIGTERM))
 795         GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "kill");
 796       GNUNET_break (GNUNET_OK == GNUNET_OS_process_wait (genproc));
 797       genproc = 0;
 798     }
 799   GNUNET_log (GNUNET_ERROR_TYPE_INFO,
 800               _("Starting `%s' process to generate entropy\n"), "find");
 801   genproc = GNUNET_OS_start_process (NULL, NULL, "sh",
 802                                      "sh",
 803                                      "-c",
 804                                      "exec find / -mount -type f -exec cp {} /dev/null \\; 2>/dev/null",
 805                                      NULL);
 806 }
 807
 808
 809 static void
 810 killfind ()
 811 {
 812   if (genproc != 0)
 813     {
 814       PLIBC_KILL (genproc, SIGKILL);
 815       genproc = 0;
 816     }
 817 }
 818
 819
 820 void __attribute__ ((constructor)) GNUNET_CRYPTO_ksk_init ()
 821 {
 822   gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
 823   if (!gcry_check_version (GCRYPT_VERSION))
 824     {
 825       fprintf (stderr,
 826                _
 827                ("libgcrypt has not the expected version (version %s is required).\n"),
 828                GCRYPT_VERSION);
 829       abort ();
 830     }
 831 #ifdef gcry_fast_random_poll
 832   gcry_fast_random_poll ();
 833 #endif
 834   gcry_set_progress_handler (&entropy_generator, NULL);
 835   atexit (&killfind);
 836 }
 837
 838
 839 void __attribute__ ((destructor)) GNUNET_CRYPTO_ksk_fini ()
 840 {
 841   int i;
 842
 843   for (i = 0; i < cacheSize; i++)
 844     {
 845       GNUNET_free (cache[i]->pke);
 846       GNUNET_free (cache[i]);
 847     }
 848   GNUNET_array_grow (cache, cacheSize, 0);
 849   gcry_set_progress_handler (NULL, NULL);
 850 }
 851
 852 /* end of kblockkey.c */