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