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