clock-curve-math 0.6.0

# clock-curve-math

[![Crates.io](https://img.shields.io/crates/v/clock-curve-math.svg)](https://crates.io/crates/clock-curve-math)
[![Documentation](https://docs.rs/clock-curve-math/badge.svg)](https://docs.rs/clock-curve-math)
[![License](https://img.shields.io/badge/license-MIT%20OR%20Apache--2.0-blue.svg)](https://github.com/Olyntar-Labs/clock-curve-math)

High-performance, constant-time, cryptography-grade number theory library for the ClockCurve ecosystem.

**🎉 Version 0.6.0 - Feature-Complete Stable Release!** Production-ready cryptography foundation with full ecosystem integration, cross-platform support, and comprehensive security guarantees.

## Overview

`clock-curve-math` provides the mathematical foundation for ClockCurve cryptography, implementing:

- **Big integer arithmetic** with constant-time operations
- **Montgomery arithmetic** for efficient modular operations
- **FieldElement** modulo `p = 2^255 - 19` (Ed25519 field)
- **Scalar** modulo `l = 2^252 + 27742317777372353535851937790883648493` (Ed25519 group order)
- **Constant-time helpers** for secure computations

All operations are designed for cryptographic security with timing attack resistance.

## ✅ Version 0.6.0 - Feature-Complete Stable Release

This stable release provides production-ready cryptography with full ecosystem integration:

- **✓ BigInt Operations**: Full arithmetic (add, sub, mul, cmp) with constant-time guarantees
- **✓ Montgomery Arithmetic**: Complete REDC algorithm with precomputed constants
- **✓ FieldElement Operations**: All arithmetic (add, sub, mul, inv, pow, square, neg) modulo p
- **✓ Scalar Operations**: All arithmetic (add, sub, mul, inv, pow, square, neg) modulo l
- **✓ Advanced Field Operations**: Batch inversion, multi-exponentiation, modular square root, Legendre symbol
- **✓ Constant-Time Helpers**: ct_eq, ct_neq, ct_lt, ct_gt, ct_select, ct_swap operations
- **✓ Multiple Backends**: Both `bigint-backend` (clock-bigint) and `custom-limbs` implementations
- **✓ Optional Features**: Serde serialization and random generation via clock-rand
- **✓ Security Verified**: Comprehensive audit with constant-time verification
- **✓ Cross-Platform**: Tested on x86_64, aarch64, riscv64, armv7, powerpc64, embedded targets
- **✓ Production Ready**: No unsafe code, comprehensive error handling, input validation
- **✓ Comprehensive Documentation**: Tutorials, examples, and API reference complete
- **✓ API Stability Assessment**: Complete API review with backward compatibility guarantees
- **✓ Ecosystem Integration**: Comprehensive testing with clock-bigint, clock-rand, and serde
- **✓ Cross-Feature Compatibility**: All feature flag combinations validated and tested
- **✓ Production Readiness**: Security audit preparation and performance benchmarking complete

## Features

### Backend Options

- **`bigint-backend`** (default): Use `clock-bigint` for optimized performance
- **`custom-limbs`**: Use custom limb array implementation (fallback)
- **`alloc`**: Heap allocations (required for advanced operations)
- **`std`**: Standard library support
- **`rand`**: Random generation via `clock-rand`
- **`serde`**: Serialization support

## Installation

Add this to your `Cargo.toml`:

```toml
[dependencies]
clock-curve-math = "0.6.0"
```

📦 **Latest Release**: [v0.6.0 - Feature-Complete Stable Release](https://github.com/Olyntar-Labs/clock-curve-math/releases/tag/v0.6.0)

## 🎯 Version 0.6.0 - Final Release Roadmap

The 0.6.0 release is the first stable version of `clock-curve-math`, providing:

- **API Stability Guarantees**: Backward compatibility for the 0.6.x series
- **Production Readiness**: Comprehensive testing and security validation
- **Ecosystem Integration**: Seamless integration with ClockCurve components
- **Documentation**: Complete API reference and integration guides

### Release Schedule
- **✅ 0.6.0**: Feature-Complete Stable Release (Complete)

### Feature Flags

For custom backend:
```toml
[dependencies]
clock-curve-math = { version = "0.6.0", default-features = false, features = ["custom-limbs", "alloc"] }
```

## Tutorials

### Getting Started

This section provides step-by-step guides for common use cases.

#### 1. Basic Field Arithmetic

```rust
use clock_curve_math::{FieldElement, FieldOps};

// Create field elements from various sources
let a = FieldElement::from_u64(42);
let b = FieldElement::from_bytes(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
                                   17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32])
    .expect("valid bytes");

// Perform basic arithmetic
let sum = a.add(&b);
let difference = a.sub(&b);
let product = a.mul(&b);
let square = a.square();

// Check if element is valid (in range [0, p))
assert!(a.is_valid());
assert!(sum.is_valid());
```

#### 2. Scalar Arithmetic for Digital Signatures

```rust
use clock_curve_math::{Scalar, ScalarOps};

// Generate a random scalar (private key)
let private_key = Scalar::from_u64(0x123456789ABCDEF);

// Perform scalar operations used in signature schemes
let k = Scalar::from_u64(42);  // Random nonce
let r = private_key.mul(&k);   // r = private_key * k
let s = k.inv().mul(&r);       // s = k^(-1) * r (simplified)

// Convert to bytes for transmission
let signature_bytes = r.to_bytes();
```

#### 3. Batch Operations for Efficiency

```rust
use clock_curve_math::{FieldElement, field::advanced::batch_inverse};

// When computing many inverses, use batch inversion for better performance
let elements = vec![
    FieldElement::from_u64(2),
    FieldElement::from_u64(3),
    FieldElement::from_u64(5),
    FieldElement::from_u64(7),
];

let inverses = batch_inverse(&elements).expect("all elements invertible");

// Verify: element[i] * inverse[i] ≡ 1 mod p
for (elem, inv) in elements.iter().zip(inverses.inverses.iter()) {
    assert_eq!(elem.mul(inv), FieldElement::from_u64(1));
}
```

#### 4. Multi-Exponentiation for Pairings

```rust
use clock_curve_math::{FieldElement, BigInt, field::advanced::multi_exp};

// Multi-exponentiation: g₁ᵉ¹ * g₂ᵉ² * ... * gₙᵉⁿ
let bases = vec![
    FieldElement::from_u64(2),
    FieldElement::from_u64(3),
    FieldElement::from_u64(5),
];

let exponents = vec![
    BigInt::from_u64(10),
    BigInt::from_u64(20),
    BigInt::from_u64(30),
];

// Compute ∏ bases[i]^exponents[i]
let result = multi_exp(&bases, &exponents).expect("computation successful");
```

#### 5. Backend Selection Guide

**For Performance (Default):**
```toml
[dependencies]
clock-curve-math = "0.6.0"
```

**For Embedded/No-Std:**
```toml
[dependencies]
clock-curve-math = { version = "0.6.0", default-features = false, features = ["custom-limbs"] }
```

**For Random Generation:**
```toml
[dependencies]
clock-curve-math = { version = "0.6.0", features = ["rand"] }
```

**For Serialization:**
```toml
[dependencies]
clock-curve-math = { version = "0.6.0", features = ["serde"] }
```

## Usage

### Basic Arithmetic

```rust
use clock_curve_math::{FieldElement, Scalar};

// Create field elements (mod p)
let a = FieldElement::from_u64(10);
let b = FieldElement::from_u64(20);

let sum = a.add(&b);
let product = a.mul(&b);

// Create scalars (mod l)
let s1 = Scalar::from_u64(5);
let s2 = Scalar::from_u64(7);

let scalar_product = s1.mul(&s2);
```

### Byte Conversions

```rust
use clock_curve_math::FieldElement;

// From canonical bytes (32 bytes)
let bytes = [42u8; 32];
let fe = FieldElement::from_bytes(&bytes).expect("valid bytes");

// Back to bytes
let recovered_bytes = fe.to_bytes();

// From u64
let fe_from_int = FieldElement::from_u64(12345);
```

### Serialization with Serde

```rust
use clock_curve_math::{FieldElement, Scalar};
use serde_json;

// Serialize to JSON
let element = FieldElement::from_u64(42);
let json = serde_json::to_string(&element).unwrap();
println!("Serialized: {}", json);

// Deserialize from JSON
let deserialized: FieldElement = serde_json::from_str(&json).unwrap();
assert_eq!(element, deserialized);
```

### Random Generation

```rust
use clock_curve_math::{FieldElement, Scalar};
use clock_rand::Xoshiro256Plus;

let mut rng = Xoshiro256Plus::new(42);

// Generate random field element in [0, p)
let random_fe = FieldElement::random(&mut rng);

// Generate random non-zero field element in [1, p)
let random_nonzero_fe = FieldElement::random_nonzero(&mut rng);

// Generate random scalar in [0, l)
let random_scalar = Scalar::random(&mut rng);

// Generate random non-zero scalar in [1, l)
let random_nonzero_scalar = Scalar::random_nonzero(&mut rng);
```

### Error Handling and Validation

The library provides comprehensive error handling with the [`MathError`] enum:

```rust
use clock_curve_math::{FieldElement, Scalar, MathError, validation};

// Byte validation before construction
let bytes = [42u8; 32];
validation::validate_field_bytes(&bytes).expect("bytes in valid range");

let element = FieldElement::from_bytes(&bytes).expect("construction successful");

// Invalid bytes will return an error
let invalid_bytes = [0xFF; 32]; // May be >= p
match FieldElement::from_bytes(&invalid_bytes) {
    Ok(_) => println!("Valid field element"),
    Err(MathError::InvalidFieldElement) => println!("Value out of range"),
    Err(e) => println!("Other error: {:?}", e),
}

// Scalars work similarly
let scalar_bytes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
                    17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32];
let scalar = Scalar::from_bytes(&scalar_bytes).expect("valid scalar");

```

### No-Std Usage

This crate supports `no_std` environments with flexible configurations for embedded systems and constrained environments.

#### Minimal Embedded Configuration

For microcontrollers and kernels with minimal memory:

```toml
[dependencies]
clock-curve-math = { version = "0.6.0", default-features = false, features = ["custom-limbs"] }
```

```rust,no_run
use clock_curve_math::{FieldElement, Scalar};

// All basic operations work without heap allocation
let a = FieldElement::from_u64(42);
let b = FieldElement::from_u64(24);
let sum = a.add(&b);
let product = a.mul(&b);

// Scalar operations work similarly
let s1 = Scalar::from_u64(5);
let s2 = Scalar::from_u64(7);
let scalar_product = s1.mul(&s2);
```

#### With Heap Allocation

For environments with allocators but no full std:

```toml
[dependencies]
clock-curve-math = { version = "0.6.0", default-features = false, features = ["alloc", "custom-limbs"] }
```

```rust,no_run
use clock_curve_math::{FieldElement, field};

// Basic operations still work
let a = FieldElement::from_u64(42);

// Advanced operations requiring allocation
let elements = vec![a, FieldElement::from_u64(24)];
let inverses = field::batch_inverse(&elements).unwrap();
```

#### Backend Options

- **`custom-limbs`**: Pure Rust implementation, no external dependencies, full no_std
- **`bigint-backend`**: High-performance using `clock-bigint` (requires `alloc`)

#### Tested Architectures

- **Desktop/Server**: x86_64, aarch64, riscv64gc, armv7, powerpc64
- **Embedded**: thumbv7em-none-eabi, thumbv8m.main-none-eabi
- **Cross-compilation**: All major Rust targets supported

### Advanced Operations

#### Batch Inversion

Efficiently compute the multiplicative inverse of multiple field elements:

```rust
use clock_curve_math::{FieldElement, field::advanced::batch_inverse};

// Batch inversion is more efficient than computing inverses individually
let elements = vec![
    FieldElement::from_u64(2),
    FieldElement::from_u64(3),
    FieldElement::from_u64(5),
    FieldElement::from_u64(7),
];

let inverses = batch_inverse(&elements).expect("all elements have inverses");

// Verify: elements[i] * inverses[i] ≡ 1 mod p
for (elem, inv) in elements.iter().zip(inverses.inverses.iter()) {
    assert_eq!(elem.mul(inv), FieldElement::from_u64(1));
}

// Performance: O(n) multiplications + O(1) inversions vs O(n) inversions individually
```

#### Multi-Exponentiation

Compute products of multiple bases raised to exponents efficiently:

```rust
use clock_curve_math::{FieldElement, BigInt, field::advanced::multi_exp};

// Multi-exponentiation: ∏ bases[i]^exponents[i]
let bases = vec![
    FieldElement::from_u64(2),  // 2^x
    FieldElement::from_u64(3),  // 3^y
    FieldElement::from_u64(5),  // 5^z
];

let exponents = vec![
    BigInt::from_u64(10),  // x = 10
    BigInt::from_u64(20),  // y = 20
    BigInt::from_u64(30),  // z = 30
];

// Result = 2^10 * 3^20 * 5^30 mod p
let result = multi_exp(&bases, &exponents).expect("computation successful");

// Uses binary method for efficiency: O(n * max_bit_length) vs O(n * max_bit_length²)
```

#### Modular Square Root

Compute square roots in the finite field:

```rust
use clock_curve_math::{FieldElement, field::advanced::{sqrt, legendre_symbol}};

// Check if a number is a quadratic residue
let num = FieldElement::from_u64(4);
let legendre = legendre_symbol(&num);

// legendre_symbol returns:
// 1 if num is a quadratic residue (has square root)
// -1 if num is not a quadratic residue
// 0 if num ≡ 0 mod p

if legendre == 1 {
    let sqrt_result = sqrt(&num).expect("should have square root");
    assert_eq!(sqrt_result.square(), num);  // Verify: sqrt^2 ≡ num mod p
}
```

#### Windowed Multi-Exponentiation

For better performance with large exponents:

```rust
use clock_curve_math::{FieldElement, BigInt, field::advanced::multi_exp_windowed};

// Windowed multi-exponentiation trades space for time
let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
let exponents = vec![BigInt::from_u64(1000), BigInt::from_u64(2000)];

// Window size w=4: precomputes tables of size 2^w for each base
let result = multi_exp_windowed(&bases, &exponents, 4).expect("computation successful");

// Optimal window size is typically 4-6 for cryptographic field sizes
```

#### Comprehensive Advanced Operations Reference

| Operation | Function | Purpose | Performance |
|-----------|----------|---------|-------------|
| **Batch Inversion** | `batch_inverse()` | Invert multiple elements efficiently | O(n) vs O(n log p) |
| **Batch Inversion (Checked)** | `batch_inverse_checked()` | Batch inversion with error handling | O(n) vs O(n log p) |
| **Small Batch Inversion** | `batch_inverse_small()` | Optimized for small arrays | O(n) |
| **Multi-Exponentiation** | `multi_exp()` | ∏ bases[i]^exponents[i] | O(n × bit_length) |
| **Multi-Exponentiation (Checked)** | `multi_exp_checked()` | Multi-exp with validation | O(n × bit_length) |
| **Windowed Multi-Exponentiation** | `multi_exp_windowed()` | Multi-exp with window optimization | O(n × bit_length / w) |
| **Legendre Symbol** | `legendre_symbol()` | Quadratic residue test | O(log p) |
| **Modular Square Root** | `sqrt()` | Square root in finite field | O(log³ p) |

##### When to Use Each Operation

- **Use `batch_inverse()`** when computing many modular inverses simultaneously
- **Use `multi_exp()`** for cryptographic protocols like signature verification
- **Use `sqrt()`** for operations requiring square roots (e.g., some signature schemes)
- **Use `legendre_symbol()`** to test if elements are quadratic residues
- **Use windowed variants** when exponents are large (>256 bits)

## Architecture

```
clock-curve-math
├── ct/           # Constant-time operations and verification
├── bigint/       # Big integer arithmetic
├── montgomery/   # Montgomery reduction
├── field/        # FieldElement (mod p)
├── scalar/       # Scalar (mod l)
├── validation.rs # Input validation functions
├── error.rs      # Error handling and MathError enum
└── constants.rs  # Mathematical constants
```

### Constant-Time Guarantees

All cryptographic operations execute in constant time regardless of input values:

- Comparisons use bitwise operations, not branches
- Conditional operations use masking, not `if`/`else`
- Loop iterations are fixed, not data-dependent
- All arithmetic avoids secret-dependent branches

### Montgomery Arithmetic

The library uses Montgomery form internally for efficient modular multiplication:

```rust
// Values are stored in Montgomery representation
let a = FieldElement::from_u64(5);  // Automatically converted to Montgomery form
let b = FieldElement::from_u64(7);
let product = a.mul(&b);            // Montgomery multiplication
```

## Mathematical Constants

### Field Modulus (p)
```
p = 2^255 - 19
  = 57896044618658097711785492504343953926634992332820282019728792003956564819949
```

### Scalar Modulus (l)
```
l = 2^252 + 27742317777372353535851937790883648493
  = 7237005577332262213973186563042994240857116359379907606001950938285454250989
```

## Security Considerations

See [SECURITY.md](SECURITY.md) for comprehensive security documentation including:

- **Constant-Time Guarantees**: All operations execute in constant time
- **Threat Model**: Attack vectors and mitigation strategies
- **Input Validation**: Comprehensive validation prevents invalid states
- **Memory Safety**: No unsafe code, Rust's safety guarantees maintained
- **Security Testing**: Constant-time verification and vulnerability scanning
- **Hardening Measures**: Build and runtime security features

### Constant-Time Verification Tools

For rigorous constant-time verification, use the included SageMath-based analysis tool:

```bash
# Setup the verification environment
./setup_constant_time_verification.sh

# Run constant-time verification
conda activate clock-curve-math-analysis
python verify_constant_time.py
```

This tool performs statistical analysis using SageMath to detect timing variations that could indicate side-channel vulnerabilities. Results are saved to `constant_time_analysis.json` with detailed statistical metrics including confidence intervals, distribution normality tests, and coefficient of variation analysis.

## Testing

Run the full test suite:

```bash
cargo test
```

Run with different backends:

```bash
# Default backend
cargo test

# Custom limbs backend
cargo test --no-default-features --features custom-limbs,alloc
```

### Test Coverage

- **160+ comprehensive tests** covering all functionality including advanced operations
- **Unit tests** for all arithmetic operations (add, sub, mul, square, neg, inv, pow)
- **Advanced operation tests** for batch inversion, multi-exponentiation, square root, Legendre symbol
- **Property-based tests** with randomized inputs verifying algebraic properties
- **Edge case testing** (zero, one, boundary values, large numbers, invalid inputs)
- **Constant-time verification** tests ensuring timing attack resistance
- **Backend compatibility testing** across different feature configurations
- **Error handling validation** for all public APIs
- **Cross-platform testing** for x86_64, aarch64, riscv64, armv7, powerpc64, embedded targets

## Benchmarks

Run performance benchmarks:

```bash
cargo bench
```

Benchmarks cover:
- Arithmetic operations (add, multiply, etc.)
- Montgomery reduction
- Modular exponentiation
- Constant-time verification

## API Reference

Complete API documentation is available at [docs.rs/clock-curve-math](https://docs.rs/clock-curve-math).

### Core Types

| Type | Purpose | Documentation |
|------|---------|---------------|
| [`FieldElement`] | Finite field arithmetic modulo p | [FieldElement docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/field/struct.FieldElement.html) |
| [`Scalar`] | Scalar arithmetic modulo l | [Scalar docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/scalar/struct.Scalar.html) |
| [`BigInt`] | Big integer arithmetic | [BigInt docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/bigint/struct.BigInt.html) |

### Traits

| Trait | Purpose | Documentation |
|-------|---------|---------------|
| [`FieldOps`] | Field element operations | [FieldOps docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/field/trait.FieldOps.html) |
| [`ScalarOps`] | Scalar operations | [ScalarOps docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/scalar/trait.ScalarOps.html) |
| [`BigIntOps`] | Big integer operations | [BigIntOps docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/bigint/trait.BigIntOps.html) |

### Advanced Operations

| Module | Purpose | Documentation |
|--------|---------|---------------|
| `field::advanced` | Batch operations, multi-exp, square root | [Advanced Field docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/field/advanced/index.html) |
| `ct` | Constant-time helpers | [CT helpers docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/ct/index.html) |
| `montgomery` | Montgomery arithmetic | [Montgomery docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/montgomery/index.html) |
| `validation` | Input validation | [Validation docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/validation/index.html) |

### Error Handling

| Type | Purpose | Documentation |
|------|---------|---------------|
| [`MathError`] | Cryptographic math errors | [MathError docs](https://docs.rs/clock-curve-math/latest/clock_curve_math/enum.MathError.html) |

For local API documentation generation:

```bash
cargo doc --open
```

## Ecosystem Integration

`clock-curve-math` integrates seamlessly with the ClockIn ecosystem:

### Core Dependencies
- **`clock-bigint`**: High-performance BigInt backend (default)
- **`clock-rand`**: Cryptographic random number generation (`rand` feature)

### Optional Integration
- **`serde`**: JSON/binary serialization support
- **Cross-platform**: Tested on x86_64, aarch64, riscv64, armv7, powerpc64

### Integration Testing
Comprehensive ecosystem tests ensure compatibility:
```bash
cargo test --test ecosystem_integration
```

For detailed integration guides, see:
- [ECOSYSTEM_INTEGRATION.md](ECOSYSTEM_INTEGRATION.md) - Complete integration guide
- [API_STABILITY_ASSESSMENT.md](API_STABILITY_ASSESSMENT.md) - API stability guarantees
- [BACKWARD_COMPATIBILITY_GUARANTEES.md](BACKWARD_COMPATIBILITY_GUARANTEES.md) - Compatibility promises

## Contributing

1. Follow the [SPEC.md](SPEC.md) specification
2. Ensure constant-time properties are maintained
3. Add comprehensive tests for new functionality
4. Update documentation for API changes

## License

Licensed under either of:
- Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE))
- MIT License ([LICENSE-MIT](LICENSE-MIT))

at your option.

## Changelog

See [CHANGELOG.md](CHANGELOG.md) for detailed release notes and version history.

## References

- [Ed25519 specification (RFC 8032)](https://tools.ietf.org/html/rfc8032)
- [Curve25519 specification](https://cr.yp.to/ecdh/curve25519-20060209.pdf)
- [Montgomery, P. L. "Modular multiplication without trial division" (1985)](https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777282-X/S0025-5718-1985-0777282-X.pdf)