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
80
//! Exponentiation of [`FixedMontyForm`].
use tc_bigint::{FixedBigUint, Word};
use tc_constant_time::{Choice, ConditionallySelectable};
use super::FixedMontyForm;
use crate::wipe::replace_wiped;
use tc_zeroize::Zeroizing;
impl<const N: usize> FixedMontyForm<N> {
/// `self` to the power `exponent`: from the top bit of the `N` limbs of
/// `exponent` down, the power is squared and multiplied by `self` at
/// every bit, and the product kept where the bit is set, through a
/// constant-time select. Constant time in both operands, for a secret
/// exponent.
pub fn pow(&self, exponent: &FixedBigUint<N>) -> Self {
let mut power = Self::one(self.params.clone());
for index in (0..N as u32 * Word::BITS).rev() {
// The square takes the place of the power, which is wiped.
let squared = power.square();
replace_wiped(&mut power, squared);
let product = Zeroizing::new(&power * self);
let bit = Choice::from_lsb(u8::from(exponent.bit(index)));
power.value.conditional_assign(&product.value, bit);
}
power
}
/// `self` to the power `exponent`, squaring from the top set bit of
/// `exponent` down and multiplying only where a bit is set. Variable
/// time: only for a public exponent, as that of an RSA public key is; a
/// secret one goes through [`pow`](Self::pow).
pub fn pow_vartime(&self, exponent: &FixedBigUint<N>) -> Self {
let mut power = Self::one(self.params.clone());
for index in (0..exponent.bits()).rev() {
// The square takes the place of the power, which is wiped.
let squared = power.square();
replace_wiped(&mut power, squared);
if exponent.bit(index) {
power *= self;
}
}
power
}
}
#[cfg(test)]
mod tests {
use super::super::testing::{MODULI, VALUES, form, int, mul_mod};
/// `a` to the power `e`, mod `m`, by squaring from the low bit up.
fn pow_mod(a: u64, e: u64, m: u64) -> u64 {
let (mut base, mut power, mut e) = (a % m, 1 % m, e);
while e != 0 {
if e & 1 == 1 {
power = mul_mod(power, base, m);
}
base = mul_mod(base, base, m);
e >>= 1;
}
power
}
#[test]
fn both_powers_match_squaring_and_multiplying_in_primitives() {
for m in MODULI {
for a in VALUES {
for e in VALUES {
let expected = int(pow_mod(a, e, m));
assert_eq!(form(a, m).pow(&int(e)).retrieve(), expected, "{a} {e} {m}");
assert_eq!(
form(a, m).pow_vartime(&int(e)).retrieve(),
expected,
"{a} {e} {m}"
);
}
}
}
}
}