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   SilcMPInt 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     SilcMPInt 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_uninit(&hlp);
 107   }
 108
 109   /* Generate the actual keys */
 110   rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
 111
 112   silc_mp_uninit(&p);
 113   silc_mp_uninit(&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_uninit(&key->e);
 226     silc_mp_uninit(&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_uninit(&key->e);
 236     silc_mp_uninit(&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_uninit(&key->e);
 265     silc_mp_uninit(&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_uninit(&key->e);
 275     silc_mp_uninit(&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_uninit(&key->e);
 285     silc_mp_uninit(&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   SilcMPInt mp_tmp;
 306   SilcMPInt mp_dst;
 307
 308   silc_mp_init(&mp_tmp);
 309   silc_mp_init(&mp_dst);
 310   silc_mp_set_ui(&mp_tmp, 0);
 311   silc_mp_set_ui(&mp_dst, 0);
 312
 313   /* Format the data into MP int */
 314   for (i = 0; i < src_len; i++) {
 315     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 316     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 317   }
 318
 319   /* Encrypt */
 320   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 321
 322   tmplen = (key->bits + 7) / 8;
 323
 324   /* Format the MP int back into data */
 325   for (i = tmplen; i > 0; i--) {
 326     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 327     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 328   }
 329   *dst_len = tmplen;
 330
 331   silc_mp_uninit(&mp_tmp);
 332   silc_mp_uninit(&mp_dst);
 333
 334   return TRUE;
 335 }
 336
 337 SILC_PKCS_API_DECRYPT(rsa)
 338 {
 339   RsaKey *key = (RsaKey *)context;
 340   int i, tmplen;
 341   SilcMPInt mp_tmp;
 342   SilcMPInt mp_dst;
 343
 344   silc_mp_init(&mp_tmp);
 345   silc_mp_init(&mp_dst);
 346   silc_mp_set_ui(&mp_tmp, 0);
 347   silc_mp_set_ui(&mp_dst, 0);
 348
 349   /* Format the data into MP int */
 350   for (i = 0; i < src_len; i++) {
 351     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 352     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 353   }
 354
 355   /* Decrypt */
 356   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 357
 358   tmplen = (key->bits + 7) / 8;
 359
 360   /* Format the MP int back into data */
 361   for (i = tmplen; i > 0; i--) {
 362     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 363     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 364   }
 365   *dst_len = tmplen;
 366
 367   silc_mp_uninit(&mp_tmp);
 368   silc_mp_uninit(&mp_dst);
 369
 370   return TRUE;
 371 }
 372
 373 SILC_PKCS_API_SIGN(rsa)
 374 {
 375   RsaKey *key = (RsaKey *)context;
 376   int i, tmplen;
 377   SilcMPInt mp_tmp;
 378   SilcMPInt mp_dst;
 379
 380   silc_mp_init(&mp_tmp);
 381   silc_mp_init(&mp_dst);
 382   silc_mp_set_ui(&mp_tmp, 0);
 383   silc_mp_set_ui(&mp_dst, 0);
 384
 385   /* Format the data into MP int */
 386   for (i = 0; i < src_len; i++) {
 387     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 388     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 389   }
 390
 391   /* Sign */
 392   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 393
 394   tmplen = (key->bits + 7) / 8;
 395
 396   /* Format the MP int back into data */
 397   for (i = tmplen; i > 0; i--) {
 398     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 399     silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
 400   }
 401   *dst_len = tmplen;
 402
 403   silc_mp_uninit(&mp_tmp);
 404   silc_mp_uninit(&mp_dst);
 405
 406   return TRUE;
 407 }
 408
 409 SILC_PKCS_API_VERIFY(rsa)
 410 {
 411   RsaKey *key = (RsaKey *)context;
 412   int i, ret;
 413   SilcMPInt mp_tmp, mp_tmp2;
 414   SilcMPInt mp_dst;
 415
 416   silc_mp_init(&mp_tmp);
 417   silc_mp_init(&mp_tmp2);
 418   silc_mp_init(&mp_dst);
 419   silc_mp_set_ui(&mp_tmp, 0);
 420   silc_mp_set_ui(&mp_tmp2, 0);
 421   silc_mp_set_ui(&mp_dst, 0);
 422
 423   /* Format the signature into MP int */
 424   for (i = 0; i < signature_len; i++) {
 425     silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
 426     silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
 427   }
 428
 429   /* Verify */
 430   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 431
 432   /* Format the data into MP int */
 433   for (i = 0; i < data_len; i++) {
 434     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 435     silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
 436   }
 437
 438   ret = TRUE;
 439
 440   /* Compare */
 441   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 442     ret = FALSE;
 443
 444   silc_mp_uninit(&mp_tmp);
 445   silc_mp_uninit(&mp_tmp2);
 446   silc_mp_uninit(&mp_dst);
 447
 448   return ret;
 449 }
 450
 451 /* Generates RSA public and private keys. Primes p and q that are used
 452    to compute the modulus n has to be generated before calling this. They
 453    are then sent as argument for the function. */
 454
 455 void rsa_generate_keys(RsaKey *key, uint32 bits,
 456                        SilcMPInt *p, SilcMPInt *q)
 457 {
 458   SilcMPInt phi, hlp;
 459   SilcMPInt div, lcm;
 460   SilcMPInt pm1, qm1;
 461
 462   /* Initialize variables */
 463   silc_mp_init(&key->p);
 464   silc_mp_init(&key->q);
 465   silc_mp_init(&key->n);
 466   silc_mp_init(&key->e);
 467   silc_mp_init(&key->d);
 468   silc_mp_init(&phi);
 469   silc_mp_init(&hlp);
 470   silc_mp_init(&div);
 471   silc_mp_init(&lcm);
 472   silc_mp_init(&pm1);
 473   silc_mp_init(&qm1);
 474
 475   /* Set modulus length */
 476   key->bits = bits;
 477
 478   /* Set the primes */
 479   silc_mp_set(&key->p, p);
 480   silc_mp_set(&key->q, q);
 481
 482   /* Compute modulus, n = p * q */
 483   silc_mp_mul(&key->n, &key->p, &key->q);
 484
 485   /* phi = (p - 1) * (q - 1) */
 486   silc_mp_sub_ui(&pm1, &key->p, 1);
 487   silc_mp_sub_ui(&qm1, &key->q, 1);
 488   silc_mp_mul(&phi, &pm1, &qm1);
 489
 490   /* Set e, the public exponent. We try to use same public exponent
 491      for all keys. Also, to make encryption faster we use small
 492      number. */
 493   silc_mp_set_ui(&key->e, 127);
 494  retry_e:
 495   /* See if e is relatively prime to phi. gcd == greates common divisor,
 496      if gcd equals 1 they are relatively prime. */
 497   silc_mp_gcd(&hlp, &key->e, &phi);
 498   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 499     silc_mp_add_ui(&key->e, &key->e, 2);
 500     goto retry_e;
 501   }
 502
 503   /* Find d, the private exponent. */
 504   silc_mp_gcd(&div, &pm1, &qm1);
 505   silc_mp_div(&lcm, &phi, &div);
 506   silc_mp_modinv(&key->d, &key->e, &lcm);
 507
 508   silc_mp_uninit(&phi);
 509   silc_mp_uninit(&hlp);
 510   silc_mp_uninit(&div);
 511   silc_mp_uninit(&lcm);
 512   silc_mp_uninit(&pm1);
 513   silc_mp_uninit(&qm1);
 514 }
 515
 516 /* Clears whole key structure. */
 517
 518 void rsa_clear_keys(RsaKey *key)
 519 {
 520   key->bits = 0;
 521   silc_mp_uninit(&key->p);
 522   silc_mp_uninit(&key->q);
 523   silc_mp_uninit(&key->n);
 524   silc_mp_uninit(&key->e);
 525   silc_mp_uninit(&key->d);
 526 }
 527
 528 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 529    mc = plaintext or ciphertext, expo = public or private exponent,
 530    and modu = modulus.
 531
 532    Encrypt: c = m ^ e mod n,
 533    Decrypt: m = c ^ d mod n
 534 */
 535
 536 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
 537                      SilcMPInt *expo, SilcMPInt *modu)
 538 {
 539   silc_mp_pow_mod(cm, mc, expo, modu);
 540 }