ic_ec/

p256.rs

//! NIST P-256 (secp256r1, prime256v1).
//!
//! The most widely deployed approved curve. The field, group law, and schemes
//! come from `crate::nist`; this module supplies the constants and the
//! public API.

use crate::mont_field;
use crate::nist::arith::{sqrt_p3mod4, Field};
use crate::nist::point::Curve;
use crate::nist::{ecdh, ecdsa};
use ic_core::traits::{Algorithm, KeyAgreement, SelfTest, SignatureScheme};
use ic_core::{ensure, Result};

// On 64-bit targets the field uses arithmetic specialised to p's shape; see
// `nist::p256_field`. Elsewhere, the generic Montgomery word loop.
#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
mont_field!(
    Fp,
    4,
    32,
    crate::nist::p256_field::P,
    "The P-256 coordinate field, GF(p) with p = 2^256 - 2^224 + 2^192 + 2^96 - 1.",
    mul = crate::nist::p256_field::active::mul,
    square = crate::nist::p256_field::active::square,
    invert = invert_field,
    add = crate::nist::p256_field::active::add,
    sub = crate::nist::p256_field::active::sub
);

#[cfg(not(all(target_pointer_width = "64", not(ic_limb32))))]
mont_field!(
    Fp,
    4,
    32,
    crate::nist::p256_field::P,
    "The P-256 coordinate field, GF(p) with p = 2^256 - 2^224 + 2^192 + 2^96 - 1."
);

/// The group order `n`, little-endian.
const N: [u64; 4] = [
    0xf3b9_cac2_fc63_2551,
    0xbce6_faad_a717_9e84,
    0xffff_ffff_ffff_ffff,
    0xffff_ffff_0000_0000,
];

// On 64-bit targets the scalar ring inverts by Bernstein-Yang divsteps rather
// than by Fermat; see `nist::safegcd`. Everything else is the generic ring.
#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
mont_field!(
    Fn,
    4,
    32,
    N,
    "The P-256 scalar ring, Z/nZ where n is the order of the base point.",
    mul = Self::mont_mul_raw,
    square = Self::mont_square_raw,
    invert = invert_scalar,
    add = Self::add_raw,
    sub = Self::sub_raw
);

#[cfg(not(all(target_pointer_width = "64", not(ic_limb32))))]
mont_field!(
    Fn,
    4,
    32,
    N,
    "The P-256 scalar ring, Z/nZ where n is the order of the base point."
);

/// `a^-1` in the coordinate field, as [`invert_scalar`] does it: 1.0
/// microseconds against 1.6 for the addition chain in `p256_field`, which
/// stays as the tests' reference.
#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
fn invert_field(a: [u64; 4]) -> [u64; 4] {
    const R3: [u64; 4] = Fp::mont_mul_const(Fp::R2, Fp::R2);
    crate::nist::p256_field::active::mul(crate::nist::safegcd::invert::<FpModulus>(&a), R3)
}

/// The prime, for the divsteps.
#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
pub(crate) struct FpModulus;

#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
impl crate::nist::safegcd::Modulus<5> for FpModulus {
    const INFO: crate::nist::safegcd::ModInfo<5> =
        crate::nist::safegcd::ModInfo::new(crate::nist::p256_field::P);
}

/// The order, for the divsteps.
#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
pub(crate) struct FnModulus;

#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
impl crate::nist::safegcd::Modulus<5> for FnModulus {
    const INFO: crate::nist::safegcd::ModInfo<5> = crate::nist::safegcd::ModInfo::new(N);
}

/// `a^-1` in the scalar ring, Montgomery form in and out, by divsteps.
///
/// The divsteps invert the integer they are given, so a Montgomery `a * R`
/// comes back as `a^-1 * R^-1`; one Montgomery multiplication by `R^3`
/// makes that `a^-1 * R`.
#[cfg(all(target_pointer_width = "64", not(ic_limb32)))]
fn invert_scalar(a: [u64; 4]) -> [u64; 4] {
    const R3: [u64; 4] = Fn::mont_mul_const(Fn::R2, Fn::R2);
    Fn::mont_mul_raw(crate::nist::safegcd::invert::<FnModulus>(&a), R3)
}

/// The P-256 curve.
#[derive(Debug, Clone, Copy)]
pub struct P256;

// Its own generator table, with its own storage; see the macro, which
// emits the table under `std` and the windowed multiplication without it.
crate::nist::gentable::generator_table_for!(P256, 32);

/// `scalar * G` by `nist::p256_x86::table_mul` on the generator table,
/// whatever else the CPU has: for the tests, so that a CPU with IFMA runs
/// the MULX/ADX path too.
#[cfg(all(test, feature = "std", target_arch = "x86_64"))]
pub(crate) fn table_mul_adx_for_tests(scalar: &Fn) -> Option<Point> {
    let (windows, built) = generator_table();
    crate::nist::gentable::prepare(windows, built);
    crate::nist::p256_x86::table_mul(windows, scalar)
}

impl Curve for P256 {
    type Field = Fp;
    type Scalar = Fn;

    const NAME: &'static str = "P-256";
    const FIELD_BYTES: usize = 32;
    const SCALAR_BYTES: usize = 32;
    const ORDER_BITS: usize = 256;

    /// `b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b`
    const B: Fp = Fp::to_mont_const([
        0x3bce_3c3e_27d2_604b,
        0x651d_06b0_cc53_b0f6,
        0xb3eb_bd55_7698_86bc,
        0x5ac6_35d8_aa3a_93e7,
    ]);

    const GX: Fp = Fp::to_mont_const([
        0xf4a1_3945_d898_c296,
        0x7703_7d81_2deb_33a0,
        0xf8bc_e6e5_63a4_40f2,
        0x6b17_d1f2_e12c_4247,
    ]);

    const GY: Fp = Fp::to_mont_const([
        0xcbb6_4068_37bf_51f5,
        0x2bce_3357_6b31_5ece,
        0x8ee7_eb4a_7c0f_9e16,
        0x4fe3_42e2_fe1a_7f9b,
    ]);

    /// `p = 3 mod 4`, so a square root is `x^((p+1)/4)`.
    fn sqrt(x: &Fp) -> Fp {
        // p = 3 mod 4, so the root is x^((p+1)/4). The shared helper computes
        // that exponent rather than this file unrolling it by limb: an unrolled
        // shift is easy to get subtly wrong and would only misbehave on inputs
        // rare enough that a round-trip test would not find them.
        sqrt_p3mod4(x, Fp::MODULUS, |v, e| v.pow(e))
    }

    fn field_from_slice(bytes: &[u8]) -> Option<Fp> {
        let mut b = [0u8; 32];
        if bytes.len() != 32 {
            return None;
        }
        b.copy_from_slice(bytes);
        Fp::from_bytes(&b)
    }

    fn scalar_from_slice(bytes: &[u8]) -> Option<Fn> {
        let mut b = [0u8; 32];
        if bytes.len() != 32 {
            return None;
        }
        b.copy_from_slice(bytes);
        Fn::from_bytes(&b)
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn double_fast(x: &Fp, y: &Fp, z: &Fp) -> Option<[Fp; 3]> {
        crate::nist::p256_x86::point_double(&x.0, &y.0, &z.0).map(|[x, y, z]| [Fp(x), Fp(y), Fp(z)])
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn scan_affine(entries: &[AffinePoint], masks: &[u64]) -> Option<AffinePoint> {
        Some(crate::nist::p256_x86::scan_affine(entries, masks))
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn scan_point(entries: &[Point], masks: &[u64]) -> Option<[Fp; 3]> {
        let [x, y, z] = crate::nist::p256_x86::scan_point(entries, masks);
        Some([Fp(x), Fp(y), Fp(z)])
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn add_fast(p: [&Fp; 3], q: [&Fp; 3]) -> Option<([Fp; 3], Fp, Fp)> {
        crate::nist::p256_x86::point_add([&p[0].0, &p[1].0, &p[2].0], [&q[0].0, &q[1].0, &q[2].0])
            .map(|([x, y, z], h, r)| ([Fp(x), Fp(y), Fp(z)], Fp(h), Fp(r)))
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn add_affine_fast(p: [&Fp; 3], q: [&Fp; 2]) -> Option<([Fp; 3], Fp, Fp)> {
        crate::nist::p256_x86::point_add_affine([&p[0].0, &p[1].0, &p[2].0], [&q[0].0, &q[1].0])
            .map(|([x, y, z], h, r)| ([Fp(x), Fp(y), Fp(z)], Fp(h), Fp(r)))
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn mul_scalar_fast(p: &Point, scalar: &Fn) -> Option<Point> {
        match crate::nist::ifma::Ifma::get() {
            Some(t) => Some(crate::nist::ifma::mul_scalar(t, p, scalar)),
            None => crate::nist::p256_x86::mul_scalar(p, scalar),
        }
    }

    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn comb_mul_fast(
        windows: &[crate::nist::gentable::AffineWindow<Self, { crate::nist::gentable::ENTRIES }>;
             crate::nist::gentable::TEETH],
        scalar: &Fn,
    ) -> Option<Point> {
        crate::nist::ifma::Ifma::get().map(|t| crate::nist::ifma::comb_mul(t, windows, scalar))
    }

    #[cfg(all(target_arch = "x86_64", feature = "std"))]
    #[inline(always)]
    fn table_mul_fast<const E: usize>(
        windows: &crate::nist::gentable::Windows<Self, E>,
        scalar: &Fn,
    ) -> Option<Point> {
        match crate::nist::ifma::Ifma::get() {
            Some(t) => Some(crate::nist::ifma::table_mul(t, windows, scalar)),
            None => crate::nist::p256_x86::table_mul(windows, scalar),
        }
    }

    /// Verification's joint chain on the formulas' assembly: public inputs
    /// only, never a secret path (`nist::verify_x86`).
    #[cfg(target_arch = "x86_64")]
    #[inline(always)]
    fn mul_double_vartime_fast(
        g: &[AffinePoint],
        q: &[AffinePoint],
        g_naf: &[i8],
        q_naf: &[i8],
    ) -> Option<Point> {
        crate::nist::verify_x86::p256(g, q, g_naf, q_naf)
    }

    fn scalar_reduce_slice(bytes: &[u8]) -> Fn {
        let mut b = [0u8; 32];
        let n = core::cmp::min(32, bytes.len());
        // Take the leftmost bytes, which is what bits2int does when the input
        // is at least as wide as the group order.
        b[32 - n..].copy_from_slice(&bytes[..n]);
        Fn::from_bytes_reduced(&b)
    }
}

impl ecdsa::EcdsaCurve for P256 {
    type Digest = ic_hash::Sha256;
    type Hmac = ic_mac::HmacSha256;
}

/// ECDSA over P-256 with SHA-256.
pub struct EcdsaP256Sha256;

impl Algorithm for EcdsaP256Sha256 {
    const ID: &'static str = "ecdsa-p256-sha256";
    const NAME: &'static str = "ECDSA P-256 with SHA-256";
}

impl SignatureScheme for EcdsaP256Sha256 {
    const PRIVATE_KEY_LEN: usize = 32;
    /// SEC1 uncompressed: `0x04 || X || Y`.
    const PUBLIC_KEY_LEN: usize = 65;
    /// Fixed-width `r || s`.
    const SIGNATURE_LEN: usize = 64;

    fn public_key(private_key: &[u8], out: &mut [u8]) -> Result<()> {
        ecdsa::public_key::<P256>(private_key, out)
    }

    fn sign(private_key: &[u8], message: &[u8], signature: &mut [u8]) -> Result<()> {
        ecdsa::sign::<P256>(private_key, message, signature)
    }

    fn verify(public_key: &[u8], message: &[u8], signature: &[u8]) -> Result<()> {
        ecdsa::verify::<P256>(public_key, message, signature)
    }
}

impl EcdsaP256Sha256 {
    /// Verify a signature over a digest the caller computed, for signatures
    /// made with a hash other than SHA-256.
    ///
    /// `digest` must be one of [`crate::PREHASH_LENS`] and at least 32
    /// bytes, so that the hash is at least as strong as the curve; narrower is
    /// refused with `InvalidLength`. Which hash produced it is the caller's to
    /// establish: nothing here can tell.
    pub fn verify_prehash(public_key: &[u8], digest: &[u8], signature: &[u8]) -> Result<()> {
        ecdsa::verify_prehash::<P256>(public_key, digest, signature)
    }

    /// Compute the public key in SEC1 compressed form (33 bytes).
    pub fn public_key_compressed(private_key: &[u8], out: &mut [u8]) -> Result<()> {
        ecdsa::public_key_compressed::<P256>(private_key, out)
    }

    /// Rewrite a signature to its low-`s` form, if it is not already.
    ///
    /// ECDSA is malleable: `(r, s)` and `(r, n - s)` are both valid for the
    /// same message, so a signature is not a unique identifier unless one form
    /// is chosen. FIPS 186-5 and RFC 6979 accept both, and this library signs
    /// and verifies per the standard, so normalization is offered rather than
    /// imposed -- apply it when a signature doubles as a database key or a
    /// transaction id.
    pub fn normalize_s(signature: &mut [u8]) -> Result<()> {
        ecdsa::normalize_s::<P256>(signature)
    }

    /// Whether a signature is already in low-`s` form.
    pub fn has_low_s(signature: &[u8]) -> Result<bool> {
        ecdsa::has_low_s::<P256>(signature)
    }
}

impl SelfTest for EcdsaP256Sha256 {
    fn self_test() -> Result<()> {
        // RFC 6979 A.2.5: P-256, SHA-256, message "sample".
        let mut key = [0u8; 32];
        ic_core::codec::hex_decode(
            b"c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721",
            &mut key,
        )?;
        let mut want = [0u8; 64];
        ic_core::codec::hex_decode(
            b"efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716f7cb1c942d657c41d436c7a1b6e29f65f3e900dbb9aff4064dc4ab2f843acda8",
            &mut want,
        )?;

        let mut sig = [0u8; 64];
        <Self as SignatureScheme>::sign(&key, b"sample", &mut sig)?;
        ensure!(
            ic_core::ct::verify(&want, &sig),
            SelfTestFailed,
            "ecdsa-p256-sha256"
        );

        let mut pk = [0u8; 65];
        <Self as SignatureScheme>::public_key(&key, &mut pk)?;
        <Self as SignatureScheme>::verify(&pk, b"sample", &sig)?;

        // A flipped bit must be rejected.
        sig[0] ^= 1;
        ensure!(
            <Self as SignatureScheme>::verify(&pk, b"sample", &sig).is_err(),
            SelfTestFailed,
            "ecdsa-p256-sha256"
        );
        Ok(())
    }
}

/// ECDH over P-256.
pub struct EcdhP256;

impl Algorithm for EcdhP256 {
    const ID: &'static str = "ecdh-p256";
    const NAME: &'static str = "ECDH P-256";
}

impl KeyAgreement for EcdhP256 {
    const PRIVATE_KEY_LEN: usize = 32;
    /// SEC1 uncompressed: `0x04 || X || Y`.
    const PUBLIC_KEY_LEN: usize = 65;
    const SHARED_SECRET_LEN: usize = 32;

    fn public_key(private_key: &[u8], out: &mut [u8]) -> Result<()> {
        ecdh::public_key::<P256>(private_key, out)
    }

    fn agree(private_key: &[u8], peer_public_key: &[u8], out: &mut [u8]) -> Result<()> {
        ecdh::agree::<P256>(private_key, peer_public_key, out)
    }
}

impl EcdhP256 {
    /// Compute the public key in SEC1 compressed form (33 bytes).
    ///
    /// Interoperates with TLS, COSE, and JOSE, which all prefer compressed
    /// points. [`KeyAgreement::agree`] accepts either form.
    pub fn public_key_compressed(private_key: &[u8], out: &mut [u8]) -> Result<()> {
        ecdh::public_key_compressed::<P256>(private_key, out)
    }
}

impl SelfTest for EcdhP256 {
    fn self_test() -> Result<()> {
        // NIST CAVP ECC CDH, P-256, the first published key-agreement case.
        let mut d = [0u8; 32];
        ic_core::codec::hex_decode(
            b"7d7dc5f71eb29ddaf80d6214632eeae03d9058af1fb6d22ed80badb62bc1a534",
            &mut d,
        )?;
        let mut peer = [0u8; 65];
        peer[0] = 0x04;
        ic_core::codec::hex_decode(
            b"700c48f77f56584c5cc632ca65640db91b6bacce3a4df6b42ce7cc838833d287",
            &mut peer[1..33],
        )?;
        ic_core::codec::hex_decode(
            b"db71e509e3fd9b060ddb20ba5c51dcc5948d46fbf640dfe0441782cab85fa4ac",
            &mut peer[33..],
        )?;
        let mut want = [0u8; 32];
        ic_core::codec::hex_decode(
            b"46fc62106420ff012e54a434fbdd2d25ccc5852060561e68040dd7778997bd7b",
            &mut want,
        )?;

        let mut got = [0u8; 32];
        <Self as KeyAgreement>::agree(&d, &peer, &mut got)?;
        ensure!(
            ic_core::ct::verify(&want, &got),
            SelfTestFailed,
            "ecdh-p256"
        );
        Ok(())
    }
}

/// A P-256 point in Jacobian coordinates.
pub type Point = crate::nist::point::Point<P256>;
/// A P-256 point in affine coordinates.
pub type AffinePoint = crate::nist::point::AffinePoint<P256>;
/// A peer's P-256 public key for [`EcdhP256`], decoded, validated and
/// expanded once: `new` takes its SEC1 encoding and refuses what
/// [`EcdhP256`]'s `agree` would refuse; `agree` takes a private key and
/// writes the 32-byte shared secret, doing only the scalar multiplication
/// in about 40 percent of the time of an unprepared agreement. About 4 KiB, not
/// allocated.
pub type PreparedPublicKey = crate::nist::ecdh::PreparedPublicKey<P256>;

#[cfg(test)]
mod tests {
    use super::*;
    use ic_core::codec::{hex, unhex};

    /// Where P-256's time goes, piece by piece. A measurement, not a check:
    /// run with `cargo test --release -p ic-ec -- --ignored --nocapture
    /// where_the_time_goes`.
    #[test]
    #[ignore = "timing; run manually with --release"]
    fn where_the_time_goes() {
        use crate::nist::arith::Field;
        use std::hint::black_box;
        use std::time::Instant;
        fn ns(label: &str, iters: u32, mut f: impl FnMut()) {
            let mut best = f64::INFINITY;
            for _ in 0..7 {
                let t = Instant::now();
                for _ in 0..iters {
                    f();
                }
                best = best.min(t.elapsed().as_secs_f64() * 1e9 / iters as f64);
            }
            std::println!("{label:32} {best:10.1} ns");
        }
        let a = Fp::to_mont([7, 11, 13, 17]);
        let b = Fp::to_mont([19, 23, 29, 31]);
        ns("fp mul", 2_000_000, || {
            black_box(black_box(a).mul(&black_box(b)));
        });
        ns("fp square", 2_000_000, || {
            black_box(black_box(a).square());
        });
        ns("fp add", 2_000_000, || {
            black_box(black_box(a).add(&black_box(b)));
        });
        ns("fp sub", 2_000_000, || {
            black_box(black_box(a).sub(&black_box(b)));
        });
        ns("fp invert", 2_000, || {
            black_box(black_box(a).invert());
        });
        let g = Point::generator();
        let p = g.double();
        ns("point double", 200_000, || {
            black_box(black_box(p).double());
        });
        ns("point add (complete)", 200_000, || {
            black_box(black_box(p).add(&black_box(g)));
        });
        ns("point add (unequal)", 200_000, || {
            black_box(black_box(p).add_unequal(&black_box(g)));
        });
        let ga = g.to_affine().unwrap();
        ns("point add (affine, unequal)", 200_000, || {
            black_box(black_box(p).add_affine_unequal(&black_box(ga.x), &black_box(ga.y)));
        });
        let k = Fn::to_mont([0x1234_5678, 0x9abc_def0, 0x1357_9bdf, 0x2468_ace0]);
        ns("scalar invert", 2_000, || {
            black_box(black_box(k).invert());
        });
        ns("mul_generator (table)", 2_000, || {
            black_box(Point::mul_generator(&black_box(k)));
        });
        ns("mul_scalar (windowed)", 500, || {
            black_box(black_box(p).mul_scalar(&black_box(k)));
        });
        ns("mul_scalar_vartime", 500, || {
            black_box(black_box(p).mul_scalar_vartime(&black_box(k)));
        });
        ns("to_affine", 2_000, || {
            black_box(black_box(p).to_affine());
        });
        let mut pk = [0u8; 65];
        EcdhP256::public_key(&[0x5a; 32], &mut pk).unwrap();
        let mut shared = [0u8; 32];
        ns("ecdh agree", 500, || {
            EcdhP256::agree(&[0x5a; 32], &pk, &mut shared).unwrap();
        });
        ns("decode point", 2_000, || {
            black_box(AffinePoint::from_sec1(black_box(&pk)));
        });
        ns("operational", 2_000, || {
            black_box(ic_core::module::operational()).unwrap();
        });
        let mut sig = [0u8; 64];
        ns("ecdsa sign", 500, || {
            EcdsaP256Sha256::sign(&[0x5a; 32], b"message", &mut sig).unwrap();
        });
    }

    fn scalar(v: u64) -> Fn {
        Fn::to_mont([v, 0, 0, 0])
    }

    fn fp(v: u64) -> Fp {
        Fp::to_mont([v, 0, 0, 0])
    }

    // -- field ------------------------------------------------------------

    #[test]
    fn montgomery_constants_are_consistent() {
        assert_eq!(Fp::MODULUS[0].wrapping_mul(Fp::NEG_INV), u64::MAX, "p");
        assert_eq!(Fn::MODULUS[0].wrapping_mul(Fn::NEG_INV), u64::MAX, "n");
    }

    #[test]
    fn small_arithmetic_matches_integers() {
        assert_eq!(fp(2).add(&fp(3)), fp(5));
        assert_eq!(fp(5).sub(&fp(3)), fp(2));
        assert_eq!(fp(6).mul(&fp(7)), fp(42));
        assert_eq!(fp(9).square(), fp(81));
        assert_eq!(fp(5).double(), fp(10));
        assert_eq!(fp(5).triple(), fp(15));
        assert_eq!(Fp::ONE.from_mont(), [1, 0, 0, 0]);
    }

    #[test]
    fn inversion_is_correct() {
        for v in [1u64, 2, 3, 19, 65537, u32::MAX as u64] {
            assert_eq!(fp(v).mul(&fp(v).invert()), Fp::ONE, "1/{v} in Fp");
            assert_eq!(scalar(v).mul(&scalar(v).invert()), Fn::ONE, "1/{v} in Fn");
        }
        assert_eq!(Fp::ZERO.invert(), Fp::ZERO);
        assert_eq!(Fn::ZERO.invert(), Fn::ZERO);
    }

    /// Both rings' inversion -- divsteps on 64-bit targets -- against the
    /// generic Fermat exponentiation, value for value in Montgomery form, on
    /// the edges and on a spread of values from repeated squaring.
    #[test]
    fn inversion_matches_fermat() {
        let mut x = fp(0x1234_5678_9abc_def1);
        let mut k = scalar(0x0fed_cba9_8765_4321);
        let mut fps = std::vec![
            Fp::ONE,
            Fp::ONE.neg(),
            Fp::ONE.double(),
            Fp::ONE.neg().double()
        ];
        let mut fns = std::vec![
            Fn::ONE,
            Fn::ONE.neg(),
            Fn::ONE.double(),
            Fn::ONE.neg().double()
        ];
        for _ in 0..300 {
            x = x.square().add(&Fp::ONE);
            k = k.square().add(&Fn::ONE);
            fps.push(x);
            fns.push(k);
        }
        for v in fps {
            assert_eq!(v.invert().0, Fp::invert_raw(v.0), "{v:?}");
        }
        for v in fns {
            assert_eq!(v.invert().0, Fn::invert_raw(v.0), "{v:?}");
        }
    }

    #[test]
    fn arithmetic_laws_hold_on_large_values() {
        let a = P256::field_from_slice(&[0x3a; 32]).unwrap();
        let b = P256::field_from_slice(&[0x91; 32]).unwrap();
        let c = P256::field_from_slice(&[0xc7; 32]).unwrap();
        assert_eq!(a.mul(&b).mul(&c), a.mul(&b.mul(&c)), "associativity");
        assert_eq!(a.mul(&b), b.mul(&a), "commutativity");
        assert_eq!(
            a.mul(&b.add(&c)),
            a.mul(&b).add(&a.mul(&c)),
            "distributivity"
        );
        assert_eq!(a.add(&a.neg()), Fp::ZERO);
    }

    #[test]
    fn byte_encoding_round_trips_and_rejects_non_canonical() {
        let bytes = [0x7fu8; 32];
        let a = P256::field_from_slice(&bytes).unwrap();
        assert_eq!(a.to_bytes(), bytes);

        // p itself must be refused but reduce to zero.
        let mut p_bytes = [0u8; 32];
        for i in 0..4 {
            let hi = 32 - i * 8;
            p_bytes[hi - 8..hi].copy_from_slice(&Fp::MODULUS[i].to_be_bytes());
        }
        assert!(P256::field_from_slice(&p_bytes).is_none());
    }

    // -- group law --------------------------------------------------------

    /// Validates B, GX, GY and the curve equation together: if any of the four
    /// constants were mistranscribed, the base point would not satisfy it.
    #[test]
    fn the_base_point_is_on_the_curve() {
        let g = Point::generator().to_affine().unwrap();
        assert!(bool::from(g.is_on_curve()));
    }

    /// Validates the group order n against the base point.
    #[test]
    fn the_base_point_has_order_n() {
        let n_minus_1 = Fn::ZERO.sub(&Fn::ONE);
        let p = Point::generator().mul_scalar(&n_minus_1);
        assert!(
            bool::from(p.ct_eq(&Point::generator().neg())),
            "[n-1]G == -G"
        );
        assert!(
            bool::from(p.add(&Point::generator()).is_identity()),
            "[n]G is the identity"
        );
    }

    #[test]
    fn identity_and_negation_behave() {
        let g = Point::generator();
        assert!(bool::from(g.add(&Point::identity()).ct_eq(&g)));
        assert!(bool::from(Point::identity().add(&g).ct_eq(&g)));
        assert!(bool::from(Point::identity().double().is_identity()));
        assert!(bool::from(g.add(&g.neg()).is_identity()));
        assert!(Point::identity().to_affine().is_none());
    }

    /// The exceptional case a naive Jacobian addition gets wrong.
    #[test]
    fn addition_handles_equal_inputs_as_a_doubling() {
        let g = Point::generator();
        assert!(bool::from(g.add(&g).ct_eq(&g.double())));
        let p = g.mul_scalar(&scalar(5));
        assert!(bool::from(p.add(&p).ct_eq(&p.double())));
    }

    /// The variable-time path must agree with the constant-time one.
    ///
    /// The RFC 6979 vectors reach it with a couple of scalars, which says
    /// little about a recoding whose digit pattern differs for every scalar.
    /// The values here stress it: zero, one, a scalar that carries at every
    /// position, alternating bits, and the top of the byte range -- which is
    /// above the group order and so exercises the carry the extra limb exists
    /// for.
    #[test]
    fn the_vartime_multiplication_agrees_with_the_ladder() {
        let g = Point::generator();

        let mut checked = 0;
        for raw in [
            [0u8; 32],
            {
                let mut v = [0u8; 32];
                v[31] = 1;
                v
            },
            [0xffu8; 32],
            [0x55u8; 32],
            [0xaau8; 32],
            [0x9du8; 32],
        ] {
            let k = Fn::from_bytes_reduced(&raw);
            assert!(
                bool::from(g.mul_scalar_vartime(&k).ct_eq(&g.mul_scalar(&k))),
                "vartime and ladder differ for {raw:02x?}"
            );
            checked += 1;
        }
        assert_eq!(checked, 6, "the comparison did not run");
    }

    #[test]
    fn scalar_multiplication_matches_repeated_addition() {
        let g = Point::generator();
        let mut acc = Point::identity();
        for k in 1..=10u64 {
            acc = acc.add(&g);
            assert!(bool::from(acc.ct_eq(&g.mul_scalar(&scalar(k)))), "[{k}]G");
        }
    }

    #[test]
    fn scalar_multiplication_is_linear() {
        let g = Point::generator();
        let a = scalar(1_234_567);
        let b = scalar(7_654_321);
        assert!(bool::from(
            g.mul_scalar(&a.add(&b))
                .ct_eq(&g.mul_scalar(&a).add(&g.mul_scalar(&b)))
        ));
        assert!(bool::from(
            g.mul_scalar(&a)
                .mul_scalar(&b)
                .ct_eq(&g.mul_scalar(&a.mul(&b)))
        ));
    }

    /// The published `[2]G`, an independent check on the group law rather than
    /// on self-consistency.
    #[test]
    fn two_g_matches_the_published_value() {
        let two_g = Point::generator().double().to_affine().unwrap();
        assert_eq!(
            hex(two_g.x.to_bytes().as_ref()),
            "7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978"
        );
        assert_eq!(
            hex(two_g.y.to_bytes().as_ref()),
            "07775510db8ed040293d9ac69f7430dbba7dade63ce982299e04b79d227873d1"
        );
    }

    #[test]
    fn sec1_round_trips_in_both_forms() {
        let g = Point::generator();
        for k in [1u64, 2, 3, 4, 5, 6, 7, 8] {
            let p = g.mul_scalar(&scalar(k)).to_affine().unwrap();
            let mut unc = [0u8; 65];
            let mut comp = [0u8; 33];
            assert!(p.write_uncompressed(&mut unc));
            assert!(p.write_compressed(&mut comp));
            assert_eq!(unc[0], 0x04);
            assert!(comp[0] == 0x02 || comp[0] == 0x03);

            let a = AffinePoint::from_sec1(&unc).unwrap();
            let b = AffinePoint::from_sec1(&comp).unwrap();
            assert_eq!(a.x, p.x);
            assert_eq!(a.y, p.y);
            assert_eq!(b.x, p.x);
            assert_eq!(b.y, p.y, "compressed y for [{k}]G");
        }
    }

    #[test]
    fn decoding_rejects_bad_encodings() {
        let g = Point::generator().to_affine().unwrap();
        let mut unc = [0u8; 65];
        assert!(g.write_uncompressed(&mut unc));

        assert!(AffinePoint::from_sec1(&[]).is_none());
        assert!(AffinePoint::from_sec1(&[0u8; 65]).is_none(), "identity");
        assert!(AffinePoint::from_sec1(&unc[..64]).is_none(), "truncated");

        let mut bad = unc;
        bad[0] = 0x05;
        assert!(AffinePoint::from_sec1(&bad).is_none(), "bad tag");

        let mut bad = unc;
        bad[64] ^= 1;
        assert!(AffinePoint::from_sec1(&bad).is_none(), "off curve");
    }

    // -- ECDSA ------------------------------------------------------------

    const KEY: &str = "c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721";

    /// RFC 6979 A.2.5, message "sample". Matching this exercises the field, the
    /// group law, the scalar ring, the nonce derivation, and the signing
    /// equation in one shot.
    #[test]
    fn rfc6979_sample_vector() {
        let key = unhex(KEY).unwrap();
        let mut sig = [0u8; 64];
        EcdsaP256Sha256::sign(&key, b"sample", &mut sig).unwrap();
        assert_eq!(
            hex(&sig[..32]),
            "efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716",
            "r"
        );
        assert_eq!(
            hex(&sig[32..]),
            "f7cb1c942d657c41d436c7a1b6e29f65f3e900dbb9aff4064dc4ab2f843acda8",
            "s"
        );
    }

    /// RFC 6979 A.2.5, message "test".
    #[test]
    fn rfc6979_test_vector() {
        let key = unhex(KEY).unwrap();
        let mut sig = [0u8; 64];
        EcdsaP256Sha256::sign(&key, b"test", &mut sig).unwrap();
        assert_eq!(
            hex(&sig[..32]),
            "f1abb023518351cd71d881567b1ea663ed3efcf6c5132b354f28d3b0b7d38367",
            "r"
        );
        assert_eq!(
            hex(&sig[32..]),
            "019f4113742a2b14bd25926b49c649155f267e60d3814b4c0cc84250e46f0083",
            "s"
        );
    }

    #[test]
    fn rfc6979_public_key() {
        let key = unhex(KEY).unwrap();
        let mut pk = [0u8; 65];
        EcdsaP256Sha256::public_key(&key, &mut pk).unwrap();
        assert_eq!(
            hex(&pk[1..33]),
            "60fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb6",
            "Ux"
        );
        assert_eq!(
            hex(&pk[33..]),
            "7903fe1008b8bc99a41ae9e95628bc64f2f1b20c2d7e9f5177a3c294d4462299",
            "Uy"
        );
    }

    #[test]
    fn signing_is_deterministic_and_message_bound() {
        let key = unhex(KEY).unwrap();
        let mut a = [0u8; 64];
        let mut b = [0u8; 64];
        EcdsaP256Sha256::sign(&key, b"same", &mut a).unwrap();
        EcdsaP256Sha256::sign(&key, b"same", &mut b).unwrap();
        assert_eq!(a, b, "RFC 6979 signing must not depend on an RNG");

        EcdsaP256Sha256::sign(&key, b"other", &mut b).unwrap();
        assert_ne!(&a[..32], &b[..32], "r must differ between messages");
    }

    #[test]
    fn sign_and_verify_round_trip() {
        let key = unhex(KEY).unwrap();
        let mut pk = [0u8; 65];
        EcdsaP256Sha256::public_key(&key, &mut pk).unwrap();
        for message in [&b""[..], b"short", &[0x5au8; 1000][..]] {
            let mut sig = [0u8; 64];
            EcdsaP256Sha256::sign(&key, message, &mut sig).unwrap();
            EcdsaP256Sha256::verify(&pk, message, &sig).unwrap();
        }
    }

    #[test]
    fn verification_rejects_tampering() {
        let key = unhex(KEY).unwrap();
        let mut pk = [0u8; 65];
        EcdsaP256Sha256::public_key(&key, &mut pk).unwrap();
        let mut sig = [0u8; 64];
        EcdsaP256Sha256::sign(&key, b"authentic", &mut sig).unwrap();

        assert!(EcdsaP256Sha256::verify(&pk, b"forged", &sig).is_err());
        let mut bad = sig;
        bad[0] ^= 1;
        assert!(EcdsaP256Sha256::verify(&pk, b"authentic", &bad).is_err());
        let mut bad = sig;
        bad[63] ^= 1;
        assert!(EcdsaP256Sha256::verify(&pk, b"authentic", &bad).is_err());

        let mut other = [0u8; 65];
        EcdsaP256Sha256::public_key(&[0x11u8; 32], &mut other).unwrap();
        assert!(EcdsaP256Sha256::verify(&other, b"authentic", &sig).is_err());
    }

    #[test]
    fn verification_rejects_degenerate_signatures() {
        let key = unhex(KEY).unwrap();
        let mut pk = [0u8; 65];
        EcdsaP256Sha256::public_key(&key, &mut pk).unwrap();

        let mut zero_r = [0u8; 64];
        zero_r[63] = 1;
        assert!(EcdsaP256Sha256::verify(&pk, b"m", &zero_r).is_err());

        let mut zero_s = [0u8; 64];
        zero_s[31] = 1;
        assert!(EcdsaP256Sha256::verify(&pk, b"m", &zero_s).is_err());

        let n_bytes =
            unhex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551").unwrap();
        let mut at_n = [0u8; 64];
        at_n[..32].copy_from_slice(&n_bytes);
        at_n[32..].copy_from_slice(&n_bytes);
        assert!(EcdsaP256Sha256::verify(&pk, b"m", &at_n).is_err());
    }

    #[test]
    fn signing_rejects_invalid_private_keys() {
        let mut sig = [0u8; 64];
        assert!(
            EcdsaP256Sha256::sign(&[0u8; 32], b"m", &mut sig).is_err(),
            "zero"
        );
        assert!(
            EcdsaP256Sha256::sign(&[0xffu8; 32], b"m", &mut sig).is_err(),
            ">= n"
        );
        assert!(
            EcdsaP256Sha256::sign(&[1u8; 31], b"m", &mut sig).is_err(),
            "short"
        );
    }

    /// Both `(r, s)` and `(r, n - s)` verify; normalization picks one.
    #[test]
    fn malleability_and_normalization() {
        let key = unhex(KEY).unwrap();
        let mut pk = [0u8; 65];
        EcdsaP256Sha256::public_key(&key, &mut pk).unwrap();
        let mut sig = [0u8; 64];
        EcdsaP256Sha256::sign(&key, b"sample", &mut sig).unwrap();
        assert!(
            !EcdsaP256Sha256::has_low_s(&sig).unwrap(),
            "RFC 6979 s is high here"
        );

        let mut flipped = sig;
        EcdsaP256Sha256::normalize_s(&mut flipped).unwrap();
        assert_ne!(flipped, sig);
        EcdsaP256Sha256::verify(&pk, b"sample", &flipped).unwrap();
        assert!(EcdsaP256Sha256::has_low_s(&flipped).unwrap());

        let mut twice = flipped;
        EcdsaP256Sha256::normalize_s(&mut twice).unwrap();
        assert_eq!(twice, flipped, "normalization must be idempotent");
    }

    #[test]
    fn ecdsa_self_test_passes() {
        EcdsaP256Sha256::self_test().unwrap();
    }

    // -- ECDH -------------------------------------------------------------

    /// NIST CAVP ECC CDH, first published case.
    #[test]
    fn cavp_ecc_cdh_vector() {
        let d = unhex("7d7dc5f71eb29ddaf80d6214632eeae03d9058af1fb6d22ed80badb62bc1a534").unwrap();
        let mut peer = vec![0x04u8];
        peer.extend_from_slice(
            &unhex("700c48f77f56584c5cc632ca65640db91b6bacce3a4df6b42ce7cc838833d287").unwrap(),
        );
        peer.extend_from_slice(
            &unhex("db71e509e3fd9b060ddb20ba5c51dcc5948d46fbf640dfe0441782cab85fa4ac").unwrap(),
        );
        let mut z = [0u8; 32];
        EcdhP256::agree(&d, &peer, &mut z).unwrap();
        assert_eq!(
            hex(&z),
            "46fc62106420ff012e54a434fbdd2d25ccc5852060561e68040dd7778997bd7b"
        );
    }

    #[test]
    fn both_parties_derive_the_same_secret() {
        let (alice, bob) = ([0x11u8; 32], [0x22u8; 32]);
        let mut alice_pk = [0u8; 65];
        let mut bob_pk = [0u8; 65];
        EcdhP256::public_key(&alice, &mut alice_pk).unwrap();
        EcdhP256::public_key(&bob, &mut bob_pk).unwrap();

        let mut z1 = [0u8; 32];
        let mut z2 = [0u8; 32];
        EcdhP256::agree(&alice, &bob_pk, &mut z1).unwrap();
        EcdhP256::agree(&bob, &alice_pk, &mut z2).unwrap();
        assert_eq!(z1, z2);
        assert_ne!(z1, [0u8; 32]);
    }

    #[test]
    fn compressed_and_uncompressed_peers_agree() {
        let (alice, bob) = ([0x33u8; 32], [0x44u8; 32]);
        let mut unc = [0u8; 65];
        let mut comp = [0u8; 33];
        EcdhP256::public_key(&bob, &mut unc).unwrap();
        EcdhP256::public_key_compressed(&bob, &mut comp).unwrap();

        let mut z1 = [0u8; 32];
        let mut z2 = [0u8; 32];
        EcdhP256::agree(&alice, &unc, &mut z1).unwrap();
        EcdhP256::agree(&alice, &comp, &mut z2).unwrap();
        assert_eq!(z1, z2, "the peer key encoding must not matter");
    }

    #[test]
    fn ecdh_rejects_invalid_inputs() {
        let alice = [0x11u8; 32];
        let mut z = [0u8; 32];
        assert!(EcdhP256::agree(&alice, &[0u8; 65], &mut z).is_err());
        assert!(EcdhP256::agree(&alice, &[], &mut z).is_err());

        let mut bob_pk = [0u8; 65];
        EcdhP256::public_key(&[0x22u8; 32], &mut bob_pk).unwrap();
        bob_pk[64] ^= 1;
        assert!(
            EcdhP256::agree(&alice, &bob_pk, &mut z).is_err(),
            "off curve"
        );

        let mut pk = [0u8; 65];
        assert!(EcdhP256::public_key(&[0u8; 32], &mut pk).is_err());
        assert!(EcdhP256::public_key(&[0xffu8; 32], &mut pk).is_err());
    }

    #[test]
    fn ecdh_self_test_passes() {
        EcdhP256::self_test().unwrap();
    }
}