Montgomery & Modular Exponentiation v1.0 - ClockinChain Big Integer Specifications
Description: Normative specifications for ClockinChain big integer arithmetic

# 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