clock_curve_math/montgomery/

mod.rs

//! Montgomery arithmetic for efficient modular operations.
//!
//! This module provides Montgomery reduction and multiplication algorithms
//! optimized for the Curve25519 elliptic curve parameters. Montgomery arithmetic
//! enables efficient modular multiplication by avoiding expensive division operations.
//!
//! ## Overview
//!
//! Montgomery arithmetic represents numbers in a transformed domain where
//! modular multiplication can be performed using only multiplication, addition,
//! and bit shifts. The key insight is that multiplication by R^(-1) (where R
//! is a power of 2) can be computed efficiently.
//!
//! For Curve25519:
//! - Field modulus: p = 2^255 - 19
//! - Scalar modulus: l = 2^252 + 27_742_317_777_372_353_535_851_937_790_883_648_493
//! - Montgomery radix: R = 2^256
//!
//! ## Usage
//!
//! For most use cases, use the high-level conversion functions:
//!
//! ```rust
//! use clock_curve_math::{BigInt, montgomery::{to_montgomery_p, from_montgomery_p}};
//!
//! // Convert to Montgomery form
//! let value = BigInt::from_u64(42);
//! let mont_value = to_montgomery_p(&value);
//!
//! // Perform operations in Montgomery domain
//! // ... arithmetic operations ...
//!
//! // Convert back to standard form
//! let result = from_montgomery_p(&mont_value);
//!
//! // Verify roundtrip
//! assert_eq!(result, value);
//! ```
//!
//! For low-level operations, use the core functions directly:
//!
//! ```rust
//! use clock_curve_math::{BigInt, constants::P_LIMBS, montgomery::{to_montgomery, R_SQUARED_MOD_P, N_PRIME_P}};
//!
//! // Manual conversion with explicit constants
//! let r_squared = BigInt::from_limbs(&R_SQUARED_MOD_P);
//! let modulus = BigInt::from_limbs(&P_LIMBS);
//! let n_prime = BigInt::from_limbs(&N_PRIME_P);
//! let value = BigInt::from_u64(42);
//!
//! let mont_value = to_montgomery(&value, &r_squared, &modulus, &n_prime);
//! ```
//!
//! ## Security Notes
//!
//! - All operations execute in constant time to prevent timing attacks
//! - Input validation ensures only supported Curve25519 moduli are used
//! - Precomputed constants are validated during initialization
//! - The implementation is hardened against side-channel attacks
//!
//! ## Performance Characteristics
//!
//! - Montgomery reduction: O(1) - fixed 256-bit operations
//! - Montgomery multiplication: O(1) - efficient limb-based arithmetic
//! - Conversion functions: O(1) - optimized for Curve25519 parameters

mod precomputed;
mod reduce;

pub use precomputed::{
    N_PRIME_L, N_PRIME_P, R_SQUARED_MOD_L, R_SQUARED_MOD_P, from_montgomery, to_montgomery,
    validate_constants,
};
pub use reduce::{montgomery_mul, montgomery_reduce, montgomery_square};

/// Initialize and validate the Montgomery arithmetic module.
///
/// This function should be called during application initialization to ensure
/// that all precomputed constants are valid and the module is ready for use.
/// It performs comprehensive validation of Montgomery parameters.
///
/// # Panics
///
/// Panics if any precomputed constants are invalid or inconsistent.
pub fn init() {
    validate_constants();
}

/// Convert a value to Montgomery form for the field modulus p.
///
/// The field modulus p = 2^255 - 19 is used for Curve25519 field elements.
/// This function converts standard BigInt values to Montgomery representation
/// for efficient modular arithmetic.
///
/// # Arguments
///
/// * `value` - The value to convert (must be reduced modulo p)
///
/// # Returns
///
/// The Montgomery representation of the input value.
pub fn to_montgomery_p(value: &crate::bigint::BigInt) -> crate::bigint::BigInt {
    let r_squared = crate::bigint::BigInt::from_limbs(&R_SQUARED_MOD_P);
    let n = crate::bigint::BigInt::from_limbs(&crate::constants::P_LIMBS);
    let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_P);
    to_montgomery(value, &r_squared, &n, &n_prime)
}

/// Convert a value from Montgomery form for the field modulus p.
///
/// This function converts Montgomery representation back to standard form.
/// The result is guaranteed to be in [0, p).
///
/// # Arguments
///
/// * `value` - The Montgomery representation to convert
///
/// # Returns
///
/// The standard representation of the input value.
pub fn from_montgomery_p(value: &crate::bigint::BigInt) -> crate::bigint::BigInt {
    let n = crate::bigint::BigInt::from_limbs(&crate::constants::P_LIMBS);
    let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_P);
    from_montgomery(value, &n, &n_prime)
}

/// Convert a value to Montgomery form for the scalar modulus l.
///
/// The scalar modulus l = 2^252 + 27_742_317_777_372_353_535_851_937_790_883_648_493
/// is used for Curve25519 scalar values.
///
/// # Arguments
///
/// * `value` - The value to convert (must be reduced modulo l)
///
/// # Returns
///
/// The Montgomery representation of the input value.
pub fn to_montgomery_l(value: &crate::bigint::BigInt) -> crate::bigint::BigInt {
    let r_squared = crate::bigint::BigInt::from_limbs(&R_SQUARED_MOD_L);
    let n = crate::bigint::BigInt::from_limbs(&crate::constants::L_LIMBS);
    let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_L);
    to_montgomery(value, &r_squared, &n, &n_prime)
}

/// Convert a value from Montgomery form for the scalar modulus l.
///
/// This function converts Montgomery representation back to standard form.
/// The result is guaranteed to be in [0, l).
///
/// # Arguments
///
/// * `value` - The Montgomery representation to convert
///
/// # Returns
///
/// The standard representation of the input value.
pub fn from_montgomery_l(value: &crate::bigint::BigInt) -> crate::bigint::BigInt {
    let n = crate::bigint::BigInt::from_limbs(&crate::constants::L_LIMBS);
    let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_L);
    from_montgomery(value, &n, &n_prime)
}

/// Trait for Montgomery arithmetic operations.
///
/// This trait provides a common interface for types that support Montgomery
/// arithmetic operations. Implementations are expected to provide constant-time
/// operations for cryptographic security.
///
/// Note: This trait is implemented by BigInt for Curve25519 field operations.
/// It provides Montgomery arithmetic for the prime modulus p = 2^255 - 19.
pub trait MontgomeryOps {
    /// Perform Montgomery reduction.
    ///
    /// Reduces a double-width product using Montgomery's REDC algorithm.
    /// Uses the Curve25519 field modulus p = 2^255 - 19.
    fn montgomery_reduce(t: &crate::bigint::BigInt) -> crate::bigint::BigInt;

    /// Perform Montgomery multiplication.
    ///
    /// Computes (a * b) * R^(-1) mod p where p is the Curve25519 field modulus.
    /// Both operands must be in Montgomery form.
    fn montgomery_mul(
        a: &crate::bigint::BigInt,
        b: &crate::bigint::BigInt,
    ) -> crate::bigint::BigInt;

    /// Convert to Montgomery form.
    ///
    /// Transforms a standard integer into its Montgomery representation for modulus p.
    fn to_montgomery(a: &crate::bigint::BigInt) -> crate::bigint::BigInt;

    /// Convert from Montgomery form.
    ///
    /// Transforms a Montgomery representation back to standard form.
    fn from_montgomery(a: &crate::bigint::BigInt) -> crate::bigint::BigInt;
}

impl MontgomeryOps for crate::bigint::BigInt {
    fn montgomery_reduce(t: &crate::bigint::BigInt) -> crate::bigint::BigInt {
        let n = crate::bigint::BigInt::from_limbs(&crate::constants::P_LIMBS);
        let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_P);
        reduce::montgomery_reduce(t, &n, &n_prime)
    }

    fn montgomery_mul(
        a: &crate::bigint::BigInt,
        b: &crate::bigint::BigInt,
    ) -> crate::bigint::BigInt {
        let n = crate::bigint::BigInt::from_limbs(&crate::constants::P_LIMBS);
        let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_P);
        reduce::montgomery_mul(a, b, &n, &n_prime)
    }

    fn to_montgomery(a: &crate::bigint::BigInt) -> crate::bigint::BigInt {
        let r_squared = crate::bigint::BigInt::from_limbs(&R_SQUARED_MOD_P);
        let n = crate::bigint::BigInt::from_limbs(&crate::constants::P_LIMBS);
        let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_P);
        precomputed::to_montgomery(a, &r_squared, &n, &n_prime)
    }

    fn from_montgomery(a: &crate::bigint::BigInt) -> crate::bigint::BigInt {
        let n = crate::bigint::BigInt::from_limbs(&crate::constants::P_LIMBS);
        let n_prime = crate::bigint::BigInt::from_limbs(&N_PRIME_P);
        precomputed::from_montgomery(a, &n, &n_prime)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::bigint::BigInt;
    use core::cmp::Ordering;

    #[test]
    fn test_to_from_montgomery_p_roundtrip() {
        // Test roundtrip conversion for field modulus
        let test_values = [
            BigInt::from_u64(0),
            BigInt::from_u64(1),
            BigInt::from_u64(42),
            BigInt::from_u64(u64::MAX),
        ];

        for value in &test_values {
            let mont = to_montgomery_p(value);
            let recovered = from_montgomery_p(&mont);
            assert_eq!(
                *value, recovered,
                "Montgomery roundtrip failed for {:?}",
                value
            );
        }
    }

    #[test]
    fn test_to_from_montgomery_l_roundtrip() {
        // Test roundtrip conversion for scalar modulus
        let test_values = [
            BigInt::from_u64(0),
            BigInt::from_u64(1),
            BigInt::from_u64(42),
            BigInt::from_u64(u64::MAX),
        ];

        for value in &test_values {
            let mont = to_montgomery_l(value);
            let recovered = from_montgomery_l(&mont);
            assert_eq!(
                *value, recovered,
                "Montgomery roundtrip failed for {:?}",
                value
            );
        }
    }

    #[test]
    fn test_montgomery_p_identity() {
        // Test that R * R^(-1) ≡ 1 mod p in Montgomery form
        let r_mont = to_montgomery_p(&BigInt::from_u64(1));
        let r_inv_mont = from_montgomery_p(&r_mont);
        assert_eq!(r_inv_mont, BigInt::from_u64(1));
    }

    #[test]
    fn test_montgomery_l_identity() {
        // Test that R * R^(-1) ≡ 1 mod l in Montgomery form
        let r_mont = to_montgomery_l(&BigInt::from_u64(1));
        let r_inv_mont = from_montgomery_l(&r_mont);
        assert_eq!(r_inv_mont, BigInt::from_u64(1));
    }

    #[test]
    fn test_montgomery_p_constants() {
        // Verify that the precomputed constants are consistent
        let _p = BigInt::from_limbs(&crate::constants::P_LIMBS);
        let _n_prime = BigInt::from_limbs(&N_PRIME_P);
        let r_squared = BigInt::from_limbs(&R_SQUARED_MOD_P);

        // R² mod p should equal the precomputed constant
        // Since r = 2^256, we can't easily compute r² mod p directly
        // Instead, we verify the constant is non-zero (basic sanity check)
        assert!(!r_squared.is_zero());

        // Test that N' is correct: N' = -N^(-1) mod R
        // For our case, we trust the precomputed values are correct
        // (they are verified in the precomputed module tests)
        assert!(!N_PRIME_P.iter().all(|&x| x == 0)); // Should be non-zero
    }

    #[test]
    fn test_montgomery_l_constants() {
        // Verify that the precomputed constants are consistent
        let l = BigInt::from_limbs(&crate::constants::L_LIMBS);

        // Test that constants are non-zero and have expected properties
        assert!(!N_PRIME_L.iter().all(|&x| x == 0)); // Should be non-zero
        assert!(!R_SQUARED_MOD_L.iter().all(|&x| x == 0)); // Should be non-zero

        // R² mod L should be less than L (basic Montgomery arithmetic property)
        let r_squared = BigInt::from_limbs(&R_SQUARED_MOD_L);
        assert!(r_squared.cmp(&l) == Ordering::Less);
    }

    #[test]
    fn test_montgomery_conversion_properties() {
        // Test mathematical properties of Montgomery conversion

        // For any x, from_montgomery(to_montgomery(x)) ≡ x mod p
        let x = BigInt::from_u64(12345);
        let mont_x = to_montgomery_p(&x);
        let recovered_x = from_montgomery_p(&mont_x);

        // The result should be x mod p, but since x < p, it should be x
        assert_eq!(recovered_x, x);

        // Test field modulus with larger values too
        for &test_val in &[1u64, 42u64, 100u64, 1000u64, 10000u64] {
            let x_test = BigInt::from_u64(test_val);
            let mont_x = to_montgomery_p(&x_test);
            let recovered_x = from_montgomery_p(&mont_x);
            assert_eq!(
                recovered_x, x_test,
                "Field modulus failed for value {}",
                test_val
            );
        }

        // Test with scalar modulus - now works for larger values
        for &test_val in &[1u64, 42u64, 10000u64, 100000u64, 1000000u64] {
            let x_test = BigInt::from_u64(test_val);
            let mont_x_l = to_montgomery_l(&x_test);
            let recovered_x_l = from_montgomery_l(&mont_x_l);
            assert_eq!(
                recovered_x_l, x_test,
                "Scalar modulus failed for value {}",
                test_val
            );
        }
    }
}