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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
use crate::{Limb, Uint, Word};
use super::mul::{mul_montgomery_form, square_montgomery_form};
/// Performs modular exponentiation using Montgomery's ladder.
/// `exponent_bits` represents the number of bits to take into account for the exponent.
///
/// NOTE: this value is leaked in the time pattern.
pub const fn pow_montgomery_form<const LIMBS: usize, const RHS_LIMBS: usize>(
x: &Uint<LIMBS>,
exponent: &Uint<RHS_LIMBS>,
exponent_bits: usize,
modulus: &Uint<LIMBS>,
r: &Uint<LIMBS>,
mod_neg_inv: Limb,
) -> Uint<LIMBS> {
if exponent_bits == 0 {
return *r; // 1 in Montgomery form
}
const WINDOW: usize = 4;
const WINDOW_MASK: Word = (1 << WINDOW) - 1;
// powers[i] contains x^i
let mut powers = [*r; 1 << WINDOW];
powers[1] = *x;
let mut i = 2;
while i < powers.len() {
powers[i] = mul_montgomery_form(&powers[i - 1], x, modulus, mod_neg_inv);
i += 1;
}
let starting_limb = (exponent_bits - 1) / Limb::BITS;
let starting_bit_in_limb = (exponent_bits - 1) % Limb::BITS;
let starting_window = starting_bit_in_limb / WINDOW;
let starting_window_mask = (1 << (starting_bit_in_limb % WINDOW + 1)) - 1;
let mut z = *r; // 1 in Montgomery form
let mut limb_num = starting_limb + 1;
while limb_num > 0 {
limb_num -= 1;
let w = exponent.as_limbs()[limb_num].0;
let mut window_num = if limb_num == starting_limb {
starting_window + 1
} else {
Limb::BITS / WINDOW
};
while window_num > 0 {
window_num -= 1;
let mut idx = (w >> (window_num * WINDOW)) & WINDOW_MASK;
if limb_num == starting_limb && window_num == starting_window {
idx &= starting_window_mask;
} else {
let mut i = 0;
while i < WINDOW {
i += 1;
z = square_montgomery_form(&z, modulus, mod_neg_inv);
}
}
// Constant-time lookup in the array of powers
let mut power = powers[0];
let mut i = 1;
while i < 1 << WINDOW {
let choice = Limb::ct_eq(Limb(i as Word), Limb(idx));
power = Uint::<LIMBS>::ct_select(&power, &powers[i], choice);
i += 1;
}
z = mul_montgomery_form(&z, &power, modulus, mod_neg_inv);
}
}
z
}
|
