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.
7 * This file is part of Libgcrypt.
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.
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.
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/>.
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.
36 gcry_mpi_t n
; /* modulus */
37 gcry_mpi_t e
; /* exponent */
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. */
52 /* A sample 1024 bit RSA key used for the selftests. */
53 static const char sample_secret_key
[] =
56 " (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
57 " 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
58 " ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
59 " 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
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
[] =
75 " (n #00e0ce96f90b6c9e02f3922beada93fe50a875eac6bcc18bb9a9cf2e84965caa"
76 " 2d1ff95a7f542465c6c0c19d276e4526ce048868a7a914fd343cc3a87dd74291"
77 " ffc565506d5bbb25cbac6a0e2dd1f8bcaab0d4a29c2f37c950f363484bf269f7"
78 " 891440464baf79827e03a36e70b814938eebdc63e964247be75dc58b014b7ea251#)"
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
);
90 /* Check that a freshly generated key actually works. Returns 0 on success. */
92 test_keys (RSA_secret_key
*sk
, unsigned int nbits
)
94 int result
= -1; /* Default to failure. */
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
);
101 /* Put the relevant parameters into a public key structure. */
105 /* Create a random plaintext. */
106 gcry_mpi_randomize (plaintext
, nbits
, GCRY_WEAK_RANDOM
);
108 /* Encrypt using the public key. */
109 public (ciphertext
, plaintext
, &pk
);
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. */
115 /* Decrypt using the secret key. */
116 secret (decr_plaintext
, ciphertext
, sk
);
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. */
122 /* Create another random plaintext as data for signature checking. */
123 gcry_mpi_randomize (plaintext
, nbits
, GCRY_WEAK_RANDOM
);
125 /* Use the RSA secret function to create a signature of the plaintext. */
126 secret (signature
, plaintext
, sk
);
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. */
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. */
139 result
= 0; /* All tests succeeded. */
142 gcry_mpi_release (signature
);
143 gcry_mpi_release (decr_plaintext
);
144 gcry_mpi_release (ciphertext
);
145 gcry_mpi_release (plaintext
);
150 /* Callback used by the prime generation to test whether the exponent
151 is suitable. Returns 0 if the test has been passed. */
153 check_exponent (void *arg
, gcry_mpi_t a
)
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);
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
177 static gpg_err_code_t
178 generate_std (RSA_secret_key
*sk
, unsigned int nbits
, unsigned long use_e
,
181 gcry_mpi_t p
, q
; /* the two primes */
182 gcry_mpi_t d
; /* the private key */
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) */
190 gcry_random_level_t random_level
;
195 return GPG_ERR_INV_VALUE
;
197 return GPG_ERR_INV_VALUE
;
200 /* The random quality depends on the transient_key flag. */
201 random_level
= transient_key
? GCRY_STRONG_RANDOM
: GCRY_VERY_STRONG_RANDOM
;
203 /* Make sure that nbits is even so that we generate p, q of equal size. */
207 if (use_e
== 1) /* Alias for a secure value */
208 use_e
= 65537; /* as demanded by Sphinx. */
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):
219 e
= mpi_alloc( (32+BITS_PER_MPI_LIMB
-1)/BITS_PER_MPI_LIMB
);
221 mpi_set_ui (e
, 41); /* This is a reasonable secure and fast value */
224 use_e
|= 1; /* make sure this is odd */
225 mpi_set_ui (e
, use_e
);
228 n
= gcry_mpi_new (nbits
);
233 /* select two (very secret) primes */
235 gcry_mpi_release (p
);
237 gcry_mpi_release (q
);
239 { /* Do an extra test to ensure that the given exponent is
241 p
= _gcry_generate_secret_prime (nbits
/2, random_level
,
243 q
= _gcry_generate_secret_prime (nbits
/2, random_level
,
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
);
251 if (mpi_cmp (p
, q
) > 0 ) /* p shall be smaller than q (for calc of u)*/
253 /* calculate the modulus */
256 while ( mpi_get_nbits(n
) != nbits
);
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
);
270 while (!gcry_mpi_gcd(t1
, e
, phi
)) /* (while gcd is not 1) */
273 BUG (); /* The prime generator already made sure that we
274 never can get to here. */
275 mpi_add_ui (e
, e
, 2);
278 /* calculate the secret key d = e^1 mod phi */
279 d
= gcry_mpi_snew ( nbits
);
281 /* calculate the inverse of p and q (used for chinese remainder theorem)*/
282 u
= gcry_mpi_snew ( nbits
);
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
);
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
);
311 /* Now we can test our keys. */
312 if (test_keys (sk
, nbits
- 64))
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
;
328 /* Helper for generate_x931. */
330 gen_x931_parm_xp (unsigned int nbits
)
334 xp
= gcry_mpi_snew (nbits
);
335 gcry_mpi_randomize (xp
, nbits
, GCRY_VERY_STRONG_RANDOM
);
337 /* The requirement for Xp is:
339 sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
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
);
352 /* Helper for generate_x931. */
354 gen_x931_parm_xi (void)
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 );
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
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
)
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. */
388 if (e_value
== 1) /* Alias for a secure value. */
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
;
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
400 return GPG_ERR_INV_VALUE
;
402 /* Our implementaion requires E to be odd. */
404 return GPG_ERR_INV_VALUE
;
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. */
410 /* Compute or extract the derive parameters. */
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
;
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);
428 gcry_mpi_release (xq
);
429 xq
= gen_x931_parm_xp (nbits
/2);
430 mpi_sub (tmpval
, xp
, xq
);
432 while (mpi_get_nbits (tmpval
) <= (nbits
/2 - 100));
433 gcry_mpi_release (tmpval
);
435 xp1
= gen_x931_parm_xi ();
436 xp2
= gen_x931_parm_xi ();
437 xq1
= gen_x931_parm_xi ();
438 xq2
= gen_x931_parm_xi ();
443 /* Parameters to derive the key are given. */
444 struct { const char *name
; gcry_mpi_t
*value
; } tbl
[] = {
456 for (idx
=0; tbl
[idx
].name
; idx
++)
458 oneparm
= gcry_sexp_find_token (deriveparms
, tbl
[idx
].name
, 0);
461 *tbl
[idx
].value
= gcry_sexp_nth_mpi (oneparm
, 1,
463 gcry_sexp_release (oneparm
);
466 for (idx
=0; tbl
[idx
].name
; idx
++)
467 if (!*tbl
[idx
].value
)
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
;
478 e
= mpi_alloc_set_ui (e_value
);
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
;
491 gcry_mpi_release (p
);
492 gcry_mpi_release (q
);
493 gcry_mpi_release (e
);
494 return GPG_ERR_NO_PRIME
;
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 )
506 n
= gcry_mpi_new (nbits
);
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
);
517 g
= gcry_mpi_snew (nbits
);
518 gcry_assert (gcry_mpi_gcd (g
, e
, phi
));
520 /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
521 gcry_mpi_gcd (g
, pm1
, qm1
);
523 gcry_mpi_release (qm1
); qm1
= NULL
;
524 mpi_fdiv_q (f
, phi
, g
);
525 gcry_mpi_release (phi
); phi
= NULL
;
527 /* Compute the secret key: d = e^{-1} mod lcm(p-1,q-1) */
530 /* Compute the inverse of p and q. */
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
);
554 /* Now we can test our keys. */
555 if (test_keys (sk
, nbits
- 64))
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
;
572 * Test wether the secret key is valid.
573 * Returns: true if this is a valid key.
576 check_secret_key( RSA_secret_key
*sk
)
579 gcry_mpi_t temp
= mpi_alloc( mpi_get_nlimbs(sk
->p
)*2 );
581 mpi_mul(temp
, sk
->p
, sk
->q
);
582 rc
= mpi_cmp( temp
, sk
->n
);
590 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
594 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
597 public(gcry_mpi_t output
, gcry_mpi_t input
, RSA_public_key
*pkey
)
599 if( output
== input
) /* powm doesn't like output and input the same */
601 gcry_mpi_t x
= mpi_alloc( mpi_get_nlimbs(input
)*2 );
602 mpi_powm( x
, input
, pkey
->e
, pkey
->n
);
607 mpi_powm( output
, input
, pkey
->e
, pkey
->n
);
612 stronger_key_check ( RSA_secret_key
*skey
)
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 );
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" );
624 /* check that p is less than q */
625 if( mpi_cmp( skey
->p
, skey
->q
) > 0 )
627 log_info ("RSA Oops: p >= q - fixed\n");
628 _gcry_mpi_swap ( skey
->p
, skey
->q
);
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" );
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
) )
650 log_info ( "RSA Oops: d is wrong - fixed\n");
651 mpi_set (skey
->d
, t
);
652 _gcry_log_mpidump (" fixed d", skey
->d
);
655 /* check for correctness of u */
656 mpi_invm(t
, skey
->p
, skey
->q
);
657 if ( mpi_cmp(t
, skey
->u
) )
659 log_info ( "RSA Oops: u is wrong - fixed\n");
660 mpi_set (skey
->u
, t
);
661 _gcry_log_mpidump (" fixed u", skey
->u
);
664 log_info ( "RSA secret key check finished\n");
676 * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
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
687 * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
690 secret(gcry_mpi_t output
, gcry_mpi_t input
, RSA_secret_key
*skey
)
692 if (!skey
->p
|| !skey
->q
|| !skey
->u
)
694 mpi_powm (output
, input
, skey
->d
, skey
->n
);
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 );
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
);
716 mpi_mul ( h
, h
, skey
->p
);
717 mpi_add ( output
, m1
, h
);
727 /* Perform RSA blinding. */
729 rsa_blind (gcry_mpi_t x
, gcry_mpi_t r
, gcry_mpi_t e
, gcry_mpi_t n
)
737 a
= gcry_mpi_snew (gcry_mpi_get_nbits (n
));
738 y
= gcry_mpi_snew (gcry_mpi_get_nbits (n
));
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
);
746 gcry_mpi_release (a
);
751 /* Undo RSA blinding. */
753 rsa_unblind (gcry_mpi_t x
, gcry_mpi_t ri
, gcry_mpi_t n
)
757 y
= gcry_mpi_snew (gcry_mpi_get_nbits (n
));
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. */
763 gcry_mpi_mulm (y
, ri
, x
, n
);
768 /*********************************************
769 ************** interface ******************
770 *********************************************/
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
)
780 gcry_sexp_t deriveparms
;
781 int transient_key
= 0;
787 *retfactors
= NULL
; /* We don't return them. */
789 deriveparms
= (genparms
?
790 gcry_sexp_find_token (genparms
, "derive-parms", 0) : NULL
);
793 /* Parse the optional "use-x931" flag. */
794 l1
= gcry_sexp_find_token (genparms
, "use-x931", 0);
798 gcry_sexp_release (l1
);
802 if (deriveparms
|| use_x931
|| fips_mode ())
805 ec
= generate_x931 (&sk
, nbits
, evalue
, deriveparms
, &swapped
);
806 gcry_sexp_release (deriveparms
);
807 if (!ec
&& r_extrainfo
&& swapped
)
809 ec
= gcry_sexp_new (r_extrainfo
,
810 "(misc-key-info(p-q-swapped))", 0, 1);
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
;
824 /* Parse the optional "transient-key" flag. */
825 l1
= gcry_sexp_find_token (genparms
, "transient-key", 0);
829 gcry_sexp_release (l1
);
832 ec
= generate_std (&sk
, nbits
, evalue
, transient_key
);
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
)
853 return rsa_generate_ext (algo
, nbits
, evalue
, NULL
, skey
, retfactors
, NULL
);
857 static gcry_err_code_t
858 rsa_check_secret_key (int algo
, gcry_mpi_t
*skey
)
860 gcry_err_code_t err
= GPG_ERR_NO_ERROR
;
872 if (!sk
.p
|| !sk
.q
|| !sk
.u
)
873 err
= GPG_ERR_NO_OBJ
; /* To check the key we need the optional
875 else if (!check_secret_key (&sk
))
876 err
= GPG_ERR_PUBKEY_ALGO
;
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
)
893 resarr
[0] = mpi_alloc (mpi_get_nlimbs (pk
.n
));
894 public (resarr
[0], data
, &pk
);
896 return GPG_ERR_NO_ERROR
;
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
)
905 gcry_mpi_t r
= MPI_NULL
; /* Random number needed for blinding. */
906 gcry_mpi_t ri
= MPI_NULL
; /* Modular multiplicative inverse of
908 gcry_mpi_t x
= MPI_NULL
; /* Data to decrypt. */
909 gcry_mpi_t y
; /* Result. */
913 /* Extract private key. */
917 sk
.p
= skey
[3]; /* Optional. */
918 sk
.q
= skey
[4]; /* Optional. */
919 sk
.u
= skey
[5]; /* Optional. */
921 y
= gcry_mpi_snew (gcry_mpi_get_nbits (sk
.n
));
923 /* We use blinding by default to mitigate timing attacks which can
924 be practically mounted over the network as shown by Brumley and
926 if (! (flags
& PUBKEY_FLAG_NO_BLINDING
))
928 /* Initialize blinding. */
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
));
938 gcry_mpi_randomize (r
, gcry_mpi_get_nbits (sk
.n
), GCRY_WEAK_RANDOM
);
939 gcry_mpi_mod (r
, r
, sk
.n
);
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
;
948 if (! (flags
& PUBKEY_FLAG_NO_BLINDING
))
949 x
= rsa_blind (data
[0], r
, sk
.e
, sk
.n
);
953 /* Do the encryption. */
956 if (! (flags
& PUBKEY_FLAG_NO_BLINDING
))
959 gcry_mpi_t a
= gcry_mpi_copy (y
);
961 gcry_mpi_release (y
);
962 y
= rsa_unblind (a
, ri
, sk
.n
);
964 gcry_mpi_release (a
);
967 if (! (flags
& PUBKEY_FLAG_NO_BLINDING
))
969 /* Deallocate resources needed for blinding. */
970 gcry_mpi_release (x
);
971 gcry_mpi_release (r
);
972 gcry_mpi_release (ri
);
975 /* Copy out result. */
978 return GPG_ERR_NO_ERROR
;
982 static gcry_err_code_t
983 rsa_sign (int algo
, gcry_mpi_t
*resarr
, gcry_mpi_t data
, gcry_mpi_t
*skey
)
995 resarr
[0] = mpi_alloc( mpi_get_nlimbs (sk
.n
));
996 secret (resarr
[0], data
, &sk
);
998 return GPG_ERR_NO_ERROR
;
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
),
1017 result
= gcry_mpi_new ( 160 );
1018 public( result
, data
[0], &pk
);
1019 #ifdef IS_DEVELOPMENT_VERSION
1022 log_mpidump ("rsa verify result:", result
);
1023 log_mpidump (" hash:", hash
);
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
);
1035 rsa_get_nbits (int algo
, gcry_mpi_t
*pkey
)
1039 return mpi_get_nbits (pkey
[0]);
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:
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
)
1063 l1
= gcry_sexp_find_token (keyparam
, "n", 1);
1065 return GPG_ERR_NO_OBJ
;
1067 data
= gcry_sexp_nth_data (l1
, 1, &datalen
);
1070 gcry_sexp_release (l1
);
1071 return GPG_ERR_NO_OBJ
;
1074 gcry_md_write (md
, data
, datalen
);
1075 gcry_sexp_release (l1
);
1090 /* Given an S-expression ENCR_DATA of the form:
1096 as returned by gcry_pk_decrypt, return the the A-VALUE. On error,
1099 extract_a_from_sexp (gcry_sexp_t encr_data
)
1101 gcry_sexp_t l1
, l2
, l3
;
1104 l1
= gcry_sexp_find_token (encr_data
, "enc-val", 0);
1107 l2
= gcry_sexp_find_token (l1
, "rsa", 0);
1108 gcry_sexp_release (l1
);
1111 l3
= gcry_sexp_find_token (l2
, "a", 0);
1112 gcry_sexp_release (l2
);
1115 a_value
= gcry_sexp_nth_mpi (l3
, 1, 0);
1116 gcry_sexp_release (l3
);
1126 /* Run a full self-test for ALGO and return 0 on success. */
1131 static const char *rsa_names
[] =
1135 "oid.1.2.840.113549.1.1.1",
1139 gcry_pk_spec_t _gcry_pubkey_spec_rsa
=
1142 "ne", "nedpqu", "a", "s", "n",
1143 GCRY_PK_USAGE_SIGN
| GCRY_PK_USAGE_ENCR
,
1145 rsa_check_secret_key
,
1152 pk_extra_spec_t _gcry_pubkey_extraspec_rsa
=