« back to all changes in this revision
Viewing changes to cipher/rsa.c
- browse files at revision 18
- compare with another revision
- download diff
- download tarball
- view history from revision 18
- Committer: Bazaar Package Importer
- Author(s): Bhavani Shankar
- Date: 2009-05-16 20:13:32 UTC
- mfrom: (1.1.6 upstream) (2.1.3 squeeze)
- Revision ID: james.westby@ubuntu.com-20090516201332-czkobpu32w318i16
Tags: 1.4.4-2ubuntu1
* Merge from Debian unstable (LP: #364535), remaining changes:
- Add libgcrypt11-udeb for use by cryptsetup-udeb.
- Add clean-la.mk, and add a symlink for the .la
- Install to /lib.
- Add libgcrypt11-udeb for use by cryptsetup-udeb.
- Add clean-la.mk, and add a symlink for the .la
- Install to /lib.
- files added:
- cipher/hash-common.c
- random
- files removed:
- BUGS
- files modified:
- AUTHORS
added
removed
cipher/rsa.c
1
/* rsa.c - RSA function
1
/* rsa.c - RSA implementation
2
2
* Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3
* Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3
* Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc.
4
4
*
5
5
* This file is part of Libgcrypt.
6
6
*
52
52
} RSA_secret_key;
53
53
54
54
55
static void test_keys (RSA_secret_key *sk, unsigned nbits);
56
static void generate (RSA_secret_key *sk,
57
unsigned int nbits, unsigned long use_e);
55
/* A sample 1024 bit RSA key used for the selftests. */
56
static const char sample_secret_key[] =
57
"(private-key"
58
" (rsa"
59
" (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
60
" 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
61
" ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
62
" 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
63
" (e #010001#)"
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[] =
76
"(public-key"
77
" (rsa"
78
" (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
79
" 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
80
" ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
81
" 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
82
" (e #010001#)))";
83
84
85
86
87
static int test_keys (RSA_secret_key *sk, unsigned nbits);
58
88
static int check_secret_key (RSA_secret_key *sk);
59
89
static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
60
90
static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
61
91
62
92
63
static void
64
test_keys( RSA_secret_key *sk, unsigned nbits )
93
/* Check that a freshly generated key actually works. Returns 0 on success. */
94
static int
95
test_keys (RSA_secret_key *sk, unsigned int nbits)
65
96
{
97
int result = -1; /* Default to failure. */
66
98
RSA_public_key pk;
67
gcry_mpi_t test = gcry_mpi_new ( nbits );
68
gcry_mpi_t out1 = gcry_mpi_new ( nbits );
69
gcry_mpi_t out2 = gcry_mpi_new ( nbits );
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);
70
103
104
/* Put the relevant parameters into a public key structure. */
71
105
pk.n = sk->n;
72
106
pk.e = sk->e;
73
gcry_mpi_randomize( test, nbits, GCRY_WEAK_RANDOM );
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
gcry_mpi_release ( test );
84
gcry_mpi_release ( out1 );
85
gcry_mpi_release ( out2 );
107
108
/* Create a random plaintext. */
109
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
110
111
/* Encrypt using the public key. */
112
public (ciphertext, plaintext, &pk);
113
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. */
117
118
/* Decrypt using the secret key. */
119
secret (decr_plaintext, ciphertext, sk);
120
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. */
124
125
/* Create another random plaintext as data for signature checking. */
126
gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
127
128
/* Use the RSA secret function to create a signature of the plaintext. */
129
secret (signature, plaintext, sk);
130
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. */
135
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. */
141
142
result = 0; /* All tests succeeded. */
143
144
leave:
145
gcry_mpi_release (signature);
146
gcry_mpi_release (decr_plaintext);
147
gcry_mpi_release (ciphertext);
148
gcry_mpi_release (plaintext);
149
return result;
86
150
}
87
151
88
152
108
172
* USE_E = 0 let Libcgrypt decide what exponent to use.
109
173
* = 1 request the use of a "secure" exponent; this is required by some
110
174
* specification to be 65537.
111
* > 2 Try starting at this value until a working exponent is found.
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.
112
178
* Returns: 2 structures filled with all needed values
113
179
*/
114
static void
115
generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e)
180
static gpg_err_code_t
181
generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
182
int transient_key)
116
183
{
117
184
gcry_mpi_t p, q; /* the two primes */
118
185
gcry_mpi_t d; /* the private key */
123
190
gcry_mpi_t phi; /* helper: (p-1)(q-1) */
124
191
gcry_mpi_t g;
125
192
gcry_mpi_t f;
126
127
/* make sure that nbits is even so that we generate p, q of equal size */
193
gcry_random_level_t random_level;
194
195
if (fips_mode ())
196
{
197
if (nbits < 1024)
198
return GPG_ERR_INV_VALUE;
199
if (transient_key)
200
return GPG_ERR_INV_VALUE;
201
}
202
203
/* The random quality depends on the transient_key flag. */
204
random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
205
206
/* Make sure that nbits is even so that we generate p, q of equal size. */
128
207
if ( (nbits&1) )
129
208
nbits++;
130
209
131
if (use_e == 1) /* Alias for a secure value. */
132
use_e = 65537; /* as demanded by Spinx. */
210
if (use_e == 1) /* Alias for a secure value */
211
use_e = 65537; /* as demanded by Sphinx. */
133
212
134
213
/* Public exponent:
135
214
In general we use 41 as this is quite fast and more secure than the
162
241
if (use_e)
163
242
{ /* Do an extra test to ensure that the given exponent is
164
243
suitable. */
165
p = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
166
q = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
244
p = _gcry_generate_secret_prime (nbits/2, random_level,
245
check_exponent, e);
246
q = _gcry_generate_secret_prime (nbits/2, random_level,
247
check_exponent, e);
167
248
}
168
249
else
169
250
{ /* We check the exponent later. */
170
p = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
171
q = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
251
p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
252
q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
172
253
}
173
254
if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
174
255
mpi_swap(p,q);
230
311
sk->d = d;
231
312
sk->u = u;
232
313
233
/* now we can test our keys (this should never fail!) */
234
test_keys( sk, nbits - 64 );
314
/* Now we can test our keys. */
315
if (test_keys (sk, nbits - 64))
316
{
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;
325
}
326
327
return 0;
328
}
329
330
331
/* Helper for generate_x931. */
332
static gcry_mpi_t
333
gen_x931_parm_xp (unsigned int nbits)
334
{
335
gcry_mpi_t xp;
336
337
xp = gcry_mpi_snew (nbits);
338
gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
339
340
/* The requirement for Xp is:
341
342
sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
343
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 );
350
351
return xp;
352
}
353
354
355
/* Helper for generate_x931. */
356
static gcry_mpi_t
357
gen_x931_parm_xi (void)
358
{
359
gcry_mpi_t xi;
360
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 );
365
366
return xi;
367
}
368
369
370
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
374
testing. */
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)
378
{
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. */
388
389
*swapped = 0;
390
391
if (e_value == 1) /* Alias for a secure value. */
392
e_value = 65537;
393
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;
397
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
401
that limit. */
402
if (e_value < 3)
403
return GPG_ERR_INV_VALUE;
404
405
/* Our implementaion requires E to be odd. */
406
if (!(e_value & 1))
407
return GPG_ERR_INV_VALUE;
408
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. */
411
412
413
/* Compute or extract the derive parameters. */
414
{
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;
421
gcry_mpi_t tmpval;
422
423
if (!deriveparms)
424
{
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);
429
do
430
{
431
gcry_mpi_release (xq);
432
xq = gen_x931_parm_xp (nbits/2);
433
mpi_sub (tmpval, xp, xq);
434
}
435
while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
436
gcry_mpi_release (tmpval);
437
438
xp1 = gen_x931_parm_xi ();
439
xp2 = gen_x931_parm_xi ();
440
xq1 = gen_x931_parm_xi ();
441
xq2 = gen_x931_parm_xi ();
442
443
}
444
else
445
{
446
/* Parameters to derive the key are given. */
447
struct { const char *name; gcry_mpi_t *value; } tbl[] = {
448
{ "Xp1", &xp1 },
449
{ "Xp2", &xp2 },
450
{ "Xp", &xp },
451
{ "Xq1", &xq1 },
452
{ "Xq2", &xq2 },
453
{ "Xq", &xq },
454
{ NULL, NULL }
455
};
456
int idx;
457
gcry_sexp_t oneparm;
458
459
for (idx=0; tbl[idx].name; idx++)
460
{
461
oneparm = gcry_sexp_find_token (deriveparms, tbl[idx].name, 0);
462
if (oneparm)
463
{
464
*tbl[idx].value = gcry_sexp_nth_mpi (oneparm, 1,
465
GCRYMPI_FMT_USG);
466
gcry_sexp_release (oneparm);
467
}
468
}
469
for (idx=0; tbl[idx].name; idx++)
470
if (!*tbl[idx].value)
471
break;
472
if (tbl[idx].name)
473
{
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;
478
}
479
}
480
481
e = mpi_alloc_set_ui (e_value);
482
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;
492
if (!p || !q)
493
{
494
gcry_mpi_release (p);
495
gcry_mpi_release (q);
496
gcry_mpi_release (e);
497
return GPG_ERR_NO_PRIME;
498
}
499
}
500
501
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 )
505
{
506
mpi_swap (p, q);
507
*swapped = 1;
508
}
509
n = gcry_mpi_new (nbits);
510
mpi_mul (n, p, q);
511
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);
519
520
g = gcry_mpi_snew (nbits);
521
gcry_assert (gcry_mpi_gcd (g, e, phi));
522
523
/* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
524
gcry_mpi_gcd (g, pm1, qm1);
525
f = pm1; pm1 = NULL;
526
gcry_mpi_release (qm1); qm1 = NULL;
527
mpi_fdiv_q (f, phi, g);
528
gcry_mpi_release (phi); phi = NULL;
529
d = g; g = NULL;
530
/* Compute the secret key: d = e^{-1} mod lcm(p-1,q-1) */
531
mpi_invm (d, e, f);
532
533
/* Compute the inverse of p and q. */
534
u = f; f = NULL;
535
mpi_invm (u, p, q );
536
537
if( DBG_CIPHER )
538
{
539
if (*swapped)
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 );
547
}
548
549
550
sk->n = n;
551
sk->e = e;
552
sk->p = p;
553
sk->q = q;
554
sk->d = d;
555
sk->u = u;
556
557
/* Now we can test our keys. */
558
if (test_keys (sk, nbits - 64))
559
{
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;
568
}
569
570
return 0;
235
571
}
236
572
237
573
436
772
************** interface ******************
437
773
*********************************************/
438
774
439
gcry_err_code_t
440
_gcry_rsa_generate (int algo, unsigned int nbits, unsigned long use_e,
441
gcry_mpi_t *skey, gcry_mpi_t **retfactors)
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)
442
780
{
443
781
RSA_secret_key sk;
444
gpg_err_code_t rc;
445
int i;
782
gpg_err_code_t ec;
783
gcry_sexp_t deriveparms;
784
int transient_key = 0;
785
int use_x931 = 0;
786
gcry_sexp_t l1;
446
787
447
788
(void)algo;
448
449
generate (&sk, nbits, use_e);
450
skey[0] = sk.n;
451
skey[1] = sk.e;
452
skey[2] = sk.d;
453
skey[3] = sk.p;
454
skey[4] = sk.q;
455
skey[5] = sk.u;
456
789
457
/* Make an empty list of factors. */
458
*retfactors = gcry_calloc ( 1, sizeof **retfactors );
459
if (!*retfactors)
460
{
461
rc = gpg_err_code_from_errno (errno);
462
for (i=0; i <= 5; i++)
463
{
464
gcry_mpi_release (skey[i]);
465
skey[i] = NULL;
790
*retfactors = NULL; /* We don't return them. */
791
792
deriveparms = (genparms?
793
gcry_sexp_find_token (genparms, "derive-parms", 0) : NULL);
794
if (!deriveparms)
795
{
796
/* Parse the optional "use-x931" flag. */
797
l1 = gcry_sexp_find_token (genparms, "use-x931", 0);
798
if (l1)
799
{
800
use_x931 = 1;
801
gcry_sexp_release (l1);
802
}
803
}
804
805
if (deriveparms || use_x931 || fips_mode ())
806
{
807
int swapped;
808
ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
809
gcry_sexp_release (deriveparms);
810
if (!ec && r_extrainfo && swapped)
811
{
812
ec = gcry_sexp_new (r_extrainfo,
813
"(misc-key-info(p-q-swapped))", 0, 1);
814
if (ec)
815
{
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;
822
}
466
823
}
467
824
}
468
825
else
469
rc = 0;
826
{
827
/* Parse the optional "transient-key" flag. */
828
l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
829
if (l1)
830
{
831
transient_key = 1;
832
gcry_sexp_release (l1);
833
}
834
/* Generate. */
835
ec = generate_std (&sk, nbits, evalue, transient_key);
836
}
837
838
if (!ec)
839
{
840
skey[0] = sk.n;
841
skey[1] = sk.e;
842
skey[2] = sk.d;
843
skey[3] = sk.p;
844
skey[4] = sk.q;
845
skey[5] = sk.u;
846
}
470
847
471
return rc;
472
}
473
474
475
gcry_err_code_t
476
_gcry_rsa_check_secret_key( int algo, gcry_mpi_t *skey )
848
return ec;
849
}
850
851
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)
855
{
856
return rsa_generate_ext (algo, nbits, evalue, NULL, skey, retfactors, NULL);
857
}
858
859
860
static gcry_err_code_t
861
rsa_check_secret_key (int algo, gcry_mpi_t *skey)
477
862
{
478
863
gcry_err_code_t err = GPG_ERR_NO_ERROR;
479
864
RSA_secret_key sk;
497
882
}
498
883
499
884
500
gcry_err_code_t
501
_gcry_rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data,
502
gcry_mpi_t *pkey, int flags)
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)
503
888
{
504
889
RSA_public_key pk;
505
890
514
899
return GPG_ERR_NO_ERROR;
515
900
}
516
901
517
gcry_err_code_t
518
_gcry_rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
519
gcry_mpi_t *skey, int flags)
902
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)
520
906
{
521
907
RSA_secret_key sk;
522
908
gcry_mpi_t r = MPI_NULL; /* Random number needed for blinding. */
537
923
538
924
y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
539
925
926
/* We use blinding by default to mitigate timing attacks which can
927
be practically mounted over the network as shown by Brumley and
928
Boney in 2003. */
540
929
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
541
930
{
542
931
/* Initialize blinding. */
543
932
544
933
/* First, we need a random number r between 0 and n - 1, which
545
is relatively prime to n (i.e. it is neither p nor q). */
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. */
546
938
r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
547
939
ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
548
940
549
gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n),
550
GCRY_STRONG_RANDOM);
941
gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n), GCRY_WEAK_RANDOM);
551
942
gcry_mpi_mod (r, r, sk.n);
552
943
553
/* Actually it should be okay to skip the check for equality
554
with either p or q here. */
555
556
/* Calculate inverse of r. */
557
if (! gcry_mpi_invm (ri, r, sk.n))
558
BUG ();
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;
559
949
}
560
950
561
951
if (! (flags & PUBKEY_FLAG_NO_BLINDING))
591
981
return GPG_ERR_NO_ERROR;
592
982
}
593
983
594
gcry_err_code_t
595
_gcry_rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
984
985
static gcry_err_code_t
986
rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
596
987
{
597
988
RSA_secret_key sk;
598
989
610
1001
return GPG_ERR_NO_ERROR;
611
1002
}
612
1003
613
gcry_err_code_t
614
_gcry_rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1004
1005
static gcry_err_code_t
1006
rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
615
1007
int (*cmp) (void *opaque, gcry_mpi_t tmp),
616
1008
void *opaquev)
617
1009
{
642
1034
}
643
1035
644
1036
645
unsigned int
646
_gcry_rsa_get_nbits (int algo, gcry_mpi_t *pkey)
1037
static unsigned int
1038
rsa_get_nbits (int algo, gcry_mpi_t *pkey)
647
1039
{
648
1040
(void)algo;
649
1041
650
1042
return mpi_get_nbits (pkey[0]);
651
1043
}
652
1044
1045
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:
1050
1051
(rsa
1052
(n #00B...#)
1053
(e #010001#))
1054
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)
1061
{
1062
gcry_sexp_t l1;
1063
const char *data;
1064
size_t datalen;
1065
1066
l1 = gcry_sexp_find_token (keyparam, "n", 1);
1067
if (!l1)
1068
return GPG_ERR_NO_OBJ;
1069
1070
data = gcry_sexp_nth_data (l1, 1, &datalen);
1071
if (!data)
1072
{
1073
gcry_sexp_release (l1);
1074
return GPG_ERR_NO_OBJ;
1075
}
1076
1077
gcry_md_write (md, data, datalen);
1078
gcry_sexp_release (l1);
1079
1080
return 0;
1081
}
1082
1083
1084
1085
1086
/*
1087
Self-test section.
1088
*/
1089
1090
static const char *
1091
selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1092
{
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#))";
1099
1100
const char *errtxt = NULL;
1101
gcry_error_t err;
1102
gcry_sexp_t data = NULL;
1103
gcry_sexp_t data_bad = NULL;
1104
gcry_sexp_t sig = NULL;
1105
1106
err = gcry_sexp_sscan (&data, NULL,
1107
sample_data, strlen (sample_data));
1108
if (!err)
1109
err = gcry_sexp_sscan (&data_bad, NULL,
1110
sample_data_bad, strlen (sample_data_bad));
1111
if (err)
1112
{
1113
errtxt = "converting data failed";
1114
goto leave;
1115
}
1116
1117
err = gcry_pk_sign (&sig, data, skey);
1118
if (err)
1119
{
1120
errtxt = "signing failed";
1121
goto leave;
1122
}
1123
err = gcry_pk_verify (sig, data, pkey);
1124
if (err)
1125
{
1126
errtxt = "verify failed";
1127
goto leave;
1128
}
1129
err = gcry_pk_verify (sig, data_bad, pkey);
1130
if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1131
{
1132
errtxt = "bad signature not detected";
1133
goto leave;
1134
}
1135
1136
1137
leave:
1138
gcry_sexp_release (sig);
1139
gcry_sexp_release (data_bad);
1140
gcry_sexp_release (data);
1141
return errtxt;
1142
}
1143
1144
1145
1146
/* Given an S-expression ENCR_DATA of the form:
1147
1148
(enc-val
1149
(rsa
1150
(a a-value)))
1151
1152
as returned by gcry_pk_decrypt, return the the A-VALUE. On error,
1153
return NULL. */
1154
static gcry_mpi_t
1155
extract_a_from_sexp (gcry_sexp_t encr_data)
1156
{
1157
gcry_sexp_t l1, l2, l3;
1158
gcry_mpi_t a_value;
1159
1160
l1 = gcry_sexp_find_token (encr_data, "enc-val", 0);
1161
if (!l1)
1162
return NULL;
1163
l2 = gcry_sexp_find_token (l1, "rsa", 0);
1164
gcry_sexp_release (l1);
1165
if (!l2)
1166
return NULL;
1167
l3 = gcry_sexp_find_token (l2, "a", 0);
1168
gcry_sexp_release (l2);
1169
if (!l3)
1170
return NULL;
1171
a_value = gcry_sexp_nth_mpi (l3, 1, 0);
1172
gcry_sexp_release (l3);
1173
1174
return a_value;
1175
}
1176
1177
1178
static const char *
1179
selftest_encr_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1180
{
1181
const char *errtxt = NULL;
1182
gcry_error_t err;
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;
1191
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);
1195
1196
/* Put the plaintext into an S-expression. */
1197
err = gcry_sexp_build (&plain, NULL,
1198
"(data (flags raw) (value %m))", plaintext);
1199
if (err)
1200
{
1201
errtxt = "converting data failed";
1202
goto leave;
1203
}
1204
1205
/* Encrypt. */
1206
err = gcry_pk_encrypt (&encr, plain, pkey);
1207
if (err)
1208
{
1209
errtxt = "encrypt failed";
1210
goto leave;
1211
}
1212
1213
/* Extraxt the ciphertext from the returned S-expression. */
1214
/*gcry_sexp_dump (encr);*/
1215
ciphertext = extract_a_from_sexp (encr);
1216
if (!ciphertext)
1217
{
1218
errtxt = "gcry_pk_decrypt returned garbage";
1219
goto leave;
1220
}
1221
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))
1226
{
1227
errtxt = "ciphertext matches plaintext";
1228
goto leave;
1229
}
1230
1231
/* Decrypt. */
1232
err = gcry_pk_decrypt (&decr, encr, skey);
1233
if (err)
1234
{
1235
errtxt = "decrypt failed";
1236
goto leave;
1237
}
1238
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);
1246
if (tmplist)
1247
decr_plaintext = gcry_sexp_nth_mpi (tmplist, 1, GCRYMPI_FMT_USG);
1248
else
1249
decr_plaintext = gcry_sexp_nth_mpi (decr, 0, GCRYMPI_FMT_USG);
1250
if (!decr_plaintext)
1251
{
1252
errtxt = "decrypt returned no plaintext";
1253
goto leave;
1254
}
1255
1256
/* Check that the decrypted plaintext matches the original plaintext. */
1257
if (gcry_mpi_cmp (plaintext, decr_plaintext))
1258
{
1259
errtxt = "mismatch";
1260
goto leave;
1261
}
1262
1263
leave:
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);
1271
return errtxt;
1272
}
1273
1274
1275
static gpg_err_code_t
1276
selftests_rsa (selftest_report_func_t report)
1277
{
1278
const char *what;
1279
const char *errtxt;
1280
gcry_error_t err;
1281
gcry_sexp_t skey = NULL;
1282
gcry_sexp_t pkey = NULL;
1283
1284
/* Convert the S-expressions into the internal representation. */
1285
what = "convert";
1286
err = gcry_sexp_sscan (&skey, NULL,
1287
sample_secret_key, strlen (sample_secret_key));
1288
if (!err)
1289
err = gcry_sexp_sscan (&pkey, NULL,
1290
sample_public_key, strlen (sample_public_key));
1291
if (err)
1292
{
1293
errtxt = gcry_strerror (err);
1294
goto failed;
1295
}
1296
1297
what = "key consistency";
1298
err = gcry_pk_testkey (skey);
1299
if (err)
1300
{
1301
errtxt = gcry_strerror (err);
1302
goto failed;
1303
}
1304
1305
what = "sign";
1306
errtxt = selftest_sign_1024 (pkey, skey);
1307
if (errtxt)
1308
goto failed;
1309
1310
what = "encrypt";
1311
errtxt = selftest_encr_1024 (pkey, skey);
1312
if (errtxt)
1313
goto failed;
1314
1315
gcry_sexp_release (pkey);
1316
gcry_sexp_release (skey);
1317
return 0; /* Succeeded. */
1318
1319
failed:
1320
gcry_sexp_release (pkey);
1321
gcry_sexp_release (skey);
1322
if (report)
1323
report ("pubkey", GCRY_PK_RSA, what, errtxt);
1324
return GPG_ERR_SELFTEST_FAILED;
1325
}
1326
1327
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)
1331
{
1332
gpg_err_code_t ec;
1333
1334
(void)extended;
1335
1336
switch (algo)
1337
{
1338
case GCRY_PK_RSA:
1339
ec = selftests_rsa (report);
1340
break;
1341
default:
1342
ec = GPG_ERR_PUBKEY_ALGO;
1343
break;
1344
1345
}
1346
return ec;
1347
}
1348
1349
1350
1351
653
1352
static const char *rsa_names[] =
654
1353
{
655
1354
"rsa",
663
1362
"RSA", rsa_names,
664
1363
"ne", "nedpqu", "a", "s", "n",
665
1364
GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
666
_gcry_rsa_generate,
667
_gcry_rsa_check_secret_key,
668
_gcry_rsa_encrypt,
669
_gcry_rsa_decrypt,
670
_gcry_rsa_sign,
671
_gcry_rsa_verify,
672
_gcry_rsa_get_nbits,
673
};
1365
rsa_generate,
1366
rsa_check_secret_key,
1367
rsa_encrypt,
1368
rsa_decrypt,
1369
rsa_sign,
1370
rsa_verify,
1371
rsa_get_nbits,
1372
};
1373
pk_extra_spec_t _gcry_pubkey_extraspec_rsa =
1374
{
1375
run_selftests,
1376
rsa_generate_ext,
1377
compute_keygrip
1378
};
1379
Loggerhead is a web-based interface for Breezy
Version: 2.0.1