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 - 2007 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
  77 #include "silc.h"
  78 #include "rsa.h"
  79
  80 /* Generates RSA public and private keys. Primes p and q that are used
  81    to compute the modulus n has to be generated before calling this. They
  82    are then sent as argument for the function. */
  83
  84 SilcBool silc_rsa_generate_keys(SilcUInt32 bits, SilcMPInt *p, SilcMPInt *q,
  85                                 void **ret_public_key, void **ret_private_key)
  86 {
  87   RsaPublicKey *pubkey;
  88   RsaPrivateKey *privkey;
  89   SilcMPInt phi, hlp;
  90   SilcMPInt div, lcm;
  91   SilcMPInt pm1, qm1;
  92
  93   *ret_public_key = pubkey = silc_calloc(1, sizeof(*pubkey));
  94   if (!pubkey)
  95     return FALSE;
  96
  97   *ret_private_key = privkey = silc_calloc(1, sizeof(*privkey));
  98   if (!privkey)
  99     return FALSE;
 100
 101   /* Initialize variables */
 102   silc_mp_init(&privkey->n);
 103   silc_mp_init(&privkey->e);
 104   silc_mp_init(&privkey->d);
 105   silc_mp_init(&privkey->dP);
 106   silc_mp_init(&privkey->dQ);
 107   silc_mp_init(&privkey->qP);
 108   silc_mp_init(&phi);
 109   silc_mp_init(&hlp);
 110   silc_mp_init(&div);
 111   silc_mp_init(&lcm);
 112   silc_mp_init(&pm1);
 113   silc_mp_init(&qm1);
 114
 115   /* Set modulus length */
 116   privkey->bits = bits;
 117
 118   /* Compute modulus, n = p * q */
 119   silc_mp_mul(&privkey->n, p, q);
 120
 121   /* phi = (p - 1) * (q - 1) */
 122   silc_mp_sub_ui(&pm1, p, 1);
 123   silc_mp_sub_ui(&qm1, q, 1);
 124   silc_mp_mul(&phi, &pm1, &qm1);
 125
 126   /* Set e, the public exponent. We try to use same public exponent
 127      for all keys. Also, to make encryption faster we use small
 128      number. */
 129   silc_mp_set_ui(&privkey->e, 65533);
 130  retry_e:
 131   /* See if e is relatively prime to phi. gcd == greates common divisor,
 132      if gcd equals 1 they are relatively prime. */
 133   silc_mp_gcd(&hlp, &privkey->e, &phi);
 134   if ((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 135     silc_mp_add_ui(&privkey->e, &privkey->e, 2);
 136     goto retry_e;
 137   }
 138
 139   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 140   silc_mp_gcd(&div, &pm1, &qm1);
 141   silc_mp_div(&lcm, &phi, &div);
 142   silc_mp_modinv(&privkey->d, &privkey->e, &lcm);
 143
 144   /* Optimize d with CRT. */
 145   silc_mp_mod(&privkey->dP, &privkey->d, &pm1);
 146   silc_mp_mod(&privkey->dQ, &privkey->d, &qm1);
 147   silc_mp_modinv(&privkey->qP, q, p);
 148   silc_mp_set(&privkey->p, p);
 149   silc_mp_set(&privkey->q, q);
 150
 151   silc_mp_uninit(&phi);
 152   silc_mp_uninit(&hlp);
 153   silc_mp_uninit(&div);
 154   silc_mp_uninit(&lcm);
 155   silc_mp_uninit(&pm1);
 156   silc_mp_uninit(&qm1);
 157
 158   /* Set public key */
 159   silc_mp_init(&pubkey->n);
 160   silc_mp_init(&pubkey->e);
 161   pubkey->bits = privkey->bits;
 162   silc_mp_set(&pubkey->n, &privkey->n);
 163   silc_mp_set(&pubkey->e, &privkey->e);
 164
 165   return TRUE;
 166 }
 167
 168 /* RSA public key operation */
 169
 170 SilcBool silc_rsa_public_operation(RsaPublicKey *key, SilcMPInt *src,
 171                                    SilcMPInt *dst)
 172 {
 173   /* dst = src ^ e mod n */
 174   silc_mp_pow_mod(dst, src, &key->e, &key->n);
 175   return TRUE;
 176 }
 177
 178 /* RSA private key operation */
 179
 180 SilcBool silc_rsa_private_operation(RsaPrivateKey *key, SilcMPInt *src,
 181                                     SilcMPInt *dst)
 182 {
 183   SilcMPInt tmp;
 184
 185   silc_mp_init(&tmp);
 186
 187   /* dst = (src ^ dP mod p) */
 188   silc_mp_pow_mod(dst, src, &key->dP, &key->p);
 189
 190   /* tmp = (src ^ dQ mod q) */
 191   silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q);
 192
 193   /* dst = (dst - tmp) * qP mod p */
 194   silc_mp_sub(dst, dst, &tmp);
 195   silc_mp_mul(dst, dst, &key->qP);
 196   silc_mp_mod(dst, dst, &key->p);
 197
 198   /* dst = (q * dst) + tmp */
 199   silc_mp_mul(dst, dst, &key->q);
 200   silc_mp_add(dst, dst, &tmp);
 201
 202   silc_mp_uninit(&tmp);
 203
 204   return TRUE;
 205 }