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   if (key_len < 4)
 240     return 0;
 241
 242   silc_mp_init(&key->e);
 243   silc_mp_init(&key->n);
 244
 245   memcpy(tmp, key_data, 4);
 246   SILC_GET32_MSB(e_len, tmp);
 247   if (!e_len || e_len + 4 > key_len) {
 248     silc_mp_uninit(&key->e);
 249     silc_mp_uninit(&key->n);
 250     return 0;
 251   }
 252
 253   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 254
 255   if (key_len < 4 + e_len + 4) {
 256     silc_mp_uninit(&key->e);
 257     silc_mp_uninit(&key->n);
 258     return 0;
 259   }
 260
 261   memcpy(tmp, key_data + 4 + e_len, 4);
 262   SILC_GET32_MSB(n_len, tmp);
 263   if (!n_len || e_len + 4 + n_len + 4 > key_len) {
 264     silc_mp_uninit(&key->e);
 265     silc_mp_uninit(&key->n);
 266     return 0;
 267   }
 268
 269   silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
 270
 271   key->bits = silc_mp_sizeinbase(&key->n, 2);
 272   key->pub_set = TRUE;
 273
 274   return key->bits;
 275 }
 276
 277 /* Set private key. This derives the public key from the private
 278    key and sets the public key as well. Public key should not be set
 279    already and should not be set after setting private key. */
 280
 281 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
 282 {
 283   RsaKey *key = (RsaKey *)context;
 284   unsigned char tmp[4];
 285   SilcUInt32 e_len, n_len, d_len;
 286
 287   if (key->prv_set) {
 288     silc_mp_uninit(&key->d);
 289     key->prv_set = FALSE;
 290   }
 291
 292   if (key->pub_set) {
 293     silc_mp_uninit(&key->e);
 294     silc_mp_uninit(&key->n);
 295     key->pub_set = FALSE;
 296   }
 297
 298   if (key_len < 4)
 299     return FALSE;
 300
 301   silc_mp_init(&key->e);
 302   silc_mp_init(&key->n);
 303   silc_mp_init(&key->d);
 304
 305   memcpy(tmp, key_data, 4);
 306   SILC_GET32_MSB(e_len, tmp);
 307   if (e_len + 4 > key_len) {
 308     silc_mp_uninit(&key->e);
 309     silc_mp_uninit(&key->n);
 310     silc_mp_uninit(&key->d);
 311     return FALSE;
 312   }
 313
 314   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 315
 316   if (key_len < e_len + 4 + 4) {
 317     silc_mp_uninit(&key->e);
 318     silc_mp_uninit(&key->n);
 319     silc_mp_uninit(&key->d);
 320     return FALSE;
 321   }
 322
 323   memcpy(tmp, key_data + 4 + e_len, 4);
 324   SILC_GET32_MSB(n_len, tmp);
 325   if (e_len + 4 + n_len + 4 > key_len) {
 326     silc_mp_uninit(&key->e);
 327     silc_mp_uninit(&key->n);
 328     silc_mp_uninit(&key->d);
 329     return FALSE;
 330   }
 331
 332   silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
 333
 334   if (key_len < e_len + 4 + n_len + 4 + 4) {
 335     silc_mp_uninit(&key->e);
 336     silc_mp_uninit(&key->n);
 337     silc_mp_uninit(&key->d);
 338     return FALSE;
 339   }
 340
 341   memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
 342   SILC_GET32_MSB(d_len, tmp);
 343   if (e_len + 4 + n_len + 4 + d_len + 4 > key_len) {
 344     silc_mp_uninit(&key->e);
 345     silc_mp_uninit(&key->n);
 346     silc_mp_uninit(&key->d);
 347     return FALSE;
 348   }
 349
 350   silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
 351
 352   key->bits = silc_mp_sizeinbase(&key->n, 2);
 353   key->prv_set = TRUE;
 354   key->pub_set = TRUE;
 355
 356   return key->bits;
 357 }
 358
 359 SILC_PKCS_API_CONTEXT_LEN(rsa)
 360 {
 361   return sizeof(RsaKey);
 362 }
 363
 364 SILC_PKCS_API_ENCRYPT(rsa)
 365 {
 366   RsaKey *key = (RsaKey *)context;
 367   int tmplen;
 368   SilcMPInt mp_tmp;
 369   SilcMPInt mp_dst;
 370
 371   silc_mp_init(&mp_tmp);
 372   silc_mp_init(&mp_dst);
 373
 374   /* Format the data into MP int */
 375   silc_mp_bin2mp(src, src_len, &mp_tmp);
 376
 377   /* Encrypt */
 378   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 379
 380   tmplen = (key->bits + 7) / 8;
 381
 382   /* Format the MP int back into data */
 383   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 384   *dst_len = tmplen;
 385
 386   silc_mp_uninit(&mp_tmp);
 387   silc_mp_uninit(&mp_dst);
 388
 389   return TRUE;
 390 }
 391
 392 SILC_PKCS_API_DECRYPT(rsa)
 393 {
 394   RsaKey *key = (RsaKey *)context;
 395   int tmplen;
 396   SilcMPInt mp_tmp;
 397   SilcMPInt mp_dst;
 398
 399   silc_mp_init(&mp_tmp);
 400   silc_mp_init(&mp_dst);
 401
 402   /* Format the data into MP int */
 403   silc_mp_bin2mp(src, src_len, &mp_tmp);
 404
 405   /* Decrypt */
 406   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 407
 408   tmplen = (key->bits + 7) / 8;
 409
 410   /* Format the MP int back into data */
 411   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 412   *dst_len = tmplen;
 413
 414   silc_mp_uninit(&mp_tmp);
 415   silc_mp_uninit(&mp_dst);
 416
 417   return TRUE;
 418 }
 419
 420 SILC_PKCS_API_SIGN(rsa)
 421 {
 422   RsaKey *key = (RsaKey *)context;
 423   int tmplen;
 424   SilcMPInt mp_tmp;
 425   SilcMPInt mp_dst;
 426
 427   silc_mp_init(&mp_tmp);
 428   silc_mp_init(&mp_dst);
 429
 430   /* Format the data into MP int */
 431   silc_mp_bin2mp(src, src_len, &mp_tmp);
 432
 433   /* Sign */
 434   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 435
 436   tmplen = (key->bits + 7) / 8;
 437
 438   /* Format the MP int back into data */
 439   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 440   *dst_len = tmplen;
 441
 442   silc_mp_uninit(&mp_tmp);
 443   silc_mp_uninit(&mp_dst);
 444
 445   return TRUE;
 446 }
 447
 448 SILC_PKCS_API_VERIFY(rsa)
 449 {
 450   RsaKey *key = (RsaKey *)context;
 451   int ret;
 452   SilcMPInt mp_tmp, mp_tmp2;
 453   SilcMPInt mp_dst;
 454
 455   silc_mp_init(&mp_tmp);
 456   silc_mp_init(&mp_tmp2);
 457   silc_mp_init(&mp_dst);
 458
 459   /* Format the signature into MP int */
 460   silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
 461
 462   /* Verify */
 463   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 464
 465   /* Format the data into MP int */
 466   silc_mp_bin2mp(data, data_len, &mp_tmp);
 467
 468   ret = TRUE;
 469
 470   /* Compare */
 471   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 472     ret = FALSE;
 473
 474   silc_mp_uninit(&mp_tmp);
 475   silc_mp_uninit(&mp_tmp2);
 476   silc_mp_uninit(&mp_dst);
 477
 478   return ret;
 479 }
 480
 481 /* Generates RSA public and private keys. Primes p and q that are used
 482    to compute the modulus n has to be generated before calling this. They
 483    are then sent as argument for the function. */
 484
 485 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
 486                        SilcMPInt *p, SilcMPInt *q)
 487 {
 488   SilcMPInt phi, hlp;
 489   SilcMPInt div, lcm;
 490   SilcMPInt pm1, qm1;
 491
 492   /* Initialize variables */
 493   silc_mp_init(&key->n);
 494   silc_mp_init(&key->e);
 495   silc_mp_init(&key->d);
 496   silc_mp_init(&phi);
 497   silc_mp_init(&hlp);
 498   silc_mp_init(&div);
 499   silc_mp_init(&lcm);
 500   silc_mp_init(&pm1);
 501   silc_mp_init(&qm1);
 502
 503   /* Set modulus length */
 504   key->bits = bits;
 505
 506   /* Compute modulus, n = p * q */
 507   silc_mp_mul(&key->n, p, q);
 508
 509   /* phi = (p - 1) * (q - 1) */
 510   silc_mp_sub_ui(&pm1, p, 1);
 511   silc_mp_sub_ui(&qm1, q, 1);
 512   silc_mp_mul(&phi, &pm1, &qm1);
 513
 514   /* Set e, the public exponent. We try to use same public exponent
 515      for all keys. Also, to make encryption faster we use small
 516      number. */
 517   silc_mp_set_ui(&key->e, 65533);
 518  retry_e:
 519   /* See if e is relatively prime to phi. gcd == greates common divisor,
 520      if gcd equals 1 they are relatively prime. */
 521   silc_mp_gcd(&hlp, &key->e, &phi);
 522   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 523     silc_mp_add_ui(&key->e, &key->e, 2);
 524     goto retry_e;
 525   }
 526
 527   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 528   silc_mp_gcd(&div, &pm1, &qm1);
 529   silc_mp_div(&lcm, &phi, &div);
 530   silc_mp_modinv(&key->d, &key->e, &lcm);
 531
 532   silc_mp_uninit(&phi);
 533   silc_mp_uninit(&hlp);
 534   silc_mp_uninit(&div);
 535   silc_mp_uninit(&lcm);
 536   silc_mp_uninit(&pm1);
 537   silc_mp_uninit(&qm1);
 538 }
 539
 540 /* Clears whole key structure. */
 541
 542 void rsa_clear_keys(RsaKey *key)
 543 {
 544   key->bits = 0;
 545   if (key->pub_set) {
 546     silc_mp_uninit(&key->n);
 547     silc_mp_uninit(&key->e);
 548   }
 549   if (key->prv_set)
 550     silc_mp_uninit(&key->d);
 551 }
 552
 553 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 554    mc = plaintext or ciphertext, expo = public or private exponent,
 555    and modu = modulus.
 556
 557    Encrypt: c = m ^ e mod n,
 558    Decrypt: m = c ^ d mod n
 559 */
 560
 561 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
 562                      SilcMPInt *expo, SilcMPInt *modu)
 563 {
 564   silc_mp_pow_mod(cm, mc, expo, modu);
 565 }