Minor cleanups.
[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 Spinx. */
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 /****************
332  * Test wether the secret key is valid.
333  * Returns: true if this is a valid key.
334  */
335 static int
336 check_secret_key( RSA_secret_key *sk )
337 {
338   int rc;
339   gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
340   
341   mpi_mul(temp, sk->p, sk->q );
342   rc = mpi_cmp( temp, sk->n );
343   mpi_free(temp);
344   return !rc;
345 }
346
347
348
349 /****************
350  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
351  *
352  *      c = m^e mod n
353  *
354  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
355  */
356 static void
357 public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
358 {
359   if( output == input )  /* powm doesn't like output and input the same */
360     {
361       gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
362       mpi_powm( x, input, pkey->e, pkey->n );
363       mpi_set(output, x);
364       mpi_free(x);
365     }
366   else
367     mpi_powm( output, input, pkey->e, pkey->n );
368 }
369
370 #if 0
371 static void
372 stronger_key_check ( RSA_secret_key *skey )
373 {
374   gcry_mpi_t t = mpi_alloc_secure ( 0 );
375   gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
376   gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
377   gcry_mpi_t phi = mpi_alloc_secure ( 0 );
378
379   /* check that n == p * q */
380   mpi_mul( t, skey->p, skey->q);
381   if (mpi_cmp( t, skey->n) )
382     log_info ( "RSA Oops: n != p * q\n" );
383
384   /* check that p is less than q */
385   if( mpi_cmp( skey->p, skey->q ) > 0 )
386     {
387       log_info ("RSA Oops: p >= q - fixed\n");
388       _gcry_mpi_swap ( skey->p, skey->q);
389     }
390
391     /* check that e divides neither p-1 nor q-1 */
392     mpi_sub_ui(t, skey->p, 1 );
393     mpi_fdiv_r(t, t, skey->e );
394     if ( !mpi_cmp_ui( t, 0) )
395         log_info ( "RSA Oops: e divides p-1\n" );
396     mpi_sub_ui(t, skey->q, 1 );
397     mpi_fdiv_r(t, t, skey->e );
398     if ( !mpi_cmp_ui( t, 0) )
399         log_info ( "RSA Oops: e divides q-1\n" );
400
401     /* check that d is correct */
402     mpi_sub_ui( t1, skey->p, 1 );
403     mpi_sub_ui( t2, skey->q, 1 );
404     mpi_mul( phi, t1, t2 );
405     gcry_mpi_gcd(t, t1, t2);
406     mpi_fdiv_q(t, phi, t);
407     mpi_invm(t, skey->e, t );
408     if ( mpi_cmp(t, skey->d ) )
409       {
410         log_info ( "RSA Oops: d is wrong - fixed\n");
411         mpi_set (skey->d, t);
412         _gcry_log_mpidump ("  fixed d", skey->d);
413       }
414
415     /* check for correctness of u */
416     mpi_invm(t, skey->p, skey->q );
417     if ( mpi_cmp(t, skey->u ) )
418       {
419         log_info ( "RSA Oops: u is wrong - fixed\n");
420         mpi_set (skey->u, t);
421         _gcry_log_mpidump ("  fixed u", skey->u);
422       }
423
424     log_info ( "RSA secret key check finished\n");
425
426     mpi_free (t);
427     mpi_free (t1);
428     mpi_free (t2);
429     mpi_free (phi);
430 }
431 #endif
432
433
434
435 /****************
436  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
437  *
438  *      m = c^d mod n
439  *
440  * Or faster:
441  *
442  *      m1 = c ^ (d mod (p-1)) mod p 
443  *      m2 = c ^ (d mod (q-1)) mod q 
444  *      h = u * (m2 - m1) mod q 
445  *      m = m1 + h * p
446  *
447  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
448  */
449 static void
450 secret(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
451 {
452   if (!skey->p || !skey->q || !skey->u)
453     {
454       mpi_powm (output, input, skey->d, skey->n);
455     }
456   else
457     {
458       gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
459       gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
460       gcry_mpi_t h  = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
461       
462       /* m1 = c ^ (d mod (p-1)) mod p */
463       mpi_sub_ui( h, skey->p, 1  );
464       mpi_fdiv_r( h, skey->d, h );   
465       mpi_powm( m1, input, h, skey->p );
466       /* m2 = c ^ (d mod (q-1)) mod q */
467       mpi_sub_ui( h, skey->q, 1  );
468       mpi_fdiv_r( h, skey->d, h );
469       mpi_powm( m2, input, h, skey->q );
470       /* h = u * ( m2 - m1 ) mod q */
471       mpi_sub( h, m2, m1 );
472       if ( mpi_is_neg( h ) ) 
473         mpi_add ( h, h, skey->q );
474       mpi_mulm( h, skey->u, h, skey->q ); 
475       /* m = m2 + h * p */
476       mpi_mul ( h, h, skey->p );
477       mpi_add ( output, m1, h );
478     
479       mpi_free ( h );
480       mpi_free ( m1 );
481       mpi_free ( m2 );
482     }
483 }
484
485
486
487 /* Perform RSA blinding.  */
488 static gcry_mpi_t
489 rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n)
490 {
491   /* A helper.  */
492   gcry_mpi_t a;
493
494   /* Result.  */
495   gcry_mpi_t y;
496
497   a = gcry_mpi_snew (gcry_mpi_get_nbits (n));
498   y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
499   
500   /* Now we calculate: y = (x * r^e) mod n, where r is the random
501      number, e is the public exponent, x is the non-blinded data and n
502      is the RSA modulus.  */
503   gcry_mpi_powm (a, r, e, n);
504   gcry_mpi_mulm (y, a, x, n);
505
506   gcry_mpi_release (a);
507
508   return y;
509 }
510
511 /* Undo RSA blinding.  */
512 static gcry_mpi_t
513 rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n)
514 {
515   gcry_mpi_t y;
516
517   y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
518
519   /* Here we calculate: y = (x * r^-1) mod n, where x is the blinded
520      decrypted data, ri is the modular multiplicative inverse of r and
521      n is the RSA modulus.  */
522
523   gcry_mpi_mulm (y, ri, x, n);
524
525   return y;
526 }
527
528 /*********************************************
529  **************  interface  ******************
530  *********************************************/
531
532 static gcry_err_code_t
533 rsa_generate_ext (int algo, unsigned int nbits, unsigned int qbits,
534                   unsigned long use_e,
535                   const char *name, const gcry_sexp_t domain,
536                   unsigned int keygen_flags,
537                   gcry_mpi_t *skey, gcry_mpi_t **retfactors)
538 {
539   RSA_secret_key sk;
540   gpg_err_code_t ec;
541   int i;
542
543   (void)algo;
544   (void)qbits;
545   (void)name;
546   (void)domain;
547
548   ec = generate_std (&sk, nbits, use_e,
549                      !!(keygen_flags & PUBKEY_FLAG_TRANSIENT_KEY) );
550   if (!ec)
551     {
552       skey[0] = sk.n;
553       skey[1] = sk.e;
554       skey[2] = sk.d;
555       skey[3] = sk.p;
556       skey[4] = sk.q;
557       skey[5] = sk.u;
558   
559       /* Make an empty list of factors.  */
560       *retfactors = gcry_calloc ( 1, sizeof **retfactors );
561       if (!*retfactors)
562         {
563           ec = gpg_err_code_from_syserror ();
564           for (i=0; i <= 5; i++)
565             {
566               gcry_mpi_release (skey[i]);
567               skey[i] = NULL;
568             }
569         }
570       else
571         ec = 0;
572     }
573   
574   return ec;
575 }
576
577
578 static gcry_err_code_t
579 rsa_generate (int algo, unsigned int nbits, unsigned long use_e,
580               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
581 {
582   return rsa_generate_ext (algo, nbits, 0, use_e, NULL, NULL, 0,
583                            skey, retfactors);
584 }
585
586
587 static gcry_err_code_t
588 rsa_check_secret_key (int algo, gcry_mpi_t *skey)
589 {
590   gcry_err_code_t err = GPG_ERR_NO_ERROR;
591   RSA_secret_key sk;
592
593   (void)algo;
594
595   sk.n = skey[0];
596   sk.e = skey[1];
597   sk.d = skey[2];
598   sk.p = skey[3];
599   sk.q = skey[4];
600   sk.u = skey[5];
601
602   if (!sk.p || !sk.q || !sk.u)
603     err = GPG_ERR_NO_OBJ;  /* To check the key we need the optional
604                               parameters. */
605   else if (!check_secret_key (&sk))
606     err = GPG_ERR_PUBKEY_ALGO;
607
608   return err;
609 }
610
611
612 static gcry_err_code_t
613 rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data,
614              gcry_mpi_t *pkey, int flags)
615 {
616   RSA_public_key pk;
617
618   (void)algo;
619   (void)flags;
620   
621   pk.n = pkey[0];
622   pk.e = pkey[1];
623   resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n));
624   public (resarr[0], data, &pk);
625   
626   return GPG_ERR_NO_ERROR;
627 }
628
629
630 static gcry_err_code_t
631 rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
632              gcry_mpi_t *skey, int flags)
633 {
634   RSA_secret_key sk;
635   gcry_mpi_t r = MPI_NULL;      /* Random number needed for blinding.  */
636   gcry_mpi_t ri = MPI_NULL;     /* Modular multiplicative inverse of
637                                    r.  */
638   gcry_mpi_t x = MPI_NULL;      /* Data to decrypt.  */
639   gcry_mpi_t y;                 /* Result.  */
640
641   (void)algo;
642
643   /* Extract private key.  */
644   sk.n = skey[0];
645   sk.e = skey[1];
646   sk.d = skey[2];
647   sk.p = skey[3]; /* Optional. */
648   sk.q = skey[4]; /* Optional. */
649   sk.u = skey[5]; /* Optional. */
650
651   y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
652
653   /* We use blinding by default to mitigate timing attacks which can
654      be practically mounted over the network as shown by Brumley and
655      Boney in 2003.  */ 
656   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
657     {
658       /* Initialize blinding.  */
659       
660       /* First, we need a random number r between 0 and n - 1, which
661          is relatively prime to n (i.e. it is neither p nor q).  The
662          random number needs to be only unpredictable, thus we employ
663          the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
664          gcry_mpi_randomize.  */
665       r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
666       ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
667       
668       gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n), GCRY_WEAK_RANDOM);
669       gcry_mpi_mod (r, r, sk.n);
670
671       /* Calculate inverse of r.  It practically impossible that the
672          follwing test fails, thus we do not add code to release
673          allocated resources.  */
674       if (!gcry_mpi_invm (ri, r, sk.n))
675         return GPG_ERR_INTERNAL;
676     }
677
678   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
679     x = rsa_blind (data[0], r, sk.e, sk.n);
680   else
681     x = data[0];
682
683   /* Do the encryption.  */
684   secret (y, x, &sk);
685
686   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
687     {
688       /* Undo blinding.  */
689       gcry_mpi_t a = gcry_mpi_copy (y);
690       
691       gcry_mpi_release (y);
692       y = rsa_unblind (a, ri, sk.n);
693
694       gcry_mpi_release (a);
695     }
696
697   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
698     {
699       /* Deallocate resources needed for blinding.  */
700       gcry_mpi_release (x);
701       gcry_mpi_release (r);
702       gcry_mpi_release (ri);
703     }
704
705   /* Copy out result.  */
706   *result = y;
707   
708   return GPG_ERR_NO_ERROR;
709 }
710
711
712 static gcry_err_code_t
713 rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
714 {
715   RSA_secret_key sk;
716
717   (void)algo;
718   
719   sk.n = skey[0];
720   sk.e = skey[1];
721   sk.d = skey[2];
722   sk.p = skey[3];
723   sk.q = skey[4];
724   sk.u = skey[5];
725   resarr[0] = mpi_alloc( mpi_get_nlimbs (sk.n));
726   secret (resarr[0], data, &sk);
727
728   return GPG_ERR_NO_ERROR;
729 }
730
731
732 static gcry_err_code_t
733 rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
734                   int (*cmp) (void *opaque, gcry_mpi_t tmp),
735                   void *opaquev)
736 {
737   RSA_public_key pk;
738   gcry_mpi_t result;
739   gcry_err_code_t rc;
740
741   (void)algo;
742   (void)cmp;
743   (void)opaquev;
744
745   pk.n = pkey[0];
746   pk.e = pkey[1];
747   result = gcry_mpi_new ( 160 );
748   public( result, data[0], &pk );
749 #ifdef IS_DEVELOPMENT_VERSION
750   if (DBG_CIPHER)
751     {
752       log_mpidump ("rsa verify result:", result );
753       log_mpidump ("             hash:", hash );
754     }
755 #endif /*IS_DEVELOPMENT_VERSION*/
756   /*rc = (*cmp)( opaquev, result );*/
757   rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
758   gcry_mpi_release (result);
759   
760   return rc;
761 }
762
763
764 static unsigned int
765 rsa_get_nbits (int algo, gcry_mpi_t *pkey)
766 {
767   (void)algo;
768
769   return mpi_get_nbits (pkey[0]);
770 }
771
772
773 /* Compute a keygrip.  MD is the hash context which we are going to
774    update.  KEYPARAM is an S-expression with the key parameters, this
775    is usually a public key but may also be a secret key.  An example
776    of such an S-expression is:
777
778       (rsa
779         (n #00B...#)
780         (e #010001#))
781         
782    PKCS-15 says that for RSA only the modulus should be hashed -
783    however, it is not clear wether this is meant to use the raw bytes
784    (assuming this is an unsigned integer) or whether the DER required
785    0 should be prefixed.  We hash the raw bytes.  */
786 static gpg_err_code_t
787 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
788 {
789   gcry_sexp_t l1;
790   const char *data;
791   size_t datalen;
792
793   l1 = gcry_sexp_find_token (keyparam, "n", 1);
794   if (!l1)
795     return GPG_ERR_NO_OBJ;
796
797   data = gcry_sexp_nth_data (l1, 1, &datalen);
798   if (!data)
799     {
800       gcry_sexp_release (l1);
801       return GPG_ERR_NO_OBJ;
802     }
803
804   gcry_md_write (md, data, datalen);
805   gcry_sexp_release (l1);
806
807   return 0;
808 }
809
810
811
812 \f
813 /* 
814      Self-test section.
815  */
816
817 static const char *
818 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
819 {
820   static const char sample_data[] = 
821     "(data (flags pkcs1)"
822     " (hash sha1 #11223344556677889900aabbccddeeff10203040#))";
823   static const char sample_data_bad[] = 
824     "(data (flags pkcs1)"
825     " (hash sha1 #11223344556677889900aabbccddeeff80203040#))";
826
827   const char *errtxt = NULL;
828   gcry_error_t err;
829   gcry_sexp_t data = NULL;
830   gcry_sexp_t data_bad = NULL;
831   gcry_sexp_t sig = NULL;
832
833   err = gcry_sexp_sscan (&data, NULL,
834                          sample_data, strlen (sample_data));
835   if (!err)
836     err = gcry_sexp_sscan (&data_bad, NULL, 
837                            sample_data_bad, strlen (sample_data_bad));
838   if (err)
839     {
840       errtxt = "converting data failed";
841       goto leave;
842     }
843
844   err = gcry_pk_sign (&sig, data, skey);
845   if (err)
846     {
847       errtxt = "signing failed";
848       goto leave;
849     }
850   err = gcry_pk_verify (sig, data, pkey);
851   if (err)
852     {
853       errtxt = "verify failed";
854       goto leave;
855     }
856   err = gcry_pk_verify (sig, data_bad, pkey);
857   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
858     {
859       errtxt = "bad signature not detected";
860       goto leave;
861     }
862
863
864  leave:
865   gcry_sexp_release (sig);
866   gcry_sexp_release (data_bad);
867   gcry_sexp_release (data);
868   return errtxt;
869 }
870
871
872
873 /* Given an S-expression ENCR_DATA of the form:
874
875    (enc-val
876     (rsa
877      (a a-value)))
878
879    as returned by gcry_pk_decrypt, return the the A-VALUE.  On error,
880    return NULL.  */
881 static gcry_mpi_t
882 extract_a_from_sexp (gcry_sexp_t encr_data)
883 {
884   gcry_sexp_t l1, l2, l3;
885   gcry_mpi_t a_value;
886
887   l1 = gcry_sexp_find_token (encr_data, "enc-val", 0);
888   if (!l1)
889     return NULL;
890   l2 = gcry_sexp_find_token (l1, "rsa", 0);
891   gcry_sexp_release (l1);
892   if (!l2)
893     return NULL;
894   l3 = gcry_sexp_find_token (l2, "a", 0);
895   gcry_sexp_release (l2);
896   if (!l3)
897     return NULL;
898   a_value = gcry_sexp_nth_mpi (l3, 1, 0);
899   gcry_sexp_release (l3);
900
901   return a_value;
902 }
903
904
905 static const char *
906 selftest_encr_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
907 {
908   const char *errtxt = NULL;
909   gcry_error_t err;
910   const unsigned int nbits = 1000; /* Encrypt 1000 random bits.  */
911   gcry_mpi_t plaintext = NULL;
912   gcry_sexp_t plain = NULL;
913   gcry_sexp_t encr  = NULL;
914   gcry_mpi_t  ciphertext = NULL;
915   gcry_sexp_t decr  = NULL;
916   gcry_mpi_t  decr_plaintext = NULL;
917   gcry_sexp_t tmplist = NULL;
918
919   /* Create plaintext.  The plaintext is actually a big integer number.  */
920   plaintext = gcry_mpi_new (nbits);
921   gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
922   
923   /* Put the plaintext into an S-expression.  */
924   err = gcry_sexp_build (&plain, NULL,
925                          "(data (flags raw) (value %m))", plaintext);
926   if (err)
927     {
928       errtxt = "converting data failed";
929       goto leave;
930     }
931
932   /* Encrypt.  */
933   err = gcry_pk_encrypt (&encr, plain, pkey);
934   if (err)
935     {
936       errtxt = "encrypt failed";
937       goto leave;
938     }
939
940   /* Extraxt the ciphertext from the returned S-expression.  */
941   /*gcry_sexp_dump (encr);*/
942   ciphertext = extract_a_from_sexp (encr);
943   if (!ciphertext)
944     {
945       errtxt = "gcry_pk_decrypt returned garbage";
946       goto leave;
947     }
948
949   /* Check that the ciphertext does no match the plaintext.  */
950   /* _gcry_log_mpidump ("plaintext", plaintext); */
951   /* _gcry_log_mpidump ("ciphertxt", ciphertext); */
952   if (!gcry_mpi_cmp (plaintext, ciphertext))
953     {
954       errtxt = "ciphertext matches plaintext";
955       goto leave;
956     }
957
958   /* Decrypt.  */
959   err = gcry_pk_decrypt (&decr, encr, skey);
960   if (err)
961     {
962       errtxt = "decrypt failed";
963       goto leave;
964     }
965
966   /* Extract the decrypted data from the S-expression.  Note that the
967      output of gcry_pk_decrypt depends on whether a flags lists occurs
968      in its input data.  Because we passed the output of
969      gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
970      won't be there as of today.  To be prepared for future changes we
971      take care of it anyway.  */
972   tmplist = gcry_sexp_find_token (decr, "value", 0);
973   if (tmplist)
974     decr_plaintext = gcry_sexp_nth_mpi (tmplist, 1, GCRYMPI_FMT_USG);
975   else
976     decr_plaintext = gcry_sexp_nth_mpi (decr, 0, GCRYMPI_FMT_USG);
977   if (!decr_plaintext)
978     {
979       errtxt = "decrypt returned no plaintext";
980       goto leave;
981     }
982   
983   /* Check that the decrypted plaintext matches the original  plaintext.  */
984   if (gcry_mpi_cmp (plaintext, decr_plaintext))
985     {
986       errtxt = "mismatch";
987       goto leave;
988     }
989
990  leave:
991   gcry_sexp_release (tmplist);
992   gcry_mpi_release (decr_plaintext);
993   gcry_sexp_release (decr);
994   gcry_mpi_release (ciphertext);
995   gcry_sexp_release (encr);
996   gcry_sexp_release (plain);
997   gcry_mpi_release (plaintext);
998   return errtxt;
999 }
1000
1001
1002 static gpg_err_code_t
1003 selftests_rsa (selftest_report_func_t report)
1004 {
1005   const char *what;
1006   const char *errtxt;
1007   gcry_error_t err;
1008   gcry_sexp_t skey = NULL;
1009   gcry_sexp_t pkey = NULL;
1010   
1011   /* Convert the S-expressions into the internal representation.  */
1012   what = "convert";
1013   err = gcry_sexp_sscan (&skey, NULL, 
1014                          sample_secret_key, strlen (sample_secret_key));
1015   if (!err)
1016     err = gcry_sexp_sscan (&pkey, NULL, 
1017                            sample_public_key, strlen (sample_public_key));
1018   if (err)
1019     {
1020       errtxt = gcry_strerror (err);
1021       goto failed;
1022     }
1023
1024   what = "key consistency";
1025   err = gcry_pk_testkey (skey);
1026   if (err)
1027     {
1028       errtxt = gcry_strerror (err);
1029       goto failed;
1030     }
1031
1032   what = "sign";
1033   errtxt = selftest_sign_1024 (pkey, skey);
1034   if (errtxt)
1035     goto failed;
1036
1037   what = "encrypt";
1038   errtxt = selftest_encr_1024 (pkey, skey);
1039   if (errtxt)
1040     goto failed;
1041
1042   gcry_sexp_release (pkey);
1043   gcry_sexp_release (skey);
1044   return 0; /* Succeeded. */
1045
1046  failed:
1047   gcry_sexp_release (pkey);
1048   gcry_sexp_release (skey);
1049   if (report)
1050     report ("pubkey", GCRY_PK_RSA, what, errtxt);
1051   return GPG_ERR_SELFTEST_FAILED;
1052 }
1053
1054
1055 /* Run a full self-test for ALGO and return 0 on success.  */
1056 static gpg_err_code_t
1057 run_selftests (int algo, int extended, selftest_report_func_t report)
1058 {
1059   gpg_err_code_t ec;
1060
1061   (void)extended;
1062
1063   switch (algo)
1064     {
1065     case GCRY_PK_RSA:
1066       ec = selftests_rsa (report);
1067       break;
1068     default:
1069       ec = GPG_ERR_PUBKEY_ALGO;
1070       break;
1071         
1072     }
1073   return ec;
1074 }
1075
1076
1077
1078 \f
1079 static const char *rsa_names[] =
1080   {
1081     "rsa",
1082     "openpgp-rsa",
1083     "oid.1.2.840.113549.1.1.1",
1084     NULL,
1085   };
1086
1087 gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1088   {
1089     "RSA", rsa_names,
1090     "ne", "nedpqu", "a", "s", "n",
1091     GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
1092     rsa_generate,
1093     rsa_check_secret_key,
1094     rsa_encrypt,
1095     rsa_decrypt,
1096     rsa_sign,
1097     rsa_verify,
1098     rsa_get_nbits,
1099   };
1100 pk_extra_spec_t _gcry_pubkey_extraspec_rsa = 
1101   {
1102     run_selftests,
1103     rsa_generate_ext,
1104     compute_keygrip
1105   };
1106