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