# Montgomery & Modular Exponentiation Specification v1.0
## Overview
This specification defines the normative cryptographic arithmetic standard for Montgomery operations and modular exponentiation, critical for ChronoSig, ChronoHash, ChronoMerkle, and ZK systems.
## 1. Base Parameters
### 1.1 Definitions
- Limb base: `B = 2^64`
- Limb count: `n`
- Modulus: `m`, where `m` MUST be odd
- `R = B^n mod m`
- `R² = B^(2n) mod m`
- `m' = -m⁻¹ mod B`
### 1.2 Montgomery Representation
A value `x` in normal representation is converted to Montgomery form:
```
x̃ = (x × R) mod m
```
Montgomery domain arithmetic operates on `x̃`.
## 2. Montgomery Reduction
### 2.1 Function Signature
```rust
fn mont_reduce(t: &BigInt, m: &BigInt, m_prime: Limb) -> BigInt
```
Where `t` is a 2n-limb value.
### 2.2 Algorithm
```
For i = 0 .. n-1:
u_i = (t[i] × m') mod B
(t[i .. i+n]) += u_i × m[0 .. n]
After loop:
t = t[n .. 2n]
if t ≥ m:
t -= m
```
### 2.3 Constant-Time Implementation
The conditional subtraction MUST be implemented via **masked subtraction** — not branching.
### 2.4 Gas Cost
`G_mont_reduce(n) = n²`
## 3. Montgomery Multiplication
### 3.1 Function Signature
```rust
fn mont_mul(ã: &BigInt, b̃: &BigInt, m: &BigInt, m_prime: Limb) -> BigInt
```
### 3.2 Definition
```
c̃ = mont_reduce(ã × b̃)
```
Produces: `c̃ = (a × b × R) mod m`
### 3.3 Gas Cost
`G_mont_mul(n) = 2n²`
## 4. Montgomery Addition/Subtraction
Performed normally in Montgomery domain:
```
Add: c̃ = (ã + b̃) mod m
Sub: c̃ = (ã - b̃) mod m
```
Both followed by conditional reduction (constant-time masked subtraction).
## 5. Conversion Functions
### 5.1 Into Montgomery Form
```rust
fn to_mont(x: &BigInt, m: &BigInt) -> BigInt
```
Definition:
```
to_mont(x) = mont_mul(x, R² mod m)
```
### 5.2 Out of Montgomery Form
```rust
fn from_mont(x̃: &BigInt, m: &BigInt) -> BigInt
```
Definition:
```
from_mont(x̃) = mont_reduce(x̃)
```
## 6. Montgomery Context
### 6.1 Structure
```rust
struct MontgomeryContext {
modulus: BigInt, // m
r_mod_m: BigInt, // R mod m
r_squared_mod_m: BigInt, // R² mod m
m_prime: Limb, // m'
limb_count: usize, // n
}
```
### 6.2 Creation
```rust
fn new(modulus: BigInt) -> Result<MontgomeryContext>
```
Requirements:
- `modulus` MUST be odd
- `modulus > 0`
- Precomputes all context values
## 7. Modular Exponentiation
### 7.1 Function Signature
```rust
fn mod_pow(base: &BigInt, exponent: &BigInt, modulus: &BigInt) -> Result<BigInt>
```
### 7.2 Montgomery Ladder Algorithm
```
Input: base in normal form
Output: base^exponent mod modulus
1. Precompute:
R mod m
R² mod m
m'
2. Convert:
x̃ = to_mont(base)
R̃ = to_mont(1)
3. Initialize:
R0 = R̃
R1 = x̃
4. For bit i from MSB(exponent) → LSB:
bit = exponent[i]
cswap(bit, R0, R1)
R1 = mont_mul(R0, R1)
R0 = mont_mul(R0, R0)
cswap(bit, R0, R1)
5. result = from_mont(R0)
```
### 7.3 Constant-Time Conditional Swap
```rust
mask = -bit // 0xFFFF... if bit=1, 0x0000... if bit=0
tmp = mask & (R0 XOR R1)
R0 ^= tmp
R1 ^= tmp
```
No branches allowed.
### 7.4 Gas Cost
`G_modexp(n, k) = k × 4n² + 20n²`
Where k = exponent bit length.
## 8. Modular Inverse
### 8.1 Via Extended GCD
```rust
fn mod_inverse(a: &BigInt, m: &BigInt) -> Result<BigInt>
```
Uses binary extended GCD with constant-time loop bounds.
### 8.2 Via Fermat's Little Theorem
For prime modulus `p`:
```
a⁻¹ mod p = a^(p-2) mod p
```
### 8.3 Gas Cost
- Via GCD: `G_inv_gcd(n) = 6n²`
- Via exponentiation: same as `G_modexp`
## 9. Error Conditions
| m even | Reject modulus (InvalidModulus error) |
| modulus = 0 | Reject (InvalidModulus error) |
| exponent = 0 | Return 1 mod m |
| base = 0 & exponent = 0 | Return 1 (by convention) |
## 10. Security Properties
### 10.1 Constant-Time Guarantee
All Montgomery operations MUST maintain:
- Constant-time execution w.r.t secret data
- No secret-dependent memory access
- Identical instruction count for equal limb sizes
- Safe for signature and ZK usage
### 10.2 Side Channel Resistance
- Montgomery reduction eliminates power analysis patterns
- Ladder exponentiation prevents timing attacks
- No data-dependent branches or memory access
## 11. Test Vector Requirements
### 11.1 Known Answer Tests
Test vectors MUST include:
- RSA modulus operations
- secp256k1 field operations
- Randomized consistency tests:
```rust
// Verify: from_mont(mont_mul(to_mont(a), to_mont(b))) == (a*b mod m)
assert_eq!(
from_mont(&mont_mul(&to_mont(a), &to_mont(b))),
(a * b) % modulus
);
```
### 11.2 Edge Cases
- Modulus = 3 (smallest valid odd modulus)
- Base = 0, 1, modulus-1
- Exponent = 0, 1, large values
- Carry propagation in Montgomery reduction
## 12. Performance Targets
| MontMul (256-bit) | ~200 cycles |
| MontReduce (256-bit) | ~100 cycles |
| ModExp (2048-bit) | within 10% of GMP |
## 13. Implementation Notes
### 13.1 Word Size Assumptions
- Assumes 64-bit limbs
- Montgomery parameters optimized for 64-bit arithmetic
- No support for 32-bit platforms
### 13.2 Memory Layout
- All Montgomery values use canonical BigInt representation
- No special internal formats
- Compatible with all other BigInt operations
### 13.3 Determinism
- Identical results across platforms
- No undefined behavior
- Reproducible for consensus-critical applications