0487b736519fd0c7064bccc478dccf1cc2503bb2
[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 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 #include "rsa.h"
35
36
37 typedef struct {
38     MPI n;          /* modulus */
39     MPI e;          /* exponent */
40 } RSA_public_key;
41
42
43 typedef struct {
44     MPI n;          /* public modulus */
45     MPI e;          /* public exponent */
46     MPI d;          /* exponent */
47     MPI p;          /* prime  p. */
48     MPI q;          /* prime  q. */
49     MPI u;          /* inverse of p mod q. */
50 } RSA_secret_key;
51
52
53 static void test_keys( RSA_secret_key *sk, unsigned nbits );
54 static void generate( RSA_secret_key *sk, unsigned nbits );
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  * Generate a key pair with a key of size NBITS
87  * Returns: 2 structures filled with all needed values
88  */
89 static void
90 generate( RSA_secret_key *sk, unsigned nbits )
91 {
92     MPI p, q; /* the two primes */
93     MPI d;    /* the private key */
94     MPI u;
95     MPI t1, t2;
96     MPI n;    /* the public key */
97     MPI e;    /* the exponent */
98     MPI phi;  /* helper: (p-1)(q-1) */
99     MPI g;
100     MPI f;
101
102     /* make sure that nbits is even so that we generate p, q of equal size */
103     if ( (nbits&1) )
104       nbits++; 
105
106     n = gcry_mpi_new (nbits);
107
108     p = q = NULL;
109     do {
110       /* select two (very secret) primes */
111       if (p)
112         gcry_mpi_release (p);
113       if (q)
114         gcry_mpi_release (q);
115       p = _gcry_generate_secret_prime (nbits/2);
116       q = _gcry_generate_secret_prime (nbits/2);
117       if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
118         mpi_swap(p,q);
119       /* calculate the modulus */
120       mpi_mul( n, p, q );
121     } while ( mpi_get_nbits(n) != nbits );
122
123     /* calculate Euler totient: phi = (p-1)(q-1) */
124     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
125     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
126     phi = gcry_mpi_snew ( nbits );
127     g   = gcry_mpi_snew ( nbits );
128     f   = gcry_mpi_snew ( nbits );
129     mpi_sub_ui( t1, p, 1 );
130     mpi_sub_ui( t2, q, 1 );
131     mpi_mul( phi, t1, t2 );
132     gcry_mpi_gcd(g, t1, t2);
133     mpi_fdiv_q(f, phi, g);
134
135     /* find an public exponent.
136        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        Note: Due to Sphinx requirements we temorrary change the
145        exponent until we can rework the interface to provide more
146        parameters than just the modulus length.  */
147     e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
148     mpi_set_ui (e, 65537); 
149     if( !gcry_mpi_gcd(t1, e, phi) ) { /* actually never triggered ;-) */
150       mpi_set_ui( e, 257); 
151       if( !gcry_mpi_gcd(t1, e, phi) ) {
152         mpi_set_ui( e, 41); 
153         while( !gcry_mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
154           mpi_add_ui( e, e, 2);
155       }
156     }
157
158     /* calculate the secret key d = e^1 mod phi */
159     d = gcry_mpi_snew ( nbits );
160     mpi_invm(d, e, f );
161     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
162     u = gcry_mpi_snew ( nbits );
163     mpi_invm(u, p, q );
164
165     if( DBG_CIPHER ) {
166         log_mpidump("  p= ", p );
167         log_mpidump("  q= ", q );
168         log_mpidump("phi= ", phi );
169         log_mpidump("  g= ", g );
170         log_mpidump("  f= ", f );
171         log_mpidump("  n= ", n );
172         log_mpidump("  e= ", e );
173         log_mpidump("  d= ", d );
174         log_mpidump("  u= ", u );
175     }
176
177     gcry_mpi_release (t1);
178     gcry_mpi_release (t2);
179     gcry_mpi_release (phi);
180     gcry_mpi_release (f);
181     gcry_mpi_release (g);
182
183     sk->n = n;
184     sk->e = e;
185     sk->p = p;
186     sk->q = q;
187     sk->d = d;
188     sk->u = u;
189
190     /* now we can test our keys (this should never fail!) */
191     test_keys( sk, nbits - 64 );
192 }
193
194
195 /****************
196  * Test wether the secret key is valid.
197  * Returns: true if this is a valid key.
198  */
199 static int
200 check_secret_key( RSA_secret_key *sk )
201 {
202     int rc;
203     MPI temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
204
205     mpi_mul(temp, sk->p, sk->q );
206     rc = mpi_cmp( temp, sk->n );
207     mpi_free(temp);
208     return !rc;
209 }
210
211
212
213 /****************
214  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
215  *
216  *      c = m^e mod n
217  *
218  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
219  */
220 static void
221 public(MPI output, MPI input, RSA_public_key *pkey )
222 {
223     if( output == input ) { /* powm doesn't like output and input the same */
224         MPI x = mpi_alloc( mpi_get_nlimbs(input)*2 );
225         mpi_powm( x, input, pkey->e, pkey->n );
226         mpi_set(output, x);
227         mpi_free(x);
228     }
229     else
230         mpi_powm( output, input, pkey->e, pkey->n );
231 }
232
233 #if 0
234 static void
235 stronger_key_check ( RSA_secret_key *skey )
236 {
237   MPI t = mpi_alloc_secure ( 0 );
238   MPI t1 = mpi_alloc_secure ( 0 );
239   MPI t2 = mpi_alloc_secure ( 0 );
240   MPI phi = mpi_alloc_secure ( 0 );
241
242   /* check that n == p * q */
243   mpi_mul( t, skey->p, skey->q);
244   if (mpi_cmp( t, skey->n) )
245     log_info ( "RSA Oops: n != p * q\n" );
246
247   /* check that p is less than q */
248   if( mpi_cmp( skey->p, skey->q ) > 0 )
249     {
250       log_info ("RSA Oops: p >= q - fixed\n");
251       _gcry_mpi_swap ( skey->p, skey->q);
252     }
253
254     /* check that e divides neither p-1 nor q-1 */
255     mpi_sub_ui(t, skey->p, 1 );
256     mpi_fdiv_r(t, t, skey->e );
257     if ( !mpi_cmp_ui( t, 0) )
258         log_info ( "RSA Oops: e divides p-1\n" );
259     mpi_sub_ui(t, skey->q, 1 );
260     mpi_fdiv_r(t, t, skey->e );
261     if ( !mpi_cmp_ui( t, 0) )
262         log_info ( "RSA Oops: e divides q-1\n" );
263
264     /* check that d is correct */
265     mpi_sub_ui( t1, skey->p, 1 );
266     mpi_sub_ui( t2, skey->q, 1 );
267     mpi_mul( phi, t1, t2 );
268     gcry_mpi_gcd(t, t1, t2);
269     mpi_fdiv_q(t, phi, t);
270     mpi_invm(t, skey->e, t );
271     if ( mpi_cmp(t, skey->d ) )
272       {
273         log_info ( "RSA Oops: d is wrong - fixed\n");
274         mpi_set (skey->d, t);
275         _gcry_log_mpidump ("  fixed d", skey->d);
276       }
277
278     /* check for correctness of u */
279     mpi_invm(t, skey->p, skey->q );
280     if ( mpi_cmp(t, skey->u ) )
281       {
282         log_info ( "RSA Oops: u is wrong - fixed\n");
283         mpi_set (skey->u, t);
284         _gcry_log_mpidump ("  fixed u", skey->u);
285       }
286
287     log_info ( "RSA secret key check finished\n");
288
289     mpi_free (t);
290     mpi_free (t1);
291     mpi_free (t2);
292     mpi_free (phi);
293 }
294 #endif
295
296
297
298 /****************
299  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
300  *
301  *      m = c^d mod n
302  *
303  * Or faster:
304  *
305  *      m1 = c ^ (d mod (p-1)) mod p 
306  *      m2 = c ^ (d mod (q-1)) mod q 
307  *      h = u * (m2 - m1) mod q 
308  *      m = m1 + h * p
309  *
310  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
311  */
312 static void
313 secret(MPI output, MPI input, RSA_secret_key *skey )
314 {
315   #if 0
316     mpi_powm( output, input, skey->d, skey->n );
317   #else
318     MPI m1   = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
319     MPI m2   = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
320     MPI h    = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
321
322     /* m1 = c ^ (d mod (p-1)) mod p */
323     mpi_sub_ui( h, skey->p, 1  );
324     mpi_fdiv_r( h, skey->d, h );   
325     mpi_powm( m1, input, h, skey->p );
326     /* m2 = c ^ (d mod (q-1)) mod q */
327     mpi_sub_ui( h, skey->q, 1  );
328     mpi_fdiv_r( h, skey->d, h );
329     mpi_powm( m2, input, h, skey->q );
330     /* h = u * ( m2 - m1 ) mod q */
331     mpi_sub( h, m2, m1 );
332     if ( mpi_is_neg( h ) ) 
333         mpi_add ( h, h, skey->q );
334     mpi_mulm( h, skey->u, h, skey->q ); 
335     /* m = m2 + h * p */
336     mpi_mul ( h, h, skey->p );
337     mpi_add ( output, m1, h );
338     /* ready */
339     
340     mpi_free ( h );
341     mpi_free ( m1 );
342     mpi_free ( m2 );
343   #endif
344 }
345
346
347
348 /*********************************************
349  **************  interface  ******************
350  *********************************************/
351
352 int
353 _gcry_rsa_generate (int algo, unsigned int nbits, MPI *skey, MPI **retfactors)
354 {
355     RSA_secret_key sk;
356
357     if( !is_RSA(algo) )
358         return GCRYERR_INV_PK_ALGO;
359
360     generate( &sk, nbits );
361     skey[0] = sk.n;
362     skey[1] = sk.e;
363     skey[2] = sk.d;
364     skey[3] = sk.p;
365     skey[4] = sk.q;
366     skey[5] = sk.u;
367     /* make an empty list of factors */
368     *retfactors = gcry_xcalloc( 1, sizeof **retfactors );
369     return 0;
370 }
371
372
373 int
374 _gcry_rsa_check_secret_key( int algo, MPI *skey )
375 {
376     RSA_secret_key sk;
377
378     if( !is_RSA(algo) )
379         return GCRYERR_INV_PK_ALGO;
380
381     sk.n = skey[0];
382     sk.e = skey[1];
383     sk.d = skey[2];
384     sk.p = skey[3];
385     sk.q = skey[4];
386     sk.u = skey[5];
387     if( !check_secret_key( &sk ) )
388         return GCRYERR_INV_PK_ALGO;
389
390     return 0;
391 }
392
393
394
395 int
396 _gcry_rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
397 {
398     RSA_public_key pk;
399
400     if( algo != 1 && algo != 2 )
401         return GCRYERR_INV_PK_ALGO;
402
403     pk.n = pkey[0];
404     pk.e = pkey[1];
405     resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
406     public( resarr[0], data, &pk );
407     return 0;
408 }
409
410 int
411 _gcry_rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
412 {
413     RSA_secret_key sk;
414
415     if( algo != 1 && algo != 2 )
416         return GCRYERR_INV_PK_ALGO;
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     *result = mpi_alloc_secure( mpi_get_nlimbs( sk.n ) );
425     secret( *result, data[0], &sk );
426     return 0;
427 }
428
429 int
430 _gcry_rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
431 {
432     RSA_secret_key sk;
433
434     if( algo != 1 && algo != 3 )
435         return GCRYERR_INV_PK_ALGO;
436
437     sk.n = skey[0];
438     sk.e = skey[1];
439     sk.d = skey[2];
440     sk.p = skey[3];
441     sk.q = skey[4];
442     sk.u = skey[5];
443     resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
444     secret( resarr[0], data, &sk );
445
446     return 0;
447 }
448
449 int
450 _gcry_rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey,
451            int (*cmp)(void *opaque, MPI tmp), void *opaquev )
452 {
453     RSA_public_key pk;
454     MPI result;
455     int rc;
456
457     if( algo != 1 && algo != 3 )
458         return GCRYERR_INV_PK_ALGO;
459     pk.n = pkey[0];
460     pk.e = pkey[1];
461     result = gcry_mpi_new ( 160 );
462     public( result, data[0], &pk );
463     /*rc = (*cmp)( opaquev, result );*/
464     rc = mpi_cmp( result, hash )? GCRYERR_BAD_SIGNATURE:0;
465     gcry_mpi_release (result);
466
467     return rc;
468 }
469
470
471 unsigned int
472 _gcry_rsa_get_nbits( int algo, MPI *pkey )
473 {
474     if( !is_RSA(algo) )
475         return 0;
476     return mpi_get_nbits( pkey[0] );
477 }
478
479
480 /****************
481  * Return some information about the algorithm.  We need algo here to
482  * distinguish different flavors of the algorithm.
483  * Returns: A pointer to string describing the algorithm or NULL if
484  *          the ALGO is invalid.
485  * Usage: Bit 0 set : allows signing
486  *            1 set : allows encryption
487  */
488 const char *
489 _gcry_rsa_get_info( int algo,
490               int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
491 {
492     *npkey = 2;
493     *nskey = 6;
494     *nenc = 1;
495     *nsig = 1;
496
497     switch( algo ) {
498       case 1: *r_usage = GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR; return "RSA";
499       case 2: *r_usage = GCRY_PK_USAGE_ENCR; return "RSA-E";
500       case 3: *r_usage = GCRY_PK_USAGE_SIGN; return "RSA-S";
501       default:*r_usage = 0; return NULL;
502     }
503 }