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
81
82
83
//! Modular exponentiation for [`U256`].
//!
//! Dispatches to `pow_mod_ct` (constant-time, always 256 iterations) when the
//! `ct-pow` feature is enabled, or `pow_mod_vt` (variable-time, `bit_len`-based
//! loop) by default.
use super::U256;
impl U256 {
/// Computes `self^exp mod modulus` via square-and-multiply.
///
/// With the `ct-pow` feature enabled, this is constant-time (always 256
/// iterations, unconditional multiply + `ct_select`). Without the feature,
/// this is variable-time (loop count depends on `exp.bit_len()` and
/// multiplies are conditional on exponent bits).
///
/// Returns 1 when `exp` is zero (for any base, including zero), matching
/// the mathematical convention `0^0 = 1`.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
///
/// let p = U256::from_be_limbs([
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
/// ]);
/// let base = U256::from_be_limbs([0, 0, 0, 2]);
/// let exp = U256::from_be_limbs([0, 0, 0, 10]);
/// assert_eq!(base.pow_mod(&exp, &p), U256::from_be_limbs([0, 0, 0, 1024]));
/// ```
#[inline]
pub fn pow_mod(&self, exp: &U256, modulus: &U256) -> U256 {
#[cfg(feature = "ct-pow")]
{ self.pow_mod_ct(exp, modulus) }
#[cfg(not(feature = "ct-pow"))]
{ self.pow_mod_vt(exp, modulus) }
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
const P: U256 = U256::from_be_limbs([
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
]);
/// Dispatcher produces the same result as the VT variant.
#[test]
fn matches_vt() {
let cases = [
(U256::from_be_limbs([0, 0, 0, 2]), U256::from_be_limbs([0, 0, 0, 10])),
(U256::from_be_limbs([0, 0, 0, 42]), U256::ZERO),
(U256::from_be_limbs([0, 0, 0, 7]), P - U256::ONE),
(U256::ZERO, U256::ZERO),
];
for (base, exp) in &cases {
assert_eq!(base.pow_mod(exp, &P), base.pow_mod_vt(exp, &P));
}
}
/// bit() helper returns correct values (relocated from old pow_mod).
#[test]
fn bit_helper() {
let v = U256::from_be_limbs([0, 0, 0, 0b1010]);
assert!(!v.bit(0));
assert!(v.bit(1));
assert!(!v.bit(2));
assert!(v.bit(3));
assert!(!v.bit(4));
}
/// bit() works across limb boundaries (relocated from old pow_mod).
#[test]
fn bit_cross_limb() {
let v = U256::from_be_limbs([1, 0, 0, 0]);
assert!(v.bit(192));
assert!(!v.bit(191));
assert!(!v.bit(193));
}
}