lib/silccrypt/rsa.c

   1 /*
   2
   3   rsa.c         RSA Public and Private key generation functions,
   4                 RSA encrypt and decrypt functions.
   5
   6   Author: Pekka Riikonen <priikone@silcnet.org>
   7
   8   Copyright (C) 1997 - 2008 Pekka Riikonen
   9
  10   This program is free software; you can redistribute it and/or modify
  11   it under the terms of the GNU General Public License as published by
  12   the Free Software Foundation; version 2 of the License.
  13
  14   This program is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19   Created: Sat Mar  1 13:26:45 1997 pekka
  20
  21   RSA public key cryptographic algorithm used in this distribution is:
  22
  23         Key generation:
  24         p, q            primes
  25         p != q
  26         n = p * q       modulus
  27
  28         Public key exponent:
  29         e   relatively prime to (p-1) * (q-1)
  30         Private key exponent:
  31         d = e ^ -1 mod lcm(((p-1) * (q-1)))
  32
  33         Encryption:
  34         c = m ^ e mod n
  35         Decryption:
  36         m = c ^ d mod n
  37
  38   Supports CRT (Chinese Remainder Theorem) for private key operations.
  39
  40   The SSH's (Secure Shell), PGP's (Pretty Good Privacy) and RSAREF
  41   Toolkit were used as reference when coding this implementation. They
  42   all were a big help for me.
  43
  44   I also suggest reading Bruce Schneier's; Applied Cryptography, Second
  45   Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and
  46   everything else too about cryptography.
  47
  48 */
  49
  50 /*
  51    ChangeLog
  52
  53    o Mon Feb 12 11:20:32 EET 2001  Pekka
  54
  55      Changed RSA private exponent generation to what PKCS #1 suggests.  We
  56      try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
  57      of modinv(e, phi).  Note: this is not security fix but optimization.
  58
  59    o Tue Feb 20 13:58:58 EET 2001  Pekka
  60
  61      Set key->bits in rsa_generate_key.  It is the modulus length in bits.
  62      The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
  63      is now calculated by (key->bits + 7) / 8.  It is the length of one block.
  64
  65    o Sat Mar 16 18:27:19 EET 2002  Pekka
  66
  67      Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime
  68      generation.
  69
  70    o Sat Sep 26 19:59:48 EEST 2002  Pekka
  71
  72      Fixed double free in public key setting.  Use a bit larger e as
  73      starting point in key generation.
  74 */
  75
  76 #include "silccrypto.h"
  77 #include "rsa.h"
  78
  79 /* Generates RSA public and private keys. Primes p and q that are used
  80    to compute the modulus n has to be generated before calling this. They
  81    are then sent as argument for the function. */
  82
  83 SilcBool silc_rsa_generate_keys(SilcUInt32 bits, SilcMPInt *p, SilcMPInt *q,
  84                                 void **ret_public_key, void **ret_private_key)
  85 {
  86   RsaPublicKey *pubkey;
  87   RsaPrivateKey *privkey;
  88   SilcMPInt phi, hlp;
  89   SilcMPInt div, lcm;
  90   SilcMPInt pm1, qm1;
  91
  92   *ret_public_key = pubkey = silc_calloc(1, sizeof(*pubkey));
  93   if (!pubkey)
  94     return FALSE;
  95
  96   *ret_private_key = privkey = silc_calloc(1, sizeof(*privkey));
  97   if (!privkey)
  98     return FALSE;
  99
 100   /* Default hash shall be sha1 */
 101   silc_hash_alloc("sha1", &pubkey->hash);
 102   silc_hash_alloc("sha1", &privkey->hash);
 103
 104   /* Initialize variables */
 105   silc_mp_init(&privkey->n);
 106   silc_mp_init(&privkey->e);
 107   silc_mp_init(&privkey->d);
 108   silc_mp_init(&privkey->dP);
 109   silc_mp_init(&privkey->dQ);
 110   silc_mp_init(&privkey->qP);
 111   silc_mp_init(&phi);
 112   silc_mp_init(&hlp);
 113   silc_mp_init(&div);
 114   silc_mp_init(&lcm);
 115   silc_mp_init(&pm1);
 116   silc_mp_init(&qm1);
 117
 118   /* Set modulus length */
 119   privkey->bits = bits;
 120
 121   /* Compute modulus, n = p * q */
 122   silc_mp_mul(&privkey->n, p, q);
 123
 124   /* phi = (p - 1) * (q - 1) */
 125   silc_mp_sub_ui(&pm1, p, 1);
 126   silc_mp_sub_ui(&qm1, q, 1);
 127   silc_mp_mul(&phi, &pm1, &qm1);
 128
 129   /* Set e, the public exponent. We try to use same public exponent
 130      for all keys. Also, to make encryption faster we use small
 131      number. */
 132   silc_mp_set_ui(&privkey->e, 65533);
 133  retry_e:
 134   /* See if e is relatively prime to phi. gcd == greates common divisor,
 135      if gcd equals 1 they are relatively prime. */
 136   silc_mp_gcd(&hlp, &privkey->e, &phi);
 137   if ((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 138     silc_mp_add_ui(&privkey->e, &privkey->e, 2);
 139     goto retry_e;
 140   }
 141
 142   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 143   silc_mp_gcd(&div, &pm1, &qm1);
 144   silc_mp_div(&lcm, &phi, &div);
 145   silc_mp_modinv(&privkey->d, &privkey->e, &lcm);
 146
 147   /* Optimize d with CRT. */
 148   silc_mp_mod(&privkey->dP, &privkey->d, &pm1);
 149   silc_mp_mod(&privkey->dQ, &privkey->d, &qm1);
 150   silc_mp_modinv(&privkey->qP, q, p);
 151   silc_mp_set(&privkey->p, p);
 152   silc_mp_set(&privkey->q, q);
 153
 154   silc_mp_uninit(&phi);
 155   silc_mp_uninit(&hlp);
 156   silc_mp_uninit(&div);
 157   silc_mp_uninit(&lcm);
 158   silc_mp_uninit(&pm1);
 159   silc_mp_uninit(&qm1);
 160
 161   /* Set public key */
 162   silc_mp_init(&pubkey->n);
 163   silc_mp_init(&pubkey->e);
 164   pubkey->bits = privkey->bits;
 165   silc_mp_set(&pubkey->n, &privkey->n);
 166   silc_mp_set(&pubkey->e, &privkey->e);
 167
 168   return TRUE;
 169 }
 170
 171 /* RSA public key operation */
 172
 173 SilcBool silc_rsa_public_operation(RsaPublicKey *key, SilcMPInt *src,
 174                                    SilcMPInt *dst)
 175 {
 176   /* dst = src ^ e mod n */
 177   silc_mp_pow_mod(dst, src, &key->e, &key->n);
 178   return TRUE;
 179 }
 180
 181 /* RSA private key operation */
 182
 183 SilcBool silc_rsa_private_operation(RsaPrivateKey *key, SilcMPInt *src,
 184                                     SilcMPInt *dst)
 185 {
 186   SilcMPInt tmp;
 187
 188   silc_mp_init(&tmp);
 189
 190   /* dst = (src ^ dP mod p) */
 191   silc_mp_pow_mod(dst, src, &key->dP, &key->p);
 192
 193   /* tmp = (src ^ dQ mod q) */
 194   silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q);
 195
 196   /* dst = (dst - tmp) * qP mod p */
 197   silc_mp_sub(dst, dst, &tmp);
 198   silc_mp_mul(dst, dst, &key->qP);
 199   silc_mp_mod(dst, dst, &key->p);
 200
 201   /* dst = (q * dst) + tmp */
 202   silc_mp_mul(dst, dst, &key->q);
 203   silc_mp_add(dst, dst, &tmp);
 204
 205   silc_mp_uninit(&tmp);
 206
 207   return TRUE;
 208 }