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_DATA_CONTEXT_LEN(rsa)
 302 {
 303   return sizeof(RsaDataContext);
 304 }
 305
 306 SILC_PKCS_API_SET_ARG(rsa)
 307 {
 308   RsaDataContext *data_ctx = (RsaDataContext *)data_context;
 309
 310   switch(argnum) {
 311   case 1:
 312     data_ctx->src = val;
 313     return TRUE;
 314     break;
 315   case 2:
 316     data_ctx->dst = val;
 317     return TRUE;
 318     break;
 319   case 3:
 320     data_ctx->exp = val;
 321     return TRUE;
 322     break;
 323   case 4:
 324     data_ctx->mod = val;
 325     return TRUE;
 326     break;
 327   default:
 328     return FALSE;
 329     break;
 330   }
 331
 332   return FALSE;
 333 }
 334
 335 SILC_PKCS_API_ENCRYPT(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   /* Encrypt */
 352   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &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_DECRYPT(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   /* Decrypt */
 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_SIGN(rsa)
 404 {
 405   RsaKey *key = (RsaKey *)context;
 406   int i, tmplen;
 407   SilcInt mp_tmp;
 408   SilcInt mp_dst;
 409
 410   silc_mp_init_set_ui(&mp_tmp, 0);
 411   silc_mp_init_set_ui(&mp_dst, 0);
 412
 413   /* Format the data into MP int */
 414   for (i = 0; i < src_len; i++) {
 415     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 416     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 417   }
 418
 419   /* Sign */
 420   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 421
 422   tmplen = (key->bits + 7) / 8;
 423
 424   /* Format the MP int back into data */
 425   for (i = tmplen; i > 0; i--) {
 426     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 427     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 428   }
 429   *dst_len = tmplen;
 430
 431   silc_mp_clear(&mp_tmp);
 432   silc_mp_clear(&mp_dst);
 433
 434   return TRUE;
 435 }
 436
 437 SILC_PKCS_API_VERIFY(rsa)
 438 {
 439   RsaKey *key = (RsaKey *)context;
 440   int i, ret;
 441   SilcInt mp_tmp, mp_tmp2;
 442   SilcInt mp_dst;
 443
 444   silc_mp_init_set_ui(&mp_tmp, 0);
 445   silc_mp_init_set_ui(&mp_tmp2, 0);
 446   silc_mp_init_set_ui(&mp_dst, 0);
 447
 448   /* Format the signature into MP int */
 449   for (i = 0; i < signature_len; i++) {
 450     silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
 451     silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
 452   }
 453
 454   /* Verify */
 455   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 456
 457   /* Format the data into MP int */
 458   for (i = 0; i < data_len; i++) {
 459     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 460     silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
 461   }
 462
 463   ret = TRUE;
 464
 465   /* Compare */
 466   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 467     ret = FALSE;
 468
 469   silc_mp_clear(&mp_tmp);
 470   silc_mp_clear(&mp_tmp2);
 471   silc_mp_clear(&mp_dst);
 472
 473   return ret;
 474 }
 475
 476 /* Generates RSA public and private keys. Primes p and q that are used
 477    to compute the modulus n has to be generated before calling this. They
 478    are then sent as argument for the function. */
 479
 480 void rsa_generate_keys(RsaKey *key, uint32 bits,
 481                        SilcInt *p, SilcInt *q)
 482 {
 483   SilcInt phi, hlp;
 484   SilcInt div, lcm;
 485   SilcInt pm1, qm1;
 486
 487   /* Initialize variables */
 488   silc_mp_init(&key->p);
 489   silc_mp_init(&key->q);
 490   silc_mp_init(&key->n);
 491   silc_mp_init(&key->e);
 492   silc_mp_init(&key->d);
 493   silc_mp_init(&phi);
 494   silc_mp_init(&hlp);
 495   silc_mp_init(&div);
 496   silc_mp_init(&lcm);
 497   silc_mp_init(&pm1);
 498   silc_mp_init(&qm1);
 499
 500   /* Set modulus length */
 501   key->bits = bits;
 502
 503   /* Set the primes */
 504   silc_mp_set(&key->p, p);
 505   silc_mp_set(&key->q, q);
 506
 507   /* Compute modulus, n = p * q */
 508   silc_mp_mul(&key->n, &key->p, &key->q);
 509
 510   /* phi = (p - 1) * (q - 1) */
 511   silc_mp_sub_ui(&pm1, &key->p, 1);
 512   silc_mp_sub_ui(&qm1, &key->q, 1);
 513   silc_mp_mul(&phi, &pm1, &qm1);
 514
 515   /* Set e, the public exponent. We try to use same public exponent
 516      for all keys. Also, to make encryption faster we use small
 517      number. */
 518   silc_mp_set_ui(&key->e, 127);
 519  retry_e:
 520   /* See if e is relatively prime to phi. gcd == greates common divisor,
 521      if gcd equals 1 they are relatively prime. */
 522   silc_mp_gcd(&hlp, &key->e, &phi);
 523   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 524     silc_mp_add_ui(&key->e, &key->e, 2);
 525     goto retry_e;
 526   }
 527
 528   /* Find d, the private exponent. */
 529   silc_mp_gcd(&div, &pm1, &qm1);
 530   silc_mp_fdiv_q(&lcm, &phi, &div);
 531   silc_mp_modinv(&key->d, &key->e, &lcm);
 532
 533   silc_mp_clear(&phi);
 534   silc_mp_clear(&hlp);
 535   silc_mp_clear(&div);
 536   silc_mp_clear(&lcm);
 537   silc_mp_clear(&pm1);
 538   silc_mp_clear(&qm1);
 539 }
 540
 541 /* Clears whole key structure. */
 542
 543 void rsa_clear_keys(RsaKey *key)
 544 {
 545   key->bits = 0;
 546   silc_mp_clear(&key->p);
 547   silc_mp_clear(&key->q);
 548   silc_mp_clear(&key->n);
 549   silc_mp_clear(&key->e);
 550   silc_mp_clear(&key->d);
 551 }
 552
 553 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 554    mc = plaintext or ciphertext, expo = public or private exponent,
 555    and modu = modulus.
 556
 557    Encrypt: c = m ^ e mod n,
 558    Decrypt: m = c ^ d mod n
 559 */
 560
 561 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
 562                      SilcInt *expo, SilcInt *modu)
 563 {
 564   silc_mp_powm(cm, mc, expo, modu);
 565 }