# Clock-Curve-Math Crate Specification
**Version:** 0.4.0 — Foundation Release
**Date:** 2026-01-15
**Status:** Final
---
## 1. Overview
**Name:** `clock-curve-math`
**Purpose:** High-performance, constant-time, cryptography-grade number theory library for ClockCurve ecosystem.
### Scope
* Arbitrary-size integers (`BigInt`) via limb arrays
* Montgomery arithmetic for efficient modular operations
* `FieldElement` modulo `p = 2^255 - 19`
* `Scalar` modulo `l = 2^252 + 27742317777372353535851937790883648493`
* Constant-time helpers for masking, comparisons, and conditional operations
### Exclusions
* No point or curve arithmetic
* No signatures or key operations
### Optional Features
* `clock-bigint` backend (default via `bigint-backend` feature)
* `clock-rand` integration for testing or optional randomness (via `rand` feature)
* `serde` for serialization/deserialization (via `serde` feature)
---
## 2. Big Integer Representation
### 2.1 Limb Representation
* **Base unit:** `u64`
* Big integers stored in **little-endian limb arrays**, `[u64; n]` for fixed-size arithmetic
* Example: `[u64; 4]` for 256-bit numbers
* All arithmetic operations must be **constant-time** for security-critical operations
### 2.2 BigInt API
```rust
pub struct BigInt {
limbs: [u64; 4];
}
pub trait BigIntOps {
fn add(&self, rhs: &Self) -> Self;
fn sub(&self, rhs: &Self) -> Self;
fn mul(&self, rhs: &Self) -> Self;
fn shl(&self, bits: u32) -> Self;
fn shr(&self, bits: u32) -> Self;
fn cmp(&self, rhs: &Self) -> Ordering;
fn is_zero(&self) -> bool;
}
```
**Requirements:**
* All operations execute in constant time
* Little-endian limb ordering
* Support for both `clock-bigint` backend (default) and custom limb arrays (via `custom-limbs` feature)
---
## 3. Montgomery Arithmetic
### 3.1 Montgomery Reduction
For modulus \(N\) and Montgomery radix \(R = 2^{64 \cdot n}\):
**Precomputed Constants:**
* \(N' = -N^{-1} \mod R\) (Montgomery inverse of N)
* \(R^2 \mod N\) (Montgomery representation of R²)
**Conversion to Montgomery Domain:**
\[
\tilde{a} = a \cdot R \mod N
\]
**Montgomery Reduction Formula (REDC):**
\[
\text{REDC}(T) = \frac{T + ((T \cdot N') \mod R) \cdot N}{R} \mod N
\]
**Montgomery Multiplication:**
\[
\text{MontMul}(a, b) = \text{REDC}(a \cdot b) = \frac{a \cdot b + ((a \cdot b \cdot N') \mod R) \cdot N}{R} \mod N
\]
### 3.2 Montgomery API
```rust
pub trait MontgomeryOps {
fn montgomery_reduce(t: &BigInt, n: &BigInt, n_prime: &BigInt) -> BigInt;
fn montgomery_mul(a: &BigInt, b: &BigInt) -> BigInt;
fn to_montgomery(a: &BigInt, r_squared: &BigInt, n: &BigInt) -> BigInt;
fn from_montgomery(a: &BigInt, n: &BigInt, n_prime: &BigInt) -> BigInt;
}
```
### 3.3 Precomputed Constants
**Field modulus p = 2^255 - 19:**
* `R_SQUARED_MOD_P: [u64; 4]` - R² mod p (precomputed)
* `N_PRIME_P: [u64; 4]` - N' for p (precomputed)
**Scalar modulus l = 2^252 + 27742317777372353535851937790883648493:**
* `R_SQUARED_MOD_L: [u64; 4]` - R² mod l (precomputed)
* `N_PRIME_L: [u64; 4]` - N' for l (precomputed)
**Verification Functions:**
* `compute_r_squared_mod_n(n: &BigInt) -> BigInt` - Compute R² mod N for verification
* `compute_n_prime(n: &BigInt) -> BigInt` - Compute N' for verification
---
## 4. Field Elements (mod p)
### 4.1 Definition
* `FieldElement` is an integer modulo **p = 2^255 - 19**
* Stored internally in **Montgomery form** for efficient multiplication
* All operations are constant-time
### 4.2 API
```rust
pub struct FieldElement {
inner: BigInt; // Montgomery form
}
pub trait FieldOps {
fn add(&self, rhs: &Self) -> Self;
fn sub(&self, rhs: &Self) -> Self;
fn mul(&self, rhs: &Self) -> Self;
fn square(&self) -> Self;
fn inv(&self) -> Self; // constant-time inversion
fn pow(&self, exp: &BigInt) -> Self; // modular exponentiation
}
impl FieldElement {
fn from_bytes(bytes: &[u8; 32]) -> Result<Self>;
fn to_bytes(&self) -> [u8; 32];
fn from_u64(value: u64) -> Self;
fn conditional_select(a: &Self, b: &Self, flag: u64) -> Self;
fn conditional_swap(a: &mut Self, b: &mut Self, flag: u64);
fn is_valid(&self) -> bool; // Check if value is in valid range [0, p)
}
```
### 4.3 Advanced Operations
* **Inversion:** Using extended Euclidean algorithm or Montgomery ladder (constant-time)
* **Exponentiation:** Using square-and-multiply algorithm (constant-time)
* **Square Root:** Using Tonelli–Shanks algorithm (future expansion)
* **Validation:** Ensure values are in range [0, p)
---
## 5. Scalars (mod l)
### 5.1 Definition
* `Scalar` is an integer modulo **l = 2^252 + 27742317777372353535851937790883648493**
* Stored in **Montgomery form**
* All operations are constant-time
### 5.2 API
```rust
pub struct Scalar {
inner: BigInt; // Montgomery form
}
pub trait ScalarOps {
fn add(&self, rhs: &Self) -> Self;
fn sub(&self, rhs: &Self) -> Self;
fn mul(&self, rhs: &Self) -> Self;
fn square(&self) -> Self;
fn inv(&self) -> Self;
}
impl Scalar {
fn from_bytes(bytes: &[u8; 32]) -> Result<Self>;
fn to_bytes(&self) -> [u8; 32];
fn from_u64(value: u64) -> Self;
fn conditional_select(a: &Self, b: &Self, flag: u64) -> Self;
fn conditional_swap(a: &mut Self, b: &mut Self, flag: u64);
fn is_valid(&self) -> bool; // Check if value is in valid range [0, l)
}
```
---
## 6. Constant-Time Helpers
### 6.1 Conditional Operations
```rust
// Core constant-time operations
pub fn ct_eq(a: u64, b: u64) -> u64; // Returns 1 if equal, 0 otherwise
pub fn ct_neq(a: u64, b: u64) -> u64; // Returns 1 if not equal, 0 otherwise
pub fn ct_lt(a: u64, b: u64) -> u64; // Returns 1 if a < b, 0 otherwise
pub fn ct_gt(a: u64, b: u64) -> u64; // Returns 1 if a > b, 0 otherwise
pub fn ct_is_zero(x: u64) -> u64; // Returns 1 if zero, 0 otherwise
pub fn ct_select(a: u64, b: u64, flag: u64) -> u64; // Select a if flag=1, b if flag=0
pub fn ct_mask(flag: u64) -> u64; // Generate mask: 0xFFFF... if flag=1, 0 if flag=0
// Array-level operations
pub fn ct_swap(a: &mut [u64], b: &mut [u64], flag: u64);
pub fn ct_select_array<const N: usize>(
a: &[u64; N],
b: &[u64; N],
flag: u64
) -> [u64; N];
```
### 6.2 Purpose
* Prevent timing attacks in arithmetic or comparisons
* Used throughout BigInt, FieldElement, Scalar operations
* All operations execute in constant time regardless of input values
**Implementation Requirements:**
* No branches based on secret data
* Use bitwise operations and masking
* Fixed loop iterations
* No data-dependent memory access patterns
---
## 7. Constants
### 7.1 Field Modulus (p)
**p = 2^255 - 19**
```rust
pub const P_LIMBS: [u64; 4] = [
0xffffffffffffffff, // 2^64 - 1
0xffffffffffffffff, // 2^64 - 1
0xffffffffffffffff, // 2^64 - 1
0x7fffffffffffffed, // 2^63 - 19
];
```
**Decimal representation:** 57896044618658097711785492504343953926634992332820282019728792003956564819949
### 7.2 Scalar Modulus (l)
**l = 2^252 + 27742317777372353535851937790883648493**
```rust
pub const L_LIMBS: [u64; 4] = [
0x5812631a5cf5d3ed,
0x14def9dea2f79cd6,
0x0000000000000000,
0x1000000000000000, // 2^60
];
```
**Decimal representation:** 7237005577332262213973186563042994240857116359379907606001950938285454250989
### 7.3 Montgomery Constants
**For Field Modulus (p):**
* `R_SQUARED_MOD_P: [u64; 4]` - Precomputed R² mod p
* `N_PRIME_P: [u64; 4]` - Precomputed N' for p
**For Scalar Modulus (l):**
* `R_SQUARED_MOD_L: [u64; 4]` - Precomputed R² mod l
* `N_PRIME_L: [u64; 4]` - Precomputed N' for l
**Note:** These constants are computed once and stored. Verification functions are provided to recompute them for testing.
---
## 8. Optional Features
### 8.1 Feature Flags
* **`bigint-backend`** (default): Use `clock-bigint` as BigInt backend
* **`custom-limbs`**: Use custom limb array implementation (mutually exclusive with `bigint-backend`)
* **`rand`**: Enable random FieldElement/Scalar generation via `clock-rand`
* **`serde`**: Enable serialization/deserialization for FieldElement and Scalar
* **`alloc`**: Enable heap allocations (required for some clock-bigint operations)
* **`std`**: Enable standard library support
### 8.2 Integration Points
**clock-bigint:**
* When `bigint-backend` is enabled, wrap `clock_bigint::U256` or `clock_bigint::BigInt`
* Use clock-bigint's Montgomery operations when available
* Maintain API compatibility between backends
* Ensure constant-time guarantees are preserved
**clock-rand:**
* Generate random FieldElements for testing
* Generate random Scalars for testing
* Optional deterministic nonce generation (future expansion)
---
## 9. Error Handling
### 9.1 Error Types
```rust
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MathError {
InvalidBytes, // Bytes out of valid range
InvalidInput, // General invalid input
DivisionByZero, // Attempted division by zero
Overflow, // Arithmetic overflow
Underflow, // Arithmetic underflow
}
```
### 9.2 Validation Requirements
* `from_bytes()` methods validate input ranges:
* FieldElement: bytes must represent value in [0, p)
* Scalar: bytes must represent value in [0, l)
* All parsing operations return `Result<T, MathError>`
* Arithmetic operations may panic on overflow/underflow in debug mode
---
## 10. Testing Requirements
### 10.1 Unit Tests
* Test all limb arithmetic operations
* Test Montgomery reduction correctness
* Test conversion to/from Montgomery form
* Test FieldElement and Scalar operations
* Test constant-time properties
### 10.2 Constant-Time Verification
* Timing tests using `criterion` benchmark suite
* Verify operations take constant time regardless of input values
* Test conditional operations for timing leaks
### 10.3 Property-Based Tests
* Randomized test vectors using `proptest`
* Test arithmetic properties (associativity, commutativity, distributivity)
* Test Montgomery arithmetic correctness
* Test inversion correctness (a * a.inv() == 1)
### 10.4 Edge Cases
* Zero, one, p-1 (for FieldElement)
* Zero, one, l-1 (for Scalar)
* Overflow and underflow scenarios
* Boundary values
---
## 11. Future Expansion
Potential additions (not in v1.0.0):
* Multi-limb modular exponentiation
* Jacobi symbol, Legendre symbol computation
* Arbitrary-length BigInt arithmetic
* Square root computation (Tonelli–Shanks)
* Prepares for future curve and signature layers
---
## 12. Security Considerations
### 12.1 Constant-Time Guarantees
* All operations must execute in constant time
* No branches based on secret data
* No data-dependent memory access
* Fixed loop iterations
* Use bitwise operations and masking
### 12.2 Input Validation
* Validate all inputs to prevent invalid states
* Check ranges for byte conversions
* Ensure values are in valid ranges [0, p) or [0, l)
### 12.3 Side-Channel Resistance
* All comparisons use constant-time operations
* Conditional operations use masking, not branches
* Montgomery arithmetic provides additional protection
---
## 13. References
* Montgomery, P. L. (1985). "Modular multiplication without trial division"
* Ed25519 specification (RFC 8032)
* Curve25519 specification
* clock-bigint crate documentation
* clock-rand crate documentation
---
**End of Specification**