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_len = silc_mp_sizeinbase(&key->e, 16);
 117   n_len = silc_mp_sizeinbase(&key->n, 16);
 118   e = silc_calloc(e_len + 1, sizeof(unsigned char));
 119   n = silc_calloc(n_len + 1, sizeof(unsigned char));
 120   silc_mp_get_str(e, 16, &key->e);
 121   silc_mp_get_str(n, 16, &key->n);
 122
 123   *ret_len = e_len + 2 + n_len + 2;
 124   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 125
 126   /* Put the length of the e. */
 127   tmp[0] = e_len >> 8;
 128   tmp[1] = e_len;
 129   memcpy(ret, tmp, 2);
 130
 131   /* Put the e. */
 132   memcpy(ret + 2, e, e_len);
 133
 134   /* Put the length of the n. */
 135   tmp[0] = n_len >> 8;
 136   tmp[1] = n_len;
 137   memcpy(ret + 2 + e_len, tmp, 2);
 138
 139   /* Put the n. */
 140   memcpy(ret + 2 + e_len + 2, n, n_len);
 141
 142   memset(e, 0, e_len);
 143   memset(n, 0, n_len);
 144   silc_free(e);
 145   silc_free(n);
 146
 147   return ret;
 148 }
 149
 150 /* Returns SILC style encoded RSA private key. Public key is always
 151    returned in private key as well. Public keys are often derived
 152    directly from private key. */
 153
 154 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
 155 {
 156   RsaKey *key = (RsaKey *)context;
 157   unsigned char *e, *n, *d, *ret;
 158   unsigned int e_len, n_len, d_len;
 159   unsigned char tmp[2];
 160
 161   e_len = silc_mp_sizeinbase(&key->e, 16);
 162   n_len = silc_mp_sizeinbase(&key->n, 16);
 163   d_len = silc_mp_sizeinbase(&key->d, 16);
 164   e = silc_calloc(e_len + 1, sizeof(unsigned char));
 165   n = silc_calloc(n_len + 1, sizeof(unsigned char));
 166   d = silc_calloc(d_len + 1, sizeof(unsigned char));
 167   silc_mp_get_str(e, 16, &key->e);
 168   silc_mp_get_str(n, 16, &key->n);
 169   silc_mp_get_str(d, 16, &key->d);
 170
 171   *ret_len = e_len + 2 + n_len + 2 + d_len + 2;
 172   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 173
 174   /* Put the length of the e. */
 175   tmp[0] = e_len >> 8;
 176   tmp[1] = e_len;
 177   memcpy(ret, tmp, 2);
 178
 179   /* Put the e. */
 180   memcpy(ret + 2, e, e_len);
 181
 182   /* Put the length of the n. */
 183   tmp[0] = n_len >> 8;
 184   tmp[1] = n_len;
 185   memcpy(ret + 2 + e_len, tmp, 2);
 186
 187   /* Put the n. */
 188   memcpy(ret + 2 + e_len + 2, n, n_len);
 189
 190   /* Put the length of the d. */
 191   tmp[0] = d_len >> 8;
 192   tmp[1] = d_len;
 193   memcpy(ret + 2 + e_len + 2 + n_len, tmp, 2);
 194
 195   /* Put the n. */
 196   memcpy(ret + 2 + e_len + 2 + n_len + 2, d, d_len);
 197
 198   memset(e, 0, e_len);
 199   memset(n, 0, n_len);
 200   memset(d, 0, d_len);
 201   silc_free(e);
 202   silc_free(n);
 203   silc_free(d);
 204
 205   return ret;
 206 }
 207
 208 /* Set public key */
 209
 210 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
 211 {
 212   RsaKey *key = (RsaKey *)context;
 213   unsigned char *e, *n, tmp[2];
 214   unsigned int e_len, n_len;
 215
 216   silc_mp_init(&key->e);
 217   silc_mp_init(&key->n);
 218
 219   memcpy(tmp, key_data, 2);
 220   e_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 221
 222   e = silc_calloc(e_len + 1, sizeof(unsigned char));
 223   memcpy(e, key_data + 2, e_len);
 224   silc_mp_set_str(&key->e, e, 16);
 225
 226   memcpy(tmp, key_data + 2 + e_len, 2);
 227   n_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 228
 229   n = silc_calloc(n_len + 1, sizeof(unsigned char));
 230   memcpy(n, key_data + 2 + e_len + 2, n_len);
 231   silc_mp_set_str(&key->n, n, 16);
 232
 233   memset(e, 0, e_len);
 234   memset(n, 0, n_len);
 235   silc_free(e);
 236   silc_free(n);
 237
 238   return TRUE;
 239 }
 240
 241 /* Set private key. This derives the public key from the private
 242    key and sets the public key as well. Public key should not be set
 243    already and should not be set after setting private key. */
 244
 245 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
 246 {
 247   RsaKey *key = (RsaKey *)context;
 248   unsigned char *e, *n, *d, tmp[2];
 249   unsigned int e_len, n_len, d_len;
 250
 251   silc_mp_init(&key->e);
 252   silc_mp_init(&key->n);
 253   silc_mp_init(&key->d);
 254
 255   memcpy(tmp, key_data, 2);
 256   e_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 257
 258   e = silc_calloc(e_len + 1, sizeof(unsigned char));
 259   memcpy(e, key_data + 2, e_len);
 260   silc_mp_set_str(&key->e, e, 16);
 261
 262   memcpy(tmp, key_data + 2 + e_len, 2);
 263   n_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 264
 265   n = silc_calloc(n_len + 1, sizeof(unsigned char));
 266   memcpy(n, key_data + 2 + e_len + 2, n_len);
 267   silc_mp_set_str(&key->n, n, 16);
 268
 269   memcpy(tmp, key_data + 2 + e_len + 2 + n_len, 2);
 270   d_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 271
 272   d = silc_calloc(d_len + 1, sizeof(unsigned char));
 273   memcpy(d, key_data + 2 + e_len + 2 + n_len + 2, d_len);
 274   silc_mp_set_str(&key->d, d, 16);
 275
 276   memset(e, 0, e_len);
 277   memset(n, 0, n_len);
 278   memset(d, 0, d_len);
 279   silc_free(e);
 280   silc_free(n);
 281   silc_free(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   silc_mp_out_str(stderr, 16, &mp_tmp);
 342
 343   /* Encrypt */
 344   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 345
 346   fprintf(stderr, "\n");
 347   silc_mp_out_str(stderr, 16, &mp_dst);
 348
 349   tmplen = (1024 + 7) / 8;
 350
 351   /* Format the MP int back into data */
 352   for (i = tmplen; i > 0; i--) {
 353     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 354     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 355   }
 356   *dst_len = tmplen;
 357
 358   silc_mp_clear(&mp_tmp);
 359   silc_mp_clear(&mp_dst);
 360
 361   return TRUE;
 362 }
 363
 364 SILC_PKCS_API_DECRYPT(rsa)
 365 {
 366   RsaKey *key = (RsaKey *)context;
 367   int i, tmplen;
 368   SilcInt mp_tmp;
 369   SilcInt mp_dst;
 370
 371   silc_mp_init_set_ui(&mp_tmp, 0);
 372   silc_mp_init_set_ui(&mp_dst, 0);
 373
 374   /* Format the data into MP int */
 375   for (i = 0; i < src_len; i++) {
 376     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 377     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 378   }
 379
 380   silc_mp_out_str(stderr, 16, &mp_tmp);
 381
 382   /* Decrypt */
 383   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 384
 385   fprintf(stderr, "\n");
 386   silc_mp_out_str(stderr, 16, &mp_dst);
 387
 388   tmplen = (1024 + 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 = (1024 + 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, unsigned int bits,
 481                        SilcInt *p, SilcInt *q)
 482 {
 483   SilcInt phi, hlp;
 484   SilcInt dq;
 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(&dq);
 496   silc_mp_init(&pm1);
 497   silc_mp_init(&qm1);
 498
 499   /* Set the primes */
 500   silc_mp_set(&key->p, p);
 501   silc_mp_set(&key->q, q);
 502
 503   /* Compute modulus, n = p * q */
 504   silc_mp_mul(&key->n, &key->p, &key->q);
 505
 506   /* phi = (p - 1) * (q - 1) */
 507   silc_mp_sub_ui(&pm1, &key->p, 1);
 508   silc_mp_sub_ui(&qm1, &key->q, 1);
 509   silc_mp_mul(&phi, &pm1, &qm1);
 510
 511   /* Set e, the public exponent. We try to use same public exponent
 512      for all keys. Also, to make encryption faster we use small
 513      number. */
 514   silc_mp_set_ui(&key->e, 127);
 515  retry_e:
 516   /* See if e is relatively prime to phi. gcd == greates common divisor,
 517      if gcd equals 1 they are relatively prime. */
 518   silc_mp_gcd(&hlp, &key->e, &phi);
 519   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 520     silc_mp_add_ui(&key->e, &key->e, 2);
 521     goto retry_e;
 522   }
 523
 524   /* Find d, the private exponent. First we do phi / 2, to get it a
 525      bit smaller */
 526   silc_mp_div_ui(&dq, &phi, 2);
 527   silc_mp_modinv(&key->d, &key->e, &dq);
 528
 529   silc_mp_clear(&phi);
 530   silc_mp_clear(&hlp);
 531   silc_mp_clear(&dq);
 532   silc_mp_clear(&pm1);
 533   silc_mp_clear(&qm1);
 534 }
 535
 536 /* Clears whole key structure. */
 537
 538 void rsa_clear_keys(RsaKey *key)
 539 {
 540   key->bits = 0;
 541   silc_mp_clear(&key->p);
 542   silc_mp_clear(&key->q);
 543   silc_mp_clear(&key->n);
 544   silc_mp_clear(&key->e);
 545   silc_mp_clear(&key->d);
 546 }
 547
 548 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 549    mc = plaintext or ciphertext, expo = public or private exponent,
 550    and modu = modulus.
 551
 552    Encrypt: c = m ^ e mod n,
 553    Decrypt: m = c ^ d mod n
 554 */
 555
 556 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
 557                      SilcInt *expo, SilcInt *modu)
 558 {
 559   silc_mp_powm(cm, mc, expo, modu);
 560 }