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