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