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