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@silcnet.org>
   6  *
   7  * Copyright (C) 1997 - 2003 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 lcm(((p-1) * (q-1)))
  32  *
  33  *      Encryption:
  34  *      c = m ^ e mod n
  35  *      Decryption:
  36  *      m = c ^ d mod n
  37  *
  38  * Supports CRT (Chinese Remainder Theorem) for private key operations.
  39  *
  40  * The SSH's (Secure Shell), PGP's (Pretty Good Privacy) and RSAREF
  41  * Toolkit were used as reference when coding this implementation. They
  42  * all were a big help for me.
  43  *
  44  * I also suggest reading Bruce Schneier's; Applied Cryptography, Second
  45  * Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and
  46  * everything else too about cryptography.
  47  *
  48  */
  49 /* $Id$ */
  50
  51 /*
  52    ChangeLog
  53
  54    o Mon Feb 12 11:20:32 EET 2001  Pekka
  55
  56      Changed RSA private exponent generation to what PKCS #1 suggests.  We
  57      try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
  58      of modinv(e, phi).  Note: this is not security fix but optimization.
  59
  60    o Tue Feb 20 13:58:58 EET 2001  Pekka
  61
  62      Set key->bits in rsa_generate_key.  It is the modulus length in bits.
  63      The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
  64      is now calculated by (key->bits + 7) / 8.  It is the length of one block.
  65
  66    o Sat Mar 16 18:27:19 EET 2002  Pekka
  67
  68      Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime
  69      generation.
  70
  71    o Sat Sep 26 19:59:48 EEST 2002  Pekka
  72
  73      Fixed double free in public key setting.  Use a bit larger e as
  74      starting point in key generation.
  75
  76 */
  77
  78 #include "silcincludes.h"
  79 #include "rsa_internal.h"
  80 #include "rsa.h"
  81
  82 /*
  83  * SILC PKCS API for RSA
  84  */
  85
  86 /* Generates RSA key pair. */
  87
  88 SILC_PKCS_API_INIT(rsa)
  89 {
  90   SilcUInt32 prime_bits = keylen / 2;
  91   SilcMPInt p, q;
  92   bool found = FALSE;
  93
  94   if (keylen < 768 || keylen > 16384)
  95     return FALSE;
  96
  97   printf("Generating RSA Public and Private keys, might take a while...\n");
  98
  99   silc_mp_init(&p);
 100   silc_mp_init(&q);
 101
 102   /* Find p and q */
 103   while (!found) {
 104     printf("Finding p: ");
 105     silc_math_gen_prime(&p, prime_bits, TRUE, rng);
 106
 107     printf("\nFinding q: ");
 108     silc_math_gen_prime(&q, prime_bits, TRUE, rng);
 109
 110     if ((silc_mp_cmp(&p, &q)) == 0)
 111       printf("\nFound equal primes, not good, retrying...\n");
 112     else
 113       found = TRUE;
 114   }
 115
 116   /* If p is smaller than q, switch them */
 117   if ((silc_mp_cmp(&p, &q)) > 0) {
 118     SilcMPInt hlp;
 119     silc_mp_init(&hlp);
 120
 121     silc_mp_set(&hlp, &p);
 122     silc_mp_set(&p, &q);
 123     silc_mp_set(&q, &hlp);
 124
 125     silc_mp_uninit(&hlp);
 126   }
 127
 128   /* Generate the actual keys */
 129   rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
 130
 131   silc_mp_uninit(&p);
 132   silc_mp_uninit(&q);
 133
 134   printf("\nKeys generated successfully.\n");
 135
 136   return TRUE;
 137 }
 138
 139 SILC_PKCS_API_CLEAR_KEYS(rsa)
 140 {
 141   rsa_clear_keys((RsaKey *)context);
 142 }
 143
 144 /* Returns SILC style encoded RSA public key. */
 145
 146 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
 147 {
 148   RsaKey *key = (RsaKey *)context;
 149   unsigned char *e, *n, *ret;
 150   SilcUInt32 e_len, n_len;
 151   unsigned char tmp[4];
 152
 153   e = silc_mp_mp2bin(&key->e, 0, &e_len);
 154   n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len);
 155
 156   *ret_len = e_len + 4 + n_len + 4;
 157   ret = silc_calloc(*ret_len, sizeof(unsigned char));
 158
 159   /* Put the length of the e. */
 160   SILC_PUT32_MSB(e_len, tmp);
 161   memcpy(ret, tmp, 4);
 162
 163   /* Put the e. */
 164   memcpy(ret + 4, e, e_len);
 165
 166   /* Put the length of the n. */
 167   SILC_PUT32_MSB(n_len, tmp);
 168   memcpy(ret + 4 + e_len, tmp, 4);
 169
 170   /* Put the n. */
 171   memcpy(ret + 4 + e_len + 4, n, n_len);
 172
 173   memset(e, 0, e_len);
 174   memset(n, 0, n_len);
 175   silc_free(e);
 176   silc_free(n);
 177
 178   return ret;
 179 }
 180
 181 /* Returns SILC style encoded RSA private key. Public key is always
 182    returned in private key as well. Public keys are often derived
 183    directly from private key. */
 184
 185 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
 186 {
 187   RsaKey *key = (RsaKey *)context;
 188   SilcBuffer buf;
 189   unsigned char *e, *n, *d, *ret, *dp = NULL, *dq = NULL;
 190   unsigned char *pq = NULL, *qp = NULL, *p = NULL, *q = NULL;
 191   SilcUInt32 e_len, n_len, d_len, dp_len, dq_len, pq_len, qp_len, p_len, q_len;
 192   SilcUInt32 len = 0;
 193
 194   e = silc_mp_mp2bin(&key->e, 0, &e_len);
 195   n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len);
 196   d = silc_mp_mp2bin(&key->d, 0, &d_len);
 197   if (key->crt) {
 198     dp = silc_mp_mp2bin(&key->dP, 0, &dp_len);
 199     dq = silc_mp_mp2bin(&key->dQ, 0, &dq_len);
 200     pq = silc_mp_mp2bin(&key->pQ, 0, &pq_len);
 201     qp = silc_mp_mp2bin(&key->qP, 0, &qp_len);
 202     p = silc_mp_mp2bin(&key->p, 0, &p_len);
 203     q = silc_mp_mp2bin(&key->q, 0, &q_len);
 204     len = dp_len + 4 + dq_len + 4 + pq_len + 4 + qp_len + 4 + p_len + 4 +
 205       q_len + 4;
 206   }
 207
 208   buf = silc_buffer_alloc_size(e_len + 4 + n_len + 4 + d_len + 4 + len);
 209   len = silc_buffer_format(buf,
 210                            SILC_STR_UI_INT(e_len),
 211                            SILC_STR_UI_XNSTRING(e, e_len),
 212                            SILC_STR_UI_INT(n_len),
 213                            SILC_STR_UI_XNSTRING(n, n_len),
 214                            SILC_STR_UI_INT(d_len),
 215                            SILC_STR_UI_XNSTRING(d, d_len),
 216                            SILC_STR_END);
 217
 218   if (key->crt) {
 219     silc_buffer_pull(buf, len);
 220     silc_buffer_format(buf,
 221                        SILC_STR_UI_INT(dp_len),
 222                        SILC_STR_UI_XNSTRING(dp, dp_len),
 223                        SILC_STR_UI_INT(dq_len),
 224                        SILC_STR_UI_XNSTRING(dq, dq_len),
 225                        SILC_STR_UI_INT(pq_len),
 226                        SILC_STR_UI_XNSTRING(pq, pq_len),
 227                        SILC_STR_UI_INT(qp_len),
 228                        SILC_STR_UI_XNSTRING(qp, qp_len),
 229                        SILC_STR_UI_INT(p_len),
 230                        SILC_STR_UI_XNSTRING(p, p_len),
 231                        SILC_STR_UI_INT(q_len),
 232                        SILC_STR_UI_XNSTRING(q, q_len),
 233                        SILC_STR_END);
 234     silc_buffer_push(buf, len);
 235
 236     memset(dp, 0, dp_len);
 237     memset(dq, 0, dq_len);
 238     memset(pq, 0, pq_len);
 239     memset(qp, 0, qp_len);
 240     memset(p, 0, p_len);
 241     memset(q, 0, q_len);
 242     silc_free(dp);
 243     silc_free(dq);
 244     silc_free(pq);
 245     silc_free(qp);
 246     silc_free(p);
 247     silc_free(q);
 248   }
 249
 250   memset(d, 0, d_len);
 251   silc_free(e);
 252   silc_free(n);
 253   silc_free(d);
 254
 255   ret = silc_buffer_steal(buf, ret_len);
 256   silc_buffer_free(buf);
 257   return ret;
 258 }
 259
 260 /* Set public key */
 261
 262 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
 263 {
 264   RsaKey *key = (RsaKey *)context;
 265   unsigned char tmp[4];
 266   SilcUInt32 e_len, n_len;
 267
 268   if (key->pub_set) {
 269     silc_mp_uninit(&key->e);
 270     silc_mp_uninit(&key->n);
 271     key->pub_set = FALSE;
 272   }
 273
 274   if (key_len < 4)
 275     return 0;
 276
 277   silc_mp_init(&key->e);
 278   silc_mp_init(&key->n);
 279
 280   memcpy(tmp, key_data, 4);
 281   SILC_GET32_MSB(e_len, tmp);
 282   if (!e_len || e_len + 4 > key_len) {
 283     silc_mp_uninit(&key->e);
 284     silc_mp_uninit(&key->n);
 285     return 0;
 286   }
 287
 288   silc_mp_bin2mp(key_data + 4, e_len, &key->e);
 289
 290   if (key_len < 4 + e_len + 4) {
 291     silc_mp_uninit(&key->e);
 292     silc_mp_uninit(&key->n);
 293     return 0;
 294   }
 295
 296   memcpy(tmp, key_data + 4 + e_len, 4);
 297   SILC_GET32_MSB(n_len, tmp);
 298   if (!n_len || e_len + 4 + n_len + 4 > key_len) {
 299     silc_mp_uninit(&key->e);
 300     silc_mp_uninit(&key->n);
 301     return 0;
 302   }
 303
 304   silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
 305
 306   key->bits = silc_mp_sizeinbase(&key->n, 2);
 307   key->pub_set = TRUE;
 308
 309   return key->bits;
 310 }
 311
 312 /* Set private key. This derives the public key from the private
 313    key and sets the public key as well. Public key should not be set
 314    already and should not be set after setting private key. */
 315
 316 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
 317 {
 318   RsaKey *key = (RsaKey *)context;
 319   SilcBufferStruct k;
 320   unsigned char *tmp;
 321   SilcUInt32 len;
 322
 323   if (key->prv_set) {
 324     silc_mp_uninit(&key->d);
 325     key->prv_set = FALSE;
 326   }
 327
 328   if (key->pub_set) {
 329     silc_mp_uninit(&key->e);
 330     silc_mp_uninit(&key->n);
 331     key->pub_set = FALSE;
 332   }
 333
 334   if (key_len < 4)
 335     return FALSE;
 336
 337   silc_buffer_set(&k, key_data, key_len);
 338
 339   silc_mp_init(&key->e);
 340   silc_mp_init(&key->n);
 341   silc_mp_init(&key->d);
 342   key->prv_set = TRUE;
 343   key->pub_set = TRUE;
 344
 345   /* Get e */
 346   if (silc_buffer_unformat(&k,
 347                            SILC_STR_UI_INT(&len),
 348                            SILC_STR_END) < 0)
 349     goto err;
 350   silc_buffer_pull(&k, 4);
 351   if (silc_buffer_unformat(&k,
 352                            SILC_STR_UI_XNSTRING(&tmp, len),
 353                            SILC_STR_END) < 0)
 354     goto err;
 355   silc_mp_bin2mp(tmp, len, &key->e);
 356   silc_buffer_pull(&k, len);
 357
 358   /* Get n */
 359   if (silc_buffer_unformat(&k,
 360                            SILC_STR_UI_INT(&len),
 361                            SILC_STR_END) < 0)
 362     goto err;
 363   silc_buffer_pull(&k, 4);
 364   if (silc_buffer_unformat(&k,
 365                            SILC_STR_UI_XNSTRING(&tmp, len),
 366                            SILC_STR_END) < 0)
 367     goto err;
 368   silc_mp_bin2mp(tmp, len, &key->n);
 369   silc_buffer_pull(&k, len);
 370
 371   /* Get d */
 372   if (silc_buffer_unformat(&k,
 373                            SILC_STR_UI_INT(&len),
 374                            SILC_STR_END) < 0)
 375     goto err;
 376   silc_buffer_pull(&k, 4);
 377   if (silc_buffer_unformat(&k,
 378                            SILC_STR_UI_XNSTRING(&tmp, len),
 379                            SILC_STR_END) < 0)
 380     goto err;
 381   silc_mp_bin2mp(tmp, len, &key->d);
 382   silc_buffer_pull(&k, len);
 383
 384   /* Get optimized d for CRT, if present. */
 385   if (k.len > 4) {
 386     key->crt = TRUE;
 387     silc_mp_init(&key->dP);
 388     silc_mp_init(&key->dQ);
 389     silc_mp_init(&key->pQ);
 390     silc_mp_init(&key->qP);
 391     silc_mp_init(&key->p);
 392     silc_mp_init(&key->q);
 393
 394     /* Get dP */
 395     if (silc_buffer_unformat(&k,
 396                              SILC_STR_UI_INT(&len),
 397                              SILC_STR_END) < 0)
 398       goto err;
 399     silc_buffer_pull(&k, 4);
 400     if (silc_buffer_unformat(&k,
 401                              SILC_STR_UI_XNSTRING(&tmp, len),
 402                              SILC_STR_END) < 0)
 403       goto err;
 404     silc_mp_bin2mp(tmp, len, &key->dP);
 405     silc_buffer_pull(&k, len);
 406
 407     /* Get dQ */
 408     if (silc_buffer_unformat(&k,
 409                              SILC_STR_UI_INT(&len),
 410                              SILC_STR_END) < 0)
 411       goto err;
 412     silc_buffer_pull(&k, 4);
 413     if (silc_buffer_unformat(&k,
 414                              SILC_STR_UI_XNSTRING(&tmp, len),
 415                              SILC_STR_END) < 0)
 416       goto err;
 417     silc_mp_bin2mp(tmp, len, &key->dQ);
 418     silc_buffer_pull(&k, len);
 419
 420     /* Get pQ */
 421     if (silc_buffer_unformat(&k,
 422                              SILC_STR_UI_INT(&len),
 423                              SILC_STR_END) < 0)
 424       goto err;
 425     silc_buffer_pull(&k, 4);
 426     if (silc_buffer_unformat(&k,
 427                              SILC_STR_UI_XNSTRING(&tmp, len),
 428                              SILC_STR_END) < 0)
 429       goto err;
 430     silc_mp_bin2mp(tmp, len, &key->pQ);
 431     silc_buffer_pull(&k, len);
 432
 433     /* Get qP */
 434     if (silc_buffer_unformat(&k,
 435                              SILC_STR_UI_INT(&len),
 436                              SILC_STR_END) < 0)
 437       goto err;
 438     silc_buffer_pull(&k, 4);
 439     if (silc_buffer_unformat(&k,
 440                              SILC_STR_UI_XNSTRING(&tmp, len),
 441                              SILC_STR_END) < 0)
 442       goto err;
 443     silc_mp_bin2mp(tmp, len, &key->qP);
 444     silc_buffer_pull(&k, len);
 445
 446     /* Get p */
 447     if (silc_buffer_unformat(&k,
 448                              SILC_STR_UI_INT(&len),
 449                              SILC_STR_END) < 0)
 450       goto err;
 451     silc_buffer_pull(&k, 4);
 452     if (silc_buffer_unformat(&k,
 453                              SILC_STR_UI_XNSTRING(&tmp, len),
 454                              SILC_STR_END) < 0)
 455       goto err;
 456     silc_mp_bin2mp(tmp, len, &key->p);
 457     silc_buffer_pull(&k, len);
 458
 459     /* Get q */
 460     if (silc_buffer_unformat(&k,
 461                              SILC_STR_UI_INT(&len),
 462                              SILC_STR_END) < 0)
 463       goto err;
 464     silc_buffer_pull(&k, 4);
 465     if (silc_buffer_unformat(&k,
 466                              SILC_STR_UI_XNSTRING(&tmp, len),
 467                              SILC_STR_END) < 0)
 468       goto err;
 469     silc_mp_bin2mp(tmp, len, &key->q);
 470     silc_buffer_pull(&k, len);
 471   }
 472
 473   key->bits = silc_mp_sizeinbase(&key->n, 2);
 474   return key->bits;
 475
 476  err:
 477   rsa_clear_keys(key);
 478   return FALSE;
 479 }
 480
 481 SILC_PKCS_API_CONTEXT_LEN(rsa)
 482 {
 483   return sizeof(RsaKey);
 484 }
 485
 486 SILC_PKCS_API_ENCRYPT(rsa)
 487 {
 488   RsaKey *key = (RsaKey *)context;
 489   int tmplen;
 490   SilcMPInt mp_tmp;
 491   SilcMPInt mp_dst;
 492
 493   silc_mp_init(&mp_tmp);
 494   silc_mp_init(&mp_dst);
 495
 496   /* Format the data into MP int */
 497   silc_mp_bin2mp(src, src_len, &mp_tmp);
 498
 499   /* Encrypt */
 500   rsa_public_operation(key, &mp_tmp, &mp_dst);
 501
 502   tmplen = (key->bits + 7) / 8;
 503
 504   /* Format the MP int back into data */
 505   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 506   *dst_len = tmplen;
 507
 508   silc_mp_uninit(&mp_tmp);
 509   silc_mp_uninit(&mp_dst);
 510
 511   return TRUE;
 512 }
 513
 514 SILC_PKCS_API_DECRYPT(rsa)
 515 {
 516   RsaKey *key = (RsaKey *)context;
 517   int tmplen;
 518   SilcMPInt mp_tmp;
 519   SilcMPInt mp_dst;
 520
 521   silc_mp_init(&mp_tmp);
 522   silc_mp_init(&mp_dst);
 523
 524   /* Format the data into MP int */
 525   silc_mp_bin2mp(src, src_len, &mp_tmp);
 526
 527   /* Decrypt */
 528   rsa_private_operation(key, &mp_tmp, &mp_dst);
 529
 530   tmplen = (key->bits + 7) / 8;
 531
 532   /* Format the MP int back into data */
 533   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 534   *dst_len = tmplen;
 535
 536   silc_mp_uninit(&mp_tmp);
 537   silc_mp_uninit(&mp_dst);
 538
 539   return TRUE;
 540 }
 541
 542 SILC_PKCS_API_SIGN(rsa)
 543 {
 544   RsaKey *key = (RsaKey *)context;
 545   int tmplen;
 546   SilcMPInt mp_tmp;
 547   SilcMPInt mp_dst;
 548
 549   silc_mp_init(&mp_tmp);
 550   silc_mp_init(&mp_dst);
 551
 552   /* Format the data into MP int */
 553   silc_mp_bin2mp(src, src_len, &mp_tmp);
 554
 555   /* Sign */
 556   rsa_private_operation(key, &mp_tmp, &mp_dst);
 557
 558   tmplen = (key->bits + 7) / 8;
 559
 560   /* Format the MP int back into data */
 561   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 562   *dst_len = tmplen;
 563
 564   silc_mp_uninit(&mp_tmp);
 565   silc_mp_uninit(&mp_dst);
 566
 567   return TRUE;
 568 }
 569
 570 SILC_PKCS_API_VERIFY(rsa)
 571 {
 572   RsaKey *key = (RsaKey *)context;
 573   int ret;
 574   SilcMPInt mp_tmp, mp_tmp2;
 575   SilcMPInt mp_dst;
 576
 577   silc_mp_init(&mp_tmp);
 578   silc_mp_init(&mp_tmp2);
 579   silc_mp_init(&mp_dst);
 580
 581   /* Format the signature into MP int */
 582   silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
 583
 584   /* Verify */
 585   rsa_public_operation(key, &mp_tmp2, &mp_dst);
 586
 587   /* Format the data into MP int */
 588   silc_mp_bin2mp(data, data_len, &mp_tmp);
 589
 590   ret = TRUE;
 591
 592   /* Compare */
 593   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 594     ret = FALSE;
 595
 596   silc_mp_uninit(&mp_tmp);
 597   silc_mp_uninit(&mp_tmp2);
 598   silc_mp_uninit(&mp_dst);
 599
 600   return ret;
 601 }
 602
 603 /* Generates RSA public and private keys. Primes p and q that are used
 604    to compute the modulus n has to be generated before calling this. They
 605    are then sent as argument for the function. */
 606
 607 bool rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
 608                        SilcMPInt *p, SilcMPInt *q)
 609 {
 610   SilcMPInt phi, hlp;
 611   SilcMPInt div, lcm;
 612   SilcMPInt pm1, qm1;
 613
 614   /* Initialize variables */
 615   silc_mp_init(&key->n);
 616   silc_mp_init(&key->e);
 617   silc_mp_init(&key->d);
 618   silc_mp_init(&key->dP);
 619   silc_mp_init(&key->dQ);
 620   silc_mp_init(&key->pQ);
 621   silc_mp_init(&key->qP);
 622   silc_mp_init(&phi);
 623   silc_mp_init(&hlp);
 624   silc_mp_init(&div);
 625   silc_mp_init(&lcm);
 626   silc_mp_init(&pm1);
 627   silc_mp_init(&qm1);
 628
 629   /* Set modulus length */
 630   key->bits = bits;
 631
 632   /* Compute modulus, n = p * q */
 633   silc_mp_mul(&key->n, p, q);
 634
 635   /* phi = (p - 1) * (q - 1) */
 636   silc_mp_sub_ui(&pm1, p, 1);
 637   silc_mp_sub_ui(&qm1, q, 1);
 638   silc_mp_mul(&phi, &pm1, &qm1);
 639
 640   /* Set e, the public exponent. We try to use same public exponent
 641      for all keys. Also, to make encryption faster we use small
 642      number. */
 643   silc_mp_set_ui(&key->e, 65533);
 644  retry_e:
 645   /* See if e is relatively prime to phi. gcd == greates common divisor,
 646      if gcd equals 1 they are relatively prime. */
 647   silc_mp_gcd(&hlp, &key->e, &phi);
 648   if ((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 649     silc_mp_add_ui(&key->e, &key->e, 2);
 650     goto retry_e;
 651   }
 652
 653   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 654   silc_mp_gcd(&div, &pm1, &qm1);
 655   silc_mp_div(&lcm, &phi, &div);
 656   silc_mp_modinv(&key->d, &key->e, &lcm);
 657
 658   /* Optimize d with CRT.  We precompute as much as possible. */
 659   silc_mp_mod(&key->dP, &key->d, &pm1);
 660   silc_mp_mod(&key->dQ, &key->d, &qm1);
 661   silc_mp_modinv(&key->pQ, p, q);
 662   silc_mp_mul(&key->pQ, p, &key->pQ);
 663   silc_mp_mod(&key->pQ, &key->pQ, &key->n);
 664   silc_mp_modinv(&key->qP, q, p);
 665   silc_mp_mul(&key->qP, q, &key->qP);
 666   silc_mp_mod(&key->qP, &key->qP, &key->n);
 667   silc_mp_set(&key->p, p);
 668   silc_mp_set(&key->q, q);
 669   key->crt = TRUE;
 670
 671   silc_mp_uninit(&phi);
 672   silc_mp_uninit(&hlp);
 673   silc_mp_uninit(&div);
 674   silc_mp_uninit(&lcm);
 675   silc_mp_uninit(&pm1);
 676   silc_mp_uninit(&qm1);
 677
 678   return TRUE;
 679 }
 680
 681 /* Clears whole key structure. */
 682
 683 bool rsa_clear_keys(RsaKey *key)
 684 {
 685   key->bits = 0;
 686   if (key->pub_set) {
 687     silc_mp_uninit(&key->n);
 688     silc_mp_uninit(&key->e);
 689   }
 690   if (key->prv_set)
 691     silc_mp_uninit(&key->d);
 692   if (key->prv_set && key->crt) {
 693     silc_mp_uninit(&key->dP);
 694     silc_mp_uninit(&key->dQ);
 695     silc_mp_uninit(&key->pQ);
 696     silc_mp_uninit(&key->qP);
 697     silc_mp_uninit(&key->p);
 698     silc_mp_uninit(&key->q);
 699   }
 700   return TRUE;
 701 }
 702
 703 /* RSA public key operation */
 704
 705 bool rsa_public_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst)
 706 {
 707   /* dst = src ^ e mod n */
 708   silc_mp_pow_mod(dst, src, &key->e, &key->n);
 709   return TRUE;
 710 }
 711
 712 /* RSA private key operation */
 713
 714 bool rsa_private_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst)
 715 {
 716   if (!key->crt) {
 717     /* dst = src ^ d mod n */
 718     silc_mp_pow_mod(dst, src, &key->d, &key->n);
 719   } else {
 720     /* CRT */
 721     SilcMPInt tmp;
 722
 723     silc_mp_init(&tmp);
 724
 725     /* dst = ((src ^ dP mod p) * qP) + ((src ^ dQ mod q) * pQ) mod n */
 726     silc_mp_pow_mod(dst, src, &key->dP, &key->p);
 727     silc_mp_mul(dst, dst, &key->qP);
 728     silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q);
 729     silc_mp_mul(&tmp, &tmp, &key->pQ);
 730     silc_mp_add(dst, dst, &tmp);
 731     silc_mp_mod(dst, dst, &key->n);
 732
 733     silc_mp_uninit(&tmp);
 734   }
 735
 736   return TRUE;
 737 }