See ChangeLog: Fri Jul 14 19:38:23 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  * ATTENTION: This code should not be used in the United States
6  * before the U.S. Patent #4,405,829 expires on September 20, 2000!
7  ***********************************************************************
8  *
9  * This file is part of GnuPG.
10  *
11  * GnuPG is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * GnuPG is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
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( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
64     MPI out1 = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
65     MPI out2 = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
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         m_free(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 filles 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-a)(q-1) */
101     MPI g;
102     MPI f;
103
104     /* select two (very secret) primes */
105     p = generate_secret_prime( nbits / 2 );
106     q = generate_secret_prime( nbits / 2 );
107     if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
108         mpi_swap(p,q);
109     /* calculate Euler totient: phi = (p-1)(q-1) */
110     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
111     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
112     phi = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
113     g   = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB  );
114     f   = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB  );
115     mpi_sub_ui( t1, p, 1 );
116     mpi_sub_ui( t2, q, 1 );
117     mpi_mul( phi, t1, t2 );
118     mpi_gcd(g, t1, t2);
119     mpi_fdiv_q(f, phi, g);
120     /* multiply them to make the private key */
121     n = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
122     mpi_mul( n, p, q );
123     /* find a public exponent  */
124     e = mpi_alloc( (6+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
125     mpi_set_ui( e, 17); /* start with 17 */
126     while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
127         mpi_add_ui( e, e, 2);
128     /* calculate the secret key d = e^1 mod phi */
129     d = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
130     mpi_invm(d, e, f );
131     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
132     u = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
133     mpi_invm(u, p, q );
134
135     if( DBG_CIPHER ) {
136         log_mpidump("  p= ", p );
137         log_mpidump("  q= ", q );
138         log_mpidump("phi= ", phi );
139         log_mpidump("  g= ", g );
140         log_mpidump("  f= ", f );
141         log_mpidump("  n= ", n );
142         log_mpidump("  e= ", e );
143         log_mpidump("  d= ", d );
144         log_mpidump("  u= ", u );
145     }
146
147     mpi_free(t1);
148     mpi_free(t2);
149     mpi_free(phi);
150     mpi_free(f);
151     mpi_free(g);
152
153     sk->n = n;
154     sk->e = e;
155     sk->p = p;
156     sk->q = q;
157     sk->d = d;
158     sk->u = u;
159
160     /* now we can test our keys (this should never fail!) */
161     test_keys( sk, nbits - 64 );
162 }
163
164
165 /****************
166  * Test wether the secret key is valid.
167  * Returns: true if this is a valid key.
168  */
169 static int
170 check_secret_key( RSA_secret_key *sk )
171 {
172     int rc;
173     MPI temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
174
175     mpi_mul(temp, sk->p, sk->q );
176     rc = mpi_cmp( temp, sk->n );
177     mpi_free(temp);
178     return !rc;
179 }
180
181
182
183 /****************
184  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
185  *
186  *      c = m^e mod n
187  *
188  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
189  */
190 static void
191 public(MPI output, MPI input, RSA_public_key *pkey )
192 {
193     if( output == input ) { /* powm doesn't like output and input the same */
194         MPI x = mpi_alloc( mpi_get_nlimbs(input)*2 );
195         mpi_powm( x, input, pkey->e, pkey->n );
196         mpi_set(output, x);
197         mpi_free(x);
198     }
199     else
200         mpi_powm( output, input, pkey->e, pkey->n );
201 }
202
203 /****************
204  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
205  *
206  *      m = c^d mod n
207  *
208  * Where m is OUTPUT, c is INPUT and d,n are elements of PKEY.
209  *
210  * FIXME: We should better use the Chinese Remainder Theorem
211  */
212 static void
213 secret(MPI output, MPI input, RSA_secret_key *skey )
214 {
215     mpi_powm( output, input, skey->d, skey->n );
216 }
217
218
219 /*********************************************
220  **************  interface  ******************
221  *********************************************/
222
223 int
224 rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
225 {
226     RSA_secret_key sk;
227
228     if( !is_RSA(algo) )
229         return G10ERR_PUBKEY_ALGO;
230
231     generate( &sk, nbits );
232     skey[0] = sk.n;
233     skey[1] = sk.e;
234     skey[2] = sk.d;
235     skey[3] = sk.p;
236     skey[4] = sk.q;
237     skey[5] = sk.u;
238     /* make an empty list of factors */
239     *retfactors = m_alloc_clear( 1 * sizeof **retfactors );
240     return 0;
241 }
242
243
244 int
245 rsa_check_secret_key( int algo, MPI *skey )
246 {
247     RSA_secret_key sk;
248
249     if( !is_RSA(algo) )
250         return G10ERR_PUBKEY_ALGO;
251
252     sk.n = skey[0];
253     sk.e = skey[1];
254     sk.d = skey[2];
255     sk.p = skey[3];
256     sk.q = skey[4];
257     sk.u = skey[5];
258     if( !check_secret_key( &sk ) )
259         return G10ERR_BAD_SECKEY;
260
261     return 0;
262 }
263
264
265
266 int
267 rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
268 {
269     RSA_public_key pk;
270
271     if( algo != 1 && algo != 2 )
272         return G10ERR_PUBKEY_ALGO;
273
274     pk.n = pkey[0];
275     pk.e = pkey[1];
276     resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
277     public( resarr[0], data, &pk );
278     return 0;
279 }
280
281 int
282 rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
283 {
284     RSA_secret_key sk;
285
286     if( algo != 1 && algo != 2 )
287         return G10ERR_PUBKEY_ALGO;
288
289     sk.n = skey[0];
290     sk.e = skey[1];
291     sk.d = skey[2];
292     sk.p = skey[3];
293     sk.q = skey[4];
294     sk.u = skey[5];
295     *result = mpi_alloc_secure( mpi_get_nlimbs( sk.n ) );
296     secret( *result, data[0], &sk );
297     return 0;
298 }
299
300 int
301 rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
302 {
303     RSA_secret_key sk;
304
305     if( algo != 1 && algo != 3 )
306         return G10ERR_PUBKEY_ALGO;
307
308     sk.n = skey[0];
309     sk.e = skey[1];
310     sk.d = skey[2];
311     sk.p = skey[3];
312     sk.q = skey[4];
313     sk.u = skey[5];
314     resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
315     secret( resarr[0], data, &sk );
316
317     return 0;
318 }
319
320 int
321 rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey,
322            int (*cmp)(void *opaque, MPI tmp), void *opaquev )
323 {
324     RSA_public_key pk;
325     MPI result;
326     int rc;
327
328     if( algo != 1 && algo != 3 )
329         return G10ERR_PUBKEY_ALGO;
330     pk.n = pkey[0];
331     pk.e = pkey[1];
332     result = mpi_alloc( (160+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB);
333     public( result, data[0], &pk );
334     /*rc = (*cmp)( opaquev, result );*/
335     rc = mpi_cmp( result, hash )? G10ERR_BAD_SIGN:0;
336     mpi_free(result);
337
338     return rc;
339 }
340
341
342 unsigned int
343 rsa_get_nbits( int algo, MPI *pkey )
344 {
345     if( !is_RSA(algo) )
346         return 0;
347     return mpi_get_nbits( pkey[0] );
348 }
349
350
351 /****************
352  * Return some information about the algorithm.  We need algo here to
353  * distinguish different flavors of the algorithm.
354  * Returns: A pointer to string describing the algorithm or NULL if
355  *          the ALGO is invalid.
356  * Usage: Bit 0 set : allows signing
357  *            1 set : allows encryption
358  */
359 const char *
360 rsa_get_info( int algo,
361               int *npkey, int *nskey, int *nenc, int *nsig, int *usage )
362 {
363     *npkey = 2;
364     *nskey = 6;
365     *nenc = 1;
366     *nsig = 1;
367
368     switch( algo ) {
369       case 1: *usage = PUBKEY_USAGE_SIG | PUBKEY_USAGE_ENC; return "RSA";
370       case 2: *usage = PUBKEY_USAGE_ENC; return "RSA-E";
371       case 3: *usage = PUBKEY_USAGE_SIG; return "RSA-S";
372       default:*usage = 0; return NULL;
373     }
374 }
375