rsa: Use 2048 bit RSA keys for selftest.
[libgcrypt.git] / 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 static const char *rsa_names[] =
57   {
58     "rsa",
59     "openpgp-rsa",
60     "oid.1.2.840.113549.1.1.1",
61     NULL,
62   };
63
64
65 /* A sample 2048 bit RSA key used for the selftests.  */
66 static const char sample_secret_key[] =
67 " (private-key"
68 "  (rsa"
69 "  (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC"
70 "      7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8"
71 "      7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C"
72 "      958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917"
73 "      DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613"
74 "      6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C"
75 "      42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918"
76 "      664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)"
77 "   (e #010001#)"
78 "   (d #07EF82500C403899934FE993AC5A36F14FF2DF38CF1EF315F205EE4C83EDAA19"
79 "       8890FC23DE9AA933CAFB37B6A8A8DBA675411958337287310D3FF2F1DDC0CB93"
80 "       7E70F57F75F833C021852B631D2B9A520E4431A03C5C3FCB5742DCD841D9FB12"
81 "       771AA1620DCEC3F1583426066ED9DC3F7028C5B59202C88FDF20396E2FA0EC4F"
82 "       5A22D9008F3043673931BC14A5046D6327398327900867E39CC61B2D1AFE2F48"
83 "       EC8E1E3861C68D257D7425F4E6F99ABD77D61F10CA100EFC14389071831B33DD"
84 "       69CC8EABEF860D1DC2AAA84ABEAE5DFC91BC124DAF0F4C8EF5BBEA436751DE84"
85 "       3A8063E827A024466F44C28614F93B0732A100D4A0D86D532FE1E22C7725E401#)"
86 "   (p #00C29D438F115825779631CD665A5739367F3E128ADC29766483A46CA80897E0"
87 "       79B32881860B8F9A6A04C2614A904F6F2578DAE13EA67CD60AE3D0AA00A1FF9B"
88 "       441485E44B2DC3D0B60260FBFE073B5AC72FAF67964DE15C8212C389D20DB9CF"
89 "       54AF6AEF5C4196EAA56495DD30CF709F499D5AB30CA35E086C2A1589D6283F1783#)"
90 "   (q #00D1984135231CB243FE959C0CBEF551EDD986AD7BEDF71EDF447BE3DA27AF46"
91 "       79C974A6FA69E4D52FE796650623DE70622862713932AA2FD9F2EC856EAEAA77"
92 "       88B4EA6084DC81C902F014829B18EA8B2666EC41586818E0589E18876065F97E"
93 "       8D22CE2DA53A05951EC132DCEF41E70A9C35F4ACC268FFAC2ADF54FA1DA110B919#)"
94 "   (u #67CF0FD7635205DD80FA814EE9E9C267C17376BF3209FB5D1BC42890D2822A04"
95 "       479DAF4D5B6ED69D0F8D1AF94164D07F8CD52ECEFE880641FA0F41DDAB1785E4"
96 "       A37A32F997A516480B4CD4F6482B9466A1765093ED95023CA32D5EDC1E34CEE9"
97 "       AF595BC51FE43C4BF810FA225AF697FB473B83815966188A4312C048B885E3F7#)))";
98
99 /* A sample 2048 bit RSA key used for the selftests (public only).  */
100 static const char sample_public_key[] =
101 " (public-key"
102 "  (rsa"
103 "   (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC"
104 "       7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8"
105 "       7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C"
106 "       958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917"
107 "       DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613"
108 "       6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C"
109 "       42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918"
110 "       664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)"
111 "   (e #010001#)))";
112
113 \f
114 static int test_keys (RSA_secret_key *sk, unsigned nbits);
115 static int  check_secret_key (RSA_secret_key *sk);
116 static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
117 static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
118 static unsigned int rsa_get_nbits (gcry_sexp_t parms);
119
120
121 /* Check that a freshly generated key actually works.  Returns 0 on success. */
122 static int
123 test_keys (RSA_secret_key *sk, unsigned int nbits)
124 {
125   int result = -1; /* Default to failure.  */
126   RSA_public_key pk;
127   gcry_mpi_t plaintext = mpi_new (nbits);
128   gcry_mpi_t ciphertext = mpi_new (nbits);
129   gcry_mpi_t decr_plaintext = mpi_new (nbits);
130   gcry_mpi_t signature = mpi_new (nbits);
131
132   /* Put the relevant parameters into a public key structure.  */
133   pk.n = sk->n;
134   pk.e = sk->e;
135
136   /* Create a random plaintext.  */
137   _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
138
139   /* Encrypt using the public key.  */
140   public (ciphertext, plaintext, &pk);
141
142   /* Check that the cipher text does not match the plaintext.  */
143   if (!mpi_cmp (ciphertext, plaintext))
144     goto leave; /* Ciphertext is identical to the plaintext.  */
145
146   /* Decrypt using the secret key.  */
147   secret (decr_plaintext, ciphertext, sk);
148
149   /* Check that the decrypted plaintext matches the original plaintext.  */
150   if (mpi_cmp (decr_plaintext, plaintext))
151     goto leave; /* Plaintext does not match.  */
152
153   /* Create another random plaintext as data for signature checking.  */
154   _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
155
156   /* Use the RSA secret function to create a signature of the plaintext.  */
157   secret (signature, plaintext, sk);
158
159   /* Use the RSA public function to verify this signature.  */
160   public (decr_plaintext, signature, &pk);
161   if (mpi_cmp (decr_plaintext, plaintext))
162     goto leave; /* Signature does not match.  */
163
164   /* Modify the signature and check that the signing fails.  */
165   mpi_add_ui (signature, signature, 1);
166   public (decr_plaintext, signature, &pk);
167   if (!mpi_cmp (decr_plaintext, plaintext))
168     goto leave; /* Signature matches but should not.  */
169
170   result = 0; /* All tests succeeded.  */
171
172  leave:
173   _gcry_mpi_release (signature);
174   _gcry_mpi_release (decr_plaintext);
175   _gcry_mpi_release (ciphertext);
176   _gcry_mpi_release (plaintext);
177   return result;
178 }
179
180
181 /* Callback used by the prime generation to test whether the exponent
182    is suitable. Returns 0 if the test has been passed. */
183 static int
184 check_exponent (void *arg, gcry_mpi_t a)
185 {
186   gcry_mpi_t e = arg;
187   gcry_mpi_t tmp;
188   int result;
189
190   mpi_sub_ui (a, a, 1);
191   tmp = _gcry_mpi_alloc_like (a);
192   result = !mpi_gcd(tmp, e, a); /* GCD is not 1. */
193   _gcry_mpi_release (tmp);
194   mpi_add_ui (a, a, 1);
195   return result;
196 }
197
198 /****************
199  * Generate a key pair with a key of size NBITS.
200  * USE_E = 0 let Libcgrypt decide what exponent to use.
201  *       = 1 request the use of a "secure" exponent; this is required by some
202  *           specification to be 65537.
203  *       > 2 Use this public exponent.  If the given exponent
204  *           is not odd one is internally added to it.
205  * TRANSIENT_KEY:  If true, generate the primes using the standard RNG.
206  * Returns: 2 structures filled with all needed values
207  */
208 static gpg_err_code_t
209 generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
210               int transient_key)
211 {
212   gcry_mpi_t p, q; /* the two primes */
213   gcry_mpi_t d;    /* the private key */
214   gcry_mpi_t u;
215   gcry_mpi_t t1, t2;
216   gcry_mpi_t n;    /* the public key */
217   gcry_mpi_t e;    /* the exponent */
218   gcry_mpi_t phi;  /* helper: (p-1)(q-1) */
219   gcry_mpi_t g;
220   gcry_mpi_t f;
221   gcry_random_level_t random_level;
222
223   if (fips_mode ())
224     {
225       if (nbits < 1024)
226         return GPG_ERR_INV_VALUE;
227       if (transient_key)
228         return GPG_ERR_INV_VALUE;
229     }
230
231   /* The random quality depends on the transient_key flag.  */
232   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
233
234   /* Make sure that nbits is even so that we generate p, q of equal size. */
235   if ( (nbits&1) )
236     nbits++;
237
238   if (use_e == 1)   /* Alias for a secure value */
239     use_e = 65537;  /* as demanded by Sphinx. */
240
241   /* Public exponent:
242      In general we use 41 as this is quite fast and more secure than the
243      commonly used 17.  Benchmarking the RSA verify function
244      with a 1024 bit key yields (2001-11-08):
245      e=17    0.54 ms
246      e=41    0.75 ms
247      e=257   0.95 ms
248      e=65537 1.80 ms
249   */
250   e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
251   if (!use_e)
252     mpi_set_ui (e, 41);     /* This is a reasonable secure and fast value */
253   else
254     {
255       use_e |= 1; /* make sure this is odd */
256       mpi_set_ui (e, use_e);
257     }
258
259   n = mpi_new (nbits);
260
261   p = q = NULL;
262   do
263     {
264       /* select two (very secret) primes */
265       if (p)
266         _gcry_mpi_release (p);
267       if (q)
268         _gcry_mpi_release (q);
269       if (use_e)
270         { /* Do an extra test to ensure that the given exponent is
271              suitable. */
272           p = _gcry_generate_secret_prime (nbits/2, random_level,
273                                            check_exponent, e);
274           q = _gcry_generate_secret_prime (nbits/2, random_level,
275                                            check_exponent, e);
276         }
277       else
278         { /* We check the exponent later. */
279           p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
280           q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
281         }
282       if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
283         mpi_swap(p,q);
284       /* calculate the modulus */
285       mpi_mul( n, p, q );
286     }
287   while ( mpi_get_nbits(n) != nbits );
288
289   /* calculate Euler totient: phi = (p-1)(q-1) */
290   t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
291   t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
292   phi   = mpi_snew ( nbits );
293   g     = mpi_snew ( nbits );
294   f     = mpi_snew ( nbits );
295   mpi_sub_ui( t1, p, 1 );
296   mpi_sub_ui( t2, q, 1 );
297   mpi_mul( phi, t1, t2 );
298   mpi_gcd (g, t1, t2);
299   mpi_fdiv_q(f, phi, g);
300
301   while (!mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
302     {
303       if (use_e)
304         BUG (); /* The prime generator already made sure that we
305                    never can get to here. */
306       mpi_add_ui (e, e, 2);
307     }
308
309   /* calculate the secret key d = e^1 mod phi */
310   d = mpi_snew ( nbits );
311   mpi_invm (d, e, f );
312   /* calculate the inverse of p and q (used for chinese remainder theorem)*/
313   u = mpi_snew ( nbits );
314   mpi_invm(u, p, q );
315
316   if( DBG_CIPHER )
317     {
318       log_mpidump("  p= ", p );
319       log_mpidump("  q= ", q );
320       log_mpidump("phi= ", phi );
321       log_mpidump("  g= ", g );
322       log_mpidump("  f= ", f );
323       log_mpidump("  n= ", n );
324       log_mpidump("  e= ", e );
325       log_mpidump("  d= ", d );
326       log_mpidump("  u= ", u );
327     }
328
329   _gcry_mpi_release (t1);
330   _gcry_mpi_release (t2);
331   _gcry_mpi_release (phi);
332   _gcry_mpi_release (f);
333   _gcry_mpi_release (g);
334
335   sk->n = n;
336   sk->e = e;
337   sk->p = p;
338   sk->q = q;
339   sk->d = d;
340   sk->u = u;
341
342   /* Now we can test our keys. */
343   if (test_keys (sk, nbits - 64))
344     {
345       _gcry_mpi_release (sk->n); sk->n = NULL;
346       _gcry_mpi_release (sk->e); sk->e = NULL;
347       _gcry_mpi_release (sk->p); sk->p = NULL;
348       _gcry_mpi_release (sk->q); sk->q = NULL;
349       _gcry_mpi_release (sk->d); sk->d = NULL;
350       _gcry_mpi_release (sk->u); sk->u = NULL;
351       fips_signal_error ("self-test after key generation failed");
352       return GPG_ERR_SELFTEST_FAILED;
353     }
354
355   return 0;
356 }
357
358
359 /* Helper for generate_x931.  */
360 static gcry_mpi_t
361 gen_x931_parm_xp (unsigned int nbits)
362 {
363   gcry_mpi_t xp;
364
365   xp = mpi_snew (nbits);
366   _gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
367
368   /* The requirement for Xp is:
369
370        sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
371
372      We set the two high order bits to 1 to satisfy the lower bound.
373      By using mpi_set_highbit we make sure that the upper bound is
374      satisfied as well.  */
375   mpi_set_highbit (xp, nbits-1);
376   mpi_set_bit (xp, nbits-2);
377   gcry_assert ( mpi_get_nbits (xp) == nbits );
378
379   return xp;
380 }
381
382
383 /* Helper for generate_x931.  */
384 static gcry_mpi_t
385 gen_x931_parm_xi (void)
386 {
387   gcry_mpi_t xi;
388
389   xi = mpi_snew (101);
390   _gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM);
391   mpi_set_highbit (xi, 100);
392   gcry_assert ( mpi_get_nbits (xi) == 101 );
393
394   return xi;
395 }
396
397
398
399 /* Variant of the standard key generation code using the algorithm
400    from X9.31.  Using this algorithm has the advantage that the
401    generation can be made deterministic which is required for CAVS
402    testing.  */
403 static gpg_err_code_t
404 generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
405                gcry_sexp_t deriveparms, int *swapped)
406 {
407   gcry_mpi_t p, q; /* The two primes.  */
408   gcry_mpi_t e;    /* The public exponent.  */
409   gcry_mpi_t n;    /* The public key.  */
410   gcry_mpi_t d;    /* The private key */
411   gcry_mpi_t u;    /* The inverse of p and q.  */
412   gcry_mpi_t pm1;  /* p - 1  */
413   gcry_mpi_t qm1;  /* q - 1  */
414   gcry_mpi_t phi;  /* Euler totient.  */
415   gcry_mpi_t f, g; /* Helper.  */
416
417   *swapped = 0;
418
419   if (e_value == 1)   /* Alias for a secure value. */
420     e_value = 65537;
421
422   /* Point 1 of section 4.1:  k = 1024 + 256s with S >= 0  */
423   if (nbits < 1024 || (nbits % 256))
424     return GPG_ERR_INV_VALUE;
425
426   /* Point 2:  2 <= bitlength(e) < 2^{k-2}
427      Note that we do not need to check the upper bound because we use
428      an unsigned long for E and thus there is no way for E to reach
429      that limit.  */
430   if (e_value < 3)
431     return GPG_ERR_INV_VALUE;
432
433   /* Our implementaion requires E to be odd.  */
434   if (!(e_value & 1))
435     return GPG_ERR_INV_VALUE;
436
437   /* Point 3:  e > 0 or e 0 if it is to be randomly generated.
438      We support only a fixed E and thus there is no need for an extra test.  */
439
440
441   /* Compute or extract the derive parameters.  */
442   {
443     gcry_mpi_t xp1 = NULL;
444     gcry_mpi_t xp2 = NULL;
445     gcry_mpi_t xp  = NULL;
446     gcry_mpi_t xq1 = NULL;
447     gcry_mpi_t xq2 = NULL;
448     gcry_mpi_t xq  = NULL;
449     gcry_mpi_t tmpval;
450
451     if (!deriveparms)
452       {
453         /* Not given: Generate them.  */
454         xp = gen_x931_parm_xp (nbits/2);
455         /* Make sure that |xp - xq| > 2^{nbits - 100} holds.  */
456         tmpval = mpi_snew (nbits/2);
457         do
458           {
459             _gcry_mpi_release (xq);
460             xq = gen_x931_parm_xp (nbits/2);
461             mpi_sub (tmpval, xp, xq);
462           }
463         while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
464         _gcry_mpi_release (tmpval);
465
466         xp1 = gen_x931_parm_xi ();
467         xp2 = gen_x931_parm_xi ();
468         xq1 = gen_x931_parm_xi ();
469         xq2 = gen_x931_parm_xi ();
470
471       }
472     else
473       {
474         /* Parameters to derive the key are given.  */
475         /* Note that we explicitly need to setup the values of tbl
476            because some compilers (e.g. OpenWatcom, IRIX) don't allow
477            to initialize a structure with automatic variables.  */
478         struct { const char *name; gcry_mpi_t *value; } tbl[] = {
479           { "Xp1" },
480           { "Xp2" },
481           { "Xp"  },
482           { "Xq1" },
483           { "Xq2" },
484           { "Xq"  },
485           { NULL }
486         };
487         int idx;
488         gcry_sexp_t oneparm;
489
490         tbl[0].value = &xp1;
491         tbl[1].value = &xp2;
492         tbl[2].value = &xp;
493         tbl[3].value = &xq1;
494         tbl[4].value = &xq2;
495         tbl[5].value = &xq;
496
497         for (idx=0; tbl[idx].name; idx++)
498           {
499             oneparm = sexp_find_token (deriveparms, tbl[idx].name, 0);
500             if (oneparm)
501               {
502                 *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG);
503                 sexp_release (oneparm);
504               }
505           }
506         for (idx=0; tbl[idx].name; idx++)
507           if (!*tbl[idx].value)
508             break;
509         if (tbl[idx].name)
510           {
511             /* At least one parameter is missing.  */
512             for (idx=0; tbl[idx].name; idx++)
513               _gcry_mpi_release (*tbl[idx].value);
514             return GPG_ERR_MISSING_VALUE;
515           }
516       }
517
518     e = mpi_alloc_set_ui (e_value);
519
520     /* Find two prime numbers.  */
521     p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL);
522     q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL);
523     _gcry_mpi_release (xp);  xp  = NULL;
524     _gcry_mpi_release (xp1); xp1 = NULL;
525     _gcry_mpi_release (xp2); xp2 = NULL;
526     _gcry_mpi_release (xq);  xq  = NULL;
527     _gcry_mpi_release (xq1); xq1 = NULL;
528     _gcry_mpi_release (xq2); xq2 = NULL;
529     if (!p || !q)
530       {
531         _gcry_mpi_release (p);
532         _gcry_mpi_release (q);
533         _gcry_mpi_release (e);
534         return GPG_ERR_NO_PRIME;
535       }
536   }
537
538
539   /* Compute the public modulus.  We make sure that p is smaller than
540      q to allow the use of the CRT.  */
541   if (mpi_cmp (p, q) > 0 )
542     {
543       mpi_swap (p, q);
544       *swapped = 1;
545     }
546   n = mpi_new (nbits);
547   mpi_mul (n, p, q);
548
549   /* Compute the Euler totient:  phi = (p-1)(q-1)  */
550   pm1 = mpi_snew (nbits/2);
551   qm1 = mpi_snew (nbits/2);
552   phi = mpi_snew (nbits);
553   mpi_sub_ui (pm1, p, 1);
554   mpi_sub_ui (qm1, q, 1);
555   mpi_mul (phi, pm1, qm1);
556
557   g = mpi_snew (nbits);
558   gcry_assert (mpi_gcd (g, e, phi));
559
560   /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
561   mpi_gcd (g, pm1, qm1);
562   f = pm1; pm1 = NULL;
563   _gcry_mpi_release (qm1); qm1 = NULL;
564   mpi_fdiv_q (f, phi, g);
565   _gcry_mpi_release (phi); phi = NULL;
566   d = g; g = NULL;
567   /* Compute the secret key:  d = e^{-1} mod lcm(p-1,q-1) */
568   mpi_invm (d, e, f);
569
570   /* Compute the inverse of p and q.  */
571   u = f; f = NULL;
572   mpi_invm (u, p, q );
573
574   if( DBG_CIPHER )
575     {
576       if (*swapped)
577         log_debug ("p and q are swapped\n");
578       log_mpidump("  p", p );
579       log_mpidump("  q", q );
580       log_mpidump("  n", n );
581       log_mpidump("  e", e );
582       log_mpidump("  d", d );
583       log_mpidump("  u", u );
584     }
585
586
587   sk->n = n;
588   sk->e = e;
589   sk->p = p;
590   sk->q = q;
591   sk->d = d;
592   sk->u = u;
593
594   /* Now we can test our keys. */
595   if (test_keys (sk, nbits - 64))
596     {
597       _gcry_mpi_release (sk->n); sk->n = NULL;
598       _gcry_mpi_release (sk->e); sk->e = NULL;
599       _gcry_mpi_release (sk->p); sk->p = NULL;
600       _gcry_mpi_release (sk->q); sk->q = NULL;
601       _gcry_mpi_release (sk->d); sk->d = NULL;
602       _gcry_mpi_release (sk->u); sk->u = NULL;
603       fips_signal_error ("self-test after key generation failed");
604       return GPG_ERR_SELFTEST_FAILED;
605     }
606
607   return 0;
608 }
609
610
611 /****************
612  * Test whether the secret key is valid.
613  * Returns: true if this is a valid key.
614  */
615 static int
616 check_secret_key( RSA_secret_key *sk )
617 {
618   int rc;
619   gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
620
621   mpi_mul(temp, sk->p, sk->q );
622   rc = mpi_cmp( temp, sk->n );
623   mpi_free(temp);
624   return !rc;
625 }
626
627
628
629 /****************
630  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
631  *
632  *      c = m^e mod n
633  *
634  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
635  */
636 static void
637 public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
638 {
639   if( output == input )  /* powm doesn't like output and input the same */
640     {
641       gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
642       mpi_powm( x, input, pkey->e, pkey->n );
643       mpi_set(output, x);
644       mpi_free(x);
645     }
646   else
647     mpi_powm( output, input, pkey->e, pkey->n );
648 }
649
650 #if 0
651 static void
652 stronger_key_check ( RSA_secret_key *skey )
653 {
654   gcry_mpi_t t = mpi_alloc_secure ( 0 );
655   gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
656   gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
657   gcry_mpi_t phi = mpi_alloc_secure ( 0 );
658
659   /* check that n == p * q */
660   mpi_mul( t, skey->p, skey->q);
661   if (mpi_cmp( t, skey->n) )
662     log_info ( "RSA Oops: n != p * q\n" );
663
664   /* check that p is less than q */
665   if( mpi_cmp( skey->p, skey->q ) > 0 )
666     {
667       log_info ("RSA Oops: p >= q - fixed\n");
668       _gcry_mpi_swap ( skey->p, skey->q);
669     }
670
671     /* check that e divides neither p-1 nor q-1 */
672     mpi_sub_ui(t, skey->p, 1 );
673     mpi_fdiv_r(t, t, skey->e );
674     if ( !mpi_cmp_ui( t, 0) )
675         log_info ( "RSA Oops: e divides p-1\n" );
676     mpi_sub_ui(t, skey->q, 1 );
677     mpi_fdiv_r(t, t, skey->e );
678     if ( !mpi_cmp_ui( t, 0) )
679         log_info ( "RSA Oops: e divides q-1\n" );
680
681     /* check that d is correct */
682     mpi_sub_ui( t1, skey->p, 1 );
683     mpi_sub_ui( t2, skey->q, 1 );
684     mpi_mul( phi, t1, t2 );
685     gcry_mpi_gcd(t, t1, t2);
686     mpi_fdiv_q(t, phi, t);
687     mpi_invm(t, skey->e, t );
688     if ( mpi_cmp(t, skey->d ) )
689       {
690         log_info ( "RSA Oops: d is wrong - fixed\n");
691         mpi_set (skey->d, t);
692         log_printmpi ("  fixed d", skey->d);
693       }
694
695     /* check for correctness of u */
696     mpi_invm(t, skey->p, skey->q );
697     if ( mpi_cmp(t, skey->u ) )
698       {
699         log_info ( "RSA Oops: u is wrong - fixed\n");
700         mpi_set (skey->u, t);
701         log_printmpi ("  fixed u", skey->u);
702       }
703
704     log_info ( "RSA secret key check finished\n");
705
706     mpi_free (t);
707     mpi_free (t1);
708     mpi_free (t2);
709     mpi_free (phi);
710 }
711 #endif
712
713
714
715 /****************
716  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
717  *
718  *      m = c^d mod n
719  *
720  * Or faster:
721  *
722  *      m1 = c ^ (d mod (p-1)) mod p
723  *      m2 = c ^ (d mod (q-1)) mod q
724  *      h = u * (m2 - m1) mod q
725  *      m = m1 + h * p
726  *
727  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
728  */
729 static void
730 secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
731 {
732   /* Remove superfluous leading zeroes from INPUT.  */
733   mpi_normalize (input);
734
735   if (!skey->p || !skey->q || !skey->u)
736     {
737       mpi_powm (output, input, skey->d, skey->n);
738     }
739   else
740     {
741       gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
742       gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
743       gcry_mpi_t h  = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
744
745       /* m1 = c ^ (d mod (p-1)) mod p */
746       mpi_sub_ui( h, skey->p, 1  );
747       mpi_fdiv_r( h, skey->d, h );
748       mpi_powm( m1, input, h, skey->p );
749       /* m2 = c ^ (d mod (q-1)) mod q */
750       mpi_sub_ui( h, skey->q, 1  );
751       mpi_fdiv_r( h, skey->d, h );
752       mpi_powm( m2, input, h, skey->q );
753       /* h = u * ( m2 - m1 ) mod q */
754       mpi_sub( h, m2, m1 );
755       if ( mpi_has_sign ( h ) )
756         mpi_add ( h, h, skey->q );
757       mpi_mulm( h, skey->u, h, skey->q );
758       /* m = m1 + h * p */
759       mpi_mul ( h, h, skey->p );
760       mpi_add ( output, m1, h );
761
762       mpi_free ( h );
763       mpi_free ( m1 );
764       mpi_free ( m2 );
765     }
766 }
767
768
769
770 /*********************************************
771  **************  interface  ******************
772  *********************************************/
773
774 static gcry_err_code_t
775 rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
776 {
777   gpg_err_code_t ec;
778   unsigned int nbits;
779   unsigned long evalue;
780   RSA_secret_key sk;
781   gcry_sexp_t deriveparms;
782   int flags = 0;
783   gcry_sexp_t l1;
784   gcry_sexp_t swap_info = NULL;
785
786   memset (&sk, 0, sizeof sk);
787
788   ec = _gcry_pk_util_get_nbits (genparms, &nbits);
789   if (ec)
790     return ec;
791
792   ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue);
793   if (ec)
794     return ec;
795
796   /* Parse the optional flags list.  */
797   l1 = sexp_find_token (genparms, "flags", 0);
798   if (l1)
799     {
800       ec = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
801       sexp_release (l1);
802       if (ec)
803         return ec;
804     }
805
806   deriveparms = (genparms?
807                  sexp_find_token (genparms, "derive-parms", 0) : NULL);
808   if (!deriveparms)
809     {
810       /* Parse the optional "use-x931" flag. */
811       l1 = sexp_find_token (genparms, "use-x931", 0);
812       if (l1)
813         {
814           flags |= PUBKEY_FLAG_USE_X931;
815           sexp_release (l1);
816         }
817     }
818
819   if (deriveparms || (flags & PUBKEY_FLAG_USE_X931) || fips_mode ())
820     {
821       int swapped;
822       ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
823       sexp_release (deriveparms);
824       if (!ec && swapped)
825         ec = sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1);
826     }
827   else
828     {
829       /* Parse the optional "transient-key" flag. */
830       if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
831         {
832           l1 = sexp_find_token (genparms, "transient-key", 0);
833           if (l1)
834             {
835               flags |= PUBKEY_FLAG_TRANSIENT_KEY;
836               sexp_release (l1);
837             }
838         }
839       /* Generate.  */
840       ec = generate_std (&sk, nbits, evalue,
841                          !!(flags & PUBKEY_FLAG_TRANSIENT_KEY));
842     }
843
844   if (!ec)
845     {
846       ec = sexp_build (r_skey, NULL,
847                        "(key-data"
848                        " (public-key"
849                        "  (rsa(n%m)(e%m)))"
850                        " (private-key"
851                        "  (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))"
852                        " %S)",
853                        sk.n, sk.e,
854                        sk.n, sk.e, sk.d, sk.p, sk.q, sk.u,
855                        swap_info);
856     }
857
858   mpi_free (sk.n);
859   mpi_free (sk.e);
860   mpi_free (sk.p);
861   mpi_free (sk.q);
862   mpi_free (sk.d);
863   mpi_free (sk.u);
864   sexp_release (swap_info);
865
866   return ec;
867 }
868
869
870 static gcry_err_code_t
871 rsa_check_secret_key (gcry_sexp_t keyparms)
872 {
873   gcry_err_code_t rc;
874   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
875
876   /* To check the key we need the optional parameters. */
877   rc = sexp_extract_param (keyparms, NULL, "nedpqu",
878                            &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
879                            NULL);
880   if (rc)
881     goto leave;
882
883   if (!check_secret_key (&sk))
884     rc = GPG_ERR_BAD_SECKEY;
885
886  leave:
887   _gcry_mpi_release (sk.n);
888   _gcry_mpi_release (sk.e);
889   _gcry_mpi_release (sk.d);
890   _gcry_mpi_release (sk.p);
891   _gcry_mpi_release (sk.q);
892   _gcry_mpi_release (sk.u);
893   if (DBG_CIPHER)
894     log_debug ("rsa_testkey    => %s\n", gpg_strerror (rc));
895   return rc;
896 }
897
898
899 static gcry_err_code_t
900 rsa_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
901 {
902   gcry_err_code_t rc;
903   struct pk_encoding_ctx ctx;
904   gcry_mpi_t data = NULL;
905   RSA_public_key pk = {NULL, NULL};
906   gcry_mpi_t ciph = NULL;
907
908   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
909                                    rsa_get_nbits (keyparms));
910
911   /* Extract the data.  */
912   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
913   if (rc)
914     goto leave;
915   if (DBG_CIPHER)
916     log_mpidump ("rsa_encrypt data", data);
917   if (mpi_is_opaque (data))
918     {
919       rc = GPG_ERR_INV_DATA;
920       goto leave;
921     }
922
923   /* Extract the key.  */
924   rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
925   if (rc)
926     goto leave;
927   if (DBG_CIPHER)
928     {
929       log_mpidump ("rsa_encrypt    n", pk.n);
930       log_mpidump ("rsa_encrypt    e", pk.e);
931     }
932
933   /* Do RSA computation and build result.  */
934   ciph = mpi_new (0);
935   public (ciph, data, &pk);
936   if (DBG_CIPHER)
937     log_mpidump ("rsa_encrypt  res", ciph);
938   if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
939     {
940       /* We need to make sure to return the correct length to avoid
941          problems with missing leading zeroes.  */
942       unsigned char *em;
943       size_t emlen = (mpi_get_nbits (pk.n)+7)/8;
944
945       rc = _gcry_mpi_to_octet_string (&em, NULL, ciph, emlen);
946       if (!rc)
947         {
948           rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%b)))", (int)emlen, em);
949           xfree (em);
950         }
951     }
952   else
953     rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%m)))", ciph);
954
955  leave:
956   _gcry_mpi_release (ciph);
957   _gcry_mpi_release (pk.n);
958   _gcry_mpi_release (pk.e);
959   _gcry_mpi_release (data);
960   _gcry_pk_util_free_encoding_ctx (&ctx);
961   if (DBG_CIPHER)
962     log_debug ("rsa_encrypt    => %s\n", gpg_strerror (rc));
963   return rc;
964 }
965
966
967 static gcry_err_code_t
968 rsa_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
969
970 {
971   gpg_err_code_t rc;
972   struct pk_encoding_ctx ctx;
973   gcry_sexp_t l1 = NULL;
974   gcry_mpi_t data = NULL;
975   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
976   gcry_mpi_t plain = NULL;
977   gcry_mpi_t r = NULL;     /* Random number needed for blinding.  */
978   gcry_mpi_t ri = NULL;    /* Modular multiplicative inverse of r.  */
979   gcry_mpi_t bldata = NULL;/* Blinded data to decrypt.  */
980   unsigned char *unpad = NULL;
981   size_t unpadlen = 0;
982
983   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
984                                    rsa_get_nbits (keyparms));
985
986   /* Extract the data.  */
987   rc = _gcry_pk_util_preparse_encval (s_data, rsa_names, &l1, &ctx);
988   if (rc)
989     goto leave;
990   rc = sexp_extract_param (l1, NULL, "a", &data, NULL);
991   if (rc)
992     goto leave;
993   if (DBG_CIPHER)
994     log_printmpi ("rsa_decrypt data", data);
995   if (mpi_is_opaque (data))
996     {
997       rc = GPG_ERR_INV_DATA;
998       goto leave;
999     }
1000
1001   /* Extract the key.  */
1002   rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?",
1003                            &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1004                            NULL);
1005   if (rc)
1006     goto leave;
1007   if (DBG_CIPHER)
1008     {
1009       log_printmpi ("rsa_decrypt    n", sk.n);
1010       log_printmpi ("rsa_decrypt    e", sk.e);
1011       if (!fips_mode ())
1012         {
1013           log_printmpi ("rsa_decrypt    d", sk.d);
1014           log_printmpi ("rsa_decrypt    p", sk.p);
1015           log_printmpi ("rsa_decrypt    q", sk.q);
1016           log_printmpi ("rsa_decrypt    u", sk.u);
1017         }
1018     }
1019
1020   /* Better make sure that there are no superfluous leading zeroes in
1021      the input and it has not been "padded" using multiples of N.
1022      This mitigates side-channel attacks (CVE-2013-4576).  */
1023   mpi_normalize (data);
1024   mpi_fdiv_r (data, data, sk.n);
1025
1026   /* Allocate MPI for the plaintext.  */
1027   plain = mpi_snew (ctx.nbits);
1028
1029   /* We use blinding by default to mitigate timing attacks which can
1030      be practically mounted over the network as shown by Brumley and
1031      Boney in 2003.  */
1032   if (!(ctx.flags & PUBKEY_FLAG_NO_BLINDING))
1033     {
1034       /* First, we need a random number r between 0 and n - 1, which
1035          is relatively prime to n (i.e. it is neither p nor q).  The
1036          random number needs to be only unpredictable, thus we employ
1037          the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
1038          gcry_mpi_randomize.  */
1039       r  = mpi_snew (ctx.nbits);
1040       ri = mpi_snew (ctx.nbits);
1041       bldata = mpi_snew (ctx.nbits);
1042
1043       do
1044         {
1045           _gcry_mpi_randomize (r, ctx.nbits, GCRY_WEAK_RANDOM);
1046           mpi_mod (r, r, sk.n);
1047         }
1048       while (!mpi_invm (ri, r, sk.n));
1049
1050       /* Do blinding.  We calculate: y = (x * r^e) mod n, where r is
1051          the random number, e is the public exponent, x is the
1052          non-blinded data and n is the RSA modulus.  */
1053       mpi_powm (bldata, r, sk.e, sk.n);
1054       mpi_mulm (bldata, bldata, data, sk.n);
1055
1056       /* Perform decryption.  */
1057       secret (plain, bldata, &sk);
1058       _gcry_mpi_release (bldata); bldata = NULL;
1059
1060       /* Undo blinding.  Here we calculate: y = (x * r^-1) mod n,
1061          where x is the blinded decrypted data, ri is the modular
1062          multiplicative inverse of r and n is the RSA modulus.  */
1063       mpi_mulm (plain, plain, ri, sk.n);
1064
1065       _gcry_mpi_release (r); r = NULL;
1066       _gcry_mpi_release (ri); ri = NULL;
1067     }
1068   else
1069     secret (plain, data, &sk);
1070
1071   if (DBG_CIPHER)
1072     log_printmpi ("rsa_decrypt  res", plain);
1073
1074   /* Reverse the encoding and build the s-expression.  */
1075   switch (ctx.encoding)
1076     {
1077     case PUBKEY_ENC_PKCS1:
1078       rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
1079       mpi_free (plain);
1080       plain = NULL;
1081       if (!rc)
1082         rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
1083       break;
1084
1085     case PUBKEY_ENC_OAEP:
1086       rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
1087                                   ctx.nbits, ctx.hash_algo,
1088                                   plain, ctx.label, ctx.labellen);
1089       mpi_free (plain);
1090       plain = NULL;
1091       if (!rc)
1092         rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
1093       break;
1094
1095     default:
1096       /* Raw format.  For backward compatibility we need to assume a
1097          signed mpi by using the sexp format string "%m".  */
1098       rc = sexp_build (r_plain, NULL,
1099                        (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
1100                        ? "%m":"(value %m)", plain);
1101       break;
1102     }
1103
1104  leave:
1105   xfree (unpad);
1106   _gcry_mpi_release (plain);
1107   _gcry_mpi_release (sk.n);
1108   _gcry_mpi_release (sk.e);
1109   _gcry_mpi_release (sk.d);
1110   _gcry_mpi_release (sk.p);
1111   _gcry_mpi_release (sk.q);
1112   _gcry_mpi_release (sk.u);
1113   _gcry_mpi_release (data);
1114   _gcry_mpi_release (r);
1115   _gcry_mpi_release (ri);
1116   _gcry_mpi_release (bldata);
1117   sexp_release (l1);
1118   _gcry_pk_util_free_encoding_ctx (&ctx);
1119   if (DBG_CIPHER)
1120     log_debug ("rsa_decrypt    => %s\n", gpg_strerror (rc));
1121   return rc;
1122 }
1123
1124
1125 static gcry_err_code_t
1126 rsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1127 {
1128   gpg_err_code_t rc;
1129   struct pk_encoding_ctx ctx;
1130   gcry_mpi_t data = NULL;
1131   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
1132   RSA_public_key pk;
1133   gcry_mpi_t sig = NULL;
1134   gcry_mpi_t result = NULL;
1135
1136   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
1137                                    rsa_get_nbits (keyparms));
1138
1139   /* Extract the data.  */
1140   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1141   if (rc)
1142     goto leave;
1143   if (DBG_CIPHER)
1144     log_printmpi ("rsa_sign   data", data);
1145   if (mpi_is_opaque (data))
1146     {
1147       rc = GPG_ERR_INV_DATA;
1148       goto leave;
1149     }
1150
1151   /* Extract the key.  */
1152   rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?",
1153                            &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1154                            NULL);
1155   if (rc)
1156     goto leave;
1157   if (DBG_CIPHER)
1158     {
1159       log_printmpi ("rsa_sign      n", sk.n);
1160       log_printmpi ("rsa_sign      e", sk.e);
1161       if (!fips_mode ())
1162         {
1163           log_printmpi ("rsa_sign      d", sk.d);
1164           log_printmpi ("rsa_sign      p", sk.p);
1165           log_printmpi ("rsa_sign      q", sk.q);
1166           log_printmpi ("rsa_sign      u", sk.u);
1167         }
1168     }
1169
1170   /* Do RSA computation.  */
1171   sig = mpi_new (0);
1172   secret (sig, data, &sk);
1173   if (DBG_CIPHER)
1174     log_printmpi ("rsa_sign    res", sig);
1175
1176   /* Check that the created signature is good.  This detects a failure
1177      of the CRT algorithm  (Lenstra's attack on RSA's use of the CRT).  */
1178   result = mpi_new (0);
1179   pk.n = sk.n;
1180   pk.e = sk.e;
1181   public (result, sig, &pk);
1182   if (mpi_cmp (result, data))
1183     {
1184       rc = GPG_ERR_BAD_SIGNATURE;
1185       goto leave;
1186     }
1187
1188   /* Convert the result.  */
1189   if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
1190     {
1191       /* We need to make sure to return the correct length to avoid
1192          problems with missing leading zeroes.  */
1193       unsigned char *em;
1194       size_t emlen = (mpi_get_nbits (sk.n)+7)/8;
1195
1196       rc = _gcry_mpi_to_octet_string (&em, NULL, sig, emlen);
1197       if (!rc)
1198         {
1199           rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%b)))", (int)emlen, em);
1200           xfree (em);
1201         }
1202     }
1203   else
1204     rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%M)))", sig);
1205
1206
1207  leave:
1208   _gcry_mpi_release (result);
1209   _gcry_mpi_release (sig);
1210   _gcry_mpi_release (sk.n);
1211   _gcry_mpi_release (sk.e);
1212   _gcry_mpi_release (sk.d);
1213   _gcry_mpi_release (sk.p);
1214   _gcry_mpi_release (sk.q);
1215   _gcry_mpi_release (sk.u);
1216   _gcry_mpi_release (data);
1217   _gcry_pk_util_free_encoding_ctx (&ctx);
1218   if (DBG_CIPHER)
1219     log_debug ("rsa_sign      => %s\n", gpg_strerror (rc));
1220   return rc;
1221 }
1222
1223
1224 static gcry_err_code_t
1225 rsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1226 {
1227   gcry_err_code_t rc;
1228   struct pk_encoding_ctx ctx;
1229   gcry_sexp_t l1 = NULL;
1230   gcry_mpi_t sig = NULL;
1231   gcry_mpi_t data = NULL;
1232   RSA_public_key pk = { NULL, NULL };
1233   gcry_mpi_t result = NULL;
1234
1235   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1236                                    rsa_get_nbits (keyparms));
1237
1238   /* Extract the data.  */
1239   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1240   if (rc)
1241     goto leave;
1242   if (DBG_CIPHER)
1243     log_printmpi ("rsa_verify data", data);
1244   if (mpi_is_opaque (data))
1245     {
1246       rc = GPG_ERR_INV_DATA;
1247       goto leave;
1248     }
1249
1250   /* Extract the signature value.  */
1251   rc = _gcry_pk_util_preparse_sigval (s_sig, rsa_names, &l1, NULL);
1252   if (rc)
1253     goto leave;
1254   rc = sexp_extract_param (l1, NULL, "s", &sig, NULL);
1255   if (rc)
1256     goto leave;
1257   if (DBG_CIPHER)
1258     log_printmpi ("rsa_verify  sig", sig);
1259
1260   /* Extract the key.  */
1261   rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
1262   if (rc)
1263     goto leave;
1264   if (DBG_CIPHER)
1265     {
1266       log_printmpi ("rsa_verify    n", pk.n);
1267       log_printmpi ("rsa_verify    e", pk.e);
1268     }
1269
1270   /* Do RSA computation and compare.  */
1271   result = mpi_new (0);
1272   public (result, sig, &pk);
1273   if (DBG_CIPHER)
1274     log_printmpi ("rsa_verify  cmp", result);
1275   if (ctx.verify_cmp)
1276     rc = ctx.verify_cmp (&ctx, result);
1277   else
1278     rc = mpi_cmp (result, data) ? GPG_ERR_BAD_SIGNATURE : 0;
1279
1280  leave:
1281   _gcry_mpi_release (result);
1282   _gcry_mpi_release (pk.n);
1283   _gcry_mpi_release (pk.e);
1284   _gcry_mpi_release (data);
1285   _gcry_mpi_release (sig);
1286   sexp_release (l1);
1287   _gcry_pk_util_free_encoding_ctx (&ctx);
1288   if (DBG_CIPHER)
1289     log_debug ("rsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1290   return rc;
1291 }
1292
1293
1294
1295 /* Return the number of bits for the key described by PARMS.  On error
1296  * 0 is returned.  The format of PARMS starts with the algorithm name;
1297  * for example:
1298  *
1299  *   (rsa
1300  *     (n <mpi>)
1301  *     (e <mpi>))
1302  *
1303  * More parameters may be given but we only need N here.
1304  */
1305 static unsigned int
1306 rsa_get_nbits (gcry_sexp_t parms)
1307 {
1308   gcry_sexp_t l1;
1309   gcry_mpi_t n;
1310   unsigned int nbits;
1311
1312   l1 = sexp_find_token (parms, "n", 1);
1313   if (!l1)
1314     return 0; /* Parameter N not found.  */
1315
1316   n = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1317   sexp_release (l1);
1318   nbits = n? mpi_get_nbits (n) : 0;
1319   _gcry_mpi_release (n);
1320   return nbits;
1321 }
1322
1323
1324 /* Compute a keygrip.  MD is the hash context which we are going to
1325    update.  KEYPARAM is an S-expression with the key parameters, this
1326    is usually a public key but may also be a secret key.  An example
1327    of such an S-expression is:
1328
1329       (rsa
1330         (n #00B...#)
1331         (e #010001#))
1332
1333    PKCS-15 says that for RSA only the modulus should be hashed -
1334    however, it is not clear whether this is meant to use the raw bytes
1335    (assuming this is an unsigned integer) or whether the DER required
1336    0 should be prefixed.  We hash the raw bytes.  */
1337 static gpg_err_code_t
1338 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1339 {
1340   gcry_sexp_t l1;
1341   const char *data;
1342   size_t datalen;
1343
1344   l1 = sexp_find_token (keyparam, "n", 1);
1345   if (!l1)
1346     return GPG_ERR_NO_OBJ;
1347
1348   data = sexp_nth_data (l1, 1, &datalen);
1349   if (!data)
1350     {
1351       sexp_release (l1);
1352       return GPG_ERR_NO_OBJ;
1353     }
1354
1355   _gcry_md_write (md, data, datalen);
1356   sexp_release (l1);
1357
1358   return 0;
1359 }
1360
1361
1362
1363 \f
1364 /*
1365      Self-test section.
1366  */
1367
1368 static const char *
1369 selftest_sign_2048 (gcry_sexp_t pkey, gcry_sexp_t skey)
1370 {
1371   static const char sample_data[] =
1372     "(data (flags pkcs1)"
1373     " (hash sha256 #11223344556677889900aabbccddeeff"
1374     /**/           "102030405060708090a0b0c0d0f01121#))";
1375   static const char sample_data_bad[] =
1376     "(data (flags pkcs1)"
1377     " (hash sha256 #11223344556677889900aabbccddeeff"
1378     /**/           "802030405060708090a0b0c0d0f01121#))";
1379
1380   const char *errtxt = NULL;
1381   gcry_error_t err;
1382   gcry_sexp_t data = NULL;
1383   gcry_sexp_t data_bad = NULL;
1384   gcry_sexp_t sig = NULL;
1385   /* raw signature data reference */
1386   const char ref_data[] =
1387     "6252a19a11e1d5155ed9376036277193d644fa239397fff03e9b92d6f86415d6"
1388     "d30da9273775f290e580d038295ff8ff89522becccfa6ae870bf76b76df402a8"
1389     "54f69347e3db3de8e1e7d4dada281ec556810c7a8ecd0b5f51f9b1c0e7aa7557"
1390     "61aa2b8ba5f811304acc6af0eca41fe49baf33bf34eddaf44e21e036ac7f0b68"
1391     "03cdef1c60021fb7b5b97ebacdd88ab755ce29af568dbc5728cc6e6eff42618d"
1392     "62a0386ca8beed46402bdeeef29b6a3feded906bace411a06a39192bf516ae10"
1393     "67e4320fa8ea113968525f4574d022a3ceeaafdc41079efe1f22cc94bf59d8d3"
1394     "328085da9674857db56de5978a62394aab48aa3b72e23a1b16260cfd9daafe65";
1395   gcry_mpi_t ref_mpi = NULL;
1396   gcry_mpi_t sig_mpi = NULL;
1397
1398   err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data));
1399   if (!err)
1400     err = sexp_sscan (&data_bad, NULL,
1401                       sample_data_bad, strlen (sample_data_bad));
1402   if (err)
1403     {
1404       errtxt = "converting data failed";
1405       goto leave;
1406     }
1407
1408   err = _gcry_pk_sign (&sig, data, skey);
1409   if (err)
1410     {
1411       errtxt = "signing failed";
1412       goto leave;
1413     }
1414
1415   err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL);
1416   if (err)
1417     {
1418       errtxt = "converting ref_data to mpi failed";
1419       goto leave;
1420     }
1421
1422   err = _gcry_sexp_extract_param(sig, "sig-val!rsa", "s", &sig_mpi, NULL);
1423   if (err)
1424     {
1425       errtxt = "extracting signature data failed";
1426       goto leave;
1427     }
1428
1429   if (mpi_cmp (sig_mpi, ref_mpi))
1430     {
1431       errtxt = "signature does not match reference data";
1432       goto leave;
1433     }
1434
1435   err = _gcry_pk_verify (sig, data, pkey);
1436   if (err)
1437     {
1438       errtxt = "verify failed";
1439       goto leave;
1440     }
1441   err = _gcry_pk_verify (sig, data_bad, pkey);
1442   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1443     {
1444       errtxt = "bad signature not detected";
1445       goto leave;
1446     }
1447
1448
1449  leave:
1450   sexp_release (sig);
1451   sexp_release (data_bad);
1452   sexp_release (data);
1453   _gcry_mpi_release (ref_mpi);
1454   _gcry_mpi_release (sig_mpi);
1455   return errtxt;
1456 }
1457
1458
1459
1460 /* Given an S-expression ENCR_DATA of the form:
1461
1462    (enc-val
1463     (rsa
1464      (a a-value)))
1465
1466    as returned by gcry_pk_decrypt, return the the A-VALUE.  On error,
1467    return NULL.  */
1468 static gcry_mpi_t
1469 extract_a_from_sexp (gcry_sexp_t encr_data)
1470 {
1471   gcry_sexp_t l1, l2, l3;
1472   gcry_mpi_t a_value;
1473
1474   l1 = sexp_find_token (encr_data, "enc-val", 0);
1475   if (!l1)
1476     return NULL;
1477   l2 = sexp_find_token (l1, "rsa", 0);
1478   sexp_release (l1);
1479   if (!l2)
1480     return NULL;
1481   l3 = sexp_find_token (l2, "a", 0);
1482   sexp_release (l2);
1483   if (!l3)
1484     return NULL;
1485   a_value = sexp_nth_mpi (l3, 1, 0);
1486   sexp_release (l3);
1487
1488   return a_value;
1489 }
1490
1491
1492 static const char *
1493 selftest_encr_2048 (gcry_sexp_t pkey, gcry_sexp_t skey)
1494 {
1495   const char *errtxt = NULL;
1496   gcry_error_t err;
1497   static const char plaintext[] =
1498     "Jim quickly realized that the beautiful gowns are expensive.";
1499   gcry_sexp_t plain = NULL;
1500   gcry_sexp_t encr  = NULL;
1501   gcry_mpi_t  ciphertext = NULL;
1502   gcry_sexp_t decr  = NULL;
1503   char *decr_plaintext = NULL;
1504   gcry_sexp_t tmplist = NULL;
1505   /* expected result of encrypting the plaintext with sample_secret_key */
1506   static const char ref_data[] =
1507     "18022e2593a402a737caaa93b4c7e750e20ca265452980e1d6b7710fbd3e"
1508     "7dce72be5c2110fb47691cb38f42170ee3b4a37f2498d4a51567d762585e"
1509     "4cb81d04fbc7df4144f8e5eac2d4b8688521b64011f11d7ad53f4c874004"
1510     "819856f2e2a6f83d1c9c4e73ac26089789c14482b0b8d44139133c88c4a5"
1511     "2dba9dd6d6ffc622666b7d129168333d999706af30a2d7d272db7734e5ed"
1512     "fb8c64ea3018af3ad20f4a013a5060cb0f5e72753967bebe294280a6ed0d"
1513     "dbd3c4f11d0a8696e9d32a0dc03deb0b5e49b2cbd1503392642d4e1211f3"
1514     "e8e2ee38abaa3671ccd57fcde8ca76e85fd2cb77c35706a970a213a27352"
1515     "cec92a9604d543ddb5fc478ff50e0622";
1516   gcry_mpi_t ref_mpi = NULL;
1517
1518   /* Put the plaintext into an S-expression.  */
1519   err = sexp_build (&plain, NULL, "(data (flags raw) (value %s))", plaintext);
1520   if (err)
1521     {
1522       errtxt = "converting data failed";
1523       goto leave;
1524     }
1525
1526   /* Encrypt.  */
1527   err = _gcry_pk_encrypt (&encr, plain, pkey);
1528   if (err)
1529     {
1530       errtxt = "encrypt failed";
1531       goto leave;
1532     }
1533
1534   err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL);
1535   if (err)
1536     {
1537       errtxt = "converting encrydata to mpi failed";
1538       goto leave;
1539     }
1540
1541   /* Extraxt the ciphertext from the returned S-expression.  */
1542   /*sexp_dump (encr);*/
1543   ciphertext = extract_a_from_sexp (encr);
1544   if (!ciphertext)
1545     {
1546       errtxt = "gcry_pk_decrypt returned garbage";
1547       goto leave;
1548     }
1549
1550   /* Check that the ciphertext does no match the plaintext.  */
1551   /* _gcry_log_printmpi ("plaintext", plaintext); */
1552   /* _gcry_log_printmpi ("ciphertxt", ciphertext); */
1553   if (mpi_cmp (ref_mpi, ciphertext))
1554     {
1555       errtxt = "ciphertext doesn't match reference data";
1556       goto leave;
1557     }
1558
1559   /* Decrypt.  */
1560   err = _gcry_pk_decrypt (&decr, encr, skey);
1561   if (err)
1562     {
1563       errtxt = "decrypt failed";
1564       goto leave;
1565     }
1566
1567   /* Extract the decrypted data from the S-expression.  Note that the
1568      output of gcry_pk_decrypt depends on whether a flags lists occurs
1569      in its input data.  Because we passed the output of
1570      gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
1571      won't be there as of today.  To be prepared for future changes we
1572      take care of it anyway.  */
1573   tmplist = sexp_find_token (decr, "value", 0);
1574   if (tmplist)
1575     decr_plaintext = sexp_nth_string (tmplist, 1);
1576   else
1577     decr_plaintext = sexp_nth_string (decr, 0);
1578   if (!decr_plaintext)
1579     {
1580       errtxt = "decrypt returned no plaintext";
1581       goto leave;
1582     }
1583
1584   /* Check that the decrypted plaintext matches the original  plaintext.  */
1585   if (strcmp (plaintext, decr_plaintext))
1586     {
1587       errtxt = "mismatch";
1588       goto leave;
1589     }
1590
1591  leave:
1592   sexp_release (tmplist);
1593   xfree (decr_plaintext);
1594   sexp_release (decr);
1595   _gcry_mpi_release (ciphertext);
1596   _gcry_mpi_release (ref_mpi);
1597   sexp_release (encr);
1598   sexp_release (plain);
1599   return errtxt;
1600 }
1601
1602
1603 static gpg_err_code_t
1604 selftests_rsa (selftest_report_func_t report)
1605 {
1606   const char *what;
1607   const char *errtxt;
1608   gcry_error_t err;
1609   gcry_sexp_t skey = NULL;
1610   gcry_sexp_t pkey = NULL;
1611
1612   /* Convert the S-expressions into the internal representation.  */
1613   what = "convert";
1614   err = sexp_sscan (&skey, NULL, sample_secret_key, strlen (sample_secret_key));
1615   if (!err)
1616     err = sexp_sscan (&pkey, NULL,
1617                       sample_public_key, strlen (sample_public_key));
1618   if (err)
1619     {
1620       errtxt = _gcry_strerror (err);
1621       goto failed;
1622     }
1623
1624   what = "key consistency";
1625   err = _gcry_pk_testkey (skey);
1626   if (err)
1627     {
1628       errtxt = _gcry_strerror (err);
1629       goto failed;
1630     }
1631
1632   what = "sign";
1633   errtxt = selftest_sign_2048 (pkey, skey);
1634   if (errtxt)
1635     goto failed;
1636
1637   what = "encrypt";
1638   errtxt = selftest_encr_2048 (pkey, skey);
1639   if (errtxt)
1640     goto failed;
1641
1642   sexp_release (pkey);
1643   sexp_release (skey);
1644   return 0; /* Succeeded. */
1645
1646  failed:
1647   sexp_release (pkey);
1648   sexp_release (skey);
1649   if (report)
1650     report ("pubkey", GCRY_PK_RSA, what, errtxt);
1651   return GPG_ERR_SELFTEST_FAILED;
1652 }
1653
1654
1655 /* Run a full self-test for ALGO and return 0 on success.  */
1656 static gpg_err_code_t
1657 run_selftests (int algo, int extended, selftest_report_func_t report)
1658 {
1659   gpg_err_code_t ec;
1660
1661   (void)extended;
1662
1663   switch (algo)
1664     {
1665     case GCRY_PK_RSA:
1666       ec = selftests_rsa (report);
1667       break;
1668     default:
1669       ec = GPG_ERR_PUBKEY_ALGO;
1670       break;
1671
1672     }
1673   return ec;
1674 }
1675
1676
1677
1678 \f
1679 gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1680   {
1681     GCRY_PK_RSA, { 0, 1 },
1682     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1683     "RSA", rsa_names,
1684     "ne", "nedpqu", "a", "s", "n",
1685     rsa_generate,
1686     rsa_check_secret_key,
1687     rsa_encrypt,
1688     rsa_decrypt,
1689     rsa_sign,
1690     rsa_verify,
1691     rsa_get_nbits,
1692     run_selftests,
1693     compute_keygrip
1694   };