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 - 2006 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 /* $Id$ */
  50
  51 /*
  52    ChangeLog
  53
  54    o Mon Feb 12 11:20:32 EET 2001  Pekka
  55
  56      Changed RSA private exponent generation to what PKCS #1 suggests.  We
  57      try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
  58      of modinv(e, phi).  Note: this is not security fix but optimization.
  59
  60    o Tue Feb 20 13:58:58 EET 2001  Pekka
  61
  62      Set key->bits in rsa_generate_key.  It is the modulus length in bits.
  63      The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
  64      is now calculated by (key->bits + 7) / 8.  It is the length of one block.
  65
  66    o Sat Mar 16 18:27:19 EET 2002  Pekka
  67
  68      Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime
  69      generation.
  70
  71    o Sat Sep 26 19:59:48 EEST 2002  Pekka
  72
  73      Fixed double free in public key setting.  Use a bit larger e as
  74      starting point in key generation.
  75
  76    o Fri Dec 30 13:39:51 EET 2005 Pekka
  77
  78      Support PKCS #1 format public and private keys.  Support for new
  79      PKCS API.
  80 */
  81
  82 #include "silc.h"
  83 #include "rsa.h"
  84
  85 /* Generates RSA public and private keys. Primes p and q that are used
  86    to compute the modulus n has to be generated before calling this. They
  87    are then sent as argument for the function. */
  88
  89 SilcBool rsa_generate_keys(SilcUInt32 bits, SilcMPInt *p, SilcMPInt *q,
  90                            void **ret_public_key, void **ret_private_key)
  91 {
  92   RsaPublicKey *pubkey;
  93   RsaPrivateKey *privkey;
  94   SilcMPInt phi, hlp;
  95   SilcMPInt div, lcm;
  96   SilcMPInt pm1, qm1;
  97
  98   *ret_public_key = pubkey = silc_calloc(1, sizeof(*pubkey));
  99   if (!pubkey)
 100     return FALSE;
 101
 102   *ret_private_key = privkey = silc_calloc(1, sizeof(*privkey));
 103   if (!privkey)
 104     return FALSE;
 105
 106   /* Initialize variables */
 107   silc_mp_init(&privkey->n);
 108   silc_mp_init(&privkey->e);
 109   silc_mp_init(&privkey->d);
 110   silc_mp_init(&privkey->dP);
 111   silc_mp_init(&privkey->dQ);
 112   silc_mp_init(&privkey->qP);
 113   silc_mp_init(&phi);
 114   silc_mp_init(&hlp);
 115   silc_mp_init(&div);
 116   silc_mp_init(&lcm);
 117   silc_mp_init(&pm1);
 118   silc_mp_init(&qm1);
 119
 120   /* Set modulus length */
 121   privkey->bits = bits;
 122
 123   /* Compute modulus, n = p * q */
 124   silc_mp_mul(&privkey->n, p, q);
 125
 126   /* phi = (p - 1) * (q - 1) */
 127   silc_mp_sub_ui(&pm1, p, 1);
 128   silc_mp_sub_ui(&qm1, q, 1);
 129   silc_mp_mul(&phi, &pm1, &qm1);
 130
 131   /* Set e, the public exponent. We try to use same public exponent
 132      for all keys. Also, to make encryption faster we use small
 133      number. */
 134   silc_mp_set_ui(&privkey->e, 65533);
 135  retry_e:
 136   /* See if e is relatively prime to phi. gcd == greates common divisor,
 137      if gcd equals 1 they are relatively prime. */
 138   silc_mp_gcd(&hlp, &privkey->e, &phi);
 139   if ((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 140     silc_mp_add_ui(&privkey->e, &privkey->e, 2);
 141     goto retry_e;
 142   }
 143
 144   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 145   silc_mp_gcd(&div, &pm1, &qm1);
 146   silc_mp_div(&lcm, &phi, &div);
 147   silc_mp_modinv(&privkey->d, &privkey->e, &lcm);
 148
 149   /* Optimize d with CRT. */
 150   silc_mp_mod(&privkey->dP, &privkey->d, &pm1);
 151   silc_mp_mod(&privkey->dQ, &privkey->d, &qm1);
 152   silc_mp_modinv(&privkey->qP, q, p);
 153   silc_mp_set(&privkey->p, p);
 154   silc_mp_set(&privkey->q, q);
 155
 156   silc_mp_uninit(&phi);
 157   silc_mp_uninit(&hlp);
 158   silc_mp_uninit(&div);
 159   silc_mp_uninit(&lcm);
 160   silc_mp_uninit(&pm1);
 161   silc_mp_uninit(&qm1);
 162
 163   /* Set public key */
 164   silc_mp_init(&pubkey->n);
 165   silc_mp_init(&pubkey->e);
 166   pubkey->bits = privkey->bits;
 167   silc_mp_set(&pubkey->n, &privkey->n);
 168   silc_mp_set(&pubkey->e, &privkey->e);
 169
 170   return TRUE;
 171 }
 172
 173 /* RSA public key operation */
 174
 175 SilcBool rsa_public_operation(RsaPublicKey *key, SilcMPInt *src,
 176                               SilcMPInt *dst)
 177 {
 178   /* dst = src ^ e mod n */
 179   silc_mp_pow_mod(dst, src, &key->e, &key->n);
 180   return TRUE;
 181 }
 182
 183 /* RSA private key operation */
 184
 185 SilcBool rsa_private_operation(RsaPrivateKey *key, SilcMPInt *src,
 186                                SilcMPInt *dst)
 187 {
 188   SilcMPInt tmp;
 189
 190   silc_mp_init(&tmp);
 191
 192   /* dst = (src ^ dP mod p) */
 193   silc_mp_pow_mod(dst, src, &key->dP, &key->p);
 194
 195   /* tmp = (src ^ dQ mod q) */
 196   silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q);
 197
 198   /* dst = (dst - tmp) * qP mod p */
 199   silc_mp_sub(dst, dst, &tmp);
 200   silc_mp_mul(dst, dst, &key->qP);
 201   silc_mp_mod(dst, dst, &key->p);
 202
 203   /* dst = (q * dst) + tmp */
 204   silc_mp_mul(dst, dst, &key->q);
 205   silc_mp_add(dst, dst, &tmp);
 206
 207   silc_mp_uninit(&tmp);
 208
 209   return TRUE;
 210 }