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