1
/* rsa.c - RSA function
2
* Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3
* Copyright (C) 2000, 2001 Free Software Foundation, Inc.
5
* This file is part of GnuPG.
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.
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.
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
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.
44
MPI n; /* public modulus */
45
MPI e; /* public exponent */
49
MPI u; /* inverse of p mod q. */
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 );
61
test_keys( RSA_secret_key *sk, unsigned nbits )
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 );
70
{ char *p = get_random_bits( nbits, 0, 0 );
71
mpi_set_buffer( test, p, (nbits+7)/8, 0 );
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");
89
* Generate a key pair with a key of size NBITS
90
* Returns: 2 structures filled with all needed values
93
generate( RSA_secret_key *sk, unsigned nbits )
95
MPI p, q; /* the two primes */
96
MPI d; /* the private key */
99
MPI n; /* the public key */
100
MPI e; /* the exponent */
101
MPI phi; /* helper: (p-1)(q-1) */
105
/* make sure that nbits is even so that we generate p, q of equal size */
109
n = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
113
/* select two (very secret) primes */
118
p = generate_secret_prime( nbits / 2 );
119
q = generate_secret_prime( nbits / 2 );
120
if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
122
/* calculate the modulus */
124
} while ( mpi_get_nbits(n) != nbits );
126
/* calculate Euler totient: phi = (p-1)(q-1) */
127
t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
128
t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
129
phi = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
130
g = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
131
f = mpi_alloc_secure( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
132
mpi_sub_ui( t1, p, 1 );
133
mpi_sub_ui( t2, q, 1 );
134
mpi_mul( phi, t1, t2 );
136
mpi_fdiv_q(f, phi, g);
138
/* find an public exponent.
139
We use 41 as this is quite fast and more secure than the
140
commonly used 17. Benchmarking the RSA verify function
141
with a 1024 bit key yields (2001-11-08):
147
e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
149
if( !mpi_gcd(t1, e, phi) ) {
151
if( !mpi_gcd(t1, e, phi) ) {
152
mpi_set_ui( e, 65537);
153
while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
154
mpi_add_ui( e, e, 2);
158
/* calculate the secret key d = e^1 mod phi */
159
d = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
161
/* calculate the inverse of p and q (used for chinese remainder theorem)*/
162
u = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
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 );
190
/* now we can test our keys (this should never fail!) */
191
test_keys( sk, nbits - 64 );
196
* Test wether the secret key is valid.
197
* Returns: true if this is a valid key.
200
check_secret_key( RSA_secret_key *sk )
203
MPI temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
205
mpi_mul(temp, sk->p, sk->q );
206
rc = mpi_cmp( temp, sk->n );
214
* Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
218
* Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
221
public(MPI output, MPI input, RSA_public_key *pkey )
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 );
230
mpi_powm( output, input, pkey->e, pkey->n );
235
stronger_key_check ( RSA_secret_key *skey )
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 );
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" );
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");
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" );
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 );
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");
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");
277
log_info ( "RSA secret key check finished\n");
288
* Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
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
299
* Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
302
secret(MPI output, MPI input, RSA_secret_key *skey )
305
mpi_powm( output, input, skey->d, skey->n );
307
MPI m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
308
MPI m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
309
MPI h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
311
/* m1 = c ^ (d mod (p-1)) mod p */
312
mpi_sub_ui( h, skey->p, 1 );
313
mpi_fdiv_r( h, skey->d, h );
314
mpi_powm( m1, input, h, skey->p );
315
/* m2 = c ^ (d mod (q-1)) mod q */
316
mpi_sub_ui( h, skey->q, 1 );
317
mpi_fdiv_r( h, skey->d, h );
318
mpi_powm( m2, input, h, skey->q );
319
/* h = u * ( m2 - m1 ) mod q */
320
mpi_sub( h, m2, m1 );
321
if ( mpi_is_neg( h ) )
322
mpi_add ( h, h, skey->q );
323
mpi_mulm( h, skey->u, h, skey->q );
325
mpi_mul ( h, h, skey->p );
326
mpi_add ( output, m1, h );
336
/*********************************************
337
************** interface ******************
338
*********************************************/
341
rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
346
return G10ERR_PUBKEY_ALGO;
348
generate( &sk, nbits );
355
/* make an empty list of factors */
357
*retfactors = m_alloc_clear( 1 * sizeof **retfactors );
363
rsa_check_secret_key( int algo, MPI *skey )
368
return G10ERR_PUBKEY_ALGO;
376
if( !check_secret_key( &sk ) )
377
return G10ERR_BAD_SECKEY;
385
rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
389
if( algo != 1 && algo != 2 )
390
return G10ERR_PUBKEY_ALGO;
394
resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
395
public( resarr[0], data, &pk );
400
rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
404
if( algo != 1 && algo != 2 )
405
return G10ERR_PUBKEY_ALGO;
413
*result = mpi_alloc_secure( mpi_get_nlimbs( sk.n ) );
414
secret( *result, data[0], &sk );
419
rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
423
if( algo != 1 && algo != 3 )
424
return G10ERR_PUBKEY_ALGO;
432
resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
433
secret( resarr[0], data, &sk );
439
rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey )
445
if( algo != 1 && algo != 3 )
446
return G10ERR_PUBKEY_ALGO;
449
result = mpi_alloc( (160+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB);
450
public( result, data[0], &pk );
451
rc = mpi_cmp( result, hash )? G10ERR_BAD_SIGN:0;
459
rsa_get_nbits( int algo, MPI *pkey )
463
return mpi_get_nbits( pkey[0] );
468
* Return some information about the algorithm. We need algo here to
469
* distinguish different flavors of the algorithm.
470
* Returns: A pointer to string describing the algorithm or NULL if
471
* the ALGO is invalid.
472
* Usage: Bit 0 set : allows signing
473
* 1 set : allows encryption
476
rsa_get_info( int algo,
477
int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
485
case 1: *r_usage = PUBKEY_USAGE_SIG | PUBKEY_USAGE_ENC; return "RSA";
486
case 2: *r_usage = PUBKEY_USAGE_ENC; return "RSA-E";
487
case 3: *r_usage = PUBKEY_USAGE_SIG; return "RSA-S";
488
default:*r_usage = 0; return NULL;
added
removed
cipher/rsa.c
