crypto_bigint/uint/modular/
pow.rs

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

crypto_bigint/uint/modular/
pow.rs
