lib/silccrypt/rsa.c

   1 /*
   2  * rsa.c        RSA Public and Private key generation functions,
   3  *              RSA encrypt and decrypt functions.
   4  *
   5  * Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
   6  *
   7  * Copyright (C) 1997 - 2001 Pekka Riikonen
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  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  * The SSH's (Secure Shell), PGP's (Pretty Good Privacy) and RSAREF
  39  * Toolkit were used as reference when coding this implementation. They
  40  * all were a big help for me.
  41  *
  42  * I also suggest reading Bruce Schneier's; Applied Cryptography, Second
  43  * Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and
  44  * everything else too about cryptography.
  45  *
  46  */
  47 /* $Id$ */
  48
  49 /*
  50    ChangeLog
  51
  52    o Mon Feb 12 11:20:32 EET 2001  Pekka
  53
  54      Changed RSA private exponent generation to what PKCS #1 suggests.  We
  55      try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
  56      of modinv(e, phi).  Note: this is not security fix but optimization.
  57
  58    o Tue Feb 20 13:58:58 EET 2001  Pekka
  59
  60      Set key->bits in rsa_generate_key.  It is the modulus length in bits.
  61      The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
  62      is now calculated by (key->bits + 7) / 8.  It is the length of one block.
  63
  64    o Sat Mar 16 18:27:19 EET 2002  Pekka
  65
  66      Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime
  67      generation.
  68
  69    o Sat Sep 26 19:59:48 EEST 2002  Pekka
  70
  71      Fixed double free in public key setting.  Use a bit larger e as
  72      starting point in key generation.
  73
  74 */
  75
  76 #include "silcincludes.h"
  77 #include "rsa_internal.h"
  78 #include "rsa.h"
  79
  80 /*
  81  * SILC PKCS API for RSA
  82  */
  83
  84 /* Generates RSA key pair. */
  85
  86 SILC_PKCS_API_INIT(rsa)
  87 {
  88   SilcUInt32 prime_bits = keylen / 2;
  89   SilcMPInt p, q;
  90   bool found = FALSE;
  91
  92   printf("Generating RSA Public and Private keys, might take a while...\n");
  93
  94   silc_mp_init(&p);
  95   silc_mp_init(&q);
  96
  97   /* Find p and q */
  98   while (!found) {
  99     printf("Finding p: ");
 100     silc_math_gen_prime(&p, prime_bits, TRUE, rng);
 101
 102     printf("\nFinding q: ");
 103     silc_math_gen_prime(&q, prime_bits, TRUE, rng);
 104
 105     if ((silc_mp_cmp(&p, &q)) == 0)
 106       printf("\nFound equal primes, not good, retrying...\n");
 107     else
 108       found = TRUE;
 109   }
 110
 111   /* If p is smaller than q, switch them */
 112   if ((silc_mp_cmp(&p, &q)) > 0) {
 113     SilcMPInt hlp;
 114     silc_mp_init(&hlp);
 115
 116     silc_mp_set(&hlp, &p);
 117     silc_mp_set(&p, &q);
 118     silc_mp_set(&q, &hlp);
 119
 120     silc_mp_uninit(&hlp);
 121   }
 122
 123   /* Generate the actual keys */
 124   rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
 125
 126   silc_mp_uninit(&p);
 127   silc_mp_uninit(&q);
 128
 129   printf("\nKeys generated successfully.\n");
 130
 131   return TRUE;
 132 }
 133
 134 SILC_PKCS_API_CLEAR_KEYS(rsa)
 135 {
 136   rsa_clear_keys((RsaKey *)context);
 137 }
 138
 139 /* Returns SILC style encoded RSA public key. */
 140
 141 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
 142 {
 143   RsaKey *key = (RsaKey *)context;
 144   unsigned char *e, *n, *ret;
 145   SilcUInt32 e_len, n_len;
 146   unsigned char tmp[4];
 147
 148   e = silc_mp_mp2bin(&key->e, 0, &e_len);
 149   n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len);
 150
 151   *ret_len = e_len + 4 + n_len + 4;
 152   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 153
 154   /* Put the length of the e. */
 155   SILC_PUT32_MSB(e_len, tmp);
 156   memcpy(ret, tmp, 4);
 157
 158   /* Put the e. */
 159   memcpy(ret + 4, e, e_len);
 160
 161   /* Put the length of the n. */
 162   SILC_PUT32_MSB(n_len, tmp);
 163   memcpy(ret + 4 + e_len, tmp, 4);
 164
 165   /* Put the n. */
 166   memcpy(ret + 4 + e_len + 4, n, n_len);
 167
 168   memset(e, 0, e_len);
 169   memset(n, 0, n_len);
 170   silc_free(e);
 171   silc_free(n);
 172
 173   return ret;
 174 }
 175
 176 /* Returns SILC style encoded RSA private key. Public key is always
 177    returned in private key as well. Public keys are often derived
 178    directly from private key. */
 179
 180 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
 181 {
 182   RsaKey *key = (RsaKey *)context;
 183   unsigned char *e, *n, *d, *ret;
 184   SilcUInt32 e_len, n_len, d_len;
 185   unsigned char tmp[4];
 186
 187   e = silc_mp_mp2bin(&key->e, 0, &e_len);
 188   n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len);
 189   d = silc_mp_mp2bin(&key->d, 0, &d_len);
 190
 191   *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
 192   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 193
 194   /* Put the length of the e. */
 195   SILC_PUT32_MSB(e_len, tmp);
 196   memcpy(ret, tmp, 4);
 197
 198   /* Put the e. */
 199   memcpy(ret + 4, e, e_len);
 200
 201   /* Put the length of the n. */
 202   SILC_PUT32_MSB(n_len, tmp);
 203   memcpy(ret + 4 + e_len, tmp, 4);
 204
 205   /* Put the n. */
 206   memcpy(ret + 4 + e_len + 4, n, n_len);
 207
 208   /* Put the length of the d. */
 209   SILC_PUT32_MSB(d_len, tmp);
 210   memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
 211
 212   /* Put the n. */
 213   memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
 214
 215   memset(e, 0, e_len);
 216   memset(n, 0, n_len);
 217   memset(d, 0, d_len);
 218   silc_free(e);
 219   silc_free(n);
 220   silc_free(d);
 221
 222   return ret;
 223 }
 224
 225 /* Set public key */
 226
 227 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
 228 {
 229   RsaKey *key = (RsaKey *)context;
 230   unsigned char tmp[4];
 231   SilcUInt32 e_len, n_len;
 232
 233   if (key->pub_set) {
 234     silc_mp_uninit(&key->e);
 235     silc_mp_uninit(&key->n);
 236     key->pub_set = FALSE;
 237   }
 238
 239   silc_mp_init(&key->e);
 240   silc_mp_init(&key->n);
 241
 242   memcpy(tmp, key_data, 4);
 243   SILC_GET32_MSB(e_len, tmp);
 244   if (!e_len || e_len > key_len) {
 245     silc_mp_uninit(&key->e);
 246     silc_mp_uninit(&key->n);
 247     return 0;
 248   }
 249
 250   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 251
 252   memcpy(tmp, key_data + 4 + e_len, 4);
 253   SILC_GET32_MSB(n_len, tmp);
 254   if (!n_len || e_len + n_len > key_len) {
 255     silc_mp_uninit(&key->e);
 256     silc_mp_uninit(&key->n);
 257     return 0;
 258   }
 259
 260   silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
 261
 262   key->bits = silc_mp_sizeinbase(&key->n, 2);
 263   key->pub_set = TRUE;
 264
 265   return key->bits;
 266 }
 267
 268 /* Set private key. This derives the public key from the private
 269    key and sets the public key as well. Public key should not be set
 270    already and should not be set after setting private key. */
 271
 272 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
 273 {
 274   RsaKey *key = (RsaKey *)context;
 275   unsigned char tmp[4];
 276   SilcUInt32 e_len, n_len, d_len;
 277
 278   if (key->prv_set) {
 279     silc_mp_uninit(&key->d);
 280     key->prv_set = FALSE;
 281   }
 282
 283   if (key->pub_set) {
 284     silc_mp_uninit(&key->e);
 285     silc_mp_uninit(&key->n);
 286     key->pub_set = FALSE;
 287   }
 288
 289   silc_mp_init(&key->e);
 290   silc_mp_init(&key->n);
 291   silc_mp_init(&key->d);
 292
 293   memcpy(tmp, key_data, 4);
 294   SILC_GET32_MSB(e_len, tmp);
 295   if (e_len > key_len) {
 296     silc_mp_uninit(&key->e);
 297     silc_mp_uninit(&key->n);
 298     silc_mp_uninit(&key->d);
 299     return FALSE;
 300   }
 301
 302   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 303
 304   memcpy(tmp, key_data + 4 + e_len, 4);
 305   SILC_GET32_MSB(n_len, tmp);
 306   if (e_len + n_len > key_len) {
 307     silc_mp_uninit(&key->e);
 308     silc_mp_uninit(&key->n);
 309     silc_mp_uninit(&key->d);
 310     return FALSE;
 311   }
 312
 313   silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
 314
 315   memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
 316   SILC_GET32_MSB(d_len, tmp);
 317   if (e_len + n_len + d_len > key_len) {
 318     silc_mp_uninit(&key->e);
 319     silc_mp_uninit(&key->n);
 320     silc_mp_uninit(&key->d);
 321     return FALSE;
 322   }
 323
 324   silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
 325
 326   key->bits = silc_mp_sizeinbase(&key->n, 2);
 327   key->prv_set = TRUE;
 328   key->pub_set = TRUE;
 329
 330   return key->bits;
 331 }
 332
 333 SILC_PKCS_API_CONTEXT_LEN(rsa)
 334 {
 335   return sizeof(RsaKey);
 336 }
 337
 338 SILC_PKCS_API_ENCRYPT(rsa)
 339 {
 340   RsaKey *key = (RsaKey *)context;
 341   int tmplen;
 342   SilcMPInt mp_tmp;
 343   SilcMPInt mp_dst;
 344
 345   silc_mp_init(&mp_tmp);
 346   silc_mp_init(&mp_dst);
 347
 348   /* Format the data into MP int */
 349   silc_mp_bin2mp(src, src_len, &mp_tmp);
 350
 351   /* Encrypt */
 352   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 353
 354   tmplen = (key->bits + 7) / 8;
 355
 356   /* Format the MP int back into data */
 357   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 358   *dst_len = tmplen;
 359
 360   silc_mp_uninit(&mp_tmp);
 361   silc_mp_uninit(&mp_dst);
 362
 363   return TRUE;
 364 }
 365
 366 SILC_PKCS_API_DECRYPT(rsa)
 367 {
 368   RsaKey *key = (RsaKey *)context;
 369   int tmplen;
 370   SilcMPInt mp_tmp;
 371   SilcMPInt mp_dst;
 372
 373   silc_mp_init(&mp_tmp);
 374   silc_mp_init(&mp_dst);
 375
 376   /* Format the data into MP int */
 377   silc_mp_bin2mp(src, src_len, &mp_tmp);
 378
 379   /* Decrypt */
 380   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 381
 382   tmplen = (key->bits + 7) / 8;
 383
 384   /* Format the MP int back into data */
 385   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 386   *dst_len = tmplen;
 387
 388   silc_mp_uninit(&mp_tmp);
 389   silc_mp_uninit(&mp_dst);
 390
 391   return TRUE;
 392 }
 393
 394 SILC_PKCS_API_SIGN(rsa)
 395 {
 396   RsaKey *key = (RsaKey *)context;
 397   int tmplen;
 398   SilcMPInt mp_tmp;
 399   SilcMPInt mp_dst;
 400
 401   silc_mp_init(&mp_tmp);
 402   silc_mp_init(&mp_dst);
 403
 404   /* Format the data into MP int */
 405   silc_mp_bin2mp(src, src_len, &mp_tmp);
 406
 407   /* Sign */
 408   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 409
 410   tmplen = (key->bits + 7) / 8;
 411
 412   /* Format the MP int back into data */
 413   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 414   *dst_len = tmplen;
 415
 416   silc_mp_uninit(&mp_tmp);
 417   silc_mp_uninit(&mp_dst);
 418
 419   return TRUE;
 420 }
 421
 422 SILC_PKCS_API_VERIFY(rsa)
 423 {
 424   RsaKey *key = (RsaKey *)context;
 425   int ret;
 426   SilcMPInt mp_tmp, mp_tmp2;
 427   SilcMPInt mp_dst;
 428
 429   silc_mp_init(&mp_tmp);
 430   silc_mp_init(&mp_tmp2);
 431   silc_mp_init(&mp_dst);
 432
 433   /* Format the signature into MP int */
 434   silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
 435
 436   /* Verify */
 437   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 438
 439   /* Format the data into MP int */
 440   silc_mp_bin2mp(data, data_len, &mp_tmp);
 441
 442   ret = TRUE;
 443
 444   /* Compare */
 445   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 446     ret = FALSE;
 447
 448   silc_mp_uninit(&mp_tmp);
 449   silc_mp_uninit(&mp_tmp2);
 450   silc_mp_uninit(&mp_dst);
 451
 452   return ret;
 453 }
 454
 455 /* Generates RSA public and private keys. Primes p and q that are used
 456    to compute the modulus n has to be generated before calling this. They
 457    are then sent as argument for the function. */
 458
 459 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
 460                        SilcMPInt *p, SilcMPInt *q)
 461 {
 462   SilcMPInt phi, hlp;
 463   SilcMPInt div, lcm;
 464   SilcMPInt pm1, qm1;
 465
 466   /* Initialize variables */
 467   silc_mp_init(&key->n);
 468   silc_mp_init(&key->e);
 469   silc_mp_init(&key->d);
 470   silc_mp_init(&phi);
 471   silc_mp_init(&hlp);
 472   silc_mp_init(&div);
 473   silc_mp_init(&lcm);
 474   silc_mp_init(&pm1);
 475   silc_mp_init(&qm1);
 476
 477   /* Set modulus length */
 478   key->bits = bits;
 479
 480   /* Compute modulus, n = p * q */
 481   silc_mp_mul(&key->n, p, q);
 482
 483   /* phi = (p - 1) * (q - 1) */
 484   silc_mp_sub_ui(&pm1, p, 1);
 485   silc_mp_sub_ui(&qm1, q, 1);
 486   silc_mp_mul(&phi, &pm1, &qm1);
 487
 488   /* Set e, the public exponent. We try to use same public exponent
 489      for all keys. Also, to make encryption faster we use small
 490      number. */
 491   silc_mp_set_ui(&key->e, 65533);
 492  retry_e:
 493   /* See if e is relatively prime to phi. gcd == greates common divisor,
 494      if gcd equals 1 they are relatively prime. */
 495   silc_mp_gcd(&hlp, &key->e, &phi);
 496   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 497     silc_mp_add_ui(&key->e, &key->e, 2);
 498     goto retry_e;
 499   }
 500
 501   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 502   silc_mp_gcd(&div, &pm1, &qm1);
 503   silc_mp_div(&lcm, &phi, &div);
 504   silc_mp_modinv(&key->d, &key->e, &lcm);
 505
 506   silc_mp_uninit(&phi);
 507   silc_mp_uninit(&hlp);
 508   silc_mp_uninit(&div);
 509   silc_mp_uninit(&lcm);
 510   silc_mp_uninit(&pm1);
 511   silc_mp_uninit(&qm1);
 512 }
 513
 514 /* Clears whole key structure. */
 515
 516 void rsa_clear_keys(RsaKey *key)
 517 {
 518   key->bits = 0;
 519   if (key->pub_set) {
 520     silc_mp_uninit(&key->n);
 521     silc_mp_uninit(&key->e);
 522   }
 523   if (key->prv_set)
 524     silc_mp_uninit(&key->d);
 525 }
 526
 527 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 528    mc = plaintext or ciphertext, expo = public or private exponent,
 529    and modu = modulus.
 530
 531    Encrypt: c = m ^ e mod n,
 532    Decrypt: m = c ^ d mod n
 533 */
 534
 535 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
 536                      SilcMPInt *expo, SilcMPInt *modu)
 537 {
 538   silc_mp_pow_mod(cm, mc, expo, modu);
 539 }