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