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 short 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 short 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 short 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   if (e_len > key_len) {
 222     silc_mp_clear(&key->e);
 223     silc_mp_clear(&key->n);
 224     return FALSE;
 225   }
 226
 227   e = silc_calloc(e_len + 1, sizeof(unsigned char));
 228   memcpy(e, key_data + 2, e_len);
 229   silc_mp_set_str(&key->e, e, 16);
 230
 231   memcpy(tmp, key_data + 2 + e_len, 2);
 232   n_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 233   if (e_len + n_len > key_len) {
 234     memset(e, 0, e_len);
 235     silc_free(e);
 236     silc_mp_clear(&key->e);
 237     silc_mp_clear(&key->n);
 238     return FALSE;
 239   }
 240
 241   n = silc_calloc(n_len + 1, sizeof(unsigned char));
 242   memcpy(n, key_data + 2 + e_len + 2, n_len);
 243   silc_mp_set_str(&key->n, n, 16);
 244
 245   memset(e, 0, e_len);
 246   memset(n, 0, n_len);
 247   silc_free(e);
 248   silc_free(n);
 249
 250   return TRUE;
 251 }
 252
 253 /* Set private key. This derives the public key from the private
 254    key and sets the public key as well. Public key should not be set
 255    already and should not be set after setting private key. */
 256
 257 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
 258 {
 259   RsaKey *key = (RsaKey *)context;
 260   unsigned char *e, *n, *d, tmp[2];
 261   unsigned short e_len, n_len, d_len;
 262
 263   silc_mp_init(&key->e);
 264   silc_mp_init(&key->n);
 265   silc_mp_init(&key->d);
 266
 267   memcpy(tmp, key_data, 2);
 268   e_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 269   if (e_len > key_len) {
 270     silc_mp_clear(&key->e);
 271     silc_mp_clear(&key->n);
 272     return FALSE;
 273   }
 274
 275   e = silc_calloc(e_len + 1, sizeof(unsigned char));
 276   memcpy(e, key_data + 2, e_len);
 277   silc_mp_set_str(&key->e, e, 16);
 278
 279   memcpy(tmp, key_data + 2 + e_len, 2);
 280   n_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 281   if (e_len + n_len > key_len) {
 282     memset(e, 0, e_len);
 283     silc_free(e);
 284     silc_mp_clear(&key->e);
 285     silc_mp_clear(&key->n);
 286     return FALSE;
 287   }
 288
 289   n = silc_calloc(n_len + 1, sizeof(unsigned char));
 290   memcpy(n, key_data + 2 + e_len + 2, n_len);
 291   silc_mp_set_str(&key->n, n, 16);
 292
 293   memcpy(tmp, key_data + 2 + e_len + 2 + n_len, 2);
 294   d_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
 295   if (e_len + n_len + d_len > key_len) {
 296     memset(n, 0, n_len);
 297     silc_free(n);
 298     memset(e, 0, e_len);
 299     silc_free(e);
 300     silc_mp_clear(&key->e);
 301     silc_mp_clear(&key->n);
 302     return FALSE;
 303   }
 304
 305   d = silc_calloc(d_len + 1, sizeof(unsigned char));
 306   memcpy(d, key_data + 2 + e_len + 2 + n_len + 2, d_len);
 307   silc_mp_set_str(&key->d, d, 16);
 308
 309   memset(e, 0, e_len);
 310   memset(n, 0, n_len);
 311   memset(d, 0, d_len);
 312   silc_free(e);
 313   silc_free(n);
 314   silc_free(d);
 315
 316   return TRUE;
 317 }
 318
 319 SILC_PKCS_API_CONTEXT_LEN(rsa)
 320 {
 321   return sizeof(RsaKey);
 322 }
 323
 324 SILC_PKCS_API_DATA_CONTEXT_LEN(rsa)
 325 {
 326   return sizeof(RsaDataContext);
 327 }
 328
 329 SILC_PKCS_API_SET_ARG(rsa)
 330 {
 331   RsaDataContext *data_ctx = (RsaDataContext *)data_context;
 332
 333   switch(argnum) {
 334   case 1:
 335     data_ctx->src = val;
 336     return TRUE;
 337     break;
 338   case 2:
 339     data_ctx->dst = val;
 340     return TRUE;
 341     break;
 342   case 3:
 343     data_ctx->exp = val;
 344     return TRUE;
 345     break;
 346   case 4:
 347     data_ctx->mod = val;
 348     return TRUE;
 349     break;
 350   default:
 351     return FALSE;
 352     break;
 353   }
 354
 355   return FALSE;
 356 }
 357
 358 SILC_PKCS_API_ENCRYPT(rsa)
 359 {
 360   RsaKey *key = (RsaKey *)context;
 361   int i, tmplen;
 362   SilcInt mp_tmp;
 363   SilcInt mp_dst;
 364
 365   silc_mp_init_set_ui(&mp_tmp, 0);
 366   silc_mp_init_set_ui(&mp_dst, 0);
 367
 368   /* Format the data into MP int */
 369   for (i = 0; i < src_len; i++) {
 370     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 371     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 372   }
 373
 374   silc_mp_out_str(stderr, 16, &mp_tmp);
 375
 376   /* Encrypt */
 377   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 378
 379   fprintf(stderr, "\n");
 380   silc_mp_out_str(stderr, 16, &mp_dst);
 381
 382   tmplen = (1024 + 7) / 8;
 383
 384   /* Format the MP int back into data */
 385   for (i = tmplen; i > 0; i--) {
 386     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 387     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 388   }
 389   *dst_len = tmplen;
 390
 391   silc_mp_clear(&mp_tmp);
 392   silc_mp_clear(&mp_dst);
 393
 394   return TRUE;
 395 }
 396
 397 SILC_PKCS_API_DECRYPT(rsa)
 398 {
 399   RsaKey *key = (RsaKey *)context;
 400   int i, tmplen;
 401   SilcInt mp_tmp;
 402   SilcInt mp_dst;
 403
 404   silc_mp_init_set_ui(&mp_tmp, 0);
 405   silc_mp_init_set_ui(&mp_dst, 0);
 406
 407   /* Format the data into MP int */
 408   for (i = 0; i < src_len; i++) {
 409     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 410     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 411   }
 412
 413   silc_mp_out_str(stderr, 16, &mp_tmp);
 414
 415   /* Decrypt */
 416   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 417
 418   fprintf(stderr, "\n");
 419   silc_mp_out_str(stderr, 16, &mp_dst);
 420
 421   tmplen = (1024 + 7) / 8;
 422
 423   /* Format the MP int back into data */
 424   for (i = tmplen; i > 0; i--) {
 425     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 426     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 427   }
 428   *dst_len = tmplen;
 429
 430   silc_mp_clear(&mp_tmp);
 431   silc_mp_clear(&mp_dst);
 432
 433   return TRUE;
 434 }
 435
 436 SILC_PKCS_API_SIGN(rsa)
 437 {
 438   RsaKey *key = (RsaKey *)context;
 439   int i, tmplen;
 440   SilcInt mp_tmp;
 441   SilcInt mp_dst;
 442
 443   silc_mp_init_set_ui(&mp_tmp, 0);
 444   silc_mp_init_set_ui(&mp_dst, 0);
 445
 446   /* Format the data into MP int */
 447   for (i = 0; i < src_len; i++) {
 448     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 449     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 450   }
 451
 452   /* Sign */
 453   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 454
 455   tmplen = (1024 + 7) / 8;
 456
 457   /* Format the MP int back into data */
 458   for (i = tmplen; i > 0; i--) {
 459     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 460     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 461   }
 462   *dst_len = tmplen;
 463
 464   silc_mp_clear(&mp_tmp);
 465   silc_mp_clear(&mp_dst);
 466
 467   return TRUE;
 468 }
 469
 470 SILC_PKCS_API_VERIFY(rsa)
 471 {
 472   RsaKey *key = (RsaKey *)context;
 473   int i, ret;
 474   SilcInt mp_tmp, mp_tmp2;
 475   SilcInt mp_dst;
 476
 477   silc_mp_init_set_ui(&mp_tmp, 0);
 478   silc_mp_init_set_ui(&mp_tmp2, 0);
 479   silc_mp_init_set_ui(&mp_dst, 0);
 480
 481   /* Format the signature into MP int */
 482   for (i = 0; i < signature_len; i++) {
 483     silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
 484     silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
 485   }
 486
 487   /* Verify */
 488   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 489
 490   /* Format the data into MP int */
 491   for (i = 0; i < data_len; i++) {
 492     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 493     silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
 494   }
 495
 496   ret = TRUE;
 497
 498   /* Compare */
 499   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 500     ret = FALSE;
 501
 502   silc_mp_clear(&mp_tmp);
 503   silc_mp_clear(&mp_tmp2);
 504   silc_mp_clear(&mp_dst);
 505
 506   return ret;
 507 }
 508
 509 /* Generates RSA public and private keys. Primes p and q that are used
 510    to compute the modulus n has to be generated before calling this. They
 511    are then sent as argument for the function. */
 512
 513 void rsa_generate_keys(RsaKey *key, unsigned int bits,
 514                        SilcInt *p, SilcInt *q)
 515 {
 516   SilcInt phi, hlp;
 517   SilcInt dq;
 518   SilcInt pm1, qm1;
 519
 520   /* Initialize variables */
 521   silc_mp_init(&key->p);
 522   silc_mp_init(&key->q);
 523   silc_mp_init(&key->n);
 524   silc_mp_init(&key->e);
 525   silc_mp_init(&key->d);
 526   silc_mp_init(&phi);
 527   silc_mp_init(&hlp);
 528   silc_mp_init(&dq);
 529   silc_mp_init(&pm1);
 530   silc_mp_init(&qm1);
 531
 532   /* Set the primes */
 533   silc_mp_set(&key->p, p);
 534   silc_mp_set(&key->q, q);
 535
 536   /* Compute modulus, n = p * q */
 537   silc_mp_mul(&key->n, &key->p, &key->q);
 538
 539   /* phi = (p - 1) * (q - 1) */
 540   silc_mp_sub_ui(&pm1, &key->p, 1);
 541   silc_mp_sub_ui(&qm1, &key->q, 1);
 542   silc_mp_mul(&phi, &pm1, &qm1);
 543
 544   /* Set e, the public exponent. We try to use same public exponent
 545      for all keys. Also, to make encryption faster we use small
 546      number. */
 547   silc_mp_set_ui(&key->e, 127);
 548  retry_e:
 549   /* See if e is relatively prime to phi. gcd == greates common divisor,
 550      if gcd equals 1 they are relatively prime. */
 551   silc_mp_gcd(&hlp, &key->e, &phi);
 552   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 553     silc_mp_add_ui(&key->e, &key->e, 2);
 554     goto retry_e;
 555   }
 556
 557   /* Find d, the private exponent. First we do phi / 2, to get it a
 558      bit smaller */
 559   silc_mp_div_ui(&dq, &phi, 2);
 560   silc_mp_modinv(&key->d, &key->e, &dq);
 561
 562   silc_mp_clear(&phi);
 563   silc_mp_clear(&hlp);
 564   silc_mp_clear(&dq);
 565   silc_mp_clear(&pm1);
 566   silc_mp_clear(&qm1);
 567 }
 568
 569 /* Clears whole key structure. */
 570
 571 void rsa_clear_keys(RsaKey *key)
 572 {
 573   key->bits = 0;
 574   silc_mp_clear(&key->p);
 575   silc_mp_clear(&key->q);
 576   silc_mp_clear(&key->n);
 577   silc_mp_clear(&key->e);
 578   silc_mp_clear(&key->d);
 579 }
 580
 581 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 582    mc = plaintext or ciphertext, expo = public or private exponent,
 583    and modu = modulus.
 584
 585    Encrypt: c = m ^ e mod n,
 586    Decrypt: m = c ^ d mod n
 587 */
 588
 589 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
 590                      SilcInt *expo, SilcInt *modu)
 591 {
 592   silc_mp_powm(cm, mc, expo, modu);
 593 }