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   silc_mp_out_str(stderr, 16, &mp_tmp);
 331
 332   /* Encrypt */
 333   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
 334
 335   fprintf(stderr, "\n");
 336   silc_mp_out_str(stderr, 16, &mp_dst);
 337
 338   tmplen = (1024 + 7) / 8;
 339
 340   /* Format the MP int back into data */
 341   for (i = tmplen; i > 0; i--) {
 342     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 343     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 344   }
 345   *dst_len = tmplen;
 346
 347   silc_mp_clear(&mp_tmp);
 348   silc_mp_clear(&mp_dst);
 349
 350   return TRUE;
 351 }
 352
 353 SILC_PKCS_API_DECRYPT(rsa)
 354 {
 355   RsaKey *key = (RsaKey *)context;
 356   int i, tmplen;
 357   SilcInt mp_tmp;
 358   SilcInt mp_dst;
 359
 360   silc_mp_init_set_ui(&mp_tmp, 0);
 361   silc_mp_init_set_ui(&mp_dst, 0);
 362
 363   /* Format the data into MP int */
 364   for (i = 0; i < src_len; i++) {
 365     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 366     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 367   }
 368
 369   silc_mp_out_str(stderr, 16, &mp_tmp);
 370
 371   /* Decrypt */
 372   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 373
 374   fprintf(stderr, "\n");
 375   silc_mp_out_str(stderr, 16, &mp_dst);
 376
 377   tmplen = (1024 + 7) / 8;
 378
 379   /* Format the MP int back into data */
 380   for (i = tmplen; i > 0; i--) {
 381     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 382     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 383   }
 384   *dst_len = tmplen;
 385
 386   silc_mp_clear(&mp_tmp);
 387   silc_mp_clear(&mp_dst);
 388
 389   return TRUE;
 390 }
 391
 392 SILC_PKCS_API_SIGN(rsa)
 393 {
 394   RsaKey *key = (RsaKey *)context;
 395   int i, tmplen;
 396   SilcInt mp_tmp;
 397   SilcInt mp_dst;
 398
 399   silc_mp_init_set_ui(&mp_tmp, 0);
 400   silc_mp_init_set_ui(&mp_dst, 0);
 401
 402   /* Format the data into MP int */
 403   for (i = 0; i < src_len; i++) {
 404     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 405     silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
 406   }
 407
 408   /* Sign */
 409   rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
 410
 411   tmplen = (1024 + 7) / 8;
 412
 413   /* Format the MP int back into data */
 414   for (i = tmplen; i > 0; i--) {
 415     dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
 416     silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
 417   }
 418   *dst_len = tmplen;
 419
 420   silc_mp_clear(&mp_tmp);
 421   silc_mp_clear(&mp_dst);
 422
 423   return TRUE;
 424 }
 425
 426 SILC_PKCS_API_VERIFY(rsa)
 427 {
 428   RsaKey *key = (RsaKey *)context;
 429   int i, ret;
 430   SilcInt mp_tmp, mp_tmp2;
 431   SilcInt mp_dst;
 432
 433   silc_mp_init_set_ui(&mp_tmp, 0);
 434   silc_mp_init_set_ui(&mp_tmp2, 0);
 435   silc_mp_init_set_ui(&mp_dst, 0);
 436
 437   /* Format the signature into MP int */
 438   for (i = 0; i < signature_len; i++) {
 439     silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
 440     silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
 441   }
 442
 443   /* Verify */
 444   rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
 445
 446   /* Format the data into MP int */
 447   for (i = 0; i < data_len; i++) {
 448     silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
 449     silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
 450   }
 451
 452   ret = TRUE;
 453
 454   /* Compare */
 455   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 456     ret = FALSE;
 457
 458   silc_mp_clear(&mp_tmp);
 459   silc_mp_clear(&mp_tmp2);
 460   silc_mp_clear(&mp_dst);
 461
 462   return ret;
 463 }
 464
 465 /* Generates RSA public and private keys. Primes p and q that are used
 466    to compute the modulus n has to be generated before calling this. They
 467    are then sent as argument for the function. */
 468
 469 void rsa_generate_keys(RsaKey *key, unsigned int bits,
 470                        SilcInt *p, SilcInt *q)
 471 {
 472   SilcInt phi, hlp;
 473   SilcInt dq;
 474   SilcInt pm1, qm1;
 475
 476   /* Initialize variables */
 477   silc_mp_init(&key->p);
 478   silc_mp_init(&key->q);
 479   silc_mp_init(&key->n);
 480   silc_mp_init(&key->e);
 481   silc_mp_init(&key->d);
 482   silc_mp_init(&phi);
 483   silc_mp_init(&hlp);
 484   silc_mp_init(&dq);
 485   silc_mp_init(&pm1);
 486   silc_mp_init(&qm1);
 487
 488   /* Set the primes */
 489   silc_mp_set(&key->p, p);
 490   silc_mp_set(&key->q, q);
 491
 492   /* Compute modulus, n = p * q */
 493   silc_mp_mul(&key->n, &key->p, &key->q);
 494
 495   /* phi = (p - 1) * (q - 1) */
 496   silc_mp_sub_ui(&pm1, &key->p, 1);
 497   silc_mp_sub_ui(&qm1, &key->q, 1);
 498   silc_mp_mul(&phi, &pm1, &qm1);
 499
 500   /* Set e, the public exponent. We try to use same public exponent
 501      for all keys. Also, to make encryption faster we use small
 502      number. */
 503   silc_mp_set_ui(&key->e, 127);
 504  retry_e:
 505   /* See if e is relatively prime to phi. gcd == greates common divisor,
 506      if gcd equals 1 they are relatively prime. */
 507   silc_mp_gcd(&hlp, &key->e, &phi);
 508   if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 509     silc_mp_add_ui(&key->e, &key->e, 2);
 510     goto retry_e;
 511   }
 512
 513   /* Find d, the private exponent. First we do phi / 2, to get it a
 514      bit smaller */
 515   silc_mp_div_ui(&dq, &phi, 2);
 516   silc_mp_modinv(&key->d, &key->e, &dq);
 517
 518   silc_mp_clear(&phi);
 519   silc_mp_clear(&hlp);
 520   silc_mp_clear(&dq);
 521   silc_mp_clear(&pm1);
 522   silc_mp_clear(&qm1);
 523 }
 524
 525 /* Clears whole key structure. */
 526
 527 void rsa_clear_keys(RsaKey *key)
 528 {
 529   key->bits = 0;
 530   silc_mp_clear(&key->p);
 531   silc_mp_clear(&key->q);
 532   silc_mp_clear(&key->n);
 533   silc_mp_clear(&key->e);
 534   silc_mp_clear(&key->d);
 535 }
 536
 537 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
 538    mc = plaintext or ciphertext, expo = public or private exponent,
 539    and modu = modulus.
 540
 541    Encrypt: c = m ^ e mod n,
 542    Decrypt: m = c ^ d mod n
 543 */
 544
 545 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
 546                      SilcInt *expo, SilcInt *modu)
 547 {
 548   silc_mp_powm(cm, mc, expo, modu);
 549 }