crypto_bigint/modular/
pow.rs

1use super::mul::{mul_montgomery_form, square_montgomery_form};
2use crate::{ConstChoice, Limb, Odd, Uint, Word};
3
4#[cfg(feature = "alloc")]
5use alloc::vec::Vec;
6
7const WINDOW: u32 = 4;
8const WINDOW_MASK: Word = (1 << WINDOW) - 1;
9
10/// Performs modular exponentiation using Montgomery's ladder.
11/// `exponent_bits` represents the number of bits to take into account for the exponent.
12///
13/// NOTE: this value is leaked in the time pattern.
14pub const fn pow_montgomery_form<const LIMBS: usize, const RHS_LIMBS: usize>(
15    x: &Uint<LIMBS>,
16    exponent: &Uint<RHS_LIMBS>,
17    exponent_bits: u32,
18    modulus: &Odd<Uint<LIMBS>>,
19    one: &Uint<LIMBS>,
20    mod_neg_inv: Limb,
21) -> Uint<LIMBS> {
22    multi_exponentiate_montgomery_form_array(
23        &[(*x, *exponent)],
24        exponent_bits,
25        modulus,
26        one,
27        mod_neg_inv,
28    )
29}
30
31pub const fn multi_exponentiate_montgomery_form_array<
32    const LIMBS: usize,
33    const RHS_LIMBS: usize,
34    const N: usize,
35>(
36    bases_and_exponents: &[(Uint<LIMBS>, Uint<RHS_LIMBS>); N],
37    exponent_bits: u32,
38    modulus: &Odd<Uint<LIMBS>>,
39    one: &Uint<LIMBS>,
40    mod_neg_inv: Limb,
41) -> Uint<LIMBS> {
42    if exponent_bits == 0 {
43        return *one; // 1 in Montgomery form
44    }
45
46    let mut powers_and_exponents =
47        [([Uint::<LIMBS>::ZERO; 1 << WINDOW], Uint::<RHS_LIMBS>::ZERO); N];
48
49    let mut i = 0;
50    while i < N {
51        let (base, exponent) = bases_and_exponents[i];
52        powers_and_exponents[i] = (compute_powers(&base, modulus, one, mod_neg_inv), exponent);
53        i += 1;
54    }
55
56    multi_exponentiate_montgomery_form_internal(
57        &powers_and_exponents,
58        exponent_bits,
59        modulus,
60        one,
61        mod_neg_inv,
62    )
63}
64
65/// Performs modular multi-exponentiation using Montgomery's ladder.
66/// `exponent_bits` represents the number of bits to take into account for the exponent.
67///
68/// See: Straus, E. G. Problems and solutions: Addition chains of vectors. American Mathematical Monthly 71 (1964), 806–808.
69///
70/// NOTE: this value is leaked in the time pattern.
71#[cfg(feature = "alloc")]
72pub fn multi_exponentiate_montgomery_form_slice<const LIMBS: usize, const RHS_LIMBS: usize>(
73    bases_and_exponents: &[(Uint<LIMBS>, Uint<RHS_LIMBS>)],
74    exponent_bits: u32,
75    modulus: &Odd<Uint<LIMBS>>,
76    one: &Uint<LIMBS>,
77    mod_neg_inv: Limb,
78) -> Uint<LIMBS> {
79    if exponent_bits == 0 {
80        return *one; // 1 in Montgomery form
81    }
82
83    let powers_and_exponents: Vec<([Uint<LIMBS>; 1 << WINDOW], Uint<RHS_LIMBS>)> =
84        bases_and_exponents
85            .iter()
86            .map(|(base, exponent)| (compute_powers(base, modulus, one, mod_neg_inv), *exponent))
87            .collect();
88
89    multi_exponentiate_montgomery_form_internal(
90        powers_and_exponents.as_slice(),
91        exponent_bits,
92        modulus,
93        one,
94        mod_neg_inv,
95    )
96}
97
98const fn compute_powers<const LIMBS: usize>(
99    x: &Uint<LIMBS>,
100    modulus: &Odd<Uint<LIMBS>>,
101    one: &Uint<LIMBS>,
102    mod_neg_inv: Limb,
103) -> [Uint<LIMBS>; 1 << WINDOW] {
104    // powers[i] contains x^i
105    let mut powers = [*one; 1 << WINDOW];
106    powers[1] = *x;
107
108    let mut i = 2;
109    while i < powers.len() {
110        powers[i] = mul_montgomery_form(&powers[i - 1], x, modulus, mod_neg_inv);
111        i += 1;
112    }
113
114    powers
115}
116
117const fn multi_exponentiate_montgomery_form_internal<const LIMBS: usize, const RHS_LIMBS: usize>(
118    powers_and_exponents: &[([Uint<LIMBS>; 1 << WINDOW], Uint<RHS_LIMBS>)],
119    exponent_bits: u32,
120    modulus: &Odd<Uint<LIMBS>>,
121    one: &Uint<LIMBS>,
122    mod_neg_inv: Limb,
123) -> Uint<LIMBS> {
124    let starting_limb = ((exponent_bits - 1) / Limb::BITS) as usize;
125    let starting_bit_in_limb = (exponent_bits - 1) % Limb::BITS;
126    let starting_window = starting_bit_in_limb / WINDOW;
127    let starting_window_mask = (1 << (starting_bit_in_limb % WINDOW + 1)) - 1;
128
129    let mut z = *one; // 1 in Montgomery form
130
131    let mut limb_num = starting_limb + 1;
132    while limb_num > 0 {
133        limb_num -= 1;
134
135        let mut window_num = if limb_num == starting_limb {
136            starting_window + 1
137        } else {
138            Limb::BITS / WINDOW
139        };
140        while window_num > 0 {
141            window_num -= 1;
142
143            if limb_num != starting_limb || window_num != starting_window {
144                let mut i = 0;
145                while i < WINDOW {
146                    i += 1;
147                    z = square_montgomery_form(&z, modulus, mod_neg_inv);
148                }
149            }
150
151            let mut i = 0;
152            while i < powers_and_exponents.len() {
153                let (powers, exponent) = powers_and_exponents[i];
154                let w = exponent.as_limbs()[limb_num].0;
155                let mut idx = (w >> (window_num * WINDOW)) & WINDOW_MASK;
156
157                if limb_num == starting_limb && window_num == starting_window {
158                    idx &= starting_window_mask;
159                }
160
161                // Constant-time lookup in the array of powers
162                let mut power = powers[0];
163                let mut j = 1;
164                while j < 1 << WINDOW {
165                    let choice = ConstChoice::from_word_eq(j, idx);
166                    power = Uint::<LIMBS>::select(&power, &powers[j as usize], choice);
167                    j += 1;
168                }
169
170                z = mul_montgomery_form(&z, &power, modulus, mod_neg_inv);
171                i += 1;
172            }
173        }
174    }
175
176    z
177}
crypto_bigint/modular/pow.rs

crypto_bigint/modular/
pow.rs
