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