crypto_bigint/modular/boxed_monty_form/
pow.rs

1//! Modular exponentiation support for [`BoxedMontyForm`].
2
3use super::{mul::MontyMultiplier, BoxedMontyForm};
4use crate::{BoxedUint, ConstantTimeSelect, Limb, PowBoundedExp, Word};
5use alloc::vec::Vec;
6use subtle::{ConstantTimeEq, ConstantTimeLess};
7
8impl BoxedMontyForm {
9    /// Raises to the `exponent` power.
10    pub fn pow(&self, exponent: &BoxedUint) -> Self {
11        self.pow_bounded_exp(exponent, exponent.bits_precision())
12    }
13
14    /// Raises to the `exponent` power,
15    /// with `exponent_bits` representing the number of (least significant) bits
16    /// to take into account for the exponent.
17    ///
18    /// NOTE: `exponent_bits` may be leaked in the time pattern.
19    pub fn pow_bounded_exp(&self, exponent: &BoxedUint, exponent_bits: u32) -> Self {
20        let ret = Self {
21            montgomery_form: pow_montgomery_form(
22                &self.montgomery_form,
23                exponent,
24                exponent_bits,
25                &self.params.modulus,
26                &self.params.one,
27                self.params.mod_neg_inv,
28            ),
29            params: self.params.clone(),
30        };
31
32        debug_assert!(ret.retrieve() < self.params.modulus);
33        ret
34    }
35}
36
37impl PowBoundedExp<BoxedUint> for BoxedMontyForm {
38    fn pow_bounded_exp(&self, exponent: &BoxedUint, exponent_bits: u32) -> Self {
39        self.pow_bounded_exp(exponent, exponent_bits)
40    }
41}
42
43/// Performs modular exponentiation using Montgomery's ladder.
44///
45/// `exponent_bits` represents the length of the exponent in bits.
46///
47/// NOTE: `exponent_bits` is leaked in the time pattern.
48fn pow_montgomery_form(
49    x: &BoxedUint,
50    exponent: &BoxedUint,
51    exponent_bits: u32,
52    modulus: &BoxedUint,
53    one: &BoxedUint,
54    mod_neg_inv: Limb,
55) -> BoxedUint {
56    if exponent_bits == 0 {
57        return one.clone(); // 1 in Montgomery form
58    }
59
60    const WINDOW: u32 = 4;
61    const WINDOW_MASK: Word = (1 << WINDOW) - 1;
62
63    let mut multiplier = MontyMultiplier::new(modulus, mod_neg_inv);
64
65    // powers[i] contains x^i
66    let mut powers = Vec::with_capacity(1 << WINDOW);
67    powers.push(one.clone()); // 1 in Montgomery form
68    powers.push(x.clone());
69
70    for i in 2..(1 << WINDOW) {
71        powers.push(multiplier.mul_amm(&powers[i - 1], x));
72    }
73
74    let starting_limb = ((exponent_bits - 1) / Limb::BITS) as usize;
75    let starting_bit_in_limb = (exponent_bits - 1) % Limb::BITS;
76    let starting_window = starting_bit_in_limb / WINDOW;
77    let starting_window_mask = (1 << (starting_bit_in_limb % WINDOW + 1)) - 1;
78
79    let mut z = one.clone(); // 1 in Montgomery form
80    let mut power = powers[0].clone();
81
82    for limb_num in (0..=starting_limb).rev() {
83        let w = exponent.as_limbs()[limb_num].0;
84
85        let mut window_num = if limb_num == starting_limb {
86            starting_window + 1
87        } else {
88            Limb::BITS / WINDOW
89        };
90
91        while window_num > 0 {
92            window_num -= 1;
93
94            let mut idx = (w >> (window_num * WINDOW)) & WINDOW_MASK;
95
96            if limb_num == starting_limb && window_num == starting_window {
97                idx &= starting_window_mask;
98            } else {
99                for _ in 1..=WINDOW {
100                    multiplier.square_amm_assign(&mut z);
101                }
102            }
103
104            // Constant-time lookup in the array of powers
105            power.limbs.copy_from_slice(&powers[0].limbs);
106            for i in 1..(1 << WINDOW) {
107                power.ct_assign(&powers[i as usize], i.ct_eq(&idx));
108            }
109
110            multiplier.mul_amm_assign(&mut z, &power);
111        }
112    }
113
114    // Ensure output is properly reduced: AMM only reduces to the bit length of `modulus`
115    // See RustCrypto/crypto-bigint#441
116    z.conditional_sbb_assign(modulus, !z.ct_lt(modulus));
117
118    // Subtract again to ensure output is fully reduced
119    // See RustCrypto/crypto-bigint#455 and golang.org/issue/13907
120    z.conditional_sbb_assign(modulus, !z.ct_lt(modulus));
121    debug_assert!(&z < modulus);
122
123    z
124}
crypto_bigint/modular/boxed_monty_form/pow.rs

crypto_bigint/modular/boxed_monty_form/
pow.rs
