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