we / crates / crypto / src / ecdsa.rs

//! ECDSA signature verification for P-256 and P-384 (FIPS 186-4).
//!
//! Supports verification of ECDSA signatures using the NIST P-256 (secp256r1)
//! and P-384 (secp384r1) curves with SHA-256 and SHA-384 respectively.

use crate::asn1::{
    self, Asn1Error, OID_EC_PUBLIC_KEY, OID_PRIME256V1, OID_SECP384R1, TAG_SEQUENCE,
};
use crate::bigint::BigUint;
use crate::sha2::{sha256, sha384};

use core::cmp::Ordering;
use core::fmt;

// ---------------------------------------------------------------------------
// Error type
// ---------------------------------------------------------------------------

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EcdsaError {
    /// ASN.1 parsing error.
    Asn1(Asn1Error),
    /// Unsupported or unknown curve.
    UnsupportedCurve,
    /// Invalid public key (not on curve, wrong format, etc.).
    InvalidPublicKey,
    /// Invalid signature format.
    InvalidSignature,
    /// Signature component r or s is out of range [1, n-1].
    SignatureOutOfRange,
    /// Signature verification failed.
    VerificationFailed,
    /// Invalid key format.
    InvalidKeyFormat,
}

impl fmt::Display for EcdsaError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Asn1(e) => write!(f, "ASN.1 error: {e}"),
            Self::UnsupportedCurve => write!(f, "unsupported elliptic curve"),
            Self::InvalidPublicKey => write!(f, "invalid EC public key"),
            Self::InvalidSignature => write!(f, "invalid ECDSA signature format"),
            Self::SignatureOutOfRange => write!(f, "signature component out of range"),
            Self::VerificationFailed => write!(f, "ECDSA verification failed"),
            Self::InvalidKeyFormat => write!(f, "invalid key format"),
        }
    }
}

impl From<Asn1Error> for EcdsaError {
    fn from(e: Asn1Error) -> Self {
        Self::Asn1(e)
    }
}

pub type Result<T> = core::result::Result<T, EcdsaError>;

// ---------------------------------------------------------------------------
// Curve identifiers
// ---------------------------------------------------------------------------

/// Supported elliptic curves.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Curve {
    P256,
    P384,
}

// ---------------------------------------------------------------------------
// Modular arithmetic helpers (over BigUint)
// ---------------------------------------------------------------------------

fn mod_add(a: &BigUint, b: &BigUint, m: &BigUint) -> BigUint {
    a.add(b).modulo(m)
}

fn mod_sub(a: &BigUint, b: &BigUint, m: &BigUint) -> BigUint {
    if a.cmp(b) != Ordering::Less {
        a.sub(b)
    } else {
        // a < b: result = m - (b - a)
        m.sub(&b.sub(a))
    }
}

fn mod_mul(a: &BigUint, b: &BigUint, m: &BigUint) -> BigUint {
    a.mul(b).modulo(m)
}

/// Modular inverse using Fermat's little theorem (for prime moduli).
/// a^(-1) = a^(p-2) mod p
fn mod_inv(a: &BigUint, p: &BigUint) -> BigUint {
    let exp = p.sub(&BigUint::from_u64(2));
    a.modpow(&exp, p)
}

// ---------------------------------------------------------------------------
// Curve parameters
// ---------------------------------------------------------------------------

struct CurveParams {
    /// Field prime p.
    p: BigUint,
    /// Curve parameter a.
    a: BigUint,
    /// Curve parameter b.
    b: BigUint,
    /// Generator x-coordinate.
    gx: BigUint,
    /// Generator y-coordinate.
    gy: BigUint,
    /// Curve order n.
    n: BigUint,
    /// Byte length of field elements.
    field_len: usize,
}

fn from_hex(s: &str) -> Vec<u8> {
    (0..s.len())
        .step_by(2)
        .map(|i| u8::from_str_radix(&s[i..i + 2], 16).unwrap())
        .collect()
}

fn p256_params() -> CurveParams {
    let p = BigUint::from_be_bytes(&from_hex(
        "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
    ));
    let a = BigUint::from_be_bytes(&from_hex(
        "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC",
    ));
    let b = BigUint::from_be_bytes(&from_hex(
        "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
    ));
    let gx = BigUint::from_be_bytes(&from_hex(
        "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
    ));
    let gy = BigUint::from_be_bytes(&from_hex(
        "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
    ));
    let n = BigUint::from_be_bytes(&from_hex(
        "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
    ));
    CurveParams {
        p,
        a,
        b,
        gx,
        gy,
        n,
        field_len: 32,
    }
}

fn p384_params() -> CurveParams {
    let p = BigUint::from_be_bytes(&from_hex(
        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
    ));
    let a = BigUint::from_be_bytes(&from_hex(
        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC",
    ));
    let b = BigUint::from_be_bytes(&from_hex(
        "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
    ));
    let gx = BigUint::from_be_bytes(&from_hex(
        "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
    ));
    let gy = BigUint::from_be_bytes(&from_hex(
        "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
    ));
    let n = BigUint::from_be_bytes(&from_hex(
        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
    ));
    CurveParams {
        p,
        a,
        b,
        gx,
        gy,
        n,
        field_len: 48,
    }
}

fn curve_params(curve: Curve) -> CurveParams {
    match curve {
        Curve::P256 => p256_params(),
        Curve::P384 => p384_params(),
    }
}

// ---------------------------------------------------------------------------
// Point types
// ---------------------------------------------------------------------------

/// A point on the curve in Jacobian coordinates (X, Y, Z).
/// Affine (x, y) = (X/Z^2, Y/Z^3). Point at infinity has Z = 0.
#[derive(Clone)]
struct JacobianPoint {
    x: BigUint,
    y: BigUint,
    z: BigUint,
}

impl JacobianPoint {
    fn infinity() -> Self {
        Self {
            x: BigUint::one(),
            y: BigUint::one(),
            z: BigUint::zero(),
        }
    }

    fn from_affine(x: &BigUint, y: &BigUint) -> Self {
        Self {
            x: x.clone(),
            y: y.clone(),
            z: BigUint::one(),
        }
    }

    fn is_infinity(&self) -> bool {
        self.z.is_zero()
    }

    /// Convert to affine coordinates (x, y).
    fn to_affine(&self, p: &BigUint) -> (BigUint, BigUint) {
        if self.is_infinity() {
            return (BigUint::zero(), BigUint::zero());
        }

        let z_inv = mod_inv(&self.z, p);
        let z_inv2 = mod_mul(&z_inv, &z_inv, p);
        let z_inv3 = mod_mul(&z_inv2, &z_inv, p);

        let x = mod_mul(&self.x, &z_inv2, p);
        let y = mod_mul(&self.y, &z_inv3, p);
        (x, y)
    }
}

// ---------------------------------------------------------------------------
// Elliptic curve point operations
// ---------------------------------------------------------------------------

/// Point doubling in Jacobian coordinates.
/// Uses the optimization for a = p - 3 (both P-256 and P-384).
fn point_double(pt: &JacobianPoint, params: &CurveParams) -> JacobianPoint {
    let p = &params.p;

    if pt.is_infinity() {
        return JacobianPoint::infinity();
    }

    // For a = -3 (mod p): M = 3*(X - Z^2)*(X + Z^2)
    let z2 = mod_mul(&pt.z, &pt.z, p);
    let x_minus_z2 = mod_sub(&pt.x, &z2, p);
    let x_plus_z2 = mod_add(&pt.x, &z2, p);
    let m = mod_mul(&x_minus_z2, &x_plus_z2, p);
    let m = mod_mul(&BigUint::from_u64(3), &m, p);

    // S = 4*X*Y^2
    let y2 = mod_mul(&pt.y, &pt.y, p);
    let s = mod_mul(&BigUint::from_u64(4), &mod_mul(&pt.x, &y2, p), p);

    // X3 = M^2 - 2*S
    let m2 = mod_mul(&m, &m, p);
    let two_s = mod_add(&s, &s, p);
    let x3 = mod_sub(&m2, &two_s, p);

    // Y3 = M*(S - X3) - 8*Y^4
    let s_minus_x3 = mod_sub(&s, &x3, p);
    let y4 = mod_mul(&y2, &y2, p);
    let eight_y4 = mod_mul(&BigUint::from_u64(8), &y4, p);
    let y3 = mod_sub(&mod_mul(&m, &s_minus_x3, p), &eight_y4, p);

    // Z3 = 2*Y*Z
    let z3 = mod_mul(&BigUint::from_u64(2), &mod_mul(&pt.y, &pt.z, p), p);

    JacobianPoint {
        x: x3,
        y: y3,
        z: z3,
    }
}

/// Point addition in Jacobian coordinates.
fn point_add(p1: &JacobianPoint, p2: &JacobianPoint, params: &CurveParams) -> JacobianPoint {
    let p = &params.p;

    if p1.is_infinity() {
        return p2.clone();
    }
    if p2.is_infinity() {
        return p1.clone();
    }

    // U1 = X1*Z2^2, U2 = X2*Z1^2
    let z1_sq = mod_mul(&p1.z, &p1.z, p);
    let z2_sq = mod_mul(&p2.z, &p2.z, p);
    let u1 = mod_mul(&p1.x, &z2_sq, p);
    let u2 = mod_mul(&p2.x, &z1_sq, p);

    // S1 = Y1*Z2^3, S2 = Y2*Z1^3
    let z1_cu = mod_mul(&z1_sq, &p1.z, p);
    let z2_cu = mod_mul(&z2_sq, &p2.z, p);
    let s1 = mod_mul(&p1.y, &z2_cu, p);
    let s2 = mod_mul(&p2.y, &z1_cu, p);

    if u1 == u2 {
        if s1 == s2 {
            // Points are equal, use doubling.
            return point_double(p1, params);
        }
        // Points are inverses of each other.
        return JacobianPoint::infinity();
    }

    // H = U2 - U1
    let h = mod_sub(&u2, &u1, p);
    // R = S2 - S1
    let r = mod_sub(&s2, &s1, p);

    let h2 = mod_mul(&h, &h, p);
    let h3 = mod_mul(&h2, &h, p);
    let u1_h2 = mod_mul(&u1, &h2, p);

    // X3 = R^2 - H^3 - 2*U1*H^2
    let r2 = mod_mul(&r, &r, p);
    let two_u1_h2 = mod_add(&u1_h2, &u1_h2, p);
    let x3 = mod_sub(&mod_sub(&r2, &h3, p), &two_u1_h2, p);

    // Y3 = R*(U1*H^2 - X3) - S1*H^3
    let y3 = mod_sub(
        &mod_mul(&r, &mod_sub(&u1_h2, &x3, p), p),
        &mod_mul(&s1, &h3, p),
        p,
    );

    // Z3 = H*Z1*Z2
    let z3 = mod_mul(&h, &mod_mul(&p1.z, &p2.z, p), p);

    JacobianPoint {
        x: x3,
        y: y3,
        z: z3,
    }
}

/// Scalar multiplication using the Montgomery ladder (constant-time w.r.t. scalar bits).
#[cfg_attr(not(test), allow(dead_code))]
fn scalar_mult(k: &BigUint, point: &JacobianPoint, params: &CurveParams) -> JacobianPoint {
    let bits = k.bit_len();
    if bits == 0 {
        return JacobianPoint::infinity();
    }

    // Montgomery ladder: R0 = infinity, R1 = point.
    // For each bit from MSB to LSB:
    //   if bit == 0: R1 = R0 + R1, R0 = 2*R0
    //   if bit == 1: R0 = R0 + R1, R1 = 2*R1
    let mut r0 = JacobianPoint::infinity();
    let mut r1 = point.clone();

    for i in (0..bits).rev() {
        if k.bit(i) {
            r0 = point_add(&r0, &r1, params);
            r1 = point_double(&r1, params);
        } else {
            r1 = point_add(&r0, &r1, params);
            r0 = point_double(&r0, params);
        }
    }

    r0
}

/// Multi-scalar multiplication: k1*G + k2*Q using Shamir's trick.
fn multi_scalar_mult(
    k1: &BigUint,
    g: &JacobianPoint,
    k2: &BigUint,
    q: &JacobianPoint,
    params: &CurveParams,
) -> JacobianPoint {
    // Precompute G + Q.
    let g_plus_q = point_add(g, q, params);

    let bits1 = k1.bit_len();
    let bits2 = k2.bit_len();
    let max_bits = bits1.max(bits2);

    let mut result = JacobianPoint::infinity();

    for i in (0..max_bits).rev() {
        result = point_double(&result, params);

        let b1 = k1.bit(i);
        let b2 = k2.bit(i);

        match (b1, b2) {
            (true, true) => result = point_add(&result, &g_plus_q, params),
            (true, false) => result = point_add(&result, g, params),
            (false, true) => result = point_add(&result, q, params),
            (false, false) => {}
        }
    }

    result
}

// ---------------------------------------------------------------------------
// Point validation
// ---------------------------------------------------------------------------

/// Verify that (x, y) is a valid point on the curve: y^2 = x^3 + ax + b (mod p).
fn is_on_curve(x: &BigUint, y: &BigUint, params: &CurveParams) -> bool {
    let p = &params.p;

    // y^2 mod p
    let y2 = mod_mul(y, y, p);

    // x^3 + ax + b mod p
    let x2 = mod_mul(x, x, p);
    let x3 = mod_mul(&x2, x, p);
    let ax = mod_mul(&params.a, x, p);
    let rhs = mod_add(&mod_add(&x3, &ax, p), &params.b, p);

    y2 == rhs
}

// ---------------------------------------------------------------------------
// ECDSA public key
// ---------------------------------------------------------------------------

/// An ECDSA public key.
#[derive(Debug, Clone)]
pub struct EcdsaPublicKey {
    /// The curve this key is on.
    pub curve: Curve,
    /// The public key point x-coordinate.
    pub x: BigUint,
    /// The public key point y-coordinate.
    pub y: BigUint,
}

impl EcdsaPublicKey {
    /// Create a public key from uncompressed point bytes (0x04 || x || y).
    pub fn from_uncompressed(curve: Curve, data: &[u8]) -> Result<Self> {
        let params = curve_params(curve);
        let expected_len = 1 + 2 * params.field_len;

        if data.len() != expected_len || data[0] != 0x04 {
            return Err(EcdsaError::InvalidPublicKey);
        }

        let x = BigUint::from_be_bytes(&data[1..1 + params.field_len]);
        let y = BigUint::from_be_bytes(&data[1 + params.field_len..]);

        // Validate the point is on the curve.
        if !is_on_curve(&x, &y, &params) {
            return Err(EcdsaError::InvalidPublicKey);
        }

        Ok(Self { curve, x, y })
    }

    /// Parse an EC public key from DER-encoded SubjectPublicKeyInfo.
    ///
    /// ```asn1
    /// SubjectPublicKeyInfo ::= SEQUENCE {
    ///     algorithm AlgorithmIdentifier,
    ///     subjectPublicKey BIT STRING
    /// }
    /// AlgorithmIdentifier ::= SEQUENCE {
    ///     algorithm OID,        -- ecPublicKey
    ///     parameters OID        -- curve OID
    /// }
    /// ```
    pub fn from_spki_der(data: &[u8]) -> Result<Self> {
        let seq = asn1::parse_one(data)?;
        if seq.tag != TAG_SEQUENCE {
            return Err(EcdsaError::InvalidKeyFormat);
        }

        let items = seq.sequence_items()?;
        if items.len() != 2 {
            return Err(EcdsaError::InvalidKeyFormat);
        }

        // Parse AlgorithmIdentifier.
        let alg_id = &items[0];
        if alg_id.tag != TAG_SEQUENCE {
            return Err(EcdsaError::InvalidKeyFormat);
        }
        let alg_items = alg_id.sequence_items()?;
        if alg_items.len() < 2 {
            return Err(EcdsaError::InvalidKeyFormat);
        }

        // Verify algorithm OID is ecPublicKey.
        let alg_oid = alg_items[0].as_oid()?;
        if !alg_oid.matches(OID_EC_PUBLIC_KEY) {
            return Err(EcdsaError::InvalidKeyFormat);
        }

        // Determine curve from parameters OID.
        let curve_oid = alg_items[1].as_oid()?;
        let curve = if curve_oid.matches(OID_PRIME256V1) {
            Curve::P256
        } else if curve_oid.matches(OID_SECP384R1) {
            Curve::P384
        } else {
            return Err(EcdsaError::UnsupportedCurve);
        };

        // Parse the BIT STRING containing the uncompressed point.
        let (unused_bits, key_data) = items[1].as_bit_string()?;
        if unused_bits != 0 {
            return Err(EcdsaError::InvalidKeyFormat);
        }

        Self::from_uncompressed(curve, key_data)
    }

    /// Verify an ECDSA signature over a message.
    ///
    /// The hash algorithm is determined by the curve:
    /// - P-256 uses SHA-256
    /// - P-384 uses SHA-384
    pub fn verify(&self, message: &[u8], signature: &EcdsaSignature) -> Result<()> {
        let hash = match self.curve {
            Curve::P256 => sha256(message).to_vec(),
            Curve::P384 => sha384(message).to_vec(),
        };

        self.verify_prehashed(&hash, signature)
    }

    /// Verify an ECDSA signature given a pre-computed hash.
    pub fn verify_prehashed(&self, hash: &[u8], signature: &EcdsaSignature) -> Result<()> {
        let params = curve_params(self.curve);
        let n = &params.n;
        let one = BigUint::one();

        // Verify r, s in [1, n-1].
        let n_minus_1 = n.sub(&one);
        if signature.r.is_zero()
            || signature.r.cmp(&n_minus_1) == Ordering::Greater
            || signature.s.is_zero()
            || signature.s.cmp(&n_minus_1) == Ordering::Greater
        {
            return Err(EcdsaError::SignatureOutOfRange);
        }

        // Convert hash to integer z (truncated to field length if needed).
        let z = hash_to_integer(hash, &params);

        // w = s^(-1) mod n
        let w = mod_inv(&signature.s, n);

        // u1 = z * w mod n
        let u1 = mod_mul(&z, &w, n);
        // u2 = r * w mod n
        let u2 = mod_mul(&signature.r, &w, n);

        // (x1, y1) = u1*G + u2*Q
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let q = JacobianPoint::from_affine(&self.x, &self.y);

        let point = multi_scalar_mult(&u1, &g, &u2, &q, &params);

        if point.is_infinity() {
            return Err(EcdsaError::VerificationFailed);
        }

        let (x1, _) = point.to_affine(&params.p);

        // v = x1 mod n
        let v = x1.modulo(n);

        if v == signature.r {
            Ok(())
        } else {
            Err(EcdsaError::VerificationFailed)
        }
    }
}

/// Convert hash bytes to an integer, truncating to the curve's bit length if needed.
fn hash_to_integer(hash: &[u8], params: &CurveParams) -> BigUint {
    let n_bits = params.n.bit_len();
    let hash_bits = hash.len() * 8;

    if hash_bits <= n_bits {
        BigUint::from_be_bytes(hash)
    } else {
        // Truncate: take the leftmost n_bits bits.
        let z = BigUint::from_be_bytes(hash);
        let shift = hash_bits - n_bits;
        // Right-shift by `shift` bits to keep only the top n_bits.
        // Since BigUint doesn't expose a general right-shift, we use division.
        let divisor = BigUint::from_u64(1u64 << shift.min(63));
        if shift <= 63 {
            z.div_rem(&divisor).0
        } else {
            // For very large shifts, this shouldn't happen with P-256/P-384 + SHA-256/384.
            z
        }
    }
}

// ---------------------------------------------------------------------------
// ECDSA signature
// ---------------------------------------------------------------------------

/// An ECDSA signature (r, s).
#[derive(Debug, Clone)]
pub struct EcdsaSignature {
    pub r: BigUint,
    pub s: BigUint,
}

impl EcdsaSignature {
    /// Create from raw r, s values.
    pub fn new(r: BigUint, s: BigUint) -> Self {
        Self { r, s }
    }

    /// Parse from DER-encoded signature.
    ///
    /// ```asn1
    /// ECDSA-Sig-Value ::= SEQUENCE {
    ///     r INTEGER,
    ///     s INTEGER
    /// }
    /// ```
    pub fn from_der(data: &[u8]) -> Result<Self> {
        let seq = asn1::parse_one(data)?;
        if seq.tag != TAG_SEQUENCE {
            return Err(EcdsaError::InvalidSignature);
        }

        let items = seq.sequence_items()?;
        if items.len() != 2 {
            return Err(EcdsaError::InvalidSignature);
        }

        let r_bytes = items[0]
            .as_positive_integer()
            .map_err(|_| EcdsaError::InvalidSignature)?;
        let s_bytes = items[1]
            .as_positive_integer()
            .map_err(|_| EcdsaError::InvalidSignature)?;

        Ok(Self {
            r: BigUint::from_be_bytes(r_bytes),
            s: BigUint::from_be_bytes(s_bytes),
        })
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    fn hex_to_bytes(s: &str) -> Vec<u8> {
        let s = s.replace(' ', "").replace('\n', "");
        (0..s.len())
            .step_by(2)
            .map(|i| u8::from_str_radix(&s[i..i + 2], 16).unwrap())
            .collect()
    }

    // -------------------------------------------------------------------
    // Curve parameter validation
    // -------------------------------------------------------------------

    #[test]
    fn p256_generator_on_curve() {
        let params = p256_params();
        assert!(is_on_curve(&params.gx, &params.gy, &params));
    }

    #[test]
    fn p384_generator_on_curve() {
        let params = p384_params();
        assert!(is_on_curve(&params.gx, &params.gy, &params));
    }

    // -------------------------------------------------------------------
    // Point arithmetic
    // -------------------------------------------------------------------

    #[test]
    fn point_double_p256() {
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let two_g = point_double(&g, &params);
        let (x, y) = two_g.to_affine(&params.p);
        assert!(is_on_curve(&x, &y, &params));
    }

    #[test]
    fn point_add_p256() {
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let two_g = point_double(&g, &params);
        let three_g = point_add(&two_g, &g, &params);
        let (x, y) = three_g.to_affine(&params.p);
        assert!(is_on_curve(&x, &y, &params));
    }

    #[test]
    fn scalar_mult_identity() {
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let result = scalar_mult(&BigUint::one(), &g, &params);
        let (x, y) = result.to_affine(&params.p);
        assert_eq!(x, params.gx);
        assert_eq!(y, params.gy);
    }

    #[test]
    fn scalar_mult_two() {
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let two_g_direct = point_double(&g, &params);
        let two_g_scalar = scalar_mult(&BigUint::from_u64(2), &g, &params);

        let (x1, y1) = two_g_direct.to_affine(&params.p);
        let (x2, y2) = two_g_scalar.to_affine(&params.p);
        assert_eq!(x1, x2);
        assert_eq!(y1, y2);
    }

    #[test]
    fn scalar_mult_three() {
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let two_g = point_double(&g, &params);
        let three_g_direct = point_add(&two_g, &g, &params);
        let three_g_scalar = scalar_mult(&BigUint::from_u64(3), &g, &params);

        let (x1, y1) = three_g_direct.to_affine(&params.p);
        let (x2, y2) = three_g_scalar.to_affine(&params.p);
        assert_eq!(x1, x2);
        assert_eq!(y1, y2);
    }

    #[test]
    fn scalar_mult_order_gives_infinity() {
        // n * G = O (point at infinity)
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        let result = scalar_mult(&params.n, &g, &params);
        assert!(result.is_infinity());
    }

    #[test]
    fn point_add_inverse_gives_infinity() {
        // G + (-G) = O
        let params = p256_params();
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);
        // -G has y-coordinate = p - Gy
        let neg_gy = params.p.sub(&params.gy);
        let neg_g = JacobianPoint::from_affine(&params.gx, &neg_gy);
        let result = point_add(&g, &neg_g, &params);
        assert!(result.is_infinity());
    }

    // -------------------------------------------------------------------
    // Public key parsing and validation
    // -------------------------------------------------------------------

    #[test]
    fn public_key_from_uncompressed_p256() {
        let params = p256_params();
        let mut data = vec![0x04];
        data.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        data.extend_from_slice(&params.gy.to_be_bytes_padded(32));

        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &data).unwrap();
        assert_eq!(key.x, params.gx);
        assert_eq!(key.y, params.gy);
    }

    #[test]
    fn public_key_reject_not_on_curve() {
        let mut data = vec![0x04];
        data.extend_from_slice(&[0x01; 32]); // x = 1
        data.extend_from_slice(&[0x01; 32]); // y = 1
        let result = EcdsaPublicKey::from_uncompressed(Curve::P256, &data);
        assert_eq!(result.unwrap_err(), EcdsaError::InvalidPublicKey);
    }

    #[test]
    fn public_key_reject_wrong_prefix() {
        let params = p256_params();
        let mut data = vec![0x03]; // compressed, not supported
        data.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        data.extend_from_slice(&params.gy.to_be_bytes_padded(32));

        let result = EcdsaPublicKey::from_uncompressed(Curve::P256, &data);
        assert_eq!(result.unwrap_err(), EcdsaError::InvalidPublicKey);
    }

    #[test]
    fn public_key_reject_wrong_length() {
        let result = EcdsaPublicKey::from_uncompressed(Curve::P256, &[0x04; 10]);
        assert_eq!(result.unwrap_err(), EcdsaError::InvalidPublicKey);
    }

    // -------------------------------------------------------------------
    // Signature parsing
    // -------------------------------------------------------------------

    #[test]
    fn signature_from_der() {
        // SEQUENCE { INTEGER 1, INTEGER 2 }
        let der = hex_to_bytes("3006020101020102");
        let sig = EcdsaSignature::from_der(&der).unwrap();
        assert_eq!(sig.r, BigUint::from_u64(1));
        assert_eq!(sig.s, BigUint::from_u64(2));
    }

    #[test]
    fn signature_reject_invalid_der() {
        let result = EcdsaSignature::from_der(&[0x00, 0x01]);
        assert!(result.is_err());
    }

    // -------------------------------------------------------------------
    // ECDSA verification: self-generated test vectors
    // -------------------------------------------------------------------

    /// Generate an ECDSA signature for testing (not for production use).
    /// Returns (public_key_x, public_key_y, r, s).
    fn sign_for_test(
        d: &BigUint,
        k: &BigUint,
        msg_hash: &[u8],
        params: &CurveParams,
    ) -> (BigUint, BigUint, BigUint, BigUint) {
        let n = &params.n;
        let g = JacobianPoint::from_affine(&params.gx, &params.gy);

        // Q = d*G
        let q = scalar_mult(d, &g, params);
        let (qx, qy) = q.to_affine(&params.p);

        // (rx, _) = k*G
        let kg = scalar_mult(k, &g, params);
        let (kgx, _) = kg.to_affine(&params.p);
        let r = kgx.modulo(n);

        // s = k^(-1) * (z + r*d) mod n
        let z = hash_to_integer(msg_hash, params);
        let k_inv = mod_inv(k, n);
        let rd = mod_mul(&r, d, n);
        let z_plus_rd = mod_add(&z, &rd, n);
        let s = mod_mul(&k_inv, &z_plus_rd, n);

        (qx, qy, r, s)
    }

    #[test]
    fn verify_self_generated_p256() {
        let params = p256_params();
        let msg = b"hello world";
        let hash = sha256(msg);

        // Arbitrary private key and nonce (must be in [1, n-1]).
        let d = BigUint::from_u64(123456789);
        let k = BigUint::from_u64(987654321);

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(r, s);
        let result = key.verify(msg, &sig);
        assert!(
            result.is_ok(),
            "self-generated P-256 signature should verify: {result:?}"
        );
    }

    #[test]
    fn verify_self_generated_p256_different_key() {
        let params = p256_params();
        let msg = b"test message for ecdsa verification";
        let hash = sha256(msg);

        let d = BigUint::from_be_bytes(&hex_to_bytes(
            "c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721",
        ));
        let k = BigUint::from_be_bytes(&hex_to_bytes(
            "a6e3c57dd01abe90086538398355dd4c3b17aa873382b0f24d6129493d8aad60",
        ));

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(r, s);
        let result = key.verify(msg, &sig);
        assert!(
            result.is_ok(),
            "P-256 with RFC 6979 key should verify: {result:?}"
        );
    }

    #[test]
    fn verify_self_generated_p256_tampered() {
        let params = p256_params();
        let msg = b"hello world";
        let hash = sha256(msg);

        let d = BigUint::from_u64(123456789);
        let k = BigUint::from_u64(987654321);

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        // Tamper with the signature.
        let tampered_s = s.add(&BigUint::one());
        let sig = EcdsaSignature::new(r, tampered_s);
        let result = key.verify(msg, &sig);
        assert!(result.is_err(), "tampered signature should fail");
    }

    #[test]
    fn verify_self_generated_p256_wrong_message() {
        let params = p256_params();
        let msg = b"hello world";
        let hash = sha256(msg);

        let d = BigUint::from_u64(123456789);
        let k = BigUint::from_u64(987654321);

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(r, s);
        let result = key.verify(b"wrong message", &sig);
        assert!(result.is_err(), "wrong message should fail verification");
    }

    #[test]
    fn verify_self_generated_p384() {
        let params = p384_params();
        let msg = b"hello p384";
        let hash = sha384(msg);

        let d = BigUint::from_u64(999999937); // a prime number
        let k = BigUint::from_u64(999999893); // another prime

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(48));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(48));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P384, &point_data).unwrap();

        let sig = EcdsaSignature::new(r, s);
        let result = key.verify(msg, &sig);
        assert!(
            result.is_ok(),
            "self-generated P-384 signature should verify: {result:?}"
        );
    }

    #[test]
    fn verify_self_generated_p384_wrong_message() {
        let params = p384_params();
        let msg = b"hello p384";
        let hash = sha384(msg);

        let d = BigUint::from_u64(999999937);
        let k = BigUint::from_u64(999999893);

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(48));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(48));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P384, &point_data).unwrap();

        let sig = EcdsaSignature::new(r, s);
        let result = key.verify(b"different message", &sig);
        assert!(result.is_err(), "P-384 wrong message should fail");
    }

    // -------------------------------------------------------------------
    // RFC 6979 test vector (P-256, SHA-256, message "sample")
    // -------------------------------------------------------------------

    #[test]
    fn verify_rfc6979_p256_sha256() {
        // From RFC 6979, Appendix A.2.5.
        // Private key x = C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721
        // Public key:
        let qx = hex_to_bytes("60FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB6");
        let qy = hex_to_bytes("7903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299");
        // Message: "sample", signature with SHA-256:
        let r = hex_to_bytes("EFD48B2AACB6A8FD1140DD9CD45E81D69D2C877B56AAF991C34D0EA84EAF3716");
        let s = hex_to_bytes("F7CB1C942D657C41D436C7A1B6E29F65F3E900DBB9AFF4064DC4AB2F843ACDA8");

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx);
        point_data.extend_from_slice(&qy);
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(BigUint::from_be_bytes(&r), BigUint::from_be_bytes(&s));

        let result = key.verify(b"sample", &sig);
        assert!(
            result.is_ok(),
            "RFC 6979 P-256/SHA-256 'sample' should verify: {result:?}"
        );
    }

    #[test]
    fn verify_rfc6979_p256_sha256_test() {
        // From RFC 6979, Appendix A.2.5, message "test".
        let qx = hex_to_bytes("60FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB6");
        let qy = hex_to_bytes("7903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299");
        let r = hex_to_bytes("F1ABB023518351CD71D881567B1EA663ED3EFCF6C5132B354F28D3B0B7D38367");
        let s = hex_to_bytes("019F4113742A2B14BD25926B49C649155F267E60D3814B4C0CC84250E46F0083");

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx);
        point_data.extend_from_slice(&qy);
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(BigUint::from_be_bytes(&r), BigUint::from_be_bytes(&s));

        let result = key.verify(b"test", &sig);
        assert!(
            result.is_ok(),
            "RFC 6979 P-256/SHA-256 'test' should verify: {result:?}"
        );
    }

    // -------------------------------------------------------------------
    // Prehashed verification
    // -------------------------------------------------------------------

    #[test]
    fn verify_prehashed_p256() {
        let params = p256_params();
        let msg = b"prehash test";
        let hash = sha256(msg);

        let d = BigUint::from_u64(42424242);
        let k = BigUint::from_u64(13131313);

        let (qx, qy, r, s) = sign_for_test(&d, &k, &hash, &params);

        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&qx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&qy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(r, s);
        let result = key.verify_prehashed(&hash, &sig);
        assert!(result.is_ok(), "prehashed verify should pass: {result:?}");
    }

    // -------------------------------------------------------------------
    // Signature rejection tests
    // -------------------------------------------------------------------

    #[test]
    fn reject_signature_r_zero() {
        let params = p256_params();
        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&params.gy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(BigUint::zero(), BigUint::one());
        let result = key.verify(b"test", &sig);
        assert_eq!(result.unwrap_err(), EcdsaError::SignatureOutOfRange);
    }

    #[test]
    fn reject_signature_s_zero() {
        let params = p256_params();
        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&params.gy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(BigUint::one(), BigUint::zero());
        let result = key.verify(b"test", &sig);
        assert_eq!(result.unwrap_err(), EcdsaError::SignatureOutOfRange);
    }

    #[test]
    fn reject_signature_r_equals_n() {
        let params = p256_params();
        let mut point_data = vec![0x04];
        point_data.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        point_data.extend_from_slice(&params.gy.to_be_bytes_padded(32));
        let key = EcdsaPublicKey::from_uncompressed(Curve::P256, &point_data).unwrap();

        let sig = EcdsaSignature::new(params.n.clone(), BigUint::one());
        let result = key.verify(b"test", &sig);
        assert_eq!(result.unwrap_err(), EcdsaError::SignatureOutOfRange);
    }

    // -------------------------------------------------------------------
    // SPKI DER parsing
    // -------------------------------------------------------------------

    /// Encode a DER length.
    fn der_length(len: usize) -> Vec<u8> {
        if len < 0x80 {
            vec![len as u8]
        } else if len < 0x100 {
            vec![0x81, len as u8]
        } else {
            vec![0x82, (len >> 8) as u8, len as u8]
        }
    }

    /// Build a DER TLV.
    fn der_tlv(tag: u8, value: &[u8]) -> Vec<u8> {
        let mut out = vec![tag];
        out.extend_from_slice(&der_length(value.len()));
        out.extend_from_slice(value);
        out
    }

    #[test]
    fn parse_spki_p256() {
        let params = p256_params();

        // Build AlgorithmIdentifier: SEQUENCE { OID ecPublicKey, OID prime256v1 }
        let alg_oid = der_tlv(0x06, OID_EC_PUBLIC_KEY);
        let curve_oid = der_tlv(0x06, OID_PRIME256V1);
        let mut alg_content = Vec::new();
        alg_content.extend_from_slice(&alg_oid);
        alg_content.extend_from_slice(&curve_oid);
        let alg_id = der_tlv(0x30, &alg_content);

        // Build BIT STRING with uncompressed point.
        let mut point = vec![0x04];
        point.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        point.extend_from_slice(&params.gy.to_be_bytes_padded(32));
        let mut bit_string_value = vec![0x00]; // unused bits
        bit_string_value.extend_from_slice(&point);
        let bit_string = der_tlv(0x03, &bit_string_value);

        let mut spki_content = Vec::new();
        spki_content.extend_from_slice(&alg_id);
        spki_content.extend_from_slice(&bit_string);
        let spki = der_tlv(0x30, &spki_content);

        let key = EcdsaPublicKey::from_spki_der(&spki).unwrap();
        assert_eq!(key.curve, Curve::P256);
        assert_eq!(key.x, params.gx);
        assert_eq!(key.y, params.gy);
    }

    #[test]
    fn parse_spki_p384() {
        let params = p384_params();

        let alg_oid = der_tlv(0x06, OID_EC_PUBLIC_KEY);
        let curve_oid = der_tlv(0x06, OID_SECP384R1);
        let mut alg_content = Vec::new();
        alg_content.extend_from_slice(&alg_oid);
        alg_content.extend_from_slice(&curve_oid);
        let alg_id = der_tlv(0x30, &alg_content);

        let mut point = vec![0x04];
        point.extend_from_slice(&params.gx.to_be_bytes_padded(48));
        point.extend_from_slice(&params.gy.to_be_bytes_padded(48));
        let mut bit_string_value = vec![0x00];
        bit_string_value.extend_from_slice(&point);
        let bit_string = der_tlv(0x03, &bit_string_value);

        let mut spki_content = Vec::new();
        spki_content.extend_from_slice(&alg_id);
        spki_content.extend_from_slice(&bit_string);
        let spki = der_tlv(0x30, &spki_content);

        let key = EcdsaPublicKey::from_spki_der(&spki).unwrap();
        assert_eq!(key.curve, Curve::P384);
        assert_eq!(key.x, params.gx);
        assert_eq!(key.y, params.gy);
    }

    #[test]
    fn parse_spki_reject_wrong_algorithm() {
        let params = p256_params();

        // Use RSA OID instead of ecPublicKey.
        let wrong_oid = der_tlv(
            0x06,
            &[0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x01, 0x01, 0x01],
        );
        let curve_oid = der_tlv(0x06, OID_PRIME256V1);
        let mut alg_content = Vec::new();
        alg_content.extend_from_slice(&wrong_oid);
        alg_content.extend_from_slice(&curve_oid);
        let alg_id = der_tlv(0x30, &alg_content);

        let mut point = vec![0x04];
        point.extend_from_slice(&params.gx.to_be_bytes_padded(32));
        point.extend_from_slice(&params.gy.to_be_bytes_padded(32));
        let mut bit_string_value = vec![0x00];
        bit_string_value.extend_from_slice(&point);
        let bit_string = der_tlv(0x03, &bit_string_value);

        let mut spki_content = Vec::new();
        spki_content.extend_from_slice(&alg_id);
        spki_content.extend_from_slice(&bit_string);
        let spki = der_tlv(0x30, &spki_content);

        let result = EcdsaPublicKey::from_spki_der(&spki);
        assert_eq!(result.unwrap_err(), EcdsaError::InvalidKeyFormat);
    }

    // -------------------------------------------------------------------
    // Modular arithmetic
    // -------------------------------------------------------------------

    #[test]
    fn mod_sub_no_underflow() {
        let a = BigUint::from_u64(10);
        let b = BigUint::from_u64(3);
        let m = BigUint::from_u64(17);
        assert_eq!(mod_sub(&a, &b, &m), BigUint::from_u64(7));
    }

    #[test]
    fn mod_sub_with_underflow() {
        let a = BigUint::from_u64(3);
        let b = BigUint::from_u64(10);
        let m = BigUint::from_u64(17);
        // 3 - 10 mod 17 = -7 mod 17 = 10
        assert_eq!(mod_sub(&a, &b, &m), BigUint::from_u64(10));
    }

    #[test]
    fn mod_inv_basic() {
        // 3^(-1) mod 7 = 5 (since 3*5 = 15 = 1 mod 7)
        let a = BigUint::from_u64(3);
        let m = BigUint::from_u64(7);
        let inv = mod_inv(&a, &m);
        assert_eq!(inv, BigUint::from_u64(5));
    }

    #[test]
    fn mod_inv_verify() {
        // a * a^(-1) mod p = 1
        let a = BigUint::from_u64(12345);
        let p = BigUint::from_u64(65537); // prime
        let inv = mod_inv(&a, &p);
        let product = mod_mul(&a, &inv, &p);
        assert_eq!(product, BigUint::one());
    }
}