kblockkey.c

GNUnet是一个安全的点对点网络框架

/*
     This file is part of GNUnet.
     Copyright (C) 1994, 1996, 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
     Copyright (C) 2004, 2005, 2006 Christian Grothoff (and other contributing authors)

     GNUnet is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published
     by the Free Software Foundation; either version 2, or (at your
     option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with GNUnet; see the file COPYING.  If not, write to the
     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
     Boston, MA 02111-1307, USA.

     Note: This code is based on code from libgcrypt
     The code was adapted for GNUnet to support RSA-key generation
     based on weak, pseudo-random keys.  Do NOT use to generate
     ordinary RSA keys!
*/


/**
 * @file util/crypto/kblockkey.c
 * @brief implementation of RSA-Key generation for KBlocks
 *        (do NOT use for pseudonyms or hostkeys!)
 * @author Christian Grothoff
 */

#include "platform.h"
#include "gnunet_util.h"
#include "gnunet_util_crypto.h"
#include <gmp.h>

typedef struct
{
  mpz_t n;                      /* public modulus */
  mpz_t e;                      /* public exponent */
  mpz_t d;                      /* exponent */
  mpz_t p;                      /* prime  p. */
  mpz_t q;                      /* prime  q. */
  mpz_t u;                      /* inverse of p mod q. */
} KBlock_secret_key;

/* Note: 2 is not included because it can be tested more easily by
   looking at bit 0. The last entry in this list is marked by a zero */
static unsigned short small_prime_numbers[] = {
  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
  47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
  103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
  157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
  211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
  269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
  331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
  389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
  449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
  509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
  587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
  643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
  709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
  773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
  853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
  919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
  991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
  1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
  1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
  1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
  1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
  1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
  1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
  1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
  1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
  1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
  1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
  1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
  1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
  1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
  1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
  1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
  1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
  1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
  2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
  2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
  2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
  2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
  2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
  2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
  2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
  2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
  2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
  2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
  2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
  2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
  2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
  2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
  2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
  3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
  3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
  3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
  3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
  3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
  3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
  3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
  3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
  3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
  3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
  3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
  3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
  3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
  3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
  3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
  4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
  4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
  4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
  4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
  4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
  4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
  4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
  4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
  4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
  4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
  4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
  4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
  4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
  4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
  4957, 4967, 4969, 4973, 4987, 4993, 4999,
  0
};

#define DIM(v) (sizeof(v)/sizeof((v)[0]))
static int no_of_small_prime_numbers = DIM (small_prime_numbers) - 1;


     static unsigned int
     get_nbits (mpz_t a)
{
  return mpz_sizeinbase (a, 2);
}

/**
 * Count the number of zerobits at the low end of A
 */
static unsigned int
get_trailing_zeros (mpz_t a)
{
  unsigned int count = 0;
  unsigned int nbits = get_nbits (a);

  while ((mpz_tstbit (a, count)) && (count < nbits))
    count++;
  return count;
}

/**
 * Set bit N of A. and clear all bits above
 */
static void
set_highbit (mpz_t a, unsigned int n)
{
  unsigned int nbits;

  nbits = get_nbits (a);
  while (nbits > n)
    mpz_clrbit (a, nbits--);
  mpz_setbit (a, n);
}

static void
mpz_randomize (mpz_t n, unsigned int nbits, GNUNET_HashCode * rnd)
{
  GNUNET_HashCode *tmp;
  int cnt;
  int i;

  cnt = (nbits / sizeof (GNUNET_HashCode) / 8) + 1;
  tmp = GNUNET_malloc (sizeof (GNUNET_HashCode) * cnt);

  tmp[0] = *rnd;
  for (i = 0; i < cnt - 1; i++)
    {
      GNUNET_hash (&tmp[i], sizeof (GNUNET_HashCode), &tmp[i + 1]);
    }
  *rnd = tmp[cnt - 1];
  mpz_import (n, cnt * sizeof (GNUNET_HashCode) / sizeof (unsigned int),
              1, sizeof (unsigned int), 1, 0, tmp);
  GNUNET_free (tmp);
  i = get_nbits (n);
  while (i > nbits)
    mpz_clrbit (n, i--);
}

/**
 * Return true if n is probably a prime
 */
static int
is_prime (mpz_t n, int steps, GNUNET_HashCode * hc)
{
  mpz_t x;
  mpz_t y;
  mpz_t z;
  mpz_t nminus1;
  mpz_t a2;
  mpz_t q;
  unsigned int i, j, k;
  int rc = 0;
  unsigned int nbits;

  mpz_init (x);
  mpz_init (y);
  mpz_init (z);
  mpz_init (nminus1);
  mpz_init_set_ui (a2, 2);
  nbits = get_nbits (n);
  mpz_sub_ui (nminus1, n, 1);

  /* Find q and k, so that n = 1 + 2^k * q . */
  mpz_init_set (q, nminus1);
  k = get_trailing_zeros (q);
  mpz_tdiv_q_2exp (q, q, k);

  for (i = 0; i < steps; i++)
    {
      if (!i)
        {
          mpz_set_ui (x, 2);
        }
      else
        {
          mpz_randomize (x, nbits, hc);

          /* Make sure that the number is smaller than the prime and
             keep the randomness of the high bit. */
          if (mpz_tstbit (x, nbits - 2))
            {
              set_highbit (x, nbits - 2);       /* Clear all higher bits. */
            }
          else
            {
              set_highbit (x, nbits - 2);
              mpz_clrbit (x, nbits - 2);
            }
          GNUNET_GE_ASSERT (NULL, mpz_cmp (x, nminus1) < 0
                            && mpz_cmp_ui (x, 1) > 0);
        }
      mpz_powm (y, x, q, n);
      if (mpz_cmp_ui (y, 1) && mpz_cmp (y, nminus1))
        {
          for (j = 1; j < k && mpz_cmp (y, nminus1); j++)
            {
              mpz_powm (y, y, a2, n);
              if (!mpz_cmp_ui (y, 1))
                goto leave;     /* Not a prime. */
            }
          if (mpz_cmp (y, nminus1))
            goto leave;         /* Not a prime. */
        }
    }
  rc = 1;                       /* May be a prime. */

leave:
  mpz_clear (x);
  mpz_clear (y);
  mpz_clear (z);
  mpz_clear (nminus1);
  mpz_clear (q);
  mpz_clear (a2);

  return rc;
}

static void
gen_prime (mpz_t ptest, unsigned int nbits, GNUNET_HashCode * hc)
{
  mpz_t prime, pminus1, val_2, val_3, result;
  int i;
  unsigned x, step;
  int *mods;
  mpz_t tmp;

  GNUNET_GE_ASSERT (NULL, nbits >= 16);

  mods = GNUNET_malloc (no_of_small_prime_numbers * sizeof (*mods));
  /* Make nbits fit into mpz_t implementation. */
  mpz_init_set_ui (val_2, 2);
  mpz_init_set_ui (val_3, 3);