← Back to branch summary

~ubuntu-branches/ubuntu/precise/gnupg2/precise-updates

« back to all changes in this revision

Viewing changes to cipher/rsa.c

  • Committer: Bazaar Package Importer
  • Author(s): Andreas Mueller
  • Date: 2005-03-29 10:30:32 UTC
  • Revision ID: james.westby@ubuntu.com-20050329103032-sj42n2ain3ipx310
Tags: upstream-1.9.15
Import upstream version 1.9.15

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 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 "util.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
        m_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 filled 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-1)(q-1) */
 
102
    MPI g;
 
103
    MPI f;
 
104
 
 
105
    /* make sure that nbits is even so that we generate p, q of equal size */
 
106
    if ( (nbits&1) )
 
107
      nbits++; 
 
108
 
 
109
    n = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
 
110
 
 
111
    p = q = NULL;
 
112
    do {
 
113
      /* select two (very secret) primes */
 
114
      if (p)
 
115
        mpi_free (p);
 
116
      if (q)
 
117
        mpi_free (q);
 
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)*/
 
121
        mpi_swap(p,q);
 
122
      /* calculate the modulus */
 
123
      mpi_mul( n, p, q );
 
124
    } while ( mpi_get_nbits(n) != nbits );
 
125
 
 
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 );
 
135
    mpi_gcd(g, t1, t2);
 
136
    mpi_fdiv_q(f, phi, g);
 
137
 
 
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): 
 
142
         e=17    0.54 ms
 
143
         e=41    0.75 ms
 
144
         e=257   0.95 ms
 
145
         e=65537 1.80 ms
 
146
     */
 
147
    e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
 
148
    mpi_set_ui( e, 41); 
 
149
    if( !mpi_gcd(t1, e, phi) ) {
 
150
      mpi_set_ui( e, 257); 
 
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);
 
155
      }
 
156
    }
 
157
 
 
158
    /* calculate the secret key d = e^1 mod phi */
 
159
    d = mpi_alloc( (nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
 
160
    mpi_invm(d, e, f );
 
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 );
 
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
    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 );
 
310
 
 
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 ); 
 
324
    /* m = m2 + h * p */
 
325
    mpi_mul ( h, h, skey->p );
 
326
    mpi_add ( output, m1, h );
 
327
    /* ready */
 
328
    
 
329
    mpi_free ( h );
 
330
    mpi_free ( m1 );
 
331
    mpi_free ( m2 );
 
332
#endif
 
333
}
 
334
 
 
335
 
 
336
/*********************************************
 
337
 **************  interface  ******************
 
338
 *********************************************/
 
339
 
 
340
int
 
341
rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
 
342
{
 
343
    RSA_secret_key sk;
 
344
 
 
345
    if( !is_RSA(algo) )
 
346
        return G10ERR_PUBKEY_ALGO;
 
347
 
 
348
    generate( &sk, nbits );
 
349
    skey[0] = sk.n;
 
350
    skey[1] = sk.e;
 
351
    skey[2] = sk.d;
 
352
    skey[3] = sk.p;
 
353
    skey[4] = sk.q;
 
354
    skey[5] = sk.u;
 
355
    /* make an empty list of factors */
 
356
    if (retfactors)
 
357
      *retfactors = m_alloc_clear( 1 * sizeof **retfactors );
 
358
    return 0;
 
359
}
 
360
 
 
361
 
 
362
int
 
363
rsa_check_secret_key( int algo, MPI *skey )
 
364
{
 
365
    RSA_secret_key sk;
 
366
 
 
367
    if( !is_RSA(algo) )
 
368
        return G10ERR_PUBKEY_ALGO;
 
369
 
 
370
    sk.n = skey[0];
 
371
    sk.e = skey[1];
 
372
    sk.d = skey[2];
 
373
    sk.p = skey[3];
 
374
    sk.q = skey[4];
 
375
    sk.u = skey[5];
 
376
    if( !check_secret_key( &sk ) )
 
377
        return G10ERR_BAD_SECKEY;
 
378
 
 
379
    return 0;
 
380
}
 
381
 
 
382
 
 
383
 
 
384
int
 
385
rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
 
386
{
 
387
    RSA_public_key pk;
 
388
 
 
389
    if( algo != 1 && algo != 2 )
 
390
        return G10ERR_PUBKEY_ALGO;
 
391
 
 
392
    pk.n = pkey[0];
 
393
    pk.e = pkey[1];
 
394
    resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
 
395
    public( resarr[0], data, &pk );
 
396
    return 0;
 
397
}
 
398
 
 
399
int
 
400
rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
 
401
{
 
402
    RSA_secret_key sk;
 
403
 
 
404
    if( algo != 1 && algo != 2 )
 
405
        return G10ERR_PUBKEY_ALGO;
 
406
 
 
407
    sk.n = skey[0];
 
408
    sk.e = skey[1];
 
409
    sk.d = skey[2];
 
410
    sk.p = skey[3];
 
411
    sk.q = skey[4];
 
412
    sk.u = skey[5];
 
413
    *result = mpi_alloc_secure( mpi_get_nlimbs( sk.n ) );
 
414
    secret( *result, data[0], &sk );
 
415
    return 0;
 
416
}
 
417
 
 
418
int
 
419
rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
 
420
{
 
421
    RSA_secret_key sk;
 
422
 
 
423
    if( algo != 1 && algo != 3 )
 
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
    resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
 
433
    secret( resarr[0], data, &sk );
 
434
 
 
435
    return 0;
 
436
}
 
437
 
 
438
int
 
439
rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey )
 
440
{
 
441
    RSA_public_key pk;
 
442
    MPI result;
 
443
    int rc;
 
444
 
 
445
    if( algo != 1 && algo != 3 )
 
446
        return G10ERR_PUBKEY_ALGO;
 
447
    pk.n = pkey[0];
 
448
    pk.e = pkey[1];
 
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;
 
452
    mpi_free(result);
 
453
 
 
454
    return rc;
 
455
}
 
456
 
 
457
 
 
458
unsigned int
 
459
rsa_get_nbits( int algo, MPI *pkey )
 
460
{
 
461
    if( !is_RSA(algo) )
 
462
        return 0;
 
463
    return mpi_get_nbits( pkey[0] );
 
464
}
 
465
 
 
466
 
 
467
/****************
 
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
 
474
 */
 
475
const char *
 
476
rsa_get_info( int algo,
 
477
              int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
 
478
{
 
479
    *npkey = 2;
 
480
    *nskey = 6;
 
481
    *nenc = 1;
 
482
    *nsig = 1;
 
483
 
 
484
    switch( algo ) {
 
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;
 
489
    }
 
490
}