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