1
/* rsa.c - RSA implementation
2
* Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3
* Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc.
5
* This file is part of Libgcrypt.
7
* Libgcrypt is free software; you can redistribute it and/or modify
8
* it under the terms of the GNU Lesser General Public License as
9
* published by the Free Software Foundation; either version 2.1 of
10
* the License, or (at your option) any later version.
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 Lesser General Public License for more details.
17
* You should have received a copy of the GNU Lesser General Public
18
* License along with this program; if not, see <http://www.gnu.org/licenses/>.
21
/* This code uses an algorithm protected by U.S. Patent #4,405,829
22
which expired on September 20, 2000. The patent holder placed that
23
patent into the public domain on Sep 6th, 2000.
39
gcry_mpi_t n; /* modulus */
40
gcry_mpi_t e; /* exponent */
46
gcry_mpi_t n; /* public modulus */
47
gcry_mpi_t e; /* public exponent */
48
gcry_mpi_t d; /* exponent */
49
gcry_mpi_t p; /* prime p. */
50
gcry_mpi_t q; /* prime q. */
51
gcry_mpi_t u; /* inverse of p mod q. */
55
/* A sample 1024 bit RSA key used for the selftests. */
56
static const char sample_secret_key[] =
59
" (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
60
" 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
61
" ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
62
" 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
64
" (d #046129f2489d71579be0a75fe029bd6cdb574ebf57ea8a5b0fda942cab943b11"
65
" 7d7bb95e5d28875e0f9fc5fcc06a72f6d502464dabded78ef6b716177b83d5bd"
66
" c543dc5d3fed932e59f5897e92e6f58a0f33424106a3b6fa2cbf877510e4ac21"
67
" c3ee47851e97d12996222ac3566d4ccb0b83d164074abf7de655fc2446da1781#)"
68
" (p #00e861b700e17e8afe6837e7512e35b6ca11d0ae47d8b85161c67baf64377213"
69
" fe52d772f2035b3ca830af41d8a4120e1c1c70d12cc22f00d28d31dd48a8d424f1#)"
70
" (q #00f7a7ca5367c661f8e62df34f0d05c10c88e5492348dd7bddc942c9a8f369f9"
71
" 35a07785d2db805215ed786e4285df1658eed3ce84f469b81b50d358407b4ad361#)"
72
" (u #304559a9ead56d2309d203811a641bb1a09626bc8eb36fffa23c968ec5bd891e"
73
" ebbafc73ae666e01ba7c8990bae06cc2bbe10b75e69fcacb353a6473079d8e9b#)))";
74
/* A sample 1024 bit RSA key used for the selftests (public only). */
75
static const char sample_public_key[] =
78
" (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
79
" 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
80
" ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
81
" 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
87
static int test_keys (RSA_secret_key *sk, unsigned nbits);
88
static int check_secret_key (RSA_secret_key *sk);
89
static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
90
static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
93
/* Check that a freshly generated key actually works. Returns 0 on success. */
95
test_keys (RSA_secret_key *sk, unsigned int nbits)
97
int result = -1; /* Default to failure. */
99
gcry_mpi_t plaintext = gcry_mpi_new (nbits);
100
gcry_mpi_t ciphertext = gcry_mpi_new (nbits);
101
gcry_mpi_t decr_plaintext = gcry_mpi_new (nbits);
102
gcry_mpi_t signature = gcry_mpi_new (nbits);
104
/* Put the relevant parameters into a public key structure. */
108
/* Create a random plaintext. */
109
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
111
/* Encrypt using the public key. */
112
public (ciphertext, plaintext, &pk);
114
/* Check that the cipher text does not match the plaintext. */
115
if (!gcry_mpi_cmp (ciphertext, plaintext))
116
goto leave; /* Ciphertext is identical to the plaintext. */
118
/* Decrypt using the secret key. */
119
secret (decr_plaintext, ciphertext, sk);
121
/* Check that the decrypted plaintext matches the original plaintext. */
122
if (gcry_mpi_cmp (decr_plaintext, plaintext))
123
goto leave; /* Plaintext does not match. */
125
/* Create another random plaintext as data for signature checking. */
126
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
128
/* Use the RSA secret function to create a signature of the plaintext. */
129
secret (signature, plaintext, sk);
131
/* Use the RSA public function to verify this signature. */
132
public (decr_plaintext, signature, &pk);
133
if (gcry_mpi_cmp (decr_plaintext, plaintext))
134
goto leave; /* Signature does not match. */
136
/* Modify the signature and check that the signing fails. */
137
gcry_mpi_add_ui (signature, signature, 1);
138
public (decr_plaintext, signature, &pk);
139
if (!gcry_mpi_cmp (decr_plaintext, plaintext))
140
goto leave; /* Signature matches but should not. */
142
result = 0; /* All tests succeeded. */
145
gcry_mpi_release (signature);
146
gcry_mpi_release (decr_plaintext);
147
gcry_mpi_release (ciphertext);
148
gcry_mpi_release (plaintext);
153
/* Callback used by the prime generation to test whether the exponent
154
is suitable. Returns 0 if the test has been passed. */
156
check_exponent (void *arg, gcry_mpi_t a)
162
mpi_sub_ui (a, a, 1);
163
tmp = _gcry_mpi_alloc_like (a);
164
result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */
165
gcry_mpi_release (tmp);
166
mpi_add_ui (a, a, 1);
171
* Generate a key pair with a key of size NBITS.
172
* USE_E = 0 let Libcgrypt decide what exponent to use.
173
* = 1 request the use of a "secure" exponent; this is required by some
174
* specification to be 65537.
175
* > 2 Use this public exponent. If the given exponent
176
* is not odd one is internally added to it.
177
* TRANSIENT_KEY: If true, generate the primes using the standard RNG.
178
* Returns: 2 structures filled with all needed values
180
static gpg_err_code_t
181
generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
184
gcry_mpi_t p, q; /* the two primes */
185
gcry_mpi_t d; /* the private key */
188
gcry_mpi_t n; /* the public key */
189
gcry_mpi_t e; /* the exponent */
190
gcry_mpi_t phi; /* helper: (p-1)(q-1) */
193
gcry_random_level_t random_level;
198
return GPG_ERR_INV_VALUE;
200
return GPG_ERR_INV_VALUE;
203
/* The random quality depends on the transient_key flag. */
204
random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
206
/* Make sure that nbits is even so that we generate p, q of equal size. */
210
if (use_e == 1) /* Alias for a secure value */
211
use_e = 65537; /* as demanded by Sphinx. */
214
In general we use 41 as this is quite fast and more secure than the
215
commonly used 17. Benchmarking the RSA verify function
216
with a 1024 bit key yields (2001-11-08):
222
e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
224
mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */
227
use_e |= 1; /* make sure this is odd */
228
mpi_set_ui (e, use_e);
231
n = gcry_mpi_new (nbits);
236
/* select two (very secret) primes */
238
gcry_mpi_release (p);
240
gcry_mpi_release (q);
242
{ /* Do an extra test to ensure that the given exponent is
244
p = _gcry_generate_secret_prime (nbits/2, random_level,
246
q = _gcry_generate_secret_prime (nbits/2, random_level,
250
{ /* We check the exponent later. */
251
p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
252
q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
254
if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
256
/* calculate the modulus */
259
while ( mpi_get_nbits(n) != nbits );
261
/* calculate Euler totient: phi = (p-1)(q-1) */
262
t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
263
t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
264
phi = gcry_mpi_snew ( nbits );
265
g = gcry_mpi_snew ( nbits );
266
f = gcry_mpi_snew ( nbits );
267
mpi_sub_ui( t1, p, 1 );
268
mpi_sub_ui( t2, q, 1 );
269
mpi_mul( phi, t1, t2 );
270
gcry_mpi_gcd(g, t1, t2);
271
mpi_fdiv_q(f, phi, g);
273
while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
276
BUG (); /* The prime generator already made sure that we
277
never can get to here. */
278
mpi_add_ui (e, e, 2);
281
/* calculate the secret key d = e^1 mod phi */
282
d = gcry_mpi_snew ( nbits );
284
/* calculate the inverse of p and q (used for chinese remainder theorem)*/
285
u = gcry_mpi_snew ( nbits );
290
log_mpidump(" p= ", p );
291
log_mpidump(" q= ", q );
292
log_mpidump("phi= ", phi );
293
log_mpidump(" g= ", g );
294
log_mpidump(" f= ", f );
295
log_mpidump(" n= ", n );
296
log_mpidump(" e= ", e );
297
log_mpidump(" d= ", d );
298
log_mpidump(" u= ", u );
301
gcry_mpi_release (t1);
302
gcry_mpi_release (t2);
303
gcry_mpi_release (phi);
304
gcry_mpi_release (f);
305
gcry_mpi_release (g);
314
/* Now we can test our keys. */
315
if (test_keys (sk, nbits - 64))
317
gcry_mpi_release (sk->n); sk->n = NULL;
318
gcry_mpi_release (sk->e); sk->e = NULL;
319
gcry_mpi_release (sk->p); sk->p = NULL;
320
gcry_mpi_release (sk->q); sk->q = NULL;
321
gcry_mpi_release (sk->d); sk->d = NULL;
322
gcry_mpi_release (sk->u); sk->u = NULL;
323
fips_signal_error ("self-test after key generation failed");
324
return GPG_ERR_SELFTEST_FAILED;
331
/* Helper for generate_x931. */
333
gen_x931_parm_xp (unsigned int nbits)
337
xp = gcry_mpi_snew (nbits);
338
gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
340
/* The requirement for Xp is:
342
sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
344
We set the two high order bits to 1 to satisfy the lower bound.
345
By using mpi_set_highbit we make sure that the upper bound is
346
satisfied as well. */
347
mpi_set_highbit (xp, nbits-1);
348
mpi_set_bit (xp, nbits-2);
349
gcry_assert ( mpi_get_nbits (xp) == nbits );
355
/* Helper for generate_x931. */
357
gen_x931_parm_xi (void)
361
xi = gcry_mpi_snew (101);
362
gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM);
363
mpi_set_highbit (xi, 100);
364
gcry_assert ( mpi_get_nbits (xi) == 101 );
371
/* Variant of the standard key generation code using the algorithm
372
from X9.31. Using this algorithm has the advantage that the
373
generation can be made deterministic which is required for CAVS
375
static gpg_err_code_t
376
generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
377
gcry_sexp_t deriveparms, int *swapped)
379
gcry_mpi_t p, q; /* The two primes. */
380
gcry_mpi_t e; /* The public exponent. */
381
gcry_mpi_t n; /* The public key. */
382
gcry_mpi_t d; /* The private key */
383
gcry_mpi_t u; /* The inverse of p and q. */
384
gcry_mpi_t pm1; /* p - 1 */
385
gcry_mpi_t qm1; /* q - 1 */
386
gcry_mpi_t phi; /* Euler totient. */
387
gcry_mpi_t f, g; /* Helper. */
391
if (e_value == 1) /* Alias for a secure value. */
394
/* Point 1 of section 4.1: k = 1024 + 256s with S >= 0 */
395
if (nbits < 1024 || (nbits % 256))
396
return GPG_ERR_INV_VALUE;
398
/* Point 2: 2 <= bitlength(e) < 2^{k-2}
399
Note that we do not need to check the upper bound because we use
400
an unsigned long for E and thus there is no way for E to reach
403
return GPG_ERR_INV_VALUE;
405
/* Our implementaion requires E to be odd. */
407
return GPG_ERR_INV_VALUE;
409
/* Point 3: e > 0 or e 0 if it is to be randomly generated.
410
We support only a fixed E and thus there is no need for an extra test. */
413
/* Compute or extract the derive parameters. */
415
gcry_mpi_t xp1 = NULL;
416
gcry_mpi_t xp2 = NULL;
417
gcry_mpi_t xp = NULL;
418
gcry_mpi_t xq1 = NULL;
419
gcry_mpi_t xq2 = NULL;
420
gcry_mpi_t xq = NULL;
425
/* Not given: Generate them. */
426
xp = gen_x931_parm_xp (nbits/2);
427
/* Make sure that |xp - xq| > 2^{nbits - 100} holds. */
428
tmpval = gcry_mpi_snew (nbits/2);
431
gcry_mpi_release (xq);
432
xq = gen_x931_parm_xp (nbits/2);
433
mpi_sub (tmpval, xp, xq);
435
while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
436
gcry_mpi_release (tmpval);
438
xp1 = gen_x931_parm_xi ();
439
xp2 = gen_x931_parm_xi ();
440
xq1 = gen_x931_parm_xi ();
441
xq2 = gen_x931_parm_xi ();
446
/* Parameters to derive the key are given. */
447
struct { const char *name; gcry_mpi_t *value; } tbl[] = {
459
for (idx=0; tbl[idx].name; idx++)
461
oneparm = gcry_sexp_find_token (deriveparms, tbl[idx].name, 0);
464
*tbl[idx].value = gcry_sexp_nth_mpi (oneparm, 1,
466
gcry_sexp_release (oneparm);
469
for (idx=0; tbl[idx].name; idx++)
470
if (!*tbl[idx].value)
474
/* At least one parameter is missing. */
475
for (idx=0; tbl[idx].name; idx++)
476
gcry_mpi_release (*tbl[idx].value);
477
return GPG_ERR_MISSING_VALUE;
481
e = mpi_alloc_set_ui (e_value);
483
/* Find two prime numbers. */
484
p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL);
485
q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL);
486
gcry_mpi_release (xp); xp = NULL;
487
gcry_mpi_release (xp1); xp1 = NULL;
488
gcry_mpi_release (xp2); xp2 = NULL;
489
gcry_mpi_release (xq); xq = NULL;
490
gcry_mpi_release (xq1); xq1 = NULL;
491
gcry_mpi_release (xq2); xq2 = NULL;
494
gcry_mpi_release (p);
495
gcry_mpi_release (q);
496
gcry_mpi_release (e);
497
return GPG_ERR_NO_PRIME;
502
/* Compute the public modulus. We make sure that p is smaller than
503
q to allow the use of the CRT. */
504
if (mpi_cmp (p, q) > 0 )
509
n = gcry_mpi_new (nbits);
512
/* Compute the Euler totient: phi = (p-1)(q-1) */
513
pm1 = gcry_mpi_snew (nbits/2);
514
qm1 = gcry_mpi_snew (nbits/2);
515
phi = gcry_mpi_snew (nbits);
516
mpi_sub_ui (pm1, p, 1);
517
mpi_sub_ui (qm1, q, 1);
518
mpi_mul (phi, pm1, qm1);
520
g = gcry_mpi_snew (nbits);
521
gcry_assert (gcry_mpi_gcd (g, e, phi));
523
/* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
524
gcry_mpi_gcd (g, pm1, qm1);
526
gcry_mpi_release (qm1); qm1 = NULL;
527
mpi_fdiv_q (f, phi, g);
528
gcry_mpi_release (phi); phi = NULL;
530
/* Compute the secret key: d = e^{-1} mod lcm(p-1,q-1) */
533
/* Compute the inverse of p and q. */
540
log_debug ("p and q are swapped\n");
541
log_mpidump(" p", p );
542
log_mpidump(" q", q );
543
log_mpidump(" n", n );
544
log_mpidump(" e", e );
545
log_mpidump(" d", d );
546
log_mpidump(" u", u );
557
/* Now we can test our keys. */
558
if (test_keys (sk, nbits - 64))
560
gcry_mpi_release (sk->n); sk->n = NULL;
561
gcry_mpi_release (sk->e); sk->e = NULL;
562
gcry_mpi_release (sk->p); sk->p = NULL;
563
gcry_mpi_release (sk->q); sk->q = NULL;
564
gcry_mpi_release (sk->d); sk->d = NULL;
565
gcry_mpi_release (sk->u); sk->u = NULL;
566
fips_signal_error ("self-test after key generation failed");
567
return GPG_ERR_SELFTEST_FAILED;
575
* Test wether the secret key is valid.
576
* Returns: true if this is a valid key.
579
check_secret_key( RSA_secret_key *sk )
582
gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
584
mpi_mul(temp, sk->p, sk->q );
585
rc = mpi_cmp( temp, sk->n );
593
* Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
597
* Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
600
public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
602
if( output == input ) /* powm doesn't like output and input the same */
604
gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
605
mpi_powm( x, input, pkey->e, pkey->n );
610
mpi_powm( output, input, pkey->e, pkey->n );
615
stronger_key_check ( RSA_secret_key *skey )
617
gcry_mpi_t t = mpi_alloc_secure ( 0 );
618
gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
619
gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
620
gcry_mpi_t phi = mpi_alloc_secure ( 0 );
622
/* check that n == p * q */
623
mpi_mul( t, skey->p, skey->q);
624
if (mpi_cmp( t, skey->n) )
625
log_info ( "RSA Oops: n != p * q\n" );
627
/* check that p is less than q */
628
if( mpi_cmp( skey->p, skey->q ) > 0 )
630
log_info ("RSA Oops: p >= q - fixed\n");
631
_gcry_mpi_swap ( skey->p, skey->q);
634
/* check that e divides neither p-1 nor q-1 */
635
mpi_sub_ui(t, skey->p, 1 );
636
mpi_fdiv_r(t, t, skey->e );
637
if ( !mpi_cmp_ui( t, 0) )
638
log_info ( "RSA Oops: e divides p-1\n" );
639
mpi_sub_ui(t, skey->q, 1 );
640
mpi_fdiv_r(t, t, skey->e );
641
if ( !mpi_cmp_ui( t, 0) )
642
log_info ( "RSA Oops: e divides q-1\n" );
644
/* check that d is correct */
645
mpi_sub_ui( t1, skey->p, 1 );
646
mpi_sub_ui( t2, skey->q, 1 );
647
mpi_mul( phi, t1, t2 );
648
gcry_mpi_gcd(t, t1, t2);
649
mpi_fdiv_q(t, phi, t);
650
mpi_invm(t, skey->e, t );
651
if ( mpi_cmp(t, skey->d ) )
653
log_info ( "RSA Oops: d is wrong - fixed\n");
654
mpi_set (skey->d, t);
655
_gcry_log_mpidump (" fixed d", skey->d);
658
/* check for correctness of u */
659
mpi_invm(t, skey->p, skey->q );
660
if ( mpi_cmp(t, skey->u ) )
662
log_info ( "RSA Oops: u is wrong - fixed\n");
663
mpi_set (skey->u, t);
664
_gcry_log_mpidump (" fixed u", skey->u);
667
log_info ( "RSA secret key check finished\n");
679
* Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
685
* m1 = c ^ (d mod (p-1)) mod p
686
* m2 = c ^ (d mod (q-1)) mod q
687
* h = u * (m2 - m1) mod q
690
* Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
693
secret(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
695
if (!skey->p || !skey->q || !skey->u)
697
mpi_powm (output, input, skey->d, skey->n);
701
gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
702
gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
703
gcry_mpi_t h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
705
/* m1 = c ^ (d mod (p-1)) mod p */
706
mpi_sub_ui( h, skey->p, 1 );
707
mpi_fdiv_r( h, skey->d, h );
708
mpi_powm( m1, input, h, skey->p );
709
/* m2 = c ^ (d mod (q-1)) mod q */
710
mpi_sub_ui( h, skey->q, 1 );
711
mpi_fdiv_r( h, skey->d, h );
712
mpi_powm( m2, input, h, skey->q );
713
/* h = u * ( m2 - m1 ) mod q */
714
mpi_sub( h, m2, m1 );
715
if ( mpi_is_neg( h ) )
716
mpi_add ( h, h, skey->q );
717
mpi_mulm( h, skey->u, h, skey->q );
719
mpi_mul ( h, h, skey->p );
720
mpi_add ( output, m1, h );
730
/* Perform RSA blinding. */
732
rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n)
740
a = gcry_mpi_snew (gcry_mpi_get_nbits (n));
741
y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
743
/* Now we calculate: y = (x * r^e) mod n, where r is the random
744
number, e is the public exponent, x is the non-blinded data and n
745
is the RSA modulus. */
746
gcry_mpi_powm (a, r, e, n);
747
gcry_mpi_mulm (y, a, x, n);
749
gcry_mpi_release (a);
754
/* Undo RSA blinding. */
756
rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n)
760
y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
762
/* Here we calculate: y = (x * r^-1) mod n, where x is the blinded
763
decrypted data, ri is the modular multiplicative inverse of r and
764
n is the RSA modulus. */
766
gcry_mpi_mulm (y, ri, x, n);
771
/*********************************************
772
************** interface ******************
773
*********************************************/
775
static gcry_err_code_t
776
rsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
777
const gcry_sexp_t genparms,
778
gcry_mpi_t *skey, gcry_mpi_t **retfactors,
779
gcry_sexp_t *r_extrainfo)
783
gcry_sexp_t deriveparms;
784
int transient_key = 0;
790
*retfactors = NULL; /* We don't return them. */
792
deriveparms = (genparms?
793
gcry_sexp_find_token (genparms, "derive-parms", 0) : NULL);
796
/* Parse the optional "use-x931" flag. */
797
l1 = gcry_sexp_find_token (genparms, "use-x931", 0);
801
gcry_sexp_release (l1);
805
if (deriveparms || use_x931 || fips_mode ())
808
ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
809
gcry_sexp_release (deriveparms);
810
if (!ec && r_extrainfo && swapped)
812
ec = gcry_sexp_new (r_extrainfo,
813
"(misc-key-info(p-q-swapped))", 0, 1);
816
gcry_mpi_release (sk.n); sk.n = NULL;
817
gcry_mpi_release (sk.e); sk.e = NULL;
818
gcry_mpi_release (sk.p); sk.p = NULL;
819
gcry_mpi_release (sk.q); sk.q = NULL;
820
gcry_mpi_release (sk.d); sk.d = NULL;
821
gcry_mpi_release (sk.u); sk.u = NULL;
827
/* Parse the optional "transient-key" flag. */
828
l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
832
gcry_sexp_release (l1);
835
ec = generate_std (&sk, nbits, evalue, transient_key);
852
static gcry_err_code_t
853
rsa_generate (int algo, unsigned int nbits, unsigned long evalue,
854
gcry_mpi_t *skey, gcry_mpi_t **retfactors)
856
return rsa_generate_ext (algo, nbits, evalue, NULL, skey, retfactors, NULL);
860
static gcry_err_code_t
861
rsa_check_secret_key (int algo, gcry_mpi_t *skey)
863
gcry_err_code_t err = GPG_ERR_NO_ERROR;
875
if (!sk.p || !sk.q || !sk.u)
876
err = GPG_ERR_NO_OBJ; /* To check the key we need the optional
878
else if (!check_secret_key (&sk))
879
err = GPG_ERR_PUBKEY_ALGO;
885
static gcry_err_code_t
886
rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data,
887
gcry_mpi_t *pkey, int flags)
896
resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n));
897
public (resarr[0], data, &pk);
899
return GPG_ERR_NO_ERROR;
903
static gcry_err_code_t
904
rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
905
gcry_mpi_t *skey, int flags)
908
gcry_mpi_t r = MPI_NULL; /* Random number needed for blinding. */
909
gcry_mpi_t ri = MPI_NULL; /* Modular multiplicative inverse of
911
gcry_mpi_t x = MPI_NULL; /* Data to decrypt. */
912
gcry_mpi_t y; /* Result. */
916
/* Extract private key. */
920
sk.p = skey[3]; /* Optional. */
921
sk.q = skey[4]; /* Optional. */
922
sk.u = skey[5]; /* Optional. */
924
y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
926
/* We use blinding by default to mitigate timing attacks which can
927
be practically mounted over the network as shown by Brumley and
929
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
931
/* Initialize blinding. */
933
/* First, we need a random number r between 0 and n - 1, which
934
is relatively prime to n (i.e. it is neither p nor q). The
935
random number needs to be only unpredictable, thus we employ
936
the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
937
gcry_mpi_randomize. */
938
r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
939
ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
941
gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n), GCRY_WEAK_RANDOM);
942
gcry_mpi_mod (r, r, sk.n);
944
/* Calculate inverse of r. It practically impossible that the
945
follwing test fails, thus we do not add code to release
946
allocated resources. */
947
if (!gcry_mpi_invm (ri, r, sk.n))
948
return GPG_ERR_INTERNAL;
951
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
952
x = rsa_blind (data[0], r, sk.e, sk.n);
956
/* Do the encryption. */
959
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
962
gcry_mpi_t a = gcry_mpi_copy (y);
964
gcry_mpi_release (y);
965
y = rsa_unblind (a, ri, sk.n);
967
gcry_mpi_release (a);
970
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
972
/* Deallocate resources needed for blinding. */
973
gcry_mpi_release (x);
974
gcry_mpi_release (r);
975
gcry_mpi_release (ri);
978
/* Copy out result. */
981
return GPG_ERR_NO_ERROR;
985
static gcry_err_code_t
986
rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
998
resarr[0] = mpi_alloc( mpi_get_nlimbs (sk.n));
999
secret (resarr[0], data, &sk);
1001
return GPG_ERR_NO_ERROR;
1005
static gcry_err_code_t
1006
rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1007
int (*cmp) (void *opaque, gcry_mpi_t tmp),
1020
result = gcry_mpi_new ( 160 );
1021
public( result, data[0], &pk );
1022
#ifdef IS_DEVELOPMENT_VERSION
1025
log_mpidump ("rsa verify result:", result );
1026
log_mpidump (" hash:", hash );
1028
#endif /*IS_DEVELOPMENT_VERSION*/
1029
/*rc = (*cmp)( opaquev, result );*/
1030
rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
1031
gcry_mpi_release (result);
1038
rsa_get_nbits (int algo, gcry_mpi_t *pkey)
1042
return mpi_get_nbits (pkey[0]);
1046
/* Compute a keygrip. MD is the hash context which we are going to
1047
update. KEYPARAM is an S-expression with the key parameters, this
1048
is usually a public key but may also be a secret key. An example
1049
of such an S-expression is:
1055
PKCS-15 says that for RSA only the modulus should be hashed -
1056
however, it is not clear wether this is meant to use the raw bytes
1057
(assuming this is an unsigned integer) or whether the DER required
1058
0 should be prefixed. We hash the raw bytes. */
1059
static gpg_err_code_t
1060
compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1066
l1 = gcry_sexp_find_token (keyparam, "n", 1);
1068
return GPG_ERR_NO_OBJ;
1070
data = gcry_sexp_nth_data (l1, 1, &datalen);
1073
gcry_sexp_release (l1);
1074
return GPG_ERR_NO_OBJ;
1077
gcry_md_write (md, data, datalen);
1078
gcry_sexp_release (l1);
1091
selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1093
static const char sample_data[] =
1094
"(data (flags pkcs1)"
1095
" (hash sha1 #11223344556677889900aabbccddeeff10203040#))";
1096
static const char sample_data_bad[] =
1097
"(data (flags pkcs1)"
1098
" (hash sha1 #11223344556677889900aabbccddeeff80203040#))";
1100
const char *errtxt = NULL;
1102
gcry_sexp_t data = NULL;
1103
gcry_sexp_t data_bad = NULL;
1104
gcry_sexp_t sig = NULL;
1106
err = gcry_sexp_sscan (&data, NULL,
1107
sample_data, strlen (sample_data));
1109
err = gcry_sexp_sscan (&data_bad, NULL,
1110
sample_data_bad, strlen (sample_data_bad));
1113
errtxt = "converting data failed";
1117
err = gcry_pk_sign (&sig, data, skey);
1120
errtxt = "signing failed";
1123
err = gcry_pk_verify (sig, data, pkey);
1126
errtxt = "verify failed";
1129
err = gcry_pk_verify (sig, data_bad, pkey);
1130
if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1132
errtxt = "bad signature not detected";
1138
gcry_sexp_release (sig);
1139
gcry_sexp_release (data_bad);
1140
gcry_sexp_release (data);
1146
/* Given an S-expression ENCR_DATA of the form:
1152
as returned by gcry_pk_decrypt, return the the A-VALUE. On error,
1155
extract_a_from_sexp (gcry_sexp_t encr_data)
1157
gcry_sexp_t l1, l2, l3;
1160
l1 = gcry_sexp_find_token (encr_data, "enc-val", 0);
1163
l2 = gcry_sexp_find_token (l1, "rsa", 0);
1164
gcry_sexp_release (l1);
1167
l3 = gcry_sexp_find_token (l2, "a", 0);
1168
gcry_sexp_release (l2);
1171
a_value = gcry_sexp_nth_mpi (l3, 1, 0);
1172
gcry_sexp_release (l3);
1179
selftest_encr_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1181
const char *errtxt = NULL;
1183
const unsigned int nbits = 1000; /* Encrypt 1000 random bits. */
1184
gcry_mpi_t plaintext = NULL;
1185
gcry_sexp_t plain = NULL;
1186
gcry_sexp_t encr = NULL;
1187
gcry_mpi_t ciphertext = NULL;
1188
gcry_sexp_t decr = NULL;
1189
gcry_mpi_t decr_plaintext = NULL;
1190
gcry_sexp_t tmplist = NULL;
1192
/* Create plaintext. The plaintext is actually a big integer number. */
1193
plaintext = gcry_mpi_new (nbits);
1194
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
1196
/* Put the plaintext into an S-expression. */
1197
err = gcry_sexp_build (&plain, NULL,
1198
"(data (flags raw) (value %m))", plaintext);
1201
errtxt = "converting data failed";
1206
err = gcry_pk_encrypt (&encr, plain, pkey);
1209
errtxt = "encrypt failed";
1213
/* Extraxt the ciphertext from the returned S-expression. */
1214
/*gcry_sexp_dump (encr);*/
1215
ciphertext = extract_a_from_sexp (encr);
1218
errtxt = "gcry_pk_decrypt returned garbage";
1222
/* Check that the ciphertext does no match the plaintext. */
1223
/* _gcry_log_mpidump ("plaintext", plaintext); */
1224
/* _gcry_log_mpidump ("ciphertxt", ciphertext); */
1225
if (!gcry_mpi_cmp (plaintext, ciphertext))
1227
errtxt = "ciphertext matches plaintext";
1232
err = gcry_pk_decrypt (&decr, encr, skey);
1235
errtxt = "decrypt failed";
1239
/* Extract the decrypted data from the S-expression. Note that the
1240
output of gcry_pk_decrypt depends on whether a flags lists occurs
1241
in its input data. Because we passed the output of
1242
gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
1243
won't be there as of today. To be prepared for future changes we
1244
take care of it anyway. */
1245
tmplist = gcry_sexp_find_token (decr, "value", 0);
1247
decr_plaintext = gcry_sexp_nth_mpi (tmplist, 1, GCRYMPI_FMT_USG);
1249
decr_plaintext = gcry_sexp_nth_mpi (decr, 0, GCRYMPI_FMT_USG);
1250
if (!decr_plaintext)
1252
errtxt = "decrypt returned no plaintext";
1256
/* Check that the decrypted plaintext matches the original plaintext. */
1257
if (gcry_mpi_cmp (plaintext, decr_plaintext))
1259
errtxt = "mismatch";
1264
gcry_sexp_release (tmplist);
1265
gcry_mpi_release (decr_plaintext);
1266
gcry_sexp_release (decr);
1267
gcry_mpi_release (ciphertext);
1268
gcry_sexp_release (encr);
1269
gcry_sexp_release (plain);
1270
gcry_mpi_release (plaintext);
1275
static gpg_err_code_t
1276
selftests_rsa (selftest_report_func_t report)
1281
gcry_sexp_t skey = NULL;
1282
gcry_sexp_t pkey = NULL;
1284
/* Convert the S-expressions into the internal representation. */
1286
err = gcry_sexp_sscan (&skey, NULL,
1287
sample_secret_key, strlen (sample_secret_key));
1289
err = gcry_sexp_sscan (&pkey, NULL,
1290
sample_public_key, strlen (sample_public_key));
1293
errtxt = gcry_strerror (err);
1297
what = "key consistency";
1298
err = gcry_pk_testkey (skey);
1301
errtxt = gcry_strerror (err);
1306
errtxt = selftest_sign_1024 (pkey, skey);
1311
errtxt = selftest_encr_1024 (pkey, skey);
1315
gcry_sexp_release (pkey);
1316
gcry_sexp_release (skey);
1317
return 0; /* Succeeded. */
1320
gcry_sexp_release (pkey);
1321
gcry_sexp_release (skey);
1323
report ("pubkey", GCRY_PK_RSA, what, errtxt);
1324
return GPG_ERR_SELFTEST_FAILED;
1328
/* Run a full self-test for ALGO and return 0 on success. */
1329
static gpg_err_code_t
1330
run_selftests (int algo, int extended, selftest_report_func_t report)
1339
ec = selftests_rsa (report);
1342
ec = GPG_ERR_PUBKEY_ALGO;
1352
static const char *rsa_names[] =
1356
"oid.1.2.840.113549.1.1.1",
1360
gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1363
"ne", "nedpqu", "a", "s", "n",
1364
GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
1366
rsa_check_secret_key,
1373
pk_extra_spec_t _gcry_pubkey_extraspec_rsa =
added
removed
grub-core/lib/libgcrypt/cipher/rsa.c
