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