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