crypto_bigint/modular/boxed_monty_form/
inv.rs

1//! Multiplicative inverses of boxed integers in Montgomery form.
2
3use super::{BoxedMontyForm, BoxedMontyParams};
4use crate::{
5    modular::BoxedSafeGcdInverter, Invert, Inverter, PrecomputeInverter,
6    PrecomputeInverterWithAdjuster,
7};
8use alloc::sync::Arc;
9use core::fmt;
10use subtle::CtOption;
11
12impl BoxedMontyForm {
13    /// Computes `self^-1` representing the multiplicative inverse of `self`,
14    /// i.e. `self * self^-1 = 1`.
15    pub fn invert(&self) -> CtOption<Self> {
16        self.params.precompute_inverter().invert(self)
17    }
18
19    /// Computes `self^-1` representing the multiplicative inverse of `self`,
20    /// i.e. `self * self^-1 = 1`.
21    ///
22    /// This version is variable-time with respect to the value of `self`, but constant-time with
23    /// respect to `self`'s `params`.
24    pub fn invert_vartime(&self) -> CtOption<Self> {
25        self.params.precompute_inverter().invert_vartime(self)
26    }
27}
28
29impl Invert for BoxedMontyForm {
30    type Output = CtOption<Self>;
31
32    fn invert(&self) -> Self::Output {
33        self.invert()
34    }
35
36    fn invert_vartime(&self) -> Self::Output {
37        self.invert_vartime()
38    }
39}
40
41impl PrecomputeInverter for BoxedMontyParams {
42    type Inverter = BoxedMontyFormInverter;
43    type Output = BoxedMontyForm;
44
45    fn precompute_inverter(&self) -> BoxedMontyFormInverter {
46        BoxedMontyFormInverter {
47            inverter: self.modulus.precompute_inverter_with_adjuster(&self.r2),
48            params: self.clone().into(),
49        }
50    }
51}
52
53/// Bernstein-Yang inverter which inverts [`DynResidue`] types.
54pub struct BoxedMontyFormInverter {
55    /// Precomputed Bernstein-Yang inverter.
56    inverter: BoxedSafeGcdInverter,
57
58    /// Residue parameters.
59    params: Arc<BoxedMontyParams>,
60}
61
62impl Inverter for BoxedMontyFormInverter {
63    type Output = BoxedMontyForm;
64
65    fn invert(&self, value: &BoxedMontyForm) -> CtOption<Self::Output> {
66        debug_assert_eq!(self.params, value.params);
67
68        let montgomery_form = self.inverter.invert(&value.montgomery_form);
69        let is_some = montgomery_form.is_some();
70        let montgomery_form2 = value.montgomery_form.clone();
71        let ret = BoxedMontyForm {
72            montgomery_form: Option::from(montgomery_form).unwrap_or(montgomery_form2),
73            params: value.params.clone(),
74        };
75
76        CtOption::new(ret, is_some)
77    }
78
79    fn invert_vartime(&self, value: &BoxedMontyForm) -> CtOption<Self::Output> {
80        debug_assert_eq!(self.params, value.params);
81
82        let montgomery_form = self.inverter.invert_vartime(&value.montgomery_form);
83        let is_some = montgomery_form.is_some();
84        let montgomery_form2 = value.montgomery_form.clone();
85        let ret = BoxedMontyForm {
86            montgomery_form: Option::from(montgomery_form).unwrap_or(montgomery_form2),
87            params: value.params.clone(),
88        };
89
90        CtOption::new(ret, is_some)
91    }
92}
93
94impl fmt::Debug for BoxedMontyFormInverter {
95    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
96        f.debug_struct("BoxedMontyFormInverter")
97            .field("modulus", &self.inverter.modulus)
98            .finish()
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use crate::{
105        modular::{BoxedMontyForm, BoxedMontyParams},
106        BoxedUint,
107    };
108    use hex_literal::hex;
109
110    fn monty_params() -> BoxedMontyParams {
111        BoxedMontyParams::new(
112            BoxedUint::from_be_slice(
113                &hex!("15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409"),
114                256,
115            )
116            .unwrap()
117            .to_odd()
118            .unwrap(),
119        )
120    }
121
122    #[test]
123    fn test_self_inverse() {
124        let params = monty_params();
125        let x = BoxedUint::from_be_slice(
126            &hex!("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685"),
127            256,
128        )
129        .unwrap();
130        let x_mod = BoxedMontyForm::new(x, params);
131
132        let inv = x_mod.invert().unwrap();
133        let res = x_mod * inv;
134
135        assert!(bool::from(res.retrieve().is_one()));
136    }
137}
crypto_bigint/modular/boxed_monty_form/inv.rs

crypto_bigint/modular/boxed_monty_form/
inv.rs
