//! Ed25519 verification as WAI verifies it (RFC 8032 §5.1.7, strictly; SPEC §7
//! *Signatures*): one routine, so every receipt family accepts exactly the signatures every
//! other conforming verifier accepts. Every signature check written in this crate calls it,
//! except OER/2's (`crate::oer`), whose rule oer-receipts §5 settles: it refuses the same
//! keys and leaves `R` to RFC 8032. The quantum receipts this crate re-exports are checked
//! in the `wai-quantum` crate, which does not call it.
//!
//! The rule, in order:
//!
//! 1. The key `A` decodes, and is the one canonical encoding of its point: `y` < p, and
//!    `x` = 0 never carries the sign bit. `VerifyingKey::from_bytes` reduces a `y` ≥ p
//!    and accepts the sign bit on `x` = 0; both are refused here by re-encoding the point
//!    and comparing bytes.
//! 2. `A` is not of small order (its order divides 8). Under such a key the equation can
//!    hold for a signature made without any private key: under the identity key, every
//!    `R` = [s]B with `S` = s verifies.
//! 3. `S` < L. Checked here as well as inside the library, whose own test shrinks to the
//!    top three bits when any crate in a build enables its `legacy_compatibility`
//!    feature, and S + L passes that test.
//! 4. `R` decodes and is not of small order, and the cofactorless equation holds with
//!    [S]B − [k]A encoded and compared with `R` byte for byte, so a non-canonical `R`
//!    never verifies (ed25519-dalek's `verify_strict`).

use ed25519_dalek::{Signature, VerifyingKey};

/// Why a signature is refused.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum SigError {
    /// The key does not decode, is not its point's one canonical encoding, or is of small
    /// order (steps 1 and 2).
    BadKey,
    /// `S` ≥ L, `R` does not decode or is of small order, or the equation does not hold
    /// with `R` compared byte for byte (steps 3 and 4).
    BadSignature,
}

impl std::fmt::Display for SigError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(match self {
            SigError::BadKey => "the key is not a canonical point of large order",
            SigError::BadSignature => "the signature does not verify strictly",
        })
    }
}

impl std::error::Error for SigError {}

/// The post-quantum half a hybrid signature adds beside an Ed25519 signature
/// (`extensions/pq-signatures.md` §2): the signer's ML-DSA-65 public key and the ML-DSA-65
/// signature, as bytes. The receipt families keep it beside their `sig`; only the readers
/// built with `pq_signatures` ever fill it, and [`crate::pq_sig`] verifies it. Without that
/// feature a reader refuses the members that carry it, so it is always `None`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PqHalf {
    /// The ML-DSA-65 public key, `pkEncode` of FIPS 204 Algorithm 22: 1952 bytes.
    pub key: Vec<u8>,
    /// The ML-DSA-65 signature, `sigEncode` of FIPS 204 Algorithm 26: 3309 bytes.
    pub sig: Vec<u8>,
}

/// The group order L = 2^252 + 27742317777372353535851937790883648493, little-endian.
const L: [u8; 32] = [
    0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10,
];

/// Whether the little-endian integer `s` is below L.
fn below_l(s: &[u8; 32]) -> bool {
    for i in (0..32).rev() {
        if s[i] != L[i] {
            return s[i] < L[i];
        }
    }
    false
}

/// Steps 1 and 2: the key, refused unless it is the canonical encoding of a point of
/// large order.
pub fn strict_key(bytes: &[u8; 32]) -> Result<VerifyingKey, SigError> {
    let key = VerifyingKey::from_bytes(bytes).map_err(|_| SigError::BadKey)?;
    if key.to_edwards().compress().to_bytes() != *bytes || key.is_weak() {
        return Err(SigError::BadKey);
    }
    Ok(key)
}

/// The whole rule over `msg`: `Ok` only when every step holds.
pub fn verify_strict(pubkey: &[u8; 32], msg: &[u8], sig: &[u8; 64]) -> Result<(), SigError> {
    let key = strict_key(pubkey)?;
    let s: &[u8; 32] = sig[32..].try_into().expect("a signature is 64 bytes");
    if !below_l(s) {
        return Err(SigError::BadSignature);
    }
    key.verify_strict(msg, &Signature::from_bytes(sig)).map_err(|_| SigError::BadSignature)
}

/// The identity point, canonically encoded (y = 1).
pub const IDENTITY: [u8; 32] = {
    let mut b = [0u8; 32];
    b[0] = 1;
    b
};

/// The identity spelled with y = p + 1: a decoder that reduces `y` reads the identity.
pub const IDENTITY_Y_NOT_REDUCED: [u8; 32] = {
    let mut b = [0xffu8; 32];
    b[0] = 0xee;
    b[31] = 0x7f;
    b
};

/// The base point B, encoded. As a key its discrete logarithm is 1.
pub const BASE_POINT: [u8; 32] = {
    let mut b = [0x66u8; 32];
    b[0] = 0x58;
    b
};

/// `bytes` (little-endian, any length) mod L, by binary long division.
fn mod_l(bytes: &[u8]) -> [u8; 32] {
    let mut r = [0u8; 33];
    for i in (0..bytes.len() * 8).rev() {
        let mut carry = (bytes[i / 8] >> (i % 8)) & 1;
        for b in r.iter_mut() {
            let top = *b >> 7;
            *b = (*b << 1) | carry;
            carry = top;
        }
        let lx = |j: usize| if j < 32 { L[j] } else { 0 };
        if (0..33).rev().find(|&j| r[j] != lx(j)).is_none_or(|j| r[j] > lx(j)) {
            let mut borrow = 0i16;
            for j in 0..33 {
                let v = r[j] as i16 - lx(j) as i16 - borrow;
                r[j] = v.rem_euclid(256) as u8;
                borrow = i16::from(v < 0);
            }
        }
    }
    r[..32].try_into().expect("the remainder is below L")
}

/// A signature a lenient verifier accepts and [`verify_strict`] refuses, for the key a
/// receipt names: what a test or a conformance corpus uses to show a receipt family
/// verifies strictly. None of them needs a private key.
#[derive(Clone, Debug)]
pub struct Forgery {
    /// A short name a corpus can build a vector name from.
    pub name: &'static str,
    /// What it is, in a sentence a corpus can carry.
    pub about: &'static str,
    /// The key the receipt names.
    pub key: [u8; 32],
    /// The signature it carries.
    pub sig: [u8; 64],
    /// Why [`verify_strict`] refuses it.
    pub refusal: SigError,
}

/// The three forgeries over `payload(key)`, the bytes a receipt signs once its key is
/// `key`. Each satisfies the cofactorless equation with `R` compared byte for byte, so
/// ed25519-dalek's lenient `verify` accepts it, which this asserts. That [`verify_strict`]
/// refuses each is left to the caller to show, so a test of a signing site fails at the
/// site when the site, or the rule, lets one through. Each fails one step of the rule:
///
/// - `key_identity`: the key is the identity and (R, S) = (B, 1), which verifies over any
///   message (step 2);
/// - `key_identity_y_not_reduced`: the same, with the identity spelled y = p + 1 (step 1,
///   and step 2 under a decoder that reduces `y`);
/// - `r_small_order`: the key is B, whose discrete logarithm is 1, `R` is the identity and
///   `S` = k, so [S]B = R + [k]B (step 4: `R` of small order).
pub fn forgeries(payload: impl Fn(&[u8; 32]) -> Vec<u8>) -> [Forgery; 3] {
    use ed25519_dalek::Verifier;
    use sha2::{Digest, Sha512};
    let sig = |r: [u8; 32], s: [u8; 32]| {
        let mut g = [0u8; 64];
        g[..32].copy_from_slice(&r);
        g[32..].copy_from_slice(&s);
        g
    };
    let r_small = {
        let m = payload(&BASE_POINT);
        let k = mod_l(&Sha512::new().chain_update(IDENTITY).chain_update(BASE_POINT).chain_update(&m).finalize());
        sig(IDENTITY, k)
    };
    let all = [
        Forgery {
            name: "key_identity",
            about: "the identity point as the key, with (R, S) = (B, 1): the equation holds for every message, and the key is of small order",
            key: IDENTITY,
            sig: sig(BASE_POINT, IDENTITY),
            refusal: SigError::BadKey,
        },
        Forgery {
            name: "key_identity_y_not_reduced",
            about: "the identity spelled y = p + 1, with (R, S) = (B, 1): a decoder that reduces y reads the identity, and the encoding is not canonical",
            key: IDENTITY_Y_NOT_REDUCED,
            sig: sig(BASE_POINT, IDENTITY),
            refusal: SigError::BadKey,
        },
        Forgery {
            name: "r_small_order",
            about: "the base point as the key (its discrete logarithm is 1), R the identity and S = k: the equation holds, and R is of small order",
            key: BASE_POINT,
            sig: r_small,
            refusal: SigError::BadSignature,
        },
    ];
    for f in &all {
        let m = payload(&f.key);
        let lenient = VerifyingKey::from_bytes(&f.key).and_then(|k| k.verify(&m, &Signature::from_bytes(&f.sig)));
        assert!(lenient.is_ok(), "{}: a lenient verifier accepts the forgery", f.name);
    }
    all
}

/// For a signing site's tests: `good` verifies, and each of [`forgeries`], set into it by
/// `set` (the key and the signature it carries), is refused by `verifies`. `payload` is
/// the bytes the site signs, computed after its key is set, since a payload may name it.
#[cfg(test)]
pub(crate) fn assert_refuses_forgeries<R: Clone>(
    good: &R,
    set: impl Fn(&mut R, [u8; 32], [u8; 64]),
    payload: impl Fn(&R) -> Vec<u8>,
    verifies: impl Fn(&R) -> bool,
) {
    assert!(verifies(good), "the site verifies what it signed");
    let with = |key: [u8; 32], sig: [u8; 64]| {
        let mut r = good.clone();
        set(&mut r, key, sig);
        r
    };
    for f in forgeries(|key| payload(&with(*key, [0; 64]))) {
        assert!(!verifies(&with(f.key, f.sig)), "{} is refused: {}", f.name, f.about);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use ed25519_dalek::{Signer, SigningKey};

    const B: [u8; 32] = BASE_POINT;

    fn le(mut n: [u8; 32], add: u8) -> [u8; 32] {
        let mut carry = add as u16;
        for b in n.iter_mut() {
            let v = *b as u16 + carry;
            *b = v as u8;
            carry = v >> 8;
        }
        n
    }

    /// p = 2^255 − 19, little-endian.
    fn p() -> [u8; 32] {
        let mut b = [0xffu8; 32];
        b[0] = 0xed;
        b[31] = 0x7f;
        b
    }

    fn sig(r: [u8; 32], s: [u8; 32]) -> [u8; 64] {
        let mut g = [0u8; 64];
        g[..32].copy_from_slice(&r);
        g[32..].copy_from_slice(&s);
        g
    }

    #[test]
    fn a_real_signature_verifies() {
        let k = SigningKey::from_bytes(&[7u8; 32]);
        let g = k.sign(b"m").to_bytes();
        verify_strict(&k.verifying_key().to_bytes(), b"m", &g).unwrap();
        assert_eq!(verify_strict(&k.verifying_key().to_bytes(), b"n", &g), Err(SigError::BadSignature));
    }

    #[test]
    fn the_identity_key_is_refused_in_either_spelling() {
        let one = le([0; 32], 1);
        // (R, S) = (B, 1) satisfies the equation under the identity for any message.
        let forged = sig(B, one);
        assert_eq!(verify_strict(&one, b"any", &forged), Err(SigError::BadKey));
        // y = p + 1, a second spelling of the identity that from_bytes reduces.
        let long = le(p(), 1);
        assert!(VerifyingKey::from_bytes(&long).is_ok(), "the library reads the long spelling");
        assert_eq!(verify_strict(&long, b"any", &forged), Err(SigError::BadKey));
        // x = 0 with the sign bit set.
        let mut signed = one;
        signed[31] |= 0x80;
        assert_eq!(verify_strict(&signed, b"any", &forged), Err(SigError::BadKey));
    }

    /// Steps 1 and 2 over every encoding RFC 8032 §5.1.3 refuses that curve25519's
    /// decompression accepts — y = p + j for j = 0 … 18, and x = 0 with the sign bit set —
    /// and over the eight points of small order.
    #[test]
    fn a_key_is_refused_unless_canonical_and_of_large_order() {
        let mut lenient = 0;
        for j in 0u8..=18 {
            let mut b = [0xff; 32];
            b[0] = 0xed + j; // p + j, little-endian
            b[31] = 0x7f;
            if VerifyingKey::from_bytes(&b).is_ok() {
                lenient += 1;
                assert_eq!(strict_key(&b).err(), Some(SigError::BadKey), "y = p + {j}");
                // The same point, spelt canonically, is refused only for being of small order.
                let mut c = [0u8; 32];
                c[0] = j;
                let canonical = VerifyingKey::from_bytes(&c).expect("the same point");
                assert_eq!(strict_key(&c).is_ok(), !canonical.is_weak(), "y = {j}");
            }
        }
        assert!(lenient > 2, "the leniency this rule closes is real: {lenient} encodings");
        let mut sign_set = [0u8; 32];
        sign_set[0] = 1;
        sign_set[31] = 0x80; // x = 0 (y = 1) with the sign bit set
        let mut minus_one = [0xff; 32];
        minus_one[0] = 0xec; // y = p - 1, x = 0, sign bit set
        for b in [sign_set, minus_one] {
            assert!(VerifyingKey::from_bytes(&b).is_ok());
            assert_eq!(strict_key(&b).err(), Some(SigError::BadKey));
        }
        let small_order = [
            "0100000000000000000000000000000000000000000000000000000000000000",
            "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
            "0000000000000000000000000000000000000000000000000000000000000000",
            "0000000000000000000000000000000000000000000000000000000000000080",
            "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a",
            "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa",
            "26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05",
            "26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85",
        ];
        for h in small_order {
            let b: [u8; 32] = (0..32).map(|i| u8::from_str_radix(&h[2 * i..2 * i + 2], 16).unwrap()).collect::<Vec<_>>().try_into().unwrap();
            let key = VerifyingKey::from_bytes(&b).expect("a curve point");
            assert_eq!(key.to_edwards().compress().to_bytes(), b, "{h} is canonical");
            assert!(key.is_weak(), "{h} is of small order");
            assert_eq!(strict_key(&b).err(), Some(SigError::BadKey), "{h}");
        }
        // A genuine key passes.
        assert!(strict_key(&SigningKey::from_bytes(&[1; 32]).verifying_key().to_bytes()).is_ok());
    }

    /// Each forgery passes the lenient check and fails exactly the step it names, over a
    /// message that names its key as a receipt's signing payload does; the constants are
    /// the points they say.
    #[test]
    fn the_forgeries_pass_a_lenient_check_and_fail_their_step() {
        let payload = |k: &[u8; 32]| [b"a receipt signed under ".as_slice(), k].concat();
        let fs = forgeries(payload);
        for f in &fs {
            assert_eq!(verify_strict(&f.key, &payload(&f.key), &f.sig), Err(f.refusal), "{}", f.name);
        }
        let got: Vec<_> = fs.iter().map(|f| (f.name, f.refusal)).collect();
        assert_eq!(
            got,
            [("key_identity", SigError::BadKey), ("key_identity_y_not_reduced", SigError::BadKey), ("r_small_order", SigError::BadSignature)]
        );
        assert_eq!(IDENTITY_Y_NOT_REDUCED, le(p(), 1));
        assert!(VerifyingKey::from_bytes(&IDENTITY).unwrap().is_weak());
        assert_eq!(VerifyingKey::from_bytes(&IDENTITY_Y_NOT_REDUCED).unwrap().to_edwards().compress().to_bytes(), IDENTITY);
        // B is a canonical key of large order: the r_small_order forgery above holds under it
        // with S = k, which says its discrete logarithm is 1.
        assert!(strict_key(&BASE_POINT).is_ok());
    }

    #[test]
    fn a_non_canonical_key_of_large_order_is_refused() {
        // A point of large order whose y is below 19 has the second spelling y + p,
        // which the library reads as the same point; strictly, only y itself is a key.
        let mut seen = 0;
        for y in 2u8..19 {
            let short = le([0; 32], y);
            let Ok(k) = VerifyingKey::from_bytes(&short) else { continue };
            if k.is_weak() {
                continue;
            }
            let long = le(p(), y);
            assert!(VerifyingKey::from_bytes(&long).is_ok(), "the library reads y = p + {y}");
            assert_eq!(strict_key(&long).err(), Some(SigError::BadKey), "y = p + {y}");
            assert!(strict_key(&short).is_ok(), "y = {y}");
            seen += 1;
        }
        assert!(seen > 0, "some y below 19 is on the curve with large order");
    }

    #[test]
    fn s_at_or_above_l_is_refused() {
        let k = SigningKey::from_bytes(&[9u8; 32]);
        let g = k.sign(b"m").to_bytes();
        let s: [u8; 32] = g[32..].try_into().unwrap();
        // S + L, as a 256-bit little-endian sum (it fits: S < L < 2^253).
        let mut sum = [0u8; 32];
        let mut carry = 0u16;
        for i in 0..32 {
            let v = s[i] as u16 + L[i] as u16 + carry;
            sum[i] = v as u8;
            carry = v >> 8;
        }
        let r: [u8; 32] = g[..32].try_into().unwrap();
        assert_eq!(verify_strict(&k.verifying_key().to_bytes(), b"m", &sig(r, sum)), Err(SigError::BadSignature));
        assert_eq!(verify_strict(&k.verifying_key().to_bytes(), b"m", &sig(r, L)), Err(SigError::BadSignature));
        assert!(!below_l(&L) && below_l(&s));
    }

    #[test]
    fn a_small_order_or_non_canonical_r_is_refused() {
        use ed25519_dalek::Verifier;
        use sha2::{Digest, Sha512};
        // Under the key B (scalar 1), R the identity and S = k satisfy the cofactorless
        // equation point for point: [k]B = O + [k]B. A lenient check accepts it.
        let msg = b"m";
        let k_of = |r: &[u8; 32]| mod_l(&Sha512::new().chain_update(r).chain_update(B).chain_update(msg).finalize());
        let one = le([0; 32], 1);
        let g = sig(one, k_of(&one));
        let key = VerifyingKey::from_bytes(&B).unwrap();
        assert!(key.verify(msg, &Signature::from_bytes(&g)).is_ok(), "the lenient check accepts R of small order");
        assert_eq!(verify_strict(&B, msg, &g), Err(SigError::BadSignature));
        // The identity respelled y = p + 1, with S over those bytes: never byte-equal.
        let long = le(p(), 1);
        assert_eq!(verify_strict(&B, msg, &sig(long, k_of(&long))), Err(SigError::BadSignature));
        // R = B, S = 1 + k: a signature by the scalar 1, which the rule accepts.
        verify_strict(&B, msg, &sig(B, mod_l(&le(k_of(&B), 1)))).unwrap();
    }
}
