Remove macro hacks for internal vs. external functions. Part 2 and last.
[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   if (!skey->p || !skey->q || !skey->u)
716     {
717       mpi_powm (output, input, skey->d, skey->n);
718     }
719   else
720     {
721       gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
722       gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
723       gcry_mpi_t h  = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
724
725       /* m1 = c ^ (d mod (p-1)) mod p */
726       mpi_sub_ui( h, skey->p, 1  );
727       mpi_fdiv_r( h, skey->d, h );
728       mpi_powm( m1, input, h, skey->p );
729       /* m2 = c ^ (d mod (q-1)) mod q */
730       mpi_sub_ui( h, skey->q, 1  );
731       mpi_fdiv_r( h, skey->d, h );
732       mpi_powm( m2, input, h, skey->q );
733       /* h = u * ( m2 - m1 ) mod q */
734       mpi_sub( h, m2, m1 );
735       if ( mpi_has_sign ( h ) )
736         mpi_add ( h, h, skey->q );
737       mpi_mulm( h, skey->u, h, skey->q );
738       /* m = m2 + h * p */
739       mpi_mul ( h, h, skey->p );
740       mpi_add ( output, m1, h );
741
742       mpi_free ( h );
743       mpi_free ( m1 );
744       mpi_free ( m2 );
745     }
746 }
747
748
749
750 /*********************************************
751  **************  interface  ******************
752  *********************************************/
753
754 static gcry_err_code_t
755 rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
756 {
757   gpg_err_code_t ec;
758   unsigned int nbits;
759   unsigned long evalue;
760   RSA_secret_key sk;
761   gcry_sexp_t deriveparms;
762   int flags = 0;
763   gcry_sexp_t l1;
764   gcry_sexp_t swap_info = NULL;
765
766   memset (&sk, 0, sizeof sk);
767
768   ec = _gcry_pk_util_get_nbits (genparms, &nbits);
769   if (ec)
770     return ec;
771
772   ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue);
773   if (ec)
774     return ec;
775
776   /* Parse the optional flags list.  */
777   l1 = sexp_find_token (genparms, "flags", 0);
778   if (l1)
779     {
780       ec = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
781       sexp_release (l1);
782       if (ec)
783         return ec;
784     }
785
786   deriveparms = (genparms?
787                  sexp_find_token (genparms, "derive-parms", 0) : NULL);
788   if (!deriveparms)
789     {
790       /* Parse the optional "use-x931" flag. */
791       l1 = sexp_find_token (genparms, "use-x931", 0);
792       if (l1)
793         {
794           flags |= PUBKEY_FLAG_USE_X931;
795           sexp_release (l1);
796         }
797     }
798
799   if (deriveparms || (flags & PUBKEY_FLAG_USE_X931) || fips_mode ())
800     {
801       int swapped;
802       ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
803       sexp_release (deriveparms);
804       if (!ec && swapped)
805         ec = sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1);
806     }
807   else
808     {
809       /* Parse the optional "transient-key" flag. */
810       if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
811         {
812           l1 = sexp_find_token (genparms, "transient-key", 0);
813           if (l1)
814             {
815               flags |= PUBKEY_FLAG_TRANSIENT_KEY;
816               sexp_release (l1);
817             }
818         }
819       /* Generate.  */
820       ec = generate_std (&sk, nbits, evalue,
821                          !!(flags & PUBKEY_FLAG_TRANSIENT_KEY));
822     }
823
824   if (!ec)
825     {
826       ec = sexp_build (r_skey, NULL,
827                        "(key-data"
828                        " (public-key"
829                        "  (rsa(n%m)(e%m)))"
830                        " (private-key"
831                        "  (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))"
832                        " %S)",
833                        sk.n, sk.e,
834                        sk.n, sk.e, sk.d, sk.p, sk.q, sk.u,
835                        swap_info);
836     }
837
838   mpi_free (sk.n);
839   mpi_free (sk.e);
840   mpi_free (sk.p);
841   mpi_free (sk.q);
842   mpi_free (sk.d);
843   mpi_free (sk.u);
844   sexp_release (swap_info);
845
846   return ec;
847 }
848
849
850 static gcry_err_code_t
851 rsa_check_secret_key (gcry_sexp_t keyparms)
852 {
853   gcry_err_code_t rc;
854   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
855
856   /* To check the key we need the optional parameters. */
857   rc = sexp_extract_param (keyparms, NULL, "nedpqu",
858                            &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
859                            NULL);
860   if (rc)
861     goto leave;
862
863   if (!check_secret_key (&sk))
864     rc = GPG_ERR_BAD_SECKEY;
865
866  leave:
867   _gcry_mpi_release (sk.n);
868   _gcry_mpi_release (sk.e);
869   _gcry_mpi_release (sk.d);
870   _gcry_mpi_release (sk.p);
871   _gcry_mpi_release (sk.q);
872   _gcry_mpi_release (sk.u);
873   if (DBG_CIPHER)
874     log_debug ("rsa_testkey    => %s\n", gpg_strerror (rc));
875   return rc;
876 }
877
878
879 static gcry_err_code_t
880 rsa_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
881 {
882   gcry_err_code_t rc;
883   struct pk_encoding_ctx ctx;
884   gcry_mpi_t data = NULL;
885   RSA_public_key pk = {NULL, NULL};
886   gcry_mpi_t ciph = NULL;
887
888   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
889                                    rsa_get_nbits (keyparms));
890
891   /* Extract the data.  */
892   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
893   if (rc)
894     goto leave;
895   if (DBG_CIPHER)
896     log_mpidump ("rsa_encrypt data", data);
897   if (mpi_is_opaque (data))
898     {
899       rc = GPG_ERR_INV_DATA;
900       goto leave;
901     }
902
903   /* Extract the key.  */
904   rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
905   if (rc)
906     goto leave;
907   if (DBG_CIPHER)
908     {
909       log_mpidump ("rsa_encrypt    n", pk.n);
910       log_mpidump ("rsa_encrypt    e", pk.e);
911     }
912
913   /* Do RSA computation and build result.  */
914   ciph = mpi_new (0);
915   public (ciph, data, &pk);
916   if (DBG_CIPHER)
917     log_mpidump ("rsa_encrypt  res", ciph);
918   if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
919     {
920       /* We need to make sure to return the correct length to avoid
921          problems with missing leading zeroes.  */
922       unsigned char *em;
923       size_t emlen = (mpi_get_nbits (pk.n)+7)/8;
924
925       rc = _gcry_mpi_to_octet_string (&em, NULL, ciph, emlen);
926       if (!rc)
927         {
928           rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%b)))", (int)emlen, em);
929           xfree (em);
930         }
931     }
932   else
933     rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%m)))", ciph);
934
935  leave:
936   _gcry_mpi_release (ciph);
937   _gcry_mpi_release (pk.n);
938   _gcry_mpi_release (pk.e);
939   _gcry_mpi_release (data);
940   _gcry_pk_util_free_encoding_ctx (&ctx);
941   if (DBG_CIPHER)
942     log_debug ("rsa_encrypt    => %s\n", gpg_strerror (rc));
943   return rc;
944 }
945
946
947 static gcry_err_code_t
948 rsa_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
949
950 {
951   gpg_err_code_t rc;
952   struct pk_encoding_ctx ctx;
953   gcry_sexp_t l1 = NULL;
954   gcry_mpi_t data = NULL;
955   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
956   gcry_mpi_t plain = NULL;
957   gcry_mpi_t r = NULL;     /* Random number needed for blinding.  */
958   gcry_mpi_t ri = NULL;    /* Modular multiplicative inverse of r.  */
959   gcry_mpi_t bldata = NULL;/* Blinded data to decrypt.  */
960   unsigned char *unpad = NULL;
961   size_t unpadlen = 0;
962
963   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
964                                    rsa_get_nbits (keyparms));
965
966   /* Extract the data.  */
967   rc = _gcry_pk_util_preparse_encval (s_data, rsa_names, &l1, &ctx);
968   if (rc)
969     goto leave;
970   rc = sexp_extract_param (l1, NULL, "a", &data, NULL);
971   if (rc)
972     goto leave;
973   if (DBG_CIPHER)
974     log_printmpi ("rsa_decrypt data", data);
975   if (mpi_is_opaque (data))
976     {
977       rc = GPG_ERR_INV_DATA;
978       goto leave;
979     }
980
981   /* Extract the key.  */
982   rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?",
983                            &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
984                            NULL);
985   if (rc)
986     goto leave;
987   if (DBG_CIPHER)
988     {
989       log_printmpi ("rsa_decrypt    n", sk.n);
990       log_printmpi ("rsa_decrypt    e", sk.e);
991       if (!fips_mode ())
992         {
993           log_printmpi ("rsa_decrypt    d", sk.d);
994           log_printmpi ("rsa_decrypt    p", sk.p);
995           log_printmpi ("rsa_decrypt    q", sk.q);
996           log_printmpi ("rsa_decrypt    u", sk.u);
997         }
998     }
999
1000   plain = mpi_snew (ctx.nbits);
1001
1002   /* We use blinding by default to mitigate timing attacks which can
1003      be practically mounted over the network as shown by Brumley and
1004      Boney in 2003.  */
1005   if (!(ctx.flags & PUBKEY_FLAG_NO_BLINDING))
1006     {
1007       /* First, we need a random number r between 0 and n - 1, which
1008          is relatively prime to n (i.e. it is neither p nor q).  The
1009          random number needs to be only unpredictable, thus we employ
1010          the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
1011          gcry_mpi_randomize.  */
1012       r  = mpi_snew (ctx.nbits);
1013       ri = mpi_snew (ctx.nbits);
1014       bldata = mpi_snew (ctx.nbits);
1015
1016       _gcry_mpi_randomize (r, ctx.nbits, GCRY_WEAK_RANDOM);
1017       mpi_mod (r, r, sk.n);
1018       if (!mpi_invm (ri, r, sk.n))
1019         {
1020           rc = GPG_ERR_INTERNAL;
1021           goto leave;
1022         }
1023
1024       /* Do blinding.  We calculate: y = (x * r^e) mod n, where r is
1025          the random number, e is the public exponent, x is the
1026          non-blinded data and n is the RSA modulus.  */
1027       mpi_powm (bldata, r, sk.e, sk.n);
1028       mpi_mulm (bldata, bldata, data, sk.n);
1029
1030       /* Perform decryption.  */
1031       secret (plain, bldata, &sk);
1032       _gcry_mpi_release (bldata); bldata = NULL;
1033
1034       /* Undo blinding.  Here we calculate: y = (x * r^-1) mod n,
1035          where x is the blinded decrypted data, ri is the modular
1036          multiplicative inverse of r and n is the RSA modulus.  */
1037       mpi_mulm (plain, plain, ri, sk.n);
1038
1039       _gcry_mpi_release (r); r = NULL;
1040       _gcry_mpi_release (ri); ri = NULL;
1041     }
1042   else
1043     secret (plain, data, &sk);
1044
1045   if (DBG_CIPHER)
1046     log_printmpi ("rsa_decrypt  res", plain);
1047
1048   /* Reverse the encoding and build the s-expression.  */
1049   switch (ctx.encoding)
1050     {
1051     case PUBKEY_ENC_PKCS1:
1052       rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
1053       mpi_free (plain);
1054       plain = NULL;
1055       if (!rc)
1056         rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
1057       break;
1058
1059     case PUBKEY_ENC_OAEP:
1060       rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
1061                                   ctx.nbits, ctx.hash_algo,
1062                                   plain, ctx.label, ctx.labellen);
1063       mpi_free (plain);
1064       plain = NULL;
1065       if (!rc)
1066         rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
1067       break;
1068
1069     default:
1070       /* Raw format.  For backward compatibility we need to assume a
1071          signed mpi by using the sexp format string "%m".  */
1072       rc = sexp_build (r_plain, NULL,
1073                        (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
1074                        ? "%m":"(value %m)", plain);
1075       break;
1076     }
1077
1078  leave:
1079   xfree (unpad);
1080   _gcry_mpi_release (plain);
1081   _gcry_mpi_release (sk.n);
1082   _gcry_mpi_release (sk.e);
1083   _gcry_mpi_release (sk.d);
1084   _gcry_mpi_release (sk.p);
1085   _gcry_mpi_release (sk.q);
1086   _gcry_mpi_release (sk.u);
1087   _gcry_mpi_release (data);
1088   _gcry_mpi_release (r);
1089   _gcry_mpi_release (ri);
1090   _gcry_mpi_release (bldata);
1091   sexp_release (l1);
1092   _gcry_pk_util_free_encoding_ctx (&ctx);
1093   if (DBG_CIPHER)
1094     log_debug ("rsa_decrypt    => %s\n", gpg_strerror (rc));
1095   return rc;
1096 }
1097
1098
1099 static gcry_err_code_t
1100 rsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1101 {
1102   gpg_err_code_t rc;
1103   struct pk_encoding_ctx ctx;
1104   gcry_mpi_t data = NULL;
1105   RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
1106   gcry_mpi_t sig = NULL;
1107
1108   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
1109                                    rsa_get_nbits (keyparms));
1110
1111   /* Extract the data.  */
1112   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1113   if (rc)
1114     goto leave;
1115   if (DBG_CIPHER)
1116     log_printmpi ("rsa_sign   data", data);
1117   if (mpi_is_opaque (data))
1118     {
1119       rc = GPG_ERR_INV_DATA;
1120       goto leave;
1121     }
1122
1123   /* Extract the key.  */
1124   rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?",
1125                            &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1126                            NULL);
1127   if (rc)
1128     goto leave;
1129   if (DBG_CIPHER)
1130     {
1131       log_printmpi ("rsa_sign      n", sk.n);
1132       log_printmpi ("rsa_sign      e", sk.e);
1133       if (!fips_mode ())
1134         {
1135           log_printmpi ("rsa_sign      d", sk.d);
1136           log_printmpi ("rsa_sign      p", sk.p);
1137           log_printmpi ("rsa_sign      q", sk.q);
1138           log_printmpi ("rsa_sign      u", sk.u);
1139         }
1140     }
1141
1142   /* Do RSA computation and build the result.  */
1143   sig = mpi_new (0);
1144   secret (sig, data, &sk);
1145   if (DBG_CIPHER)
1146     log_printmpi ("rsa_sign    res", sig);
1147   if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
1148     {
1149       /* We need to make sure to return the correct length to avoid
1150          problems with missing leading zeroes.  */
1151       unsigned char *em;
1152       size_t emlen = (mpi_get_nbits (sk.n)+7)/8;
1153
1154       rc = _gcry_mpi_to_octet_string (&em, NULL, sig, emlen);
1155       if (!rc)
1156         {
1157           rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%b)))", (int)emlen, em);
1158           xfree (em);
1159         }
1160     }
1161   else
1162     rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%M)))", sig);
1163
1164
1165  leave:
1166   _gcry_mpi_release (sig);
1167   _gcry_mpi_release (sk.n);
1168   _gcry_mpi_release (sk.e);
1169   _gcry_mpi_release (sk.d);
1170   _gcry_mpi_release (sk.p);
1171   _gcry_mpi_release (sk.q);
1172   _gcry_mpi_release (sk.u);
1173   _gcry_mpi_release (data);
1174   _gcry_pk_util_free_encoding_ctx (&ctx);
1175   if (DBG_CIPHER)
1176     log_debug ("rsa_sign      => %s\n", gpg_strerror (rc));
1177   return rc;
1178 }
1179
1180
1181 static gcry_err_code_t
1182 rsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1183 {
1184   gcry_err_code_t rc;
1185   struct pk_encoding_ctx ctx;
1186   gcry_sexp_t l1 = NULL;
1187   gcry_mpi_t sig = NULL;
1188   gcry_mpi_t data = NULL;
1189   RSA_public_key pk = { NULL, NULL };
1190   gcry_mpi_t result = NULL;
1191
1192   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1193                                    rsa_get_nbits (keyparms));
1194
1195   /* Extract the data.  */
1196   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1197   if (rc)
1198     goto leave;
1199   if (DBG_CIPHER)
1200     log_printmpi ("rsa_verify data", data);
1201   if (mpi_is_opaque (data))
1202     {
1203       rc = GPG_ERR_INV_DATA;
1204       goto leave;
1205     }
1206
1207   /* Extract the signature value.  */
1208   rc = _gcry_pk_util_preparse_sigval (s_sig, rsa_names, &l1, NULL);
1209   if (rc)
1210     goto leave;
1211   rc = sexp_extract_param (l1, NULL, "s", &sig, NULL);
1212   if (rc)
1213     goto leave;
1214   if (DBG_CIPHER)
1215     log_printmpi ("rsa_verify  sig", sig);
1216
1217   /* Extract the key.  */
1218   rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
1219   if (rc)
1220     goto leave;
1221   if (DBG_CIPHER)
1222     {
1223       log_printmpi ("rsa_verify    n", pk.n);
1224       log_printmpi ("rsa_verify    e", pk.e);
1225     }
1226
1227   /* Do RSA computation and compare.  */
1228   result = mpi_new (0);
1229   public (result, sig, &pk);
1230   if (DBG_CIPHER)
1231     log_printmpi ("rsa_verify  cmp", result);
1232   if (ctx.verify_cmp)
1233     rc = ctx.verify_cmp (&ctx, result);
1234   else
1235     rc = mpi_cmp (result, data) ? GPG_ERR_BAD_SIGNATURE : 0;
1236
1237  leave:
1238   _gcry_mpi_release (result);
1239   _gcry_mpi_release (pk.n);
1240   _gcry_mpi_release (pk.e);
1241   _gcry_mpi_release (data);
1242   _gcry_mpi_release (sig);
1243   sexp_release (l1);
1244   _gcry_pk_util_free_encoding_ctx (&ctx);
1245   if (DBG_CIPHER)
1246     log_debug ("rsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1247   return rc;
1248 }
1249
1250
1251
1252 /* Return the number of bits for the key described by PARMS.  On error
1253  * 0 is returned.  The format of PARMS starts with the algorithm name;
1254  * for example:
1255  *
1256  *   (rsa
1257  *     (n <mpi>)
1258  *     (e <mpi>))
1259  *
1260  * More parameters may be given but we only need N here.
1261  */
1262 static unsigned int
1263 rsa_get_nbits (gcry_sexp_t parms)
1264 {
1265   gcry_sexp_t l1;
1266   gcry_mpi_t n;
1267   unsigned int nbits;
1268
1269   l1 = sexp_find_token (parms, "n", 1);
1270   if (!l1)
1271     return 0; /* Parameter N not found.  */
1272
1273   n = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1274   sexp_release (l1);
1275   nbits = n? mpi_get_nbits (n) : 0;
1276   _gcry_mpi_release (n);
1277   return nbits;
1278 }
1279
1280
1281 /* Compute a keygrip.  MD is the hash context which we are going to
1282    update.  KEYPARAM is an S-expression with the key parameters, this
1283    is usually a public key but may also be a secret key.  An example
1284    of such an S-expression is:
1285
1286       (rsa
1287         (n #00B...#)
1288         (e #010001#))
1289
1290    PKCS-15 says that for RSA only the modulus should be hashed -
1291    however, it is not clear whether this is meant to use the raw bytes
1292    (assuming this is an unsigned integer) or whether the DER required
1293    0 should be prefixed.  We hash the raw bytes.  */
1294 static gpg_err_code_t
1295 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1296 {
1297   gcry_sexp_t l1;
1298   const char *data;
1299   size_t datalen;
1300
1301   l1 = sexp_find_token (keyparam, "n", 1);
1302   if (!l1)
1303     return GPG_ERR_NO_OBJ;
1304
1305   data = sexp_nth_data (l1, 1, &datalen);
1306   if (!data)
1307     {
1308       sexp_release (l1);
1309       return GPG_ERR_NO_OBJ;
1310     }
1311
1312   _gcry_md_write (md, data, datalen);
1313   sexp_release (l1);
1314
1315   return 0;
1316 }
1317
1318
1319
1320 \f
1321 /*
1322      Self-test section.
1323  */
1324
1325 static const char *
1326 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1327 {
1328   static const char sample_data[] =
1329     "(data (flags pkcs1)"
1330     " (hash sha1 #11223344556677889900aabbccddeeff10203040#))";
1331   static const char sample_data_bad[] =
1332     "(data (flags pkcs1)"
1333     " (hash sha1 #11223344556677889900aabbccddeeff80203040#))";
1334
1335   const char *errtxt = NULL;
1336   gcry_error_t err;
1337   gcry_sexp_t data = NULL;
1338   gcry_sexp_t data_bad = NULL;
1339   gcry_sexp_t sig = NULL;
1340
1341   err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data));
1342   if (!err)
1343     err = sexp_sscan (&data_bad, NULL,
1344                       sample_data_bad, strlen (sample_data_bad));
1345   if (err)
1346     {
1347       errtxt = "converting data failed";
1348       goto leave;
1349     }
1350
1351   err = _gcry_pk_sign (&sig, data, skey);
1352   if (err)
1353     {
1354       errtxt = "signing failed";
1355       goto leave;
1356     }
1357   err = _gcry_pk_verify (sig, data, pkey);
1358   if (err)
1359     {
1360       errtxt = "verify failed";
1361       goto leave;
1362     }
1363   err = _gcry_pk_verify (sig, data_bad, pkey);
1364   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1365     {
1366       errtxt = "bad signature not detected";
1367       goto leave;
1368     }
1369
1370
1371  leave:
1372   sexp_release (sig);
1373   sexp_release (data_bad);
1374   sexp_release (data);
1375   return errtxt;
1376 }
1377
1378
1379
1380 /* Given an S-expression ENCR_DATA of the form:
1381
1382    (enc-val
1383     (rsa
1384      (a a-value)))
1385
1386    as returned by gcry_pk_decrypt, return the the A-VALUE.  On error,
1387    return NULL.  */
1388 static gcry_mpi_t
1389 extract_a_from_sexp (gcry_sexp_t encr_data)
1390 {
1391   gcry_sexp_t l1, l2, l3;
1392   gcry_mpi_t a_value;
1393
1394   l1 = sexp_find_token (encr_data, "enc-val", 0);
1395   if (!l1)
1396     return NULL;
1397   l2 = sexp_find_token (l1, "rsa", 0);
1398   sexp_release (l1);
1399   if (!l2)
1400     return NULL;
1401   l3 = sexp_find_token (l2, "a", 0);
1402   sexp_release (l2);
1403   if (!l3)
1404     return NULL;
1405   a_value = sexp_nth_mpi (l3, 1, 0);
1406   sexp_release (l3);
1407
1408   return a_value;
1409 }
1410
1411
1412 static const char *
1413 selftest_encr_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1414 {
1415   const char *errtxt = NULL;
1416   gcry_error_t err;
1417   const unsigned int nbits = 1000; /* Encrypt 1000 random bits.  */
1418   gcry_mpi_t plaintext = NULL;
1419   gcry_sexp_t plain = NULL;
1420   gcry_sexp_t encr  = NULL;
1421   gcry_mpi_t  ciphertext = NULL;
1422   gcry_sexp_t decr  = NULL;
1423   gcry_mpi_t  decr_plaintext = NULL;
1424   gcry_sexp_t tmplist = NULL;
1425
1426   /* Create plaintext.  The plaintext is actually a big integer number.  */
1427   plaintext = mpi_new (nbits);
1428   _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
1429
1430   /* Put the plaintext into an S-expression.  */
1431   err = sexp_build (&plain, NULL, "(data (flags raw) (value %m))", plaintext);
1432   if (err)
1433     {
1434       errtxt = "converting data failed";
1435       goto leave;
1436     }
1437
1438   /* Encrypt.  */
1439   err = _gcry_pk_encrypt (&encr, plain, pkey);
1440   if (err)
1441     {
1442       errtxt = "encrypt failed";
1443       goto leave;
1444     }
1445
1446   /* Extraxt the ciphertext from the returned S-expression.  */
1447   /*sexp_dump (encr);*/
1448   ciphertext = extract_a_from_sexp (encr);
1449   if (!ciphertext)
1450     {
1451       errtxt = "gcry_pk_decrypt returned garbage";
1452       goto leave;
1453     }
1454
1455   /* Check that the ciphertext does no match the plaintext.  */
1456   /* _gcry_log_printmpi ("plaintext", plaintext); */
1457   /* _gcry_log_printmpi ("ciphertxt", ciphertext); */
1458   if (!mpi_cmp (plaintext, ciphertext))
1459     {
1460       errtxt = "ciphertext matches plaintext";
1461       goto leave;
1462     }
1463
1464   /* Decrypt.  */
1465   err = _gcry_pk_decrypt (&decr, encr, skey);
1466   if (err)
1467     {
1468       errtxt = "decrypt failed";
1469       goto leave;
1470     }
1471
1472   /* Extract the decrypted data from the S-expression.  Note that the
1473      output of gcry_pk_decrypt depends on whether a flags lists occurs
1474      in its input data.  Because we passed the output of
1475      gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
1476      won't be there as of today.  To be prepared for future changes we
1477      take care of it anyway.  */
1478   tmplist = sexp_find_token (decr, "value", 0);
1479   if (tmplist)
1480     decr_plaintext = sexp_nth_mpi (tmplist, 1, GCRYMPI_FMT_USG);
1481   else
1482     decr_plaintext = sexp_nth_mpi (decr, 0, GCRYMPI_FMT_USG);
1483   if (!decr_plaintext)
1484     {
1485       errtxt = "decrypt returned no plaintext";
1486       goto leave;
1487     }
1488
1489   /* Check that the decrypted plaintext matches the original  plaintext.  */
1490   if (mpi_cmp (plaintext, decr_plaintext))
1491     {
1492       errtxt = "mismatch";
1493       goto leave;
1494     }
1495
1496  leave:
1497   sexp_release (tmplist);
1498   _gcry_mpi_release (decr_plaintext);
1499   sexp_release (decr);
1500   _gcry_mpi_release (ciphertext);
1501   sexp_release (encr);
1502   sexp_release (plain);
1503   _gcry_mpi_release (plaintext);
1504   return errtxt;
1505 }
1506
1507
1508 static gpg_err_code_t
1509 selftests_rsa (selftest_report_func_t report)
1510 {
1511   const char *what;
1512   const char *errtxt;
1513   gcry_error_t err;
1514   gcry_sexp_t skey = NULL;
1515   gcry_sexp_t pkey = NULL;
1516
1517   /* Convert the S-expressions into the internal representation.  */
1518   what = "convert";
1519   err = sexp_sscan (&skey, NULL, sample_secret_key, strlen (sample_secret_key));
1520   if (!err)
1521     err = sexp_sscan (&pkey, NULL,
1522                       sample_public_key, strlen (sample_public_key));
1523   if (err)
1524     {
1525       errtxt = _gcry_strerror (err);
1526       goto failed;
1527     }
1528
1529   what = "key consistency";
1530   err = _gcry_pk_testkey (skey);
1531   if (err)
1532     {
1533       errtxt = _gcry_strerror (err);
1534       goto failed;
1535     }
1536
1537   what = "sign";
1538   errtxt = selftest_sign_1024 (pkey, skey);
1539   if (errtxt)
1540     goto failed;
1541
1542   what = "encrypt";
1543   errtxt = selftest_encr_1024 (pkey, skey);
1544   if (errtxt)
1545     goto failed;
1546
1547   sexp_release (pkey);
1548   sexp_release (skey);
1549   return 0; /* Succeeded. */
1550
1551  failed:
1552   sexp_release (pkey);
1553   sexp_release (skey);
1554   if (report)
1555     report ("pubkey", GCRY_PK_RSA, what, errtxt);
1556   return GPG_ERR_SELFTEST_FAILED;
1557 }
1558
1559
1560 /* Run a full self-test for ALGO and return 0 on success.  */
1561 static gpg_err_code_t
1562 run_selftests (int algo, int extended, selftest_report_func_t report)
1563 {
1564   gpg_err_code_t ec;
1565
1566   (void)extended;
1567
1568   switch (algo)
1569     {
1570     case GCRY_PK_RSA:
1571       ec = selftests_rsa (report);
1572       break;
1573     default:
1574       ec = GPG_ERR_PUBKEY_ALGO;
1575       break;
1576
1577     }
1578   return ec;
1579 }
1580
1581
1582
1583 \f
1584 gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1585   {
1586     GCRY_PK_RSA, { 0, 1 },
1587     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1588     "RSA", rsa_names,
1589     "ne", "nedpqu", "a", "s", "n",
1590     rsa_generate,
1591     rsa_check_secret_key,
1592     rsa_encrypt,
1593     rsa_decrypt,
1594     rsa_sign,
1595     rsa_verify,
1596     rsa_get_nbits,
1597     run_selftests,
1598     compute_keygrip
1599   };