rind 0.1.10

// Written for Graviola by Joe Birr-Pixton, 2024.
// SPDX-License-Identifier: Apache-2.0 OR ISC OR MIT-0

use core::fmt;
use core::ops::Range;

use super::util;
use crate::error::{Error, KeyFormatError};
use crate::low;
use crate::mid::rng::{RandomSource, SystemRandom};

mod precomp;

/// A P-256 public key.
#[derive(Clone, Debug)]
pub(crate) struct PublicKey {
    point: AffineMontPoint,
}

impl PublicKey {
    pub(crate) const BYTES: usize = 1 + FieldElement::BYTES + FieldElement::BYTES;

    /// Create an P-256 [`PublicKey`] from a byte slice.
    ///
    /// This must be exactly 65 bytes in length, using the X9.62
    /// uncompressed encoding.  An error is returned if a coordinate
    /// is not below the field prime, or the point is not on the curve.
    pub(crate) fn from_x962_uncompressed(bytes: &[u8]) -> Result<Self, Error> {
        let _entry = low::Entry::new_public();
        let point = AffineMontPoint::from_x962_uncompressed(bytes)?;
        Ok(Self { point })
    }
}

/// A P-256 public key for ECDSA verification.
///
/// It keeps the point's multiples, so verifying again with the same key
/// skips computing them; Diffie-Hellman's [`PublicKey`] is used once and
/// never needs them.
#[derive(Clone, Debug)]
pub(crate) struct VerifyingKey {
    /// P, 3P, ..., 15P.
    odd_multiples: [JacobianMontPoint; 8],
}

impl VerifyingKey {
    /// Create a [`VerifyingKey`] as [`PublicKey::from_x962_uncompressed`] does.
    pub(crate) fn from_x962_uncompressed(bytes: &[u8]) -> Result<Self, Error> {
        let PublicKey { point } = PublicKey::from_x962_uncompressed(bytes)?;
        Ok(Self {
            odd_multiples: point.public_odd_multiples(),
        })
    }

    pub(crate) fn raw_ecdsa_verify(&self, r: &Scalar, s: &Scalar, e: &Scalar) -> Result<(), Error> {
        // 4. Compute: u1 = e s^-1 mod n and u2 = r s^−1 mod n
        let s_inv = s.inv().as_mont();
        let u1 = s_inv.mont_mul(&e.as_mont()).demont();
        let u2 = s_inv.mont_mul(&r.as_mont()).demont();

        // 5. Compute: R = (xR, yR) = u1 G + u2 QU
        //  If R = O, output "invalid" and stop.
        let point = JacobianMontPoint::public_twin_multiply(&u1, &u2, &self.odd_multiples);

        if point.public_is_infinity() {
            return Err(Error::BadSignature);
        }

        // 6. Convert the field element xR to an integer xR using the conversion routine specified in Section 2.3.9.
        // 7. Set v = xR mod n.
        // 8. Compare v and r — if v = r, output "valid", and if v != r, output "invalid".
        match point.public_x_is(r) {
            true => Ok(()),
            false => Err(Error::BadSignature),
        }
    }
}

/// A P-256 ephemeral private key.
///
/// `agreement::PrivateKey` uses one for a single Diffie-Hellman
/// operation. It is not wiped on drop: the public keys holding one wipe it,
/// and an ECDSA nonce is one too, which lives only for the signing call.
pub(crate) struct PrivateKey {
    scalar: Scalar,
}

impl PrivateKey {
    /// Generate a new random private key using the system RNG.
    pub(crate) fn new_random() -> Result<Self, Error> {
        Self::generate(&mut SystemRandom)
    }

    /// Derive the corresponding public key, and return it in
    /// X9.62 uncompressed encoding.
    pub(crate) fn public_key_uncompressed(&self) -> [u8; PublicKey::BYTES] {
        let _entry = low::Entry::new_secret();
        self.public_point().as_bytes_uncompressed()
    }

    /// Do the Diffie-Hellman operation.
    ///
    /// `peer` is the peer's public key (and this type means it was
    /// already checked to be on the curve.)
    ///
    /// Returns a [`SharedSecret`].  May return an error in fault conditions.
    pub(crate) fn diffie_hellman(&self, peer: &PublicKey) -> Result<SharedSecret, Error> {
        let _entry = low::Entry::new_secret();
        let result = JacobianMontPoint::multiply(&self.scalar, &peer.point).as_affine();
        match low::ct::into_public(result.on_curve()) {
            true => Ok(SharedSecret(util::u64x4_to_big_endian(
                &result.x().demont().0,
            ))),
            false => Err(Error::Fault),
        }
    }

    fn public_point(&self) -> AffineMontPoint {
        let point = low::ct::into_public(AffineMontPoint::base_multiply(&self.scalar));
        match point.on_curve() {
            true => point,
            false => panic!("internal fault"),
        }
    }

    pub(crate) fn generate(rng: &mut dyn RandomSource) -> Result<Self, Error> {
        let _entry = low::Entry::new_secret();
        for _ in 0..64 {
            let mut r = [0u8; Scalar::BYTES];
            rng.fill(&mut r)?;
            low::ct::secret_slice(&r);
            if let Ok(p) = Self::from_bytes(&r) {
                return Ok(p);
            }
        }

        Err(Error::RngFailed)
    }

    fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
        Scalar::from_bytes_checked(bytes).map(|scalar| Self {
            scalar: low::ct::into_secret(scalar),
        })
    }
}

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

/// A P-256 static private key.
///
/// This backs ECDSA, so it can be serialized and deserialized. Its
/// Diffie-Hellman operation is only for tests with known scalars.
pub(crate) struct StaticPrivateKey(PrivateKey);

impl StaticPrivateKey {
    /// Generate a new random private key using the system RNG.
    #[cfg(test)]
    pub(crate) fn new_random() -> Result<Self, Error> {
        PrivateKey::generate(&mut SystemRandom).map(Self)
    }

    /// Decode a private key from `bytes`.
    ///
    /// `bytes` may be larger or smaller than the size of `n`: excess bytes
    /// must be zero.  If given a variable-sized input, this is deemed a
    /// non-secret property.  Prefer to use fixed-sized inputs.
    ///
    /// An error is returned if the magnitude of the value is larger than
    /// `n` (ie, the input is never reduced mod n),  or the value is zero.
    pub(crate) fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
        let _entry = low::Entry::new_secret();
        PrivateKey::from_bytes(bytes).map(Self)
    }

    /// Return a fixed-length encoding of this private key's value, still secret.
    pub(crate) fn secret_bytes(&self) -> [u8; Scalar::BYTES] {
        self.0.scalar.as_bytes()
    }

    /// Derive the corresponding public key, and return it in
    /// X9.62 uncompressed encoding.
    pub(crate) fn public_key_uncompressed(&self) -> [u8; PublicKey::BYTES] {
        let _entry = low::Entry::new_secret();
        self.0.public_point().as_bytes_uncompressed()
    }

    /// Do the Diffie-Hellman operation.
    ///
    /// `peer` is the peer's public key (and this type means it was
    /// already checked to be on the curve.)
    ///
    /// Returns a [`SharedSecret`].  May return an error in fault conditions.
    #[cfg(test)]
    pub(crate) fn diffie_hellman(&self, peer: &PublicKey) -> Result<SharedSecret, Error> {
        let _entry = low::Entry::new_secret();
        self.0.diffie_hellman(peer)
    }

    pub(crate) fn generate(rng: &mut dyn RandomSource) -> Result<Self, Error> {
        let _entry = low::Entry::new_secret();
        PrivateKey::generate(rng).map(Self)
    }

    pub(crate) fn public_key_x_scalar(&self) -> Scalar {
        let _entry = low::Entry::new_secret();
        self.0.public_point().x_scalar()
    }

    pub(crate) fn raw_ecdsa_sign(&self, k: &Self, e: &Scalar, r: &Scalar) -> Scalar {
        // this is (e + r * d) / k
        let lhs_mont = self
            .0
            .scalar
            .as_mont()
            .mont_mul(&r.as_mont())
            .demont()
            .add(e)
            .as_mont();
        low::ct::into_public(k.0.scalar.inv().mont_mul(&lhs_mont))
    }
}

/// A shared secret output from a P-256 Diffie-Hellman operation.
///
/// It is not wiped on drop: `agreement::SharedSecret` wipes it.
pub(crate) struct SharedSecret(pub(crate) [u8; FieldElement::BYTES]);

#[derive(Clone, Copy, Debug, Default)]
struct AffineMontPoint {
    xy: [u64; 8],
}

impl AffineMontPoint {
    const X: Range<usize> = 0..4;
    const Y: Range<usize> = 4..8;

    fn from_x962_uncompressed(bytes: &[u8]) -> Result<Self, Error> {
        match bytes.first() {
            Some(&0x04) => (),
            Some(_) => return Err(KeyFormatError::Compressed.into()),
            None => return Err(KeyFormatError::WrongLength.into()),
        }

        if bytes.len() != PublicKey::BYTES {
            return Err(KeyFormatError::WrongLength.into());
        }

        let (_, xy) = bytes.split_at(1);
        let (x, y) = xy.split_at(FieldElement::BYTES);

        let x = util::big_endian_slice_to_u64x4(x).unwrap();
        let y = util::big_endian_slice_to_u64x4(y).unwrap();

        // A coordinate at or above p would be reduced, giving the point a
        // second encoding.  Public, so this need not be constant time.
        let below_p = |v: &[u64; 4]| v.iter().rev().lt(CURVE_PRIME.iter().rev());
        if !below_p(&x) || !below_p(&y) {
            return Err(KeyFormatError::NotOnCurve.into());
        }

        let point = Self::from_xy(FieldElement(x).as_mont(), FieldElement(y).as_mont());

        if !point.on_curve() {
            return Err(KeyFormatError::NotOnCurve.into());
        }

        Ok(point)
    }

    fn x_scalar(&self) -> Scalar {
        let bytes = self.as_bytes_uncompressed();
        Scalar::from_bytes_reduced(&bytes[1..1 + Scalar::BYTES]).unwrap()
    }

    fn from_xy(x: FieldElement, y: FieldElement) -> Self {
        let mut r = Self::default();
        r.xy[Self::X].copy_from_slice(&x.0[..]);
        r.xy[Self::Y].copy_from_slice(&y.0[..]);
        r
    }

    fn x(&self) -> FieldElement {
        FieldElement(self.xy[Self::X].try_into().unwrap())
    }

    fn y(&self) -> FieldElement {
        FieldElement(self.xy[Self::Y].try_into().unwrap())
    }

    fn on_curve(&self) -> bool {
        // Compute the curve equation:
        //
        // y ^ 2 === x ^ 3 + ax + b
        //
        // all in GF(p)
        //

        let x = self.x();
        let rhs = x.mont_sqr(); // x ^ 2
        let rhs = rhs.add(&CURVE_A_MONT); // x ^ 2 + a
        let rhs = rhs.mont_mul(&x); // (x ^ 2 + a) * x   equiv  x ^ 3 + ax
        let rhs = rhs.add(&CURVE_B_MONT);

        let lhs = self.y().mont_sqr();

        // Constant time, since `diffie_hellman` checks a secret point.
        low::bignum_eq(&lhs.0, &rhs.0)
    }

    fn as_bytes_uncompressed(&self) -> [u8; PublicKey::BYTES] {
        let mut r = [0u8; PublicKey::BYTES];
        let (indicator, xy) = r.split_at_mut(1);
        let (x, y) = xy.split_at_mut(FieldElement::BYTES);

        indicator[0] = 0x04;
        x.copy_from_slice(&util::u64x4_to_big_endian(&self.x().demont().0));
        y.copy_from_slice(&util::u64x4_to_big_endian(&self.y().demont().0));
        r
    }

    #[cfg(test)]
    fn slow_multiply(&self, scalar: &Scalar) -> Self {
        let mut result = JacobianMontPoint::infinity();

        let mut j = JacobianMontPoint::from_affine(self);
        let zero = JacobianMontPoint::zero();

        for bit in scalar.bits() {
            result.add_inplace(&JacobianMontPoint::select(&zero, &j, bit));
            j = j.double();
        }

        result.as_affine()
    }

    fn negate_y(&mut self) {
        let neg_y = self.y().negate_mod_p();
        self.xy[Self::Y].copy_from_slice(&neg_y.0);
    }

    /// P, 3P, ..., 15P: the odd multiples a width-5 NAF digit picks.
    fn public_odd_multiples(&self) -> [JacobianMontPoint; 8] {
        let p = JacobianMontPoint::from_affine(self);
        let p2 = p.double();
        let mut r = [p; 8];
        for i in 1..r.len() {
            r[i] = r[i - 1].add(&p2);
        }
        r
    }

    /// `scalar * G`, by aws-lc's routines over the generator table.
    #[cfg(target_arch = "x86_64")]
    fn base_multiply(scalar: &Scalar) -> Self {
        JacobianMontPoint::base_multiply(scalar).as_affine()
    }

    /// `scalar * G`, by s2n-bignum's `p256_scalarmulbase` over the
    /// generator table.
    #[cfg(target_arch = "aarch64")]
    fn base_multiply(scalar: &Scalar) -> Self {
        let mut xy = [0; 8];
        low::p256_scalarmulbase(&mut xy, &scalar.0, &precomp::CURVE_GENERATOR_PRECOMP);
        let x = FieldElement(xy[Self::X].try_into().unwrap());
        let y = FieldElement(xy[Self::Y].try_into().unwrap());
        Self::from_xy(x.as_mont(), y.as_mont())
    }

    /// Returns `row[index - 1]`, for a public `index` above zero.
    fn public_lookup(row: &[u64], index: u8) -> Self {
        Self {
            xy: row.as_chunks::<8>().0[index as usize - 1],
        }
    }

    /// Negates `y` if `negate` is 1, in constant time.
    #[cfg(target_arch = "x86_64")]
    fn negate_y_if(&mut self, negate: u8) {
        let y = self.y();
        low::bignum_mux(
            negate.into(),
            &mut self.xy[Self::Y],
            &y.negate_mod_p().0,
            &y.0,
        );
    }
}

#[derive(Clone, Copy, Debug)]
struct JacobianMontPoint {
    xyz: [u64; 12],
}

impl JacobianMontPoint {
    const X: Range<usize> = 0..4;
    const Y: Range<usize> = 4..8;
    const XY: Range<usize> = 0..8;
    const Z: Range<usize> = 8..12;

    fn infinity() -> Self {
        Self {
            xyz: [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
        }
    }

    fn public_is_infinity(&self) -> bool {
        self.z().public_eq(&FieldElement::default())
    }

    fn zero() -> Self {
        Self { xyz: [0; 12] }
    }

    fn x(&self) -> FieldElement {
        FieldElement(self.xyz[Self::X].try_into().unwrap())
    }

    fn y(&self) -> FieldElement {
        FieldElement(self.xyz[Self::Y].try_into().unwrap())
    }

    fn z(&self) -> FieldElement {
        FieldElement(self.xyz[Self::Z].try_into().unwrap())
    }

    /// `scalar * point`, by s2n-bignum's `p256_montjscalarmul`.
    fn multiply(scalar: &Scalar, point: &AffineMontPoint) -> Self {
        let mut r = Self::zero();
        low::p256_montjscalarmul(&mut r.xyz, &scalar.0, &Self::from_affine(point).xyz);
        r
    }

    /// `scalar * G`, as aws-lc's `ecp_nistz256_point_mul_base` computes it:
    /// one addition from each generator table row per Booth-recoded 7-bit
    /// window, with every row scanned whole.
    ///
    /// No addition doubles, which `p256_point_add_affine` cannot: the
    /// accumulator sums lower windows, so it is a smaller integer than the
    /// table point, in magnitude, and below n.
    #[cfg(target_arch = "x86_64")]
    fn base_multiply(scalar: &Scalar) -> Self {
        let mut windows = precomp::CURVE_GENERATOR_PRECOMP
            .iter()
            .zip(scalar.booth_recoded::<BASE_WINDOW>());
        let lookup = |row, digit, sign| {
            let mut point = AffineMontPoint {
                xy: low::p256_select_w7(row, digit),
            };
            point.negate_y_if(sign);
            point
        };

        // unwrap: the number of windows is constant. The first point is
        // infinity, with a zero `z`, when its digit is zero.
        let (row, (digit, sign)) = windows.next().unwrap();
        let mut result = Self::from_affine(&lookup(row, digit, sign));
        low::bignum_mux(
            digit.into(),
            &mut result.xyz[Self::Z],
            &CURVE_ONE_MONT.0,
            &[0; 4],
        );

        for (row, (digit, sign)) in windows {
            result.xyz = low::p256_point_add_affine(&result.xyz, &lookup(row, digit, sign).xy);
        }
        result
    }

    /// `g * G + p * P` for public scalars, given P's odd multiples.
    ///
    /// One chain of doublings serves both: P's digits are a width-5 NAF
    /// over `odd_multiples`, and G's a width-6 NAF over the generator
    /// table's first row, which holds G to at least 32G.
    fn public_twin_multiply(g: &Scalar, p: &Scalar, odd_multiples: &[Self; 8]) -> Self {
        let g_digits = g.public_naf::<6>();
        let p_digits = p.public_naf::<5>();
        let g_multiples = &precomp::CURVE_GENERATOR_PRECOMP[0][..];

        let mut result = Self::infinity();
        for (g_digit, p_digit) in g_digits.iter().zip(&p_digits).rev() {
            if !result.public_is_infinity() {
                result = result.double();
            }
            if *p_digit != 0 {
                let mut tmp = odd_multiples[usize::from(p_digit.unsigned_abs() / 2)];
                if *p_digit < 0 {
                    tmp.negate_y();
                }
                result = Self::public_add_fast(&result, &tmp);
            }
            if *g_digit != 0 {
                let mut tmp = AffineMontPoint::public_lookup(g_multiples, g_digit.unsigned_abs());
                if *g_digit < 0 {
                    tmp.negate_y();
                }
                result = result.public_add_affine(&tmp);
            }
        }
        result
    }

    fn from_affine(p: &AffineMontPoint) -> Self {
        let mut xyz: [u64; 12] = Default::default();
        xyz[Self::XY].copy_from_slice(&p.xy);
        xyz[Self::Z].copy_from_slice(&CURVE_ONE_MONT.0);
        Self { xyz }
    }

    fn as_affine(&self) -> AffineMontPoint {
        // recover (x, y) from (x / z ^ 2, x / z ^ 3, z)
        // inversion calculated outside montgomery domain
        // (benchmarked vs addition chain in montgomery)
        let z_inv = self.z().demont().inv().as_mont();
        let z2_inv = z_inv.mont_sqr();
        let z3_inv = z2_inv.mont_mul(&z_inv);

        let x = self.x().mont_mul(&z2_inv);
        let y = self.y().mont_mul(&z3_inv);

        AffineMontPoint::from_xy(x, y)
    }

    /// `a + b`, for any points, including at infinity, equal, or opposite,
    /// which `p256_montjadd` does not handle.
    fn public_add(a: &Self, b: &Self) -> Self {
        if a.public_is_infinity() {
            return *b;
        }
        if b.public_is_infinity() {
            return *a;
        }

        // Both points scaled to the product of their z's.
        let (az2, bz2) = (a.z().mont_sqr(), b.z().mont_sqr());
        let same_x = a.x().mont_mul(&bz2).public_eq(&b.x().mont_mul(&az2));
        if !same_x {
            return a.add(b);
        }
        let ay = a.y().mont_mul(&bz2.mont_mul(&b.z()));
        let by = b.y().mont_mul(&az2.mont_mul(&a.z()));
        match ay.public_eq(&by) {
            true => a.double(),
            false => Self::infinity(),
        }
    }

    /// `a + b`, for any points, by [`Self::public_add`] only when they turn
    /// out to be equal or opposite.
    ///
    /// The formulas give such points a zero z, as they do infinity, so
    /// only a zero z from two points not at infinity takes the slow path.
    fn public_add_fast(a: &Self, b: &Self) -> Self {
        let sum = a.add(b);
        match sum.public_is_infinity() && !a.public_is_infinity() && !b.public_is_infinity() {
            true => Self::public_add(a, b),
            false => sum,
        }
    }

    /// `self + p`, for any points, as [`Self::public_add_fast`] does.
    fn public_add_affine(&self, p: &AffineMontPoint) -> Self {
        let mut sum = *self;
        sum.add_inplace_affine(p);
        match sum.public_is_infinity() && !self.public_is_infinity() {
            true => Self::public_add(self, &Self::from_affine(p)),
            false => sum,
        }
    }

    /// Whether this point's x, reduced mod n, is `r`, for a point not at
    /// infinity.
    ///
    /// x = X / z², so this checks X = r * z², and (r + n) * z² when that is
    /// below p, the only other x that reduces to `r`. Unlike computing x,
    /// that needs no inversion.
    fn public_x_is(&self, r: &Scalar) -> bool {
        let z2 = self.z().mont_sqr();
        let is = |x: [u64; 4]| FieldElement(x).as_mont().mont_mul(&z2).public_eq(&self.x());
        if is(r.0) {
            return true;
        }
        let mut r_plus_n = [0; 4];
        let mut carry = false;
        for (sum, (r, n)) in r_plus_n.iter_mut().zip(r.0.iter().zip(CURVE_ORDER)) {
            let (s, c1) = r.overflowing_add(n);
            let (s, c2) = s.overflowing_add(u64::from(carry));
            *sum = s;
            carry = c1 | c2;
        }
        !carry && r_plus_n.iter().rev().lt(CURVE_PRIME.iter().rev()) && is(r_plus_n)
    }

    #[must_use]
    fn double(&self) -> Self {
        let mut tmp = Self::zero();
        low::p256_montjdouble(&mut tmp.xyz, &self.xyz);
        tmp
    }

    #[cfg(test)]
    fn double_inplace_n(&mut self, n: usize) {
        for _ in 0..n {
            let tmp = *self;
            low::p256_montjdouble(&mut self.xyz, &tmp.xyz);
        }
    }

    #[cfg(test)]
    fn add_inplace(&mut self, p: &Self) {
        let mut r = Self::infinity();
        low::p256_montjadd(&mut r.xyz, &self.xyz, &p.xyz);
        *self = r;
    }

    fn add_inplace_affine(&mut self, p: &AffineMontPoint) {
        let mut r = Self::infinity();
        low::p256_montjmixadd(&mut r.xyz, &self.xyz, &p.xy);
        *self = r;
    }

    #[must_use]
    fn add(&self, p: &Self) -> Self {
        let mut r = Self::infinity();
        low::p256_montjadd(&mut r.xyz, &self.xyz, &p.xyz);
        r
    }

    /// Return p0 if select == 0, p1 otherwise
    #[cfg(test)]
    #[must_use]
    fn select(p0: &Self, p1: &Self, select: u8) -> Self {
        let mut r = Self::zero();
        let select = select as u64;
        low::bignum_mux(select, &mut r.xyz[..], &p1.xyz[..], &p0.xyz[..]);
        r
    }

    fn negate_y(&mut self) {
        let neg_y = self.y().negate_mod_p();
        self.xyz[Self::Y].copy_from_slice(&neg_y.0);
    }
}

#[derive(Clone, Copy, Debug, Default)]
struct FieldElement([u64; 4]);

impl FieldElement {
    const BYTES: usize = 32;

    fn inv(&self) -> Self {
        let mut r = Self::default();
        low::bignum_inv_p256(&mut r.0, &self.0);
        r
    }

    /// Montgomery squaring mod p256
    fn mont_sqr(&self) -> Self {
        let mut r = Self::default();
        low::bignum_montsqr_p256(&mut r.0, &self.0);
        r
    }

    /// Addition mod p256
    fn add(&self, other: &Self) -> Self {
        let mut r = Self::default();
        low::bignum_add_p256(&mut r.0, &self.0, &other.0);
        r
    }

    /// Montgomery multiplication mod p256
    fn mont_mul(&self, other: &Self) -> Self {
        let mut r = Self::default();
        low::bignum_montmul_p256(&mut r.0, &self.0, &other.0);
        r
    }

    /// Remove one montgomery factor
    fn demont(&self) -> Self {
        let mut r = Self::default();
        low::bignum_demont_p256(&mut r.0, &self.0);
        r
    }

    /// Add a montgomery factor
    fn as_mont(&self) -> Self {
        let mut r = Self::default();
        low::bignum_tomont_p256(&mut r.0, &self.0);
        r
    }

    fn negate_mod_p(&self) -> Self {
        let mut r = Self::default();
        low::bignum_neg_p256(&mut r.0, &self.0);
        r
    }

    /// Public equality
    fn public_eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

#[derive(Default)]
pub(crate) struct Scalar([u64; 4]);

impl Scalar {
    pub(crate) const BYTES: usize = 32;

    /// Create a scalar from the given slice, which can be any size.
    ///
    /// If it is larger than 32 bytes, the leading bytes must be
    /// zero (this is deemed a non-secret property).
    ///
    /// This returns an error if the scalar is zero or larger than
    /// the curve order.
    pub(crate) fn from_bytes_checked(bytes: &[u8]) -> Result<Self, Error> {
        let full = Self(
            util::big_endian_slice_any_size_to_u64x4(bytes)
                .ok_or(KeyFormatError::ScalarOutOfRange)?,
        );

        full.into_range_check()
    }

    pub(crate) fn from_bytes_reduced(bytes: &[u8]) -> Result<Self, Error> {
        Ok(
            Self(util::big_endian_slice_any_size_to_u64x4(bytes).ok_or(Error::WrongLength)?)
                .reduce_mod_n(),
        )
    }

    fn into_range_check(self) -> Result<Self, Error> {
        let reduced = self.reduce_mod_n();

        // Whether a scalar is in range is public: a key or signature is refused
        // on it, and a rejected nonce candidate says nothing of the one accepted.
        match low::ct::into_public(reduced.private_eq(&self) & !self.is_zero()) {
            true => Ok(self),
            false => Err(KeyFormatError::ScalarOutOfRange.into()),
        }
    }

    pub(crate) fn as_bytes(&self) -> [u8; Self::BYTES] {
        util::u64x4_to_big_endian(&self.0)
    }

    #[cfg(test)]
    fn small_u64(v: u64) -> Self {
        Self([v, 0, 0, 0])
    }

    /// Private test for zero
    pub(crate) fn is_zero(&self) -> bool {
        self.private_eq(&Self::default())
    }

    /// Private equality
    fn private_eq(&self, other: &Self) -> bool {
        low::bignum_eq(&self.0, &other.0)
    }

    /// Reduce mod n (curve order)
    fn reduce_mod_n(&self) -> Self {
        let mut r = Self::default();
        low::bignum_mod_n256(&mut r.0, &self.0);
        r
    }

    /// Remove one montgomery factor mod n
    fn demont(&self) -> Self {
        let mut r = Self::default();
        low::bignum_demont(&mut r.0, &self.0, &CURVE_ORDER);
        r
    }

    /// Add a montgomery factor mod n
    fn as_mont(&self) -> Self {
        let mut r = Self::default();
        low::bignum_montmul(&mut r.0, &self.0, &CURVE_ORDER_MM, &CURVE_ORDER);
        r
    }

    /// Return 2^512 mod n, ie MM mod n
    #[cfg(test)]
    fn montifier() -> Self {
        let mut r = Self::default();
        let mut tmp = Self::default();
        low::bignum_montifier(&mut r.0, &CURVE_ORDER, &mut tmp.0);
        r
    }

    /// Montgomery multiplication mod n
    ///
    /// Assumes `self` and `other` are in montgomery domain.
    /// Result is in montgomery domain.
    fn mont_mul(&self, other: &Self) -> Self {
        let mut r = Self::default();
        low::bignum_montmul(&mut r.0, &self.0, &other.0, &CURVE_ORDER);
        r
    }

    /// Find the multiplicative inverse of `self` mod n
    fn inv(&self) -> Self {
        let mut r = Self::default();
        let mut temp = [0u64; 4 * 3];
        low::bignum_modinv(&mut r.0, &self.0, &CURVE_ORDER, &mut temp);
        r
    }

    /// Add `self` + `other` mod n
    fn add(&self, other: &Self) -> Self {
        let mut r = Self::default();
        low::bignum_modadd(&mut r.0, &self.0, &other.0, &CURVE_ORDER);
        r
    }

    /// Iterator of the bits of the element, lowest first
    #[cfg(test)]
    fn bits(&self) -> Bits<'_> {
        Bits {
            scalar: self,
            word: 0,
            bit: 0,
        }
    }

    /// Iterator of `256 / W + 1` W-bit elements, LSB first, sign bit is separate
    #[cfg(target_arch = "x86_64")]
    fn booth_recoded<const W: usize>(&self) -> BoothRecode<W> {
        BoothRecode::new(self)
    }

    /// The width-`W` non-adjacent form of this scalar, by
    /// [`util::public_naf`].
    fn public_naf<const W: u32>(&self) -> [i8; 257] {
        let mut digits = [0; 257];
        util::public_naf::<W>(&self.0, &mut digits);
        digits
    }
}

#[cfg(test)]
struct Bits<'a> {
    scalar: &'a Scalar,
    word: usize,
    bit: usize,
}

#[cfg(test)]
impl Iterator for Bits<'_> {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        if self.word > 3 {
            return None;
        }

        let v = (self.scalar.0[self.word] >> self.bit) & 1;

        self.bit += 1;
        if self.bit == 64 {
            self.word += 1;
            self.bit = 0;
        }

        Some(v as u8)
    }
}

#[cfg(target_arch = "x86_64")]
struct BoothRecode<const W: usize> {
    // little endian
    bytes: [u8; 33],
    index: usize,
}

#[cfg(target_arch = "x86_64")]
impl<const W: usize> BoothRecode<W> {
    fn new(scalar: &Scalar) -> Self {
        let mut bytes = [0u8; 33];

        bytes[0..8].copy_from_slice(&scalar.0[0].to_le_bytes());
        bytes[8..16].copy_from_slice(&scalar.0[1].to_le_bytes());
        bytes[16..24].copy_from_slice(&scalar.0[2].to_le_bytes());
        bytes[24..32].copy_from_slice(&scalar.0[3].to_le_bytes());

        Self { bytes, index: 0 }
    }

    fn recode(v: u8) -> (u8, u8) {
        // see the comment above boringssl's `ec_GFp_nistp_recode_scalar_bits` for
        // references
        let sign = !((v >> W).wrapping_sub(1));

        let d = (1u16 << (W + 1)).wrapping_sub(v as u16).wrapping_sub(1) as u8;
        let d = (d & sign) | (v & !sign);
        let d = (d >> 1).wrapping_add(d & 1);

        (d, sign & 1)
    }
}

#[cfg(target_arch = "x86_64")]
impl<const W: usize> Iterator for BoothRecode<W> {
    type Item = (u8, u8);

    fn next(&mut self) -> Option<Self::Item> {
        let mask = ((1u16 << (W + 1)) - 1) as u8;

        match self.index {
            0 => {
                self.index += W;
                Some(Self::recode((self.bytes[0] << 1) & mask))
            }

            _ if self.index < 256 => {
                let offset = (self.index - 1) / 8;
                let shift = (self.index - 1) % 8;
                let value = (((self.bytes[offset] as u16) | ((self.bytes[offset + 1] as u16) << 8))
                    >> shift) as u8
                    & mask;
                self.index += W;
                Some(Self::recode(value))
            }

            _ => None,
        }
    }
}

/// The generator table's window, aws-lc's.
#[cfg(target_arch = "x86_64")]
const BASE_WINDOW: usize = 7;

/// 37 rows of the 64 multiples `i * 2^(7 * j) * G`, one row per 7-bit window.
///
/// 37 := 256 / 7 + 1, as Booth recoding carries into a window above the top bit.
#[cfg(target_arch = "x86_64")]
type AffineMontPointTable = [low::P256GeneratorRow; 37];

/// 43 rows of the 32 multiples `i * 2^(6 * j) * G`, one row per 6-bit window.
///
/// 43 := 256 / 6 + 1, as Booth recoding carries into a window above the top bit.
#[cfg(target_arch = "aarch64")]
type AffineMontPointTable = [[u64; 256]; 43];

const CURVE_A_MONT: FieldElement = FieldElement([
    0xffff_ffff_ffff_fffc,
    0x0000_0003_ffff_ffff,
    0x0000_0000_0000_0000,
    0xffff_fffc_0000_0004,
]);

const CURVE_B_MONT: FieldElement = FieldElement([
    0xd89c_df62_29c4_bddf,
    0xacf0_05cd_7884_3090,
    0xe5a2_20ab_f721_2ed6,
    0xdc30_061d_0487_4834,
]);

const CURVE_ONE_MONT: FieldElement = FieldElement([
    0x0000_0000_0000_0001,
    0xffff_ffff_0000_0000,
    0xffff_ffff_ffff_ffff,
    0x0000_0000_ffff_fffe,
]);

const CURVE_PRIME: [u64; 4] = [
    0xffff_ffff_ffff_ffff,
    0x0000_0000_ffff_ffff,
    0x0000_0000_0000_0000,
    0xffff_ffff_0000_0001,
];

const CURVE_ORDER: [u64; 4] = [
    0xf3b9_cac2_fc63_2551,
    0xbce6_faad_a717_9e84,
    0xffff_ffff_ffff_ffff,
    0xffff_ffff_0000_0000,
];

const CURVE_ORDER_MM: [u64; 4] = [
    0x83244c95be79eea2,
    0x4699799c49bd6fa6,
    0x2845b2392b6bec59,
    0x66e12d94f3d95620,
];

#[cfg(test)]
#[cfg_attr(coverage_nightly, coverage(off))]
mod tests {
    use super::*;

    const CURVE_GENERATOR: AffineMontPoint = AffineMontPoint {
        xy: [
            0x79e7_30d4_18a9_143c,
            0x75ba_95fc_5fed_b601,
            0x79fb_732b_7762_2510,
            0x1890_5f76_a537_55c6,
            0xddf2_5357_ce95_560a,
            0x8b4a_b8e4_ba19_e45c,
            0xd2e8_8688_dd21_f325,
            0x8571_ff18_2588_5d85,
        ],
    };

    #[test]
    fn generator_on_curve() {
        println!("{CURVE_GENERATOR:x?}");
        assert!(CURVE_GENERATOR.on_curve());
        println!("demont {:x?}", CURVE_GENERATOR.as_bytes_uncompressed());
    }

    #[test]
    fn generate_key_1() {
        let scalar = Scalar::small_u64(1);
        let r = CURVE_GENERATOR.slow_multiply(&scalar);
        assert_eq!(
            r.as_bytes_uncompressed(),
            CURVE_GENERATOR.as_bytes_uncompressed()
        );
        println!("raw {r:x?}");
        println!("fmt {:x?}", r.as_bytes_uncompressed());
    }

    #[test]
    fn point_double() {
        let mut p = JacobianMontPoint::from_affine(&CURVE_GENERATOR);
        println!("p = {p:x?}");
        p = p.double();
        println!("p2 = {p:x?}");
        println!("p2 aff = {:x?}", p.as_affine());
        println!("enc = {:x?}", p.as_affine().as_bytes_uncompressed());
    }

    #[test]
    fn generate_key_2() {
        let scalar = Scalar::small_u64(2);
        let r = CURVE_GENERATOR.slow_multiply(&scalar);
        println!("raw {r:x?}");
        println!("fmt {:x?}", r.as_bytes_uncompressed());
    }

    #[test]
    fn multiply_matches_double_and_add() {
        let n_minus = |k: u64| {
            let mut s = CURVE_ORDER;
            s[0] -= k;
            Scalar(s)
        };
        // Every 6-bit window 32, and every 7-bit window 64, so each Booth
        // digit is a full row's last entry, on aarch64 and x86_64.
        let all_32 = Scalar([0x0820_8208_2082_0820; 4]);
        let all_64 = Scalar([
            0x4081_0204_0810_2040,
            0x2040_8102_0408_1020,
            0x1020_4081_0204_0810,
            0x0810_2040_8102_0408,
        ]);
        for scalar in [
            Scalar::small_u64(1),
            Scalar::small_u64(2),
            Scalar::small_u64(3),
            Scalar::small_u64(32),
            Scalar::small_u64(33),
            Scalar::small_u64(99999999),
            Scalar([0, 0, 0, 1 << 63]),
            all_32,
            all_64,
            n_minus(1),
            n_minus(2),
        ] {
            let expected = CURVE_GENERATOR.slow_multiply(&scalar).xy;
            assert_eq!(AffineMontPoint::base_multiply(&scalar).xy, expected);
            let odd_multiples = CURVE_GENERATOR.public_odd_multiples();
            let zero = Scalar::default();
            for (g, p) in [(&scalar, &zero), (&zero, &scalar)] {
                assert_eq!(
                    JacobianMontPoint::public_twin_multiply(g, p, &odd_multiples)
                        .as_affine()
                        .xy,
                    expected
                );
            }
            assert_eq!(
                JacobianMontPoint::multiply(&scalar, &CURVE_GENERATOR)
                    .as_affine()
                    .xy,
                expected
            );
        }
    }

    #[test]
    fn twin_multiply_exceptional() {
        // With P = G, the accumulator meets the point it adds: equal, which
        // must double, or opposite, which must give infinity.
        let odd_multiples = CURVE_GENERATOR.public_odd_multiples();
        let n_minus = |k: u64| {
            let mut s = CURVE_ORDER;
            s[0] -= k;
            Scalar(s)
        };
        for (g, p) in [
            (Scalar::small_u64(1), Scalar::small_u64(1)),
            (Scalar::small_u64(3), Scalar::small_u64(3)),
            (Scalar::small_u64(2), Scalar::small_u64(1)),
            (Scalar::small_u64(1), n_minus(1)),
            (n_minus(5), Scalar::small_u64(5)),
            (n_minus(1), n_minus(1)),
            (Scalar([0, 0, 0, 1 << 63]), Scalar([0, 0, 0, 1 << 63])),
        ] {
            let expected = CURVE_GENERATOR.slow_multiply(&g.add(&p)).xy;
            assert_eq!(
                JacobianMontPoint::public_twin_multiply(&g, &p, &odd_multiples)
                    .as_affine()
                    .xy,
                expected
            );
        }
    }

    #[test]
    fn generate_key_known_answer() {
        let bytes = b"\x1F\x55\x45\x23\x08\x50\x8C\x6B\x24\x37\x0F\x22\x1E\xF1\xB3\xF9\x54\x46\xBE\x4F\x8A\x4B\x42\x8A\x5B\x51\xB7\x10\xC2\x68\x4C\x03";
        let private = PrivateKey::from_bytes(bytes).unwrap();
        println!("priv = {private:x?}");
        let public = private.public_key_uncompressed();
        println!("pub = {public:x?}");
        const EXPECTED: &[u8; 65] = b"\x04\xcb\x8a\x14\x1c\xd7\xe4\x07\xaf\x69\xa5\x01\x88\xe9\x1c\xe5\x5d\xcc\xfd\x33\x48\xda\xba\x4a\x9c\x46\x64\x33\x2e\x95\x59\xb6\x81\x44\xfc\x1a\x61\xd8\x41\xe4\xdb\x80\x1b\x33\x51\x20\x12\x1d\x0b\xa4\x84\xb3\xc9\x53\xb3\x1d\x35\x1d\x7f\xa2\x13\x97\xd1\x25\x47";
        assert_eq!(&public, EXPECTED);
        PublicKey::from_x962_uncompressed(&public).unwrap();
    }

    #[test]
    fn test_raw_ecdsa_sign() {
        let private = StaticPrivateKey::from_bytes(b"\xd1\xf6\xbc\xcc\x3e\x5a\x40\x1b\xcc\x2c\x21\xbe\x34\x90\xed\x38\xde\xf4\x93\x7f\x78\x06\x03\xf5\x2b\x23\xb9\xa6\xfa\x9c\xf6\x0e").unwrap();
        let k = StaticPrivateKey::from_bytes(b"\xe7\x95\x37\xa1\xd7\x55\x45\x1f\x8c\x3c\xbf\xf7\x84\xea\x5c\x1c\xdf\xe1\x6b\x1d\x13\xe7\xbf\xbb\x04\xd7\xfd\x90\x57\xee\xee\xf7").unwrap();
        let e = Scalar::from_bytes_checked(b"\x2c\xf2\x4d\xba\x5f\xb0\xa3\x0e\x26\xe8\x3b\x2a\xc5\xb9\xe2\x9e\x1b\x16\x1e\x5c\x1f\xa7\x42\x5e\x73\x04\x33\x62\x93\x8b\x98\x24").unwrap();
        let r = Scalar::from_bytes_checked(b"\x78\xee\x34\xc8\xb6\x52\x29\x54\x96\x19\x79\x45\x2e\x6e\x0c\xe0\x68\x5d\x40\x42\x38\x41\xef\xeb\x06\xfe\x3e\x3f\xf7\xb6\x5d\xf5").unwrap();
        let s = private.raw_ecdsa_sign(&k, &e, &r);
        assert_eq!(
            format!("{:02x?}", s.as_bytes()),
            "[5b, c9, 8e, 7d, 28, 74, d0, 9d, e8, fb, da, 22, 34, 83, 24, 4f, a1, ba, a2, 6a, 71, 91, 4e, 8e, d4, 8f, 88, b8, 2d, 17, 0b, 4b]"
        );
    }

    #[test]
    fn private_key_in_range() {
        assert_eq!(
            PrivateKey::from_bytes(&[0u8; 32]).unwrap_err(),
            Error::from(KeyFormatError::ScalarOutOfRange)
        );

        // order rejected
        assert_eq!(PrivateKey::from_bytes(b"\xff\xff\xff\xff\x00\x00\x00\x00\xff\xff\xff\xff\xff\xff\xff\xff\xbc\xe6\xfa\xad\xa7\x17\x9e\x84\xf3\xb9\xca\xc2\xfc\x63\x25\x51").unwrap_err(), Error::from(KeyFormatError::ScalarOutOfRange));

        // order + 1 rejected
        assert_eq!(PrivateKey::from_bytes(b"\xff\xff\xff\xff\x00\x00\x00\x00\xff\xff\xff\xff\xff\xff\xff\xff\xbc\xe6\xfa\xad\xa7\x17\x9e\x84\xf3\xb9\xca\xc2\xfc\x63\x25\x52").unwrap_err(), Error::from(KeyFormatError::ScalarOutOfRange));

        // order - 1 is ok
        PrivateKey::from_bytes(b"\xff\xff\xff\xff\x00\x00\x00\x00\xff\xff\xff\xff\xff\xff\xff\xff\xbc\xe6\xfa\xad\xa7\x17\x9e\x84\xf3\xb9\xca\xc2\xfc\x63\x25\x50").unwrap();
    }

    #[test]
    fn curve_field_elements_as_mont() {
        const CURVE_A: FieldElement = FieldElement([
            0xffff_ffff_ffff_fffc,
            0x0000_0000_ffff_ffff,
            0x0000_0000_0000_0000,
            0xffff_ffff_0000_0001,
        ]);
        const CURVE_B: FieldElement = FieldElement([
            0x3bce_3c3e_27d2_604b,
            0x651d_06b0_cc53_b0f6,
            0xb3eb_bd55_7698_86bc,
            0x5ac6_35d8_aa3a_93e7,
        ]);

        println!("G.x = {:x?}", CURVE_GENERATOR.x().as_mont());
        println!("G.y = {:x?}", CURVE_GENERATOR.y().as_mont());
        println!("a = {:x?}", CURVE_A.as_mont());
        println!("b = {:x?}", CURVE_B.as_mont());
        let one = FieldElement([1, 0, 0, 0]);
        println!("R = {:x?}", one.as_mont());
        println!("R * R = {:x?}", one.as_mont().as_mont());

        println!("montify n = {:016x?}", Scalar::montifier().0);
    }

    #[test]
    fn base_point_precomp() {
        let mut base = JacobianMontPoint::from_affine(&CURVE_GENERATOR);
        for row in &precomp::CURVE_GENERATOR_PRECOMP {
            let mut multiple = base;
            for (i, entry) in (1..).zip(row.as_chunks::<8>().0) {
                assert_eq!(&multiple.as_affine().xy, entry);
                multiple = match i {
                    1 => multiple.double(),
                    _ => multiple.add(&base),
                };
            }
            // A row of 2^(w - 1) multiples spans a w-bit window.
            let window = row.as_chunks::<8>().0.len().ilog2() + 1;
            base.double_inplace_n(window as usize);
        }
    }
}