f23f3fcaad66fd3e7f43aef545d0b3a5748b3f00
[gnupg.git] / cipher / rsa.c
1 /* rsa.c  -  RSA function
2  *      Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3  *      Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4  *
5  * This file is part of GnuPG.
6  *
7  * GnuPG is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * GnuPG 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 General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20  * USA.
21  */
22
23 /* This code uses an algorithm protected by U.S. Patent #4,405,829
24    which expires on September 20, 2000.  The patent holder placed that
25    patent into the public domain on Sep 6th, 2000.
26 */
27  
28 #include <config.h>
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include "util.h"
33 #include "mpi.h"
34 #include "cipher.h"
35 #include "rsa.h"
36
37
38 typedef struct {
39     MPI n;          /* modulus */
40     MPI e;          /* exponent */
41 } RSA_public_key;
42
43
44 typedef struct {
45     MPI n;          /* public modulus */
46     MPI e;          /* public exponent */
47     MPI d;          /* exponent */
48     MPI p;          /* prime  p. */
49     MPI q;          /* prime  q. */
50     MPI 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, unsigned nbits );
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 = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
66     MPI out1 = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
67     MPI out2 = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
68
69     pk.n = sk->n;
70     pk.e = sk->e;
71     {   char *p = get_random_bits( nbits, 0, 0 );
72         mpi_set_buffer( test, p, (nbits+7)/8, 0 );
73         m_free(p);
74     }
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     mpi_free( test );
85     mpi_free( out1 );
86     mpi_free( out2 );
87 }
88
89 /****************
90  * Generate a key pair with a key of size NBITS
91  * Returns: 2 structures filled with all needed values
92  */
93 static void
94 generate( RSA_secret_key *sk, unsigned nbits )
95 {
96     MPI p, q; /* the two primes */
97     MPI d;    /* the private key */
98     MPI u;
99     MPI t1, t2;
100     MPI n;    /* the public key */
101     MPI e;    /* the exponent */
102     MPI phi;  /* helper: (p-1)(q-1) */
103     MPI g;
104     MPI f;
105
106     /* make sure that nbits is even so that we generate p, q of equal size */
107     if ( (nbits&1) )
108       nbits++; 
109
110     n = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
111
112     p = q = NULL;
113     do {
114       /* select two (very secret) primes */
115       if (p)
116         mpi_free (p);
117       if (q)
118         mpi_free (q);
119       p = generate_secret_prime( nbits / 2 );
120       q = generate_secret_prime( nbits / 2 );
121       if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
122         mpi_swap(p,q);
123       /* calculate the modulus */
124       mpi_mul( n, p, q );
125     } while ( mpi_get_nbits(n) != nbits );
126
127     /* calculate Euler totient: phi = (p-1)(q-1) */
128     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
129     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
130     phi = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
131     g   = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB  );
132     f   = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB  );
133     mpi_sub_ui( t1, p, 1 );
134     mpi_sub_ui( t2, q, 1 );
135     mpi_mul( phi, t1, t2 );
136     mpi_gcd(g, t1, t2);
137     mpi_fdiv_q(f, phi, g);
138
139     /* find an public exponent.
140        We use 41 as this is quite fast and more secure than the
141        commonly used 17.  Benchmarking the RSA verify function
142        with a 1024 bit key yields (2001-11-08): 
143          e=17    0.54 ms
144          e=41    0.75 ms
145          e=257   0.95 ms
146          e=65537 1.80 ms
147      */
148     e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
149     mpi_set_ui( e, 41); 
150     if( !mpi_gcd(t1, e, phi) ) {
151       mpi_set_ui( e, 257); 
152       if( !mpi_gcd(t1, e, phi) ) {
153         mpi_set_ui( e, 65537); 
154         while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
155           mpi_add_ui( e, e, 2);
156       }
157     }
158
159     /* calculate the secret key d = e^1 mod phi */
160     d = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
161     mpi_invm(d, e, f );
162     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
163     u = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
164     mpi_invm(u, p, q );
165
166     if( DBG_CIPHER ) {
167         log_mpidump("  p= ", p );
168         log_mpidump("  q= ", q );
169         log_mpidump("phi= ", phi );
170         log_mpidump("  g= ", g );
171         log_mpidump("  f= ", f );
172         log_mpidump("  n= ", n );
173         log_mpidump("  e= ", e );
174         log_mpidump("  d= ", d );
175         log_mpidump("  u= ", u );
176     }
177
178     mpi_free(t1);
179     mpi_free(t2);
180     mpi_free(phi);
181     mpi_free(f);
182     mpi_free(g);
183
184     sk->n = n;
185     sk->e = e;
186     sk->p = p;
187     sk->q = q;
188     sk->d = d;
189     sk->u = u;
190
191     /* now we can test our keys (this should never fail!) */
192     test_keys( sk, nbits - 64 );
193 }
194
195
196 /****************
197  * Test wether the secret key is valid.
198  * Returns: true if this is a valid key.
199  */
200 static int
201 check_secret_key( RSA_secret_key *sk )
202 {
203     int rc;
204     MPI temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
205
206     mpi_mul(temp, sk->p, sk->q );
207     rc = mpi_cmp( temp, sk->n );
208     mpi_free(temp);
209     return !rc;
210 }
211
212
213
214 /****************
215  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
216  *
217  *      c = m^e mod n
218  *
219  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
220  */
221 static void
222 public(MPI output, MPI input, RSA_public_key *pkey )
223 {
224     if( output == input ) { /* powm doesn't like output and input the same */
225         MPI x = mpi_alloc( mpi_get_nlimbs(input)*2 );
226         mpi_powm( x, input, pkey->e, pkey->n );
227         mpi_set(output, x);
228         mpi_free(x);
229     }
230     else
231         mpi_powm( output, input, pkey->e, pkey->n );
232 }
233
234 #if 0
235 static void
236 stronger_key_check ( RSA_secret_key *skey )
237 {
238     MPI t = mpi_alloc_secure ( 0 );
239     MPI t1 = mpi_alloc_secure ( 0 );
240     MPI t2 = mpi_alloc_secure ( 0 );
241     MPI phi = mpi_alloc_secure ( 0 );
242
243     /* check that n == p * q */
244     mpi_mul( t, skey->p, skey->q);
245     if (mpi_cmp( t, skey->n) )
246         log_info ( "RSA Oops: n != p * q\n" );
247
248     /* check that p is less than q */
249     if( mpi_cmp( skey->p, skey->q ) > 0 )
250         log_info ("RSA Oops: p >= q\n");
251
252
253     /* check that e divides neither p-1 nor q-1 */
254     mpi_sub_ui(t, skey->p, 1 );
255     mpi_fdiv_r(t, t, skey->e );
256     if ( !mpi_cmp_ui( t, 0) )
257         log_info ( "RSA Oops: e divides p-1\n" );
258     mpi_sub_ui(t, skey->q, 1 );
259     mpi_fdiv_r(t, t, skey->e );
260     if ( !mpi_cmp_ui( t, 0) )
261         log_info ( "RSA Oops: e divides q-1\n" );
262
263     /* check that d is correct */
264     mpi_sub_ui( t1, skey->p, 1 );
265     mpi_sub_ui( t2, skey->q, 1 );
266     mpi_mul( phi, t1, t2 );
267     mpi_gcd(t, t1, t2);
268     mpi_fdiv_q(t, phi, t);
269     mpi_invm(t, skey->e, t );
270     if ( mpi_cmp(t, skey->d ) )
271         log_info ( "RSA Oops: d is wrong\n");
272
273     /* check for crrectness of u */
274     mpi_invm(t, skey->p, skey->q );
275     if ( mpi_cmp(t, skey->u ) )
276         log_info ( "RSA Oops: u is wrong\n");
277    
278     log_info ( "RSA secret key check finished\n");
279
280     mpi_free (t);
281     mpi_free (t1);
282     mpi_free (t2);
283     mpi_free (phi);
284 }
285 #endif
286
287
288 /****************
289  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
290  *
291  *      m = c^d mod n
292  *
293  * Or faster:
294  *
295  *      m1 = c ^ (d mod (p-1)) mod p 
296  *      m2 = c ^ (d mod (q-1)) mod q 
297  *      h = u * (m2 - m1) mod q 
298  *      m = m1 + h * p
299  *
300  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
301  */
302 static void
303 secret(MPI output, MPI input, RSA_secret_key *skey )
304 {
305 #if 0
306     mpi_powm( output, input, skey->d, skey->n );
307 #else
308     MPI m1   = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
309     MPI m2   = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
310     MPI h    = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
311
312     /* m1 = c ^ (d mod (p-1)) mod p */
313     mpi_sub_ui( h, skey->p, 1  );
314     mpi_fdiv_r( h, skey->d, h );   
315     mpi_powm( m1, input, h, skey->p );
316     /* m2 = c ^ (d mod (q-1)) mod q */
317     mpi_sub_ui( h, skey->q, 1  );
318     mpi_fdiv_r( h, skey->d, h );
319     mpi_powm( m2, input, h, skey->q );
320     /* h = u * ( m2 - m1 ) mod q */
321     mpi_sub( h, m2, m1 );
322     if ( mpi_is_neg( h ) ) 
323         mpi_add ( h, h, skey->q );
324     mpi_mulm( h, skey->u, h, skey->q ); 
325     /* m = m2 + h * p */
326     mpi_mul ( h, h, skey->p );
327     mpi_add ( output, m1, h );
328     /* ready */
329     
330     mpi_free ( h );
331     mpi_free ( m1 );
332     mpi_free ( m2 );
333 #endif
334 }
335
336
337 /*********************************************
338  **************  interface  ******************
339  *********************************************/
340
341 int
342 rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
343 {
344     RSA_secret_key sk;
345
346     if( !is_RSA(algo) )
347         return G10ERR_PUBKEY_ALGO;
348
349     generate( &sk, nbits );
350     skey[0] = sk.n;
351     skey[1] = sk.e;
352     skey[2] = sk.d;
353     skey[3] = sk.p;
354     skey[4] = sk.q;
355     skey[5] = sk.u;
356     /* make an empty list of factors */
357     if (retfactors)
358       *retfactors = m_alloc_clear( 1 * sizeof **retfactors );
359     return 0;
360 }
361
362
363 int
364 rsa_check_secret_key( int algo, MPI *skey )
365 {
366     RSA_secret_key sk;
367
368     if( !is_RSA(algo) )
369         return G10ERR_PUBKEY_ALGO;
370
371     sk.n = skey[0];
372     sk.e = skey[1];
373     sk.d = skey[2];
374     sk.p = skey[3];
375     sk.q = skey[4];
376     sk.u = skey[5];
377     if( !check_secret_key( &sk ) )
378         return G10ERR_BAD_SECKEY;
379
380     return 0;
381 }
382
383
384
385 int
386 rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
387 {
388     RSA_public_key pk;
389
390     if( algo != 1 && algo != 2 )
391         return G10ERR_PUBKEY_ALGO;
392
393     pk.n = pkey[0];
394     pk.e = pkey[1];
395     resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
396     public( resarr[0], data, &pk );
397     return 0;
398 }
399
400 int
401 rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
402 {
403     RSA_secret_key sk;
404
405     if( algo != 1 && algo != 2 )
406         return G10ERR_PUBKEY_ALGO;
407
408     sk.n = skey[0];
409     sk.e = skey[1];
410     sk.d = skey[2];
411     sk.p = skey[3];
412     sk.q = skey[4];
413     sk.u = skey[5];
414     *result = mpi_alloc_secure( mpi_get_nlimbs( sk.n ) );
415     secret( *result, data[0], &sk );
416     return 0;
417 }
418
419 int
420 rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
421 {
422     RSA_secret_key sk;
423
424     if( algo != 1 && algo != 3 )
425         return G10ERR_PUBKEY_ALGO;
426
427     sk.n = skey[0];
428     sk.e = skey[1];
429     sk.d = skey[2];
430     sk.p = skey[3];
431     sk.q = skey[4];
432     sk.u = skey[5];
433     resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
434     secret( resarr[0], data, &sk );
435
436     return 0;
437 }
438
439 int
440 rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey )
441 {
442     RSA_public_key pk;
443     MPI result;
444     int rc;
445
446     if( algo != 1 && algo != 3 )
447         return G10ERR_PUBKEY_ALGO;
448     pk.n = pkey[0];
449     pk.e = pkey[1];
450     result = mpi_alloc( (160+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB);
451     public( result, data[0], &pk );
452     rc = mpi_cmp( result, hash )? G10ERR_BAD_SIGN:0;
453     mpi_free(result);
454
455     return rc;
456 }
457
458
459 unsigned int
460 rsa_get_nbits( int algo, MPI *pkey )
461 {
462     if( !is_RSA(algo) )
463         return 0;
464     return mpi_get_nbits( pkey[0] );
465 }
466
467
468 /****************
469  * Return some information about the algorithm.  We need algo here to
470  * distinguish different flavors of the algorithm.
471  * Returns: A pointer to string describing the algorithm or NULL if
472  *          the ALGO is invalid.
473  * Usage: Bit 0 set : allows signing
474  *            1 set : allows encryption
475  */
476 const char *
477 rsa_get_info( int algo,
478               int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
479 {
480     *npkey = 2;
481     *nskey = 6;
482     *nenc = 1;
483     *nsig = 1;
484
485     switch( algo ) {
486       case 1: *r_usage = PUBKEY_USAGE_SIG | PUBKEY_USAGE_ENC; return "RSA";
487       case 2: *r_usage = PUBKEY_USAGE_ENC; return "RSA-E";
488       case 3: *r_usage = PUBKEY_USAGE_SIG; return "RSA-S";
489       default:*r_usage = 0; return NULL;
490     }
491 }