dstu-core 0.3.8

//! Scalar (mod `n`) integer arithmetic for DSTU 4145 signing - the curve's group order
//! (`curve163::order()`), unrelated to `gf2m163::FieldElement`'s `GF(2^163)` polynomial
//! arithmetic. Kept as a **distinct type** specifically so the two can never be mixed up by
//! accident: both are 3-limb `[u64; 3]` internally, but `FieldElement::add` is XOR and
//! `FieldElement::multiply` is carryless, while `Scalar::add`/`Scalar::multiply` are ordinary
//! carrying integer arithmetic reduced mod `n` (`docs/DECISIONS.md` D-25's follow-up note - this was
//! flagged as the layer's single biggest silent-correctness risk).
//!
//! Both operations are branchless throughout: `Scalar` carries the private key `d` and the
//! ephemeral nonce `e` during signing, both secret. Reduction mod `n` uses a fixed-iteration
//! restoring-division pass (double-and-conditionally-subtract, one pass per product bit, always
//! run in full) rather than Barrett or any early-exit scheme - correctness-first, same posture as
//! `gf2m163`'s field reduction.

use super::curve163;
use zeroize::Zeroize;

// Not `ZeroizeOnDrop`: `Scalar` is `Copy` and used by-value pervasively (arithmetic ops, hazmat
// `sign`/`verify` signatures) - `ZeroizeOnDrop`'s `Drop` impl is incompatible with `Copy` (E0184).
// Callers holding a `Scalar` they want zeroized on drop (e.g. `crypto_sign::SigningKey`) call
// `.zeroize()` explicitly instead.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Zeroize)]
pub struct Scalar([u64; 3]);

impl Scalar {
    /// Builds a scalar from a big-endian byte slice (up to 21 bytes). The caller must ensure the
    /// value is already less than `n` - this does not reduce (same convention as
    /// `FieldElement::from_be_bytes`).
    #[must_use]
    pub fn from_be_bytes(bytes: &[u8]) -> Self {
        Scalar(limbs_from_be_bytes(bytes))
    }

    #[must_use]
    #[allow(clippy::cast_possible_truncation)] // deliberate: extracting one byte from a shifted limb
    pub fn to_be_bytes(self) -> [u8; 21] {
        let mut out = [0u8; 21];
        for (i, byte) in out.iter_mut().rev().enumerate() {
            let limb = i / 8;
            let shift = (i % 8) * 8;
            *byte = (self.0[limb] >> shift) as u8;
        }
        out
    }

    #[must_use]
    pub fn is_zero(self) -> bool {
        self.0 == [0, 0, 0]
    }

    fn n() -> [u64; 3] {
        limbs_from_be_bytes(&curve163::order())
    }

    /// Builds a scalar from a big-endian 21-byte candidate, but only if it lies in `[1, n)` - the
    /// valid private-key range. Used by `crypto_sign::SigningKey::generate`'s rejection-sampling
    /// loop (`docs/TASKS.md` T-122): the comparison against `n` goes through the same constant-time
    /// subtract-and-select primitive (`sub3`'s borrow flag) the rest of this module already uses
    /// for secret arithmetic, rather than a branching `>=`, so evaluating one candidate doesn't
    /// add a data-dependent-branch timing signal beyond the "how many draws until one was
    /// accepted" every rejection-sampling scheme inherently has.
    ///
    /// Gated the same way its only caller (`crypto_sign::SigningKey::generate`) is: needs
    /// `crate::randombytes` to draw candidates in the first place (`std` or the narrower
    /// `getrandom` feature, `docs/TASKS.md` T-123/`docs/DECISIONS.md` D-74) - a build with neither has no way
    /// to call this, so it would otherwise be dead code there.
    #[cfg(any(feature = "std", feature = "getrandom"))]
    #[must_use]
    pub(crate) fn from_candidate_bytes(bytes: &[u8; 21]) -> Option<Self> {
        let limbs = limbs_from_be_bytes(bytes);
        let (_, borrow) = sub3(limbs, Self::n());
        let in_range = borrow == 1; // borrow == 1 <=> limbs < n
        let nonzero = limbs != [0, 0, 0];
        (in_range && nonzero).then_some(Scalar(limbs))
    }

    #[must_use]
    pub fn multiply(self, other: Self) -> Self {
        Scalar(reduce_mod_n(mul3(self.0, other.0)))
    }

    /// Reduces an arbitrary-length big-endian byte string mod `n`, via the same bit-serial
    /// restoring reduction as `reduce_mod_n` (constant-time, always processes every input bit
    /// regardless of value) - used by `crypto_sign`'s deterministic nonce derivation to fold a
    /// wider KMAC output (32+ bytes) into a valid scalar, the same role `reduce_mod_n` plays for a
    /// multiplication product.
    #[must_use]
    pub(crate) fn reduce_wide_bytes(bytes: &[u8]) -> Self {
        let n = Self::n();
        let mut r = [0u64; 3];
        for &byte in bytes {
            for bit in (0..8).rev() {
                let bit_val = u64::from((byte >> bit) & 1);
                r = shl1_or(r, bit_val);
                r = cond_sub_if_ge(r, n);
            }
        }
        Scalar(r)
    }
}

impl core::ops::Add for Scalar {
    type Output = Self;

    /// Ordinary integer addition mod `n` (not XOR - see the module doc).
    fn add(self, other: Self) -> Self {
        let (sum, _carry) = add3(self.0, other.0);
        Scalar(cond_sub_if_ge(sum, Self::n()))
    }
}

fn limbs_from_be_bytes(bytes: &[u8]) -> [u64; 3] {
    let mut limbs = [0u64; 3];
    for (i, &byte) in bytes.iter().rev().enumerate() {
        let limb = i / 8;
        let shift = (i % 8) * 8;
        limbs[limb] |= u64::from(byte) << shift;
    }
    limbs
}

/// 3-limb add with carry-out.
fn add3(a: [u64; 3], b: [u64; 3]) -> ([u64; 3], u64) {
    let mut out = [0u64; 3];
    let mut carry = 0u64;
    for i in 0..3 {
        let (s1, c1) = a[i].overflowing_add(b[i]);
        let (s2, c2) = s1.overflowing_add(carry);
        out[i] = s2;
        carry = u64::from(c1) + u64::from(c2);
    }
    (out, carry)
}

/// 3-limb subtract with borrow-out (`1` if `a < b`).
fn sub3(a: [u64; 3], b: [u64; 3]) -> ([u64; 3], u64) {
    let mut out = [0u64; 3];
    let mut borrow = 0u64;
    for i in 0..3 {
        let (d1, b1) = a[i].overflowing_sub(b[i]);
        let (d2, b2) = d1.overflowing_sub(borrow);
        out[i] = d2;
        borrow = u64::from(b1) + u64::from(b2);
    }
    (out, borrow)
}

/// Returns `a - b` if `a >= b`, otherwise `a` unchanged - via a constant-time select on the
/// subtraction's borrow flag (`borrow == 0` means `a >= b`), never a branch on the comparison.
fn cond_sub_if_ge(a: [u64; 3], b: [u64; 3]) -> [u64; 3] {
    let (diff, borrow) = sub3(a, b);
    let mask = borrow.wrapping_sub(1); // borrow == 0 (a >= b) -> all-ones; borrow == 1 -> all-zeros
    let mut out = [0u64; 3];
    for i in 0..3 {
        out[i] = a[i] ^ (mask & (a[i] ^ diff[i]));
    }
    out
}

/// 3-limb by 3-limb schoolbook multiplication into 6 limbs (real carrying arithmetic, unlike
/// `gf2m163`'s carryless `poly_mul_wide`).
#[allow(clippy::cast_possible_truncation)] // deliberate: low 64 bits of a u128 partial product
fn mul3(a: [u64; 3], b: [u64; 3]) -> [u64; 6] {
    let mut out = [0u64; 6];
    for i in 0..3 {
        let mut carry = 0u128;
        for j in 0..3 {
            let product = u128::from(a[i]) * u128::from(b[j]) + u128::from(out[i + j]) + carry;
            out[i + j] = product as u64;
            carry = product >> 64;
        }
        out[i + 3] = carry as u64;
    }
    out
}

/// Reduces a 6-limb product mod `n` via restoring division: process every bit of `product` from
/// the most significant down, doubling the running remainder and folding in each bit, then always
/// running the conditional subtract - the same fixed number of passes (`6 * 64`) regardless of
/// `product`'s actual value.
fn reduce_mod_n(product: [u64; 6]) -> [u64; 3] {
    let n = Scalar::n();
    let mut r = [0u64; 3];
    for limb_idx in (0..6).rev() {
        for bit in (0..64).rev() {
            let bit_val = (product[limb_idx] >> bit) & 1;
            r = shl1_or(r, bit_val);
            r = cond_sub_if_ge(r, n);
        }
    }
    r
}

/// Left-shifts a 3-limb value by 1 bit, OR-ing `bit` into the vacated low bit.
fn shl1_or(x: [u64; 3], bit: u64) -> [u64; 3] {
    let mut out = [0u64; 3];
    let mut carry = bit;
    for i in 0..3 {
        let next_carry = x[i] >> 63;
        out[i] = (x[i] << 1) | carry;
        carry = next_carry;
    }
    out
}

#[cfg(all(test, any(feature = "std", feature = "getrandom")))]
mod from_candidate_bytes_tests {
    use super::{curve163, Scalar};

    #[test]
    fn rejects_zero() {
        assert!(Scalar::from_candidate_bytes(&[0u8; 21]).is_none());
    }

    #[test]
    fn rejects_n_itself() {
        assert!(Scalar::from_candidate_bytes(&curve163::order()).is_none());
    }

    #[test]
    fn rejects_above_n() {
        let mut above_n = curve163::order();
        above_n[20] += 1; // n's low byte is 0x4D, room to increment without carrying
        assert!(Scalar::from_candidate_bytes(&above_n).is_none());
    }

    #[test]
    fn accepts_n_minus_one() {
        let mut n_minus_one = curve163::order();
        n_minus_one[20] -= 1;
        let scalar = Scalar::from_candidate_bytes(&n_minus_one).expect("n - 1 is in [1, n)");
        assert_eq!(scalar.to_be_bytes(), n_minus_one);
    }

    #[test]
    fn accepts_one() {
        let mut one = [0u8; 21];
        one[20] = 1;
        let scalar = Scalar::from_candidate_bytes(&one).expect("1 is in [1, n)");
        assert_eq!(scalar.to_be_bytes(), one);
    }
}