51b76404f05313a341b445863d1f605996f59939
[gnupg.git] / cipher / rsa.c
1 /* rsa.c  -  RSA function
2  *      Copyright (C) 1997, 1998, 1999, 2013 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 "mpi-internal.h"
33 #include "cipher.h"
34 #include "rsa.h"
35
36 /* Blinding is used to mitigate side-channel attacks.  You may undef
37    this to speed up the operation in case the system is secured
38    against physical and network mounted side-channel attacks.  */
39 #define USE_BLINDING 1
40
41 typedef struct {
42     MPI n;          /* modulus */
43     MPI e;          /* exponent */
44 } RSA_public_key;
45
46
47 typedef struct {
48     MPI n;          /* public modulus */
49     MPI e;          /* public exponent */
50     MPI d;          /* exponent */
51     MPI p;          /* prime  p. */
52     MPI q;          /* prime  q. */
53     MPI u;          /* inverse of p mod q. */
54 } RSA_secret_key;
55
56
57 static void test_keys( RSA_secret_key *sk, unsigned nbits );
58 static void generate( RSA_secret_key *sk, unsigned nbits );
59 static int  check_secret_key( RSA_secret_key *sk );
60 static void public(MPI output, MPI input, RSA_public_key *skey );
61 static void secret(MPI output, MPI input, RSA_secret_key *skey );
62
63
64 static void
65 test_keys( RSA_secret_key *sk, unsigned nbits )
66 {
67     RSA_public_key pk;
68     MPI test = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
69     MPI out1 = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
70     MPI out2 = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
71
72     pk.n = sk->n;
73     pk.e = sk->e;
74     {   char *p = get_random_bits( nbits, 0, 0 );
75         mpi_set_buffer( test, p, (nbits+7)/8, 0 );
76         xfree(p);
77     }
78
79     public( out1, test, &pk );
80     secret( out2, out1, sk );
81     if( mpi_cmp( test, out2 ) )
82         log_fatal("RSA operation: public, secret failed\n");
83     secret( out1, test, sk );
84     public( out2, out1, &pk );
85     if( mpi_cmp( test, out2 ) )
86         log_fatal("RSA operation: secret, public failed\n");
87     mpi_free( test );
88     mpi_free( out1 );
89     mpi_free( out2 );
90 }
91
92 /****************
93  * Generate a key pair with a key of size NBITS
94  * Returns: 2 structures filled with all needed values
95  */
96 static void
97 generate( RSA_secret_key *sk, unsigned nbits )
98 {
99     MPI p, q; /* the two primes */
100     MPI d;    /* the private key */
101     MPI u;
102     MPI t1, t2;
103     MPI n;    /* the public key */
104     MPI e;    /* the exponent */
105     MPI phi;  /* helper: (p-1)(q-1) */
106     MPI g;
107     MPI f;
108
109     /* make sure that nbits is even so that we generate p, q of equal size */
110     if ( (nbits&1) )
111       nbits++;
112
113     n = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
114
115     p = q = NULL;
116     do {
117       /* select two (very secret) primes */
118       if (p)
119         mpi_free (p);
120       if (q)
121         mpi_free (q);
122       p = generate_secret_prime( nbits / 2 );
123       q = generate_secret_prime( nbits / 2 );
124       if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
125         mpi_swap(p,q);
126       /* calculate the modulus */
127       mpi_mul( n, p, q );
128     } while ( mpi_get_nbits(n) != nbits );
129
130     /* calculate Euler totient: phi = (p-1)(q-1) */
131     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
132     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
133     phi = mpi_alloc_secure ( mpi_nlimb_hint_from_nbits (nbits) );
134     g   = mpi_alloc_secure ( mpi_nlimb_hint_from_nbits (nbits) );
135     f   = mpi_alloc_secure ( mpi_nlimb_hint_from_nbits (nbits) );
136     mpi_sub_ui( t1, p, 1 );
137     mpi_sub_ui( t2, q, 1 );
138     mpi_mul( phi, t1, t2 );
139     mpi_gcd(g, t1, t2);
140     mpi_fdiv_q(f, phi, g);
141
142     /* Find an public exponent.
143        Benchmarking the RSA verify function with a 1024 bit key yields
144        (2001-11-08):
145          e=17    0.54 ms
146          e=41    0.75 ms
147          e=257   0.95 ms
148          e=65537 1.80 ms
149
150        This code used 41 until 2006-06-28 when it was changed to use
151        65537 as the new best practice.  See FIPS-186-3.
152      */
153     e = mpi_alloc ( mpi_nlimb_hint_from_nbits (32) );
154     mpi_set_ui( e, 65537);
155     while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
156       mpi_add_ui( e, e, 2);
157
158     /* calculate the secret key d = e^1 mod phi */
159     d = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
160     mpi_invm(d, e, f );
161     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
162     u = mpi_alloc ( mpi_nlimb_hint_from_nbits (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     mpi_free(t1);
178     mpi_free(t2);
179     mpi_free(phi);
180     mpi_free(f);
181     mpi_free(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         log_info ("RSA Oops: p >= q\n");
250
251
252     /* check that e divides neither p-1 nor q-1 */
253     mpi_sub_ui(t, skey->p, 1 );
254     mpi_fdiv_r(t, t, skey->e );
255     if ( !mpi_cmp_ui( t, 0) )
256         log_info ( "RSA Oops: e divides p-1\n" );
257     mpi_sub_ui(t, skey->q, 1 );
258     mpi_fdiv_r(t, t, skey->e );
259     if ( !mpi_cmp_ui( t, 0) )
260         log_info ( "RSA Oops: e divides q-1\n" );
261
262     /* check that d is correct */
263     mpi_sub_ui( t1, skey->p, 1 );
264     mpi_sub_ui( t2, skey->q, 1 );
265     mpi_mul( phi, t1, t2 );
266     mpi_gcd(t, t1, t2);
267     mpi_fdiv_q(t, phi, t);
268     mpi_invm(t, skey->e, t );
269     if ( mpi_cmp(t, skey->d ) )
270         log_info ( "RSA Oops: d is wrong\n");
271
272     /* check for crrectness of u */
273     mpi_invm(t, skey->p, skey->q );
274     if ( mpi_cmp(t, skey->u ) )
275         log_info ( "RSA Oops: u is wrong\n");
276
277     log_info ( "RSA secret key check finished\n");
278
279     mpi_free (t);
280     mpi_free (t1);
281     mpi_free (t2);
282     mpi_free (phi);
283 }
284 #endif
285
286
287 /****************
288  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
289  *
290  *      m = c^d mod n
291  *
292  * Or faster:
293  *
294  *      m1 = c ^ (d mod (p-1)) mod p
295  *      m2 = c ^ (d mod (q-1)) mod q
296  *      h = u * (m2 - m1) mod q
297  *      m = m1 + h * p
298  *
299  * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
300  */
301 static void
302 secret(MPI output, MPI input, RSA_secret_key *skey )
303 {
304 #if 0
305     mpi_powm( output, input, skey->d, skey->n );
306 #else
307     int nlimbs = mpi_get_nlimbs (skey->n)+1;
308     MPI m1   = mpi_alloc_secure (nlimbs);
309     MPI m2   = mpi_alloc_secure (nlimbs);
310     MPI h    = mpi_alloc_secure (nlimbs);
311 # ifdef USE_BLINDING
312     MPI bdata= mpi_alloc_secure (nlimbs);
313     MPI r    = mpi_alloc_secure (nlimbs);
314 # endif /* USE_BLINDING */
315
316     /* Remove superfluous leading zeroes from INPUT.  */
317     mpi_normalize (input);
318
319 # ifdef USE_BLINDING
320     /* Blind:  bdata = (data * r^e) mod n   */
321     randomize_mpi (r, mpi_get_nbits (skey->n), 0);
322     mpi_fdiv_r (r, r, skey->n);
323     mpi_powm (bdata, r, skey->e, skey->n);
324     mpi_mulm (bdata, bdata, input, skey->n);
325     input = bdata;
326 # endif /* USE_BLINDING */
327
328     /* RSA secret operation:  */
329     MPI D_blind = mpi_alloc_secure (nlimbs);
330     MPI rr;
331     unsigned int rr_nbits;
332
333     rr_nbits = mpi_get_nbits (skey->p) / 4;
334     if (rr_nbits < 96)
335       rr_nbits = 96;
336     rr = mpi_alloc_secure ( (rr_nbits + BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
337
338     /* d_blind = (d mod (p-1)) + (p-1) * r            */
339     /* m1 = c ^ d_blind mod p */
340     randomize_mpi (rr, rr_nbits, 0);
341     mpi_set_highbit (rr, rr_nbits - 1);
342     mpi_sub_ui( h, skey->p, 1  );
343     mpi_mul ( D_blind, h, rr );
344     mpi_free ( rr );
345     mpi_fdiv_r( h, skey->d, h );
346     mpi_add ( D_blind, D_blind, h );
347     mpi_free ( h );
348     mpi_powm ( m1, input, D_blind, skey->p );
349
350     h = mpi_alloc_secure (nlimbs);
351     rr = mpi_alloc_secure ( (rr_nbits + BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
352
353     /* d_blind = (d mod (q-1)) + (q-1) * r            */
354     /* m2 = c ^ d_blind mod q */
355     randomize_mpi (rr, rr_nbits, 0);
356     mpi_set_highbit (rr, rr_nbits - 1);
357     mpi_sub_ui( h, skey->q, 1  );
358     mpi_mul ( D_blind, h, rr );
359     mpi_free ( rr );
360     mpi_fdiv_r( h, skey->d, h );
361     mpi_add ( D_blind, D_blind, h );
362     mpi_free ( h );
363     mpi_powm ( m2, input, D_blind, skey->q );
364
365     mpi_free ( D_blind );
366     h = mpi_alloc_secure (nlimbs);
367
368     /* h = u * ( m2 - m1 ) mod q */
369     mpi_sub( h, m2, m1 );
370     if ( mpi_is_neg( h ) )
371         mpi_add ( h, h, skey->q );
372     mpi_mulm( h, skey->u, h, skey->q );
373     /* m = m2 + h * p */
374     mpi_mul ( h, h, skey->p );
375     mpi_add ( output, m1, h );
376
377 # ifdef USE_BLINDING
378     mpi_free (bdata);
379     /* Unblind: output = (output * r^(-1)) mod n  */
380     mpi_invm (r, r, skey->n);
381     mpi_mulm (output, output, r, skey->n);
382     mpi_free (r);
383 # endif /* USE_BLINDING */
384
385     mpi_free ( h );
386     mpi_free ( m1 );
387     mpi_free ( m2 );
388 #endif
389 }
390
391
392 /*********************************************
393  **************  interface  ******************
394  *********************************************/
395
396 int
397 rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
398 {
399     RSA_secret_key sk;
400
401     if( !is_RSA(algo) )
402         return G10ERR_PUBKEY_ALGO;
403
404     generate( &sk, nbits );
405     skey[0] = sk.n;
406     skey[1] = sk.e;
407     skey[2] = sk.d;
408     skey[3] = sk.p;
409     skey[4] = sk.q;
410     skey[5] = sk.u;
411     /* make an empty list of factors */
412     if (retfactors)
413       *retfactors = xmalloc_clear( 1 * sizeof **retfactors );
414     return 0;
415 }
416
417
418 int
419 rsa_check_secret_key( int algo, MPI *skey )
420 {
421     RSA_secret_key sk;
422
423     if( !is_RSA(algo) )
424         return G10ERR_PUBKEY_ALGO;
425
426     sk.n = skey[0];
427     sk.e = skey[1];
428     sk.d = skey[2];
429     sk.p = skey[3];
430     sk.q = skey[4];
431     sk.u = skey[5];
432     if( !check_secret_key( &sk ) )
433         return G10ERR_BAD_SECKEY;
434
435     return 0;
436 }
437
438
439
440 int
441 rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
442 {
443     RSA_public_key pk;
444
445     if( algo != 1 && algo != 2 )
446         return G10ERR_PUBKEY_ALGO;
447
448     pk.n = pkey[0];
449     pk.e = pkey[1];
450     resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
451     public( resarr[0], data, &pk );
452     return 0;
453 }
454
455 int
456 rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
457 {
458     RSA_secret_key sk;
459     MPI input;
460
461     if( algo != 1 && algo != 2 )
462         return G10ERR_PUBKEY_ALGO;
463
464     sk.n = skey[0];
465     sk.e = skey[1];
466     sk.d = skey[2];
467     sk.p = skey[3];
468     sk.q = skey[4];
469     sk.u = skey[5];
470
471     /* Better make sure that there are no superfluous leading zeroes
472        in the input and it has not been padded using multiples of N.
473        This mitigates side-channel attacks (CVE-2013-4576).  */
474     input = mpi_alloc (0);
475     mpi_normalize (data[0]);
476     mpi_fdiv_r (input, data[0], sk.n);
477     *result = mpi_alloc_secure (mpi_get_nlimbs (sk.n));
478     secret (*result, input, &sk);
479     mpi_free (input);
480     return 0;
481 }
482
483 int
484 rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
485 {
486     RSA_secret_key sk;
487     RSA_public_key pk;
488     MPI cres;
489     int rc;
490
491     if( algo != 1 && algo != 3 )
492         return G10ERR_PUBKEY_ALGO;
493
494     sk.n = skey[0];
495     sk.e = skey[1];
496     sk.d = skey[2];
497     sk.p = skey[3];
498     sk.q = skey[4];
499     sk.u = skey[5];
500     resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
501     secret( resarr[0], data, &sk );
502
503     /* Check for a failure in secret().  */
504     cres = mpi_alloc ( mpi_nlimb_hint_from_nbits (160) );
505     pk.n = sk.n;
506     pk.e = sk.e;
507     public (cres, resarr[0], &pk);
508     rc = mpi_cmp (cres, data)? G10ERR_BAD_SIGN : 0;
509     mpi_free (cres);
510
511     return rc;
512 }
513
514 int
515 rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey )
516 {
517     RSA_public_key pk;
518     MPI result;
519     int rc;
520
521     if( algo != 1 && algo != 3 )
522         return G10ERR_PUBKEY_ALGO;
523     pk.n = pkey[0];
524     pk.e = pkey[1];
525     result = mpi_alloc ( mpi_nlimb_hint_from_nbits (160) );
526     public( result, data[0], &pk );
527     rc = mpi_cmp( result, hash )? G10ERR_BAD_SIGN:0;
528     mpi_free(result);
529
530     return rc;
531 }
532
533
534 unsigned int
535 rsa_get_nbits( int algo, MPI *pkey )
536 {
537     if( !is_RSA(algo) )
538         return 0;
539     return mpi_get_nbits( pkey[0] );
540 }
541
542
543 /****************
544  * Return some information about the algorithm.  We need algo here to
545  * distinguish different flavors of the algorithm.
546  * Returns: A pointer to string describing the algorithm or NULL if
547  *          the ALGO is invalid.
548  * Usage: Bit 0 set : allows signing
549  *            1 set : allows encryption
550  */
551 const char *
552 rsa_get_info( int algo,
553               int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
554 {
555     *npkey = 2;
556     *nskey = 6;
557     *nenc = 1;
558     *nsig = 1;
559
560     switch( algo ) {
561       case 1: *r_usage = PUBKEY_USAGE_SIG | PUBKEY_USAGE_ENC; return "RSA";
562       case 2: *r_usage = PUBKEY_USAGE_ENC; return "RSA-E";
563       case 3: *r_usage = PUBKEY_USAGE_SIG; return "RSA-S";
564       default:*r_usage = 0; return NULL;
565     }
566 }