use num_traits::{One, Zero};
use tc_bigint::{PaddedBigUint, Word};
use tc_constant_time::{Choice, ConditionallySelectable};
use super::mul::mul_residues;
use crate::wipe::replace_wiped;
use crate::{ModPow, NonZero, Odd, PaddedMontyForm, PaddedMontyParams};
use tc_zeroize::Zeroizing;
impl ModPow for PaddedBigUint {
type Output = Self;
fn mod_pow(&self, exponent: &Self, modulus: &NonZero<Self>) -> Self {
let modulus: &Self = modulus;
match Odd::new(modulus.clone()) {
Some(odd) => {
let params = Zeroizing::new(PaddedMontyParams::new(odd));
let base = Zeroizing::new(PaddedMontyForm::new(self, ¶ms));
let power = Zeroizing::new(base.pow(exponent));
let power = Zeroizing::new(power.retrieve());
let mut zero = self.clone();
zero.set_zero();
zero + &*power
}
None => pow_residues(&Zeroizing::new(self % modulus), exponent, modulus),
}
}
}
fn pow_residues(
base: &PaddedBigUint,
exponent: &PaddedBigUint,
modulus: &PaddedBigUint,
) -> PaddedBigUint {
let mut one = base.clone();
one.set_one();
let mut power = &one % modulus;
for index in (0..exponent.as_limbs().len() as u32 * Word::BITS).rev() {
let squared = mul_residues(&power, &power, modulus);
replace_wiped(&mut power, squared);
let product = Zeroizing::new(mul_residues(&power, base, modulus));
power.conditional_assign(&product, Choice::from_lsb(u8::from(exponent.bit(index))));
}
power
}
#[cfg(test)]
mod tests {
use tc_bigint::{PaddedBigUint, Word};
use crate::{ModPow, NonZero};
const VALUES: [u64; 6] = [0, 1, 2, u32::MAX as u64 + 1, i64::MAX as u64, u64::MAX];
fn expected(a: u64, e: u64, m: u64) -> u64 {
let m = u128::from(m);
let (mut base, mut power, mut e) = (u128::from(a) % m, 1 % m, e);
while e != 0 {
if e & 1 == 1 {
power = power * base % m;
}
base = base * base % m;
e >>= 1;
}
power as u64
}
#[test]
fn the_power_matches_squaring_and_multiplying_in_primitives() {
for m in &VALUES[1..] {
let modulus = NonZero::new(PaddedBigUint::from(*m)).unwrap();
for a in VALUES {
for e in VALUES {
let (x, y) = (PaddedBigUint::from(a), PaddedBigUint::from(e));
let expected = PaddedBigUint::from(expected(a, e, *m));
assert_eq!(x.mod_pow(&y, &modulus), expected, "{a} {e} {m}");
}
}
}
}
#[test]
fn a_power_of_a_prime_minus_one_is_one_as_fermat_has_it() {
let prime = i128::MAX as u128;
let modulus = NonZero::new(PaddedBigUint::from(prime)).unwrap();
let power = PaddedBigUint::from(3u8).mod_pow(&PaddedBigUint::from(prime - 1), &modulus);
assert_eq!(power, PaddedBigUint::from(1u8));
}
#[test]
fn the_result_takes_the_wider_width_of_the_base_and_the_modulus() {
let narrow = |value: u8| PaddedBigUint::from(value);
let broad = |value: u8| PaddedBigUint::from(u128::from(value));
let (one, wide) = (1, (u128::BITS / Word::BITS) as usize);
for (a, e, m, width) in [
(broad(7), narrow(5), narrow(9), wide),
(narrow(7), narrow(5), broad(9), wide),
(narrow(7), broad(5), narrow(9), one),
(broad(7), narrow(0), narrow(9), wide),
] {
let expected = if e == narrow(0) { 1u8 } else { 4 };
let power = a.mod_pow(&e, &NonZero::new(m).unwrap());
assert_eq!(
(power.as_limbs().len(), power),
(width, PaddedBigUint::from(expected))
);
}
}
}