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