lib/silccrypt/rsa.c

   1 /*
   2
   3   rsa.c         RSA Public and Private key generation functions,
   4                 RSA encrypt and decrypt functions.
   5
   6   Author: Pekka Riikonen <priikone@silcnet.org>
   7
   8   Copyright (C) 1997 - 2005 Pekka Riikonen
   9
  10   This program is free software; you can redistribute it and/or modify
  11   it under the terms of the GNU General Public License as published by
  12   the Free Software Foundation; version 2 of the License.
  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 "silc.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   SilcBool 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 (silc_buffer_len(&k) > 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 /* Raw RSA routines */
 487
 488 SILC_PKCS_API_ENCRYPT(rsa)
 489 {
 490   RsaKey *key = (RsaKey *)context;
 491   int tmplen;
 492   SilcMPInt mp_tmp;
 493   SilcMPInt mp_dst;
 494
 495   silc_mp_init(&mp_tmp);
 496   silc_mp_init(&mp_dst);
 497
 498   /* Format the data into MP int */
 499   silc_mp_bin2mp(src, src_len, &mp_tmp);
 500
 501   /* Encrypt */
 502   rsa_public_operation(key, &mp_tmp, &mp_dst);
 503
 504   tmplen = (key->bits + 7) / 8;
 505
 506   /* Format the MP int back into data */
 507   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 508   *dst_len = tmplen;
 509
 510   silc_mp_uninit(&mp_tmp);
 511   silc_mp_uninit(&mp_dst);
 512
 513   return TRUE;
 514 }
 515
 516 SILC_PKCS_API_DECRYPT(rsa)
 517 {
 518   RsaKey *key = (RsaKey *)context;
 519   int tmplen;
 520   SilcMPInt mp_tmp;
 521   SilcMPInt mp_dst;
 522
 523   silc_mp_init(&mp_tmp);
 524   silc_mp_init(&mp_dst);
 525
 526   /* Format the data into MP int */
 527   silc_mp_bin2mp(src, src_len, &mp_tmp);
 528
 529   /* Decrypt */
 530   rsa_private_operation(key, &mp_tmp, &mp_dst);
 531
 532   tmplen = (key->bits + 7) / 8;
 533
 534   /* Format the MP int back into data */
 535   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 536   *dst_len = tmplen;
 537
 538   silc_mp_uninit(&mp_tmp);
 539   silc_mp_uninit(&mp_dst);
 540
 541   return TRUE;
 542 }
 543
 544 SILC_PKCS_API_SIGN(rsa)
 545 {
 546   RsaKey *key = (RsaKey *)context;
 547   int tmplen;
 548   SilcMPInt mp_tmp;
 549   SilcMPInt mp_dst;
 550
 551   silc_mp_init(&mp_tmp);
 552   silc_mp_init(&mp_dst);
 553
 554   /* Format the data into MP int */
 555   silc_mp_bin2mp(src, src_len, &mp_tmp);
 556
 557   /* Sign */
 558   rsa_private_operation(key, &mp_tmp, &mp_dst);
 559
 560   tmplen = (key->bits + 7) / 8;
 561
 562   /* Format the MP int back into data */
 563   silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
 564   *dst_len = tmplen;
 565
 566   silc_mp_uninit(&mp_tmp);
 567   silc_mp_uninit(&mp_dst);
 568
 569   return TRUE;
 570 }
 571
 572 SILC_PKCS_API_VERIFY(rsa)
 573 {
 574   RsaKey *key = (RsaKey *)context;
 575   int ret;
 576   SilcMPInt mp_tmp, mp_tmp2;
 577   SilcMPInt mp_dst;
 578
 579   silc_mp_init(&mp_tmp);
 580   silc_mp_init(&mp_tmp2);
 581   silc_mp_init(&mp_dst);
 582
 583   /* Format the signature into MP int */
 584   silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
 585
 586   /* Verify */
 587   rsa_public_operation(key, &mp_tmp2, &mp_dst);
 588
 589   /* Format the data into MP int */
 590   silc_mp_bin2mp(data, data_len, &mp_tmp);
 591
 592   ret = TRUE;
 593
 594   /* Compare */
 595   if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
 596     ret = FALSE;
 597
 598   silc_mp_uninit(&mp_tmp);
 599   silc_mp_uninit(&mp_tmp2);
 600   silc_mp_uninit(&mp_dst);
 601
 602   return ret;
 603 }
 604
 605
 606 /* PKCS#1 RSA routines */
 607
 608 SILC_PKCS_API_ENCRYPT(pkcs1)
 609 {
 610   RsaKey *key = (RsaKey *)context;
 611   SilcMPInt mp_tmp;
 612   SilcMPInt mp_dst;
 613   unsigned char padded[2048 + 1];
 614   SilcUInt32 len = (key->bits + 7) / 8;
 615
 616   if (sizeof(padded) < len)
 617     return FALSE;
 618
 619   /* Pad data */
 620   if (!silc_pkcs1_encode(SILC_PKCS1_BT_PUB, src, src_len,
 621                          padded, len, NULL))
 622     return FALSE;
 623
 624   silc_mp_init(&mp_tmp);
 625   silc_mp_init(&mp_dst);
 626
 627   /* Data to MP */
 628   silc_mp_bin2mp(padded, len, &mp_tmp);
 629
 630   /* Encrypt */
 631   rsa_public_operation(key, &mp_tmp, &mp_dst);
 632
 633   /* MP to data */
 634   silc_mp_mp2bin_noalloc(&mp_dst, dst, len);
 635   *dst_len = len;
 636
 637   memset(padded, 0, sizeof(padded));
 638   silc_mp_uninit(&mp_tmp);
 639   silc_mp_uninit(&mp_dst);
 640
 641   return TRUE;
 642 }
 643
 644 SILC_PKCS_API_DECRYPT(pkcs1)
 645 {
 646   RsaKey *key = (RsaKey *)context;
 647   SilcMPInt mp_tmp;
 648   SilcMPInt mp_dst;
 649   unsigned char *padded, unpadded[2048 + 1];
 650   SilcUInt32 padded_len;
 651
 652   silc_mp_init(&mp_tmp);
 653   silc_mp_init(&mp_dst);
 654
 655   /* Data to MP */
 656   silc_mp_bin2mp(src, src_len, &mp_tmp);
 657
 658   /* Decrypt */
 659   rsa_private_operation(key, &mp_tmp, &mp_dst);
 660
 661   /* MP to data */
 662   padded = silc_mp_mp2bin(&mp_dst, (key->bits + 7) / 8, &padded_len);
 663
 664   /* Unpad data */
 665   if (!silc_pkcs1_decode(SILC_PKCS1_BT_PUB, padded, padded_len,
 666                          unpadded, sizeof(unpadded), dst_len)) {
 667     memset(padded, 0, padded_len);
 668     silc_free(padded);
 669     silc_mp_uninit(&mp_tmp);
 670     silc_mp_uninit(&mp_dst);
 671     return FALSE;
 672   }
 673
 674   /* Copy to destination */
 675   memcpy(dst, unpadded, *dst_len);
 676
 677   memset(padded, 0, padded_len);
 678   memset(unpadded, 0, sizeof(unpadded));
 679   silc_free(padded);
 680   silc_mp_uninit(&mp_tmp);
 681   silc_mp_uninit(&mp_dst);
 682
 683   return TRUE;
 684 }
 685
 686 SILC_PKCS_API_SIGN(pkcs1)
 687 {
 688   RsaKey *key = (RsaKey *)context;
 689   SilcMPInt mp_tmp;
 690   SilcMPInt mp_dst;
 691   unsigned char padded[2048 + 1];
 692   SilcUInt32 len = (key->bits + 7) / 8;
 693
 694   if (sizeof(padded) < len)
 695     return FALSE;
 696
 697   /* Pad data */
 698   if (!silc_pkcs1_encode(SILC_PKCS1_BT_PRV1, src, src_len,
 699                          padded, len, NULL))
 700     return FALSE;
 701
 702   silc_mp_init(&mp_tmp);
 703   silc_mp_init(&mp_dst);
 704
 705   /* Data to MP */
 706   silc_mp_bin2mp(padded, len, &mp_tmp);
 707
 708   /* Sign */
 709   rsa_private_operation(key, &mp_tmp, &mp_dst);
 710
 711   /* MP to data */
 712   silc_mp_mp2bin_noalloc(&mp_dst, dst, len);
 713   *dst_len = len;
 714
 715   memset(padded, 0, sizeof(padded));
 716   silc_mp_uninit(&mp_tmp);
 717   silc_mp_uninit(&mp_dst);
 718
 719   return TRUE;
 720 }
 721
 722 SILC_PKCS_API_VERIFY(pkcs1)
 723 {
 724   RsaKey *key = (RsaKey *)context;
 725   int ret = TRUE;
 726   SilcMPInt mp_tmp2;
 727   SilcMPInt mp_dst;
 728   unsigned char *verify, unpadded[2048 + 1];
 729   SilcUInt32 verify_len, len = (key->bits + 7) / 8;
 730
 731   silc_mp_init(&mp_tmp2);
 732   silc_mp_init(&mp_dst);
 733
 734   /* Format the signature into MP int */
 735   silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
 736
 737   /* Verify */
 738   rsa_public_operation(key, &mp_tmp2, &mp_dst);
 739
 740   /* MP to data */
 741   verify = silc_mp_mp2bin(&mp_dst, len, &verify_len);
 742
 743   /* Unpad data */
 744   if (!silc_pkcs1_decode(SILC_PKCS1_BT_PRV1, verify, verify_len,
 745                          unpadded, sizeof(unpadded), &len)) {
 746     memset(verify, 0, verify_len);
 747     silc_free(verify);
 748     silc_mp_uninit(&mp_tmp2);
 749     silc_mp_uninit(&mp_dst);
 750     return FALSE;
 751   }
 752
 753   /* Compare */
 754   if (memcmp(data, unpadded, len))
 755     ret = FALSE;
 756
 757   memset(verify, 0, verify_len);
 758   memset(unpadded, 0, sizeof(unpadded));
 759   silc_free(verify);
 760   silc_mp_uninit(&mp_tmp2);
 761   silc_mp_uninit(&mp_dst);
 762
 763   return ret;
 764 }
 765
 766 /* Generates RSA public and private keys. Primes p and q that are used
 767    to compute the modulus n has to be generated before calling this. They
 768    are then sent as argument for the function. */
 769
 770 SilcBool rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
 771                        SilcMPInt *p, SilcMPInt *q)
 772 {
 773   SilcMPInt phi, hlp;
 774   SilcMPInt div, lcm;
 775   SilcMPInt pm1, qm1;
 776
 777   /* Initialize variables */
 778   silc_mp_init(&key->n);
 779   silc_mp_init(&key->e);
 780   silc_mp_init(&key->d);
 781   silc_mp_init(&key->dP);
 782   silc_mp_init(&key->dQ);
 783   silc_mp_init(&key->pQ);
 784   silc_mp_init(&key->qP);
 785   silc_mp_init(&phi);
 786   silc_mp_init(&hlp);
 787   silc_mp_init(&div);
 788   silc_mp_init(&lcm);
 789   silc_mp_init(&pm1);
 790   silc_mp_init(&qm1);
 791
 792   /* Set modulus length */
 793   key->bits = bits;
 794
 795   /* Compute modulus, n = p * q */
 796   silc_mp_mul(&key->n, p, q);
 797
 798   /* phi = (p - 1) * (q - 1) */
 799   silc_mp_sub_ui(&pm1, p, 1);
 800   silc_mp_sub_ui(&qm1, q, 1);
 801   silc_mp_mul(&phi, &pm1, &qm1);
 802
 803   /* Set e, the public exponent. We try to use same public exponent
 804      for all keys. Also, to make encryption faster we use small
 805      number. */
 806   silc_mp_set_ui(&key->e, 65533);
 807  retry_e:
 808   /* See if e is relatively prime to phi. gcd == greates common divisor,
 809      if gcd equals 1 they are relatively prime. */
 810   silc_mp_gcd(&hlp, &key->e, &phi);
 811   if ((silc_mp_cmp_ui(&hlp, 1)) > 0) {
 812     silc_mp_add_ui(&key->e, &key->e, 2);
 813     goto retry_e;
 814   }
 815
 816   /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
 817   silc_mp_gcd(&div, &pm1, &qm1);
 818   silc_mp_div(&lcm, &phi, &div);
 819   silc_mp_modinv(&key->d, &key->e, &lcm);
 820
 821   /* Optimize d with CRT.  We precompute as much as possible. */
 822   silc_mp_mod(&key->dP, &key->d, &pm1);
 823   silc_mp_mod(&key->dQ, &key->d, &qm1);
 824   silc_mp_modinv(&key->pQ, p, q);
 825   silc_mp_mul(&key->pQ, p, &key->pQ);
 826   silc_mp_mod(&key->pQ, &key->pQ, &key->n);
 827   silc_mp_modinv(&key->qP, q, p);
 828   silc_mp_mul(&key->qP, q, &key->qP);
 829   silc_mp_mod(&key->qP, &key->qP, &key->n);
 830   silc_mp_set(&key->p, p);
 831   silc_mp_set(&key->q, q);
 832   key->crt = TRUE;
 833
 834   silc_mp_uninit(&phi);
 835   silc_mp_uninit(&hlp);
 836   silc_mp_uninit(&div);
 837   silc_mp_uninit(&lcm);
 838   silc_mp_uninit(&pm1);
 839   silc_mp_uninit(&qm1);
 840
 841   return TRUE;
 842 }
 843
 844 /* Clears whole key structure. */
 845
 846 SilcBool rsa_clear_keys(RsaKey *key)
 847 {
 848   key->bits = 0;
 849   if (key->pub_set) {
 850     silc_mp_uninit(&key->n);
 851     silc_mp_uninit(&key->e);
 852   }
 853   if (key->prv_set)
 854     silc_mp_uninit(&key->d);
 855   if (key->prv_set && key->crt) {
 856     silc_mp_uninit(&key->dP);
 857     silc_mp_uninit(&key->dQ);
 858     silc_mp_uninit(&key->pQ);
 859     silc_mp_uninit(&key->qP);
 860     silc_mp_uninit(&key->p);
 861     silc_mp_uninit(&key->q);
 862   }
 863   return TRUE;
 864 }
 865
 866 /* RSA public key operation */
 867
 868 SilcBool rsa_public_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst)
 869 {
 870   /* dst = src ^ e mod n */
 871   silc_mp_pow_mod(dst, src, &key->e, &key->n);
 872   return TRUE;
 873 }
 874
 875 /* RSA private key operation */
 876
 877 SilcBool rsa_private_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst)
 878 {
 879   if (!key->crt) {
 880     /* dst = src ^ d mod n */
 881     silc_mp_pow_mod(dst, src, &key->d, &key->n);
 882   } else {
 883     /* CRT */
 884     SilcMPInt tmp;
 885
 886     silc_mp_init(&tmp);
 887
 888     /* dst = ((src ^ dP mod p) * qP) + ((src ^ dQ mod q) * pQ) mod n */
 889     silc_mp_pow_mod(dst, src, &key->dP, &key->p);
 890     silc_mp_mul(dst, dst, &key->qP);
 891     silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q);
 892     silc_mp_mul(&tmp, &tmp, &key->pQ);
 893     silc_mp_add(dst, dst, &tmp);
 894     silc_mp_mod(dst, dst, &key->n);
 895
 896     silc_mp_uninit(&tmp);
 897   }
 898
 899   return TRUE;
 900 }