libs/libtomcrypt/pk/rsa/rsa_make_key.c

   1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
   2  *
   3  * LibTomCrypt is a library that provides various cryptographic
   4  * algorithms in a highly modular and flexible manner.
   5  *
   6  * The library is free for all purposes without any express
   7  * guarantee it works.
   8  *
   9  * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com
  10  */
  11 #include "tomcrypt.h"
  12
  13 /**
  14   @file rsa_make_key.c
  15   RSA key generation, Tom St Denis
  16 */
  17
  18 #ifdef MRSA
  19
  20 /**
  21    Create an RSA key
  22    @param prng     An active PRNG state
  23    @param wprng    The index of the PRNG desired
  24    @param size     The size of the modulus (key size) desired (octets)
  25    @param e        The "e" value (public key).  e==65537 is a good choice
  26    @param key      [out] Destination of a newly created private key pair
  27    @return CRYPT_OK if successful, upon error all allocated ram is freed
  28 */
  29 int rsa_make_key(prng_state *prng, int wprng, int size, long e, rsa_key *key)
  30 {
  31    void *p, *q, *tmp1, *tmp2, *tmp3;
  32    int    err;
  33
  34    LTC_ARGCHK(ltc_mp.name != NULL);
  35    LTC_ARGCHK(key         != NULL);
  36
  37    if ((size < (MIN_RSA_SIZE/8)) || (size > (MAX_RSA_SIZE/8))) {
  38       return CRYPT_INVALID_KEYSIZE;
  39    }
  40
  41    if ((e < 3) || ((e & 1) == 0)) {
  42       return CRYPT_INVALID_ARG;
  43    }
  44
  45    if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
  46       return err;
  47    }
  48
  49    if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != CRYPT_OK) {
  50       return err;
  51    }
  52
  53    /* make primes p and q (optimization provided by Wayne Scott) */
  54    if ((err = mp_set_int(tmp3, e)) != CRYPT_OK)                      { goto errkey; }  /* tmp3 = e */
  55
  56    /* make prime "p" */
  57    do {
  58        if ((err = rand_prime( p, size/2, prng, wprng)) != CRYPT_OK)  { goto errkey; }
  59        if ((err = mp_sub_d( p, 1,  tmp1)) != CRYPT_OK)               { goto errkey; }  /* tmp1 = p-1 */
  60        if ((err = mp_gcd( tmp1,  tmp3,  tmp2)) != CRYPT_OK)          { goto errkey; }  /* tmp2 = gcd(p-1, e) */
  61    } while (mp_cmp_d( tmp2, 1) != 0);                                                  /* while e divides p-1 */
  62
  63    /* make prime "q" */
  64    do {
  65        if ((err = rand_prime( q, size/2, prng, wprng)) != CRYPT_OK)  { goto errkey; }
  66        if ((err = mp_sub_d( q, 1,  tmp1)) != CRYPT_OK)               { goto errkey; } /* tmp1 = q-1 */
  67        if ((err = mp_gcd( tmp1,  tmp3,  tmp2)) != CRYPT_OK)          { goto errkey; } /* tmp2 = gcd(q-1, e) */
  68    } while (mp_cmp_d( tmp2, 1) != 0);                                                 /* while e divides q-1 */
  69
  70    /* tmp1 = lcm(p-1, q-1) */
  71    if ((err = mp_sub_d( p, 1,  tmp2)) != CRYPT_OK)                   { goto errkey; } /* tmp2 = p-1 */
  72                                                                                       /* tmp1 = q-1 (previous do/while loop) */
  73    if ((err = mp_lcm( tmp1,  tmp2,  tmp1)) != CRYPT_OK)              { goto errkey; } /* tmp1 = lcm(p-1, q-1) */
  74
  75    /* make key */
  76    if ((err = mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP, &key->qP, &key->p, &key->q, NULL)) != CRYPT_OK) {
  77       goto errkey;
  78    }
  79
  80    if ((err = mp_set_int( key->e, e)) != CRYPT_OK)                     { goto errkey; } /* key->e =  e */
  81    if ((err = mp_invmod( key->e,  tmp1,  key->d)) != CRYPT_OK)         { goto errkey; } /* key->d = 1/e mod lcm(p-1,q-1) */
  82    if ((err = mp_mul( p,  q,  key->N)) != CRYPT_OK)                    { goto errkey; } /* key->N = pq */
  83
  84    /* optimize for CRT now */
  85    /* find d mod q-1 and d mod p-1 */
  86    if ((err = mp_sub_d( p, 1,  tmp1)) != CRYPT_OK)                     { goto errkey; } /* tmp1 = q-1 */
  87    if ((err = mp_sub_d( q, 1,  tmp2)) != CRYPT_OK)                     { goto errkey; } /* tmp2 = p-1 */
  88    if ((err = mp_mod( key->d,  tmp1,  key->dP)) != CRYPT_OK)           { goto errkey; } /* dP = d mod p-1 */
  89    if ((err = mp_mod( key->d,  tmp2,  key->dQ)) != CRYPT_OK)           { goto errkey; } /* dQ = d mod q-1 */
  90    if ((err = mp_invmod( q,  p,  key->qP)) != CRYPT_OK)                { goto errkey; } /* qP = 1/q mod p */
  91
  92    if ((err = mp_copy( p,  key->p)) != CRYPT_OK)                       { goto errkey; }
  93    if ((err = mp_copy( q,  key->q)) != CRYPT_OK)                       { goto errkey; }
  94
  95    /* set key type (in this case it's CRT optimized) */
  96    key->type = PK_PRIVATE;
  97
  98    /* return ok and free temps */
  99    err       = CRYPT_OK;
 100    goto cleanup;
 101 errkey:
 102    mp_clear_multi(key->d, key->e, key->N, key->dQ, key->dP, key->qP, key->p, key->q, NULL);
 103 cleanup:
 104    mp_clear_multi(tmp3, tmp2, tmp1, p, q, NULL);
 105    return err;
 106 }
 107
 108 #endif
 109
 110 /* $Source: /cvs/libtom/libtomcrypt/src/pk/rsa/rsa_make_key.c,v $ */
 111 /* $Revision: 1.14 $ */
 112 /* $Date: 2006/12/04 22:23:27 $ */