crypto_bigint/modular/boxed_monty_form/
invert.rs

1//! Multiplicative inverses of boxed integers in Montgomery form.
2
3use super::{BoxedMontyForm, BoxedMontyParams};
4use crate::{CtOption, Invert, modular::safegcd::boxed::BoxedSafeGcdInverter};
5
6impl BoxedMontyForm {
7    /// Computes `self^-1` representing the multiplicative inverse of `self`,
8    /// i.e. `self * self^-1 = 1`.
9    #[must_use]
10    pub fn invert(&self) -> CtOption<Self> {
11        let montgomery_form = self.params.inverter().invert(&self.montgomery_form);
12        let is_some = montgomery_form.is_some();
13        let montgomery_form2 = self.montgomery_form.clone();
14        let ret = BoxedMontyForm {
15            montgomery_form: Option::from(montgomery_form).unwrap_or(montgomery_form2),
16            params: self.params.clone(),
17        };
18
19        CtOption::new(ret, is_some)
20    }
21
22    /// Computes `self^-1` representing the multiplicative inverse of `self`,
23    /// i.e. `self * self^-1 = 1`.
24    ///
25    /// This version is variable-time with respect to the self of `self`, but constant-time with
26    /// respect to `self`'s `params`.
27    #[must_use]
28    pub fn invert_vartime(&self) -> CtOption<Self> {
29        let montgomery_form = self.params.inverter().invert_vartime(&self.montgomery_form);
30        let is_some = montgomery_form.is_some();
31        let montgomery_form2 = self.montgomery_form.clone();
32        let ret = BoxedMontyForm {
33            montgomery_form: Option::from(montgomery_form).unwrap_or(montgomery_form2),
34            params: self.params.clone(),
35        };
36
37        CtOption::new(ret, is_some)
38    }
39}
40
41impl Invert for BoxedMontyForm {
42    type Output = CtOption<Self>;
43
44    fn invert(&self) -> Self::Output {
45        self.invert()
46    }
47
48    fn invert_vartime(&self) -> Self::Output {
49        self.invert_vartime()
50    }
51}
52
53impl BoxedMontyParams {
54    /// Compute the inverter for these params.
55    fn inverter(&self) -> BoxedSafeGcdInverter {
56        BoxedSafeGcdInverter::new_with_inverse(
57            self.modulus().clone(),
58            self.mod_inv(),
59            self.r2().clone(),
60        )
61    }
62}
63
64#[cfg(test)]
65mod tests {
66    use crate::{
67        BoxedUint,
68        modular::{BoxedMontyForm, BoxedMontyParams},
69    };
70    use hex_literal::hex;
71
72    fn monty_params() -> BoxedMontyParams {
73        BoxedMontyParams::new(
74            BoxedUint::from_be_slice(
75                &hex!("15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409"),
76                256,
77            )
78            .unwrap()
79            .to_odd()
80            .unwrap(),
81        )
82    }
83
84    #[test]
85    fn test_self_inverse() {
86        let params = monty_params();
87        let x = BoxedUint::from_be_slice(
88            &hex!("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685"),
89            256,
90        )
91        .unwrap();
92        let x_mod = BoxedMontyForm::new(x, &params);
93
94        let inv = x_mod.invert().unwrap();
95        let res = x_mod * inv;
96
97        assert!(bool::from(res.retrieve().is_one()));
98    }
99}
crypto_bigint/modular/boxed_monty_form/invert.rs

crypto_bigint/modular/boxed_monty_form/
invert.rs
