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