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

#![allow(unused)]
fn main() {
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

#![allow(unused)]
fn main() {
fn mont_mul(ã: &BigInt, b̃: &BigInt, m: &BigInt, m_prime: Limb) -> BigInt
}

3.2 Definition

c̃ = mont_reduce(ã × 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̃ = (ã + b̃) mod m
Sub: c̃ = (ã - b̃) mod m

Both followed by conditional reduction (constant-time masked subtraction).

5. Conversion Functions

5.1 Into Montgomery Form

#![allow(unused)]
fn main() {
fn to_mont(x: &BigInt, m: &BigInt) -> BigInt
}

Definition:

to_mont(x) = mont_mul(x, R² mod m)

5.2 Out of Montgomery Form

#![allow(unused)]
fn main() {
fn from_mont(x̃: &BigInt, m: &BigInt) -> BigInt
}

Definition:

from_mont(x̃) = mont_reduce(x̃)

6. Montgomery Context

6.1 Structure

#![allow(unused)]
fn main() {
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

#![allow(unused)]
fn main() {
fn new(modulus: BigInt) -> Result<MontgomeryContext>
}

Requirements:

modulus MUST be odd
modulus > 0
Precomputes all context values

7. Modular Exponentiation

7.1 Function Signature

#![allow(unused)]
fn main() {
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

#![allow(unused)]
fn main() {
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

#![allow(unused)]
fn main() {
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

Condition	Result
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:

#![allow(unused)]
fn main() {
// 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

Operation	Target
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

ClockinChain Big Integer Specifications