cipher/rsa.c

   1 /* rsa.c - RSA implementation
   2  * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
   3  * Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc.
   4  *
   5  * This file is part of Libgcrypt.
   6  *
   7  * Libgcrypt is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as
   9  * published by the Free Software Foundation; either version 2.1 of
  10  * the License, or (at your option) any later version.
  11  *
  12  * Libgcrypt is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21 /* This code uses an algorithm protected by U.S. Patent #4,405,829
  22    which expired on September 20, 2000.  The patent holder placed that
  23    patent into the public domain on Sep 6th, 2000.
  24 */
  25
  26 #include <config.h>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <errno.h>
  31
  32 #include "g10lib.h"
  33 #include "mpi.h"
  34 #include "cipher.h"
  35 #include "pubkey-internal.h"
  36
  37
  38 typedef struct
  39 {
  40   gcry_mpi_t n;     /* modulus */
  41   gcry_mpi_t e;     /* exponent */
  42 } RSA_public_key;
  43
  44
  45 typedef struct
  46 {
  47   gcry_mpi_t n;     /* public modulus */
  48   gcry_mpi_t e;     /* public exponent */
  49   gcry_mpi_t d;     /* exponent */
  50   gcry_mpi_t p;     /* prime  p. */
  51   gcry_mpi_t q;     /* prime  q. */
  52   gcry_mpi_t u;     /* inverse of p mod q. */
  53 } RSA_secret_key;
  54
  55
  56 /* A sample 1024 bit RSA key used for the selftests.  */
  57 static const char sample_secret_key[] =
  58 "(private-key"
  59 " (rsa"
  60 "  (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
  61 "      2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
  62 "      ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
  63 "      891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
  64 "  (e #010001#)"
  65 "  (d #046129f2489d71579be0a75fe029bd6cdb574ebf57ea8a5b0fda942cab943b11"
  66 "      7d7bb95e5d28875e0f9fc5fcc06a72f6d502464dabded78ef6b716177b83d5bd"
  67 "      c543dc5d3fed932e59f5897e92e6f58a0f33424106a3b6fa2cbf877510e4ac21"
  68 "      c3ee47851e97d12996222ac3566d4ccb0b83d164074abf7de655fc2446da1781#)"
  69 "  (p #00e861b700e17e8afe6837e7512e35b6ca11d0ae47d8b85161c67baf64377213"
  70 "      fe52d772f2035b3ca830af41d8a4120e1c1c70d12cc22f00d28d31dd48a8d424f1#)"
  71 "  (q #00f7a7ca5367c661f8e62df34f0d05c10c88e5492348dd7bddc942c9a8f369f9"
  72 "      35a07785d2db805215ed786e4285df1658eed3ce84f469b81b50d358407b4ad361#)"
  73 "  (u #304559a9ead56d2309d203811a641bb1a09626bc8eb36fffa23c968ec5bd891e"
  74 "      ebbafc73ae666e01ba7c8990bae06cc2bbe10b75e69fcacb353a6473079d8e9b#)))";
  75 /* A sample 1024 bit RSA key used for the selftests (public only).  */
  76 static const char sample_public_key[] =
  77 "(public-key"
  78 " (rsa"
  79 "  (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
  80 "      2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
  81 "      ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
  82 "      891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
  83 "  (e #010001#)))";
  84
  85
  86
  87 \f
  88 static int test_keys (RSA_secret_key *sk, unsigned nbits);
  89 static int  check_secret_key (RSA_secret_key *sk);
  90 static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
  91 static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
  92
  93
  94 /* Check that a freshly generated key actually works.  Returns 0 on success. */
  95 static int
  96 test_keys (RSA_secret_key *sk, unsigned int nbits)
  97 {
  98   int result = -1; /* Default to failure.  */
  99   RSA_public_key pk;
 100   gcry_mpi_t plaintext = gcry_mpi_new (nbits);
 101   gcry_mpi_t ciphertext = gcry_mpi_new (nbits);
 102   gcry_mpi_t decr_plaintext = gcry_mpi_new (nbits);
 103   gcry_mpi_t signature = gcry_mpi_new (nbits);
 104
 105   /* Put the relevant parameters into a public key structure.  */
 106   pk.n = sk->n;
 107   pk.e = sk->e;
 108
 109   /* Create a random plaintext.  */
 110   gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
 111
 112   /* Encrypt using the public key.  */
 113   public (ciphertext, plaintext, &pk);
 114
 115   /* Check that the cipher text does not match the plaintext.  */
 116   if (!gcry_mpi_cmp (ciphertext, plaintext))
 117     goto leave; /* Ciphertext is identical to the plaintext.  */
 118
 119   /* Decrypt using the secret key.  */
 120   secret (decr_plaintext, ciphertext, sk);
 121
 122   /* Check that the decrypted plaintext matches the original plaintext.  */
 123   if (gcry_mpi_cmp (decr_plaintext, plaintext))
 124     goto leave; /* Plaintext does not match.  */
 125
 126   /* Create another random plaintext as data for signature checking.  */
 127   gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
 128
 129   /* Use the RSA secret function to create a signature of the plaintext.  */
 130   secret (signature, plaintext, sk);
 131
 132   /* Use the RSA public function to verify this signature.  */
 133   public (decr_plaintext, signature, &pk);
 134   if (gcry_mpi_cmp (decr_plaintext, plaintext))
 135     goto leave; /* Signature does not match.  */
 136
 137   /* Modify the signature and check that the signing fails.  */
 138   gcry_mpi_add_ui (signature, signature, 1);
 139   public (decr_plaintext, signature, &pk);
 140   if (!gcry_mpi_cmp (decr_plaintext, plaintext))
 141     goto leave; /* Signature matches but should not.  */
 142
 143   result = 0; /* All tests succeeded.  */
 144
 145  leave:
 146   gcry_mpi_release (signature);
 147   gcry_mpi_release (decr_plaintext);
 148   gcry_mpi_release (ciphertext);
 149   gcry_mpi_release (plaintext);
 150   return result;
 151 }
 152
 153
 154 /* Callback used by the prime generation to test whether the exponent
 155    is suitable. Returns 0 if the test has been passed. */
 156 static int
 157 check_exponent (void *arg, gcry_mpi_t a)
 158 {
 159   gcry_mpi_t e = arg;
 160   gcry_mpi_t tmp;
 161   int result;
 162
 163   mpi_sub_ui (a, a, 1);
 164   tmp = _gcry_mpi_alloc_like (a);
 165   result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */
 166   gcry_mpi_release (tmp);
 167   mpi_add_ui (a, a, 1);
 168   return result;
 169 }
 170
 171 /****************
 172  * Generate a key pair with a key of size NBITS.
 173  * USE_E = 0 let Libcgrypt decide what exponent to use.
 174  *       = 1 request the use of a "secure" exponent; this is required by some
 175  *           specification to be 65537.
 176  *       > 2 Use this public exponent.  If the given exponent
 177  *           is not odd one is internally added to it.
 178  * TRANSIENT_KEY:  If true, generate the primes using the standard RNG.
 179  * Returns: 2 structures filled with all needed values
 180  */
 181 static gpg_err_code_t
 182 generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
 183               int transient_key)
 184 {
 185   gcry_mpi_t p, q; /* the two primes */
 186   gcry_mpi_t d;    /* the private key */
 187   gcry_mpi_t u;
 188   gcry_mpi_t t1, t2;
 189   gcry_mpi_t n;    /* the public key */
 190   gcry_mpi_t e;    /* the exponent */
 191   gcry_mpi_t phi;  /* helper: (p-1)(q-1) */
 192   gcry_mpi_t g;
 193   gcry_mpi_t f;
 194   gcry_random_level_t random_level;
 195
 196   if (fips_mode ())
 197     {
 198       if (nbits < 1024)
 199         return GPG_ERR_INV_VALUE;
 200       if (transient_key)
 201         return GPG_ERR_INV_VALUE;
 202     }
 203
 204   /* The random quality depends on the transient_key flag.  */
 205   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
 206
 207   /* Make sure that nbits is even so that we generate p, q of equal size. */
 208   if ( (nbits&1) )
 209     nbits++;
 210
 211   if (use_e == 1)   /* Alias for a secure value */
 212     use_e = 65537;  /* as demanded by Sphinx. */
 213
 214   /* Public exponent:
 215      In general we use 41 as this is quite fast and more secure than the
 216      commonly used 17.  Benchmarking the RSA verify function
 217      with a 1024 bit key yields (2001-11-08):
 218      e=17    0.54 ms
 219      e=41    0.75 ms
 220      e=257   0.95 ms
 221      e=65537 1.80 ms
 222   */
 223   e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
 224   if (!use_e)
 225     mpi_set_ui (e, 41);     /* This is a reasonable secure and fast value */
 226   else
 227     {
 228       use_e |= 1; /* make sure this is odd */
 229       mpi_set_ui (e, use_e);
 230     }
 231
 232   n = gcry_mpi_new (nbits);
 233
 234   p = q = NULL;
 235   do
 236     {
 237       /* select two (very secret) primes */
 238       if (p)
 239         gcry_mpi_release (p);
 240       if (q)
 241         gcry_mpi_release (q);
 242       if (use_e)
 243         { /* Do an extra test to ensure that the given exponent is
 244              suitable. */
 245           p = _gcry_generate_secret_prime (nbits/2, random_level,
 246                                            check_exponent, e);
 247           q = _gcry_generate_secret_prime (nbits/2, random_level,
 248                                            check_exponent, e);
 249         }
 250       else
 251         { /* We check the exponent later. */
 252           p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
 253           q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
 254         }
 255       if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
 256         mpi_swap(p,q);
 257       /* calculate the modulus */
 258       mpi_mul( n, p, q );
 259     }
 260   while ( mpi_get_nbits(n) != nbits );
 261
 262   /* calculate Euler totient: phi = (p-1)(q-1) */
 263   t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
 264   t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
 265   phi = gcry_mpi_snew ( nbits );
 266   g     = gcry_mpi_snew ( nbits );
 267   f     = gcry_mpi_snew ( nbits );
 268   mpi_sub_ui( t1, p, 1 );
 269   mpi_sub_ui( t2, q, 1 );
 270   mpi_mul( phi, t1, t2 );
 271   gcry_mpi_gcd(g, t1, t2);
 272   mpi_fdiv_q(f, phi, g);
 273
 274   while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
 275     {
 276       if (use_e)
 277         BUG (); /* The prime generator already made sure that we
 278                    never can get to here. */
 279       mpi_add_ui (e, e, 2);
 280     }
 281
 282   /* calculate the secret key d = e^1 mod phi */
 283   d = gcry_mpi_snew ( nbits );
 284   mpi_invm(d, e, f );
 285   /* calculate the inverse of p and q (used for chinese remainder theorem)*/
 286   u = gcry_mpi_snew ( nbits );
 287   mpi_invm(u, p, q );
 288
 289   if( DBG_CIPHER )
 290     {
 291       log_mpidump("  p= ", p );
 292       log_mpidump("  q= ", q );
 293       log_mpidump("phi= ", phi );
 294       log_mpidump("  g= ", g );
 295       log_mpidump("  f= ", f );
 296       log_mpidump("  n= ", n );
 297       log_mpidump("  e= ", e );
 298       log_mpidump("  d= ", d );
 299       log_mpidump("  u= ", u );
 300     }
 301
 302   gcry_mpi_release (t1);
 303   gcry_mpi_release (t2);
 304   gcry_mpi_release (phi);
 305   gcry_mpi_release (f);
 306   gcry_mpi_release (g);
 307
 308   sk->n = n;
 309   sk->e = e;
 310   sk->p = p;
 311   sk->q = q;
 312   sk->d = d;
 313   sk->u = u;
 314
 315   /* Now we can test our keys. */
 316   if (test_keys (sk, nbits - 64))
 317     {
 318       gcry_mpi_release (sk->n); sk->n = NULL;
 319       gcry_mpi_release (sk->e); sk->e = NULL;
 320       gcry_mpi_release (sk->p); sk->p = NULL;
 321       gcry_mpi_release (sk->q); sk->q = NULL;
 322       gcry_mpi_release (sk->d); sk->d = NULL;
 323       gcry_mpi_release (sk->u); sk->u = NULL;
 324       fips_signal_error ("self-test after key generation failed");
 325       return GPG_ERR_SELFTEST_FAILED;
 326     }
 327
 328   return 0;
 329 }
 330
 331
 332 /* Helper for generate_x931.  */
 333 static gcry_mpi_t
 334 gen_x931_parm_xp (unsigned int nbits)
 335 {
 336   gcry_mpi_t xp;
 337
 338   xp = gcry_mpi_snew (nbits);
 339   gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
 340
 341   /* The requirement for Xp is:
 342
 343        sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
 344
 345      We set the two high order bits to 1 to satisfy the lower bound.
 346      By using mpi_set_highbit we make sure that the upper bound is
 347      satisfied as well.  */
 348   mpi_set_highbit (xp, nbits-1);
 349   mpi_set_bit (xp, nbits-2);
 350   gcry_assert ( mpi_get_nbits (xp) == nbits );
 351
 352   return xp;
 353 }
 354
 355
 356 /* Helper for generate_x931.  */
 357 static gcry_mpi_t
 358 gen_x931_parm_xi (void)
 359 {
 360   gcry_mpi_t xi;
 361
 362   xi = gcry_mpi_snew (101);
 363   gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM);
 364   mpi_set_highbit (xi, 100);
 365   gcry_assert ( mpi_get_nbits (xi) == 101 );
 366
 367   return xi;
 368 }
 369
 370
 371
 372 /* Variant of the standard key generation code using the algorithm
 373    from X9.31.  Using this algorithm has the advantage that the
 374    generation can be made deterministic which is required for CAVS
 375    testing.  */
 376 static gpg_err_code_t
 377 generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
 378                gcry_sexp_t deriveparms, int *swapped)
 379 {
 380   gcry_mpi_t p, q; /* The two primes.  */
 381   gcry_mpi_t e;    /* The public exponent.  */
 382   gcry_mpi_t n;    /* The public key.  */
 383   gcry_mpi_t d;    /* The private key */
 384   gcry_mpi_t u;    /* The inverse of p and q.  */
 385   gcry_mpi_t pm1;  /* p - 1  */
 386   gcry_mpi_t qm1;  /* q - 1  */
 387   gcry_mpi_t phi;  /* Euler totient.  */
 388   gcry_mpi_t f, g; /* Helper.  */
 389
 390   *swapped = 0;
 391
 392   if (e_value == 1)   /* Alias for a secure value. */
 393     e_value = 65537;
 394
 395   /* Point 1 of section 4.1:  k = 1024 + 256s with S >= 0  */
 396   if (nbits < 1024 || (nbits % 256))
 397     return GPG_ERR_INV_VALUE;
 398
 399   /* Point 2:  2 <= bitlength(e) < 2^{k-2}
 400      Note that we do not need to check the upper bound because we use
 401      an unsigned long for E and thus there is no way for E to reach
 402      that limit.  */
 403   if (e_value < 3)
 404     return GPG_ERR_INV_VALUE;
 405
 406   /* Our implementaion requires E to be odd.  */
 407   if (!(e_value & 1))
 408     return GPG_ERR_INV_VALUE;
 409
 410   /* Point 3:  e > 0 or e 0 if it is to be randomly generated.
 411      We support only a fixed E and thus there is no need for an extra test.  */
 412
 413
 414   /* Compute or extract the derive parameters.  */
 415   {
 416     gcry_mpi_t xp1 = NULL;
 417     gcry_mpi_t xp2 = NULL;
 418     gcry_mpi_t xp  = NULL;
 419     gcry_mpi_t xq1 = NULL;
 420     gcry_mpi_t xq2 = NULL;
 421     gcry_mpi_t xq  = NULL;
 422     gcry_mpi_t tmpval;
 423
 424     if (!deriveparms)
 425       {
 426         /* Not given: Generate them.  */
 427         xp = gen_x931_parm_xp (nbits/2);
 428         /* Make sure that |xp - xq| > 2^{nbits - 100} holds.  */
 429         tmpval = gcry_mpi_snew (nbits/2);
 430         do
 431           {
 432             gcry_mpi_release (xq);
 433             xq = gen_x931_parm_xp (nbits/2);
 434             mpi_sub (tmpval, xp, xq);
 435           }
 436         while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
 437         gcry_mpi_release (tmpval);
 438
 439         xp1 = gen_x931_parm_xi ();
 440         xp2 = gen_x931_parm_xi ();
 441         xq1 = gen_x931_parm_xi ();
 442         xq2 = gen_x931_parm_xi ();
 443
 444       }
 445     else
 446       {
 447         /* Parameters to derive the key are given.  */
 448         /* Note that we explicitly need to setup the values of tbl
 449            because some compilers (e.g. OpenWatcom, IRIX) don't allow
 450            to initialize a structure with automatic variables.  */
 451         struct { const char *name; gcry_mpi_t *value; } tbl[] = {
 452           { "Xp1" },
 453           { "Xp2" },
 454           { "Xp"  },
 455           { "Xq1" },
 456           { "Xq2" },
 457           { "Xq"  },
 458           { NULL }
 459         };
 460         int idx;
 461         gcry_sexp_t oneparm;
 462
 463         tbl[0].value = &xp1;
 464         tbl[1].value = &xp2;
 465         tbl[2].value = &xp;
 466         tbl[3].value = &xq1;
 467         tbl[4].value = &xq2;
 468         tbl[5].value = &xq;
 469
 470         for (idx=0; tbl[idx].name; idx++)
 471           {
 472             oneparm = gcry_sexp_find_token (deriveparms, tbl[idx].name, 0);
 473             if (oneparm)
 474               {
 475                 *tbl[idx].value = gcry_sexp_nth_mpi (oneparm, 1,
 476                                                      GCRYMPI_FMT_USG);
 477                 gcry_sexp_release (oneparm);
 478               }
 479           }
 480         for (idx=0; tbl[idx].name; idx++)
 481           if (!*tbl[idx].value)
 482             break;
 483         if (tbl[idx].name)
 484           {
 485             /* At least one parameter is missing.  */
 486             for (idx=0; tbl[idx].name; idx++)
 487               gcry_mpi_release (*tbl[idx].value);
 488             return GPG_ERR_MISSING_VALUE;
 489           }
 490       }
 491
 492     e = mpi_alloc_set_ui (e_value);
 493
 494     /* Find two prime numbers.  */
 495     p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL);
 496     q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL);
 497     gcry_mpi_release (xp);  xp  = NULL;
 498     gcry_mpi_release (xp1); xp1 = NULL;
 499     gcry_mpi_release (xp2); xp2 = NULL;
 500     gcry_mpi_release (xq);  xq  = NULL;
 501     gcry_mpi_release (xq1); xq1 = NULL;
 502     gcry_mpi_release (xq2); xq2 = NULL;
 503     if (!p || !q)
 504       {
 505         gcry_mpi_release (p);
 506         gcry_mpi_release (q);
 507         gcry_mpi_release (e);
 508         return GPG_ERR_NO_PRIME;
 509       }
 510   }
 511
 512
 513   /* Compute the public modulus.  We make sure that p is smaller than
 514      q to allow the use of the CRT.  */
 515   if (mpi_cmp (p, q) > 0 )
 516     {
 517       mpi_swap (p, q);
 518       *swapped = 1;
 519     }
 520   n = gcry_mpi_new (nbits);
 521   mpi_mul (n, p, q);
 522
 523   /* Compute the Euler totient:  phi = (p-1)(q-1)  */
 524   pm1 = gcry_mpi_snew (nbits/2);
 525   qm1 = gcry_mpi_snew (nbits/2);
 526   phi = gcry_mpi_snew (nbits);
 527   mpi_sub_ui (pm1, p, 1);
 528   mpi_sub_ui (qm1, q, 1);
 529   mpi_mul (phi, pm1, qm1);
 530
 531   g = gcry_mpi_snew (nbits);
 532   gcry_assert (gcry_mpi_gcd (g, e, phi));
 533
 534   /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
 535   gcry_mpi_gcd (g, pm1, qm1);
 536   f = pm1; pm1 = NULL;
 537   gcry_mpi_release (qm1); qm1 = NULL;
 538   mpi_fdiv_q (f, phi, g);
 539   gcry_mpi_release (phi); phi = NULL;
 540   d = g; g = NULL;
 541   /* Compute the secret key:  d = e^{-1} mod lcm(p-1,q-1) */
 542   mpi_invm (d, e, f);
 543
 544   /* Compute the inverse of p and q.  */
 545   u = f; f = NULL;
 546   mpi_invm (u, p, q );
 547
 548   if( DBG_CIPHER )
 549     {
 550       if (*swapped)
 551         log_debug ("p and q are swapped\n");
 552       log_mpidump("  p", p );
 553       log_mpidump("  q", q );
 554       log_mpidump("  n", n );
 555       log_mpidump("  e", e );
 556       log_mpidump("  d", d );
 557       log_mpidump("  u", u );
 558     }
 559
 560
 561   sk->n = n;
 562   sk->e = e;
 563   sk->p = p;
 564   sk->q = q;
 565   sk->d = d;
 566   sk->u = u;
 567
 568   /* Now we can test our keys. */
 569   if (test_keys (sk, nbits - 64))
 570     {
 571       gcry_mpi_release (sk->n); sk->n = NULL;
 572       gcry_mpi_release (sk->e); sk->e = NULL;
 573       gcry_mpi_release (sk->p); sk->p = NULL;
 574       gcry_mpi_release (sk->q); sk->q = NULL;
 575       gcry_mpi_release (sk->d); sk->d = NULL;
 576       gcry_mpi_release (sk->u); sk->u = NULL;
 577       fips_signal_error ("self-test after key generation failed");
 578       return GPG_ERR_SELFTEST_FAILED;
 579     }
 580
 581   return 0;
 582 }
 583
 584
 585 /****************
 586  * Test whether the secret key is valid.
 587  * Returns: true if this is a valid key.
 588  */
 589 static int
 590 check_secret_key( RSA_secret_key *sk )
 591 {
 592   int rc;
 593   gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
 594
 595   mpi_mul(temp, sk->p, sk->q );
 596   rc = mpi_cmp( temp, sk->n );
 597   mpi_free(temp);
 598   return !rc;
 599 }
 600
 601
 602
 603 /****************
 604  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
 605  *
 606  *      c = m^e mod n
 607  *
 608  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
 609  */
 610 static void
 611 public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
 612 {
 613   if( output == input )  /* powm doesn't like output and input the same */
 614     {
 615       gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
 616       mpi_powm( x, input, pkey->e, pkey->n );
 617       mpi_set(output, x);
 618       mpi_free(x);
 619     }
 620   else
 621     mpi_powm( output, input, pkey->e, pkey->n );
 622 }
 623
 624 #if 0
 625 static void
 626 stronger_key_check ( RSA_secret_key *skey )
 627 {
 628   gcry_mpi_t t = mpi_alloc_secure ( 0 );
 629   gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
 630   gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
 631   gcry_mpi_t phi = mpi_alloc_secure ( 0 );
 632
 633   /* check that n == p * q */
 634   mpi_mul( t, skey->p, skey->q);
 635   if (mpi_cmp( t, skey->n) )
 636     log_info ( "RSA Oops: n != p * q\n" );
 637
 638   /* check that p is less than q */
 639   if( mpi_cmp( skey->p, skey->q ) > 0 )
 640     {
 641       log_info ("RSA Oops: p >= q - fixed\n");
 642       _gcry_mpi_swap ( skey->p, skey->q);
 643     }
 644
 645     /* check that e divides neither p-1 nor q-1 */
 646     mpi_sub_ui(t, skey->p, 1 );
 647     mpi_fdiv_r(t, t, skey->e );
 648     if ( !mpi_cmp_ui( t, 0) )
 649         log_info ( "RSA Oops: e divides p-1\n" );
 650     mpi_sub_ui(t, skey->q, 1 );
 651     mpi_fdiv_r(t, t, skey->e );
 652     if ( !mpi_cmp_ui( t, 0) )
 653         log_info ( "RSA Oops: e divides q-1\n" );
 654
 655     /* check that d is correct */
 656     mpi_sub_ui( t1, skey->p, 1 );
 657     mpi_sub_ui( t2, skey->q, 1 );
 658     mpi_mul( phi, t1, t2 );
 659     gcry_mpi_gcd(t, t1, t2);
 660     mpi_fdiv_q(t, phi, t);
 661     mpi_invm(t, skey->e, t );
 662     if ( mpi_cmp(t, skey->d ) )
 663       {
 664         log_info ( "RSA Oops: d is wrong - fixed\n");
 665         mpi_set (skey->d, t);
 666         log_printmpi ("  fixed d", skey->d);
 667       }
 668
 669     /* check for correctness of u */
 670     mpi_invm(t, skey->p, skey->q );
 671     if ( mpi_cmp(t, skey->u ) )
 672       {
 673         log_info ( "RSA Oops: u is wrong - fixed\n");
 674         mpi_set (skey->u, t);
 675         log_printmpi ("  fixed u", skey->u);
 676       }
 677
 678     log_info ( "RSA secret key check finished\n");
 679
 680     mpi_free (t);
 681     mpi_free (t1);
 682     mpi_free (t2);
 683     mpi_free (phi);
 684 }
 685 #endif
 686
 687
 688
 689 /****************
 690  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
 691  *
 692  *      m = c^d mod n
 693  *
 694  * Or faster:
 695  *
 696  *      m1 = c ^ (d mod (p-1)) mod p
 697  *      m2 = c ^ (d mod (q-1)) mod q
 698  *      h = u * (m2 - m1) mod q
 699  *      m = m1 + h * p
 700  *
 701  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
 702  */
 703 static void
 704 secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
 705 {
 706   if (!skey->p || !skey->q || !skey->u)
 707     {
 708       mpi_powm (output, input, skey->d, skey->n);
 709     }
 710   else
 711     {
 712       gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
 713       gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
 714       gcry_mpi_t h  = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
 715
 716       /* m1 = c ^ (d mod (p-1)) mod p */
 717       mpi_sub_ui( h, skey->p, 1  );
 718       mpi_fdiv_r( h, skey->d, h );
 719       mpi_powm( m1, input, h, skey->p );
 720       /* m2 = c ^ (d mod (q-1)) mod q */
 721       mpi_sub_ui( h, skey->q, 1  );
 722       mpi_fdiv_r( h, skey->d, h );
 723       mpi_powm( m2, input, h, skey->q );
 724       /* h = u * ( m2 - m1 ) mod q */
 725       mpi_sub( h, m2, m1 );
 726       if ( mpi_has_sign ( h ) )
 727         mpi_add ( h, h, skey->q );
 728       mpi_mulm( h, skey->u, h, skey->q );
 729       /* m = m2 + h * p */
 730       mpi_mul ( h, h, skey->p );
 731       mpi_add ( output, m1, h );
 732
 733       mpi_free ( h );
 734       mpi_free ( m1 );
 735       mpi_free ( m2 );
 736     }
 737 }
 738
 739
 740
 741 /*********************************************
 742  **************  interface  ******************
 743  *********************************************/
 744
 745 static gcry_err_code_t
 746 rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
 747 {
 748   gpg_err_code_t ec;
 749   unsigned int nbits;
 750   unsigned long evalue;
 751   RSA_secret_key sk;
 752   gcry_sexp_t deriveparms;
 753   int transient_key = 0;
 754   int use_x931 = 0;
 755   gcry_sexp_t l1;
 756   gcry_sexp_t swap_info = NULL;
 757
 758   memset (&sk, 0, sizeof sk);
 759
 760   ec = _gcry_pk_util_get_nbits (genparms, &nbits);
 761   if (ec)
 762     return ec;
 763
 764   ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue);
 765   if (ec)
 766     return ec;
 767
 768   deriveparms = (genparms?
 769                  gcry_sexp_find_token (genparms, "derive-parms", 0) : NULL);
 770   if (!deriveparms)
 771     {
 772       /* Parse the optional "use-x931" flag. */
 773       l1 = gcry_sexp_find_token (genparms, "use-x931", 0);
 774       if (l1)
 775         {
 776           use_x931 = 1;
 777           gcry_sexp_release (l1);
 778         }
 779     }
 780
 781   if (deriveparms || use_x931 || fips_mode ())
 782     {
 783       int swapped;
 784       ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
 785       gcry_sexp_release (deriveparms);
 786       if (!ec && swapped)
 787         ec = gcry_sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1);
 788     }
 789   else
 790     {
 791       /* Parse the optional "transient-key" flag. */
 792       l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
 793       if (l1)
 794         {
 795           transient_key = 1;
 796           gcry_sexp_release (l1);
 797         }
 798       /* Generate.  */
 799       ec = generate_std (&sk, nbits, evalue, transient_key);
 800     }
 801
 802   if (!ec)
 803     {
 804       ec = gcry_sexp_build (r_skey, NULL,
 805                             "(key-data"
 806                             " (public-key"
 807                             "  (rsa(n%m)(e%m)))"
 808                             " (private-key"
 809                             "  (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))"
 810                             " %S)",
 811                             sk.n, sk.e,
 812                             sk.n, sk.e, sk.d, sk.p, sk.q, sk.u,
 813                             swap_info);
 814     }
 815
 816   mpi_free (sk.n);
 817   mpi_free (sk.e);
 818   mpi_free (sk.p);
 819   mpi_free (sk.q);
 820   mpi_free (sk.d);
 821   mpi_free (sk.u);
 822   gcry_sexp_release (swap_info);
 823
 824   return ec;
 825 }
 826
 827
 828 static gcry_err_code_t
 829 rsa_check_secret_key (int algo, gcry_mpi_t *skey)
 830 {
 831   gcry_err_code_t err = GPG_ERR_NO_ERROR;
 832   RSA_secret_key sk;
 833
 834   (void)algo;
 835
 836   sk.n = skey[0];
 837   sk.e = skey[1];
 838   sk.d = skey[2];
 839   sk.p = skey[3];
 840   sk.q = skey[4];
 841   sk.u = skey[5];
 842
 843   if (!sk.p || !sk.q || !sk.u)
 844     err = GPG_ERR_NO_OBJ;  /* To check the key we need the optional
 845                               parameters. */
 846   else if (!check_secret_key (&sk))
 847     err = GPG_ERR_BAD_SECKEY;
 848
 849   return err;
 850 }
 851
 852
 853 static gcry_err_code_t
 854 rsa_encrypt (int algo, gcry_sexp_t *r_result, gcry_mpi_t data,
 855              gcry_mpi_t *pkey, int flags)
 856 {
 857   gpg_err_code_t rc;
 858   RSA_public_key pk;
 859   gcry_mpi_t result;
 860
 861   (void)algo;
 862   (void)flags;
 863
 864   pk.n = pkey[0];
 865   pk.e = pkey[1];
 866   result = mpi_alloc (mpi_get_nlimbs (pk.n));
 867   public (result, data, &pk);
 868   if ((flags & PUBKEY_FLAG_FIXEDLEN))
 869     {
 870       /* We need to make sure to return the correct length to avoid
 871          problems with missing leading zeroes.  */
 872       unsigned char *em;
 873       size_t emlen = (mpi_get_nbits (pk.n)+7)/8;
 874
 875       rc = _gcry_mpi_to_octet_string (&em, NULL, result, emlen);
 876       if (!rc)
 877         {
 878           rc = gcry_sexp_build (r_result, NULL,
 879                                 "(enc-val(rsa(a%b)))", (int)emlen, em);
 880           gcry_free (em);
 881         }
 882     }
 883   else
 884     rc = gcry_sexp_build (r_result, NULL, "(enc-val(rsa(a%m)))", result);
 885
 886   mpi_free (result);
 887   return rc;
 888 }
 889
 890
 891 static gcry_err_code_t
 892 rsa_decrypt (int algo, gcry_sexp_t *r_plain, gcry_mpi_t *data,
 893              gcry_mpi_t *skey, int flags,
 894              enum pk_encoding encoding, int hash_algo,
 895              unsigned char *label, size_t labellen)
 896
 897 {
 898   gpg_err_code_t rc;
 899   RSA_secret_key sk;
 900   gcry_mpi_t plain;             /* Decrypted data.  */
 901   unsigned char *unpad = NULL;
 902   size_t unpadlen = 0;
 903   unsigned int nbits;
 904
 905   (void)algo;
 906
 907   /* Extract private key.  */
 908   sk.n = skey[0];
 909   sk.e = skey[1];
 910   sk.d = skey[2];
 911   sk.p = skey[3]; /* Optional. */
 912   sk.q = skey[4]; /* Optional. */
 913   sk.u = skey[5]; /* Optional. */
 914
 915   nbits = gcry_mpi_get_nbits (sk.n);
 916
 917   plain = gcry_mpi_snew (nbits);
 918
 919   /* We use blinding by default to mitigate timing attacks which can
 920      be practically mounted over the network as shown by Brumley and
 921      Boney in 2003.  */
 922   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
 923     {
 924       gcry_mpi_t r;     /* Random number needed for blinding.  */
 925       gcry_mpi_t ri;    /* Modular multiplicative inverse of r.  */
 926       gcry_mpi_t ciph;  /* Blinded data to decrypt.  */
 927
 928       /* First, we need a random number r between 0 and n - 1, which
 929          is relatively prime to n (i.e. it is neither p nor q).  The
 930          random number needs to be only unpredictable, thus we employ
 931          the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
 932          gcry_mpi_randomize.  */
 933       r = gcry_mpi_snew (nbits);
 934       ri = gcry_mpi_snew (nbits);
 935       ciph = gcry_mpi_snew (nbits);
 936
 937       gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);
 938       gcry_mpi_mod (r, r, sk.n);
 939
 940       /* Calculate inverse of r.  It practically impossible that the
 941          following test fails, thus we do not add code to release
 942          allocated resources.  */
 943       if (!gcry_mpi_invm (ri, r, sk.n))
 944         return GPG_ERR_INTERNAL;
 945
 946       /* Do blinding.  We calculate: y = (x * r^e) mod n, where r is
 947          the random number, e is the public exponent, x is the
 948          non-blinded data and n is the RSA modulus.  */
 949       gcry_mpi_powm (ciph, r, sk.e, sk.n);
 950       gcry_mpi_mulm (ciph, ciph, data[0], sk.n);
 951
 952       /* Perform decryption.  */
 953       secret (plain, ciph, &sk);
 954
 955       /* Undo blinding.  Here we calculate: y = (x * r^-1) mod n,
 956          where x is the blinded decrypted data, ri is the modular
 957          multiplicative inverse of r and n is the RSA modulus.  */
 958       gcry_mpi_mulm (plain, plain, ri, sk.n);
 959
 960       gcry_mpi_release (ciph);
 961       gcry_mpi_release (r);
 962       gcry_mpi_release (ri);
 963     }
 964   else
 965     secret (plain, data[0], &sk);
 966
 967   /* Reverse the encoding and build the s-expression.  */
 968   switch (encoding)
 969     {
 970     case PUBKEY_ENC_PKCS1:
 971       rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, nbits, plain);
 972       mpi_free (plain);
 973       plain = NULL;
 974       if (!rc)
 975         rc = gcry_sexp_build (r_plain, NULL,
 976                               "(value %b)", (int)unpadlen, unpad);
 977       break;
 978
 979     case PUBKEY_ENC_OAEP:
 980       rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
 981                                   nbits, hash_algo, plain, label, labellen);
 982       mpi_free (plain);
 983       plain = NULL;
 984       if (!rc)
 985         rc = gcry_sexp_build (r_plain, NULL,
 986                               "(value %b)", (int)unpadlen, unpad);
 987       break;
 988
 989     default:
 990       /* Raw format.  For backward compatibility we need to assume a
 991          signed mpi by using the sexp format string "%m".  */
 992       rc = gcry_sexp_build (r_plain, NULL,
 993                             (flags & PUBKEY_FLAG_LEGACYRESULT)
 994                             ? "%m":"(value %m)", plain);
 995       break;
 996     }
 997
 998   gcry_free (unpad);
 999   mpi_free (plain);
1000
1001   return rc;
1002 }
1003
1004
1005 static gcry_err_code_t
1006 rsa_sign (int algo, gcry_sexp_t *r_result, gcry_mpi_t data, gcry_mpi_t *skey,
1007           int flags, int hashalgo)
1008 {
1009   gpg_err_code_t rc;
1010   RSA_secret_key sk;
1011   gcry_mpi_t result;
1012
1013   (void)algo;
1014   (void)flags;
1015   (void)hashalgo;
1016
1017   if (mpi_is_opaque (data))
1018     return GPG_ERR_INV_DATA;
1019
1020   sk.n = skey[0];
1021   sk.e = skey[1];
1022   sk.d = skey[2];
1023   sk.p = skey[3];
1024   sk.q = skey[4];
1025   sk.u = skey[5];
1026   result = mpi_alloc (mpi_get_nlimbs (sk.n));
1027   secret (result, data, &sk);
1028   if ((flags & PUBKEY_FLAG_FIXEDLEN))
1029     {
1030       /* We need to make sure to return the correct length to avoid
1031          problems with missing leading zeroes.  */
1032       unsigned char *em;
1033       size_t emlen = (mpi_get_nbits (sk.n)+7)/8;
1034
1035       rc = _gcry_mpi_to_octet_string (&em, NULL, result, emlen);
1036       if (!rc)
1037         {
1038           rc = gcry_sexp_build (r_result, NULL,
1039                                 "(sig-val(rsa(s%b)))", (int)emlen, em);
1040           gcry_free (em);
1041         }
1042     }
1043   else
1044     rc = gcry_sexp_build (r_result, NULL, "(sig-val(rsa(s%M)))",  result);
1045   mpi_free (result);
1046
1047   return rc;
1048 }
1049
1050
1051 static gcry_err_code_t
1052 rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1053             int (*cmp) (void *opaque, gcry_mpi_t tmp), void *opaquev,
1054             int flags, int hashalgo)
1055 {
1056   RSA_public_key pk;
1057   gcry_mpi_t result;
1058   gcry_err_code_t rc;
1059
1060   (void)algo;
1061   (void)cmp;
1062   (void)opaquev;
1063   (void)flags;
1064   (void)hashalgo;
1065
1066   if (mpi_is_opaque (hash))
1067     return GPG_ERR_INV_DATA;
1068
1069   pk.n = pkey[0];
1070   pk.e = pkey[1];
1071   result = gcry_mpi_new ( 160 );
1072   public( result, data[0], &pk );
1073 #ifdef IS_DEVELOPMENT_VERSION
1074   if (DBG_CIPHER)
1075     {
1076       log_mpidump ("rsa verify result", result );
1077       log_mpidump ("             hash", hash );
1078     }
1079 #endif /*IS_DEVELOPMENT_VERSION*/
1080   if (cmp)
1081     rc = (*cmp) (opaquev, result);
1082   else
1083     rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
1084   gcry_mpi_release (result);
1085
1086   return rc;
1087 }
1088
1089
1090 static unsigned int
1091 rsa_get_nbits (int algo, gcry_mpi_t *pkey)
1092 {
1093   (void)algo;
1094
1095   return mpi_get_nbits (pkey[0]);
1096 }
1097
1098
1099 /* Compute a keygrip.  MD is the hash context which we are going to
1100    update.  KEYPARAM is an S-expression with the key parameters, this
1101    is usually a public key but may also be a secret key.  An example
1102    of such an S-expression is:
1103
1104       (rsa
1105         (n #00B...#)
1106         (e #010001#))
1107
1108    PKCS-15 says that for RSA only the modulus should be hashed -
1109    however, it is not clear whether this is meant to use the raw bytes
1110    (assuming this is an unsigned integer) or whether the DER required
1111    0 should be prefixed.  We hash the raw bytes.  */
1112 static gpg_err_code_t
1113 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1114 {
1115   gcry_sexp_t l1;
1116   const char *data;
1117   size_t datalen;
1118
1119   l1 = gcry_sexp_find_token (keyparam, "n", 1);
1120   if (!l1)
1121     return GPG_ERR_NO_OBJ;
1122
1123   data = gcry_sexp_nth_data (l1, 1, &datalen);
1124   if (!data)
1125     {
1126       gcry_sexp_release (l1);
1127       return GPG_ERR_NO_OBJ;
1128     }
1129
1130   gcry_md_write (md, data, datalen);
1131   gcry_sexp_release (l1);
1132
1133   return 0;
1134 }
1135
1136
1137
1138 \f
1139 /*
1140      Self-test section.
1141  */
1142
1143 static const char *
1144 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1145 {
1146   static const char sample_data[] =
1147     "(data (flags pkcs1)"
1148     " (hash sha1 #11223344556677889900aabbccddeeff10203040#))";
1149   static const char sample_data_bad[] =
1150     "(data (flags pkcs1)"
1151     " (hash sha1 #11223344556677889900aabbccddeeff80203040#))";
1152
1153   const char *errtxt = NULL;
1154   gcry_error_t err;
1155   gcry_sexp_t data = NULL;
1156   gcry_sexp_t data_bad = NULL;
1157   gcry_sexp_t sig = NULL;
1158
1159   err = gcry_sexp_sscan (&data, NULL,
1160                          sample_data, strlen (sample_data));
1161   if (!err)
1162     err = gcry_sexp_sscan (&data_bad, NULL,
1163                            sample_data_bad, strlen (sample_data_bad));
1164   if (err)
1165     {
1166       errtxt = "converting data failed";
1167       goto leave;
1168     }
1169
1170   err = gcry_pk_sign (&sig, data, skey);
1171   if (err)
1172     {
1173       errtxt = "signing failed";
1174       goto leave;
1175     }
1176   err = gcry_pk_verify (sig, data, pkey);
1177   if (err)
1178     {
1179       errtxt = "verify failed";
1180       goto leave;
1181     }
1182   err = gcry_pk_verify (sig, data_bad, pkey);
1183   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1184     {
1185       errtxt = "bad signature not detected";
1186       goto leave;
1187     }
1188
1189
1190  leave:
1191   gcry_sexp_release (sig);
1192   gcry_sexp_release (data_bad);
1193   gcry_sexp_release (data);
1194   return errtxt;
1195 }
1196
1197
1198
1199 /* Given an S-expression ENCR_DATA of the form:
1200
1201    (enc-val
1202     (rsa
1203      (a a-value)))
1204
1205    as returned by gcry_pk_decrypt, return the the A-VALUE.  On error,
1206    return NULL.  */
1207 static gcry_mpi_t
1208 extract_a_from_sexp (gcry_sexp_t encr_data)
1209 {
1210   gcry_sexp_t l1, l2, l3;
1211   gcry_mpi_t a_value;
1212
1213   l1 = gcry_sexp_find_token (encr_data, "enc-val", 0);
1214   if (!l1)
1215     return NULL;
1216   l2 = gcry_sexp_find_token (l1, "rsa", 0);
1217   gcry_sexp_release (l1);
1218   if (!l2)
1219     return NULL;
1220   l3 = gcry_sexp_find_token (l2, "a", 0);
1221   gcry_sexp_release (l2);
1222   if (!l3)
1223     return NULL;
1224   a_value = gcry_sexp_nth_mpi (l3, 1, 0);
1225   gcry_sexp_release (l3);
1226
1227   return a_value;
1228 }
1229
1230
1231 static const char *
1232 selftest_encr_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1233 {
1234   const char *errtxt = NULL;
1235   gcry_error_t err;
1236   const unsigned int nbits = 1000; /* Encrypt 1000 random bits.  */
1237   gcry_mpi_t plaintext = NULL;
1238   gcry_sexp_t plain = NULL;
1239   gcry_sexp_t encr  = NULL;
1240   gcry_mpi_t  ciphertext = NULL;
1241   gcry_sexp_t decr  = NULL;
1242   gcry_mpi_t  decr_plaintext = NULL;
1243   gcry_sexp_t tmplist = NULL;
1244
1245   /* Create plaintext.  The plaintext is actually a big integer number.  */
1246   plaintext = gcry_mpi_new (nbits);
1247   gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
1248
1249   /* Put the plaintext into an S-expression.  */
1250   err = gcry_sexp_build (&plain, NULL,
1251                          "(data (flags raw) (value %m))", plaintext);
1252   if (err)
1253     {
1254       errtxt = "converting data failed";
1255       goto leave;
1256     }
1257
1258   /* Encrypt.  */
1259   err = gcry_pk_encrypt (&encr, plain, pkey);
1260   if (err)
1261     {
1262       errtxt = "encrypt failed";
1263       goto leave;
1264     }
1265
1266   /* Extraxt the ciphertext from the returned S-expression.  */
1267   /*gcry_sexp_dump (encr);*/
1268   ciphertext = extract_a_from_sexp (encr);
1269   if (!ciphertext)
1270     {
1271       errtxt = "gcry_pk_decrypt returned garbage";
1272       goto leave;
1273     }
1274
1275   /* Check that the ciphertext does no match the plaintext.  */
1276   /* _gcry_log_mpidump ("plaintext", plaintext); */
1277   /* _gcry_log_mpidump ("ciphertxt", ciphertext); */
1278   if (!gcry_mpi_cmp (plaintext, ciphertext))
1279     {
1280       errtxt = "ciphertext matches plaintext";
1281       goto leave;
1282     }
1283
1284   /* Decrypt.  */
1285   err = gcry_pk_decrypt (&decr, encr, skey);
1286   if (err)
1287     {
1288       errtxt = "decrypt failed";
1289       goto leave;
1290     }
1291
1292   /* Extract the decrypted data from the S-expression.  Note that the
1293      output of gcry_pk_decrypt depends on whether a flags lists occurs
1294      in its input data.  Because we passed the output of
1295      gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
1296      won't be there as of today.  To be prepared for future changes we
1297      take care of it anyway.  */
1298   tmplist = gcry_sexp_find_token (decr, "value", 0);
1299   if (tmplist)
1300     decr_plaintext = gcry_sexp_nth_mpi (tmplist, 1, GCRYMPI_FMT_USG);
1301   else
1302     decr_plaintext = gcry_sexp_nth_mpi (decr, 0, GCRYMPI_FMT_USG);
1303   if (!decr_plaintext)
1304     {
1305       errtxt = "decrypt returned no plaintext";
1306       goto leave;
1307     }
1308
1309   /* Check that the decrypted plaintext matches the original  plaintext.  */
1310   if (gcry_mpi_cmp (plaintext, decr_plaintext))
1311     {
1312       errtxt = "mismatch";
1313       goto leave;
1314     }
1315
1316  leave:
1317   gcry_sexp_release (tmplist);
1318   gcry_mpi_release (decr_plaintext);
1319   gcry_sexp_release (decr);
1320   gcry_mpi_release (ciphertext);
1321   gcry_sexp_release (encr);
1322   gcry_sexp_release (plain);
1323   gcry_mpi_release (plaintext);
1324   return errtxt;
1325 }
1326
1327
1328 static gpg_err_code_t
1329 selftests_rsa (selftest_report_func_t report)
1330 {
1331   const char *what;
1332   const char *errtxt;
1333   gcry_error_t err;
1334   gcry_sexp_t skey = NULL;
1335   gcry_sexp_t pkey = NULL;
1336
1337   /* Convert the S-expressions into the internal representation.  */
1338   what = "convert";
1339   err = gcry_sexp_sscan (&skey, NULL,
1340                          sample_secret_key, strlen (sample_secret_key));
1341   if (!err)
1342     err = gcry_sexp_sscan (&pkey, NULL,
1343                            sample_public_key, strlen (sample_public_key));
1344   if (err)
1345     {
1346       errtxt = gcry_strerror (err);
1347       goto failed;
1348     }
1349
1350   what = "key consistency";
1351   err = gcry_pk_testkey (skey);
1352   if (err)
1353     {
1354       errtxt = gcry_strerror (err);
1355       goto failed;
1356     }
1357
1358   what = "sign";
1359   errtxt = selftest_sign_1024 (pkey, skey);
1360   if (errtxt)
1361     goto failed;
1362
1363   what = "encrypt";
1364   errtxt = selftest_encr_1024 (pkey, skey);
1365   if (errtxt)
1366     goto failed;
1367
1368   gcry_sexp_release (pkey);
1369   gcry_sexp_release (skey);
1370   return 0; /* Succeeded. */
1371
1372  failed:
1373   gcry_sexp_release (pkey);
1374   gcry_sexp_release (skey);
1375   if (report)
1376     report ("pubkey", GCRY_PK_RSA, what, errtxt);
1377   return GPG_ERR_SELFTEST_FAILED;
1378 }
1379
1380
1381 /* Run a full self-test for ALGO and return 0 on success.  */
1382 static gpg_err_code_t
1383 run_selftests (int algo, int extended, selftest_report_func_t report)
1384 {
1385   gpg_err_code_t ec;
1386
1387   (void)extended;
1388
1389   switch (algo)
1390     {
1391     case GCRY_PK_RSA:
1392       ec = selftests_rsa (report);
1393       break;
1394     default:
1395       ec = GPG_ERR_PUBKEY_ALGO;
1396       break;
1397
1398     }
1399   return ec;
1400 }
1401
1402
1403
1404 \f
1405 static const char *rsa_names[] =
1406   {
1407     "rsa",
1408     "openpgp-rsa",
1409     "oid.1.2.840.113549.1.1.1",
1410     NULL,
1411   };
1412
1413 gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1414   {
1415     GCRY_PK_RSA, { 0, 1 },
1416     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1417     "RSA", rsa_names,
1418     "ne", "nedpqu", "a", "s", "n",
1419     rsa_generate,
1420     rsa_check_secret_key,
1421     rsa_encrypt,
1422     rsa_decrypt,
1423     rsa_sign,
1424     rsa_verify,
1425     rsa_get_nbits,
1426     run_selftests,
1427     compute_keygrip
1428   };