~ilya-yanok/ubuntu/precise/grub2/fix-for-948716
» Revision
1.17.14
: grub-core/lib/libgcrypt-grub/cipher/rsa.c
« back to all changes in this revision
Viewing changes to grub-core/lib/libgcrypt-grub/cipher/rsa.c
- browse files at revision 1.17.14
- compare with another revision
- download diff
- download tarball
- view history from revision 1.17.14
- Committer: Bazaar Package Importer
- Author(s): Colin Watson
- Date: 2011-01-17 13:43:06 UTC
- mto: (17.6.26 experimental)
- mto: This revision was merged to the branch mainline in revision 102.
- Revision ID: james.westby@ubuntu.com-20110117134306-fy7qewn4s3qdx2pl
Tags: upstream-1.99~rc1
Import upstream version 1.99~rc1
- files added:
- Makefile.in
- autom4te.cache
- grub-core/lib/libgcrypt-grub
- grub-core/lib/libgcrypt-grub/cipher
- files removed:
- po/LINGUAS
- files modified:
- .bzrignore
added
removed
grub-core/lib/libgcrypt-grub/cipher/rsa.c
1
/* This file was automatically imported with
2
import_gcry.py. Please don't modify it */
3
/* rsa.c - RSA implementation
4
* Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
5
* Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc.
6
*
7
* This file is part of Libgcrypt.
8
*
9
* Libgcrypt is free software; you can redistribute it and/or modify
10
* it under the terms of the GNU Lesser General Public License as
11
* published by the Free Software Foundation; either version 2.1 of
12
* the License, or (at your option) any later version.
13
*
14
* Libgcrypt is distributed in the hope that it will be useful,
15
* but WITHOUT ANY WARRANTY; without even the implied warranty of
16
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
* GNU Lesser General Public License for more details.
18
*
19
* You should have received a copy of the GNU Lesser General Public
20
* License along with this program; if not, see <http://www.gnu.org/licenses/>.
21
*/
22
23
/* This code uses an algorithm protected by U.S. Patent #4,405,829
24
which expired on September 20, 2000. The patent holder placed that
25
patent into the public domain on Sep 6th, 2000.
26
*/
27
28
29
#include "g10lib.h"
30
#include "mpi.h"
31
#include "cipher.h"
32
33
34
typedef struct
35
{
36
gcry_mpi_t n; /* modulus */
37
gcry_mpi_t e; /* exponent */
38
} RSA_public_key;
39
40
41
typedef struct
42
{
43
gcry_mpi_t n; /* public modulus */
44
gcry_mpi_t e; /* public exponent */
45
gcry_mpi_t d; /* exponent */
46
gcry_mpi_t p; /* prime p. */
47
gcry_mpi_t q; /* prime q. */
48
gcry_mpi_t u; /* inverse of p mod q. */
49
} RSA_secret_key;
50
51
52
/* A sample 1024 bit RSA key used for the selftests. */
53
static const char sample_secret_key[] =
54
"(private-key"
55
" (rsa"
56
" (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
57
" 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
58
" ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
59
" 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
60
" (e #010001#)"
61
" (d #046129f2489d71579be0a75fe029bd6cdb574ebf57ea8a5b0fda942cab943b11"
62
" 7d7bb95e5d28875e0f9fc5fcc06a72f6d502464dabded78ef6b716177b83d5bd"
63
" c543dc5d3fed932e59f5897e92e6f58a0f33424106a3b6fa2cbf877510e4ac21"
64
" c3ee47851e97d12996222ac3566d4ccb0b83d164074abf7de655fc2446da1781#)"
65
" (p #00e861b700e17e8afe6837e7512e35b6ca11d0ae47d8b85161c67baf64377213"
66
" fe52d772f2035b3ca830af41d8a4120e1c1c70d12cc22f00d28d31dd48a8d424f1#)"
67
" (q #00f7a7ca5367c661f8e62df34f0d05c10c88e5492348dd7bddc942c9a8f369f9"
68
" 35a07785d2db805215ed786e4285df1658eed3ce84f469b81b50d358407b4ad361#)"
69
" (u #304559a9ead56d2309d203811a641bb1a09626bc8eb36fffa23c968ec5bd891e"
70
" ebbafc73ae666e01ba7c8990bae06cc2bbe10b75e69fcacb353a6473079d8e9b#)))";
71
/* A sample 1024 bit RSA key used for the selftests (public only). */
72
static const char sample_public_key[] =
73
"(public-key"
74
" (rsa"
75
" (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
76
" 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
77
" ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
78
" 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
79
" (e #010001#)))";
80
81
82
83
84
static int test_keys (RSA_secret_key *sk, unsigned nbits);
85
static int check_secret_key (RSA_secret_key *sk);
86
static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
87
static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
88
89
90
/* Check that a freshly generated key actually works. Returns 0 on success. */
91
static int
92
test_keys (RSA_secret_key *sk, unsigned int nbits)
93
{
94
int result = -1; /* Default to failure. */
95
RSA_public_key pk;
96
gcry_mpi_t plaintext = gcry_mpi_new (nbits);
97
gcry_mpi_t ciphertext = gcry_mpi_new (nbits);
98
gcry_mpi_t decr_plaintext = gcry_mpi_new (nbits);
99
gcry_mpi_t signature = gcry_mpi_new (nbits);
100
101
/* Put the relevant parameters into a public key structure. */
102
pk.n = sk->n;
103
pk.e = sk->e;
104
105
/* Create a random plaintext. */
106
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
107
108
/* Encrypt using the public key. */
109
public (ciphertext, plaintext, &pk);
110
111
/* Check that the cipher text does not match the plaintext. */
112
if (!gcry_mpi_cmp (ciphertext, plaintext))
113
goto leave; /* Ciphertext is identical to the plaintext. */
114
115
/* Decrypt using the secret key. */
116
secret (decr_plaintext, ciphertext, sk);
117
118
/* Check that the decrypted plaintext matches the original plaintext. */
119
if (gcry_mpi_cmp (decr_plaintext, plaintext))
120
goto leave; /* Plaintext does not match. */
121
122
/* Create another random plaintext as data for signature checking. */
123
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
124
125
/* Use the RSA secret function to create a signature of the plaintext. */
126
secret (signature, plaintext, sk);
127
128
/* Use the RSA public function to verify this signature. */
129
public (decr_plaintext, signature, &pk);
130
if (gcry_mpi_cmp (decr_plaintext, plaintext))
131
goto leave; /* Signature does not match. */
132
133
/* Modify the signature and check that the signing fails. */
134
gcry_mpi_add_ui (signature, signature, 1);
135
public (decr_plaintext, signature, &pk);
136
if (!gcry_mpi_cmp (decr_plaintext, plaintext))
137
goto leave; /* Signature matches but should not. */
138
139
result = 0; /* All tests succeeded. */
140
141
leave:
142
gcry_mpi_release (signature);
143
gcry_mpi_release (decr_plaintext);
144
gcry_mpi_release (ciphertext);
145
gcry_mpi_release (plaintext);
146
return result;
147
}
148
149
150
/* Callback used by the prime generation to test whether the exponent
151
is suitable. Returns 0 if the test has been passed. */
152
static int
153
check_exponent (void *arg, gcry_mpi_t a)
154
{
155
gcry_mpi_t e = arg;
156
gcry_mpi_t tmp;
157
int result;
158
159
mpi_sub_ui (a, a, 1);
160
tmp = _gcry_mpi_alloc_like (a);
161
result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */
162
gcry_mpi_release (tmp);
163
mpi_add_ui (a, a, 1);
164
return result;
165
}
166
167
/****************
168
* Generate a key pair with a key of size NBITS.
169
* USE_E = 0 let Libcgrypt decide what exponent to use.
170
* = 1 request the use of a "secure" exponent; this is required by some
171
* specification to be 65537.
172
* > 2 Use this public exponent. If the given exponent
173
* is not odd one is internally added to it.
174
* TRANSIENT_KEY: If true, generate the primes using the standard RNG.
175
* Returns: 2 structures filled with all needed values
176
*/
177
static gpg_err_code_t
178
generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
179
int transient_key)
180
{
181
gcry_mpi_t p, q; /* the two primes */
182
gcry_mpi_t d; /* the private key */
183
gcry_mpi_t u;
184
gcry_mpi_t t1, t2;
185
gcry_mpi_t n; /* the public key */
186
gcry_mpi_t e; /* the exponent */
187
gcry_mpi_t phi; /* helper: (p-1)(q-1) */
188
gcry_mpi_t g;
189
gcry_mpi_t f;
190
gcry_random_level_t random_level;
191
192
if (fips_mode ())
193
{
194
if (nbits < 1024)
195
return GPG_ERR_INV_VALUE;
196
if (transient_key)
197
return GPG_ERR_INV_VALUE;
198
}
199
200
/* The random quality depends on the transient_key flag. */
201
random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
202
203
/* Make sure that nbits is even so that we generate p, q of equal size. */
204
if ( (nbits&1) )
205
nbits++;
206
207
if (use_e == 1) /* Alias for a secure value */
208
use_e = 65537; /* as demanded by Sphinx. */
209
210
/* Public exponent:
211
In general we use 41 as this is quite fast and more secure than the
212
commonly used 17. Benchmarking the RSA verify function
213
with a 1024 bit key yields (2001-11-08):
214
e=17 0.54 ms
215
e=41 0.75 ms
216
e=257 0.95 ms
217
e=65537 1.80 ms
218
*/
219
e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
220
if (!use_e)
221
mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */
222
else
223
{
224
use_e |= 1; /* make sure this is odd */
225
mpi_set_ui (e, use_e);
226
}
227
228
n = gcry_mpi_new (nbits);
229
230
p = q = NULL;
231
do
232
{
233
/* select two (very secret) primes */
234
if (p)
235
gcry_mpi_release (p);
236
if (q)
237
gcry_mpi_release (q);
238
if (use_e)
239
{ /* Do an extra test to ensure that the given exponent is
240
suitable. */
241
p = _gcry_generate_secret_prime (nbits/2, random_level,
242
check_exponent, e);
243
q = _gcry_generate_secret_prime (nbits/2, random_level,
244
check_exponent, e);
245
}
246
else
247
{ /* We check the exponent later. */
248
p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
249
q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
250
}
251
if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
252
mpi_swap(p,q);
253
/* calculate the modulus */
254
mpi_mul( n, p, q );
255
}
256
while ( mpi_get_nbits(n) != nbits );
257
258
/* calculate Euler totient: phi = (p-1)(q-1) */
259
t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
260
t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
261
phi = gcry_mpi_snew ( nbits );
262
g = gcry_mpi_snew ( nbits );
263
f = gcry_mpi_snew ( nbits );
264
mpi_sub_ui( t1, p, 1 );
265
mpi_sub_ui( t2, q, 1 );
266
mpi_mul( phi, t1, t2 );
267
gcry_mpi_gcd(g, t1, t2);
268
mpi_fdiv_q(f, phi, g);
269
270
while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
271
{
272
if (use_e)
273
BUG (); /* The prime generator already made sure that we
274
never can get to here. */
275
mpi_add_ui (e, e, 2);
276
}
277
278
/* calculate the secret key d = e^1 mod phi */
279
d = gcry_mpi_snew ( nbits );
280
mpi_invm(d, e, f );
281
/* calculate the inverse of p and q (used for chinese remainder theorem)*/
282
u = gcry_mpi_snew ( nbits );
283
mpi_invm(u, p, q );
284
285
if( DBG_CIPHER )
286
{
287
log_mpidump(" p= ", p );
288
log_mpidump(" q= ", q );
289
log_mpidump("phi= ", phi );
290
log_mpidump(" g= ", g );
291
log_mpidump(" f= ", f );
292
log_mpidump(" n= ", n );
293
log_mpidump(" e= ", e );
294
log_mpidump(" d= ", d );
295
log_mpidump(" u= ", u );
296
}
297
298
gcry_mpi_release (t1);
299
gcry_mpi_release (t2);
300
gcry_mpi_release (phi);
301
gcry_mpi_release (f);
302
gcry_mpi_release (g);
303
304
sk->n = n;
305
sk->e = e;
306
sk->p = p;
307
sk->q = q;
308
sk->d = d;
309
sk->u = u;
310
311
/* Now we can test our keys. */
312
if (test_keys (sk, nbits - 64))
313
{
314
gcry_mpi_release (sk->n); sk->n = NULL;
315
gcry_mpi_release (sk->e); sk->e = NULL;
316
gcry_mpi_release (sk->p); sk->p = NULL;
317
gcry_mpi_release (sk->q); sk->q = NULL;
318
gcry_mpi_release (sk->d); sk->d = NULL;
319
gcry_mpi_release (sk->u); sk->u = NULL;
320
fips_signal_error ("self-test after key generation failed");
321
return GPG_ERR_SELFTEST_FAILED;
322
}
323
324
return 0;
325
}
326
327
328
/* Helper for generate_x931. */
329
static gcry_mpi_t
330
gen_x931_parm_xp (unsigned int nbits)
331
{
332
gcry_mpi_t xp;
333
334
xp = gcry_mpi_snew (nbits);
335
gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
336
337
/* The requirement for Xp is:
338
339
sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
340
341
We set the two high order bits to 1 to satisfy the lower bound.
342
By using mpi_set_highbit we make sure that the upper bound is
343
satisfied as well. */
344
mpi_set_highbit (xp, nbits-1);
345
mpi_set_bit (xp, nbits-2);
346
gcry_assert ( mpi_get_nbits (xp) == nbits );
347
348
return xp;
349
}
350
351
352
/* Helper for generate_x931. */
353
static gcry_mpi_t
354
gen_x931_parm_xi (void)
355
{
356
gcry_mpi_t xi;
357
358
xi = gcry_mpi_snew (101);
359
gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM);
360
mpi_set_highbit (xi, 100);
361
gcry_assert ( mpi_get_nbits (xi) == 101 );
362
363
return xi;
364
}
365
366
367
368
/* Variant of the standard key generation code using the algorithm
369
from X9.31. Using this algorithm has the advantage that the
370
generation can be made deterministic which is required for CAVS
371
testing. */
372
static gpg_err_code_t
373
generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
374
gcry_sexp_t deriveparms, int *swapped)
375
{
376
gcry_mpi_t p, q; /* The two primes. */
377
gcry_mpi_t e; /* The public exponent. */
378
gcry_mpi_t n; /* The public key. */
379
gcry_mpi_t d; /* The private key */
380
gcry_mpi_t u; /* The inverse of p and q. */
381
gcry_mpi_t pm1; /* p - 1 */
382
gcry_mpi_t qm1; /* q - 1 */
383
gcry_mpi_t phi; /* Euler totient. */
384
gcry_mpi_t f, g; /* Helper. */
385
386
*swapped = 0;
387
388
if (e_value == 1) /* Alias for a secure value. */
389
e_value = 65537;
390
391
/* Point 1 of section 4.1: k = 1024 + 256s with S >= 0 */
392
if (nbits < 1024 || (nbits % 256))
393
return GPG_ERR_INV_VALUE;
394
395
/* Point 2: 2 <= bitlength(e) < 2^{k-2}
396
Note that we do not need to check the upper bound because we use
397
an unsigned long for E and thus there is no way for E to reach
398
that limit. */
399
if (e_value < 3)
400
return GPG_ERR_INV_VALUE;
401
402
/* Our implementaion requires E to be odd. */
403
if (!(e_value & 1))
404
return GPG_ERR_INV_VALUE;
405
406
/* Point 3: e > 0 or e 0 if it is to be randomly generated.
407
We support only a fixed E and thus there is no need for an extra test. */
408
409
410
/* Compute or extract the derive parameters. */
411
{
412
gcry_mpi_t xp1 = NULL;
413
gcry_mpi_t xp2 = NULL;
414
gcry_mpi_t xp = NULL;
415
gcry_mpi_t xq1 = NULL;
416
gcry_mpi_t xq2 = NULL;
417
gcry_mpi_t xq = NULL;
418
gcry_mpi_t tmpval;
419
420
if (!deriveparms)
421
{
422
/* Not given: Generate them. */
423
xp = gen_x931_parm_xp (nbits/2);
424
/* Make sure that |xp - xq| > 2^{nbits - 100} holds. */
425
tmpval = gcry_mpi_snew (nbits/2);
426
do
427
{
428
gcry_mpi_release (xq);
429
xq = gen_x931_parm_xp (nbits/2);
430
mpi_sub (tmpval, xp, xq);
431
}
432
while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
433
gcry_mpi_release (tmpval);
434
435
xp1 = gen_x931_parm_xi ();
436
xp2 = gen_x931_parm_xi ();
437
xq1 = gen_x931_parm_xi ();
438
xq2 = gen_x931_parm_xi ();
439
440
}
441
else
442
{
443
/* Parameters to derive the key are given. */
444
struct { const char *name; gcry_mpi_t *value; } tbl[] = {
445
{ "Xp1", &xp1 },
446
{ "Xp2", &xp2 },
447
{ "Xp", &xp },
448
{ "Xq1", &xq1 },
449
{ "Xq2", &xq2 },
450
{ "Xq", &xq },
451
{ NULL, NULL }
452
};
453
int idx;
454
gcry_sexp_t oneparm;
455
456
for (idx=0; tbl[idx].name; idx++)
457
{
458
oneparm = gcry_sexp_find_token (deriveparms, tbl[idx].name, 0);
459
if (oneparm)
460
{
461
*tbl[idx].value = gcry_sexp_nth_mpi (oneparm, 1,
462
GCRYMPI_FMT_USG);
463
gcry_sexp_release (oneparm);
464
}
465
}
466
for (idx=0; tbl[idx].name; idx++)
467
if (!*tbl[idx].value)
468
break;
469
if (tbl[idx].name)
470
{
471
/* At least one parameter is missing. */
472
for (idx=0; tbl[idx].name; idx++)
473
gcry_mpi_release (*tbl[idx].value);
474
return GPG_ERR_MISSING_VALUE;
475
}
476
}
477
478
e = mpi_alloc_set_ui (e_value);
479
480
/* Find two prime numbers. */
481
p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL);
482
q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL);
483
gcry_mpi_release (xp); xp = NULL;
484
gcry_mpi_release (xp1); xp1 = NULL;
485
gcry_mpi_release (xp2); xp2 = NULL;
486
gcry_mpi_release (xq); xq = NULL;
487
gcry_mpi_release (xq1); xq1 = NULL;
488
gcry_mpi_release (xq2); xq2 = NULL;
489
if (!p || !q)
490
{
491
gcry_mpi_release (p);
492
gcry_mpi_release (q);
493
gcry_mpi_release (e);
494
return GPG_ERR_NO_PRIME;
495
}
496
}
497
498
499
/* Compute the public modulus. We make sure that p is smaller than
500
q to allow the use of the CRT. */
501
if (mpi_cmp (p, q) > 0 )
502
{
503
mpi_swap (p, q);
504
*swapped = 1;
505
}
506
n = gcry_mpi_new (nbits);
507
mpi_mul (n, p, q);
508
509
/* Compute the Euler totient: phi = (p-1)(q-1) */
510
pm1 = gcry_mpi_snew (nbits/2);
511
qm1 = gcry_mpi_snew (nbits/2);
512
phi = gcry_mpi_snew (nbits);
513
mpi_sub_ui (pm1, p, 1);
514
mpi_sub_ui (qm1, q, 1);
515
mpi_mul (phi, pm1, qm1);
516
517
g = gcry_mpi_snew (nbits);
518
gcry_assert (gcry_mpi_gcd (g, e, phi));
519
520
/* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
521
gcry_mpi_gcd (g, pm1, qm1);
522
f = pm1; pm1 = NULL;
523
gcry_mpi_release (qm1); qm1 = NULL;
524
mpi_fdiv_q (f, phi, g);
525
gcry_mpi_release (phi); phi = NULL;
526
d = g; g = NULL;
527
/* Compute the secret key: d = e^{-1} mod lcm(p-1,q-1) */
528
mpi_invm (d, e, f);
529
530
/* Compute the inverse of p and q. */
531
u = f; f = NULL;
532
mpi_invm (u, p, q );
533
534
if( DBG_CIPHER )
535
{
536
if (*swapped)
537
log_debug ("p and q are swapped\n");
538
log_mpidump(" p", p );
539
log_mpidump(" q", q );
540
log_mpidump(" n", n );
541
log_mpidump(" e", e );
542
log_mpidump(" d", d );
543
log_mpidump(" u", u );
544
}
545
546
547
sk->n = n;
548
sk->e = e;
549
sk->p = p;
550
sk->q = q;
551
sk->d = d;
552
sk->u = u;
553
554
/* Now we can test our keys. */
555
if (test_keys (sk, nbits - 64))
556
{
557
gcry_mpi_release (sk->n); sk->n = NULL;
558
gcry_mpi_release (sk->e); sk->e = NULL;
559
gcry_mpi_release (sk->p); sk->p = NULL;
560
gcry_mpi_release (sk->q); sk->q = NULL;
561
gcry_mpi_release (sk->d); sk->d = NULL;
562
gcry_mpi_release (sk->u); sk->u = NULL;
563
fips_signal_error ("self-test after key generation failed");
564
return GPG_ERR_SELFTEST_FAILED;
565
}
566
567
return 0;
568
}
569
570
571
/****************
572
* Test wether the secret key is valid.
573
* Returns: true if this is a valid key.
574
*/
575
static int
576
check_secret_key( RSA_secret_key *sk )
577
{
578
int rc;
579
gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
580
581
mpi_mul(temp, sk->p, sk->q );
582
rc = mpi_cmp( temp, sk->n );
583
mpi_free(temp);
584
return !rc;
585
}
586
587
588
589
/****************
590
* Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
591
*
592
* c = m^e mod n
593
*
594
* Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
595
*/
596
static void
597
public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
598
{
599
if( output == input ) /* powm doesn't like output and input the same */
600
{
601
gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
602
mpi_powm( x, input, pkey->e, pkey->n );
603
mpi_set(output, x);
604
mpi_free(x);
605
}
606
else
607
mpi_powm( output, input, pkey->e, pkey->n );
608
}
609
610
#if 0
611
static void
612
stronger_key_check ( RSA_secret_key *skey )
613
{
614
gcry_mpi_t t = mpi_alloc_secure ( 0 );
615
gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
616
gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
617
gcry_mpi_t phi = mpi_alloc_secure ( 0 );
618
619
/* check that n == p * q */
620
mpi_mul( t, skey->p, skey->q);
621
if (mpi_cmp( t, skey->n) )
622
log_info ( "RSA Oops: n != p * q\n" );
623
624
/* check that p is less than q */
625
if( mpi_cmp( skey->p, skey->q ) > 0 )
626
{
627
log_info ("RSA Oops: p >= q - fixed\n");
628
_gcry_mpi_swap ( skey->p, skey->q);
629
}
630
631
/* check that e divides neither p-1 nor q-1 */
632
mpi_sub_ui(t, skey->p, 1 );
633
mpi_fdiv_r(t, t, skey->e );
634
if ( !mpi_cmp_ui( t, 0) )
635
log_info ( "RSA Oops: e divides p-1\n" );
636
mpi_sub_ui(t, skey->q, 1 );
637
mpi_fdiv_r(t, t, skey->e );
638
if ( !mpi_cmp_ui( t, 0) )
639
log_info ( "RSA Oops: e divides q-1\n" );
640
641
/* check that d is correct */
642
mpi_sub_ui( t1, skey->p, 1 );
643
mpi_sub_ui( t2, skey->q, 1 );
644
mpi_mul( phi, t1, t2 );
645
gcry_mpi_gcd(t, t1, t2);
646
mpi_fdiv_q(t, phi, t);
647
mpi_invm(t, skey->e, t );
648
if ( mpi_cmp(t, skey->d ) )
649
{
650
log_info ( "RSA Oops: d is wrong - fixed\n");
651
mpi_set (skey->d, t);
652
_gcry_log_mpidump (" fixed d", skey->d);
653
}
654
655
/* check for correctness of u */
656
mpi_invm(t, skey->p, skey->q );
657
if ( mpi_cmp(t, skey->u ) )
658
{
659
log_info ( "RSA Oops: u is wrong - fixed\n");
660
mpi_set (skey->u, t);
661
_gcry_log_mpidump (" fixed u", skey->u);
662
}
663
664
log_info ( "RSA secret key check finished\n");
665
666
mpi_free (t);
667
mpi_free (t1);
668
mpi_free (t2);
669
mpi_free (phi);
670
}
671
#endif
672
673
674
675
/****************
676
* Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
677
*
678
* m = c^d mod n
679
*
680
* Or faster:
681
*
682
* m1 = c ^ (d mod (p-1)) mod p
683
* m2 = c ^ (d mod (q-1)) mod q
684
* h = u * (m2 - m1) mod q
685
* m = m1 + h * p
686
*
687
* Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
688
*/
689
static void
690
secret(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
691
{
692
if (!skey->p || !skey->q || !skey->u)
693
{
694
mpi_powm (output, input, skey->d, skey->n);
695
}
696
else
697
{
698
gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
699
gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
700
gcry_mpi_t h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
701
702
/* m1 = c ^ (d mod (p-1)) mod p */
703
mpi_sub_ui( h, skey->p, 1 );
704
mpi_fdiv_r( h, skey->d, h );
705
mpi_powm( m1, input, h, skey->p );
706
/* m2 = c ^ (d mod (q-1)) mod q */
707
mpi_sub_ui( h, skey->q, 1 );
708
mpi_fdiv_r( h, skey->d, h );
709
mpi_powm( m2, input, h, skey->q );
710
/* h = u * ( m2 - m1 ) mod q */
711
mpi_sub( h, m2, m1 );
712
if ( mpi_is_neg( h ) )
713
mpi_add ( h, h, skey->q );
714
mpi_mulm( h, skey->u, h, skey->q );
715
/* m = m2 + h * p */
716
mpi_mul ( h, h, skey->p );
717
mpi_add ( output, m1, h );
718
719
mpi_free ( h );
720
mpi_free ( m1 );
721
mpi_free ( m2 );
722
}
723
}
724
725
726
727
/* Perform RSA blinding. */
728
static gcry_mpi_t
729
rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n)
730
{
731
/* A helper. */
732
gcry_mpi_t a;
733
734
/* Result. */
735
gcry_mpi_t y;
736
737
a = gcry_mpi_snew (gcry_mpi_get_nbits (n));
738
y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
739
740
/* Now we calculate: y = (x * r^e) mod n, where r is the random
741
number, e is the public exponent, x is the non-blinded data and n
742
is the RSA modulus. */
743
gcry_mpi_powm (a, r, e, n);
744
gcry_mpi_mulm (y, a, x, n);
745
746
gcry_mpi_release (a);
747
748
return y;
749
}
750
751
/* Undo RSA blinding. */
752
static gcry_mpi_t
753
rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n)
754
{
755
gcry_mpi_t y;
756
757
y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
758
759
/* Here we calculate: y = (x * r^-1) mod n, where x is the blinded
760
decrypted data, ri is the modular multiplicative inverse of r and
761
n is the RSA modulus. */
762
763
gcry_mpi_mulm (y, ri, x, n);
764
765
return y;
766
}
767
768
/*********************************************
769
************** interface ******************
770
*********************************************/
771
772
static gcry_err_code_t
773
rsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
774
const gcry_sexp_t genparms,
775
gcry_mpi_t *skey, gcry_mpi_t **retfactors,
776
gcry_sexp_t *r_extrainfo)
777
{
778
RSA_secret_key sk;
779
gpg_err_code_t ec;
780
gcry_sexp_t deriveparms;
781
int transient_key = 0;
782
int use_x931 = 0;
783
gcry_sexp_t l1;
784
785
(void)algo;
786
787
*retfactors = NULL; /* We don't return them. */
788
789
deriveparms = (genparms?
790
gcry_sexp_find_token (genparms, "derive-parms", 0) : NULL);
791
if (!deriveparms)
792
{
793
/* Parse the optional "use-x931" flag. */
794
l1 = gcry_sexp_find_token (genparms, "use-x931", 0);
795
if (l1)
796
{
797
use_x931 = 1;
798
gcry_sexp_release (l1);
799
}
800
}
801
802
if (deriveparms || use_x931 || fips_mode ())
803
{
804
int swapped;
805
ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
806
gcry_sexp_release (deriveparms);
807
if (!ec && r_extrainfo && swapped)
808
{
809
ec = gcry_sexp_new (r_extrainfo,
810
"(misc-key-info(p-q-swapped))", 0, 1);
811
if (ec)
812
{
813
gcry_mpi_release (sk.n); sk.n = NULL;
814
gcry_mpi_release (sk.e); sk.e = NULL;
815
gcry_mpi_release (sk.p); sk.p = NULL;
816
gcry_mpi_release (sk.q); sk.q = NULL;
817
gcry_mpi_release (sk.d); sk.d = NULL;
818
gcry_mpi_release (sk.u); sk.u = NULL;
819
}
820
}
821
}
822
else
823
{
824
/* Parse the optional "transient-key" flag. */
825
l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
826
if (l1)
827
{
828
transient_key = 1;
829
gcry_sexp_release (l1);
830
}
831
/* Generate. */
832
ec = generate_std (&sk, nbits, evalue, transient_key);
833
}
834
835
if (!ec)
836
{
837
skey[0] = sk.n;
838
skey[1] = sk.e;
839
skey[2] = sk.d;
840
skey[3] = sk.p;
841
skey[4] = sk.q;
842
skey[5] = sk.u;
843
}
844
845
return ec;
846
}
847
848
849
static gcry_err_code_t
850
rsa_generate (int algo, unsigned int nbits, unsigned long evalue,
851
gcry_mpi_t *skey, gcry_mpi_t **retfactors)
852
{
853
return rsa_generate_ext (algo, nbits, evalue, NULL, skey, retfactors, NULL);
854
}
855
856
857
static gcry_err_code_t
858
rsa_check_secret_key (int algo, gcry_mpi_t *skey)
859
{
860
gcry_err_code_t err = GPG_ERR_NO_ERROR;
861
RSA_secret_key sk;
862
863
(void)algo;
864
865
sk.n = skey[0];
866
sk.e = skey[1];
867
sk.d = skey[2];
868
sk.p = skey[3];
869
sk.q = skey[4];
870
sk.u = skey[5];
871
872
if (!sk.p || !sk.q || !sk.u)
873
err = GPG_ERR_NO_OBJ; /* To check the key we need the optional
874
parameters. */
875
else if (!check_secret_key (&sk))
876
err = GPG_ERR_PUBKEY_ALGO;
877
878
return err;
879
}
880
881
882
static gcry_err_code_t
883
rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data,
884
gcry_mpi_t *pkey, int flags)
885
{
886
RSA_public_key pk;
887
888
(void)algo;
889
(void)flags;
890
891
pk.n = pkey[0];
892
pk.e = pkey[1];
893
resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n));
894
public (resarr[0], data, &pk);
895
896
return GPG_ERR_NO_ERROR;
897
}
898
899
900
static gcry_err_code_t
901
rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
902
gcry_mpi_t *skey, int flags)
903
{
904
RSA_secret_key sk;
905
gcry_mpi_t r = MPI_NULL; /* Random number needed for blinding. */
906
gcry_mpi_t ri = MPI_NULL; /* Modular multiplicative inverse of
907
r. */
908
gcry_mpi_t x = MPI_NULL; /* Data to decrypt. */
909
gcry_mpi_t y; /* Result. */
910
911
(void)algo;
912
913
/* Extract private key. */
914
sk.n = skey[0];
915
sk.e = skey[1];
916
sk.d = skey[2];
917
sk.p = skey[3]; /* Optional. */
918
sk.q = skey[4]; /* Optional. */
919
sk.u = skey[5]; /* Optional. */
920
921
y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
922
923
/* We use blinding by default to mitigate timing attacks which can
924
be practically mounted over the network as shown by Brumley and
925
Boney in 2003. */
926
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
927
{
928
/* Initialize blinding. */
929
930
/* First, we need a random number r between 0 and n - 1, which
931
is relatively prime to n (i.e. it is neither p nor q). The
932
random number needs to be only unpredictable, thus we employ
933
the gcry_create_nonce function by using GCRY_WEAK_RANDOM with
934
gcry_mpi_randomize. */
935
r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
936
ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
937
938
gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n), GCRY_WEAK_RANDOM);
939
gcry_mpi_mod (r, r, sk.n);
940
941
/* Calculate inverse of r. It practically impossible that the
942
follwing test fails, thus we do not add code to release
943
allocated resources. */
944
if (!gcry_mpi_invm (ri, r, sk.n))
945
return GPG_ERR_INTERNAL;
946
}
947
948
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
949
x = rsa_blind (data[0], r, sk.e, sk.n);
950
else
951
x = data[0];
952
953
/* Do the encryption. */
954
secret (y, x, &sk);
955
956
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
957
{
958
/* Undo blinding. */
959
gcry_mpi_t a = gcry_mpi_copy (y);
960
961
gcry_mpi_release (y);
962
y = rsa_unblind (a, ri, sk.n);
963
964
gcry_mpi_release (a);
965
}
966
967
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
968
{
969
/* Deallocate resources needed for blinding. */
970
gcry_mpi_release (x);
971
gcry_mpi_release (r);
972
gcry_mpi_release (ri);
973
}
974
975
/* Copy out result. */
976
*result = y;
977
978
return GPG_ERR_NO_ERROR;
979
}
980
981
982
static gcry_err_code_t
983
rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
984
{
985
RSA_secret_key sk;
986
987
(void)algo;
988
989
sk.n = skey[0];
990
sk.e = skey[1];
991
sk.d = skey[2];
992
sk.p = skey[3];
993
sk.q = skey[4];
994
sk.u = skey[5];
995
resarr[0] = mpi_alloc( mpi_get_nlimbs (sk.n));
996
secret (resarr[0], data, &sk);
997
998
return GPG_ERR_NO_ERROR;
999
}
1000
1001
1002
static gcry_err_code_t
1003
rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1004
int (*cmp) (void *opaque, gcry_mpi_t tmp),
1005
void *opaquev)
1006
{
1007
RSA_public_key pk;
1008
gcry_mpi_t result;
1009
gcry_err_code_t rc;
1010
1011
(void)algo;
1012
(void)cmp;
1013
(void)opaquev;
1014
1015
pk.n = pkey[0];
1016
pk.e = pkey[1];
1017
result = gcry_mpi_new ( 160 );
1018
public( result, data[0], &pk );
1019
#ifdef IS_DEVELOPMENT_VERSION
1020
if (DBG_CIPHER)
1021
{
1022
log_mpidump ("rsa verify result:", result );
1023
log_mpidump (" hash:", hash );
1024
}
1025
#endif /*IS_DEVELOPMENT_VERSION*/
1026
/*rc = (*cmp)( opaquev, result );*/
1027
rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
1028
gcry_mpi_release (result);
1029
1030
return rc;
1031
}
1032
1033
1034
static unsigned int
1035
rsa_get_nbits (int algo, gcry_mpi_t *pkey)
1036
{
1037
(void)algo;
1038
1039
return mpi_get_nbits (pkey[0]);
1040
}
1041
1042
1043
/* Compute a keygrip. MD is the hash context which we are going to
1044
update. KEYPARAM is an S-expression with the key parameters, this
1045
is usually a public key but may also be a secret key. An example
1046
of such an S-expression is:
1047
1048
(rsa
1049
(n #00B...#)
1050
(e #010001#))
1051
1052
PKCS-15 says that for RSA only the modulus should be hashed -
1053
however, it is not clear wether this is meant to use the raw bytes
1054
(assuming this is an unsigned integer) or whether the DER required
1055
0 should be prefixed. We hash the raw bytes. */
1056
static gpg_err_code_t
1057
compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1058
{
1059
gcry_sexp_t l1;
1060
const char *data;
1061
size_t datalen;
1062
1063
l1 = gcry_sexp_find_token (keyparam, "n", 1);
1064
if (!l1)
1065
return GPG_ERR_NO_OBJ;
1066
1067
data = gcry_sexp_nth_data (l1, 1, &datalen);
1068
if (!data)
1069
{
1070
gcry_sexp_release (l1);
1071
return GPG_ERR_NO_OBJ;
1072
}
1073
1074
gcry_md_write (md, data, datalen);
1075
gcry_sexp_release (l1);
1076
1077
return 0;
1078
}
1079
1080
1081
1082
1083
/*
1084
Self-test section.
1085
*/
1086
1087
1088
1089
1090
/* Given an S-expression ENCR_DATA of the form:
1091
1092
(enc-val
1093
(rsa
1094
(a a-value)))
1095
1096
as returned by gcry_pk_decrypt, return the the A-VALUE. On error,
1097
return NULL. */
1098
static gcry_mpi_t
1099
extract_a_from_sexp (gcry_sexp_t encr_data)
1100
{
1101
gcry_sexp_t l1, l2, l3;
1102
gcry_mpi_t a_value;
1103
1104
l1 = gcry_sexp_find_token (encr_data, "enc-val", 0);
1105
if (!l1)
1106
return NULL;
1107
l2 = gcry_sexp_find_token (l1, "rsa", 0);
1108
gcry_sexp_release (l1);
1109
if (!l2)
1110
return NULL;
1111
l3 = gcry_sexp_find_token (l2, "a", 0);
1112
gcry_sexp_release (l2);
1113
if (!l3)
1114
return NULL;
1115
a_value = gcry_sexp_nth_mpi (l3, 1, 0);
1116
gcry_sexp_release (l3);
1117
1118
return a_value;
1119
}
1120
1121
1122
1123
1124
1125
1126
/* Run a full self-test for ALGO and return 0 on success. */
1127
1128
1129
1130
1131
static const char *rsa_names[] =
1132
{
1133
"rsa",
1134
"openpgp-rsa",
1135
"oid.1.2.840.113549.1.1.1",
1136
NULL,
1137
};
1138
1139
gcry_pk_spec_t _gcry_pubkey_spec_rsa =
1140
{
1141
"RSA", rsa_names,
1142
"ne", "nedpqu", "a", "s", "n",
1143
GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
1144
rsa_generate,
1145
rsa_check_secret_key,
1146
rsa_encrypt,
1147
rsa_decrypt,
1148
rsa_sign,
1149
rsa_verify,
1150
rsa_get_nbits,
1151
};
1152
pk_extra_spec_t _gcry_pubkey_extraspec_rsa =
1153
{
1154
run_selftests,
1155
rsa_generate_ext,
1156
compute_keygrip
1157
};
1158
Loggerhead is a web-based interface for Breezy
Version: 2.0.1