kblockkey.c

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

  mpz_init (prime);
  mpz_init (result);
  mpz_init (pminus1);
  mpz_init (ptest);
  while (1)
    {
      /* generate a random number */
      mpz_randomize (prime, nbits, hc);
      /* Set high order bit to 1, set low order bit to 1.  If we are
         generating a secret prime we are most probably doing that
         for RSA, to make sure that the modulus does have the
         requested key size we set the 2 high order bits. */
      set_highbit (prime, nbits - 1);
      mpz_setbit (prime, nbits - 2);
      mpz_setbit (prime, 0);

      /* Calculate all remainders. */
      mpz_init (tmp);
      for (i = 0; (x = small_prime_numbers[i]); i++)
        mods[i] = mpz_fdiv_r_ui (tmp, prime, x);
      mpz_clear (tmp);
      /* Now try some primes starting with prime. */
      for (step = 0; step < 20000; step += 2)
        {
          /* Check against all the small primes we have in mods. */
          for (i = 0; (x = small_prime_numbers[i]); i++)
            {
              while (mods[i] + step >= x)
                mods[i] -= x;
              if (!(mods[i] + step))
                break;
            }
          if (x)
            continue;           /* Found a multiple of an already known prime. */

          mpz_add_ui (ptest, prime, step);
          if (!mpz_tstbit (ptest, nbits - 2))
            break;

          /* Do a fast Fermat test now. */
          mpz_sub_ui (pminus1, ptest, 1);
          mpz_powm (result, val_2, pminus1, ptest);
          if ((!mpz_cmp_ui (result, 1)) && (is_prime (ptest, 5, hc)))
            {
              /* Got it. */
              mpz_clear (val_2);
              mpz_clear (val_3);
              mpz_clear (result);
              mpz_clear (pminus1);
              mpz_clear (prime);
              GNUNET_free (mods);
              return;
            }
        }
    }
}

/**
 * Find the greatest common divisor G of A and B.
 * Return: 1 if this 1, 0 in all other cases
 */
static int
test_gcd (mpz_t g, mpz_t xa, mpz_t xb)
{
  mpz_t a, b;

  mpz_init_set (a, xa);
  mpz_init_set (b, xb);

  /* TAOCP Vol II, 4.5.2, Algorithm A */
  while (mpz_cmp_ui (b, 0))
    {
      mpz_fdiv_r (g, a, b);     /* g used as temorary variable */
      mpz_set (a, b);
      mpz_set (b, g);
    }
  mpz_set (g, a);

  mpz_clear (a);
  mpz_clear (b);
  return (0 == mpz_cmp_ui (g, 1));
}

/**
 * Generate a key pair with a key of size NBITS.
 * @param sk where to store the key
 * @param nbits the number of bits to use
 * @param hc the HC to use for PRNG (modified!)
 */
static void
generate_kblock_key (KBlock_secret_key * sk,
                     unsigned int nbits, GNUNET_HashCode * hc)
{
  mpz_t t1, t2;
  mpz_t phi;                    /* helper: (p-1)(q-1) */
  mpz_t g;
  mpz_t f;

  /* make sure that nbits is even so that we generate p, q of equal size */
  if ((nbits & 1))
    nbits++;

  mpz_init_set_ui (sk->e, 257);
  mpz_init (sk->n);
  mpz_init (sk->p);
  mpz_init (sk->q);
  mpz_init (sk->d);
  mpz_init (sk->u);

  mpz_init (t1);
  mpz_init (t2);
  mpz_init (phi);
  mpz_init (g);
  mpz_init (f);

  do
    {
      do
        {
          mpz_clear (sk->p);
          mpz_clear (sk->q);
          gen_prime (sk->p, nbits / 2, hc);
          gen_prime (sk->q, nbits / 2, hc);

          if (mpz_cmp (sk->p, sk->q) > 0)       /* p shall be smaller than q (for calc of u) */
            mpz_swap (sk->p, sk->q);
          /* calculate the modulus */
          mpz_mul (sk->n, sk->p, sk->q);
        }
      while (get_nbits (sk->n) != nbits);

      /* calculate Euler totient: phi = (p-1)(q-1) */
      mpz_sub_ui (t1, sk->p, 1);
      mpz_sub_ui (t2, sk->q, 1);
      mpz_mul (phi, t1, t2);
      mpz_gcd (g, t1, t2);
      mpz_fdiv_q (f, phi, g);

      while (0 == test_gcd (t1, sk->e, phi))
        {                       /* (while gcd is not 1) */
          mpz_add_ui (sk->e, sk->e, 2);
        }

      /* calculate the secret key d = e^1 mod phi */
    }
  while ((0 == mpz_invert (sk->d, sk->e, f)) ||
         (0 == mpz_invert (sk->u, sk->p, sk->q)));

  mpz_clear (t1);
  mpz_clear (t2);
  mpz_clear (phi);
  mpz_clear (f);
  mpz_clear (g);
}

/**
 * Deterministically (!) create a hostkey using only the
 * given HashCode as input to the PRNG.
 */
static GNUNET_RSA_PrivateKeyEncoded *
makeKblockKeyInternal (const GNUNET_HashCode * hc)
{
  KBlock_secret_key sk;
  GNUNET_HashCode hx;
  void *pbu[6];
  mpz_t *pkv[6];
  size_t sizes[6];
  GNUNET_RSA_PrivateKeyEncoded *retval;
  int i;
  size_t size;

  hx = *hc;
  generate_kblock_key (&sk, 1024,       /* at least 10x as fast than 2048 bits
                                           -- we simply cannot afford 2048 bits
                                           even on modern hardware, and especially
                                           not since clearly a dictionary attack
                                           will still be much cheaper
                                           than breaking a 1024 bit RSA key.
                                           If an adversary can spend the time to
                                           break a 1024 bit RSA key just to forge
                                           a signature -- SO BE IT. [ CG, 6/2005 ] */
                       &hx);
  pkv[0] = &sk.n;
  pkv[1] = &sk.e;
  pkv[2] = &sk.d;
  pkv[3] = &sk.p;
  pkv[4] = &sk.q;
  pkv[5] = &sk.u;
  size = sizeof (GNUNET_RSA_PrivateKeyEncoded);
  for (i = 0; i < 6; i++)
    {
      pbu[i] = mpz_export (NULL, &sizes[i], 1,  /* most significant word first */
                           1,   /* unit is bytes */
                           1,   /* big endian */
                           0,   /* nails */
                           *pkv[i]);
      size += sizes[i];
    }
  GNUNET_GE_ASSERT (NULL, size < 65536);
  retval = GNUNET_malloc (size);
  retval->len = htons (size);
  i = 0;
  retval->sizen = htons (sizes[0]);
  memcpy (&((char *) &retval[1])[i], pbu[0], sizes[0]);
  i += sizes[0];
  retval->sizee = htons (sizes[1]);
  memcpy (&((char *) &retval[1])[i], pbu[1], sizes[1]);
  i += sizes[1];
  retval->sized = htons (sizes[2]);
  memcpy (&((char *) &retval[1])[i], pbu[2], sizes[2]);
  i += sizes[2];
  /* swap p and q! */
  retval->sizep = htons (sizes[4]);
  memcpy (&((char *) &retval[1])[i], pbu[4], sizes[4]);
  i += sizes[4];
  retval->sizeq = htons (sizes[3]);
  memcpy (&((char *) &retval[1])[i], pbu[3], sizes[3]);
  i += sizes[3];
  retval->sizedmp1 = htons (0);
  retval->sizedmq1 = htons (0);
  memcpy (&((char *) &retval[1])[i], pbu[5], sizes[5]);
  for (i = 0; i < 6; i++)
    {
      mpz_clear (*pkv[i]);
      free (pbu[i]);
    }
  return retval;
}

typedef struct
{
  GNUNET_HashCode hc;
  GNUNET_RSA_PrivateKeyEncoded *pke;
} KBlockKeyCacheLine;

static KBlockKeyCacheLine **cache;
static unsigned int cacheSize;
static struct GNUNET_Mutex *lock;

/**
 * Deterministically (!) create a hostkey using only the
 * given HashCode as input to the PRNG.
 */
struct GNUNET_RSA_PrivateKey *
GNUNET_RSA_create_key_from_hash (const GNUNET_HashCode * hc)
{
  struct GNUNET_RSA_PrivateKey *ret;
  KBlockKeyCacheLine *line;
  int i;

  GNUNET_mutex_lock (lock);
  for (i = 0; i < cacheSize; i++)
    {
      if (0 == memcmp (hc, &cache[i]->hc, sizeof (GNUNET_HashCode)))
        {
          ret = GNUNET_RSA_decode_key (cache[i]->pke);
          GNUNET_mutex_unlock (lock);
          return ret;
        }
    }

  line = GNUNET_malloc (sizeof (KBlockKeyCacheLine));
  line->hc = *hc;
  line->pke = makeKblockKeyInternal (hc);
  GNUNET_array_grow (cache, cacheSize, cacheSize + 1);
  cache[cacheSize - 1] = line;
  GNUNET_mutex_unlock (lock);
  return GNUNET_RSA_decode_key (line->pke);
}

void __attribute__ ((constructor)) GNUNET_crypto_kblock_ltdl_init ()
{
  lock = GNUNET_mutex_create (GNUNET_NO);
}

void __attribute__ ((destructor)) GNUNET_crypto_kblock_ltdl_fini ()
{
  int i;
  for (i = 0; i < cacheSize; i++)
    {
      GNUNET_free (cache[i]->pke);
      GNUNET_free (cache[i]);
    }
  GNUNET_array_grow (cache, cacheSize, 0);
  GNUNET_mutex_destroy (lock);
}

/* end of kblockkey.c */