1// Copyright 2015-2016 Brian Smith.
2//
3// Permission to use, copy, modify, and/or distribute this software for any
4// purpose with or without fee is hereby granted, provided that the above
5// copyright notice and this permission notice appear in all copies.
6//
7// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
8// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
10// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
14
15use super::{
16 padding::RsaEncoding, KeyPairComponents, PublicExponent, PublicKey, PublicKeyComponents, N,
17};
18
19/// RSA PKCS#1 1.5 signatures.
20use crate::{
21 arithmetic::{
22 bigint,
23 montgomery::{R, RR, RRR},
24 LimbSliceError,
25 },
26 bits::BitLength,
27 cpu, digest,
28 error::{self, KeyRejected},
29 io::der,
30 pkcs8, rand, signature,
31};
32
33/// An RSA key pair, used for signing.
34pub struct KeyPair {
35 p: PrivateCrtPrime<P>,
36 q: PrivateCrtPrime<Q>,
37 qInv: bigint::Elem<P, R>,
38 public: PublicKey,
39}
40
41derive_debug_via_field!(KeyPair, stringify!(RsaKeyPair), public);
42
43impl KeyPair {
44 /// Parses an unencrypted PKCS#8-encoded RSA private key.
45 ///
46 /// This will generate a 2048-bit RSA private key of the correct form using
47 /// OpenSSL's command line tool:
48 ///
49 /// ```sh
50 /// openssl genpkey -algorithm RSA \
51 /// -pkeyopt rsa_keygen_bits:2048 \
52 /// -pkeyopt rsa_keygen_pubexp:65537 | \
53 /// openssl pkcs8 -topk8 -nocrypt -outform der > rsa-2048-private-key.pk8
54 /// ```
55 ///
56 /// This will generate a 3072-bit RSA private key of the correct form:
57 ///
58 /// ```sh
59 /// openssl genpkey -algorithm RSA \
60 /// -pkeyopt rsa_keygen_bits:3072 \
61 /// -pkeyopt rsa_keygen_pubexp:65537 | \
62 /// openssl pkcs8 -topk8 -nocrypt -outform der > rsa-3072-private-key.pk8
63 /// ```
64 ///
65 /// Often, keys generated for use in OpenSSL-based software are stored in
66 /// the Base64 “PEM” format without the PKCS#8 wrapper. Such keys can be
67 /// converted to binary PKCS#8 form using the OpenSSL command line tool like
68 /// this:
69 ///
70 /// ```sh
71 /// openssl pkcs8 -topk8 -nocrypt -outform der \
72 /// -in rsa-2048-private-key.pem > rsa-2048-private-key.pk8
73 /// ```
74 ///
75 /// Base64 (“PEM”) PKCS#8-encoded keys can be converted to the binary PKCS#8
76 /// form like this:
77 ///
78 /// ```sh
79 /// openssl pkcs8 -nocrypt -outform der \
80 /// -in rsa-2048-private-key.pem > rsa-2048-private-key.pk8
81 /// ```
82 ///
83 /// See [`Self::from_components`] for more details on how the input is
84 /// validated.
85 ///
86 /// See [RFC 5958] and [RFC 3447 Appendix A.1.2] for more details of the
87 /// encoding of the key.
88 ///
89 /// [NIST SP-800-56B rev. 1]:
90 /// http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br1.pdf
91 ///
92 /// [RFC 3447 Appendix A.1.2]:
93 /// https://tools.ietf.org/html/rfc3447#appendix-A.1.2
94 ///
95 /// [RFC 5958]:
96 /// https://tools.ietf.org/html/rfc5958
97 pub fn from_pkcs8(pkcs8: &[u8]) -> Result<Self, KeyRejected> {
98 const RSA_ENCRYPTION: &[u8] = include_bytes!("../data/alg-rsa-encryption.der");
99 let (der, _) = pkcs8::unwrap_key_(
100 untrusted::Input::from(RSA_ENCRYPTION),
101 pkcs8::Version::V1Only,
102 untrusted::Input::from(pkcs8),
103 )?;
104 Self::from_der(der.as_slice_less_safe())
105 }
106
107 /// Parses an RSA private key that is not inside a PKCS#8 wrapper.
108 ///
109 /// The private key must be encoded as a binary DER-encoded ASN.1
110 /// `RSAPrivateKey` as described in [RFC 3447 Appendix A.1.2]). In all other
111 /// respects, this is just like `from_pkcs8()`. See the documentation for
112 /// `from_pkcs8()` for more details.
113 ///
114 /// It is recommended to use `from_pkcs8()` (with a PKCS#8-encoded key)
115 /// instead.
116 ///
117 /// See [`Self::from_components()`] for more details on how the input is
118 /// validated.
119 ///
120 /// [RFC 3447 Appendix A.1.2]:
121 /// https://tools.ietf.org/html/rfc3447#appendix-A.1.2
122 ///
123 /// [NIST SP-800-56B rev. 1]:
124 /// http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br1.pdf
125 pub fn from_der(input: &[u8]) -> Result<Self, KeyRejected> {
126 untrusted::Input::from(input).read_all(KeyRejected::invalid_encoding(), |input| {
127 der::nested(
128 input,
129 der::Tag::Sequence,
130 KeyRejected::invalid_encoding(),
131 Self::from_der_reader,
132 )
133 })
134 }
135
136 fn from_der_reader(input: &mut untrusted::Reader) -> Result<Self, KeyRejected> {
137 let version = der::small_nonnegative_integer(input)
138 .map_err(|error::Unspecified| KeyRejected::invalid_encoding())?;
139 if version != 0 {
140 return Err(KeyRejected::version_not_supported());
141 }
142
143 fn nonnegative_integer<'a>(
144 input: &mut untrusted::Reader<'a>,
145 ) -> Result<&'a [u8], KeyRejected> {
146 der::nonnegative_integer(input)
147 .map(|input| input.as_slice_less_safe())
148 .map_err(|error::Unspecified| KeyRejected::invalid_encoding())
149 }
150
151 let n = nonnegative_integer(input)?;
152 let e = nonnegative_integer(input)?;
153 let d = nonnegative_integer(input)?;
154 let p = nonnegative_integer(input)?;
155 let q = nonnegative_integer(input)?;
156 let dP = nonnegative_integer(input)?;
157 let dQ = nonnegative_integer(input)?;
158 let qInv = nonnegative_integer(input)?;
159
160 let components = KeyPairComponents {
161 public_key: PublicKeyComponents { n, e },
162 d,
163 p,
164 q,
165 dP,
166 dQ,
167 qInv,
168 };
169
170 Self::from_components(&components)
171 }
172
173 /// Constructs an RSA private key from its big-endian-encoded components.
174 ///
175 /// Only two-prime (not multi-prime) keys are supported. The public modulus
176 /// (n) must be at least 2047 bits. The public modulus must be no larger
177 /// than 4096 bits. It is recommended that the public modulus be exactly
178 /// 2048 or 3072 bits. The public exponent must be at least 65537 and must
179 /// be no more than 33 bits long.
180 ///
181 /// The private key is validated according to [NIST SP-800-56B rev. 1]
182 /// section 6.4.1.4.3, crt_pkv (Intended Exponent-Creation Method Unknown),
183 /// with the following exceptions:
184 ///
185 /// * Section 6.4.1.2.1, Step 1: Neither a target security level nor an
186 /// expected modulus length is provided as a parameter, so checks
187 /// regarding these expectations are not done.
188 /// * Section 6.4.1.2.1, Step 3: Since neither the public key nor the
189 /// expected modulus length is provided as a parameter, the consistency
190 /// check between these values and the private key's value of n isn't
191 /// done.
192 /// * Section 6.4.1.2.1, Step 5: No primality tests are done, both for
193 /// performance reasons and to avoid any side channels that such tests
194 /// would provide.
195 /// * Section 6.4.1.2.1, Step 6, and 6.4.1.4.3, Step 7:
196 /// * *ring* has a slightly looser lower bound for the values of `p`
197 /// and `q` than what the NIST document specifies. This looser lower
198 /// bound matches what most other crypto libraries do. The check might
199 /// be tightened to meet NIST's requirements in the future. Similarly,
200 /// the check that `p` and `q` are not too close together is skipped
201 /// currently, but may be added in the future.
202 /// * The validity of the mathematical relationship of `dP`, `dQ`, `e`
203 /// and `n` is verified only during signing. Some size checks of `d`,
204 /// `dP` and `dQ` are performed at construction, but some NIST checks
205 /// are skipped because they would be expensive and/or they would leak
206 /// information through side channels. If a preemptive check of the
207 /// consistency of `dP`, `dQ`, `e` and `n` with each other is
208 /// necessary, that can be done by signing any message with the key
209 /// pair.
210 ///
211 /// * `d` is not fully validated, neither at construction nor during
212 /// signing. This is OK as far as *ring*'s usage of the key is
213 /// concerned because *ring* never uses the value of `d` (*ring* always
214 /// uses `p`, `q`, `dP` and `dQ` via the Chinese Remainder Theorem,
215 /// instead). However, *ring*'s checks would not be sufficient for
216 /// validating a key pair for use by some other system; that other
217 /// system must check the value of `d` itself if `d` is to be used.
218 pub fn from_components<Public, Private>(
219 components: &KeyPairComponents<Public, Private>,
220 ) -> Result<Self, KeyRejected>
221 where
222 Public: AsRef<[u8]>,
223 Private: AsRef<[u8]>,
224 {
225 let components = KeyPairComponents {
226 public_key: PublicKeyComponents {
227 n: components.public_key.n.as_ref(),
228 e: components.public_key.e.as_ref(),
229 },
230 d: components.d.as_ref(),
231 p: components.p.as_ref(),
232 q: components.q.as_ref(),
233 dP: components.dP.as_ref(),
234 dQ: components.dQ.as_ref(),
235 qInv: components.qInv.as_ref(),
236 };
237 Self::from_components_(&components, cpu::features())
238 }
239
240 fn from_components_(
241 &KeyPairComponents {
242 public_key,
243 d,
244 p,
245 q,
246 dP,
247 dQ,
248 qInv,
249 }: &KeyPairComponents<&[u8]>,
250 cpu_features: cpu::Features,
251 ) -> Result<Self, KeyRejected> {
252 let d = untrusted::Input::from(d);
253 let p = untrusted::Input::from(p);
254 let q = untrusted::Input::from(q);
255 let dP = untrusted::Input::from(dP);
256 let dQ = untrusted::Input::from(dQ);
257 let qInv = untrusted::Input::from(qInv);
258
259 // XXX: Some steps are done out of order, but the NIST steps are worded
260 // in such a way that it is clear that NIST intends for them to be done
261 // in order. TODO: Does this matter at all?
262
263 // 6.4.1.4.3/6.4.1.2.1 - Step 1.
264
265 // Step 1.a is omitted, as explained above.
266
267 // Step 1.b is omitted per above. Instead, we check that the public
268 // modulus is 2048 to `PRIVATE_KEY_PUBLIC_MODULUS_MAX_BITS` bits.
269 // XXX: The maximum limit of 4096 bits is primarily due to lack of
270 // testing of larger key sizes; see, in particular,
271 // https://www.mail-archive.com/openssl-dev@openssl.org/msg44586.html
272 // and
273 // https://www.mail-archive.com/openssl-dev@openssl.org/msg44759.html.
274 // Also, this limit might help with memory management decisions later.
275
276 // Step 1.c. We validate e >= 65537.
277 let n = untrusted::Input::from(public_key.n);
278 let e = untrusted::Input::from(public_key.e);
279 let public_key = PublicKey::from_modulus_and_exponent(
280 n,
281 e,
282 BitLength::from_bits(2048),
283 super::PRIVATE_KEY_PUBLIC_MODULUS_MAX_BITS,
284 PublicExponent::_65537,
285 cpu_features,
286 )?;
287
288 let n_one = public_key.inner().n().oneRR();
289 let n = &public_key.inner().n().value(cpu_features);
290
291 // 6.4.1.4.3 says to skip 6.4.1.2.1 Step 2.
292
293 // 6.4.1.4.3 Step 3.
294
295 // Step 3.a is done below, out of order.
296 // Step 3.b is unneeded since `n_bits` is derived here from `n`.
297
298 // 6.4.1.4.3 says to skip 6.4.1.2.1 Step 4. (We don't need to recover
299 // the prime factors since they are already given.)
300
301 // 6.4.1.4.3 - Step 5.
302
303 // Steps 5.a and 5.b are omitted, as explained above.
304
305 let n_bits = public_key.inner().n().len_bits();
306
307 let p = PrivatePrime::new(p, n_bits, cpu_features)?;
308 let q = PrivatePrime::new(q, n_bits, cpu_features)?;
309
310 // TODO: Step 5.i
311 //
312 // 3.b is unneeded since `n_bits` is derived here from `n`.
313
314 // 6.4.1.4.3 - Step 3.a (out of order).
315 //
316 // Verify that p * q == n. We restrict ourselves to modular
317 // multiplication. We rely on the fact that we've verified
318 // 0 < q < p < n. We check that q and p are close to sqrt(n) and then
319 // assume that these preconditions are enough to let us assume that
320 // checking p * q == 0 (mod n) is equivalent to checking p * q == n.
321 let q_mod_n = q
322 .modulus
323 .to_elem(n)
324 .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
325 let p_mod_n = p
326 .modulus
327 .to_elem(n)
328 .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
329 let p_mod_n = bigint::elem_mul(n_one, p_mod_n, n);
330 let pq_mod_n = bigint::elem_mul(&q_mod_n, p_mod_n, n);
331 if !pq_mod_n.is_zero() {
332 return Err(KeyRejected::inconsistent_components());
333 }
334
335 // 6.4.1.4.3/6.4.1.2.1 - Step 6.
336
337 // Step 6.a, partial.
338 //
339 // First, validate `2**half_n_bits < d`. Since 2**half_n_bits has a bit
340 // length of half_n_bits + 1, this check gives us 2**half_n_bits <= d,
341 // and knowing d is odd makes the inequality strict.
342 let d = bigint::OwnedModulusValue::<D>::from_be_bytes(d)
343 .map_err(|_| KeyRejected::invalid_component())?;
344 if !(n_bits.half_rounded_up() < d.len_bits()) {
345 return Err(KeyRejected::inconsistent_components());
346 }
347 // XXX: This check should be `d < LCM(p - 1, q - 1)`, but we don't have
348 // a good way of calculating LCM, so it is omitted, as explained above.
349 d.verify_less_than(n)
350 .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
351
352 // Step 6.b is omitted as explained above.
353
354 let pm = &p.modulus.modulus(cpu_features);
355
356 // 6.4.1.4.3 - Step 7.
357
358 // Step 7.c.
359 let qInv = bigint::Elem::from_be_bytes_padded(qInv, pm)
360 .map_err(|error::Unspecified| KeyRejected::invalid_component())?;
361
362 // Steps 7.d and 7.e are omitted per the documentation above, and
363 // because we don't (in the long term) have a good way to do modulo
364 // with an even modulus.
365
366 // Step 7.f.
367 let qInv = bigint::elem_mul(p.oneRR.as_ref(), qInv, pm);
368 let q_mod_p = bigint::elem_reduced(pm.alloc_zero(), &q_mod_n, pm, q.modulus.len_bits());
369 let q_mod_p = bigint::elem_mul(p.oneRR.as_ref(), q_mod_p, pm);
370 bigint::verify_inverses_consttime(&qInv, q_mod_p, pm)
371 .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
372
373 // This should never fail since `n` and `e` were validated above.
374
375 let p = PrivateCrtPrime::new(p, dP, cpu_features)?;
376 let q = PrivateCrtPrime::new(q, dQ, cpu_features)?;
377
378 Ok(Self {
379 p,
380 q,
381 qInv,
382 public: public_key,
383 })
384 }
385
386 /// Returns a reference to the public key.
387 pub fn public(&self) -> &PublicKey {
388 &self.public
389 }
390
391 /// Returns the length in bytes of the key pair's public modulus.
392 ///
393 /// A signature has the same length as the public modulus.
394 #[deprecated = "Use `public().modulus_len()`"]
395 #[inline]
396 pub fn public_modulus_len(&self) -> usize {
397 self.public().modulus_len()
398 }
399}
400
401impl signature::KeyPair for KeyPair {
402 type PublicKey = PublicKey;
403
404 fn public_key(&self) -> &Self::PublicKey {
405 self.public()
406 }
407}
408
409struct PrivatePrime<M> {
410 modulus: bigint::OwnedModulus<M>,
411 oneRR: bigint::One<M, RR>,
412}
413
414impl<M> PrivatePrime<M> {
415 fn new(
416 p: untrusted::Input,
417 n_bits: BitLength,
418 cpu_features: cpu::Features,
419 ) -> Result<Self, KeyRejected> {
420 let p = bigint::OwnedModulusValue::from_be_bytes(p)?;
421
422 // 5.c / 5.g:
423 //
424 // TODO: First, stop if `p < (√2) * 2**((nBits/2) - 1)`.
425 // TODO: First, stop if `q < (√2) * 2**((nBits/2) - 1)`.
426 //
427 // Second, stop if `p > 2**(nBits/2) - 1`.
428 // Second, stop if `q > 2**(nBits/2) - 1`.
429 if p.len_bits() != n_bits.half_rounded_up() {
430 return Err(KeyRejected::inconsistent_components());
431 }
432
433 if p.len_bits().as_bits() % 512 != 0 {
434 return Err(KeyRejected::private_modulus_len_not_multiple_of_512_bits());
435 }
436
437 // TODO: Step 5.d: Verify GCD(p - 1, e) == 1.
438 // TODO: Step 5.h: Verify GCD(q - 1, e) == 1.
439
440 // Steps 5.e and 5.f are omitted as explained above.
441 let p = bigint::OwnedModulus::from(p);
442 let pm = p.modulus(cpu_features);
443 let oneRR = bigint::One::newRR(pm.alloc_zero(), &pm);
444
445 Ok(Self { modulus: p, oneRR })
446 }
447}
448
449struct PrivateCrtPrime<M> {
450 modulus: bigint::OwnedModulus<M>,
451 oneRRR: bigint::One<M, RRR>,
452 exponent: bigint::PrivateExponent,
453}
454
455impl<M> PrivateCrtPrime<M> {
456 /// Constructs a `PrivateCrtPrime` from the private prime `p` and `dP` where
457 /// dP == d % (p - 1).
458 fn new(
459 p: PrivatePrime<M>,
460 dP: untrusted::Input,
461 cpu_features: cpu::Features,
462 ) -> Result<Self, KeyRejected> {
463 let m = &p.modulus.modulus(cpu_features);
464 // [NIST SP-800-56B rev. 1] 6.4.1.4.3 - Steps 7.a & 7.b.
465 let dP = bigint::PrivateExponent::from_be_bytes_padded(dP, m)
466 .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
467
468 // XXX: Steps 7.d and 7.e are omitted. We don't check that
469 // `dP == d % (p - 1)` because we don't (in the long term) have a good
470 // way to do modulo with an even modulus. Instead we just check that
471 // `1 <= dP < p - 1`. We'll check it, to some unknown extent, when we
472 // do the private key operation, since we verify that the result of the
473 // private key operation using the CRT parameters is consistent with `n`
474 // and `e`. TODO: Either prove that what we do is sufficient, or make
475 // it so.
476
477 let oneRRR = bigint::One::newRRR(p.oneRR, m);
478
479 Ok(Self {
480 modulus: p.modulus,
481 oneRRR,
482 exponent: dP,
483 })
484 }
485}
486
487fn elem_exp_consttime<M>(
488 c: &bigint::Elem<N>,
489 p: &PrivateCrtPrime<M>,
490 other_prime_len_bits: BitLength,
491 cpu_features: cpu::Features,
492) -> Result<bigint::Elem<M>, error::Unspecified> {
493 let m: &Modulus<'_, M> = &p.modulus.modulus(cpu_features);
494 bigint::elem_exp_consttime(
495 m.alloc_zero(),
496 c,
497 &p.oneRRR,
498 &p.exponent,
499 m,
500 other_prime_len_bits,
501 )
502 .map_err(op:error::erase::<LimbSliceError>)
503}
504
505// Type-level representations of the different moduli used in RSA signing, in
506// addition to `super::N`. See `super::bigint`'s modulue-level documentation.
507
508enum P {}
509
510enum Q {}
511
512enum D {}
513
514impl KeyPair {
515 /// Computes the signature of `msg` and writes it into `signature`.
516 ///
517 /// `msg` is digested using the digest algorithm from `padding_alg` and the
518 /// digest is then padded using the padding algorithm from `padding_alg`.
519 ///
520 /// The signature it written into `signature`; `signature`'s length must be
521 /// exactly the length returned by `self::public().modulus_len()` or else
522 /// an error will be returned. On failure, `signature` may contain
523 /// intermediate results, but won't contain anything that would endanger the
524 /// private key.
525 ///
526 /// `rng` may be used to randomize the padding (e.g. for PSS).
527 ///
528 /// Many other crypto libraries have signing functions that takes a
529 /// precomputed digest as input, instead of the message to digest. This
530 /// function does *not* take a precomputed digest; instead, `sign`
531 /// calculates the digest itself.
532 pub fn sign(
533 &self,
534 padding_alg: &'static dyn RsaEncoding,
535 rng: &dyn rand::SecureRandom,
536 msg: &[u8],
537 signature: &mut [u8],
538 ) -> Result<(), error::Unspecified> {
539 let cpu_features = cpu::features();
540
541 if signature.len() != self.public().modulus_len() {
542 return Err(error::Unspecified);
543 }
544
545 let m_hash = digest::digest(padding_alg.digest_alg(), msg);
546
547 // Use the output buffer as the scratch space for the signature to
548 // reduce the required stack space.
549 padding_alg.encode(m_hash, signature, self.public().inner().n().len_bits(), rng)?;
550
551 // RFC 8017 Section 5.1.2: RSADP, using the Chinese Remainder Theorem
552 // with Garner's algorithm.
553
554 // Steps 1 and 2.
555 let m = self.private_exponentiate(signature, cpu_features)?;
556
557 // Step 3.
558 m.fill_be_bytes(signature);
559
560 Ok(())
561 }
562
563 /// Returns base**d (mod n).
564 ///
565 /// This does not return or write any intermediate results into any buffers
566 /// that are provided by the caller so that no intermediate state will be
567 /// leaked that would endanger the private key.
568 ///
569 /// Panics if `in_out` is not `self.public().modulus_len()`.
570 fn private_exponentiate(
571 &self,
572 base: &[u8],
573 cpu_features: cpu::Features,
574 ) -> Result<bigint::Elem<N>, error::Unspecified> {
575 assert_eq!(base.len(), self.public().modulus_len());
576
577 // RFC 8017 Section 5.1.2: RSADP, using the Chinese Remainder Theorem
578 // with Garner's algorithm.
579
580 let n = &self.public.inner().n().value(cpu_features);
581 let n_one = self.public.inner().n().oneRR();
582
583 // Step 1. The value zero is also rejected.
584 let base = bigint::Elem::from_be_bytes_padded(untrusted::Input::from(base), n)?;
585
586 // Step 2
587 let c = base;
588
589 // Step 2.b.i.
590 let q_bits = self.q.modulus.len_bits();
591 let m_1 = elem_exp_consttime(&c, &self.p, q_bits, cpu_features)?;
592 let m_2 = elem_exp_consttime(&c, &self.q, self.p.modulus.len_bits(), cpu_features)?;
593
594 // Step 2.b.ii isn't needed since there are only two primes.
595
596 // Step 2.b.iii.
597 let h = {
598 let p = &self.p.modulus.modulus(cpu_features);
599 let m_2 = bigint::elem_reduced_once(p.alloc_zero(), &m_2, p, q_bits);
600 let m_1_minus_m_2 = bigint::elem_sub(m_1, &m_2, p);
601 bigint::elem_mul(&self.qInv, m_1_minus_m_2, p)
602 };
603
604 // Step 2.b.iv. The reduction in the modular multiplication isn't
605 // necessary because `h < p` and `p * q == n` implies `h * q < n`.
606 // Modular arithmetic is used simply to avoid implementing
607 // non-modular arithmetic.
608 let p_bits = self.p.modulus.len_bits();
609 let h = bigint::elem_widen(n.alloc_zero(), h, n, p_bits)?;
610 let q_mod_n = self.q.modulus.to_elem(n)?;
611 let q_mod_n = bigint::elem_mul(n_one, q_mod_n, n);
612 let q_times_h = bigint::elem_mul(&q_mod_n, h, n);
613 let m_2 = bigint::elem_widen(n.alloc_zero(), m_2, n, q_bits)?;
614 let m = bigint::elem_add(m_2, q_times_h, n);
615
616 // Step 2.b.v isn't needed since there are only two primes.
617
618 // Verify the result to protect against fault attacks as described
619 // in "On the Importance of Checking Cryptographic Protocols for
620 // Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton.
621 // This check is cheap assuming `e` is small, which is ensured during
622 // `KeyPair` construction. Note that this is the only validation of `e`
623 // that is done other than basic checks on its size, oddness, and
624 // minimum value, since the relationship of `e` to `d`, `p`, and `q` is
625 // not verified during `KeyPair` construction.
626 {
627 let verify = n.alloc_zero();
628 let verify = self
629 .public
630 .inner()
631 .exponentiate_elem(verify, &m, cpu_features);
632 bigint::elem_verify_equal_consttime(&verify, &c)?;
633 }
634
635 // Step 3 will be done by the caller.
636
637 Ok(m)
638 }
639}
640
641#[cfg(test)]
642mod tests {
643 use super::*;
644 use crate::test;
645 use alloc::vec;
646
647 #[test]
648 fn test_rsakeypair_private_exponentiate() {
649 let cpu = cpu::features();
650 test::run(
651 test_file!("keypair_private_exponentiate_tests.txt"),
652 |section, test_case| {
653 assert_eq!(section, "");
654
655 let key = test_case.consume_bytes("Key");
656 let key = KeyPair::from_pkcs8(&key).unwrap();
657 let test_cases = &[
658 test_case.consume_bytes("p"),
659 test_case.consume_bytes("p_plus_1"),
660 test_case.consume_bytes("p_minus_1"),
661 test_case.consume_bytes("q"),
662 test_case.consume_bytes("q_plus_1"),
663 test_case.consume_bytes("q_minus_1"),
664 ];
665 for test_case in test_cases {
666 // THe call to `elem_verify_equal_consttime` will cause
667 // `private_exponentiate` to fail if the computation is
668 // incorrect.
669 let mut padded = vec![0; key.public.modulus_len()];
670 let zeroes = padded.len() - test_case.len();
671 padded[zeroes..].copy_from_slice(test_case);
672 let _: bigint::Elem<_> = key.private_exponentiate(&padded, cpu).unwrap();
673 }
674 Ok(())
675 },
676 );
677 }
678}
679