tests/prime.c

/* prime.c - part of the Libgcrypt test suite.
   Copyright (C) 2001, 2002, 2003, 2005 Free Software Foundation, Inc.

   This program 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 of the
   License, or (at your option) any later version.

   This program 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 this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
   USA.  */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "../src/gcrypt-int.h"

static int verbose;

static void
die (const char *format, ...)
{
  va_list arg_ptr;

  va_start (arg_ptr, format);
  vfprintf (stderr, format, arg_ptr);
  va_end (arg_ptr);
  exit (1);
}

static void
check_primes (void)
{
  gcry_error_t err = GPG_ERR_NO_ERROR;
  gcry_mpi_t *factors = NULL;
  gcry_mpi_t prime = NULL;
  gcry_mpi_t g;
  unsigned int i = 0;
  struct prime_spec
  {
    unsigned int prime_bits;
    unsigned int factor_bits;
    unsigned int flags;
  } prime_specs[] =
    {
      { 1024, 100, GCRY_PRIME_FLAG_SPECIAL_FACTOR },
      { 128, 0, 0 },
      { 0 },
    };

  for (i = 0; prime_specs[i].prime_bits; i++)
    {
      err = gcry_prime_generate (&prime,
				 prime_specs[i].prime_bits,
				 prime_specs[i].factor_bits,
				 &factors,
				 NULL, NULL,
				 GCRY_WEAK_RANDOM,
				 prime_specs[i].flags);
      assert (! err);
      if (verbose)
        {
          fprintf (stderr, "test %d: p = ", i);
          gcry_mpi_dump (prime);
          putc ('\n', stderr);
        }

      err = gcry_prime_check (prime, 0);
      assert (! err);

      err = gcry_prime_group_generator (&g, prime, factors, NULL);
      assert (!err);
      gcry_prime_release_factors (factors); factors = NULL;

      if (verbose)
        {
          fprintf (stderr, "     %d: g = ", i);
          gcry_mpi_dump (g);
          putc ('\n', stderr);
        }
      gcry_mpi_release (g);


      gcry_mpi_add_ui (prime, prime, 1);
      err = gcry_prime_check (prime, 0);
      assert (err);
      gcry_mpi_release (prime); prime = NULL;
    }
}


/* Print an MPI S-expression.  */
static void
print_mpi (const char *name, gcry_mpi_t a)
{
  gcry_error_t err;
  unsigned char *buf;
  int writerr = 0;

  err = gcry_mpi_aprint (GCRYMPI_FMT_HEX, &buf, NULL, a);
  if (err)
    die ("gcry_mpi_aprint failed: %s\n", gcry_strerror (err));

  printf ("  (%s #%s#)\n", name, buf);
  if (ferror (stdout))
    writerr++;
  if (!writerr && fflush (stdout) == EOF)
    writerr++;
  if (writerr)
    die ("writing output failed\n");
  gcry_free (buf);
}


/* Create the key for our public standard dummy CA.  */
static void
create_42prime (void)
{
  gcry_error_t err;
  char string[128*2+1];
  int i;
  gcry_mpi_t start = NULL;
  gcry_mpi_t p, q, n, t1, t2, phi, f, g, e, d, u;


  /* Our start value is a string of 0x42 values, with the exception
     that the two high order bits are set.  This is to resemble the
     way Lingcrypt generates RSA primes.  */
  for (i=0; i < 128;)
    {
      string[i++] = '4';
      string[i++] = '2';
    }
  string[i] = 0;
  string[0] = 'C';

  err = gcry_mpi_scan (&start, GCRYMPI_FMT_HEX, string, 0, NULL);
  if (err)
    die ("gcry_mpi_scan failed: %s\n", gcry_strerror (err));
  fputs ("start:", stderr); gcry_mpi_dump (start); putc ('\n', stderr);

  /* Generate two primes with p < q.  We take the first primes below
     and above a start value. */
  p = gcry_mpi_copy (start);
  gcry_mpi_sub_ui (p, p, 1);
  while (gcry_prime_check (p, 0))
    gcry_mpi_sub_ui (p, p, 2);
  fputs ("    p:", stderr); gcry_mpi_dump (p); putc ('\n', stderr);
  q = gcry_mpi_copy (start);
  gcry_mpi_add_ui (q, q, 1);
  while (gcry_prime_check (q, 0))
    gcry_mpi_add_ui (q, q, 2);
  fputs ("    q:", stderr); gcry_mpi_dump (q); putc ('\n', stderr);

  /* Compute the modulus.  */
  n = gcry_mpi_new (1024);
  gcry_mpi_mul (n, p, q);
  fputs ("    n:", stderr); gcry_mpi_dump (n); putc ('\n', stderr);
  if (gcry_mpi_get_nbits (n) != 1024)
    die ("Oops: the size of N is not 1024 but %u\n", gcry_mpi_get_nbits (n));

  /* Calculate Euler totient: phi = (p-1)(q-1) */
  t1 = gcry_mpi_new (0);
  t2 = gcry_mpi_new (0);
  phi = gcry_mpi_new (0);
  g   = gcry_mpi_new (0);
  f   = gcry_mpi_new (0);
  gcry_mpi_sub_ui (t1, p, 1);
  gcry_mpi_sub_ui (t2, q, 1);
  gcry_mpi_mul (phi, t1, t2);
  gcry_mpi_gcd (g, t1, t2);
  gcry_mpi_div (f, NULL, phi, g, -1);

  /* Check the public exponent.  */
  e = gcry_mpi_set_ui (NULL, 65537);
  if (!gcry_mpi_gcd (t1, e, phi))
    die ("Oops: E is not a generator\n");
  fputs ("    e:", stderr); gcry_mpi_dump (e); putc ('\n', stderr);

  /* Compute the secret key:  d = e^-1 mod phi */
  d = gcry_mpi_new (0);
  gcry_mpi_invm (d, e, f );
  fputs ("    d:", stderr); gcry_mpi_dump (d); putc ('\n', stderr);

  /* Compute the inverse of p and q. */
  u = gcry_mpi_new (0);
  gcry_mpi_invm (u, p, q);
  fputs ("    u:", stderr); gcry_mpi_dump (u); putc ('\n', stderr);

  /* Print the S-expression.  */
  fputs ("(private-key\n (rsa\n", stdout);
  print_mpi ("n", n);
  print_mpi ("e", e);
  print_mpi ("d", d);
  print_mpi ("p", p);
  print_mpi ("q", q);
  print_mpi ("u", u);
  fputs ("))\n", stdout);

  gcry_mpi_release (p);
  gcry_mpi_release (q);
  gcry_mpi_release (n);
  gcry_mpi_release (t1);
  gcry_mpi_release (t2);
  gcry_mpi_release (phi);
  gcry_mpi_release (f);
  gcry_mpi_release (g);
  gcry_mpi_release (e);
  gcry_mpi_release (d);
  gcry_mpi_release (u);
}




int
main (int argc, char **argv)
{
  int debug = 0;
  int mode42 = 0;

  if ((argc > 1) && (! strcmp (argv[1], "--verbose")))
    verbose = 1;
  else if ((argc > 1) && (! strcmp (argv[1], "--debug")))
    verbose = debug = 1;
  else if ((argc > 1) && (! strcmp (argv[1], "--42")))
    verbose = debug = mode42 = 1;

  gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
  if (! gcry_check_version (GCRYPT_VERSION))
    die ("version mismatch\n");

  gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
  if (debug)
    gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);

  if (mode42)
    create_42prime ();
  else
    check_primes ();

  return 0;
}