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