pd.if.org Git - zpackage/blob - libtomcrypt/src/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 #include "tomcrypt.h"
  10
  11 /**
  12   @file rsa_make_key.c
  13   RSA key generation, Tom St Denis
  14 */
  15
  16 #ifdef LTC_MRSA
  17
  18 /**
  19    Create an RSA key
  20    @param prng     An active PRNG state
  21    @param wprng    The index of the PRNG desired
  22    @param size     The size of the modulus (key size) desired (octets)
  23    @param e        The "e" value (public key).  e==65537 is a good choice
  24    @param key      [out] Destination of a newly created private key pair
  25    @return CRYPT_OK if successful, upon error all allocated ram is freed
  26 */
  27 int rsa_make_key(prng_state *prng, int wprng, int size, long e, rsa_key *key)
  28 {
  29    void *p, *q, *tmp1, *tmp2, *tmp3;
  30    int    err;
  31
  32    LTC_ARGCHK(ltc_mp.name != NULL);
  33    LTC_ARGCHK(key         != NULL);
  34    LTC_ARGCHK(size        > 0);
  35
  36    if ((e < 3) || ((e & 1) == 0)) {
  37       return CRYPT_INVALID_ARG;
  38    }
  39
  40    if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
  41       return err;
  42    }
  43
  44    if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != CRYPT_OK) {
  45       return err;
  46    }
  47
  48    /* make primes p and q (optimization provided by Wayne Scott) */
  49    if ((err = mp_set_int(tmp3, e)) != CRYPT_OK)                      { goto cleanup; }  /* tmp3 = e */
  50
  51    /* make prime "p" */
  52    do {
  53        if ((err = rand_prime( p, size/2, prng, wprng)) != CRYPT_OK)  { goto cleanup; }
  54        if ((err = mp_sub_d( p, 1,  tmp1)) != CRYPT_OK)               { goto cleanup; }  /* tmp1 = p-1 */
  55        if ((err = mp_gcd( tmp1,  tmp3,  tmp2)) != CRYPT_OK)          { goto cleanup; }  /* tmp2 = gcd(p-1, e) */
  56    } while (mp_cmp_d( tmp2, 1) != 0);                                                  /* while e divides p-1 */
  57
  58    /* make prime "q" */
  59    do {
  60        if ((err = rand_prime( q, size/2, prng, wprng)) != CRYPT_OK)  { goto cleanup; }
  61        if ((err = mp_sub_d( q, 1,  tmp1)) != CRYPT_OK)               { goto cleanup; } /* tmp1 = q-1 */
  62        if ((err = mp_gcd( tmp1,  tmp3,  tmp2)) != CRYPT_OK)          { goto cleanup; } /* tmp2 = gcd(q-1, e) */
  63    } while (mp_cmp_d( tmp2, 1) != 0);                                                 /* while e divides q-1 */
  64
  65    /* tmp1 = lcm(p-1, q-1) */
  66    if ((err = mp_sub_d( p, 1,  tmp2)) != CRYPT_OK)                   { goto cleanup; } /* tmp2 = p-1 */
  67                                                                                       /* tmp1 = q-1 (previous do/while loop) */
  68    if ((err = mp_lcm( tmp1,  tmp2,  tmp1)) != CRYPT_OK)              { goto cleanup; } /* tmp1 = lcm(p-1, q-1) */
  69
  70    /* make key */
  71    if ((err = mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP, &key->qP, &key->p, &key->q, NULL)) != CRYPT_OK) {
  72       goto errkey;
  73    }
  74
  75    if ((err = mp_set_int( key->e, e)) != CRYPT_OK)                     { goto errkey; } /* key->e =  e */
  76    if ((err = mp_invmod( key->e,  tmp1,  key->d)) != CRYPT_OK)         { goto errkey; } /* key->d = 1/e mod lcm(p-1,q-1) */
  77    if ((err = mp_mul( p,  q,  key->N)) != CRYPT_OK)                    { goto errkey; } /* key->N = pq */
  78
  79    /* optimize for CRT now */
  80    /* find d mod q-1 and d mod p-1 */
  81    if ((err = mp_sub_d( p, 1,  tmp1)) != CRYPT_OK)                     { goto errkey; } /* tmp1 = q-1 */
  82    if ((err = mp_sub_d( q, 1,  tmp2)) != CRYPT_OK)                     { goto errkey; } /* tmp2 = p-1 */
  83    if ((err = mp_mod( key->d,  tmp1,  key->dP)) != CRYPT_OK)           { goto errkey; } /* dP = d mod p-1 */
  84    if ((err = mp_mod( key->d,  tmp2,  key->dQ)) != CRYPT_OK)           { goto errkey; } /* dQ = d mod q-1 */
  85    if ((err = mp_invmod( q,  p,  key->qP)) != CRYPT_OK)                { goto errkey; } /* qP = 1/q mod p */
  86
  87    if ((err = mp_copy( p,  key->p)) != CRYPT_OK)                       { goto errkey; }
  88    if ((err = mp_copy( q,  key->q)) != CRYPT_OK)                       { goto errkey; }
  89
  90    /* set key type (in this case it's CRT optimized) */
  91    key->type = PK_PRIVATE;
  92
  93    /* return ok and free temps */
  94    err       = CRYPT_OK;
  95    goto cleanup;
  96 errkey:
  97    rsa_free(key);
  98 cleanup:
  99    mp_clear_multi(tmp3, tmp2, tmp1, q, p, NULL);
 100    return err;
 101 }
 102
 103 #endif
 104
 105 /* ref:         $Format:%D$ */
 106 /* git commit:  $Format:%H$ */
 107 /* commit time: $Format:%ai$ */