clock_curve_math/field/

field_element.rs

//! FieldElement implementation.
//!
//! This module provides arithmetic operations in the finite field modulo p = 2^255 - 19,
//! which is the prime field used by the Curve25519 elliptic curve.
//!
//! # Field Parameters
//!
//! - **Prime modulus (p)**: 2^255 - 19
//! - **Field size**: ~2^255 elements
//! - **Representation**: Montgomery form for efficient multiplication
//!
//! # Security Properties
//!
//! All operations are designed to be constant-time to prevent timing-based
//! side-channel attacks. This includes arithmetic operations, comparisons,
//! and conditional operations.
//!
//! # Examples
//!
//! ```
//! use clock_curve_math::{FieldElement, FieldOps};
//!
//! // Create field elements
//! let a = FieldElement::from_u64(10);
//! let b = FieldElement::from_u64(20);
//!
//! // Perform arithmetic
//! let sum = a.add(&b);
//! let product = a.mul(&b);
//! let square = a.square();
//!
//! // Modular inverse
//! let inv_a = a.inv();
//! assert_eq!(a.mul(&inv_a), FieldElement::from_u64(1));
//!
//! // Conditional operations (constant-time)
//! let selected = FieldElement::conditional_select(&a, &b, 1); // selects a
//! let selected = FieldElement::conditional_select(&a, &b, 0); // selects b
//! ```

use crate::bigint::BigInt;
use crate::constants::P_LIMBS;
use crate::ct;
use crate::montgomery::{N_PRIME_P, montgomery_mul};

/// FieldElement represents an element of the field modulo p = 2^255 - 19.
///
/// Values are stored in Montgomery form for efficient multiplication.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct FieldElement {
    /// The value in Montgomery form
    inner: BigInt,
}

#[cfg(feature = "serde")]
impl serde::Serialize for FieldElement {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        // Serialize as bytes for canonical representation
        self.to_bytes().serialize(serializer)
    }
}

#[cfg(feature = "serde")]
impl<'de> serde::Deserialize<'de> for FieldElement {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        // Deserialize from bytes
        let bytes = <[u8; 32]>::deserialize(deserializer)?;
        Self::from_bytes(&bytes).map_err(serde::de::Error::custom)
    }
}

impl FieldElement {
    /// Create a FieldElement from bytes (canonical representation).
    ///
    /// The bytes must represent a value in the range [0, p). Values outside this
    /// range will result in an error.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::FieldElement;
    ///
    /// let bytes = [1u8; 32]; // Little-endian representation of a small number
    /// let element = FieldElement::from_bytes(&bytes).unwrap();
    /// assert_eq!(element.to_bytes(), bytes);
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`crate::error::MathError::InvalidBytes`] if the byte representation is not in [0, p).
    pub fn from_bytes(bytes: &[u8; 32]) -> Result<Self, crate::error::MathError> {
        let value = BigInt::from_bytes(bytes);

        // Check if value < p
        let p = BigInt::from_limbs(&P_LIMBS);
        if value.cmp(&p) != core::cmp::Ordering::Less {
            return Err(crate::error::MathError::InvalidBytes);
        }

        // Convert to Montgomery form
        let mont_value = crate::montgomery::to_montgomery_p(&value);

        Ok(Self { inner: mont_value })
    }

    /// Convert to bytes (canonical representation).
    ///
    /// Returns the canonical little-endian byte representation of the field element.
    /// The result is guaranteed to be in the range [0, p).
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::FieldElement;
    ///
    /// let element = FieldElement::from_u64(42);
    /// let bytes = element.to_bytes();
    /// let reconstructed = FieldElement::from_bytes(&bytes).unwrap();
    /// assert_eq!(element, reconstructed);
    /// ```
    pub fn to_bytes(&self) -> [u8; 32] {
        let value = crate::montgomery::from_montgomery_p(&self.inner);
        value.to_bytes()
    }

    /// Create a FieldElement from a u64 value.
    ///
    /// The value is automatically reduced modulo p if necessary.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::FieldElement;
    ///
    /// let zero = FieldElement::from_u64(0);
    /// let one = FieldElement::from_u64(1);
    /// let large = FieldElement::from_u64(u64::MAX); // Will be reduced mod p
    /// ```
    pub fn from_u64(value: u64) -> Self {
        let bigint = BigInt::from_u64(value);
        let mont_value = crate::montgomery::to_montgomery_p(&bigint);
        Self { inner: mont_value }
    }

    /// Create a FieldElement from a BigInt value with validation.
    ///
    /// The value must be in the range [0, p) where p is the field modulus.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, BigInt};
    ///
    /// let value = BigInt::from_u64(42);
    /// let element = FieldElement::from_bigint(&value).unwrap();
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`crate::error::MathError::InvalidFieldElement`] if the value is not in [0, p).
    pub fn from_bigint(value: &BigInt) -> Result<Self, crate::error::MathError> {
        crate::validation::validate_field_bigint(value)?;
        let mont_value = crate::montgomery::to_montgomery_p(value);
        Ok(Self { inner: mont_value })
    }

    /// Constant-time conditional selection.
    ///
    /// Returns `a` if `flag == 1`, `b` if `flag == 0`.
    /// Executes in constant time regardless of the flag value.
    ///
    /// # Safety
    ///
    /// `flag` should be either `0` or `1` for correct behavior.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::FieldElement;
    ///
    /// let a = FieldElement::from_u64(10);
    /// let b = FieldElement::from_u64(20);
    ///
    /// let selected = FieldElement::conditional_select(&a, &b, 1); // selects a
    /// assert_eq!(selected, a);
    ///
    /// let selected = FieldElement::conditional_select(&a, &b, 0); // selects b
    /// assert_eq!(selected, b);
    /// ```
    pub fn conditional_select(a: &Self, b: &Self, flag: u64) -> Self {
        let a_limbs = a.inner.limbs();
        let b_limbs = b.inner.limbs();
        let result_limbs = ct::ct_select_array(&a_limbs, &b_limbs, flag);
        Self {
            inner: BigInt::from_limbs(&result_limbs),
        }
    }

    /// Constant-time conditional swap.
    ///
    /// Swaps `a` and `b` if `flag == 1`, leaves them unchanged if `flag == 0`.
    /// Executes in constant time regardless of the flag value.
    ///
    /// # Safety
    ///
    /// `flag` should be either `0` or `1` for correct behavior.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::FieldElement;
    ///
    /// let mut a = FieldElement::from_u64(10);
    /// let mut b = FieldElement::from_u64(20);
    ///
    /// FieldElement::conditional_swap(&mut a, &mut b, 0);
    /// assert_eq!(a, FieldElement::from_u64(10)); // unchanged
    /// assert_eq!(b, FieldElement::from_u64(20)); // unchanged
    ///
    /// FieldElement::conditional_swap(&mut a, &mut b, 1);
    /// assert_eq!(a, FieldElement::from_u64(20)); // swapped
    /// assert_eq!(b, FieldElement::from_u64(10)); // swapped
    /// ```
    pub fn conditional_swap(a: &mut Self, b: &mut Self, flag: u64) {
        let mut a_limbs = a.inner.limbs();
        let mut b_limbs = b.inner.limbs();
        ct::ct_swap(&mut a_limbs, &mut b_limbs, flag);
        a.inner = BigInt::from_limbs(&a_limbs);
        b.inner = BigInt::from_limbs(&b_limbs);
    }

    /// Check if the value is valid (in range [0, p)).
    ///
    /// Returns true if the field element represents a value in [0, p).
    /// Field elements created through the public API are always valid.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::FieldElement;
    ///
    /// let element = FieldElement::from_u64(42);
    /// assert!(element.is_valid());
    /// ```
    pub fn is_valid(&self) -> bool {
        crate::field::helpers::is_valid_field(self)
    }

    /// Compute the additive inverse (negation).
    ///
    /// Returns `-self mod p`, which satisfies `self + (-self) ≡ 0 mod p`.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, FieldOps};
    ///
    /// let a = FieldElement::from_u64(5);
    /// let neg_a = a.neg();
    /// let sum = a.add(&neg_a);
    /// assert_eq!(sum, FieldElement::from_u64(0));
    /// ```
    pub fn neg(&self) -> Self {
        let zero = Self::from_u64(0);
        zero.sub(self)
    }

    /// Get the inner BigInt value (in Montgomery form).
    ///
    /// This is primarily used by internal helper functions.
    pub(crate) fn inner(&self) -> &BigInt {
        &self.inner
    }

    /// Generate a random field element.
    ///
    /// Uses the provided random number generator to create a uniformly random
    /// field element in the range [0, p).
    ///
    /// # Examples
    ///
    /// ```rust
    /// # #[cfg(feature = "rand")]
    /// use clock_curve_math::FieldElement;
    /// # #[cfg(feature = "rand")]
    /// use clock_rand::Rng;
    ///
    /// # #[cfg(feature = "rand")]
    /// # fn example() {
    /// let mut rng = clock_rand::Xoshiro256Plus::new(42);
    /// let random_element = FieldElement::random(&mut rng);
    /// # }
    /// ```
    ///
    /// # Security Notes
    ///
    /// Uses rejection sampling to ensure the generated value is always in the valid range [0, p).
    /// This may require multiple random draws in the worst case, but the probability of rejection
    /// is very low since p ≈ 2^255.
    #[cfg(feature = "rand")]
    pub fn random<R: clock_rand::Rng>(rng: &mut R) -> Self {
        loop {
            // Generate 32 random bytes
            let mut bytes = [0u8; 32];
            rng.fill_bytes(&mut bytes);

            // Try to create field element from bytes
            // Since p is very close to 2^255, most random 32-byte values will be >= p
            // We use rejection sampling to ensure we get a valid value
            if let Ok(element) = Self::from_bytes(&bytes) {
                return element;
            }
            // If from_bytes fails (value >= p), try again
        }
    }

    /// Generate a random non-zero field element.
    ///
    /// Uses the provided random number generator to create a uniformly random
    /// field element in the range [1, p).
    ///
    /// # Examples
    ///
    /// ```rust
    /// # #[cfg(feature = "rand")]
    /// use clock_curve_math::FieldElement;
    /// # #[cfg(feature = "rand")]
    /// use clock_rand::Xoshiro256Plus;
    ///
    /// # #[cfg(feature = "rand")]
    /// # fn example() {
    /// let mut rng = clock_rand::Xoshiro256Plus::new(42);
    /// let random_element = FieldElement::random_nonzero(&mut rng);
    /// assert_ne!(random_element, FieldElement::from_u64(0));
    /// # }
    /// ```
    #[cfg(feature = "rand")]
    pub fn random_nonzero<R: clock_rand::Rng>(rng: &mut R) -> Self {
        loop {
            let element = Self::random(rng);
            if !element.is_zero() {
                return element;
            }
        }
    }

    /// Check if this field element is zero.
    pub fn is_zero(&self) -> bool {
        // Convert from Montgomery form and check if zero
        let value = crate::montgomery::from_montgomery_p(&self.inner);
        value.is_zero()
    }
}

/// Trait for field element operations.
///
/// This trait defines the arithmetic operations available on field elements.
/// All operations are constant-time and automatically reduce their results
/// modulo the field prime p = 2^255 - 19.
pub trait FieldOps {
    /// Modular addition.
    ///
    /// Computes `(self + rhs) mod p` in constant time.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, FieldOps};
    ///
    /// let a = FieldElement::from_u64(10);
    /// let b = FieldElement::from_u64(20);
    /// let sum = a.add(&b);
    /// assert_eq!(sum, FieldElement::from_u64(30));
    /// ```
    fn add(&self, rhs: &Self) -> Self;

    /// Modular subtraction.
    ///
    /// Computes `(self - rhs) mod p` in constant time.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, FieldOps};
    ///
    /// let a = FieldElement::from_u64(20);
    /// let b = FieldElement::from_u64(10);
    /// let diff = a.sub(&b);
    /// assert_eq!(diff, FieldElement::from_u64(10));
    /// ```
    fn sub(&self, rhs: &Self) -> Self;

    /// Montgomery multiplication.
    ///
    /// Computes `(self * rhs) mod p` using Montgomery arithmetic for efficiency.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, FieldOps};
    ///
    /// let a = FieldElement::from_u64(10);
    /// let b = FieldElement::from_u64(20);
    /// let product = a.mul(&b);
    /// assert_eq!(product, FieldElement::from_u64(200));
    /// ```
    fn mul(&self, rhs: &Self) -> Self;

    /// Squaring (optimized).
    ///
    /// Computes `(self * self) mod p`. This is typically faster than general multiplication.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, FieldOps};
    ///
    /// let a = FieldElement::from_u64(10);
    /// let square = a.square();
    /// assert_eq!(square, FieldElement::from_u64(100));
    /// ```
    fn square(&self) -> Self;

    /// Constant-time modular inverse.
    ///
    /// Computes the modular inverse of `self` modulo p using Fermat's Little Theorem.
    /// The result satisfies `(self * inv) ≡ 1 mod p`.
    ///
    /// # Panics
    ///
    /// Panics if `self` is zero (which has no multiplicative inverse).
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, FieldOps};
    ///
    /// let a = FieldElement::from_u64(5);
    /// let inv = a.inv();
    /// let product = a.mul(&inv);
    /// assert_eq!(product, FieldElement::from_u64(1));
    /// ```
    fn inv(&self) -> Self;

    /// Modular exponentiation.
    ///
    /// Computes `(self ^ exp) mod p` using constant-time exponentiation by squaring.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, BigInt, FieldOps};
    ///
    /// let base = FieldElement::from_u64(2);
    /// let exp = BigInt::from_u64(10);
    /// let result = base.pow(&exp);
    /// assert_eq!(result, FieldElement::from_u64(1024)); // 2^10 = 1024
    /// ```
    fn pow(&self, exp: &BigInt) -> Self;

    /// Modular exponentiation with input validation.
    ///
    /// Computes `(self ^ exp) mod p` using constant-time exponentiation by squaring.
    /// Validates that the exponent is non-negative.
    ///
    /// # Examples
    ///
    /// ```
    /// use clock_curve_math::{FieldElement, BigInt, FieldOps};
    ///
    /// let base = FieldElement::from_u64(2);
    /// let exp = BigInt::from_u64(10);
    /// let result = base.pow_checked(&exp).unwrap();
    /// assert_eq!(result, FieldElement::from_u64(1024)); // 2^10 = 1024
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`crate::error::MathError::InvalidExponent`] if the exponent is negative.
    fn pow_checked(&self, exp: &BigInt) -> Result<Self, crate::error::MathError>
    where
        Self: Sized;
}

impl FieldOps for FieldElement {
    fn add(&self, rhs: &Self) -> Self {
        let p = BigInt::from_limbs(&P_LIMBS);
        let sum = self.inner.add(&rhs.inner);

        // Constant-time reduction: subtract p, then add it back if the result would be negative
        let diff = sum.sub(&p);
        let sign_bit = (diff.limbs()[3] >> 63) & 1;
        let needs_carry = sign_bit; // Add p back if result would be negative

        let mask = ct::ct_mask(needs_carry);
        let p_masked = BigInt::from_limbs(&[
            P_LIMBS[0] & mask,
            P_LIMBS[1] & mask,
            P_LIMBS[2] & mask,
            P_LIMBS[3] & mask,
        ]);
        let result = diff.add(&p_masked);

        Self { inner: result }
    }

    fn sub(&self, rhs: &Self) -> Self {
        let _p = BigInt::from_limbs(&P_LIMBS);
        let diff = self.inner.sub(&rhs.inner);

        // Constant-time correction: add p if diff is negative (underflow)
        let is_negative = ct::ct_is_zero(diff.limbs()[3] >> 63) ^ 1; // 1 if MSB is set (negative)

        let mask = ct::ct_mask(is_negative);
        let p_masked = BigInt::from_limbs(&[
            P_LIMBS[0] & mask,
            P_LIMBS[1] & mask,
            P_LIMBS[2] & mask,
            P_LIMBS[3] & mask,
        ]);
        let result = diff.add(&p_masked);

        Self { inner: result }
    }

    fn mul(&self, rhs: &Self) -> Self {
        let p = BigInt::from_limbs(&P_LIMBS);
        let n_prime = BigInt::from_limbs(&N_PRIME_P);
        let result = montgomery_mul(&self.inner, &rhs.inner, &p, &n_prime);
        Self { inner: result }
    }

    fn square(&self) -> Self {
        // For now, use the same multiplication. In the future, we could optimize
        // Montgomery squaring specifically, but the current montgomery_mul
        // is already quite efficient.
        self.mul(self)
    }

    fn inv(&self) -> Self {
        Self {
            inner: crate::field::helpers::field_inv(self),
        }
    }

    fn pow(&self, exp: &BigInt) -> Self {
        Self {
            inner: crate::field::helpers::field_pow(self, exp),
        }
    }

    fn pow_checked(&self, exp: &BigInt) -> Result<Self, crate::error::MathError> {
        crate::validation::validate_exponent(exp)?;
        Ok(Self {
            inner: crate::field::helpers::field_pow(self, exp),
        })
    }
}

impl Default for FieldElement {
    fn default() -> Self {
        Self::from_u64(0)
    }
}