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