#include <stdio.h>
#include <signal.h>
#include <sys/time.h>
#include "gmp.h"

/**********************************************************************

  program by Aggelos Keromitis <kermit@gr.forthnet>

  modified by Adam Back <aba@dcs.ex.ac.uk>
  -  changed to use bits rather than hex nibbles when specifying key sizes
  -  added option to allow choice of small public key exponents

  You need the GNU mp library for this, get gmp-1.3.2.tar.gz

**********************************************************************/

#define PUBFILE  "pubkey.rsa"
#define SECFILE "seckey.rsa"

volatile unsigned int i, counter, value;

static void handler(void);

/*
 * get_random:
 * return a random integer 0-255
 */

unsigned int
get_random(void)
{
  struct itimerval x, y;

  i = 0;
  counter = 0;
  value = 0;

  x.it_interval.tv_sec = 0;
  x.it_interval.tv_usec = 1;
  x.it_value.tv_sec = 0;
  x.it_value.tv_usec = 1;

  if (setitimer(ITIMER_REAL, &x, &y) == -1)
  {
    perror("get_random()");
    return 0;
  }

  signal(SIGALRM, handler);

  while (counter < 8)
    i++;

  signal(SIGALRM, SIG_IGN);

        if (setitimer(ITIMER_REAL, &y, (struct itimerval *) NULL) == -1)
          perror("get_random()");

  return value;
}

/*
 * handler:
 * the SIGALRM handler
 */

void
handler(void)
{
  value = (value << 1) | (i & 0x1);
  counter++;
  i = 0;
  signal(SIGALRM, handler);
}

/*
 * the key files are of the form:
 * modulus        in hex
 * key component (secret or public accordingly) also in hex
 */

main(int argc, char **argv)
{
  MP_INT p, q, phi, n;
  int i, k, bits, nibbles, encrypt_key = 0;
  char *buf, *n_buf;
  FILE *fp1, *fp2;

  if (argc < 2)
  {
    fprintf(stderr, "Usage: %s <modulus> [<public exponent>]\n", argv[0]);
    fprintf(stderr, "\tgive modulus size in bits\n");
    fprintf(stderr, "\toptionally give your choice of public exponent\n");
    exit(-1);
  }

  bits = atoi(argv[1]);
  if (bits < 32)
  {
    fprintf(stderr, "Invalid keysize.\n");
    exit(-1);
  }
  nibbles = (bits + 3)/ 4;

  i = nibbles;

  if ( argc > 2 )
  {
    encrypt_key = atoi(argv[2]);
  }
try_again:
  mpz_init_set_ui(&p, 0);        /* Get a "random" p */
  while ((i -= 2) > 0)
  {
    mpz_mul_ui(&p, &p, 16);
    mpz_add_ui(&p, &p, get_random());
  }

  while (!mpz_probab_prime_p(&p, 25))  /* Find a prime */
    mpz_add_ui(&p, &p, 1);

  fprintf(stderr, "Got one prime.\n");

  i = nibbles;

        mpz_init_set_ui(&q, 0);                         /* Get a "random" q */
        while ((i -= 2) > 0)
        {
                mpz_mul_ui(&q, &q, 16);
                mpz_add_ui(&q, &q, get_random());
        }

        while (!mpz_probab_prime_p(&q, 25))  /* Find a prime */
          mpz_add_ui(&q, &q, 1);

  fprintf(stderr, "Got second prime.\n");

  mpz_init(&n);
  mpz_mul(&n, &p, &q);      /* Calculate the RSA modulus */

  fp1 = fopen(SECFILE, "w");
  if (fp1 == (FILE *) NULL)
  {
    perror(SECFILE);
    exit(-1);
  }

  fp2 = fopen(PUBFILE, "w");
  if (fp2 == (FILE *) NULL)
  {
    perror(PUBFILE);
    exit(-1);
  }

  n_buf = mpz_get_str((char *) NULL, 16, &n);

  mpz_sub_ui(&p, &p, 1);
  mpz_sub_ui(&q, &q, 1);
  mpz_init(&phi);
  mpz_mul(&phi, &p, &q);      /* Calculate (p - 1)*(q - 1) */
  mpz_clear(&p);

  i = nibbles;

  if (encrypt_key)
  {          /* user chosen */ 
    mpz_init_set_ui(&p,encrypt_key);/* small public exponent */
  }
  else
  {
    mpz_init_set_ui(&p, 0);    /* Get a "random" secret */
          while ((i--) > 0)
          {
                  mpz_mul_ui(&p, &p, 16);
                  mpz_add_ui(&p, &p, get_random());
          }

          while (mpz_cmp(&p, &n) >= 0)  /* Chop it if larger than n */
      mpz_div_ui(&p, &p, 2);

    do
    {
      mpz_add_ui(&p, &p, 1);
      mpz_gcd(&q, &p, &phi);    /* Get the GCD */
    } while (mpz_cmp_ui(&q, 1) && mpz_cmp(&q,&phi)<=0);    /* until it is 1 */
  }
  buf = mpz_get_str((char *) NULL, 16, &p);
  mpz_gcdext(&p, &q, &p, &p, &phi);

  if ( !mpz_cmp_ui(&q,1) || mpz_cmp(&q,&phi) >= 0)
  {
    fprintf( stderr, "failed to find d, starting again\n" );
    goto try_again;
  }
  
  fprintf(fp2, "e = %s\n", buf);
  free(buf);

  mpz_clear(&p);

  if (mpz_cmp_ui(&q, 0) < 0)    /* If negative, add modulus */
    mpz_add(&q, &q, &phi);

  mpz_clear(&phi);

  buf = mpz_get_str((char *) NULL, 16, &q);
  fprintf(fp1, "d = %s\n", buf);
  free(buf);

  fprintf(fp1, "n = %s\n", n_buf);
  fprintf(fp2, "n = %s\n", n_buf);

  fclose(fp1);
  fclose(fp2);

  mpz_clear(&q);
  fprintf(stderr, "written public key to \"%s\"\n", PUBFILE);
  fprintf(stderr, "written secret key to \"%s\"\n", SECFILE);
  exit(0);
}