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