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