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