cryptography/public_key/

ecdsa.rs

//! Elliptic-Curve Digital Signature Algorithm (ECDSA, FIPS 186-5).
//!
//! ECDSA is the elliptic-curve analogue of DSA: rather than computing scalar
//! multiplications in a prime subgroup of `Z_p^*`, it uses the group of points
//! on a short-Weierstrass elliptic curve and produces the same `(r, s)`
//! signature shape.
//!
//! ## Algorithm summary
//!
//! **Key generation**: Choose a named curve with generator `G` and prime order
//! `n`.  Sample a uniform random scalar `d ∈ [1, n)` and set `Q = d·G`.
//! The public key is `(curve, Q)`; the private key is `(curve, d)`.
//!
//! **Signing** (given message digest representative `z` and nonce `k ∈ [1, n)`):
//! 1. Compute `(x₁, y₁) = k·G`.
//! 2. Set `r = x₁ mod n`.  If `r = 0`, retry with a new `k`.
//! 3. Set `s = k⁻¹ · (z + r·d) mod n`.  If `s = 0`, retry.
//!
//! **Verification** (given public key `Q`, representative `z`, signature `(r, s)`):
//! 1. Check `r, s ∈ [1, n)`.
//! 2. Compute `w = s⁻¹ mod n`, `u₁ = z·w mod n`, `u₂ = r·w mod n`.
//! 3. Compute `(x₁, y₁) = u₁·G + u₂·Q`.
//! 4. Accept if and only if `r ≡ x₁ (mod n)`.
//!
//! ## Side-channel note
//!
//! The scalar multiplication in [`ec`] is not constant-time (left-to-right
//! double-and-add, branching on secret bits).  This implementation is
//! suitable for educational and experimental use.  Replace the scalar-mul
//! loop with a Montgomery ladder before deploying in an environment with
//! side-channel adversaries.
//!
//! [`ec`]: crate::public_key::ec

use core::fmt;

use crate::hash::Digest;
use crate::public_key::bigint::BigUint;
use crate::public_key::ec::{AffinePoint, CurveParams};
use crate::public_key::io::{
    decode_biguints, encode_biguints, pem_unwrap, pem_wrap, xml_unwrap, xml_wrap,
};
use crate::public_key::primes::{mod_inverse, random_nonzero_below};
use crate::Csprng;
use crate::Hmac;

const ECDSA_PUBLIC_LABEL: &str = "CRYPTOGRAPHY ECDSA PUBLIC KEY";
const ECDSA_PRIVATE_LABEL: &str = "CRYPTOGRAPHY ECDSA PRIVATE KEY";

// ─── Key and signature types ─────────────────────────────────────────────────

/// Public key for ECDSA.
///
/// Stores the curve parameters and the public point `Q = d·G`.
#[derive(Clone, Debug)]
pub struct EcdsaPublicKey {
    /// Full short-Weierstrass curve parameters for this key.
    curve: CurveParams,
    /// Public point `Q = d·G`.
    q: AffinePoint,
}

/// Private key for ECDSA.
///
/// Stores the curve parameters and the secret scalar `d ∈ [1, n)`.
/// The matching public key is derived on demand via [`to_public_key`].
///
/// [`to_public_key`]: EcdsaPrivateKey::to_public_key
#[derive(Clone)]
pub struct EcdsaPrivateKey {
    /// Full short-Weierstrass curve parameters for this key.
    curve: CurveParams,
    /// Secret scalar `d ∈ [1, n)`.
    d: BigUint,
    /// Cached public point `Q = d·G`.
    q: AffinePoint,
}

/// Raw ECDSA signature pair `(r, s)`.
///
/// Both components are positive integers in `[1, n)` relative to the subgroup
/// order of the signing curve.  The serialized form is a DER `SEQUENCE` of
/// two `INTEGER` values, matching the shape used by [`DsaSignature`].
///
/// [`DsaSignature`]: crate::public_key::dsa::DsaSignature
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct EcdsaSignature {
    r: BigUint,
    s: BigUint,
}

pub struct Ecdsa;

// ─── EcdsaPublicKey ───────────────────────────────────────────────────────────

impl EcdsaPublicKey {
    /// The curve parameters for this key.
    #[must_use]
    pub fn curve(&self) -> &CurveParams {
        &self.curve
    }

    /// The public point `Q = d·G`.
    #[must_use]
    pub fn public_point(&self) -> &AffinePoint {
        &self.q
    }

    /// Encode the public point as a compact SEC 1 point string.
    #[must_use]
    pub fn to_wire_bytes(&self) -> Vec<u8> {
        self.curve.encode_point(&self.q)
    }

    /// Rebuild a public key from a compact SEC 1 point string plus explicit curve parameters.
    #[must_use]
    pub fn from_wire_bytes(curve: CurveParams, bytes: &[u8]) -> Option<Self> {
        let q = curve.decode_point(bytes)?;
        // Same subgroup check as from_key_blob: reject torsion points on
        // curves with h > 1 (e.g. binary curves where h = 2).
        if !curve.scalar_mul(&q, &curve.n).is_infinity() {
            return None;
        }
        Some(Self { curve, q })
    }

    /// Convenience: hashes `message` with `H` then calls [`verify`][Self::verify].
    #[must_use]
    pub fn verify_message<H: Digest>(&self, message: &[u8], signature: &EcdsaSignature) -> bool {
        let digest = H::digest(message);
        self.verify(&digest, signature)
    }

    /// Convenience: hashes `message` with `H` then calls [`verify_bytes`][Self::verify_bytes].
    #[must_use]
    pub fn verify_message_bytes<H: Digest>(&self, message: &[u8], signature: &[u8]) -> bool {
        let digest = H::digest(message);
        self.verify_bytes(&digest, signature)
    }

    /// Verify `signature` over a raw digest byte string.
    ///
    /// The digest is reduced to a scalar representative matching FIPS 186-5
    /// (leftmost `bits(n)` bits of the hash output).
    #[must_use]
    pub fn verify(&self, digest: &[u8], signature: &EcdsaSignature) -> bool {
        let z = digest_to_scalar(digest, &self.curve.n);
        self.verify_digest_scalar(&z, signature)
    }

    /// Core ECDSA verification over a pre-reduced scalar `z`.
    #[must_use]
    pub fn verify_digest_scalar(&self, hash: &BigUint, signature: &EcdsaSignature) -> bool {
        let n = &self.curve.n;

        // Both components must lie in [1, n).
        if signature.r.is_zero() || signature.s.is_zero() || &signature.r >= n || &signature.s >= n
        {
            return false;
        }

        // Reject high-s to prevent malleability: for any valid (r, s), the
        // pair (r, n-s) also satisfies the verification equation, so without
        // this check two distinct byte strings verify for the same message.
        // Matches the low-s enforcement in sign_digest_with_nonce.
        let mut half_n = n.clone();
        half_n.shr1();
        if signature.s.cmp(&half_n).is_gt() {
            return false;
        }

        let Some(w) = mod_inverse(&signature.s, n) else {
            return false;
        };

        // u₁ = z·w mod n,  u₂ = r·w mod n
        let u1 = BigUint::mod_mul(hash, &w, n);
        let u2 = BigUint::mod_mul(&signature.r, &w, n);

        // (x₁, y₁) = u₁·G + u₂·Q
        let g = self.curve.base_point();
        let term1 = self.curve.scalar_mul(&g, &u1);
        let term2 = self.curve.scalar_mul(&self.q, &u2);
        let sum = self.curve.add(&term1, &term2);

        if sum.is_infinity() {
            return false;
        }

        // Accept iff r ≡ x₁ (mod n).
        sum.x.modulo(n) == signature.r
    }

    /// Verify a byte-encoded signature produced by [`EcdsaPrivateKey::sign_bytes`].
    #[must_use]
    pub fn verify_bytes(&self, digest: &[u8], signature: &[u8]) -> bool {
        let Some(sig) = EcdsaSignature::from_key_blob(signature) else {
            return false;
        };
        self.verify(digest, &sig)
    }

    /// Encode the public key in the crate-defined binary format.
    ///
    /// Layout: one field-type byte (`0x00` = prime, `0x01` = binary) followed
    /// by `[p, a, b, n, h, Gx, Gy, Qx, Qy]` as a DER `SEQUENCE` of positive
    /// `INTEGER`s.
    #[must_use]
    pub fn to_key_blob(&self) -> Vec<u8> {
        let h = BigUint::from_u64(self.curve.h);
        let field_byte = u8::from(self.curve.gf2m_degree().is_some());
        let mut out = vec![field_byte];
        out.extend_from_slice(&encode_biguints(&[
            &self.curve.p,
            &self.curve.a,
            &self.curve.b,
            &self.curve.n,
            &h,
            &self.curve.gx,
            &self.curve.gy,
            &self.q.x,
            &self.q.y,
        ]));
        out
    }

    /// Decode a public key from the crate-defined binary format.
    #[must_use]
    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
        let (&field_type, rest) = blob.split_first()?;
        let mut fields = decode_biguints(rest)?.into_iter();
        let field_prime = fields.next()?;
        let curve_a = fields.next()?;
        let curve_b = fields.next()?;
        let subgroup_order = fields.next()?;
        let cofactor_big = fields.next()?;
        let base_x = fields.next()?;
        let base_y = fields.next()?;
        let public_x = fields.next()?;
        let public_y = fields.next()?;
        if fields.next().is_some() {
            return None;
        }
        let cofactor = biguint_to_u64(&cofactor_big)?;
        let curve = if field_type == 0x01 {
            let field_degree = field_prime.bits().checked_sub(1)?;
            CurveParams::new_binary(
                field_prime,
                field_degree,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                (base_x, base_y),
            )?
        } else {
            CurveParams::new(
                field_prime,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                base_x,
                base_y,
            )?
        };
        let public_point = AffinePoint::new(public_x, public_y);
        if !curve.is_on_curve(&public_point) {
            return None;
        }
        // For curves with cofactor h > 1 (e.g. binary curves), an on-curve
        // point may lie in a small torsion subgroup of order h rather than n.
        // Verify n·Q = O so that u₂·Q in verification is never decoupled from
        // the private key.  For h = 1 this is always true but costs little.
        if !curve.scalar_mul(&public_point, &curve.n).is_infinity() {
            return None;
        }
        Some(Self {
            curve,
            q: public_point,
        })
    }

    #[must_use]
    pub fn to_pem(&self) -> String {
        pem_wrap(ECDSA_PUBLIC_LABEL, &self.to_key_blob())
    }

    /// Returns `None` if the PEM label does not match or the payload is malformed.
    #[must_use]
    pub fn from_pem(pem: &str) -> Option<Self> {
        let blob = pem_unwrap(ECDSA_PUBLIC_LABEL, pem)?;
        Self::from_key_blob(&blob)
    }

    /// # Panics
    ///
    /// Panics only if a binary-field curve reports a degree that does not fit
    /// in `u64`, which would indicate malformed curve parameters.
    #[must_use]
    pub fn to_xml(&self) -> String {
        let h = BigUint::from_u64(self.curve.h);
        let degree = BigUint::from_u64(
            u64::try_from(self.curve.gf2m_degree().unwrap_or(0)).expect("degree fits in u64"),
        );
        xml_wrap(
            "EcdsaPublicKey",
            &[
                ("p", &self.curve.p),
                ("a", &self.curve.a),
                ("b", &self.curve.b),
                ("n", &self.curve.n),
                ("h", &h),
                ("degree", &degree),
                ("gx", &self.curve.gx),
                ("gy", &self.curve.gy),
                ("qx", &self.q.x),
                ("qy", &self.q.y),
            ],
        )
    }

    /// Returns `None` if the XML root element, tag names, or integer encoding is invalid.
    #[must_use]
    pub fn from_xml(xml: &str) -> Option<Self> {
        let mut fields = xml_unwrap(
            "EcdsaPublicKey",
            &["p", "a", "b", "n", "h", "degree", "gx", "gy", "qx", "qy"],
            xml,
        )?
        .into_iter();
        let field_prime = fields.next()?;
        let curve_a = fields.next()?;
        let curve_b = fields.next()?;
        let subgroup_order = fields.next()?;
        let cofactor_big = fields.next()?;
        let degree_big = fields.next()?;
        let base_x = fields.next()?;
        let base_y = fields.next()?;
        let public_x = fields.next()?;
        let public_y = fields.next()?;
        if fields.next().is_some() {
            return None;
        }
        let cofactor = biguint_to_u64(&cofactor_big)?;
        let field_degree = usize::try_from(biguint_to_u64(&degree_big)?).ok()?;
        let curve = if field_degree > 0 {
            CurveParams::new_binary(
                field_prime,
                field_degree,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                (base_x, base_y),
            )?
        } else {
            CurveParams::new(
                field_prime,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                base_x,
                base_y,
            )?
        };
        let public_point = AffinePoint::new(public_x, public_y);
        if !curve.is_on_curve(&public_point) {
            return None;
        }
        if !curve.scalar_mul(&public_point, &curve.n).is_infinity() {
            return None;
        }
        Some(Self {
            curve,
            q: public_point,
        })
    }
}

// ─── EcdsaPrivateKey ──────────────────────────────────────────────────────────

impl EcdsaPrivateKey {
    /// The curve parameters for this key.
    #[must_use]
    pub fn curve(&self) -> &CurveParams {
        &self.curve
    }

    /// The private scalar `d ∈ [1, n)`.
    #[must_use]
    pub fn private_scalar(&self) -> &BigUint {
        &self.d
    }

    /// Derive the matching public key `Q = d·G`.
    #[must_use]
    pub fn to_public_key(&self) -> EcdsaPublicKey {
        EcdsaPublicKey {
            curve: self.curve.clone(),
            q: self.q.clone(),
        }
    }

    /// Sign with an explicit nonce `k`.
    ///
    /// ECDSA requires a fresh `k ∈ [1, n)` for every signature. This
    /// lower-level entry point keeps the arithmetic explicit for fixed-vector
    /// tests.
    ///
    /// Reusing the same `k` for two different messages with the same key
    /// immediately reveals the private scalar. Outside of fixed vectors,
    /// prefer [`Self::sign_digest`] or [`Self::sign_message`].
    ///
    /// Returned signatures are canonicalized to low-`s` form (`s <= n/2`) to
    /// maximize interoperability with protocols that reject high-`s` ECDSA.
    #[must_use]
    pub fn sign_digest_with_nonce(&self, digest: &[u8], nonce: &BigUint) -> Option<EcdsaSignature> {
        let n = &self.curve.n;
        if nonce.is_zero() || nonce >= n {
            return None;
        }

        let z = digest_to_scalar(digest, n);

        // (x₁, y₁) = k·G
        let r_point = self.curve.scalar_mul(&self.curve.base_point(), nonce);
        if r_point.is_infinity() {
            return None;
        }
        let r = r_point.x.modulo(n);
        if r.is_zero() {
            return None;
        }

        // s = k⁻¹ · (z + r·d) mod n
        let k_inv = mod_inverse(nonce, n)?;
        let rd = BigUint::mod_mul(&r, &self.d, n);
        let z_plus_rd = z.add_ref(&rd).modulo(n);
        let mut s = BigUint::mod_mul(&k_inv, &z_plus_rd, n);
        if s.is_zero() {
            return None;
        }
        canonicalize_low_s(n, &mut s);

        Some(EcdsaSignature { r, s })
    }

    /// Sign a digest using RFC 6979 deterministic nonce derivation.
    #[must_use]
    pub fn sign_digest<H: Digest>(&self, digest: &[u8]) -> Option<EcdsaSignature> {
        let nonce = rfc6979_nonce::<H>(&self.curve.n, &self.d, digest)?;
        self.sign_digest_with_nonce(digest, &nonce)
    }

    /// Sign a digest using a fresh random nonce.
    ///
    /// Retries only in the negligible edge cases where `r = 0` or `s = 0`.
    #[must_use]
    pub fn sign_digest_with_rng<R: Csprng>(
        &self,
        digest: &[u8],
        rng: &mut R,
    ) -> Option<EcdsaSignature> {
        loop {
            let nonce = random_nonzero_below(rng, &self.curve.n)?;
            if let Some(sig) = self.sign_digest_with_nonce(digest, &nonce) {
                return Some(sig);
            }
        }
    }

    /// Hash one message with `H`, then sign deterministically.
    #[must_use]
    pub fn sign_message<H: Digest>(&self, message: &[u8]) -> Option<EcdsaSignature> {
        let digest = H::digest(message);
        self.sign_digest::<H>(&digest)
    }

    /// Hash one message with `H`, then sign with randomized nonces.
    #[must_use]
    pub fn sign_message_with_rng<H: Digest, R: Csprng>(
        &self,
        message: &[u8],
        rng: &mut R,
    ) -> Option<EcdsaSignature> {
        let digest = H::digest(message);
        self.sign_digest_with_rng(&digest, rng)
    }

    /// Sign and serialize a digest using deterministic nonce derivation.
    #[must_use]
    pub fn sign_digest_bytes<H: Digest>(&self, digest: &[u8]) -> Option<Vec<u8>> {
        let sig = self.sign_digest::<H>(digest)?;
        Some(sig.to_key_blob())
    }

    /// Sign and serialize a digest using randomized nonces.
    #[must_use]
    pub fn sign_digest_bytes_with_rng<R: Csprng>(
        &self,
        digest: &[u8],
        rng: &mut R,
    ) -> Option<Vec<u8>> {
        let sig = self.sign_digest_with_rng(digest, rng)?;
        Some(sig.to_key_blob())
    }

    /// Hash one message with `H`, then sign and serialize deterministically.
    #[must_use]
    pub fn sign_message_bytes<H: Digest>(&self, message: &[u8]) -> Option<Vec<u8>> {
        let sig = self.sign_message::<H>(message)?;
        Some(sig.to_key_blob())
    }

    /// Hash one message with `H`, then sign and serialize with randomized nonces.
    #[must_use]
    pub fn sign_message_bytes_with_rng<H: Digest, R: Csprng>(
        &self,
        message: &[u8],
        rng: &mut R,
    ) -> Option<Vec<u8>> {
        let sig = self.sign_message_with_rng::<H, R>(message, rng)?;
        Some(sig.to_key_blob())
    }

    /// Encode the private key in the crate-defined binary format.
    ///
    /// Layout: one field-type byte (`0x00` = prime, `0x01` = binary) followed
    /// by `[p, a, b, n, h, Gx, Gy, d]`.
    #[must_use]
    pub fn to_key_blob(&self) -> Vec<u8> {
        let h = BigUint::from_u64(self.curve.h);
        let field_byte = u8::from(self.curve.gf2m_degree().is_some());
        let mut out = vec![field_byte];
        out.extend_from_slice(&encode_biguints(&[
            &self.curve.p,
            &self.curve.a,
            &self.curve.b,
            &self.curve.n,
            &h,
            &self.curve.gx,
            &self.curve.gy,
            &self.d,
        ]));
        out
    }

    /// Decode a private key from the crate-defined binary format.
    #[must_use]
    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
        let (&field_type, rest) = blob.split_first()?;
        let mut fields = decode_biguints(rest)?.into_iter();
        let field_prime = fields.next()?;
        let curve_a = fields.next()?;
        let curve_b = fields.next()?;
        let subgroup_order = fields.next()?;
        let cofactor_big = fields.next()?;
        let base_x = fields.next()?;
        let base_y = fields.next()?;
        let private_scalar = fields.next()?;
        if fields.next().is_some() {
            return None;
        }
        let cofactor = biguint_to_u64(&cofactor_big)?;
        let curve = if field_type == 0x01 {
            let field_degree = field_prime.bits().checked_sub(1)?;
            CurveParams::new_binary(
                field_prime,
                field_degree,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                (base_x, base_y),
            )?
        } else {
            CurveParams::new(
                field_prime,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                base_x,
                base_y,
            )?
        };
        if private_scalar.is_zero() || private_scalar.cmp(&curve.n).is_ge() {
            return None;
        }
        let q = curve.scalar_mul(&curve.base_point(), &private_scalar);
        Some(Self {
            curve,
            d: private_scalar,
            q,
        })
    }

    #[must_use]
    pub fn to_pem(&self) -> String {
        pem_wrap(ECDSA_PRIVATE_LABEL, &self.to_key_blob())
    }

    /// Returns `None` if the PEM label does not match or the payload is malformed.
    #[must_use]
    pub fn from_pem(pem: &str) -> Option<Self> {
        let blob = pem_unwrap(ECDSA_PRIVATE_LABEL, pem)?;
        Self::from_key_blob(&blob)
    }

    /// # Panics
    ///
    /// Panics only if a binary-field curve reports a degree that does not fit
    /// in `u64`, which would indicate malformed curve parameters.
    #[must_use]
    pub fn to_xml(&self) -> String {
        let h = BigUint::from_u64(self.curve.h);
        let degree = BigUint::from_u64(
            u64::try_from(self.curve.gf2m_degree().unwrap_or(0)).expect("degree fits in u64"),
        );
        xml_wrap(
            "EcdsaPrivateKey",
            &[
                ("p", &self.curve.p),
                ("a", &self.curve.a),
                ("b", &self.curve.b),
                ("n", &self.curve.n),
                ("h", &h),
                ("degree", &degree),
                ("gx", &self.curve.gx),
                ("gy", &self.curve.gy),
                ("d", &self.d),
            ],
        )
    }

    /// Returns `None` if the XML root element, tag names, or integer encoding is invalid.
    #[must_use]
    pub fn from_xml(xml: &str) -> Option<Self> {
        let mut fields = xml_unwrap(
            "EcdsaPrivateKey",
            &["p", "a", "b", "n", "h", "degree", "gx", "gy", "d"],
            xml,
        )?
        .into_iter();
        let field_prime = fields.next()?;
        let curve_a = fields.next()?;
        let curve_b = fields.next()?;
        let subgroup_order = fields.next()?;
        let cofactor_big = fields.next()?;
        let degree_big = fields.next()?;
        let base_x = fields.next()?;
        let base_y = fields.next()?;
        let private_scalar = fields.next()?;
        if fields.next().is_some() {
            return None;
        }
        let cofactor = biguint_to_u64(&cofactor_big)?;
        let field_degree = usize::try_from(biguint_to_u64(&degree_big)?).ok()?;
        let curve = if field_degree > 0 {
            CurveParams::new_binary(
                field_prime,
                field_degree,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                (base_x, base_y),
            )?
        } else {
            CurveParams::new(
                field_prime,
                curve_a,
                curve_b,
                subgroup_order,
                cofactor,
                base_x,
                base_y,
            )?
        };
        if private_scalar.is_zero() || private_scalar.cmp(&curve.n).is_ge() {
            return None;
        }
        let q = curve.scalar_mul(&curve.base_point(), &private_scalar);
        Some(Self {
            curve,
            d: private_scalar,
            q,
        })
    }
}

impl fmt::Debug for EcdsaPrivateKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("EcdsaPrivateKey(<redacted>)")
    }
}

// ─── EcdsaSignature ───────────────────────────────────────────────────────────

impl EcdsaSignature {
    #[must_use]
    pub fn r(&self) -> &BigUint {
        &self.r
    }

    #[must_use]
    pub fn s(&self) -> &BigUint {
        &self.s
    }

    /// Encode the signature as a DER `SEQUENCE` of `(r, s)`.
    #[must_use]
    pub fn to_key_blob(&self) -> Vec<u8> {
        encode_biguints(&[&self.r, &self.s])
    }

    /// Decode a crate-defined binary ECDSA signature.
    ///
    /// Zero values are rejected immediately.  Range checks against the curve
    /// order happen during verification because the signature encoding does
    /// not carry the curve parameters.
    #[must_use]
    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
        let mut fields = decode_biguints(blob)?.into_iter();
        let r = fields.next()?;
        let s = fields.next()?;
        if fields.next().is_some() || r.is_zero() || s.is_zero() {
            return None;
        }
        Some(Self { r, s })
    }
}

// ─── Ecdsa namespace ──────────────────────────────────────────────────────────

impl Ecdsa {
    /// Returns `(public_key, private_key)`.
    #[must_use]
    pub fn generate<R: Csprng>(
        curve: CurveParams,
        rng: &mut R,
    ) -> (EcdsaPublicKey, EcdsaPrivateKey) {
        let (d, q) = curve.generate_keypair(rng);
        let public = EcdsaPublicKey {
            curve: curve.clone(),
            q: q.clone(),
        };
        let private = EcdsaPrivateKey { curve, d, q };
        (public, private)
    }

    /// Derive a key pair from an explicit curve and secret scalar.
    ///
    /// Returns `None` if `secret` is zero or ≥ `n`.
    #[must_use]
    pub fn from_secret_scalar(
        curve: CurveParams,
        secret: &BigUint,
    ) -> Option<(EcdsaPublicKey, EcdsaPrivateKey)> {
        if secret.is_zero() || secret >= &curve.n {
            return None;
        }
        let q = curve.scalar_mul(&curve.base_point(), secret);
        Some((
            EcdsaPublicKey {
                curve: curve.clone(),
                q: q.clone(),
            },
            EcdsaPrivateKey {
                curve,
                d: secret.clone(),
                q,
            },
        ))
    }
}

// ─── Helpers ─────────────────────────────────────────────────────────────────

/// Convert a small `BigUint` (≤ 8 bytes) to a `u64`.
///
/// Returns `None` if the value has more than 8 bytes, which would indicate
/// a corrupt or unusually large cofactor in a serialized key.
fn biguint_to_u64(value: &BigUint) -> Option<u64> {
    let bytes = value.to_be_bytes();
    if bytes.len() > 8 {
        return None;
    }
    let mut arr = [0u8; 8];
    arr[8 - bytes.len()..].copy_from_slice(&bytes);
    Some(u64::from_be_bytes(arr))
}

/// FIPS 186-5 digest representative reduction.
///
/// Keeps the leftmost `N = bits(n)` bits of the hash.  The shift amount is
/// derived from `digest.len() * 8`, not from the trimmed width of the integer,
/// to avoid a length-dependent branch on the hash output.
fn digest_to_scalar(digest: &[u8], modulus: &BigUint) -> BigUint {
    let mut value = BigUint::from_be_bytes(digest);
    let hash_bits = digest.len() * 8;
    let target_bits = modulus.bits();
    if hash_bits > target_bits {
        for _ in 0..(hash_bits - target_bits) {
            value.shr1();
        }
    }
    value
}

fn canonicalize_low_s(order: &BigUint, s: &mut BigUint) {
    let mut half = order.clone();
    half.shr1();
    if (*s).cmp(&half).is_gt() {
        *s = order.sub_ref(s);
    }
}

fn int_to_octets(value: &BigUint, len: usize) -> Vec<u8> {
    let bytes = value.to_be_bytes();
    if bytes.len() >= len {
        return bytes[bytes.len() - len..].to_vec();
    }
    let mut out = vec![0u8; len];
    out[len - bytes.len()..].copy_from_slice(&bytes);
    out
}

fn bits_to_int(input: &[u8], target_bits: usize) -> BigUint {
    let mut value = BigUint::from_be_bytes(input);
    let input_bits = input.len() * 8;
    if input_bits > target_bits {
        for _ in 0..(input_bits - target_bits) {
            value.shr1();
        }
    }
    value
}

fn bits_to_octets(input: &[u8], q: &BigUint, q_bits: usize, ro_len: usize) -> Vec<u8> {
    let z1 = bits_to_int(input, q_bits);
    let z2 = z1.modulo(q);
    int_to_octets(&z2, ro_len)
}

fn rfc6979_nonce<H: Digest>(q: &BigUint, x: &BigUint, digest: &[u8]) -> Option<BigUint> {
    if q <= &BigUint::one() {
        return None;
    }

    let q_bits = q.bits();
    let ro_len = q_bits.div_ceil(8);
    let bx = int_to_octets(x, ro_len);
    let bh = bits_to_octets(digest, q, q_bits, ro_len);

    let mut v = vec![0x01; H::OUTPUT_LEN];
    let mut k = vec![0x00; H::OUTPUT_LEN];

    let mut data = Vec::with_capacity(v.len() + 1 + bx.len() + bh.len());
    data.extend_from_slice(&v);
    data.push(0x00);
    data.extend_from_slice(&bx);
    data.extend_from_slice(&bh);
    k = Hmac::<H>::compute(&k, &data);
    v = Hmac::<H>::compute(&k, &v);

    data.clear();
    data.extend_from_slice(&v);
    data.push(0x01);
    data.extend_from_slice(&bx);
    data.extend_from_slice(&bh);
    k = Hmac::<H>::compute(&k, &data);
    v = Hmac::<H>::compute(&k, &v);

    loop {
        let mut t = Vec::with_capacity(ro_len);
        while t.len() < ro_len {
            v = Hmac::<H>::compute(&k, &v);
            let take = (ro_len - t.len()).min(v.len());
            t.extend_from_slice(&v[..take]);
        }

        let candidate = bits_to_int(&t, q_bits);
        if !candidate.is_zero() && &candidate < q {
            return Some(candidate);
        }

        data.clear();
        data.extend_from_slice(&v);
        data.push(0x00);
        k = Hmac::<H>::compute(&k, &data);
        v = Hmac::<H>::compute(&k, &v);
    }
}

// ─── Tests ────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::{Ecdsa, EcdsaPrivateKey, EcdsaPublicKey, EcdsaSignature};
    use crate::public_key::bigint::BigUint;
    use crate::public_key::ec::{b163, p256, p384, p521, secp256k1};
    use crate::{CtrDrbgAes256, Sha256, Sha384, Sha512};

    fn rng() -> CtrDrbgAes256 {
        CtrDrbgAes256::new(&[0xab; 48])
    }

    fn decode_hex(hex: &str) -> Vec<u8> {
        let cleaned: String = hex.chars().filter(|c| !c.is_whitespace()).collect();
        assert_eq!(
            cleaned.len() % 2,
            0,
            "hex input must have an even number of nybbles"
        );
        (0..cleaned.len())
            .step_by(2)
            .map(|i| u8::from_str_radix(&cleaned[i..i + 2], 16).expect("valid hex byte"))
            .collect()
    }

    fn from_hex(hex: &str) -> BigUint {
        BigUint::from_be_bytes(&decode_hex(hex))
    }

    // ── Sign-and-verify round trips ──────────────────────────────────────────

    #[test]
    fn sign_verify_roundtrip_p256() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"hello world";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        assert!(public.verify_message::<Sha256>(msg, &sig));
    }

    #[test]
    fn sign_verify_roundtrip_p384() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p384(), &mut rng);
        let msg = b"p384 test message";
        let sig = private.sign_message::<Sha384>(msg).expect("sign");
        assert!(public.verify_message::<Sha384>(msg, &sig));
    }

    #[test]
    fn sign_verify_roundtrip_secp256k1() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(secp256k1(), &mut rng);
        let msg = b"secp256k1 test";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        assert!(public.verify_message::<Sha256>(msg, &sig));
    }

    #[test]
    fn sign_verify_roundtrip_p521() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p521(), &mut rng);
        let msg = b"p521 test message";
        let sig = private.sign_message::<Sha512>(msg).expect("sign");
        assert!(public.verify_message::<Sha512>(msg, &sig));
    }

    #[test]
    fn sign_verify_roundtrip_b163() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(b163(), &mut rng);
        let msg = b"binary curve ecdsa";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        assert!(public.verify_message::<Sha256>(msg, &sig));
    }

    // ── Deterministic signing via explicit nonce ──────────────────────────────

    #[test]
    fn sign_digest_with_nonce_is_deterministic() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p256(), &mut rng);
        let digest = [0x42u8; 32];
        let k = BigUint::from_u64(12_345_678_901_234_567_u64);
        let sig1 = private
            .sign_digest_with_nonce(&digest, &k)
            .expect("first sign");
        let sig2 = private
            .sign_digest_with_nonce(&digest, &k)
            .expect("second sign");
        assert_eq!(sig1, sig2);
    }

    #[test]
    fn sign_digest_with_nonce_repeatable_for_fixed_nonce() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p256(), &mut rng);
        let digest = [0x42u8; 32];
        let nonce = BigUint::from_u64(12_345_678_901_234_567_u64);
        let lhs = private
            .sign_digest_with_nonce(&digest, &nonce)
            .expect("first");
        let rhs = private
            .sign_digest_with_nonce(&digest, &nonce)
            .expect("second");
        assert_eq!(lhs, rhs);
    }

    #[test]
    fn sign_digest_with_nonce_zero_rejected() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p256(), &mut rng);
        let digest = [0x00u8; 32];
        assert!(private
            .sign_digest_with_nonce(&digest, &BigUint::zero())
            .is_none());
    }

    #[test]
    fn sign_digest_with_nonce_equal_to_n_rejected() {
        let curve = p256();
        let n = curve.n.clone();
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(curve, &mut rng);
        let digest = [0x01u8; 32];
        assert!(private.sign_digest_with_nonce(&digest, &n).is_none());
    }

    #[test]
    fn sign_digest_with_nonce_returns_low_s() {
        let curve = p256();
        let secret = BigUint::from_u64(0x1234_5678_9abc_def0);
        let (_, private) = Ecdsa::from_secret_scalar(curve.clone(), &secret).expect("from secret");
        let digest = Sha256::digest(b"low-s canonicalization");
        let nonce = BigUint::from_u64(0xdead_beef_cafe_babe);

        let sig = private
            .sign_digest_with_nonce(&digest, &nonce)
            .expect("sign with nonce");
        let mut half = curve.n.clone();
        half.shr1();
        assert!(
            sig.s.cmp(&half).is_le(),
            "signature must be canonical low-s"
        );
    }

    // ── Rejection tests ───────────────────────────────────────────────────────

    #[test]
    fn wrong_message_rejected() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"correct message";
        let wrong = b"wrong message";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        assert!(!public.verify_message::<Sha256>(wrong, &sig));
    }

    #[test]
    fn tampered_r_rejected() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"message";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        let bad = EcdsaSignature {
            r: sig.r.add_ref(&BigUint::one()),
            s: sig.s.clone(),
        };
        assert!(!public.verify_message::<Sha256>(msg, &bad));
    }

    #[test]
    fn tampered_s_rejected() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"message";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        let bad = EcdsaSignature {
            r: sig.r.clone(),
            s: sig.s.add_ref(&BigUint::one()),
        };
        assert!(!public.verify_message::<Sha256>(msg, &bad));
    }

    #[test]
    fn wrong_key_rejected() {
        let mut rng = rng();
        let (_, private1) = Ecdsa::generate(p256(), &mut rng);
        let (public2, _) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"message";
        let sig = private1.sign_message::<Sha256>(msg).expect("sign");
        assert!(!public2.verify_message::<Sha256>(msg, &sig));
    }

    // ── to_public_key ─────────────────────────────────────────────────────────

    #[test]
    fn to_public_key_matches_generated() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let derived = private.to_public_key();
        // Signing with private and verifying with the derived public key must work.
        let msg = b"derived key test";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        assert!(derived.verify_message::<Sha256>(msg, &sig));
        // The derived public point must match the original.
        assert_eq!(derived.q, public.q);
    }

    // ── from_secret_scalar ────────────────────────────────────────────────────

    #[test]
    fn from_secret_scalar_rejects_zero() {
        assert!(Ecdsa::from_secret_scalar(p256(), &BigUint::zero()).is_none());
    }

    #[test]
    fn from_secret_scalar_rejects_out_of_range() {
        let curve = p256();
        let too_large = curve.n.clone();
        assert!(Ecdsa::from_secret_scalar(curve, &too_large).is_none());
    }

    // ── Serialization: binary ─────────────────────────────────────────────────

    #[test]
    fn public_key_binary_roundtrip() {
        let mut rng = rng();
        let (public, _) = Ecdsa::generate(p256(), &mut rng);
        let blob = public.to_key_blob();
        let recovered = EcdsaPublicKey::from_key_blob(&blob).expect("from_binary");
        assert_eq!(recovered.q, public.q);
        assert_eq!(recovered.curve.n, public.curve.n);
    }

    #[test]
    fn public_key_bytes_roundtrip() {
        let mut rng = rng();
        let (public, _) = Ecdsa::generate(p256(), &mut rng);
        let bytes = public.to_wire_bytes();
        let recovered = EcdsaPublicKey::from_wire_bytes(p256(), &bytes).expect("from_bytes");
        assert_eq!(recovered.q, public.q);
        assert_eq!(recovered.curve.n, public.curve.n);
    }

    #[test]
    fn private_key_binary_roundtrip() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p256(), &mut rng);
        let blob = private.to_key_blob();
        let recovered = EcdsaPrivateKey::from_key_blob(&blob).expect("from_binary");
        assert_eq!(recovered.d, private.d);
        assert_eq!(recovered.curve.n, private.curve.n);
    }

    #[test]
    fn signature_binary_roundtrip() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"roundtrip test";
        let sig = private.sign_message::<Sha256>(msg).expect("sign");
        let blob = sig.to_key_blob();
        let recovered = EcdsaSignature::from_key_blob(&blob).expect("from_binary");
        assert_eq!(recovered, sig);
    }

    // ── Serialization: PEM ────────────────────────────────────────────────────

    #[test]
    fn public_key_pem_roundtrip() {
        let mut rng = rng();
        let (public, _) = Ecdsa::generate(p384(), &mut rng);
        let pem = public.to_pem();
        assert!(pem.contains("CRYPTOGRAPHY ECDSA PUBLIC KEY"));
        let recovered = EcdsaPublicKey::from_pem(&pem).expect("from_pem");
        assert_eq!(recovered.q, public.q);
    }

    #[test]
    fn private_key_pem_roundtrip() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p384(), &mut rng);
        let pem = private.to_pem();
        assert!(pem.contains("CRYPTOGRAPHY ECDSA PRIVATE KEY"));
        let recovered = EcdsaPrivateKey::from_pem(&pem).expect("from_pem");
        assert_eq!(recovered.d, private.d);
    }

    // ── Serialization: XML ────────────────────────────────────────────────────

    #[test]
    fn public_key_xml_roundtrip() {
        let mut rng = rng();
        let (public, _) = Ecdsa::generate(secp256k1(), &mut rng);
        let xml = public.to_xml();
        assert!(xml.contains("EcdsaPublicKey"));
        let recovered = EcdsaPublicKey::from_xml(&xml).expect("from_xml");
        assert_eq!(recovered.q, public.q);
    }

    #[test]
    fn private_key_xml_roundtrip() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(secp256k1(), &mut rng);
        let xml = private.to_xml();
        assert!(xml.contains("EcdsaPrivateKey"));
        let recovered = EcdsaPrivateKey::from_xml(&xml).expect("from_xml");
        assert_eq!(recovered.d, private.d);
    }

    // ── Byte-level sign_bytes / verify_bytes ──────────────────────────────────

    #[test]
    fn sign_bytes_verify_bytes_roundtrip() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let digest = Sha256::digest(b"test message bytes");
        let sig_bytes = private
            .sign_digest_bytes::<Sha256>(&digest)
            .expect("sign_digest_bytes");
        assert!(public.verify_bytes(&digest, &sig_bytes));
    }

    #[test]
    fn sign_message_bytes_verify_message_bytes_roundtrip() {
        let mut rng = rng();
        let (public, private) = Ecdsa::generate(p256(), &mut rng);
        let msg = b"end-to-end bytes test";
        let sig_bytes = private
            .sign_message_bytes::<Sha256>(msg)
            .expect("sign_message_bytes");
        assert!(public.verify_message_bytes::<Sha256>(msg, &sig_bytes));
    }

    // ── Debug impl ────────────────────────────────────────────────────────────

    #[test]
    fn private_key_debug_redacted() {
        let mut rng = rng();
        let (_, private) = Ecdsa::generate(p256(), &mut rng);
        let s = format!("{private:?}");
        assert_eq!(s, "EcdsaPrivateKey(<redacted>)");
        // The scalar itself must not appear.
        assert!(!s.contains(&format!("{:?}", private.d)));
    }

    #[test]
    fn rfc6979_ecdsa_p256_sha256_sample_vector_with_low_s_canonicalization() {
        // RFC 6979, Appendix A.2.5 (ECDSA over NIST P-256), SHA-256, "sample".
        let x = from_hex("C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721");
        let expected_ux =
            from_hex("60FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB6");
        let expected_uy =
            from_hex("7903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299");
        let expected_k =
            from_hex("A6E3C57DD01ABE90086538398355DD4C3B17AA873382B0F24D6129493D8AAD60");
        let expected_r =
            from_hex("EFD48B2AACB6A8FD1140DD9CD45E81D69D2C877B56AAF991C34D0EA84EAF3716");
        let expected_s_rfc =
            from_hex("F7CB1C942D657C41D436C7A1B6E29F65F3E900DBB9AFF4064DC4AB2F843ACDA8");

        let (public, private) =
            Ecdsa::from_secret_scalar(p256(), &x).expect("RFC secret scalar must be valid");
        assert_eq!(public.q.x, expected_ux);
        assert_eq!(public.q.y, expected_uy);

        let message = b"sample";
        let digest = Sha256::digest(message);
        let derived_k = super::rfc6979_nonce::<Sha256>(&private.curve.n, &private.d, &digest)
            .expect("RFC nonce must derive");
        assert_eq!(derived_k, expected_k, "RFC 6979 nonce mismatch");

        let signature = private.sign_message::<Sha256>(message).expect("sign");
        assert_eq!(signature.r, expected_r);

        // This implementation enforces low-s canonicalization.
        let expected_s_low = private.curve.n.sub_ref(&expected_s_rfc);
        assert_eq!(signature.s, expected_s_low);
        assert!(public.verify_message::<Sha256>(message, &signature));
    }
}