clock_bigint/
modexp.rs

1//! Modular exponentiation using Montgomery ladder.
2//!
3//! Implements constant-time modular exponentiation using the Montgomery ladder
4//! algorithm with constant-time conditional swaps.
5
6use crate::ct;
7use crate::error::Result;
8use crate::montgomery::{MontgomeryContext, from_mont, mont_mul, to_mont};
9use crate::types::BigIntCore;
10
11#[cfg(feature = "alloc")]
12use crate::types::BigInt;
13
14/// Modular exponentiation: base^exponent mod modulus
15///
16/// Uses Montgomery ladder algorithm for constant-time execution.
17#[cfg(feature = "alloc")]
18pub fn mod_pow(ctx: &MontgomeryContext, base: &BigInt, exponent: &BigInt) -> Result<BigInt> {
19    // Handle special cases
20    if exponent.is_zero() {
21        // base^0 = 1 mod m
22        let one = BigInt::from_u64(1, ctx.modulus().max_limbs());
23        return Ok(one);
24    }
25
26    if base.is_zero() {
27        // 0^exponent = 0 mod m (if exponent > 0)
28        return Ok(BigInt::from_u64(0, ctx.modulus().max_limbs()));
29    }
30
31    // Convert base to Montgomery form
32    let x_mont = to_mont(ctx, base)?;
33
34    // Convert 1 to Montgomery form (R̃ = to_mont(1))
35    let one = BigInt::from_u64(1, ctx.modulus().max_limbs());
36    let r_mont = to_mont(ctx, &one)?;
37
38    // Initialize Montgomery ladder: R0 = R̃, R1 = x̃
39    let mut r0 = r_mont;
40    let mut r1 = x_mont;
41
42    // Get exponent bits (from MSB to LSB)
43    let exp_limbs = exponent.limbs();
44    let mut bit_pos = 0;
45
46    // Find the most significant bit
47    let mut msb_found = false;
48    for i in (0..exp_limbs.len()).rev() {
49        if exp_limbs[i] != 0 {
50            bit_pos = (i * 64) + (63 - exp_limbs[i].leading_zeros() as usize);
51            msb_found = true;
52            break;
53        }
54    }
55
56    if !msb_found {
57        // Exponent is zero (should have been caught above, but handle it)
58        let one = BigInt::from_u64(1, ctx.modulus().max_limbs());
59        return Ok(one);
60    }
61
62    // Process bits from MSB to LSB
63    for i in (0..=bit_pos).rev() {
64        let limb_idx = i / 64;
65        let bit_idx = i % 64;
66        let bit = if limb_idx < exp_limbs.len() {
67            (exp_limbs[limb_idx] >> bit_idx) & 1
68        } else {
69            0
70        };
71
72        // Constant-time conditional swap
73        swap_bigint(bit, &mut r0, &mut r1);
74
75        // Montgomery ladder step
76        r1 = mont_mul(ctx, &r0, &r1)?;
77        r0 = mont_mul(ctx, &r0, &r0)?;
78
79        // Swap again
80        swap_bigint(bit, &mut r0, &mut r1);
81    }
82
83    // Convert result from Montgomery form
84    from_mont(ctx, &r0)
85}
86
87/// Constant-time swap of two BigInt values.
88fn swap_bigint(choice: u64, a: &mut BigInt, b: &mut BigInt) {
89    let a_limbs = a.limbs_mut();
90    let b_limbs = b.limbs_mut();
91    let len = a_limbs.len().min(b_limbs.len());
92
93    for i in 0..len {
94        ct::ct_swap(choice, &mut a_limbs[i], &mut b_limbs[i]);
95    }
96
97    // Also swap signs
98    let a_sign = a.sign();
99    let b_sign = b.sign();
100    let new_a_sign = ct::ct_select(choice, b_sign as u64, a_sign as u64) != 0;
101    let new_b_sign = ct::ct_select(choice, a_sign as u64, b_sign as u64) != 0;
102    a.set_sign(new_a_sign);
103    b.set_sign(new_b_sign);
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[test]
111    fn test_mod_pow_exponent_zero() {
112        let modulus = BigInt::from_u64(97, 10);
113        let ctx = MontgomeryContext::new(modulus).unwrap();
114        let base = BigInt::from_u64(5, 10);
115        let exponent = BigInt::from_u64(0, 10);
116        let result = mod_pow(&ctx, &base, &exponent).unwrap();
117        assert_eq!(result.limbs()[0], 1);
118    }
119}
clock_bigint/modexp.rs

clock_bigint/
modexp.rs
