crypto_bigint/modular/fixed_monty_form/
pow.rs

1//! Exponentiation of integers in Montgomery form with a modulus set at runtime.
2
3use super::FixedMontyForm;
4use crate::{
5    MultiExponentiateBoundedExp, PowBoundedExp, Uint,
6    modular::pow::{
7        multi_exponentiate_montgomery_form_array, pow_montgomery_form, pow_montgomery_form_amm,
8    },
9};
10
11#[cfg(feature = "alloc")]
12use {crate::modular::pow::multi_exponentiate_montgomery_form_slice, alloc::vec::Vec};
13
14impl<const LIMBS: usize> FixedMontyForm<LIMBS> {
15    /// Raises to the `exponent` power.
16    #[must_use]
17    pub const fn pow<const RHS_LIMBS: usize>(&self, exponent: &Uint<RHS_LIMBS>) -> Self {
18        self.pow_bounded_exp(exponent, Uint::<RHS_LIMBS>::BITS)
19    }
20
21    /// Raises to the `exponent` power,
22    /// with `exponent_bits` representing the number of (least significant) bits
23    /// to take into account for the exponent.
24    ///
25    /// NOTE: `exponent_bits` may be leaked in the time pattern.
26    #[must_use]
27    pub const fn pow_bounded_exp<const RHS_LIMBS: usize>(
28        &self,
29        exponent: &Uint<RHS_LIMBS>,
30        exponent_bits: u32,
31    ) -> Self {
32        Self {
33            montgomery_form: pow_montgomery_form::<LIMBS, RHS_LIMBS, false>(
34                &self.montgomery_form,
35                exponent,
36                exponent_bits,
37                &self.params,
38            ),
39            params: self.params,
40        }
41    }
42
43    /// Raises to the `exponent` power.
44    ///
45    /// This method is variable time in `exponent`.
46    #[must_use]
47    pub const fn pow_vartime<const RHS_LIMBS: usize>(&self, exponent: &Uint<RHS_LIMBS>) -> Self {
48        let exponent_bits = exponent.bits_vartime();
49        Self {
50            montgomery_form: pow_montgomery_form::<LIMBS, RHS_LIMBS, true>(
51                &self.montgomery_form,
52                exponent,
53                exponent_bits,
54                &self.params,
55            ),
56            params: self.params,
57        }
58    }
59
60    /// Raises to the `exponent` power using Almost Montgomery Multiplication (AMM).
61    #[must_use]
62    pub fn pow_amm(&self, exponent: &Uint<LIMBS>) -> Self {
63        self.pow_amm_bounded_exp(exponent, Uint::<LIMBS>::BITS)
64    }
65
66    /// Raises to the `exponent` power using Almost Montgomery Multiplication (AMM)
67    /// with `exponent_bits` representing the number of (least significant) bits
68    /// to take into account for the exponent.
69    ///
70    /// NOTE: `exponent_bits` may be leaked in the time pattern.
71    #[must_use]
72    pub fn pow_amm_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: u32) -> Self {
73        Self {
74            montgomery_form: pow_montgomery_form_amm(
75                &self.montgomery_form,
76                exponent,
77                exponent_bits,
78                &self.params,
79            ),
80            params: self.params,
81        }
82    }
83}
84
85impl<const LIMBS: usize, const RHS_LIMBS: usize> PowBoundedExp<Uint<RHS_LIMBS>>
86    for FixedMontyForm<LIMBS>
87{
88    fn pow_bounded_exp(&self, exponent: &Uint<RHS_LIMBS>, exponent_bits: u32) -> Self {
89        self.pow_bounded_exp(exponent, exponent_bits)
90    }
91}
92
93impl<const N: usize, const LIMBS: usize, const RHS_LIMBS: usize>
94    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>); N]>
95    for FixedMontyForm<LIMBS>
96{
97    fn multi_exponentiate_bounded_exp(
98        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>); N],
99        exponent_bits: u32,
100    ) -> Self {
101        assert!(N != 0, "bases_and_exponents must not be empty");
102        let params = bases_and_exponents[0].0.params;
103
104        let mut bases_and_exponents_montgomery_form =
105            [(Uint::<LIMBS>::ZERO, Uint::<RHS_LIMBS>::ZERO); N];
106
107        let mut i = 0;
108        while i < N {
109            let (base, exponent) = bases_and_exponents[i];
110            bases_and_exponents_montgomery_form[i] = (base.montgomery_form, exponent);
111            i += 1;
112        }
113
114        Self {
115            montgomery_form: multi_exponentiate_montgomery_form_array::<LIMBS, RHS_LIMBS, N, false>(
116                &bases_and_exponents_montgomery_form,
117                exponent_bits,
118                &params,
119            ),
120            params,
121        }
122    }
123}
124
125#[cfg(feature = "alloc")]
126impl<const LIMBS: usize, const RHS_LIMBS: usize>
127    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>)]>
128    for FixedMontyForm<LIMBS>
129{
130    fn multi_exponentiate_bounded_exp(
131        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>)],
132        exponent_bits: u32,
133    ) -> Self {
134        assert!(
135            !bases_and_exponents.is_empty(),
136            "bases_and_exponents must not be empty"
137        );
138        let params = bases_and_exponents[0].0.params;
139
140        let bases_and_exponents: Vec<(Uint<LIMBS>, Uint<RHS_LIMBS>)> = bases_and_exponents
141            .iter()
142            .map(|(base, exp)| (base.montgomery_form, *exp))
143            .collect();
144        Self {
145            montgomery_form: multi_exponentiate_montgomery_form_slice::<LIMBS, RHS_LIMBS, false>(
146                &bases_and_exponents,
147                exponent_bits,
148                &params,
149            ),
150            params,
151        }
152    }
153}
154
155#[cfg(test)]
156mod tests {
157    use crate::{
158        U64, U256,
159        modular::{FixedMontyForm, FixedMontyParams},
160        traits::MultiExponentiate,
161    };
162
163    const PARAMS: FixedMontyParams<{ U256::LIMBS }> = FixedMontyParams::new_vartime(
164        U256::from_be_hex("9CC24C5DF431A864188AB905AC751B727C9447A8E99E6366E1AD78A21E8D882B")
165            .to_odd()
166            .expect_copied("ensured odd"),
167    );
168
169    #[test]
170    fn test_powmod_zero() {
171        let base = U256::from(105u64);
172        let base_mod = FixedMontyForm::new(&base, &PARAMS);
173
174        let res = base_mod.pow(&U256::ZERO);
175        let res_vartime = base_mod.pow_vartime(&U256::ZERO);
176
177        assert_eq!(res.retrieve(), U256::ONE);
178        assert_eq!(res_vartime.retrieve(), U256::ONE);
179    }
180
181    #[test]
182    fn test_powmod_small_base() {
183        let base = U256::from(105u64);
184        let base_mod = FixedMontyForm::new(&base, &PARAMS);
185
186        let exponent =
187            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
188
189        let res = base_mod.pow(&exponent);
190        let res_vartime = base_mod.pow_vartime(&exponent);
191
192        let expected =
193            U256::from_be_hex("7B2CD7BDDD96C271E6F232F2F415BB03FE2A90BD6CCCEA5E94F1BFD064993766");
194        assert_eq!(res.retrieve(), expected);
195        assert_eq!(res_vartime.retrieve(), expected);
196    }
197
198    #[test]
199    fn test_powmod_small_exponent() {
200        let base =
201            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
202        let base_mod = FixedMontyForm::new(&base, &PARAMS);
203
204        let exponent = U256::from(105u64);
205
206        let res = base_mod.pow(&exponent);
207        let res_vartime = base_mod.pow_vartime(&exponent);
208
209        let expected =
210            U256::from_be_hex("89E2A4E99F649A5AE2C18068148C355CA927B34A3245C938178ED00D6EF218AA");
211        assert_eq!(res.retrieve(), expected);
212        assert_eq!(res_vartime.retrieve(), expected);
213    }
214
215    #[test]
216    fn test_powmod() {
217        let base =
218            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
219        let base_mod = FixedMontyForm::new(&base, &PARAMS);
220
221        let exponent =
222            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
223
224        let res = base_mod.pow(&exponent);
225        let res_vartime = base_mod.pow_vartime(&exponent);
226
227        let expected =
228            U256::from_be_hex("3681BC0FEA2E5D394EB178155A127B0FD2EF405486D354251C385BDD51B9D421");
229        assert_eq!(res.retrieve(), expected);
230        assert_eq!(res_vartime.retrieve(), expected);
231    }
232
233    #[test]
234    fn issue_1343_regression_test() {
235        let modulus = U64::from_u64(0x7241_9be3_5d7d_03fb).to_odd().unwrap();
236
237        let params = FixedMontyParams::new_vartime(modulus);
238        let x = FixedMontyForm::new(&U64::from_u64(13480), &params);
239        let exponent = U64::from_u64(16);
240
241        let ct = x.pow(&exponent);
242        let vt = x.pow_vartime(&exponent);
243
244        assert_eq!(ct, vt);
245    }
246
247    #[test]
248    fn test_multi_exp_array() {
249        let base = U256::from(2u8);
250        let base_mod = FixedMontyForm::new(&base, &PARAMS);
251
252        let exponent = U256::from(33u8);
253        let bases_and_exponents = [(base_mod, exponent)];
254        let res = FixedMontyForm::<{ U256::LIMBS }>::multi_exponentiate(&bases_and_exponents);
255
256        let expected =
257            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000200000000");
258
259        assert_eq!(res.retrieve(), expected);
260
261        let base2 =
262            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
263        let base2_mod = FixedMontyForm::new(&base2, &PARAMS);
264
265        let exponent2 =
266            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
267
268        let expected = base_mod.pow(&exponent) * base2_mod.pow(&exponent2);
269        let bases_and_exponents = [(base_mod, exponent), (base2_mod, exponent2)];
270        let res = FixedMontyForm::<{ U256::LIMBS }>::multi_exponentiate(&bases_and_exponents);
271
272        assert_eq!(res, expected);
273    }
274
275    #[cfg(feature = "alloc")]
276    #[test]
277    fn test_multi_exp_slice() {
278        let base = U256::from(2u8);
279        let base_mod = FixedMontyForm::new(&base, &PARAMS);
280
281        let exponent = U256::from(33u8);
282        let bases_and_exponents = vec![(base_mod, exponent)];
283        let res =
284            FixedMontyForm::<{ U256::LIMBS }>::multi_exponentiate(bases_and_exponents.as_slice());
285
286        let expected =
287            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000200000000");
288
289        assert_eq!(res.retrieve(), expected);
290
291        let base2 =
292            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
293        let base2_mod = FixedMontyForm::new(&base2, &PARAMS);
294
295        let exponent2 =
296            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
297
298        let expected = base_mod.pow(&exponent) * base2_mod.pow(&exponent2);
299        let bases_and_exponents = vec![(base_mod, exponent), (base2_mod, exponent2)];
300        let res =
301            FixedMontyForm::<{ U256::LIMBS }>::multi_exponentiate(bases_and_exponents.as_slice());
302
303        assert_eq!(res, expected);
304    }
305}
crypto_bigint/modular/fixed_monty_form/pow.rs

crypto_bigint/modular/fixed_monty_form/
pow.rs
