polyjose 0.2.0

//! The PKCS#1 RSA key structures (RFC 8017 App. A.1): the RSAPublicKey
//! (App. A.1.1), standalone as OpenSSL's `RSA PUBLIC KEY` and inside the
//! SPKI subjectPublicKey, and the two-prime RSAPrivateKey (App. A.1.2),
//! standalone as OpenSSL's `RSA PRIVATE KEY` and inside the PKCS#8
//! privateKey of rsaEncryption (ADR 0067 §2). Every INTEGER is positive and
//! minimal (X.690 §8.3).
//!
//! ```text
//! RSAPublicKey ::= SEQUENCE {
//!     modulus           INTEGER,  -- n
//!     publicExponent    INTEGER   -- e
//! }
//!
//! RSAPrivateKey ::= SEQUENCE {
//!     version           Version,  -- two-prime(0) or multi(1)
//!     modulus           INTEGER,  -- n
//!     publicExponent    INTEGER,  -- e
//!     privateExponent   INTEGER,  -- d
//!     prime1            INTEGER,  -- p
//!     prime2            INTEGER,  -- q
//!     exponent1         INTEGER,  -- d mod (p-1)
//!     exponent2         INTEGER,  -- d mod (q-1)
//!     coefficient       INTEGER,  -- (inverse of q) mod p
//!     otherPrimeInfos   OtherPrimeInfos OPTIONAL
//! }
//! ```
//!
//! Only the encoding is checked here. What makes the INTEGERs a usable key
//! (at least 2048 bits, odd `n`, odd `e` with 3 ≤ e < n, and a private key
//! consistent with its public part; RFC 7518 §3.3, §4.2, RFC 8017 §3.1,
//! §3.2, ADR 0007, ADR 0043) is checked once, by `Jwk::from_object`, when
//! `rsa.rs` builds the JWK.
//!
//! # Secrets
//!
//! An RSAPrivateKey's INTEGERs are borrowed from the caller's DER buffer,
//! which must be a zeroizing one, and [`encode_private`] writes into a
//! zeroizing buffer. Their minimal-encoding check (`der::Reader::
//! unsigned_integer`) looks at the first two contents octets only; nothing
//! else about a secret INTEGER is branched on here, and no error carries its
//! octets (ADR 0007).

use core::fmt;

use zeroize::Zeroizing;

use super::der::{self, Reader, Writer};
use crate::error::{Error, Result};

/// The two RSAPublicKey INTEGERs as unsigned big-endian magnitudes in the
/// fewest octets (the DER sign octet removed, X.690 §8.3.3), the form JWK's
/// Base64urlUInt needs (RFC 7518 §2, §6.3.1). Both borrow from the decoded
/// DER. The values are public, so they need no zeroization.
#[derive(Clone, Copy)]
pub(crate) struct RsaPublicParts<'a> {
    /// `modulus`, n (RFC 8017 App. A.1.1).
    pub(crate) n: &'a [u8],
    /// `publicExponent`, e (RFC 8017 App. A.1.1).
    pub(crate) e: &'a [u8],
}

/// The eight INTEGERs of a two-prime RSAPrivateKey (RFC 8017 App. A.1.2) as
/// unsigned big-endian magnitudes in the fewest octets, the form of the
/// JWK's Base64urlUInt members (RFC 7518 §2, §6.3.1, §6.3.2). They borrow
/// from a zeroizing DER buffer. `Debug` shows `n` and `e` only.
#[derive(Clone, Copy)]
pub(crate) struct RsaPrivateFields<'a> {
    /// `modulus`, n (JWK `n`, RFC 7518 §6.3.1.1).
    pub(crate) n: &'a [u8],
    /// `publicExponent`, e (JWK `e`, RFC 7518 §6.3.1.2).
    pub(crate) e: &'a [u8],
    /// `privateExponent`, d (JWK `d`, RFC 7518 §6.3.2.1). Secret.
    pub(crate) d: &'a [u8],
    /// `prime1`, p (JWK `p`, RFC 7518 §6.3.2.2). Secret.
    pub(crate) p: &'a [u8],
    /// `prime2`, q (JWK `q`, RFC 7518 §6.3.2.3). Secret.
    pub(crate) q: &'a [u8],
    /// `exponent1`, d mod (p − 1) (JWK `dp`, RFC 7518 §6.3.2.4). Secret.
    pub(crate) dp: &'a [u8],
    /// `exponent2`, d mod (q − 1) (JWK `dq`, RFC 7518 §6.3.2.5). Secret.
    pub(crate) dq: &'a [u8],
    /// `coefficient`, q⁻¹ mod p (JWK `qi`, RFC 7518 §6.3.2.6). Secret.
    pub(crate) qi: &'a [u8],
}

impl fmt::Debug for RsaPrivateFields<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("RsaPrivateFields")
            .field("n_len", &self.n.len())
            .field("e_len", &self.e.len())
            .field("private", &"<redacted>")
            .finish()
    }
}

/// A standalone PKCS#1 key (`KeyFormat::Pkcs1`): either structure of
/// RFC 8017 App. A.1.
pub(crate) enum Pkcs1Key<'a> {
    /// An RSAPublicKey (App. A.1.1).
    Public(RsaPublicParts<'a>),
    /// A two-prime RSAPrivateKey (App. A.1.2).
    Private(RsaPrivateFields<'a>),
}

/// Decodes a DER RSAPublicKey (RFC 8017 App. A.1.1), as found in the
/// subjectPublicKey of an rsaEncryption SPKI (RFC 3279 §2.3.1: the key
/// "MUST" be an RSAPublicKey) and under OpenSSL's `RSA PUBLIC KEY` label:
/// one SEQUENCE of exactly two non-negative, minimal INTEGERs (X.690
/// §8.3.2), with no data after it (§8.1.1).
///
/// # Errors
///
/// [`Error::InvalidKey`] for anything else: a negative or non-minimal
/// INTEGER, a missing or extra field (an RSAPrivateKey among them),
/// trailing data.
pub(crate) fn decode_public(der: &[u8]) -> Result<RsaPublicParts<'_>> {
    let mut outer = Reader::new(der)?;
    let fields = outer.sequence()?;
    outer.finish()?;
    read_public(fields)
}

/// Decodes a DER RSAPrivateKey (RFC 8017 App. A.1.2): the body of OpenSSL's
/// `RSA PRIVATE KEY` label and the privateKey of a PKCS#8 rsaEncryption key
/// (RFC 8017 App. A.1.2: "the RSA private key SHALL have ASN.1 type
/// RSAPrivateKey"). See [`read_private`].
///
/// # Errors
///
/// As [`read_private`]; an RSAPublicKey or any other shape is
/// [`Error::InvalidKey`].
pub(crate) fn decode_private(der: &[u8]) -> Result<RsaPrivateFields<'_>> {
    let mut outer = Reader::new(der)?;
    let fields = outer.sequence()?;
    outer.finish()?;
    if !has_private_key_shape(fields) {
        return Err(Error::InvalidKey("PKCS#1 key is not an RSAPrivateKey"));
    }
    read_private(fields)
}

/// Decodes standalone PKCS#1 DER, the `KeyFormat::Pkcs1` input: an
/// RSAPublicKey (RFC 8017 App. A.1.1) or an RSAPrivateKey (App. A.1.2).
///
/// The two structures share an outer SEQUENCE of INTEGERs, so they are told
/// apart by shape:
///
/// - Exactly two INTEGERs: RSAPublicKey, checked as in [`decode_public`].
/// - A first INTEGER of 0 (`two-prime`) or 1 (`multi`), the `Version` of
///   App. A.1.2, followed by eight or more INTEGERs: RSAPrivateKey, checked
///   as in [`decode_private`]. An RSAPublicKey can never look like this: it
///   has two INTEGERs, and its first is a modulus of at least 2048 bits.
/// - Anything else: [`Error::InvalidKey`].
///
/// # Errors
///
/// [`Error::UnsupportedAlgorithm`] for a multi-prime RSAPrivateKey
/// (ADR 0067 §3); [`Error::InvalidKey`] for everything malformed.
pub(crate) fn decode(der: &[u8]) -> Result<Pkcs1Key<'_>> {
    let mut outer = Reader::new(der)?;
    let fields = outer.sequence()?;
    outer.finish()?;
    if has_private_key_shape(fields) {
        return read_private(fields).map(Pkcs1Key::Private);
    }
    read_public(fields).map(Pkcs1Key::Public)
}

/// How many INTEGERs follow `version` in every RSAPrivateKey (RFC 8017
/// App. A.1.2): modulus, publicExponent, privateExponent, prime1, prime2,
/// exponent1, exponent2 and coefficient.
const PRIVATE_KEY_INTEGERS: usize = 8;

/// Whether the SEQUENCE contents `fields` have the shape of an RSAPrivateKey
/// (RFC 8017 App. A.1.2): a version INTEGER whose contents are exactly 0x00
/// (two-prime) or 0x01 (multi), then at least [`PRIVATE_KEY_INTEGERS`]
/// elements tagged INTEGER. This reads framing only; [`read_private`]
/// parses the fields.
fn has_private_key_shape(mut fields: Reader<'_>) -> bool {
    let Ok(version) = fields.expect(der::INTEGER) else {
        return false;
    };
    if !matches!(version.contents, [0x00] | [0x01]) {
        return false;
    }
    (0..PRIVATE_KEY_INTEGERS).all(|_| {
        fields
            .element()
            .is_ok_and(|element| element.tag == der::INTEGER)
    })
}

/// Reads the fields of an RSAPrivateKey SEQUENCE (RFC 8017 App. A.1.2).
///
/// - `version` two-prime(0): eight non-negative minimal INTEGERs
///   ([`Reader::unsigned_integer`], X.690 §8.3) and nothing after them.
/// - `version` multi(1), which App. A.1.2 requires when otherPrimeInfos is
///   present (a key of more than two primes): [`Error::UnsupportedAlgorithm`]
///   (ADR 0067 §3, as the JWK `oth`), before any INTEGER after the version
///   is parsed.
///
/// # Errors
///
/// [`Error::UnsupportedAlgorithm`] for version multi; [`Error::InvalidKey`]
/// for any other version, a malformed or negative INTEGER, or data after
/// the eighth.
fn read_private(mut fields: Reader<'_>) -> Result<RsaPrivateFields<'_>> {
    match fields.small_unsigned()? {
        0 => {}
        1 => return Err(Error::UnsupportedAlgorithm),
        _ => return Err(Error::InvalidKey("RSAPrivateKey version is not two-prime")),
    }
    let key = RsaPrivateFields {
        n: fields.unsigned_integer()?,
        e: fields.unsigned_integer()?,
        d: fields.unsigned_integer()?,
        p: fields.unsigned_integer()?,
        q: fields.unsigned_integer()?,
        dp: fields.unsigned_integer()?,
        dq: fields.unsigned_integer()?,
        qi: fields.unsigned_integer()?,
    };
    if !fields.is_empty() {
        return Err(Error::InvalidKey(
            "two-prime RSAPrivateKey holds more than its eight INTEGERs",
        ));
    }
    Ok(key)
}

/// Reads the fields of an RSAPublicKey SEQUENCE: `modulus` and
/// `publicExponent`, each a non-negative minimal INTEGER
/// ([`Reader::unsigned_integer`], X.690 §8.3), and nothing else
/// (RFC 8017 App. A.1.1).
fn read_public(mut fields: Reader<'_>) -> Result<RsaPublicParts<'_>> {
    let n = fields.unsigned_integer()?;
    let e = fields.unsigned_integer()?;
    if !fields.is_empty() {
        return Err(Error::InvalidKey(
            "RSAPublicKey holds more than modulus and publicExponent",
        ));
    }
    Ok(RsaPublicParts { n, e })
}

/// Encodes an RSAPublicKey (RFC 8017 App. A.1.1) in DER from the unsigned
/// magnitudes `n` and `e`: each a minimal INTEGER with a 0x00 sign octet
/// where the top bit is set (X.690 §8.3.2, §8.3.3), the layout OpenSSL 4
/// emits (ADR 0018 §3).
pub(crate) fn encode_public(n: &[u8], e: &[u8]) -> Result<Zeroizing<Vec<u8>>> {
    let body = der::unsigned_integer_len(n) + der::unsigned_integer_len(e);
    let mut writer = Writer::new(der::encoded_len(body))?;
    writer.header(der::SEQUENCE, body)?;
    writer.unsigned_integer(n)?;
    writer.unsigned_integer(e)?;
    writer.finish()
}

/// Encodes a two-prime RSAPrivateKey (RFC 8017 App. A.1.2) in DER: version
/// two-prime(0), then the eight INTEGERs of `key`, each minimal with a sign
/// octet where needed (X.690 §8.3.2, §8.3.3), the layout OpenSSL 4 emits
/// (ADR 0018 §3). The output is zeroized on drop.
pub(crate) fn encode_private(key: &RsaPrivateFields<'_>) -> Result<Zeroizing<Vec<u8>>> {
    let ints = [key.n, key.e, key.d, key.p, key.q, key.dp, key.dq, key.qi];
    let body = der::unsigned_integer_len(&[0])
        + ints
            .iter()
            .map(|int| der::unsigned_integer_len(int))
            .sum::<usize>();
    let mut writer = Writer::new(der::encoded_len(body))?;
    writer.header(der::SEQUENCE, body)?;
    writer.unsigned_integer(&[0])?;
    for int in ints {
        writer.unsigned_integer(int)?;
    }
    writer.finish()
}

#[cfg(test)]
mod tests {
    use super::super::der::fixtures;
    use super::*;
    use crate::util::b64url_decode;

    fn is_invalid<T>(result: &Result<T>) -> bool {
        matches!(result, Err(Error::InvalidKey(_)))
    }

    /// RFC 7517 App. A.1, the RSA public key: `n` and `e` as Base64urlUInt
    /// (RFC 7518 §6.3.1.1, §6.3.1.2).
    const A1_N: &str = "0vx7agoebGcQSuuPiLJXZptN9nndrQmbXEps2aiAFbWhM78LhWx4cbbfAAtVT86zwu1RK7aPFFxuhDR1L6tSoc_BJECPebWKRXjBZCiFV4n3oknjhMstn64tZ_2W-5JsGY4Hc5n9yBXArwl93lqt7_RN5w6Cf0h4QyQ5v-65YGjQR0_FDW2QvzqY368QQMicAtaSqzs8KJZgnYb9c7d0zgdAZHzu6qMQvRL5hajrn1n91CbOpbISD08qNLyrdkt-bFTWhAI4vMQFh6WeZu0fM4lFd2NcRwr3XPksINHaQ-G_xBniIqbw0Ls1jF44-csFCur-kEgU8awapJzKnqDKgw";

    /// Every positive standalone RSAPublicKey fixture, as DER.
    fn public_fixtures() -> Vec<(&'static str, String)> {
        let mut out = Vec::new();
        for dir in ["openssl", "rfc"] {
            for file in fixtures::files(dir, |name| {
                name.contains("-pkcs1-pub") && !name.starts_with("reject-")
            }) {
                out.push((dir, file));
            }
        }
        assert_eq!(
            out.len(),
            5,
            "rsa2048 (der, pem), rsa4096 (pem), RFC 7517 A.1 (der, pem)"
        );
        out
    }

    #[test]
    fn rfc7517_a1_rsa_public_key_decodes_to_its_n_and_e() {
        // RFC 7517 App. A.1 as PKCS#1: `n` with its DER sign octet removed
        // is exactly the JWK's minimal `n`, and e is 65537 (AQAB).
        let der = fixtures::load("rfc", "rfc7517-a1-rsa-pkcs1-pub.der");
        let key = decode_public(&der).unwrap();
        assert_eq!(key.n, b64url_decode(A1_N).unwrap().as_slice());
        assert_eq!(key.e, &[0x01, 0x00, 0x01]);
        // The modulus's top bit is set, so DER carries a 0x00 sign octet
        // (X.690 §8.3.3) that the magnitude does not.
        assert_eq!(key.n.len(), 256);
        assert!(key.n[0] & 0x80 != 0);
    }

    #[test]
    fn every_public_fixture_decodes_and_re_encodes_to_its_bytes() {
        // ADR 0018 §3: export in the layout OpenSSL 4 emits.
        for (dir, file) in public_fixtures() {
            let der = fixtures::load(dir, &file);
            let key = decode_public(&der).unwrap_or_else(|e| panic!("{file}: {e:?}"));
            assert_ne!(key.n[0], 0, "{file}: n is minimal");
            let again = encode_public(key.n, key.e).unwrap();
            assert_eq!(&again[..], &der[..], "{file}");
        }
    }

    #[test]
    fn decode_borrows_the_input() {
        let der = fixtures::load("rfc", "rfc7517-a1-rsa-pkcs1-pub.der");
        let key = decode_public(&der).unwrap();
        let range = der.as_ptr_range();
        assert!(range.contains(&key.n.as_ptr()));
        assert!(range.contains(&key.e.as_ptr()));
    }

    #[test]
    fn encode_adds_the_sign_octet_only_where_needed() {
        // X.690 §8.3.2, §8.3.3: 0x80 needs a leading 0x00, 0x7F does not;
        // leading zero octets in the input are not significant.
        let der = encode_public(&[0x80, 0x01], &[0x00, 0x03]).unwrap();
        assert_eq!(
            &der[..],
            &[0x30, 0x08, 0x02, 0x03, 0x00, 0x80, 0x01, 0x02, 0x01, 0x03]
        );
        let der = encode_public(&[0x7F], &[0x03]).unwrap();
        assert_eq!(&der[..], &[0x30, 0x06, 0x02, 0x01, 0x7F, 0x02, 0x01, 0x03]);
    }

    #[test]
    fn malformed_rsa_public_keys_are_invalid() {
        // RFC 8017 App. A.1.1: exactly modulus and publicExponent, both
        // positive (X.690 §8.3.3) and minimal (§8.3.2).
        for (what, der) in [
            ("empty", vec![]),
            ("empty SEQUENCE", vec![0x30, 0x00]),
            ("one INTEGER", vec![0x30, 0x03, 0x02, 0x01, 0x05]),
            (
                "three INTEGERs",
                vec![
                    0x30, 0x09, 0x02, 0x01, 0x05, 0x02, 0x01, 0x03, 0x02, 0x01, 0x03,
                ],
            ),
            (
                "negative n",
                vec![0x30, 0x06, 0x02, 0x01, 0x85, 0x02, 0x01, 0x03],
            ),
            (
                "negative e",
                vec![0x30, 0x06, 0x02, 0x01, 0x05, 0x02, 0x01, 0x83],
            ),
            (
                "non-minimal n",
                vec![0x30, 0x07, 0x02, 0x02, 0x00, 0x05, 0x02, 0x01, 0x03],
            ),
            (
                "n not an INTEGER",
                vec![0x30, 0x06, 0x04, 0x01, 0x05, 0x02, 0x01, 0x03],
            ),
            (
                "trailing data",
                vec![0x30, 0x06, 0x02, 0x01, 0x05, 0x02, 0x01, 0x03, 0x00],
            ),
            (
                "an uncompressed EC point",
                vec![0x04, 0x01, 0x02, 0x03, 0x04],
            ),
        ] {
            assert!(is_invalid(&decode_public(&der)), "{what}");
        }
    }

    #[test]
    fn the_rsa_public_key_negative_vectors_are_invalid() {
        // N65: RSAPublicKey with a third INTEGER (RFC 8017 App. A.1.1).
        assert!(is_invalid(&decode_public(&fixtures::negative("N65"))));
    }

    /// `SEQUENCE { parts... }` in the short or one-octet long form.
    fn sequence(parts: &[&[u8]]) -> Vec<u8> {
        let body = parts.concat();
        let mut out = vec![0x30];
        match u8::try_from(body.len()).unwrap() {
            len @ 0..=0x7F => out.push(len),
            len => out.extend_from_slice(&[0x81, len]),
        }
        out.extend_from_slice(&body);
        out
    }

    fn is_unsupported<T>(result: &Result<T>) -> bool {
        matches!(result, Err(Error::UnsupportedAlgorithm))
    }

    /// INTEGER 0 and 1: the RSAPrivateKey `Version` values two-prime and
    /// multi (RFC 8017 App. A.1.2).
    const TWO_PRIME: &[u8] = &[0x02, 0x01, 0x00];
    const MULTI: &[u8] = &[0x02, 0x01, 0x01];
    /// A small valid INTEGER, standing in for an RSAPrivateKey field.
    const SMALL: &[u8] = &[0x02, 0x01, 0x05];

    /// `version` followed by `count` copies of `field`.
    fn version_then(version: &[u8], field: &[u8], count: usize) -> Vec<u8> {
        let mut parts = vec![version];
        parts.extend(std::iter::repeat_n(field, count));
        sequence(&parts)
    }

    #[test]
    fn two_integers_are_an_rsa_public_key() {
        for (dir, file) in public_fixtures() {
            let der = fixtures::load(dir, &file);
            let Ok(Pkcs1Key::Public(classified)) = decode(&der) else {
                panic!("{file}: not an RSAPublicKey");
            };
            let public = decode_public(&der).unwrap();
            assert_eq!(classified.n, public.n, "{file}");
            assert_eq!(classified.e, public.e, "{file}");
            assert!(is_invalid(&decode_private(&der)), "{file}");
        }
        // Shape alone decides: two INTEGERs are an RSAPublicKey even when
        // the first is 0 or 1. Such a key is then refused by the JWK
        // validation in rsa.rs (RFC 8017 §3.1), not here.
        for first in [TWO_PRIME, MULTI] {
            let der = sequence(&[first, SMALL]);
            let Ok(Pkcs1Key::Public(key)) = decode(&der) else {
                panic!("not an RSAPublicKey");
            };
            assert_eq!(key.e, &[0x05]);
        }
    }

    /// The two-prime RSAPrivateKey fixtures (RFC 8017 App. A.1.2): OpenSSL's
    /// 2048-bit key (DER and PEM) and the RFC 9500 §2.1 test keys.
    fn two_prime_fixtures() -> Vec<(&'static str, String)> {
        let mut files: Vec<(&str, String)> = [
            "reject-rsa2048-private-pkcs1.der",
            "reject-rsa2048-private-pkcs1.pem",
        ]
        .map(|file| ("openssl", file.to_owned()))
        .into();
        for bits in [1024, 2048, 4096] {
            files.push((
                "rfc",
                format!("reject-rfc9500-testRSA{bits}-private-pkcs1.pem"),
            ));
        }
        files
    }

    #[test]
    fn two_prime_rsa_private_keys_decode_and_re_encode_to_their_bytes() {
        // RFC 8017 App. A.1.2, version two-prime(0); ADR 0018 §3: the
        // export is byte-identical. (The `reject-` names predate ADR 0067;
        // the 1024-bit key is refused later, by the JWK validation.)
        for (dir, file) in two_prime_fixtures() {
            let der = fixtures::load(dir, &file);
            let Ok(Pkcs1Key::Private(key)) = decode(&der) else {
                panic!("{file}: not an RSAPrivateKey");
            };
            let direct = decode_private(&der).unwrap();
            assert_eq!(key.n, direct.n, "{file}");
            assert_eq!(key.qi, direct.qi, "{file}");
            assert_eq!(&encode_private(&key).unwrap()[..], &der[..], "{file}");
            // e = 65537, and no field keeps a sign octet (X.690 §8.3.3).
            assert_eq!(key.e, &[0x01, 0x00, 0x01], "{file}");
            for field in [key.n, key.d, key.p, key.q, key.dp, key.dq, key.qi] {
                assert_ne!(field.first(), Some(&0), "{file}");
            }
            // As the SPKI contents, it is not an RSAPublicKey (RFC 3279
            // §2.3.1) and is simply malformed.
            assert!(is_invalid(&decode_public(&der)), "{file}");
        }
    }

    #[test]
    fn a_multi_prime_rsa_private_key_is_unsupported() {
        // ADR 0067 §3: version multi(1) (RFC 8017 App. A.1.2), whatever
        // follows, before any INTEGER after the version is parsed.
        let der = fixtures::load("openssl", "reject-rsa2048-3prime-private-pkcs1.pem");
        assert!(is_unsupported(&decode(&der)));
        assert!(is_unsupported(&decode_private(&der)));
        let other_prime_infos = sequence(&[&sequence(&[SMALL, SMALL, SMALL])]);
        let empty: &[u8] = &[0x02, 0x00];
        for (what, der) in [
            ("multi", version_then(MULTI, SMALL, 8)),
            ("multi with otherPrimeInfos", {
                let mut parts = vec![MULTI];
                parts.extend(std::iter::repeat_n(SMALL, 8));
                parts.push(&other_prime_infos);
                sequence(&parts)
            }),
            ("multi with empty INTEGERs", version_then(MULTI, empty, 8)),
        ] {
            assert!(is_unsupported(&decode(&der)), "{what}");
            assert!(is_unsupported(&decode_private(&der)), "{what}");
        }
    }

    #[test]
    fn two_prime_private_integers_are_strict_der() {
        // X.690 §8.3.1 (empty), §8.3.2 (not minimal), a negative value, and
        // a ninth element (RFC 8017 App. A.1.2: otherPrimeInfos only with
        // version multi): all malformed, InvalidKey.
        let empty: &[u8] = &[0x02, 0x00];
        let non_minimal: &[u8] = &[0x02, 0x02, 0x00, 0x01];
        let negative: &[u8] = &[0x02, 0x01, 0x80];
        for (what, der) in [
            ("empty INTEGERs", version_then(TWO_PRIME, empty, 8)),
            (
                "non-minimal INTEGERs",
                version_then(TWO_PRIME, non_minimal, 8),
            ),
            ("negative INTEGERs", version_then(TWO_PRIME, negative, 8)),
            ("nine INTEGERs", version_then(TWO_PRIME, SMALL, 9)),
            ("high-tag-number garbage after the eighth", {
                let mut parts = vec![TWO_PRIME];
                parts.extend(std::iter::repeat_n(SMALL, 8));
                parts.push(&[0x1F, 0xFF, 0xFF]);
                sequence(&parts)
            }),
        ] {
            assert!(is_invalid(&decode(&der)), "{what}");
            assert!(is_invalid(&decode_private(&der)), "{what}");
        }
        // Eight small INTEGERs are a well-formed RSAPrivateKey; whether they
        // are a key is the JWK validation's question (rsa.rs).
        let der = version_then(TWO_PRIME, SMALL, 8);
        let Ok(Pkcs1Key::Private(key)) = decode(&der) else {
            panic!("not an RSAPrivateKey");
        };
        assert_eq!(key.qi, &[0x05]);
        // Debug shows lengths only.
        let debug = format!("{key:?}");
        assert_eq!(
            debug,
            r#"RsaPrivateFields { n_len: 1, e_len: 1, private: "<redacted>" }"#
        );
    }

    #[test]
    fn every_other_shape_is_invalid() {
        let octets: &[u8] = &[0x04, 0x01, 0x00];
        for (what, der) in [
            ("empty", vec![]),
            ("empty SEQUENCE", sequence(&[])),
            ("version alone", sequence(&[TWO_PRIME])),
            (
                "version and seven INTEGERs",
                version_then(TWO_PRIME, SMALL, 7),
            ),
            ("version 2", version_then(&[0x02, 0x01, 0x02], SMALL, 8)),
            ("version -1", version_then(&[0x02, 0x01, 0xFF], SMALL, 8)),
            (
                "non-minimal version 0",
                version_then(&[0x02, 0x02, 0x00, 0x00], SMALL, 8),
            ),
            ("version not an INTEGER", version_then(octets, SMALL, 8)),
            ("an OCTET STRING among the eight", {
                let mut parts = vec![TWO_PRIME];
                parts.extend(std::iter::repeat_n(SMALL, 7));
                parts.push(octets);
                sequence(&parts)
            }),
            (
                "three INTEGERs, the first a modulus",
                sequence(&[&[0x02, 0x01, 0x07], SMALL, SMALL]),
            ),
            (
                "not a SEQUENCE",
                version_then(TWO_PRIME, SMALL, 8)[2..].to_vec(),
            ),
            ("trailing data after a private key", {
                let mut der = version_then(TWO_PRIME, SMALL, 8);
                der.push(0x00);
                der
            }),
        ] {
            assert!(is_invalid(&decode(&der)), "{what}");
        }
        // N65 (RFC 8017 App. A.1.1, exactly modulus and publicExponent).
        assert!(is_invalid(&decode(&fixtures::negative("N65"))));
    }

    mod properties {
        use proptest::prelude::*;

        use super::{Pkcs1Key, decode, decode_public, encode_private, encode_public};

        /// Never panics, and canonical: whatever decodes as an RSAPublicKey
        /// re-encodes to exactly the input (X.690 §10), through both entry
        /// points.
        fn canonical(input: &[u8]) -> Result<(), TestCaseError> {
            if let Ok(key) = decode_public(input) {
                prop_assert_eq!(&encode_public(key.n, key.e).unwrap()[..], input);
            }
            match decode(input) {
                Ok(Pkcs1Key::Public(key)) => {
                    prop_assert_eq!(&encode_public(key.n, key.e).unwrap()[..], input);
                }
                Ok(Pkcs1Key::Private(key)) => {
                    prop_assert_eq!(&encode_private(&key).unwrap()[..], input);
                }
                Err(_) => {}
            }
            Ok(())
        }

        /// DER length octets for `len` (X.690 §8.1.3), in the fewest octets.
        fn length(len: usize) -> Vec<u8> {
            match len {
                0..=0x7F => vec![u8::try_from(len).unwrap()],
                0x80..=0xFF => vec![0x81, u8::try_from(len).unwrap()],
                _ => {
                    let [high, low] = u16::try_from(len).unwrap().to_be_bytes();
                    vec![0x82, high, low]
                }
            }
        }

        proptest! {
            #![proptest_config(ProptestConfig::with_cases(1_000))]

            #[test]
            fn arbitrary_bytes_fail_or_are_canonical(bytes in proptest::collection::vec(any::<u8>(), 0..256)) {
                canonical(&bytes)?;
            }

            #[test]
            fn any_two_magnitudes_round_trip(
                n in proptest::collection::vec(any::<u8>(), 1..300),
                e in proptest::collection::vec(any::<u8>(), 1..8),
            ) {
                // Leading zero octets are not significant (X.690 §8.3.2).
                let der = encode_public(&n, &e).unwrap();
                let Pkcs1Key::Public(key) = decode(&der).unwrap() else {
                    return Err(TestCaseError::fail("not an RSAPublicKey"));
                };
                let strip = |v: &[u8]| -> Vec<u8> {
                    let start = v.iter().position(|&b| b != 0).unwrap_or(v.len() - 1);
                    v[start..].to_vec()
                };
                prop_assert_eq!(key.n.to_vec(), strip(&n));
                prop_assert_eq!(key.e.to_vec(), strip(&e));
                canonical(&der)?;
            }

            #[test]
            fn private_key_shapes_are_unsupported_or_canonical(
                multi in any::<bool>(),
                fields in proptest::collection::vec(proptest::collection::vec(any::<u8>(), 0..20), 8..12),
            ) {
                // RFC 8017 App. A.1.2 / ADR 0067 §3: version multi(1) is
                // always unsupported, whatever follows; version two-prime(0)
                // decodes only when canonical, and then re-encodes exactly.
                let version: &[u8] = if multi { &[0x02, 0x01, 0x01] } else { &[0x02, 0x01, 0x00] };
                let mut body = version.to_vec();
                for contents in &fields {
                    body.push(0x02);
                    body.push(u8::try_from(contents.len()).unwrap());
                    body.extend_from_slice(contents);
                }
                let mut der = vec![0x30];
                der.extend_from_slice(&length(body.len()));
                der.extend_from_slice(&body);
                if multi {
                    prop_assert_eq!(decode(&der).err(), Some(crate::Error::UnsupportedAlgorithm));
                } else {
                    prop_assert!(!matches!(decode(&der), Err(crate::Error::UnsupportedAlgorithm)));
                    canonical(&der)?;
                }
            }
        }
    }
}