fed52a1fc3cefb00a7f682cce581f7d7cdbd7368
[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 = gcry_mpi_new (nbits);
111   gcry_mpi_t ciphertext = gcry_mpi_new (nbits);
112   gcry_mpi_t decr_plaintext = gcry_mpi_new (nbits);
113   gcry_mpi_t signature = gcry_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 (!gcry_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 (gcry_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 (gcry_mpi_cmp (decr_plaintext, plaintext))
145     goto leave; /* Signature does not match.  */
146
147   /* Modify the signature and check that the signing fails.  */
148   gcry_mpi_add_ui (signature, signature, 1);
149   public (decr_plaintext, signature, &pk);
150   if (!gcry_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 = !gcry_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 = gcry_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 = gcry_mpi_snew ( nbits );
276   g     = gcry_mpi_snew ( nbits );
277   f     = gcry_mpi_snew ( nbits );
278   mpi_sub_ui( t1, p, 1 );
279   mpi_sub_ui( t2, q, 1 );
280   mpi_mul( phi, t1, t2 );
281   gcry_mpi_gcd(g, t1, t2);
282   mpi_fdiv_q(f, phi, g);
283
284   while (!gcry_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 = gcry_mpi_snew ( nbits );
294   mpi_invm(d, e, f );
295   /* calculate the inverse of p and q (used for chinese remainder theorem)*/
296   u = gcry_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 = gcry_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 = gcry_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 = gcry_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 = gcry_sexp_find_token (deriveparms, tbl[idx].name, 0);
483             if (oneparm)
484               {
485                 *tbl[idx].value = gcry_sexp_nth_mpi (oneparm, 1,
486                                                      GCRYMPI_FMT_USG);
487                 gcry_sexp_release (oneparm);
488               }
489           }
490         for (idx=0; tbl[idx].name; idx++)
491           if (!*tbl[idx].value)
492             break;
493         if (tbl[idx].name)
494           {
495             /* At least one parameter is missing.  */
496             for (idx=0; tbl[idx].name; idx++)
497               gcry_mpi_release (*tbl[idx].value);
498             return GPG_ERR_MISSING_VALUE;
499           }
500       }
501
502     e = mpi_alloc_set_ui (e_value);
503
504     /* Find two prime numbers.  */
505     p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL);
506     q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL);
507     gcry_mpi_release (xp);  xp  = NULL;
508     gcry_mpi_release (xp1); xp1 = NULL;
509     gcry_mpi_release (xp2); xp2 = NULL;
510     gcry_mpi_release (xq);  xq  = NULL;
511     gcry_mpi_release (xq1); xq1 = NULL;
512     gcry_mpi_release (xq2); xq2 = NULL;
513     if (!p || !q)
514       {
515         gcry_mpi_release (p);
516         gcry_mpi_release (q);
517         gcry_mpi_release (e);
518         return GPG_ERR_NO_PRIME;
519       }
520   }
521
522
523   /* Compute the public modulus.  We make sure that p is smaller than
524      q to allow the use of the CRT.  */
525   if (mpi_cmp (p, q) > 0 )
526     {
527       mpi_swap (p, q);
528       *swapped = 1;
529     }
530   n = gcry_mpi_new (nbits);
531   mpi_mul (n, p, q);
532
533   /* Compute the Euler totient:  phi = (p-1)(q-1)  */
534   pm1 = gcry_mpi_snew (nbits/2);
535   qm1 = gcry_mpi_snew (nbits/2);
536   phi = gcry_mpi_snew (nbits);
537   mpi_sub_ui (pm1, p, 1);
538   mpi_sub_ui (qm1, q, 1);
539   mpi_mul (phi, pm1, qm1);
540
541   g = gcry_mpi_snew (nbits);
542   gcry_assert (gcry_mpi_gcd (g, e, phi));
543
544   /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
545   gcry_mpi_gcd (g, pm1, qm1);
546   f = pm1; pm1 = NULL;
547   gcry_mpi_release (qm1); qm1 = NULL;
548   mpi_fdiv_q (f, phi, g);
549   gcry_mpi_release (phi); phi = NULL;
550   d = g; g = NULL;
551   /* Compute the secret key:  d = e^{-1} mod lcm(p-1,q-1) */
552   mpi_invm (d, e, f);
553
554   /* Compute the inverse of p and q.  */
555   u = f; f = NULL;
556   mpi_invm (u, p, q );
557
558   if( DBG_CIPHER )
559     {
560       if (*swapped)
561         log_debug ("p and q are swapped\n");
562       log_mpidump("  p", p );
563       log_mpidump("  q", q );
564       log_mpidump("  n", n );
565       log_mpidump("  e", e );
566       log_mpidump("  d", d );
567       log_mpidump("  u", u );
568     }
569
570
571   sk->n = n;
572   sk->e = e;
573   sk->p = p;
574   sk->q = q;
575   sk->d = d;
576   sk->u = u;
577
578   /* Now we can test our keys. */
579   if (test_keys (sk, nbits - 64))
580     {
581       gcry_mpi_release (sk->n); sk->n = NULL;
582       gcry_mpi_release (sk->e); sk->e = NULL;
583       gcry_mpi_release (sk->p); sk->p = NULL;
584       gcry_mpi_release (sk->q); sk->q = NULL;
585       gcry_mpi_release (sk->d); sk->d = NULL;
586       gcry_mpi_release (sk->u); sk->u = NULL;
587       fips_signal_error ("self-test after key generation failed");
588       return GPG_ERR_SELFTEST_FAILED;
589     }
590
591   return 0;
592 }
593
594
595 /****************
596  * Test whether the secret key is valid.
597  * Returns: true if this is a valid key.
598  */
599 static int
600 check_secret_key( RSA_secret_key *sk )
601 {
602   int rc;
603   gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
604
605   mpi_mul(temp, sk->p, sk->q );
606   rc = mpi_cmp( temp, sk->n );
607   mpi_free(temp);
608   return !rc;
609 }
610
611
612
613 /****************
614  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
615  *
616  *      c = m^e mod n
617  *
618  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
619  */
620 static void
621 public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
622 {
623   if( output == input )  /* powm doesn't like output and input the same */
624     {
625       gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
626       mpi_powm( x, input, pkey->e, pkey->n );
627       mpi_set(output, x);
628       mpi_free(x);
629     }
630   else
631     mpi_powm( output, input, pkey->e, pkey->n );
632 }
633
634 #if 0
635 static void
636 stronger_key_check ( RSA_secret_key *skey )
637 {
638   gcry_mpi_t t = mpi_alloc_secure ( 0 );
639   gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
640   gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
641   gcry_mpi_t phi = mpi_alloc_secure ( 0 );
642
643   /* check that n == p * q */
644   mpi_mul( t, skey->p, skey->q);
645   if (mpi_cmp( t, skey->n) )
646     log_info ( "RSA Oops: n != p * q\n" );
647
648   /* check that p is less than q */
649   if( mpi_cmp( skey->p, skey->q ) > 0 )
650     {
651       log_info ("RSA Oops: p >= q - fixed\n");
652       _gcry_mpi_swap ( skey->p, skey->q);
653     }
654
655     /* check that e divides neither p-1 nor q-1 */
656     mpi_sub_ui(t, skey->p, 1 );
657     mpi_fdiv_r(t, t, skey->e );
658     if ( !mpi_cmp_ui( t, 0) )
659         log_info ( "RSA Oops: e divides p-1\n" );
660     mpi_sub_ui(t, skey->q, 1 );
661     mpi_fdiv_r(t, t, skey->e );
662     if ( !mpi_cmp_ui( t, 0) )
663         log_info ( "RSA Oops: e divides q-1\n" );
664
665     /* check that d is correct */
666     mpi_sub_ui( t1, skey->p, 1 );
667     mpi_sub_ui( t2, skey->q, 1 );
668     mpi_mul( phi, t1, t2 );
669     gcry_mpi_gcd(t, t1, t2);
670     mpi_fdiv_q(t, phi, t);
671     mpi_invm(t, skey->e, t );
672     if ( mpi_cmp(t, skey->d ) )
673       {
674         log_info ( "RSA Oops: d is wrong - fixed\n");
675         mpi_set (skey->d, t);
676         log_printmpi ("  fixed d", skey->d);
677       }
678
679     /* check for correctness of u */
680     mpi_invm(t, skey->p, skey->q );
681     if ( mpi_cmp(t, skey->u ) )
682       {
683         log_info ( "RSA Oops: u is wrong - fixed\n");
684         mpi_set (skey->u, t);
685         log_printmpi ("  fixed u", skey->u);
686       }
687
688     log_info ( "RSA secret key check finished\n");
689
690     mpi_free (t);
691     mpi_free (t1);
692     mpi_free (t2);
693     mpi_free (phi);
694 }
695 #endif
696
697
698
699 /****************
700  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
701  *
702  *      m = c^d mod n
703  *
704  * Or faster:
705  *
706  *      m1 = c ^ (d mod (p-1)) mod p
707  *      m2 = c ^ (d mod (q-1)) mod q
708  *      h = u * (m2 - m1) mod q
709  *      m = m1 + h * p
710  *
711  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
712  */
713 static void
714 secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
715 {
716   if (!skey->p || !skey->q || !skey->u)
717     {
718       mpi_powm (output, input, skey->d, skey->n);
719     }
720   else
721     {
722       gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
723       gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
724       gcry_mpi_t h  = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
725
726       /* m1 = c ^ (d mod (p-1)) mod p */
727       mpi_sub_ui( h, skey->p, 1  );
728       mpi_fdiv_r( h, skey->d, h );
729       mpi_powm( m1, input, h, skey->p );
730       /* m2 = c ^ (d mod (q-1)) mod q */
731       mpi_sub_ui( h, skey->q, 1  );
732       mpi_fdiv_r( h, skey->d, h );
733       mpi_powm( m2, input, h, skey->q );
734       /* h = u * ( m2 - m1 ) mod q */
735       mpi_sub( h, m2, m1 );
736       if ( mpi_has_sign ( h ) )
737         mpi_add ( h, h, skey->q );
738       mpi_mulm( h, skey->u, h, skey->q );
739       /* m = m2 + h * p */
740       mpi_mul ( h, h, skey->p );
741       mpi_add ( output, m1, h );
742
743       mpi_free ( h );
744       mpi_free ( m1 );
745       mpi_free ( m2 );
746     }
747 }
748
749
750
751 /*********************************************
752  **************  interface  ******************
753  *********************************************/
754
755 static gcry_err_code_t
756 rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
757 {
758   gpg_err_code_t ec;
759   unsigned int nbits;
760   unsigned long evalue;
761   RSA_secret_key sk;
762   gcry_sexp_t deriveparms;
763   int flags = 0;
764   gcry_sexp_t l1;
765   gcry_sexp_t swap_info = NULL;
766
767   memset (&sk, 0, sizeof sk);
768
769   ec = _gcry_pk_util_get_nbits (genparms, &nbits);
770   if (ec)
771     return ec;
772
773   ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue);
774   if (ec)
775     return ec;
776
777   /* Parse the optional flags list.  */
778   l1 = gcry_sexp_find_token (genparms, "flags", 0);
779   if (l1)
780     {
781       ec = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
782       gcry_sexp_release (l1);
783       if (ec)
784         return ec;
785     }
786
787   deriveparms = (genparms?
788                  gcry_sexp_find_token (genparms, "derive-parms", 0) : NULL);
789   if (!deriveparms)
790     {
791       /* Parse the optional "use-x931" flag. */
792       l1 = gcry_sexp_find_token (genparms, "use-x931", 0);
793       if (l1)
794         {
795           flags |= PUBKEY_FLAG_USE_X931;
796           gcry_sexp_release (l1);
797         }
798     }
799
800   if (deriveparms || (flags & PUBKEY_FLAG_USE_X931) || fips_mode ())
801     {
802       int swapped;
803       ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
804       gcry_sexp_release (deriveparms);
805       if (!ec && swapped)
806         ec = gcry_sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1);
807     }
808   else
809     {
810       /* Parse the optional "transient-key" flag. */
811       if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
812         {
813           l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
814           if (l1)
815             {
816               flags |= PUBKEY_FLAG_TRANSIENT_KEY;
817               gcry_sexp_release (l1);
818             }
819         }
820       /* Generate.  */
821       ec = generate_std (&sk, nbits, evalue,
822                          !!(flags & PUBKEY_FLAG_TRANSIENT_KEY));
823     }
824
825   if (!ec)
826     {
827       ec = gcry_sexp_build (r_skey, NULL,
828                             "(key-data"
829                             " (public-key"
830                             "  (rsa(n%m)(e%m)))"
831                             " (private-key"
832                             "  (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))"
833                             " %S)",
834                             sk.n, sk.e,
835                             sk.n, sk.e, sk.d, sk.p, sk.q, sk.u,
836                             swap_info);
837     }
838
839   mpi_free (sk.n);
840   mpi_free (sk.e);
841   mpi_free (sk.p);
842   mpi_free (sk.q);
843   mpi_free (sk.d);
844   mpi_free (sk.u);
845   gcry_sexp_release (swap_info);
846
847   return ec;
848 }
849
850
851 static gcry_err_code_t
852 rsa_check_secret_key (gcry_sexp_t keyparms)
853 {
854   gcry_err_code_t rc;
855   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
856
857   /* To check the key we need the optional parameters. */
858   rc = _gcry_sexp_extract_param (keyparms, NULL, "nedpqu",
859                                  &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
860                                  NULL);
861   if (rc)
862     goto leave;
863
864   if (!check_secret_key (&sk))
865     rc = GPG_ERR_BAD_SECKEY;
866
867  leave:
868   gcry_mpi_release (sk.n);
869   gcry_mpi_release (sk.e);
870   gcry_mpi_release (sk.d);
871   gcry_mpi_release (sk.p);
872   gcry_mpi_release (sk.q);
873   gcry_mpi_release (sk.u);
874   if (DBG_CIPHER)
875     log_debug ("rsa_testkey    => %s\n", gpg_strerror (rc));
876   return rc;
877 }
878
879
880 static gcry_err_code_t
881 rsa_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
882 {
883   gcry_err_code_t rc;
884   struct pk_encoding_ctx ctx;
885   gcry_mpi_t data = NULL;
886   RSA_public_key pk = {NULL, NULL};
887   gcry_mpi_t ciph = NULL;
888
889   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
890                                    rsa_get_nbits (keyparms));
891
892   /* Extract the data.  */
893   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
894   if (rc)
895     goto leave;
896   if (DBG_CIPHER)
897     log_mpidump ("rsa_encrypt data", data);
898   if (mpi_is_opaque (data))
899     {
900       rc = GPG_ERR_INV_DATA;
901       goto leave;
902     }
903
904   /* Extract the key.  */
905   rc = _gcry_sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
906   if (rc)
907     goto leave;
908   if (DBG_CIPHER)
909     {
910       log_mpidump ("rsa_encrypt    n", pk.n);
911       log_mpidump ("rsa_encrypt    e", pk.e);
912     }
913
914   /* Do RSA computation and build result.  */
915   ciph = gcry_mpi_new (0);
916   public (ciph, data, &pk);
917   if (DBG_CIPHER)
918     log_mpidump ("rsa_encrypt  res", ciph);
919   if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
920     {
921       /* We need to make sure to return the correct length to avoid
922          problems with missing leading zeroes.  */
923       unsigned char *em;
924       size_t emlen = (mpi_get_nbits (pk.n)+7)/8;
925
926       rc = _gcry_mpi_to_octet_string (&em, NULL, ciph, emlen);
927       if (!rc)
928         {
929           rc = gcry_sexp_build (r_ciph, NULL,
930                                 "(enc-val(rsa(a%b)))", (int)emlen, em);
931           gcry_free (em);
932         }
933     }
934   else
935     rc = gcry_sexp_build (r_ciph, NULL, "(enc-val(rsa(a%m)))", ciph);
936
937  leave:
938   gcry_mpi_release (ciph);
939   gcry_mpi_release (pk.n);
940   gcry_mpi_release (pk.e);
941   gcry_mpi_release (data);
942   _gcry_pk_util_free_encoding_ctx (&ctx);
943   if (DBG_CIPHER)
944     log_debug ("rsa_encrypt    => %s\n", gpg_strerror (rc));
945   return rc;
946 }
947
948
949 static gcry_err_code_t
950 rsa_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
951
952 {
953   gpg_err_code_t rc;
954   struct pk_encoding_ctx ctx;
955   gcry_sexp_t l1 = NULL;
956   gcry_mpi_t data = NULL;
957   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
958   gcry_mpi_t plain = NULL;
959   gcry_mpi_t r = NULL;     /* Random number needed for blinding.  */
960   gcry_mpi_t ri = NULL;    /* Modular multiplicative inverse of r.  */
961   gcry_mpi_t bldata = NULL;/* Blinded data to decrypt.  */
962   unsigned char *unpad = NULL;
963   size_t unpadlen = 0;
964
965   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
966                                    rsa_get_nbits (keyparms));
967
968   /* Extract the data.  */
969   rc = _gcry_pk_util_preparse_encval (s_data, rsa_names, &l1, &ctx);
970   if (rc)
971     goto leave;
972   rc = _gcry_sexp_extract_param (l1, NULL, "a", &data, NULL);
973   if (rc)
974     goto leave;
975   if (DBG_CIPHER)
976     log_printmpi ("rsa_decrypt data", data);
977   if (mpi_is_opaque (data))
978     {
979       rc = GPG_ERR_INV_DATA;
980       goto leave;
981     }
982
983   /* Extract the key.  */
984   rc = _gcry_sexp_extract_param (keyparms, NULL, "nedp?q?u?",
985                                  &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
986                                  NULL);
987   if (rc)
988     goto leave;
989   if (DBG_CIPHER)
990     {
991       log_printmpi ("rsa_decrypt    n", sk.n);
992       log_printmpi ("rsa_decrypt    e", sk.e);
993       if (!fips_mode ())
994         {
995           log_printmpi ("rsa_decrypt    d", sk.d);
996           log_printmpi ("rsa_decrypt    p", sk.p);
997           log_printmpi ("rsa_decrypt    q", sk.q);
998           log_printmpi ("rsa_decrypt    u", sk.u);
999         }
1000     }
1001
1002   plain = gcry_mpi_snew (ctx.nbits);
1003
1004   /* We use blinding by default to mitigate timing attacks which can
1005      be practically mounted over the network as shown by Brumley and
1006      Boney in 2003.  */
1007   if (!(ctx.flags & PUBKEY_FLAG_NO_BLINDING))
1008     {
1009       /* First, we need a random number r between 0 and n - 1, which
1010          is relatively prime to n (i.e. it is neither p nor q).  The
1011          random number needs to be only unpredictable, thus we employ
1012          the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
1013          gcry_mpi_randomize.  */
1014       r = gcry_mpi_snew (ctx.nbits);
1015       ri = gcry_mpi_snew (ctx.nbits);
1016       bldata = gcry_mpi_snew (ctx.nbits);
1017
1018       gcry_mpi_randomize (r, ctx.nbits, GCRY_WEAK_RANDOM);
1019       gcry_mpi_mod (r, r, sk.n);
1020       if (!gcry_mpi_invm (ri, r, sk.n))
1021         {
1022           rc = GPG_ERR_INTERNAL;
1023           goto leave;
1024         }
1025
1026       /* Do blinding.  We calculate: y = (x * r^e) mod n, where r is
1027          the random number, e is the public exponent, x is the
1028          non-blinded data and n is the RSA modulus.  */
1029       gcry_mpi_powm (bldata, r, sk.e, sk.n);
1030       gcry_mpi_mulm (bldata, bldata, data, sk.n);
1031
1032       /* Perform decryption.  */
1033       secret (plain, bldata, &sk);
1034       gcry_mpi_release (bldata); bldata = NULL;
1035
1036       /* Undo blinding.  Here we calculate: y = (x * r^-1) mod n,
1037          where x is the blinded decrypted data, ri is the modular
1038          multiplicative inverse of r and n is the RSA modulus.  */
1039       gcry_mpi_mulm (plain, plain, ri, sk.n);
1040
1041       gcry_mpi_release (r); r = NULL;
1042       gcry_mpi_release (ri); ri = NULL;
1043     }
1044   else
1045     secret (plain, data, &sk);
1046
1047   if (DBG_CIPHER)
1048     log_printmpi ("rsa_decrypt  res", plain);
1049
1050   /* Reverse the encoding and build the s-expression.  */
1051   switch (ctx.encoding)
1052     {
1053     case PUBKEY_ENC_PKCS1:
1054       rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
1055       mpi_free (plain);
1056       plain = NULL;
1057       if (!rc)
1058         rc = gcry_sexp_build (r_plain, NULL,
1059                               "(value %b)", (int)unpadlen, unpad);
1060       break;
1061
1062     case PUBKEY_ENC_OAEP:
1063       rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
1064                                   ctx.nbits, ctx.hash_algo,
1065                                   plain, ctx.label, ctx.labellen);
1066       mpi_free (plain);
1067       plain = NULL;
1068       if (!rc)
1069         rc = gcry_sexp_build (r_plain, NULL,
1070                               "(value %b)", (int)unpadlen, unpad);
1071       break;
1072
1073     default:
1074       /* Raw format.  For backward compatibility we need to assume a
1075          signed mpi by using the sexp format string "%m".  */
1076       rc = gcry_sexp_build (r_plain, NULL,
1077                             (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
1078                             ? "%m":"(value %m)", plain);
1079       break;
1080     }
1081
1082  leave:
1083   gcry_free (unpad);
1084   gcry_mpi_release (plain);
1085   gcry_mpi_release (sk.n);
1086   gcry_mpi_release (sk.e);
1087   gcry_mpi_release (sk.d);
1088   gcry_mpi_release (sk.p);
1089   gcry_mpi_release (sk.q);
1090   gcry_mpi_release (sk.u);
1091   gcry_mpi_release (data);
1092   gcry_mpi_release (r);
1093   gcry_mpi_release (ri);
1094   gcry_mpi_release (bldata);
1095   gcry_sexp_release (l1);
1096   _gcry_pk_util_free_encoding_ctx (&ctx);
1097   if (DBG_CIPHER)
1098     log_debug ("rsa_decrypt    => %s\n", gpg_strerror (rc));
1099   return rc;
1100 }
1101
1102
1103 static gcry_err_code_t
1104 rsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1105 {
1106   gpg_err_code_t rc;
1107   struct pk_encoding_ctx ctx;
1108   gcry_mpi_t data = NULL;
1109   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
1110   gcry_mpi_t sig = NULL;
1111
1112   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
1113                                    rsa_get_nbits (keyparms));
1114
1115   /* Extract the data.  */
1116   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1117   if (rc)
1118     goto leave;
1119   if (DBG_CIPHER)
1120     log_printmpi ("rsa_sign   data", data);
1121   if (mpi_is_opaque (data))
1122     {
1123       rc = GPG_ERR_INV_DATA;
1124       goto leave;
1125     }
1126
1127   /* Extract the key.  */
1128   rc = _gcry_sexp_extract_param (keyparms, NULL, "nedp?q?u?",
1129                                  &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1130                                  NULL);
1131   if (rc)
1132     goto leave;
1133   if (DBG_CIPHER)
1134     {
1135       log_printmpi ("rsa_sign      n", sk.n);
1136       log_printmpi ("rsa_sign      e", sk.e);
1137       if (!fips_mode ())
1138         {
1139           log_printmpi ("rsa_sign      d", sk.d);
1140           log_printmpi ("rsa_sign      p", sk.p);
1141           log_printmpi ("rsa_sign      q", sk.q);
1142           log_printmpi ("rsa_sign      u", sk.u);
1143         }
1144     }
1145
1146   /* Do RSA computation and build the result.  */
1147   sig = gcry_mpi_new (0);
1148   secret (sig, data, &sk);
1149   if (DBG_CIPHER)
1150     log_printmpi ("rsa_sign    res", sig);
1151   if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
1152     {
1153       /* We need to make sure to return the correct length to avoid
1154          problems with missing leading zeroes.  */
1155       unsigned char *em;
1156       size_t emlen = (mpi_get_nbits (sk.n)+7)/8;
1157
1158       rc = _gcry_mpi_to_octet_string (&em, NULL, sig, emlen);
1159       if (!rc)
1160         {
1161           rc = gcry_sexp_build (r_sig, NULL,
1162                                 "(sig-val(rsa(s%b)))", (int)emlen, em);
1163           gcry_free (em);
1164         }
1165     }
1166   else
1167     rc = gcry_sexp_build (r_sig, NULL, "(sig-val(rsa(s%M)))", sig);
1168
1169
1170  leave:
1171   gcry_mpi_release (sig);
1172   gcry_mpi_release (sk.n);
1173   gcry_mpi_release (sk.e);
1174   gcry_mpi_release (sk.d);
1175   gcry_mpi_release (sk.p);
1176   gcry_mpi_release (sk.q);
1177   gcry_mpi_release (sk.u);
1178   gcry_mpi_release (data);
1179   _gcry_pk_util_free_encoding_ctx (&ctx);
1180   if (DBG_CIPHER)
1181     log_debug ("rsa_sign      => %s\n", gpg_strerror (rc));
1182   return rc;
1183 }
1184
1185
1186 static gcry_err_code_t
1187 rsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1188 {
1189   gcry_err_code_t rc;
1190   struct pk_encoding_ctx ctx;
1191   gcry_sexp_t l1 = NULL;
1192   gcry_mpi_t sig = NULL;
1193   gcry_mpi_t data = NULL;
1194   RSA_public_key pk = { NULL, NULL };
1195   gcry_mpi_t result = NULL;
1196
1197   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1198                                    rsa_get_nbits (keyparms));
1199
1200   /* Extract the data.  */
1201   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1202   if (rc)
1203     goto leave;
1204   if (DBG_CIPHER)
1205     log_printmpi ("rsa_verify data", data);
1206   if (mpi_is_opaque (data))
1207     {
1208       rc = GPG_ERR_INV_DATA;
1209       goto leave;
1210     }
1211
1212   /* Extract the signature value.  */
1213   rc = _gcry_pk_util_preparse_sigval (s_sig, rsa_names, &l1, NULL);
1214   if (rc)
1215     goto leave;
1216   rc = _gcry_sexp_extract_param (l1, NULL, "s", &sig, NULL);
1217   if (rc)
1218     goto leave;
1219   if (DBG_CIPHER)
1220     log_printmpi ("rsa_verify  sig", sig);
1221
1222   /* Extract the key.  */
1223   rc = _gcry_sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
1224   if (rc)
1225     goto leave;
1226   if (DBG_CIPHER)
1227     {
1228       log_printmpi ("rsa_verify    n", pk.n);
1229       log_printmpi ("rsa_verify    e", pk.e);
1230     }
1231
1232   /* Do RSA computation and compare.  */
1233   result = gcry_mpi_new (0);
1234   public (result, sig, &pk);
1235   if (DBG_CIPHER)
1236     log_printmpi ("rsa_verify  cmp", result);
1237   if (ctx.verify_cmp)
1238     rc = ctx.verify_cmp (&ctx, result);
1239   else
1240     rc = mpi_cmp (result, data) ? GPG_ERR_BAD_SIGNATURE : 0;
1241
1242  leave:
1243   gcry_mpi_release (result);
1244   gcry_mpi_release (pk.n);
1245   gcry_mpi_release (pk.e);
1246   gcry_mpi_release (data);
1247   gcry_mpi_release (sig);
1248   gcry_sexp_release (l1);
1249   _gcry_pk_util_free_encoding_ctx (&ctx);
1250   if (DBG_CIPHER)
1251     log_debug ("rsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1252   return rc;
1253 }
1254
1255
1256
1257 /* Return the number of bits for the key described by PARMS.  On error
1258  * 0 is returned.  The format of PARMS starts with the algorithm name;
1259  * for example:
1260  *
1261  *   (rsa
1262  *     (n <mpi>)
1263  *     (e <mpi>))
1264  *
1265  * More parameters may be given but we only need N here.
1266  */
1267 static unsigned int
1268 rsa_get_nbits (gcry_sexp_t parms)
1269 {
1270   gcry_sexp_t l1;
1271   gcry_mpi_t n;
1272   unsigned int nbits;
1273
1274   l1 = gcry_sexp_find_token (parms, "n", 1);
1275   if (!l1)
1276     return 0; /* Parameter N not found.  */
1277
1278   n = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1279   gcry_sexp_release (l1);
1280   nbits = n? mpi_get_nbits (n) : 0;
1281   gcry_mpi_release (n);
1282   return nbits;
1283 }
1284
1285
1286 /* Compute a keygrip.  MD is the hash context which we are going to
1287    update.  KEYPARAM is an S-expression with the key parameters, this
1288    is usually a public key but may also be a secret key.  An example
1289    of such an S-expression is:
1290
1291       (rsa
1292         (n #00B...#)
1293         (e #010001#))
1294
1295    PKCS-15 says that for RSA only the modulus should be hashed -
1296    however, it is not clear whether this is meant to use the raw bytes
1297    (assuming this is an unsigned integer) or whether the DER required
1298    0 should be prefixed.  We hash the raw bytes.  */
1299 static gpg_err_code_t
1300 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1301 {
1302   gcry_sexp_t l1;
1303   const char *data;
1304   size_t datalen;
1305
1306   l1 = gcry_sexp_find_token (keyparam, "n", 1);
1307   if (!l1)
1308     return GPG_ERR_NO_OBJ;
1309
1310   data = gcry_sexp_nth_data (l1, 1, &datalen);
1311   if (!data)
1312     {
1313       gcry_sexp_release (l1);
1314       return GPG_ERR_NO_OBJ;
1315     }
1316
1317   gcry_md_write (md, data, datalen);
1318   gcry_sexp_release (l1);
1319
1320   return 0;
1321 }
1322
1323
1324
1325 \f
1326 /*
1327      Self-test section.
1328  */
1329
1330 static const char *
1331 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1332 {
1333   static const char sample_data[] =
1334     "(data (flags pkcs1)"
1335     " (hash sha1 #11223344556677889900aabbccddeeff10203040#))";
1336   static const char sample_data_bad[] =
1337     "(data (flags pkcs1)"
1338     " (hash sha1 #11223344556677889900aabbccddeeff80203040#))";
1339
1340   const char *errtxt = NULL;
1341   gcry_error_t err;
1342   gcry_sexp_t data = NULL;
1343   gcry_sexp_t data_bad = NULL;
1344   gcry_sexp_t sig = NULL;
1345
1346   err = gcry_sexp_sscan (&data, NULL,
1347                          sample_data, strlen (sample_data));
1348   if (!err)
1349     err = gcry_sexp_sscan (&data_bad, NULL,
1350                            sample_data_bad, strlen (sample_data_bad));
1351   if (err)
1352     {
1353       errtxt = "converting data failed";
1354       goto leave;
1355     }
1356
1357   err = gcry_pk_sign (&sig, data, skey);
1358   if (err)
1359     {
1360       errtxt = "signing failed";
1361       goto leave;
1362     }
1363   err = gcry_pk_verify (sig, data, pkey);
1364   if (err)
1365     {
1366       errtxt = "verify failed";
1367       goto leave;
1368     }
1369   err = gcry_pk_verify (sig, data_bad, pkey);
1370   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1371     {
1372       errtxt = "bad signature not detected";
1373       goto leave;
1374     }
1375
1376
1377  leave:
1378   gcry_sexp_release (sig);
1379   gcry_sexp_release (data_bad);
1380   gcry_sexp_release (data);
1381   return errtxt;
1382 }
1383
1384
1385
1386 /* Given an S-expression ENCR_DATA of the form:
1387
1388    (enc-val
1389     (rsa
1390      (a a-value)))
1391
1392    as returned by gcry_pk_decrypt, return the the A-VALUE.  On error,
1393    return NULL.  */
1394 static gcry_mpi_t
1395 extract_a_from_sexp (gcry_sexp_t encr_data)
1396 {
1397   gcry_sexp_t l1, l2, l3;
1398   gcry_mpi_t a_value;
1399
1400   l1 = gcry_sexp_find_token (encr_data, "enc-val", 0);
1401   if (!l1)
1402     return NULL;
1403   l2 = gcry_sexp_find_token (l1, "rsa", 0);
1404   gcry_sexp_release (l1);
1405   if (!l2)
1406     return NULL;
1407   l3 = gcry_sexp_find_token (l2, "a", 0);
1408   gcry_sexp_release (l2);
1409   if (!l3)
1410     return NULL;
1411   a_value = gcry_sexp_nth_mpi (l3, 1, 0);
1412   gcry_sexp_release (l3);
1413
1414   return a_value;
1415 }
1416
1417
1418 static const char *
1419 selftest_encr_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1420 {
1421   const char *errtxt = NULL;
1422   gcry_error_t err;
1423   const unsigned int nbits = 1000; /* Encrypt 1000 random bits.  */
1424   gcry_mpi_t plaintext = NULL;
1425   gcry_sexp_t plain = NULL;
1426   gcry_sexp_t encr  = NULL;
1427   gcry_mpi_t  ciphertext = NULL;
1428   gcry_sexp_t decr  = NULL;
1429   gcry_mpi_t  decr_plaintext = NULL;
1430   gcry_sexp_t tmplist = NULL;
1431
1432   /* Create plaintext.  The plaintext is actually a big integer number.  */
1433   plaintext = gcry_mpi_new (nbits);
1434   gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
1435
1436   /* Put the plaintext into an S-expression.  */
1437   err = gcry_sexp_build (&plain, NULL,
1438                          "(data (flags raw) (value %m))", plaintext);
1439   if (err)
1440     {
1441       errtxt = "converting data failed";
1442       goto leave;
1443     }
1444
1445   /* Encrypt.  */
1446   err = gcry_pk_encrypt (&encr, plain, pkey);
1447   if (err)
1448     {
1449       errtxt = "encrypt failed";
1450       goto leave;
1451     }
1452
1453   /* Extraxt the ciphertext from the returned S-expression.  */
1454   /*gcry_sexp_dump (encr);*/
1455   ciphertext = extract_a_from_sexp (encr);
1456   if (!ciphertext)
1457     {
1458       errtxt = "gcry_pk_decrypt returned garbage";
1459       goto leave;
1460     }
1461
1462   /* Check that the ciphertext does no match the plaintext.  */
1463   /* _gcry_log_printmpi ("plaintext", plaintext); */
1464   /* _gcry_log_printmpi ("ciphertxt", ciphertext); */
1465   if (!gcry_mpi_cmp (plaintext, ciphertext))
1466     {
1467       errtxt = "ciphertext matches plaintext";
1468       goto leave;
1469     }
1470
1471   /* Decrypt.  */
1472   err = gcry_pk_decrypt (&decr, encr, skey);
1473   if (err)
1474     {
1475       errtxt = "decrypt failed";
1476       goto leave;
1477     }
1478
1479   /* Extract the decrypted data from the S-expression.  Note that the
1480      output of gcry_pk_decrypt depends on whether a flags lists occurs
1481      in its input data.  Because we passed the output of
1482      gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
1483      won't be there as of today.  To be prepared for future changes we
1484      take care of it anyway.  */
1485   tmplist = gcry_sexp_find_token (decr, "value", 0);
1486   if (tmplist)
1487     decr_plaintext = gcry_sexp_nth_mpi (tmplist, 1, GCRYMPI_FMT_USG);
1488   else
1489     decr_plaintext = gcry_sexp_nth_mpi (decr, 0, GCRYMPI_FMT_USG);
1490   if (!decr_plaintext)
1491     {
1492       errtxt = "decrypt returned no plaintext";
1493       goto leave;
1494     }
1495
1496   /* Check that the decrypted plaintext matches the original  plaintext.  */
1497   if (gcry_mpi_cmp (plaintext, decr_plaintext))
1498     {
1499       errtxt = "mismatch";
1500       goto leave;
1501     }
1502
1503  leave:
1504   gcry_sexp_release (tmplist);
1505   gcry_mpi_release (decr_plaintext);
1506   gcry_sexp_release (decr);
1507   gcry_mpi_release (ciphertext);
1508   gcry_sexp_release (encr);
1509   gcry_sexp_release (plain);
1510   gcry_mpi_release (plaintext);
1511   return errtxt;
1512 }
1513
1514
1515 static gpg_err_code_t
1516 selftests_rsa (selftest_report_func_t report)
1517 {
1518   const char *what;
1519   const char *errtxt;
1520   gcry_error_t err;
1521   gcry_sexp_t skey = NULL;
1522   gcry_sexp_t pkey = NULL;
1523
1524   /* Convert the S-expressions into the internal representation.  */
1525   what = "convert";
1526   err = gcry_sexp_sscan (&skey, NULL,
1527                          sample_secret_key, strlen (sample_secret_key));
1528   if (!err)
1529     err = gcry_sexp_sscan (&pkey, NULL,
1530                            sample_public_key, strlen (sample_public_key));
1531   if (err)
1532     {
1533       errtxt = gcry_strerror (err);
1534       goto failed;
1535     }
1536
1537   what = "key consistency";
1538   err = gcry_pk_testkey (skey);
1539   if (err)
1540     {
1541       errtxt = gcry_strerror (err);
1542       goto failed;
1543     }
1544
1545   what = "sign";
1546   errtxt = selftest_sign_1024 (pkey, skey);
1547   if (errtxt)
1548     goto failed;
1549
1550   what = "encrypt";
1551   errtxt = selftest_encr_1024 (pkey, skey);
1552   if (errtxt)
1553     goto failed;
1554
1555   gcry_sexp_release (pkey);
1556   gcry_sexp_release (skey);
1557   return 0; /* Succeeded. */
1558
1559  failed:
1560   gcry_sexp_release (pkey);
1561   gcry_sexp_release (skey);
1562   if (report)
1563     report ("pubkey", GCRY_PK_RSA, what, errtxt);
1564   return GPG_ERR_SELFTEST_FAILED;
1565 }
1566
1567
1568 /* Run a full self-test for ALGO and return 0 on success.  */
1569 static gpg_err_code_t
1570 run_selftests (int algo, int extended, selftest_report_func_t report)
1571 {
1572   gpg_err_code_t ec;
1573
1574   (void)extended;
1575
1576   switch (algo)
1577     {
1578     case GCRY_PK_RSA:
1579       ec = selftests_rsa (report);
1580       break;
1581     default:
1582       ec = GPG_ERR_PUBKEY_ALGO;
1583       break;
1584
1585     }
1586   return ec;
1587 }
1588
1589
1590
1591 \f
1592 gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1593   {
1594     GCRY_PK_RSA, { 0, 1 },
1595     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1596     "RSA", rsa_names,
1597     "ne", "nedpqu", "a", "s", "n",
1598     rsa_generate,
1599     rsa_check_secret_key,
1600     rsa_encrypt,
1601     rsa_decrypt,
1602     rsa_sign,
1603     rsa_verify,
1604     rsa_get_nbits,
1605     run_selftests,
1606     compute_keygrip
1607   };