clock_curve_math/bigint/

arithmetic.rs

//! BigInt arithmetic operations trait for multi-precision integer mathematics.
//!
//! This module defines the core arithmetic operations for big integers (multi-precision
//! integers) used throughout the cryptographic library. BigInt operations are fundamental
//! to all cryptographic computations, providing the mathematical foundation for modular
//! arithmetic, elliptic curve operations, and cryptographic protocols.
//!
//! # Multi-Precision Arithmetic
//!
//! BigInt represents integers that exceed the range of standard machine word sizes
//! (typically 64 bits). Operations are implemented using:
//!
//! - **Limb-based representation**: Numbers stored as arrays of 64-bit limbs
//! - **Little-endian ordering**: Least significant limb at index 0
//! - **Fixed precision**: Operations assume consistent limb counts
//! - **Constant-time execution**: All operations execute in time independent of values
//!
//! # Security Critical Operations
//!
//! All BigInt operations are designed with cryptographic security in mind:
//!
//! - **Constant-time execution**: Prevents timing-based side-channel attacks
//! - **No data-dependent branches**: Eliminates cache timing vulnerabilities
//! - **Predictable memory access**: Prevents cache-based information leakage
//! - **Secure comparisons**: Constant-time equality and ordering checks
//!
//! # Performance Characteristics
//!
//! BigInt operations have different computational complexities:
//!
//! - **Addition/Subtraction**: O(n) where n is limb count
//! - **Multiplication**: O(n²) for standard multiplication
//! - **Wide multiplication**: O(n²) producing double-width results
//! - **Shifts**: O(n) with bit-wise operations
//! - **Comparisons**: O(n) with constant-time properties
//!
//! # Usage in Cryptographic Contexts
//!
//! BigInt arithmetic serves as the foundation for higher-level cryptographic operations:
//!
//! ```ignore
//! use clock_curve_math::bigint::{BigInt, BigIntOps};
//!
//! // Modular arithmetic for Diffie-Hellman
//! let base = BigInt::from_hex("2");
//! let exponent = BigInt::from_hex("123456789ABCDEF");
//! let modulus = BigInt::from_hex("FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD...");
//!
//! // Compute base^exponent mod modulus (constant-time)
//! let result = mod_pow(&base, &exponent, &modulus);
//!
//! // Elliptic curve point operations
//! let x1 = BigInt::from_hex("123...");
//! let y1 = BigInt::from_hex("456...");
//! let x2 = BigInt::from_hex("789...");
//! let y2 = BigInt::from_hex("ABC...");
//!
//! // Point addition uses BigInt arithmetic extensively
//! let (x3, y3) = point_add(&x1, &y1, &x2, &y2, &curve_modulus);
//! ```
//!
//! # Implementation Considerations
//!
//! ## Constant-Time Requirements
//!
//! Cryptographic operations require constant-time execution to prevent:
//!
//! - **Timing attacks**: Measuring execution time to infer secret keys
//! - **Cache attacks**: Observing which memory locations are accessed
//! - **Branch prediction attacks**: Analyzing control flow patterns
//!
//! ## Error Handling
//!
//! BigInt operations generally don't fail, but some considerations:
//!
//! - **Overflow**: Wide operations return double-width results to prevent overflow
//! - **Invalid inputs**: Functions assume valid BigInt instances
//! - **Memory safety**: All operations are memory-safe with bounds checking
//!
//! ## Optimization Opportunities
//!
//! The implementation provides optimization hooks:
//!
//! - **SIMD acceleration**: Potential for vectorized limb operations
//! - **Hardware acceleration**: Integration with CPU carry chains
//! - **Montgomery arithmetic**: Optimized modular operations
//! - **Algorithm selection**: Different multiplication algorithms based on size

use core::cmp::Ordering;

use super::BigInt;

/// Core trait for big integer arithmetic operations with cryptographic security guarantees.
///
/// This trait defines the essential arithmetic operations for multi-precision integers
/// used in cryptographic computations. All operations are required to execute in
/// constant time to prevent timing-based side-channel attacks that could compromise
/// cryptographic security.
///
/// # Security Requirements
///
/// All implementing types must ensure:
/// - **Constant-time execution**: Operation time independent of input values
/// - **No data-dependent branches**: Control flow doesn't depend on secret data
/// - **Predictable memory access**: Memory access patterns are consistent
/// - **Secure comparisons**: Comparison operations don't leak timing information
///
/// # Implementation Contract
///
/// Implementations must:
/// - Handle all edge cases (zero, maximum values, overflow conditions)
/// - Maintain constant-time properties across all input ranges
/// - Provide correct mathematical results for all operations
/// - Document any performance characteristics or limitations
///
/// # Usage in Cryptographic Libraries
///
/// ```ignore
/// use clock_curve_math::bigint::{BigInt, BigIntOps};
///
/// fn secure_modular_multiplication(a: &BigInt, b: &BigInt, modulus: &BigInt) -> BigInt {
///     // Use wide multiplication to prevent overflow
///     let (low, high) = a.mul_wide(b);
///
///     // Perform modular reduction (simplified example)
///     let mut result = low;
///     while result.ct_cmp(modulus) != core::cmp::Ordering::Less {
///         result = result.sub(modulus);
///     }
///
///     result
/// }
///
/// fn constant_time_conditional_swap(a: &mut BigInt, b: &mut BigInt, condition: u64) {
///     // Secure conditional swap without branching
///     let temp = a.clone();
///     *a = BigInt::ct_select(a, b, condition);
///     *b = BigInt::ct_select(b, &temp, condition);
/// }
/// ```
///
/// # Performance Expectations
///
/// Implementations should optimize for cryptographic use cases:
/// - Fast constant-time operations
/// - Efficient limb-based arithmetic
/// - Minimal memory allocations
/// - Good cache locality
pub trait BigIntOps {
    /// Performs constant-time addition of two big integers.
    ///
    /// Computes `self + rhs` with full carry propagation. The operation
    /// executes in constant time regardless of input values or carry patterns,
    /// preventing timing attacks that could leak information about the operands.
    ///
    /// # Mathematical Properties
    /// - **Commutative**: `a + b = b + a`
    /// - **Associative**: `(a + b) + c = a + (b + c)`
    /// - **Identity**: `a + 0 = a`
    /// - **Overflow**: No overflow occurs (arbitrary precision)
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents carry-based timing attacks
    /// - No information leaks through execution time variations
    /// - Safe for cryptographic use with secret operands
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs.
    fn add(&self, rhs: &Self) -> Self;

    /// Performs constant-time subtraction of two big integers.
    ///
    /// Computes `self - rhs` with borrow propagation. The operation maintains
    /// constant-time execution even when borrowing occurs, preventing timing
    /// attacks that could reveal information about relative magnitudes.
    ///
    /// # Mathematical Properties
    /// - **Anti-commutative**: `a - b = -(b - a)`
    /// - **Non-associative**: Subtraction is not associative
    /// - **Identity**: `a - 0 = a`
    /// - **Inverse**: `a - a = 0`
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents borrow-based timing attacks
    /// - No timing leaks when `rhs > self` (produces negative result)
    /// - Safe for cryptographic comparisons and reductions
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs.
    fn sub(&self, rhs: &Self) -> Self;

    /// Performs constant-time multiplication of two big integers.
    ///
    /// Computes `self * rhs` using efficient multi-precision multiplication.
    /// The result may require modular reduction for cryptographic applications.
    ///
    /// # Implementation Notes
    /// This method may produce a result that overflows the standard BigInt
    /// representation. For cryptographic modular arithmetic, consider using
    /// `mul_wide()` followed by modular reduction to handle overflow correctly.
    ///
    /// # Mathematical Properties
    /// - **Commutative**: `a * b = b * a`
    /// - **Associative**: `(a * b) * c = a * (b * c)`
    /// - **Distributive**: `a * (b + c) = a*b + a*c`
    /// - **Identity**: `a * 1 = a`
    /// - **Zero**: `a * 0 = 0`
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents timing attacks on multiplication
    /// - No leaks through partial product computation timing
    /// - Safe for cryptographic use with secret multiplicands
    ///
    /// # Performance
    /// O(n²) time complexity for standard multiplication where n is limb count.
    /// Consider using specialized algorithms for large operands.
    ///
    /// # Warning
    /// The result may be double-width. Use `mul_wide()` for guaranteed
    /// overflow handling in cryptographic applications.
    fn mul(&self, rhs: &Self) -> Self;

    /// Performs wide multiplication returning the full double-width result.
    ///
    /// Computes `self * rhs` and returns the result as two BigInts representing
    /// the low and high parts of the full product. This prevents overflow and
    /// enables correct modular reduction for cryptographic applications.
    ///
    /// # Return Value
    /// Returns a tuple `(low, high)` where:
    /// - `low`: Lower 256 bits (or equivalent) of the product
    /// - `high`: Upper 256 bits (or equivalent) of the product
    /// - The full product is `high * 2^(limb_count * 64) + low`
    ///
    /// # Use Cases
    /// - **Montgomery reduction**: Requires full product before modular reduction
    /// - **Barrett reduction**: Needs high bits for approximation
    /// - **Modular exponentiation**: Prevents intermediate overflow
    /// - **Large integer arithmetic**: Exact computation without precision loss
    ///
    /// # Security Considerations
    /// - Constant-time execution for both operands
    /// - No timing leaks during carry propagation
    /// - Safe for cryptographic modular arithmetic
    ///
    /// # Performance
    /// O(n²) time complexity where n is the number of limbs.
    /// More expensive than regular multiplication but prevents overflow issues.
    fn mul_wide(&self, rhs: &Self) -> (Self, Self)
    where
        Self: Sized;

    /// Performs wide squaring returning the full double-width result.
    ///
    /// Computes `self * self` (squaring) and returns the result as two BigInts
    /// representing the low and high parts. This is optimized compared to
    /// `mul_wide(self, self)` by exploiting the symmetry of squaring.
    ///
    /// # Optimization Details
    /// Squaring benefits from symmetry: each pair `(a[i], a[j])` where `i ≠ j`
    /// contributes `2 * a[i] * a[j]` to the product, which can be computed more
    /// efficiently than general multiplication. Diagonal terms `a[i] * a[i]`
    /// are computed normally.
    ///
    /// # Return Value
    /// Returns a tuple `(low, high)` where:
    /// - `low`: Lower bits of the squared result
    /// - `high`: Upper bits of the squared result
    /// - The full square is `high * 2^(limb_count * 64) + low`
    ///
    /// # Use Cases
    /// - **Montgomery squaring**: Optimized modular squaring in ECC
    /// - **Exponentiation**: Squaring step in exponentiation algorithms
    /// - **Field arithmetic**: Squaring in finite field operations
    /// - **Performance-critical code**: Faster than general multiplication
    ///
    /// # Security Considerations
    /// - Constant-time execution maintains security properties
    /// - No optimization leaks timing information about the operand
    /// - Safe for cryptographic use with secret values
    ///
    /// # Performance
    /// Typically 25-50% faster than `mul_wide(self, self)` due to symmetry optimization.
    /// O(n²) time complexity but with lower constant factors for squaring.
    fn square_wide(&self) -> (Self, Self)
    where
        Self: Sized;

    /// Performs constant-time left shift (multiplication by power of 2).
    ///
    /// Shifts the BigInt left by the specified number of bits, effectively
    /// multiplying by `2^bits`. The operation maintains constant-time execution
    /// regardless of the shift amount or the bit pattern of the operand.
    ///
    /// # Parameters
    /// * `bits` - Number of bits to shift left (0 ≤ bits ≤ maximum bit length)
    ///
    /// # Mathematical Properties
    /// - **Identity**: `x << 0 = x`
    /// - **Additive**: `(x << a) << b = x << (a + b)`
    /// - **Multiplicative**: `x << n = x * 2^n`
    /// - **Associative**: `(x + y) << n = (x << n) + (y << n)`
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents shift-based timing attacks
    /// - No leaks through shift amount processing
    /// - Safe for cryptographic bit manipulation with secret shift amounts
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs affected by the shift.
    fn shl(&self, bits: u32) -> Self;

    /// Performs constant-time right shift (division by power of 2).
    ///
    /// Shifts the BigInt right by the specified number of bits, effectively
    /// performing floor division by `2^bits`. The operation executes in
    /// constant time regardless of shift amount or operand values.
    ///
    /// # Parameters
    /// * `bits` - Number of bits to shift right (0 ≤ bits ≤ maximum bit length)
    ///
    /// # Mathematical Properties
    /// - **Identity**: `x >> 0 = x`
    /// - **Additive**: `(x >> a) >> b = x >> (a + b)`
    /// - **Divisive**: `x >> n = floor(x / 2^n)`
    /// - **Rounding**: Always rounds toward zero (floor division)
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents shift-based timing attacks
    /// - No information leaks through shift processing
    /// - Safe for cryptographic bit extraction with secret shift amounts
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs affected by the shift.
    fn shr(&self, bits: u32) -> Self;

    /// Performs standard comparison with potential timing side-channels.
    ///
    /// Compares two BigInts and returns their ordering relationship.
    /// **Warning**: This comparison may leak timing information and should
    /// not be used with secret values in cryptographic contexts.
    ///
    /// # Return Value
    /// - `Ordering::Less` if `self < rhs`
    /// - `Ordering::Equal` if `self == rhs`
    /// - `Ordering::Greater` if `self > rhs`
    ///
    /// # Security Warning
    /// This method may execute in variable time depending on the input values,
    /// potentially leaking information about the operands through timing
    /// side-channels. Use `ct_cmp()` for cryptographic applications.
    ///
    /// # Performance
    /// May short-circuit on first difference, leading to variable execution time.
    fn cmp(&self, rhs: &Self) -> Ordering;

    /// Performs constant-time comparison that prevents timing side-channels.
    ///
    /// Compares two BigInts and returns their ordering relationship while
    /// executing in constant time regardless of the input values. This prevents
    /// timing-based attacks that could recover information about secret operands.
    ///
    /// # Security Properties
    /// - **Constant-time execution**: Time independent of operand values
    /// - **No data-dependent branches**: Control flow doesn't depend on secrets
    /// - **Leak-resistant**: Prevents timing attacks on comparisons
    /// - **Cryptographically secure**: Safe for use with secret values
    ///
    /// # Return Value
    /// - `Ordering::Less` if `self < rhs`
    /// - `Ordering::Equal` if `self == rhs`
    /// - `Ordering::Greater` if `self > rhs`
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs, with no short-circuiting.
    /// Slightly slower than `cmp()` but cryptographically secure.
    ///
    /// # Use Cases
    /// - Comparing cryptographic keys or intermediate values
    /// - Sorting operations on secret data
    /// - Conditional logic based on secret comparisons
    /// - Any comparison involving cryptographic secrets
    fn ct_cmp(&self, rhs: &Self) -> Ordering;

    /// Performs constant-time conditional selection between two BigInts.
    ///
    /// Returns `a` if `flag == 0`, `b` if `flag == 1`. This operation is
    /// fundamental for implementing constant-time conditional logic without
    /// branching, which is essential for preventing timing side-channels.
    ///
    /// # Algorithm
    /// Uses bitwise masking to select values without conditional execution:
    /// ```text
    /// result[i] = (a[i] & ~mask) | (b[i] & mask)
    /// where mask = 0xFFFF_FFFF_FFFF_FFFF if flag == 1, else 0
    /// ```
    ///
    /// # Security Properties
    /// - **Constant-time**: Execution time independent of flag value or operands
    /// - **Branch-free**: No conditional jumps that could create timing variations
    /// - **Leak-proof**: No information leaks through selection process
    /// - **Data-independent**: Memory access patterns are consistent
    ///
    /// # Parameters
    /// * `a` - Value selected when `flag == 0`
    /// * `b` - Value selected when `flag == 1`
    /// * `flag` - Selection flag (must be 0 or 1)
    ///
    /// # Safety
    /// `flag` must be either `0` or `1`. Other values may leak timing information
    /// through the underlying mask generation. Always ensure flag is properly
    /// sanitized before use.
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs.
    /// More expensive than simple assignment but cryptographically secure.
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::{BigInt, BigIntOps};
    ///
    /// let secret_a = BigInt::from_u64(42);
    /// let secret_b = BigInt::from_u64(123);
    /// let condition = 1u64; // Some boolean condition (0 or 1)
    ///
    /// // Secure conditional assignment
    /// let result = BigInt::ct_select(&secret_a, &secret_b, condition);
    /// ```
    fn ct_select(a: &Self, b: &Self, flag: u64) -> Self
    where
        Self: Sized;

    /// Checks whether the BigInt represents zero in constant time.
    ///
    /// Returns `true` if all bits are zero, `false` otherwise. The operation
    /// executes in constant time regardless of the value, preventing timing
    /// attacks that could leak information about whether a secret value is zero.
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents zero-testing attacks
    /// - No leaks through early exit or short-circuiting
    /// - Safe for cryptographic use with secret values
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs.
    /// Checks all limbs even if an early zero is found.
    fn is_zero(&self) -> bool;

    /// Extracts a specific bit from the BigInt in constant time.
    ///
    /// Returns 1 if the bit at the specified position is set, 0 otherwise.
    /// Bit positions start from 0 (least significant bit). The operation
    /// executes in constant time regardless of the bit position or value.
    ///
    /// # Parameters
    /// * `bit_position` - The bit position to extract (0 = LSB)
    ///
    /// # Return Value
    /// - `1` if the bit is set
    /// - `0` if the bit is clear
    ///
    /// # Security Considerations
    /// - Constant-time execution prevents bit extraction timing attacks
    /// - No leaks through array indexing or limb access patterns
    /// - Safe for cryptographic bit manipulation with secret positions
    ///
    /// # Performance
    /// O(1) time complexity - direct limb and bit access.
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::{BigInt, BigIntOps};
    ///
    /// let value = BigInt::from_u64(0b1010); // Binary: 1010
    /// assert_eq!(value.get_bit(0), 0); // LSB is 0
    /// assert_eq!(value.get_bit(1), 1); // Bit 1 is set
    /// assert_eq!(value.get_bit(2), 0); // Bit 2 is clear
    /// assert_eq!(value.get_bit(3), 1); // Bit 3 is set
    /// ```
    fn get_bit(&self, bit_position: u32) -> u64;

    /// Computes the minimum number of bits needed to represent the BigInt.
    ///
    /// Returns the position of the highest set bit plus one. Returns 0 for zero.
    /// This is equivalent to `floor(log2(value)) + 1` for non-zero values.
    ///
    /// # Return Value
    /// - `0` if the BigInt is zero
    /// - `floor(log2(abs(value))) + 1` otherwise
    ///
    /// # Mathematical Properties
    /// - **Zero case**: `bit_length(0) = 0`
    /// - **Power of 2**: `bit_length(2^k) = k + 1`
    /// - **Range**: For value v, `2^(length-1) ≤ v < 2^length`
    ///
    /// # Performance
    /// O(n) time complexity where n is the number of limbs.
    /// May short-circuit when the highest limb is found.
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::{BigInt, BigIntOps};
    ///
    /// assert_eq!(BigInt::from_u64(0).bit_length(), 0);
    /// assert_eq!(BigInt::from_u64(1).bit_length(), 1);     // 2^0
    /// assert_eq!(BigInt::from_u64(2).bit_length(), 2);     // 2^1
    /// assert_eq!(BigInt::from_u64(3).bit_length(), 2);     // Between 2^1 and 2^2
    /// assert_eq!(BigInt::from_u64(4).bit_length(), 3);     // 2^2
    /// ```
    fn bit_length(&self) -> u32;
}

/// Implementation of BigIntOps for the BigInt type.
///
/// This implementation provides constant-time multi-precision arithmetic
/// operations for cryptographic applications. All operations delegate to
/// the underlying BigInt implementation while ensuring constant-time properties.
///
/// # Security Guarantees
/// All operations maintain constant-time execution characteristics,
/// making them safe for use with cryptographic secrets and private keys.
///
/// # Performance Characteristics
/// Operations are optimized for the specific limb size and architecture,
/// providing efficient multi-precision arithmetic for cryptographic workloads.
impl BigIntOps for BigInt {
    /// Delegates to BigInt::add for constant-time addition.
    fn add(&self, rhs: &Self) -> Self {
        self.add(rhs)
    }

    /// Delegates to BigInt::sub for constant-time subtraction.
    fn sub(&self, rhs: &Self) -> Self {
        self.sub(rhs)
    }

    /// Delegates to BigInt::mul for constant-time multiplication.
    fn mul(&self, rhs: &Self) -> Self {
        self.mul(rhs)
    }

    /// Delegates to BigInt::mul_wide for wide multiplication.
    fn mul_wide(&self, rhs: &Self) -> (Self, Self) {
        self.mul_wide(rhs)
    }

    /// Delegates to BigInt::square_wide for optimized wide squaring.
    fn square_wide(&self) -> (Self, Self) {
        self.square_wide()
    }

    /// Delegates to BigInt::shl for constant-time left shift.
    fn shl(&self, bits: u32) -> Self {
        self.shl(bits)
    }

    /// Delegates to BigInt::shr for constant-time right shift.
    fn shr(&self, bits: u32) -> Self {
        self.shr(bits)
    }

    /// Delegates to BigInt::cmp for standard comparison.
    /// Warning: This may leak timing information - use ct_cmp for crypto.
    fn cmp(&self, rhs: &Self) -> Ordering {
        self.cmp(rhs)
    }

    /// Delegates to BigInt::ct_cmp for constant-time comparison.
    fn ct_cmp(&self, rhs: &Self) -> Ordering {
        self.ct_cmp(rhs)
    }

    /// Delegates to BigInt::ct_select for constant-time conditional selection.
    fn ct_select(a: &Self, b: &Self, flag: u64) -> Self {
        Self::ct_select(a, b, flag)
    }

    /// Delegates to BigInt::is_zero for constant-time zero check.
    fn is_zero(&self) -> bool {
        self.is_zero()
    }

    /// Delegates to BigInt::get_bit for constant-time bit extraction.
    fn get_bit(&self, bit_position: u32) -> u64 {
        self.get_bit(bit_position)
    }

    /// Delegates to BigInt::bit_length for bit length calculation.
    fn bit_length(&self) -> u32 {
        self.bit_length()
    }
}