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 */
  65
  66 #include "silcincludes.h"
  67 #include "rsa_internal.h"
  68 #include "rsa.h"
  69
  70 /*
  71  * SILC PKCS API for RSA
  72  */
  73
  74 /* Generates RSA key pair. */
  75
  76 SILC_PKCS_API_INIT(rsa)
  77 {
  78   SilcUInt32 prime_bits = keylen / 2;
  79   SilcMPInt p, q;
  80   bool found = FALSE;
  81
  82   printf("Generating RSA Public and Private keys, might take a while...\n");
  83
  84   silc_mp_init(&p);
  85   silc_mp_init(&q);
  86
  87   /* Find p and q */
  88   while (!found) {
  89     printf("Finding p: ");
  90     silc_math_gen_prime(&p, prime_bits, TRUE);
  91
  92     printf("\nFinding q: ");
  93     silc_math_gen_prime(&q, prime_bits, TRUE);
  94
  95     if ((silc_mp_cmp(&p, &q)) == 0)
  96       printf("\nFound equal primes, not good, retrying...\n");
  97     else
  98       found = TRUE;
  99   }
 100
 101   /* If p is smaller than q, switch them */
 102   if ((silc_mp_cmp(&p, &q)) > 0) {
 103     SilcMPInt hlp;
 104     silc_mp_init(&hlp);
 105
 106     silc_mp_set(&hlp, &p);
 107     silc_mp_set(&p, &q);
 108     silc_mp_set(&q, &hlp);
 109
 110     silc_mp_uninit(&hlp);
 111   }
 112
 113   /* Generate the actual keys */
 114   rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
 115
 116   silc_mp_uninit(&p);
 117   silc_mp_uninit(&q);
 118
 119   printf("\nKeys generated succesfully.\n");
 120
 121   return TRUE;
 122 }
 123
 124 SILC_PKCS_API_CLEAR_KEYS(rsa)
 125 {
 126   rsa_clear_keys((RsaKey *)context);
 127 }
 128
 129 /* Returns SILC style encoded RSA public key. */
 130
 131 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
 132 {
 133   RsaKey *key = (RsaKey *)context;
 134   unsigned char *e, *n, *ret;
 135   SilcUInt32 e_len, n_len;
 136   unsigned char tmp[4];
 137
 138   e = silc_mp_mp2bin(&key->e, 0, &e_len);
 139   n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
 140
 141   *ret_len = e_len + 4 + n_len + 4;
 142   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 143
 144   /* Put the length of the e. */
 145   SILC_PUT32_MSB(e_len, tmp);
 146   memcpy(ret, tmp, 4);
 147
 148   /* Put the e. */
 149   memcpy(ret + 4, e, e_len);
 150
 151   /* Put the length of the n. */
 152   SILC_PUT32_MSB(n_len, tmp);
 153   memcpy(ret + 4 + e_len, tmp, 4);
 154
 155   /* Put the n. */
 156   memcpy(ret + 4 + e_len + 4, n, n_len);
 157
 158   memset(e, 0, e_len);
 159   memset(n, 0, n_len);
 160   silc_free(e);
 161   silc_free(n);
 162
 163   return ret;
 164 }
 165
 166 /* Returns SILC style encoded RSA private key. Public key is always
 167    returned in private key as well. Public keys are often derived
 168    directly from private key. */
 169
 170 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
 171 {
 172   RsaKey *key = (RsaKey *)context;
 173   unsigned char *e, *n, *d, *ret;
 174   SilcUInt32 e_len, n_len, d_len;
 175   unsigned char tmp[4];
 176
 177   e = silc_mp_mp2bin(&key->e, 0, &e_len);
 178   n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
 179   d = silc_mp_mp2bin(&key->d, 0, &d_len);
 180
 181   *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
 182   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 183
 184   /* Put the length of the e. */
 185   SILC_PUT32_MSB(e_len, tmp);
 186   memcpy(ret, tmp, 4);
 187
 188   /* Put the e. */
 189   memcpy(ret + 4, e, e_len);
 190
 191   /* Put the length of the n. */
 192   SILC_PUT32_MSB(n_len, tmp);
 193   memcpy(ret + 4 + e_len, tmp, 4);
 194
 195   /* Put the n. */
 196   memcpy(ret + 4 + e_len + 4, n, n_len);
 197
 198   /* Put the length of the d. */
 199   SILC_PUT32_MSB(d_len, tmp);
 200   memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
 201
 202   /* Put the n. */
 203   memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
 204
 205   memset(e, 0, e_len);
 206   memset(n, 0, n_len);
 207   memset(d, 0, d_len);
 208   silc_free(e);
 209   silc_free(n);
 210   silc_free(d);
 211
 212   return ret;
 213 }
 214
 215 /* Set public key */
 216
 217 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
 218 {
 219   RsaKey *key = (RsaKey *)context;
 220   unsigned char tmp[4];
 221   SilcUInt32 e_len, n_len;
 222
 223   if (key->pub_set) {
 224     silc_mp_uninit(&key->e);
 225     silc_mp_uninit(&key->e);
 226     key->pub_set = FALSE;
 227   }
 228
 229   silc_mp_init(&key->e);
 230   silc_mp_init(&key->n);
 231
 232   memcpy(tmp, key_data, 4);
 233   SILC_GET32_MSB(e_len, tmp);
 234   if (e_len > key_len) {
 235     silc_mp_uninit(&key->e);
 236     silc_mp_uninit(&key->n);
 237     return 0;
 238   }
 239
 240   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 241
 242   memcpy(tmp, key_data + 4 + e_len, 4);
 243   SILC_GET32_MSB(n_len, tmp);
 244   if (e_len + n_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 + 4, n_len, &key->n);
 251
 252   key->bits = n_len * 8;
 253   key->pub_set = TRUE;
 254
 255   return key->bits;
 256 }
 257
 258 /* Set private key. This derives the public key from the private
 259    key and sets the public key as well. Public key should not be set
 260    already and should not be set after setting private key. */
 261
 262 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
 263 {
 264   RsaKey *key = (RsaKey *)context;
 265   unsigned char tmp[4];
 266   SilcUInt32 e_len, n_len, d_len;
 267
 268   if (key->prv_set) {
 269     silc_mp_uninit(&key->d);
 270     key->prv_set = FALSE;
 271   }
 272
 273   if (key->pub_set) {
 274     silc_mp_uninit(&key->e);
 275     silc_mp_uninit(&key->n);
 276     key->pub_set = FALSE;
 277   }
 278
 279   silc_mp_init(&key->e);
 280   silc_mp_init(&key->n);
 281   silc_mp_init(&key->d);
 282
 283   memcpy(tmp, key_data, 4);
 284   SILC_GET32_MSB(e_len, tmp);
 285   if (e_len > key_len) {
 286     silc_mp_uninit(&key->e);
 287     silc_mp_uninit(&key->n);
 288     silc_mp_uninit(&key->d);
 289     return FALSE;
 290   }
 291
 292   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 293
 294   memcpy(tmp, key_data + 4 + e_len, 4);
 295   SILC_GET32_MSB(n_len, tmp);
 296   if (e_len + n_len > key_len) {
 297     silc_mp_uninit(&key->e);
 298     silc_mp_uninit(&key->n);
 299     silc_mp_uninit(&key->d);
 300     return FALSE;
 301   }
 302
 303   silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
 304
 305   memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
 306   SILC_GET32_MSB(d_len, tmp);
 307   if (e_len + n_len + d_len > 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 + 4 + n_len + 4, d_len, &key->d);
 315
 316   key->bits = n_len * 8;
 317   key->prv_set = TRUE;
 318   key->pub_set = TRUE;
 319
 320   return TRUE;
 321 }
 322
 323 SILC_PKCS_API_CONTEXT_LEN(rsa)
 324 {
 325   return sizeof(RsaKey);
 326 }
 327
 328 SILC_PKCS_API_ENCRYPT(rsa)
 329 {
 330   RsaKey *key = (RsaKey *)context;
 331   int i, tmplen;
 332   SilcMPInt mp_tmp;
 333   SilcMPInt mp_dst;
 334
 335   silc_mp_init(&mp_tmp);
 336   silc_mp_init(&mp_dst);
 337   silc_mp_set_ui(&mp_tmp, 0);
 338   silc_mp_set_ui(&mp_dst, 0);
 339
 340   /* Format the data into MP int */
 341   for (i = 0; i < src_len; i++) {
 342     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 343     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 344   }
 345
 346   /* Encrypt */
 347   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 348
 349   tmplen = (key->bits + 7) / 8;
 350
 351   /* Format the MP int back into data */
 352   for (i = tmplen; i > 0; i--) {
 353     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 354     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 355   }
 356   *dst_len = tmplen;
 357
 358   silc_mp_uninit(&mp_tmp);
 359   silc_mp_uninit(&mp_dst);
 360
 361   return TRUE;
 362 }
 363
 364 SILC_PKCS_API_DECRYPT(rsa)
 365 {
 366   RsaKey *key = (RsaKey *)context;
 367   int i, tmplen;
 368   SilcMPInt mp_tmp;
 369   SilcMPInt mp_dst;
 370
 371   silc_mp_init(&mp_tmp);
 372   silc_mp_init(&mp_dst);
 373   silc_mp_set_ui(&mp_tmp, 0);
 374   silc_mp_set_ui(&mp_dst, 0);
 375
 376   /* Format the data into MP int */
 377   for (i = 0; i < src_len; i++) {
 378     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 379     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 380   }
 381
 382   /* Decrypt */
 383   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 384
 385   tmplen = (key->bits + 7) / 8;
 386
 387   /* Format the MP int back into data */
 388   for (i = tmplen; i > 0; i--) {
 389     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 390     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 391   }
 392   *dst_len = tmplen;
 393
 394   silc_mp_uninit(&mp_tmp);
 395   silc_mp_uninit(&mp_dst);
 396
 397   return TRUE;
 398 }
 399
 400 SILC_PKCS_API_SIGN(rsa)
 401 {
 402   RsaKey *key = (RsaKey *)context;
 403   int i, tmplen;
 404   SilcMPInt mp_tmp;
 405   SilcMPInt mp_dst;
 406
 407   silc_mp_init(&mp_tmp);
 408   silc_mp_init(&mp_dst);
 409   silc_mp_set_ui(&mp_tmp, 0);
 410   silc_mp_set_ui(&mp_dst, 0);
 411
 412   /* Format the data into MP int */
 413   for (i = 0; i < src_len; i++) {
 414     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 415     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 416   }
 417
 418   /* Sign */
 419   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 420
 421   tmplen = (key->bits + 7) / 8;
 422
 423   /* Format the MP int back into data */
 424   for (i = tmplen; i > 0; i--) {
 425     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 426     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 427   }
 428   *dst_len = tmplen;
 429
 430   silc_mp_uninit(&mp_tmp);
 431   silc_mp_uninit(&mp_dst);
 432
 433   return TRUE;
 434 }
 435
 436 SILC_PKCS_API_VERIFY(rsa)
 437 {
 438   RsaKey *key = (RsaKey *)context;
 439   int i, ret;
 440   SilcMPInt mp_tmp, mp_tmp2;
 441   SilcMPInt mp_dst;
 442
 443   silc_mp_init(&mp_tmp);
 444   silc_mp_init(&mp_tmp2);
 445   silc_mp_init(&mp_dst);
 446   silc_mp_set_ui(&mp_tmp, 0);
 447   silc_mp_set_ui(&mp_tmp2, 0);
 448   silc_mp_set_ui(&mp_dst, 0);
 449
 450   /* Format the signature into MP int */
 451   for (i = 0; i < signature_len; i++) {
 452     silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
 453     silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
 454   }
 455
 456   /* Verify */
 457   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 458
 459   /* Format the data into MP int */
 460   for (i = 0; i < data_len; i++) {
 461     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 462     silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
 463   }
 464
 465   ret = TRUE;
 466
 467   /* Compare */
 468   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 469     ret = FALSE;
 470
 471   silc_mp_uninit(&mp_tmp);
 472   silc_mp_uninit(&mp_tmp2);
 473   silc_mp_uninit(&mp_dst);
 474
 475   return ret;
 476 }
 477
 478 /* Generates RSA public and private keys. Primes p and q that are used
 479    to compute the modulus n has to be generated before calling this. They
 480    are then sent as argument for the function. */
 481
 482 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
 483                        SilcMPInt *p, SilcMPInt *q)
 484 {
 485   SilcMPInt phi, hlp;
 486   SilcMPInt div, lcm;
 487   SilcMPInt pm1, qm1;
 488
 489   /* Initialize variables */
 490   silc_mp_init(&key->n);
 491   silc_mp_init(&key->e);
 492   silc_mp_init(&key->d);
 493   silc_mp_init(&phi);
 494   silc_mp_init(&hlp);
 495   silc_mp_init(&div);
 496   silc_mp_init(&lcm);
 497   silc_mp_init(&pm1);
 498   silc_mp_init(&qm1);
 499
 500   /* Set modulus length */
 501   key->bits = bits;
 502
 503   /* Compute modulus, n = p * q */
 504   silc_mp_mul(&key->n, p, q);
 505
 506   /* phi = (p - 1) * (q - 1) */
 507   silc_mp_sub_ui(&pm1, p, 1);
 508   silc_mp_sub_ui(&qm1, q, 1);
 509   silc_mp_mul(&phi, &pm1, &qm1);
 510
 511   /* Set e, the public exponent. We try to use same public exponent
 512      for all keys. Also, to make encryption faster we use small
 513      number. */
 514   silc_mp_set_ui(&key->e, 127);
 515  retry_e:
 516   /* See if e is relatively prime to phi. gcd == greates common divisor,
 517      if gcd equals 1 they are relatively prime. */
 518   silc_mp_gcd(&hlp, &key->e, &phi);
 519   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 520     silc_mp_add_ui(&key->e, &key->e, 2);
 521     goto retry_e;
 522   }
 523
 524   /* Find d, the private exponent. */
 525   silc_mp_gcd(&div, &pm1, &qm1);
 526   silc_mp_div(&lcm, &phi, &div);
 527   silc_mp_modinv(&key->d, &key->e, &lcm);
 528
 529   silc_mp_uninit(&phi);
 530   silc_mp_uninit(&hlp);
 531   silc_mp_uninit(&div);
 532   silc_mp_uninit(&lcm);
 533   silc_mp_uninit(&pm1);
 534   silc_mp_uninit(&qm1);
 535 }
 536
 537 /* Clears whole key structure. */
 538
 539 void rsa_clear_keys(RsaKey *key)
 540 {
 541   key->bits = 0;
 542   if (key->pub_set) {
 543     silc_mp_uninit(&key->n);
 544     silc_mp_uninit(&key->e);
 545   }
 546   if (key->prv_set)
 547     silc_mp_uninit(&key->d);
 548 }
 549
 550 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 551    mc = plaintext or ciphertext, expo = public or private exponent,
 552    and modu = modulus.
 553
 554    Encrypt: c = m ^ e mod n,
 555    Decrypt: m = c ^ d mod n
 556 */
 557
 558 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
 559                      SilcMPInt *expo, SilcMPInt *modu)
 560 {
 561   silc_mp_pow_mod(cm, mc, expo, modu);
 562 }