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 / 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 / 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 = n_len * 8;
 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 = n_len * 8;
 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 i, tmplen;
 342   SilcMPInt mp_tmp;
 343   SilcMPInt mp_dst;
 344
 345   silc_mp_init(&mp_tmp);
 346   silc_mp_init(&mp_dst);
 347   silc_mp_set_ui(&mp_tmp, 0);
 348   silc_mp_set_ui(&mp_dst, 0);
 349
 350   /* Format the data into MP int */
 351   for (i = 0; i < src_len; i++) {
 352     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 353     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 354   }
 355
 356   /* Encrypt */
 357   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 358
 359   tmplen = (key->bits + 7) / 8;
 360
 361   /* Format the MP int back into data */
 362   for (i = tmplen; i > 0; i--) {
 363     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 364     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 365   }
 366   *dst_len = tmplen;
 367
 368   silc_mp_uninit(&mp_tmp);
 369   silc_mp_uninit(&mp_dst);
 370
 371   return TRUE;
 372 }
 373
 374 SILC_PKCS_API_DECRYPT(rsa)
 375 {
 376   RsaKey *key = (RsaKey *)context;
 377   int i, tmplen;
 378   SilcMPInt mp_tmp;
 379   SilcMPInt mp_dst;
 380
 381   silc_mp_init(&mp_tmp);
 382   silc_mp_init(&mp_dst);
 383   silc_mp_set_ui(&mp_tmp, 0);
 384   silc_mp_set_ui(&mp_dst, 0);
 385
 386   /* Format the data into MP int */
 387   for (i = 0; i < src_len; i++) {
 388     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 389     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 390   }
 391
 392   /* Decrypt */
 393   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 394
 395   tmplen = (key->bits + 7) / 8;
 396
 397   /* Format the MP int back into data */
 398   for (i = tmplen; i > 0; i--) {
 399     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 400     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 401   }
 402   *dst_len = tmplen;
 403
 404   silc_mp_uninit(&mp_tmp);
 405   silc_mp_uninit(&mp_dst);
 406
 407   return TRUE;
 408 }
 409
 410 SILC_PKCS_API_SIGN(rsa)
 411 {
 412   RsaKey *key = (RsaKey *)context;
 413   int i, tmplen;
 414   SilcMPInt mp_tmp;
 415   SilcMPInt mp_dst;
 416
 417   silc_mp_init(&mp_tmp);
 418   silc_mp_init(&mp_dst);
 419   silc_mp_set_ui(&mp_tmp, 0);
 420   silc_mp_set_ui(&mp_dst, 0);
 421
 422   /* Format the data into MP int */
 423   for (i = 0; i < src_len; i++) {
 424     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 425     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 426   }
 427
 428   /* Sign */
 429   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 430
 431   tmplen = (key->bits + 7) / 8;
 432
 433   /* Format the MP int back into data */
 434   for (i = tmplen; i > 0; i--) {
 435     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 436     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 437   }
 438   *dst_len = tmplen;
 439
 440   silc_mp_uninit(&mp_tmp);
 441   silc_mp_uninit(&mp_dst);
 442
 443   return TRUE;
 444 }
 445
 446 SILC_PKCS_API_VERIFY(rsa)
 447 {
 448   RsaKey *key = (RsaKey *)context;
 449   int i, ret;
 450   SilcMPInt mp_tmp, mp_tmp2;
 451   SilcMPInt mp_dst;
 452
 453   silc_mp_init(&mp_tmp);
 454   silc_mp_init(&mp_tmp2);
 455   silc_mp_init(&mp_dst);
 456   silc_mp_set_ui(&mp_tmp, 0);
 457   silc_mp_set_ui(&mp_tmp2, 0);
 458   silc_mp_set_ui(&mp_dst, 0);
 459
 460   /* Format the signature into MP int */
 461   for (i = 0; i < signature_len; i++) {
 462     silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
 463     silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
 464   }
 465
 466   /* Verify */
 467   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 468
 469   /* Format the data into MP int */
 470   for (i = 0; i < data_len; i++) {
 471     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 472     silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
 473   }
 474
 475   ret = TRUE;
 476
 477   /* Compare */
 478   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 479     ret = FALSE;
 480
 481   silc_mp_uninit(&mp_tmp);
 482   silc_mp_uninit(&mp_tmp2);
 483   silc_mp_uninit(&mp_dst);
 484
 485   return ret;
 486 }
 487
 488 /* Generates RSA public and private keys. Primes p and q that are used
 489    to compute the modulus n has to be generated before calling this. They
 490    are then sent as argument for the function. */
 491
 492 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
 493                        SilcMPInt *p, SilcMPInt *q)
 494 {
 495   SilcMPInt phi, hlp;
 496   SilcMPInt div, lcm;
 497   SilcMPInt pm1, qm1;
 498
 499   /* Initialize variables */
 500   silc_mp_init(&key->n);
 501   silc_mp_init(&key->e);
 502   silc_mp_init(&key->d);
 503   silc_mp_init(&phi);
 504   silc_mp_init(&hlp);
 505   silc_mp_init(&div);
 506   silc_mp_init(&lcm);
 507   silc_mp_init(&pm1);
 508   silc_mp_init(&qm1);
 509
 510   /* Set modulus length */
 511   key->bits = bits;
 512
 513   /* Compute modulus, n = p * q */
 514   silc_mp_mul(&key->n, p, q);
 515
 516   /* phi = (p - 1) * (q - 1) */
 517   silc_mp_sub_ui(&pm1, p, 1);
 518   silc_mp_sub_ui(&qm1, q, 1);
 519   silc_mp_mul(&phi, &pm1, &qm1);
 520
 521   /* Set e, the public exponent. We try to use same public exponent
 522      for all keys. Also, to make encryption faster we use small
 523      number. */
 524   silc_mp_set_ui(&key->e, 65533);
 525  retry_e:
 526   /* See if e is relatively prime to phi. gcd == greates common divisor,
 527      if gcd equals 1 they are relatively prime. */
 528   silc_mp_gcd(&hlp, &key->e, &phi);
 529   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 530     silc_mp_add_ui(&key->e, &key->e, 2);
 531     goto retry_e;
 532   }
 533
 534   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 535   silc_mp_gcd(&div, &pm1, &qm1);
 536   silc_mp_div(&lcm, &phi, &div);
 537   silc_mp_modinv(&key->d, &key->e, &lcm);
 538
 539   silc_mp_uninit(&phi);
 540   silc_mp_uninit(&hlp);
 541   silc_mp_uninit(&div);
 542   silc_mp_uninit(&lcm);
 543   silc_mp_uninit(&pm1);
 544   silc_mp_uninit(&qm1);
 545 }
 546
 547 /* Clears whole key structure. */
 548
 549 void rsa_clear_keys(RsaKey *key)
 550 {
 551   key->bits = 0;
 552   if (key->pub_set) {
 553     silc_mp_uninit(&key->n);
 554     silc_mp_uninit(&key->e);
 555   }
 556   if (key->prv_set)
 557     silc_mp_uninit(&key->d);
 558 }
 559
 560 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 561    mc = plaintext or ciphertext, expo = public or private exponent,
 562    and modu = modulus.
 563
 564    Encrypt: c = m ^ e mod n,
 565    Decrypt: m = c ^ d mod n
 566 */
 567
 568 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
 569                      SilcMPInt *expo, SilcMPInt *modu)
 570 {
 571   silc_mp_pow_mod(cm, mc, expo, modu);
 572 }