Better AES performance.
[libgcrypt.git] / cipher / rsa.c
1 /* rsa.c  -  RSA function
2  * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3  * Copyright (C) 2000, 2001, 2002, 2003 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 static void test_keys (RSA_secret_key *sk, unsigned nbits);
56 static void generate (RSA_secret_key *sk,
57                       unsigned int nbits, unsigned long use_e);
58 static int  check_secret_key (RSA_secret_key *sk);
59 static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
60 static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
61
62
63 static void
64 test_keys( RSA_secret_key *sk, unsigned nbits )
65 {
66   RSA_public_key pk;
67   gcry_mpi_t test = gcry_mpi_new ( nbits );
68   gcry_mpi_t out1 = gcry_mpi_new ( nbits );
69   gcry_mpi_t out2 = gcry_mpi_new ( nbits );
70
71   pk.n = sk->n;
72   pk.e = sk->e;
73   gcry_mpi_randomize( test, nbits, GCRY_WEAK_RANDOM );
74
75   public( out1, test, &pk );
76   secret( out2, out1, sk );
77   if( mpi_cmp( test, out2 ) )
78     log_fatal("RSA operation: public, secret failed\n");
79   secret( out1, test, sk );
80   public( out2, out1, &pk );
81   if( mpi_cmp( test, out2 ) )
82     log_fatal("RSA operation: secret, public failed\n");
83   gcry_mpi_release ( test );
84   gcry_mpi_release ( out1 );
85   gcry_mpi_release ( out2 );
86 }
87
88
89 /* Callback used by the prime generation to test whether the exponent
90    is suitable. Returns 0 if the test has been passed. */
91 static int
92 check_exponent (void *arg, gcry_mpi_t a)
93 {
94   gcry_mpi_t e = arg;
95   gcry_mpi_t tmp;
96   int result;
97   
98   mpi_sub_ui (a, a, 1);
99   tmp = _gcry_mpi_alloc_like (a);
100   result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */
101   gcry_mpi_release (tmp);
102   mpi_add_ui (a, a, 1);
103   return result;
104 }
105
106 /****************
107  * Generate a key pair with a key of size NBITS.  
108  * USE_E = 0 let Libcgrypt decide what exponent to use.
109  *       = 1 request the use of a "secure" exponent; this is required by some 
110  *           specification to be 65537.
111  *       > 2 Try starting at this value until a working exponent is found.
112  * Returns: 2 structures filled with all needed values
113  */
114 static void
115 generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e)
116 {
117   gcry_mpi_t p, q; /* the two primes */
118   gcry_mpi_t d;    /* the private key */
119   gcry_mpi_t u;
120   gcry_mpi_t t1, t2;
121   gcry_mpi_t n;    /* the public key */
122   gcry_mpi_t e;    /* the exponent */
123   gcry_mpi_t phi;  /* helper: (p-1)(q-1) */
124   gcry_mpi_t g;
125   gcry_mpi_t f;
126
127   /* make sure that nbits is even so that we generate p, q of equal size */
128   if ( (nbits&1) )
129     nbits++; 
130
131   if (use_e == 1)   /* Alias for a secure value. */
132     use_e = 65537;  /* as demanded by Spinx. */
133
134   /* Public exponent:
135      In general we use 41 as this is quite fast and more secure than the
136      commonly used 17.  Benchmarking the RSA verify function
137      with a 1024 bit key yields (2001-11-08): 
138      e=17    0.54 ms
139      e=41    0.75 ms
140      e=257   0.95 ms
141      e=65537 1.80 ms
142   */
143   e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
144   if (!use_e)
145     mpi_set_ui (e, 41);     /* This is a reasonable secure and fast value */
146   else 
147     {
148       use_e |= 1; /* make sure this is odd */
149       mpi_set_ui (e, use_e); 
150     }
151     
152   n = gcry_mpi_new (nbits);
153
154   p = q = NULL;
155   do
156     {
157       /* select two (very secret) primes */
158       if (p)
159         gcry_mpi_release (p);
160       if (q)
161         gcry_mpi_release (q);
162       if (use_e)
163         { /* Do an extra test to ensure that the given exponent is
164              suitable. */
165           p = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
166           q = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
167         }
168       else
169         { /* We check the exponent later. */
170           p = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
171           q = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
172         }
173       if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
174         mpi_swap(p,q);
175       /* calculate the modulus */
176       mpi_mul( n, p, q );
177     }
178   while ( mpi_get_nbits(n) != nbits );
179
180   /* calculate Euler totient: phi = (p-1)(q-1) */
181   t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
182   t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
183   phi = gcry_mpi_snew ( nbits );
184   g     = gcry_mpi_snew ( nbits );
185   f     = gcry_mpi_snew ( nbits );
186   mpi_sub_ui( t1, p, 1 );
187   mpi_sub_ui( t2, q, 1 );
188   mpi_mul( phi, t1, t2 );
189   gcry_mpi_gcd(g, t1, t2);
190   mpi_fdiv_q(f, phi, g);
191
192   while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
193     {
194       if (use_e)
195         BUG (); /* The prime generator already made sure that we
196                    never can get to here. */
197       mpi_add_ui (e, e, 2);
198     }
199
200   /* calculate the secret key d = e^1 mod phi */
201   d = gcry_mpi_snew ( nbits );
202   mpi_invm(d, e, f );
203   /* calculate the inverse of p and q (used for chinese remainder theorem)*/
204   u = gcry_mpi_snew ( nbits );
205   mpi_invm(u, p, q );
206
207   if( DBG_CIPHER )
208     {
209       log_mpidump("  p= ", p );
210       log_mpidump("  q= ", q );
211       log_mpidump("phi= ", phi );
212       log_mpidump("  g= ", g );
213       log_mpidump("  f= ", f );
214       log_mpidump("  n= ", n );
215       log_mpidump("  e= ", e );
216       log_mpidump("  d= ", d );
217       log_mpidump("  u= ", u );
218     }
219
220   gcry_mpi_release (t1);
221   gcry_mpi_release (t2);
222   gcry_mpi_release (phi);
223   gcry_mpi_release (f);
224   gcry_mpi_release (g);
225
226   sk->n = n;
227   sk->e = e;
228   sk->p = p;
229   sk->q = q;
230   sk->d = d;
231   sk->u = u;
232
233   /* now we can test our keys (this should never fail!) */
234   test_keys( sk, nbits - 64 );
235 }
236
237
238 /****************
239  * Test wether the secret key is valid.
240  * Returns: true if this is a valid key.
241  */
242 static int
243 check_secret_key( RSA_secret_key *sk )
244 {
245   int rc;
246   gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
247   
248   mpi_mul(temp, sk->p, sk->q );
249   rc = mpi_cmp( temp, sk->n );
250   mpi_free(temp);
251   return !rc;
252 }
253
254
255
256 /****************
257  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
258  *
259  *      c = m^e mod n
260  *
261  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
262  */
263 static void
264 public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
265 {
266   if( output == input )  /* powm doesn't like output and input the same */
267     {
268       gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
269       mpi_powm( x, input, pkey->e, pkey->n );
270       mpi_set(output, x);
271       mpi_free(x);
272     }
273   else
274     mpi_powm( output, input, pkey->e, pkey->n );
275 }
276
277 #if 0
278 static void
279 stronger_key_check ( RSA_secret_key *skey )
280 {
281   gcry_mpi_t t = mpi_alloc_secure ( 0 );
282   gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
283   gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
284   gcry_mpi_t phi = mpi_alloc_secure ( 0 );
285
286   /* check that n == p * q */
287   mpi_mul( t, skey->p, skey->q);
288   if (mpi_cmp( t, skey->n) )
289     log_info ( "RSA Oops: n != p * q\n" );
290
291   /* check that p is less than q */
292   if( mpi_cmp( skey->p, skey->q ) > 0 )
293     {
294       log_info ("RSA Oops: p >= q - fixed\n");
295       _gcry_mpi_swap ( skey->p, skey->q);
296     }
297
298     /* check that e divides neither p-1 nor q-1 */
299     mpi_sub_ui(t, skey->p, 1 );
300     mpi_fdiv_r(t, t, skey->e );
301     if ( !mpi_cmp_ui( t, 0) )
302         log_info ( "RSA Oops: e divides p-1\n" );
303     mpi_sub_ui(t, skey->q, 1 );
304     mpi_fdiv_r(t, t, skey->e );
305     if ( !mpi_cmp_ui( t, 0) )
306         log_info ( "RSA Oops: e divides q-1\n" );
307
308     /* check that d is correct */
309     mpi_sub_ui( t1, skey->p, 1 );
310     mpi_sub_ui( t2, skey->q, 1 );
311     mpi_mul( phi, t1, t2 );
312     gcry_mpi_gcd(t, t1, t2);
313     mpi_fdiv_q(t, phi, t);
314     mpi_invm(t, skey->e, t );
315     if ( mpi_cmp(t, skey->d ) )
316       {
317         log_info ( "RSA Oops: d is wrong - fixed\n");
318         mpi_set (skey->d, t);
319         _gcry_log_mpidump ("  fixed d", skey->d);
320       }
321
322     /* check for correctness of u */
323     mpi_invm(t, skey->p, skey->q );
324     if ( mpi_cmp(t, skey->u ) )
325       {
326         log_info ( "RSA Oops: u is wrong - fixed\n");
327         mpi_set (skey->u, t);
328         _gcry_log_mpidump ("  fixed u", skey->u);
329       }
330
331     log_info ( "RSA secret key check finished\n");
332
333     mpi_free (t);
334     mpi_free (t1);
335     mpi_free (t2);
336     mpi_free (phi);
337 }
338 #endif
339
340
341
342 /****************
343  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
344  *
345  *      m = c^d mod n
346  *
347  * Or faster:
348  *
349  *      m1 = c ^ (d mod (p-1)) mod p 
350  *      m2 = c ^ (d mod (q-1)) mod q 
351  *      h = u * (m2 - m1) mod q 
352  *      m = m1 + h * p
353  *
354  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
355  */
356 static void
357 secret(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
358 {
359   if (!skey->p || !skey->q || !skey->u)
360     {
361       mpi_powm (output, input, skey->d, skey->n);
362     }
363   else
364     {
365       gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
366       gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
367       gcry_mpi_t h  = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
368       
369       /* m1 = c ^ (d mod (p-1)) mod p */
370       mpi_sub_ui( h, skey->p, 1  );
371       mpi_fdiv_r( h, skey->d, h );   
372       mpi_powm( m1, input, h, skey->p );
373       /* m2 = c ^ (d mod (q-1)) mod q */
374       mpi_sub_ui( h, skey->q, 1  );
375       mpi_fdiv_r( h, skey->d, h );
376       mpi_powm( m2, input, h, skey->q );
377       /* h = u * ( m2 - m1 ) mod q */
378       mpi_sub( h, m2, m1 );
379       if ( mpi_is_neg( h ) ) 
380         mpi_add ( h, h, skey->q );
381       mpi_mulm( h, skey->u, h, skey->q ); 
382       /* m = m2 + h * p */
383       mpi_mul ( h, h, skey->p );
384       mpi_add ( output, m1, h );
385     
386       mpi_free ( h );
387       mpi_free ( m1 );
388       mpi_free ( m2 );
389     }
390 }
391
392
393
394 /* Perform RSA blinding.  */
395 static gcry_mpi_t
396 rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n)
397 {
398   /* A helper.  */
399   gcry_mpi_t a;
400
401   /* Result.  */
402   gcry_mpi_t y;
403
404   a = gcry_mpi_snew (gcry_mpi_get_nbits (n));
405   y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
406   
407   /* Now we calculate: y = (x * r^e) mod n, where r is the random
408      number, e is the public exponent, x is the non-blinded data and n
409      is the RSA modulus.  */
410   gcry_mpi_powm (a, r, e, n);
411   gcry_mpi_mulm (y, a, x, n);
412
413   gcry_mpi_release (a);
414
415   return y;
416 }
417
418 /* Undo RSA blinding.  */
419 static gcry_mpi_t
420 rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n)
421 {
422   gcry_mpi_t y;
423
424   y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
425
426   /* Here we calculate: y = (x * r^-1) mod n, where x is the blinded
427      decrypted data, ri is the modular multiplicative inverse of r and
428      n is the RSA modulus.  */
429
430   gcry_mpi_mulm (y, ri, x, n);
431
432   return y;
433 }
434
435 /*********************************************
436  **************  interface  ******************
437  *********************************************/
438
439 gcry_err_code_t
440 _gcry_rsa_generate (int algo, unsigned int nbits, unsigned long use_e,
441                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
442 {
443   RSA_secret_key sk;
444   gpg_err_code_t rc;
445   int i;
446
447   (void)algo;
448
449   generate (&sk, nbits, use_e);
450   skey[0] = sk.n;
451   skey[1] = sk.e;
452   skey[2] = sk.d;
453   skey[3] = sk.p;
454   skey[4] = sk.q;
455   skey[5] = sk.u;
456   
457   /* Make an empty list of factors.  */
458   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
459   if (!*retfactors)
460     {
461       rc = gpg_err_code_from_errno (errno);
462       for (i=0; i <= 5; i++)
463         {
464           gcry_mpi_release (skey[i]);
465           skey[i] = NULL;
466         }
467     }
468   else
469     rc = 0;
470   
471   return rc;
472 }
473
474
475 gcry_err_code_t
476 _gcry_rsa_check_secret_key( int algo, gcry_mpi_t *skey )
477 {
478   gcry_err_code_t err = GPG_ERR_NO_ERROR;
479   RSA_secret_key sk;
480
481   (void)algo;
482
483   sk.n = skey[0];
484   sk.e = skey[1];
485   sk.d = skey[2];
486   sk.p = skey[3];
487   sk.q = skey[4];
488   sk.u = skey[5];
489
490   if (!sk.p || !sk.q || !sk.u)
491     err = GPG_ERR_NO_OBJ;  /* To check the key we need the optional
492                               parameters. */
493   else if (!check_secret_key (&sk))
494     err = GPG_ERR_PUBKEY_ALGO;
495
496   return err;
497 }
498
499
500 gcry_err_code_t
501 _gcry_rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data,
502                    gcry_mpi_t *pkey, int flags)
503 {
504   RSA_public_key pk;
505
506   (void)algo;
507   (void)flags;
508   
509   pk.n = pkey[0];
510   pk.e = pkey[1];
511   resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n));
512   public (resarr[0], data, &pk);
513   
514   return GPG_ERR_NO_ERROR;
515 }
516
517 gcry_err_code_t
518 _gcry_rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
519                    gcry_mpi_t *skey, int flags)
520 {
521   RSA_secret_key sk;
522   gcry_mpi_t r = MPI_NULL;      /* Random number needed for blinding.  */
523   gcry_mpi_t ri = MPI_NULL;     /* Modular multiplicative inverse of
524                                    r.  */
525   gcry_mpi_t x = MPI_NULL;      /* Data to decrypt.  */
526   gcry_mpi_t y;                 /* Result.  */
527
528   (void)algo;
529
530   /* Extract private key.  */
531   sk.n = skey[0];
532   sk.e = skey[1];
533   sk.d = skey[2];
534   sk.p = skey[3]; /* Optional. */
535   sk.q = skey[4]; /* Optional. */
536   sk.u = skey[5]; /* Optional. */
537
538   y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
539
540   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
541     {
542       /* Initialize blinding.  */
543       
544       /* First, we need a random number r between 0 and n - 1, which
545          is relatively prime to n (i.e. it is neither p nor q).  */
546       r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
547       ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
548       
549       gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n),
550                           GCRY_STRONG_RANDOM);
551       gcry_mpi_mod (r, r, sk.n);
552
553       /* Actually it should be okay to skip the check for equality
554          with either p or q here.  */
555
556       /* Calculate inverse of r.  */
557       if (! gcry_mpi_invm (ri, r, sk.n))
558         BUG ();
559     }
560
561   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
562     x = rsa_blind (data[0], r, sk.e, sk.n);
563   else
564     x = data[0];
565
566   /* Do the encryption.  */
567   secret (y, x, &sk);
568
569   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
570     {
571       /* Undo blinding.  */
572       gcry_mpi_t a = gcry_mpi_copy (y);
573       
574       gcry_mpi_release (y);
575       y = rsa_unblind (a, ri, sk.n);
576
577       gcry_mpi_release (a);
578     }
579
580   if (! (flags & PUBKEY_FLAG_NO_BLINDING))
581     {
582       /* Deallocate resources needed for blinding.  */
583       gcry_mpi_release (x);
584       gcry_mpi_release (r);
585       gcry_mpi_release (ri);
586     }
587
588   /* Copy out result.  */
589   *result = y;
590   
591   return GPG_ERR_NO_ERROR;
592 }
593
594 gcry_err_code_t
595 _gcry_rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
596 {
597   RSA_secret_key sk;
598
599   (void)algo;
600   
601   sk.n = skey[0];
602   sk.e = skey[1];
603   sk.d = skey[2];
604   sk.p = skey[3];
605   sk.q = skey[4];
606   sk.u = skey[5];
607   resarr[0] = mpi_alloc( mpi_get_nlimbs (sk.n));
608   secret (resarr[0], data, &sk);
609
610   return GPG_ERR_NO_ERROR;
611 }
612
613 gcry_err_code_t
614 _gcry_rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
615                   int (*cmp) (void *opaque, gcry_mpi_t tmp),
616                   void *opaquev)
617 {
618   RSA_public_key pk;
619   gcry_mpi_t result;
620   gcry_err_code_t rc;
621
622   (void)algo;
623   (void)cmp;
624   (void)opaquev;
625
626   pk.n = pkey[0];
627   pk.e = pkey[1];
628   result = gcry_mpi_new ( 160 );
629   public( result, data[0], &pk );
630 #ifdef IS_DEVELOPMENT_VERSION
631   if (DBG_CIPHER)
632     {
633       log_mpidump ("rsa verify result:", result );
634       log_mpidump ("             hash:", hash );
635     }
636 #endif /*IS_DEVELOPMENT_VERSION*/
637   /*rc = (*cmp)( opaquev, result );*/
638   rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
639   gcry_mpi_release (result);
640   
641   return rc;
642 }
643
644
645 unsigned int
646 _gcry_rsa_get_nbits (int algo, gcry_mpi_t *pkey)
647 {
648   (void)algo;
649
650   return mpi_get_nbits (pkey[0]);
651 }
652
653 static const char *rsa_names[] =
654   {
655     "rsa",
656     "openpgp-rsa",
657     "oid.1.2.840.113549.1.1.1",
658     NULL,
659   };
660
661 gcry_pk_spec_t _gcry_pubkey_spec_rsa =
662   {
663     "RSA", rsa_names,
664     "ne", "nedpqu", "a", "s", "n",
665     GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
666     _gcry_rsa_generate,
667     _gcry_rsa_check_secret_key,
668     _gcry_rsa_encrypt,
669     _gcry_rsa_decrypt,
670     _gcry_rsa_sign,
671     _gcry_rsa_verify,
672     _gcry_rsa_get_nbits,
673   };