// Copyright 2015-2016 Brian Smith.
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use super::{
    bigint::{self, Prime},
    verification, RsaEncoding, N,
};
/// RSA PKCS#1 1.5 signatures.
use crate::{
    arithmetic::montgomery::R,
    bits, digest,
    error::{self, KeyRejected},
    io::{self, der, der_writer},
    pkcs8, rand, signature,
};
use alloc::boxed::Box;

/// An RSA key pair, used for signing.
pub struct RsaKeyPair {
    p: PrivatePrime<P>,
    q: PrivatePrime<Q>,
    qInv: bigint::Elem<P, R>,
    qq: bigint::Modulus<QQ>,
    q_mod_n: bigint::Elem<N, R>,
    public: verification::Key,
    public_key: RsaSubjectPublicKey,
}

derive_debug_via_field!(RsaKeyPair, stringify!(RsaKeyPair), public_key);

impl RsaKeyPair {
    /// Parses an unencrypted PKCS#8-encoded RSA private key.
    ///
    /// Only two-prime (not multi-prime) keys are supported. The public modulus
    /// (n) must be at least 2047 bits. The public modulus must be no larger
    /// than 4096 bits. It is recommended that the public modulus be exactly
    /// 2048 or 3072 bits. The public exponent must be at least 65537.
    ///
    /// This will generate a 2048-bit RSA private key of the correct form using
    /// OpenSSL's command line tool:
    ///
    /// ```sh
    ///    openssl genpkey -algorithm RSA \
    ///        -pkeyopt rsa_keygen_bits:2048 \
    ///        -pkeyopt rsa_keygen_pubexp:65537 | \
    ///      openssl pkcs8 -topk8 -nocrypt -outform der > rsa-2048-private-key.pk8
    /// ```
    ///
    /// This will generate a 3072-bit RSA private key of the correct form:
    ///
    /// ```sh
    ///    openssl genpkey -algorithm RSA \
    ///        -pkeyopt rsa_keygen_bits:3072 \
    ///        -pkeyopt rsa_keygen_pubexp:65537 | \
    ///      openssl pkcs8 -topk8 -nocrypt -outform der > rsa-3072-private-key.pk8
    /// ```
    ///
    /// Often, keys generated for use in OpenSSL-based software are stored in
    /// the Base64 “PEM” format without the PKCS#8 wrapper. Such keys can be
    /// converted to binary PKCS#8 form using the OpenSSL command line tool like
    /// this:
    ///
    /// ```sh
    /// openssl pkcs8 -topk8 -nocrypt -outform der \
    ///     -in rsa-2048-private-key.pem > rsa-2048-private-key.pk8
    /// ```
    ///
    /// Base64 (“PEM”) PKCS#8-encoded keys can be converted to the binary PKCS#8
    /// form like this:
    ///
    /// ```sh
    /// openssl pkcs8 -nocrypt -outform der \
    ///     -in rsa-2048-private-key.pem > rsa-2048-private-key.pk8
    /// ```
    ///
    /// The private key is validated according to [NIST SP-800-56B rev. 1]
    /// section 6.4.1.4.3, crt_pkv (Intended Exponent-Creation Method Unknown),
    /// with the following exceptions:
    ///
    /// * Section 6.4.1.2.1, Step 1: Neither a target security level nor an
    ///   expected modulus length is provided as a parameter, so checks
    ///   regarding these expectations are not done.
    /// * Section 6.4.1.2.1, Step 3: Since neither the public key nor the
    ///   expected modulus length is provided as a parameter, the consistency
    ///   check between these values and the private key's value of n isn't
    ///   done.
    /// * Section 6.4.1.2.1, Step 5: No primality tests are done, both for
    ///   performance reasons and to avoid any side channels that such tests
    ///   would provide.
    /// * Section 6.4.1.2.1, Step 6, and 6.4.1.4.3, Step 7:
    ///     * *ring* has a slightly looser lower bound for the values of `p`
    ///     and `q` than what the NIST document specifies. This looser lower
    ///     bound matches what most other crypto libraries do. The check might
    ///     be tightened to meet NIST's requirements in the future. Similarly,
    ///     the check that `p` and `q` are not too close together is skipped
    ///     currently, but may be added in the future.
    ///     - The validity of the mathematical relationship of `dP`, `dQ`, `e`
    ///     and `n` is verified only during signing. Some size checks of `d`,
    ///     `dP` and `dQ` are performed at construction, but some NIST checks
    ///     are skipped because they would be expensive and/or they would leak
    ///     information through side channels. If a preemptive check of the
    ///     consistency of `dP`, `dQ`, `e` and `n` with each other is
    ///     necessary, that can be done by signing any message with the key
    ///     pair.
    ///
    ///     * `d` is not fully validated, neither at construction nor during
    ///     signing. This is OK as far as *ring*'s usage of the key is
    ///     concerned because *ring* never uses the value of `d` (*ring* always
    ///     uses `p`, `q`, `dP` and `dQ` via the Chinese Remainder Theorem,
    ///     instead). However, *ring*'s checks would not be sufficient for
    ///     validating a key pair for use by some other system; that other
    ///     system must check the value of `d` itself if `d` is to be used.
    ///
    /// In addition to the NIST requirements, *ring* requires that `p > q` and
    /// that `e` must be no more than 33 bits.
    ///
    /// See [RFC 5958] and [RFC 3447 Appendix A.1.2] for more details of the
    /// encoding of the key.
    ///
    /// [NIST SP-800-56B rev. 1]:
    ///     http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br1.pdf
    ///
    /// [RFC 3447 Appendix A.1.2]:
    ///     https://tools.ietf.org/html/rfc3447#appendix-A.1.2
    ///
    /// [RFC 5958]:
    ///     https://tools.ietf.org/html/rfc5958
    pub fn from_pkcs8(pkcs8: &[u8]) -> Result<Self, KeyRejected> {
        const RSA_ENCRYPTION: &[u8] = include_bytes!("../data/alg-rsa-encryption.der");
        let (der, _) = pkcs8::unwrap_key_(
            untrusted::Input::from(&RSA_ENCRYPTION),
            pkcs8::Version::V1Only,
            untrusted::Input::from(pkcs8),
        )?;
        Self::from_der(der.as_slice_less_safe())
    }

    /// Parses an RSA private key that is not inside a PKCS#8 wrapper.
    ///
    /// The private key must be encoded as a binary DER-encoded ASN.1
    /// `RSAPrivateKey` as described in [RFC 3447 Appendix A.1.2]). In all other
    /// respects, this is just like `from_pkcs8()`. See the documentation for
    /// `from_pkcs8()` for more details.
    ///
    /// It is recommended to use `from_pkcs8()` (with a PKCS#8-encoded key)
    /// instead.
    ///
    /// [RFC 3447 Appendix A.1.2]:
    ///     https://tools.ietf.org/html/rfc3447#appendix-A.1.2
    ///
    /// [NIST SP-800-56B rev. 1]:
    ///     http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br1.pdf
    pub fn from_der(input: &[u8]) -> Result<Self, KeyRejected> {
        untrusted::Input::from(input).read_all(KeyRejected::invalid_encoding(), |input| {
            der::nested(
                input,
                der::Tag::Sequence,
                error::KeyRejected::invalid_encoding(),
                Self::from_der_reader,
            )
        })
    }

    fn from_der_reader(input: &mut untrusted::Reader) -> Result<Self, KeyRejected> {
        let version = der::small_nonnegative_integer(input)
            .map_err(|error::Unspecified| KeyRejected::invalid_encoding())?;
        if version != 0 {
            return Err(KeyRejected::version_not_supported());
        }

        fn positive_integer<'a>(
            input: &mut untrusted::Reader<'a>,
        ) -> Result<io::Positive<'a>, KeyRejected> {
            der::positive_integer(input)
                .map_err(|error::Unspecified| KeyRejected::invalid_encoding())
        }

        let n = positive_integer(input)?;
        let e = positive_integer(input)?;
        let d = positive_integer(input)?.big_endian_without_leading_zero_as_input();
        let p = positive_integer(input)?.big_endian_without_leading_zero_as_input();
        let q = positive_integer(input)?.big_endian_without_leading_zero_as_input();
        let dP = positive_integer(input)?.big_endian_without_leading_zero_as_input();
        let dQ = positive_integer(input)?.big_endian_without_leading_zero_as_input();
        let qInv = positive_integer(input)?.big_endian_without_leading_zero_as_input();

        let (p, p_bits) = bigint::Nonnegative::from_be_bytes_with_bit_length(p)
            .map_err(|error::Unspecified| KeyRejected::invalid_encoding())?;
        let (q, q_bits) = bigint::Nonnegative::from_be_bytes_with_bit_length(q)
            .map_err(|error::Unspecified| KeyRejected::invalid_encoding())?;

        // Our implementation of CRT-based modular exponentiation used requires
        // that `p > q` so swap them if `p < q`. If swapped, `qInv` is
        // recalculated below. `p != q` is verified implicitly below, e.g. when
        // `q_mod_p` is constructed.
        let ((p, p_bits, dP), (q, q_bits, dQ, qInv)) = match q.verify_less_than(&p) {
            Ok(_) => ((p, p_bits, dP), (q, q_bits, dQ, Some(qInv))),
            Err(error::Unspecified) => {
                // TODO: verify `q` and `qInv` are inverses (mod p).
                ((q, q_bits, dQ), (p, p_bits, dP, None))
            }
        };

        // XXX: Some steps are done out of order, but the NIST steps are worded
        // in such a way that it is clear that NIST intends for them to be done
        // in order. TODO: Does this matter at all?

        // 6.4.1.4.3/6.4.1.2.1 - Step 1.

        // Step 1.a is omitted, as explained above.

        // Step 1.b is omitted per above. Instead, we check that the public
        // modulus is 2048 to `PRIVATE_KEY_PUBLIC_MODULUS_MAX_BITS` bits.
        // XXX: The maximum limit of 4096 bits is primarily due to lack of
        // testing of larger key sizes; see, in particular,
        // https://www.mail-archive.com/openssl-dev@openssl.org/msg44586.html
        // and
        // https://www.mail-archive.com/openssl-dev@openssl.org/msg44759.html.
        // Also, this limit might help with memory management decisions later.

        // Step 1.c. We validate e >= 65537.
        let public_key = verification::Key::from_modulus_and_exponent(
            n.big_endian_without_leading_zero_as_input(),
            e.big_endian_without_leading_zero_as_input(),
            bits::BitLength::from_usize_bits(2048),
            super::PRIVATE_KEY_PUBLIC_MODULUS_MAX_BITS,
            65537,
        )?;

        // 6.4.1.4.3 says to skip 6.4.1.2.1 Step 2.

        // 6.4.1.4.3 Step 3.

        // Step 3.a is done below, out of order.
        // Step 3.b is unneeded since `n_bits` is derived here from `n`.

        // 6.4.1.4.3 says to skip 6.4.1.2.1 Step 4. (We don't need to recover
        // the prime factors since they are already given.)

        // 6.4.1.4.3 - Step 5.

        // Steps 5.a and 5.b are omitted, as explained above.

        // Step 5.c.
        //
        // TODO: First, stop if `p < (√2) * 2**((nBits/2) - 1)`.
        //
        // Second, stop if `p > 2**(nBits/2) - 1`.
        let half_n_bits = public_key.n_bits.half_rounded_up();
        if p_bits != half_n_bits {
            return Err(KeyRejected::inconsistent_components());
        }

        // TODO: Step 5.d: Verify GCD(p - 1, e) == 1.

        // Steps 5.e and 5.f are omitted as explained above.

        // Step 5.g.
        //
        // TODO: First, stop if `q < (√2) * 2**((nBits/2) - 1)`.
        //
        // Second, stop if `q > 2**(nBits/2) - 1`.
        if p_bits != q_bits {
            return Err(KeyRejected::inconsistent_components());
        }

        // TODO: Step 5.h: Verify GCD(p - 1, e) == 1.

        let q_mod_n_decoded = q
            .to_elem(&public_key.n)
            .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;

        // TODO: Step 5.i
        //
        // 3.b is unneeded since `n_bits` is derived here from `n`.

        // 6.4.1.4.3 - Step 3.a (out of order).
        //
        // Verify that p * q == n. We restrict ourselves to modular
        // multiplication. We rely on the fact that we've verified
        // 0 < q < p < n. We check that q and p are close to sqrt(n) and then
        // assume that these preconditions are enough to let us assume that
        // checking p * q == 0 (mod n) is equivalent to checking p * q == n.
        let q_mod_n = bigint::elem_mul(
            public_key.n.oneRR().as_ref(),
            q_mod_n_decoded.clone(),
            &public_key.n,
        );
        let p_mod_n = p
            .to_elem(&public_key.n)
            .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
        let pq_mod_n = bigint::elem_mul(&q_mod_n, p_mod_n, &public_key.n);
        if !pq_mod_n.is_zero() {
            return Err(KeyRejected::inconsistent_components());
        }

        // 6.4.1.4.3/6.4.1.2.1 - Step 6.

        // Step 6.a, partial.
        //
        // First, validate `2**half_n_bits < d`. Since 2**half_n_bits has a bit
        // length of half_n_bits + 1, this check gives us 2**half_n_bits <= d,
        // and knowing d is odd makes the inequality strict.
        let (d, d_bits) = bigint::Nonnegative::from_be_bytes_with_bit_length(d)
            .map_err(|_| error::KeyRejected::invalid_encoding())?;
        if !(half_n_bits < d_bits) {
            return Err(KeyRejected::inconsistent_components());
        }
        // XXX: This check should be `d < LCM(p - 1, q - 1)`, but we don't have
        // a good way of calculating LCM, so it is omitted, as explained above.
        d.verify_less_than_modulus(&public_key.n)
            .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;
        if !d.is_odd() {
            return Err(KeyRejected::invalid_component());
        }

        // Step 6.b is omitted as explained above.

        // 6.4.1.4.3 - Step 7.

        // Step 7.a.
        let p = PrivatePrime::new(p, dP)?;

        // Step 7.b.
        let q = PrivatePrime::new(q, dQ)?;

        let q_mod_p = q.modulus.to_elem(&p.modulus);

        // Step 7.c.
        let qInv = if let Some(qInv) = qInv {
            bigint::Elem::from_be_bytes_padded(qInv, &p.modulus)
                .map_err(|error::Unspecified| KeyRejected::invalid_component())?
        } else {
            // We swapped `p` and `q` above, so we need to calculate `qInv`.
            // Step 7.f below will verify `qInv` is correct.
            let q_mod_p = bigint::elem_mul(p.modulus.oneRR().as_ref(), q_mod_p.clone(), &p.modulus);
            bigint::elem_inverse_consttime(q_mod_p, &p.modulus)
                .map_err(|error::Unspecified| KeyRejected::unexpected_error())?
        };

        // Steps 7.d and 7.e are omitted per the documentation above, and
        // because we don't (in the long term) have a good way to do modulo
        // with an even modulus.

        // Step 7.f.
        let qInv = bigint::elem_mul(p.modulus.oneRR().as_ref(), qInv, &p.modulus);
        bigint::verify_inverses_consttime(&qInv, q_mod_p, &p.modulus)
            .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;

        let qq = bigint::elem_mul(&q_mod_n, q_mod_n_decoded, &public_key.n).into_modulus::<QQ>()?;

        let public_key_serialized = RsaSubjectPublicKey::from_n_and_e(n, e);

        Ok(Self {
            p,
            q,
            qInv,
            q_mod_n,
            qq,
            public: public_key,
            public_key: public_key_serialized,
        })
    }

    /// Returns the length in bytes of the key pair's public modulus.
    ///
    /// A signature has the same length as the public modulus.
    pub fn public_modulus_len(&self) -> usize {
        self.public_key
            .modulus()
            .big_endian_without_leading_zero_as_input()
            .as_slice_less_safe()
            .len()
    }
}

impl signature::KeyPair for RsaKeyPair {
    type PublicKey = RsaSubjectPublicKey;

    fn public_key(&self) -> &Self::PublicKey {
        &self.public_key
    }
}

/// A serialized RSA public key.
#[derive(Clone)]
pub struct RsaSubjectPublicKey(Box<[u8]>);

impl AsRef<[u8]> for RsaSubjectPublicKey {
    fn as_ref(&self) -> &[u8] {
        self.0.as_ref()
    }
}

derive_debug_self_as_ref_hex_bytes!(RsaSubjectPublicKey);

impl RsaSubjectPublicKey {
    fn from_n_and_e(n: io::Positive, e: io::Positive) -> Self {
        let bytes = der_writer::write_all(der::Tag::Sequence, &|output| {
            der_writer::write_positive_integer(output, &n);
            der_writer::write_positive_integer(output, &e);
        });
        RsaSubjectPublicKey(bytes)
    }

    /// The public modulus (n).
    pub fn modulus(&self) -> io::Positive {
        // Parsing won't fail because we serialized it ourselves.
        let (public_key, _exponent) =
            super::parse_public_key(untrusted::Input::from(self.as_ref())).unwrap();
        public_key
    }

    /// The public exponent (e).
    pub fn exponent(&self) -> io::Positive {
        // Parsing won't fail because we serialized it ourselves.
        let (_public_key, exponent) =
            super::parse_public_key(untrusted::Input::from(self.as_ref())).unwrap();
        exponent
    }
}

struct PrivatePrime<M: Prime> {
    modulus: bigint::Modulus<M>,
    exponent: bigint::PrivateExponent<M>,
}

impl<M: Prime + Clone> PrivatePrime<M> {
    /// Constructs a `PrivatePrime` from the private prime `p` and `dP` where
    /// dP == d % (p - 1).
    fn new(p: bigint::Nonnegative, dP: untrusted::Input) -> Result<Self, KeyRejected> {
        let (p, p_bits) = bigint::Modulus::from_nonnegative_with_bit_length(p)?;
        if p_bits.as_usize_bits() % 512 != 0 {
            return Err(error::KeyRejected::private_modulus_len_not_multiple_of_512_bits());
        }

        // [NIST SP-800-56B rev. 1] 6.4.1.4.3 - Steps 7.a & 7.b.
        let dP = bigint::PrivateExponent::from_be_bytes_padded(dP, &p)
            .map_err(|error::Unspecified| KeyRejected::inconsistent_components())?;

        // XXX: Steps 7.d and 7.e are omitted. We don't check that
        // `dP == d % (p - 1)` because we don't (in the long term) have a good
        // way to do modulo with an even modulus. Instead we just check that
        // `1 <= dP < p - 1`. We'll check it, to some unknown extent, when we
        // do the private key operation, since we verify that the result of the
        // private key operation using the CRT parameters is consistent with `n`
        // and `e`. TODO: Either prove that what we do is sufficient, or make
        // it so.

        Ok(PrivatePrime {
            modulus: p,
            exponent: dP,
        })
    }
}

fn elem_exp_consttime<M, MM>(
    c: &bigint::Elem<MM>,
    p: &PrivatePrime<M>,
) -> Result<bigint::Elem<M>, error::Unspecified>
where
    M: bigint::NotMuchSmallerModulus<MM>,
    M: Prime,
{
    let c_mod_m = bigint::elem_reduced(c, &p.modulus);
    // We could precompute `oneRRR = elem_squared(&p.oneRR`) as mentioned
    // in the Smooth CRT-RSA paper.
    let c_mod_m = bigint::elem_mul(p.modulus.oneRR().as_ref(), c_mod_m, &p.modulus);
    let c_mod_m = bigint::elem_mul(p.modulus.oneRR().as_ref(), c_mod_m, &p.modulus);
    bigint::elem_exp_consttime(c_mod_m, &p.exponent, &p.modulus)
}

// Type-level representations of the different moduli used in RSA signing, in
// addition to `super::N`. See `super::bigint`'s modulue-level documentation.

#[derive(Copy, Clone)]
enum P {}
unsafe impl Prime for P {}
unsafe impl bigint::SmallerModulus<N> for P {}
unsafe impl bigint::NotMuchSmallerModulus<N> for P {}

#[derive(Copy, Clone)]
enum QQ {}
unsafe impl bigint::SmallerModulus<N> for QQ {}
unsafe impl bigint::NotMuchSmallerModulus<N> for QQ {}

// `q < p < 2*q` since `q` is slightly smaller than `p` (see below). Thus:
//
//                         q <  p  < 2*q
//                       q*q < p*q < 2*q*q.
//                      q**2 <  n  < 2*(q**2).
unsafe impl bigint::SlightlySmallerModulus<N> for QQ {}

#[derive(Copy, Clone)]
enum Q {}
unsafe impl Prime for Q {}
unsafe impl bigint::SmallerModulus<N> for Q {}
unsafe impl bigint::SmallerModulus<P> for Q {}

// q < p && `p.bit_length() == q.bit_length()` implies `q < p < 2*q`.
unsafe impl bigint::SlightlySmallerModulus<P> for Q {}

unsafe impl bigint::SmallerModulus<QQ> for Q {}
unsafe impl bigint::NotMuchSmallerModulus<QQ> for Q {}

impl RsaKeyPair {
    /// Sign `msg`. `msg` is digested using the digest algorithm from
    /// `padding_alg` and the digest is then padded using the padding algorithm
    /// from `padding_alg`. The signature it written into `signature`;
    /// `signature`'s length must be exactly the length returned by
    /// `public_modulus_len()`. `rng` may be used to randomize the padding
    /// (e.g. for PSS).
    ///
    /// Many other crypto libraries have signing functions that takes a
    /// precomputed digest as input, instead of the message to digest. This
    /// function does *not* take a precomputed digest; instead, `sign`
    /// calculates the digest itself.
    ///
    /// Lots of effort has been made to make the signing operations close to
    /// constant time to protect the private key from side channel attacks. On
    /// x86-64, this is done pretty well, but not perfectly. On other
    /// platforms, it is done less perfectly.
    pub fn sign(
        &self,
        padding_alg: &'static dyn RsaEncoding,
        rng: &dyn rand::SecureRandom,
        msg: &[u8],
        signature: &mut [u8],
    ) -> Result<(), error::Unspecified> {
        let mod_bits = self.public.n_bits;
        if signature.len() != mod_bits.as_usize_bytes_rounded_up() {
            return Err(error::Unspecified);
        }

        let m_hash = digest::digest(padding_alg.digest_alg(), msg);
        padding_alg.encode(&m_hash, signature, mod_bits, rng)?;

        // RFC 8017 Section 5.1.2: RSADP, using the Chinese Remainder Theorem
        // with Garner's algorithm.

        let n = &self.public.n;

        // Step 1. The value zero is also rejected.
        let base = bigint::Elem::from_be_bytes_padded(untrusted::Input::from(signature), n)?;

        // Step 2
        let c = base;

        // Step 2.b.i.
        let m_1 = elem_exp_consttime(&c, &self.p)?;
        let c_mod_qq = bigint::elem_reduced_once(&c, &self.qq);
        let m_2 = elem_exp_consttime(&c_mod_qq, &self.q)?;

        // Step 2.b.ii isn't needed since there are only two primes.

        // Step 2.b.iii.
        let p = &self.p.modulus;
        let m_2 = bigint::elem_widen(m_2, p);
        let m_1_minus_m_2 = bigint::elem_sub(m_1, &m_2, p);
        let h = bigint::elem_mul(&self.qInv, m_1_minus_m_2, p);

        // Step 2.b.iv. The reduction in the modular multiplication isn't
        // necessary because `h < p` and `p * q == n` implies `h * q < n`.
        // Modular arithmetic is used simply to avoid implementing
        // non-modular arithmetic.
        let h = bigint::elem_widen(h, n);
        let q_times_h = bigint::elem_mul(&self.q_mod_n, h, n);
        let m_2 = bigint::elem_widen(m_2, n);
        let m = bigint::elem_add(m_2, q_times_h, n);

        // Step 2.b.v isn't needed since there are only two primes.

        // Verify the result to protect against fault attacks as described
        // in "On the Importance of Checking Cryptographic Protocols for
        // Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton.
        // This check is cheap assuming `e` is small, which is ensured during
        // `KeyPair` construction. Note that this is the only validation of `e`
        // that is done other than basic checks on its size, oddness, and
        // minimum value, since the relationship of `e` to `d`, `p`, and `q` is
        // not verified during `KeyPair` construction.
        {
            let verify = bigint::elem_exp_vartime(m.clone(), self.public.e, n);
            let verify = verify.into_unencoded(n);
            bigint::elem_verify_equal_consttime(&verify, &c)?;
        }

        // Step 3.
        //
        // See Falko Strenzke, "Manger's Attack revisited", ICICS 2010.
        m.fill_be_bytes(signature);

        Ok(())
    }
}

#[cfg(test)]
mod tests {
    // We intentionally avoid `use super::*` so that we are sure to use only
    // the public API; this ensures that enough of the API is public.
    use crate::{rand, signature};
    use alloc::vec;

    // `KeyPair::sign` requires that the output buffer is the same length as
    // the public key modulus. Test what happens when it isn't the same length.
    #[test]
    fn test_signature_rsa_pkcs1_sign_output_buffer_len() {
        // Sign the message "hello, world", using PKCS#1 v1.5 padding and the
        // SHA256 digest algorithm.
        const MESSAGE: &[u8] = b"hello, world";
        let rng = rand::SystemRandom::new();

        const PRIVATE_KEY_DER: &[u8] = include_bytes!("signature_rsa_example_private_key.der");
        let key_pair = signature::RsaKeyPair::from_der(PRIVATE_KEY_DER).unwrap();

        // The output buffer is one byte too short.
        let mut signature = vec![0; key_pair.public_modulus_len() - 1];

        assert!(key_pair
            .sign(&signature::RSA_PKCS1_SHA256, &rng, MESSAGE, &mut signature)
            .is_err());

        // The output buffer is the right length.
        signature.push(0);
        assert!(key_pair
            .sign(&signature::RSA_PKCS1_SHA256, &rng, MESSAGE, &mut signature)
            .is_ok());

        // The output buffer is one byte too long.
        signature.push(0);
        assert!(key_pair
            .sign(&signature::RSA_PKCS1_SHA256, &rng, MESSAGE, &mut signature)
            .is_err());
    }
}