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