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