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