crypto_bigint/modular/
boxed_monty_form.rs

1//! Implements heap-allocated `BoxedMontyForm`s, supporting modular arithmetic with a modulus set at runtime.
2
3mod add;
4mod ct;
5mod from;
6mod invert;
7mod lincomb;
8mod mul;
9mod neg;
10mod pow;
11mod sub;
12
13use super::{
14    BoxedMontyParams, Retrieve, div_by_2, monty_params::MontyParams,
15    reduction::montgomery_retrieve_inner,
16};
17use crate::{BoxedUint, Choice, MontyForm, Odd};
18use mul::BoxedMontyMultiplier;
19
20#[cfg(feature = "zeroize")]
21use zeroize::Zeroize;
22
23/// An integer in Montgomery form represented using heap-allocated limbs.
24#[derive(Clone, Debug, Eq, PartialEq)]
25pub struct BoxedMontyForm {
26    /// Value in the Montgomery form.
27    montgomery_form: BoxedUint,
28
29    /// Montgomery form parameters.
30    params: BoxedMontyParams,
31}
32
33impl BoxedMontyForm {
34    /// Instantiates a new [`BoxedMontyForm`] that represents an integer modulo the provided params.
35    #[must_use]
36    pub fn new(mut integer: BoxedUint, params: &BoxedMontyParams) -> Self {
37        debug_assert_eq!(integer.bits_precision(), params.bits_precision());
38        convert_to_montgomery(&mut integer, params);
39
40        Self {
41            montgomery_form: integer,
42            params: params.clone(),
43        }
44    }
45
46    /// Bits of precision in the modulus.
47    #[must_use]
48    pub fn bits_precision(&self) -> u32 {
49        self.params.bits_precision()
50    }
51
52    /// Retrieves the integer currently encoded in this [`BoxedMontyForm`], guaranteed to be reduced.
53    #[must_use]
54    pub fn retrieve(&self) -> BoxedUint {
55        let mut out = BoxedUint::zero_with_precision(self.bits_precision());
56        montgomery_retrieve_inner(
57            &self.montgomery_form.limbs,
58            &mut out.limbs,
59            self.params.modulus().as_ref().as_limbs(),
60            self.params.mod_neg_inv(),
61        );
62        out
63    }
64
65    /// Instantiates a new `ConstMontyForm` that represents zero.
66    #[must_use]
67    pub fn zero(params: &BoxedMontyParams) -> Self {
68        Self {
69            montgomery_form: BoxedUint::zero_with_precision(params.bits_precision()),
70            params: params.clone(),
71        }
72    }
73
74    /// Instantiates a new `ConstMontyForm` that represents 1.
75    #[must_use]
76    pub fn one(params: &BoxedMontyParams) -> Self {
77        Self {
78            montgomery_form: params.one().clone(),
79            params: params.clone(),
80        }
81    }
82
83    /// Determine if this value is equal to zero.
84    ///
85    /// # Returns
86    ///
87    /// If zero, returns `Choice(1)`. Otherwise, returns `Choice(0)`.
88    #[must_use]
89    pub fn is_zero(&self) -> Choice {
90        self.montgomery_form.is_zero()
91    }
92
93    /// Determine if this value is not equal to zero.
94    ///
95    /// # Returns
96    ///
97    /// If zero, returns `Choice(0)`. Otherwise, returns `Choice(1)`.
98    #[inline]
99    #[must_use]
100    pub fn is_nonzero(&self) -> Choice {
101        !self.is_zero()
102    }
103
104    /// Returns the parameter struct used to initialize this object.
105    #[must_use]
106    pub fn params(&self) -> &BoxedMontyParams {
107        &self.params
108    }
109
110    /// Access the [`BoxedMontyForm`] value in Montgomery form.
111    #[must_use]
112    pub fn as_montgomery(&self) -> &BoxedUint {
113        debug_assert!(&self.montgomery_form < self.params.modulus());
114        &self.montgomery_form
115    }
116
117    /// Mutably access the [`BoxedMontyForm`] value in Montgomery form.
118    pub fn as_montgomery_mut(&mut self) -> &mut BoxedUint {
119        &mut self.montgomery_form
120    }
121
122    /// Create a [`BoxedMontyForm`] from a value in Montgomery form.
123    #[must_use]
124    pub fn from_montgomery(integer: BoxedUint, params: &BoxedMontyParams) -> Self {
125        debug_assert_eq!(integer.bits_precision(), params.bits_precision());
126        Self {
127            montgomery_form: integer,
128            params: params.clone(),
129        }
130    }
131
132    /// Extract the value from the [`BoxedMontyForm`] in Montgomery form.
133    #[must_use]
134    pub fn to_montgomery(&self) -> BoxedUint {
135        debug_assert!(&self.montgomery_form < self.params.modulus());
136        self.montgomery_form.clone()
137    }
138
139    /// Performs division by 2, that is returns `x` such that `x + x = self`.
140    #[must_use]
141    pub fn div_by_2(&self) -> Self {
142        Self {
143            montgomery_form: div_by_2::div_by_2_boxed(&self.montgomery_form, self.params.modulus()),
144            params: self.params.clone(),
145        }
146    }
147
148    /// Performs division by 2 inplace, that is finds `x` such that `x + x = self`
149    /// and writes it into `self`.
150    pub fn div_by_2_assign(&mut self) {
151        div_by_2::div_by_2_boxed_assign(&mut self.montgomery_form, self.params.modulus());
152    }
153}
154
155impl Retrieve for BoxedMontyForm {
156    type Output = BoxedUint;
157    fn retrieve(&self) -> BoxedUint {
158        self.retrieve()
159    }
160}
161
162impl MontyForm for BoxedMontyForm {
163    type Integer = BoxedUint;
164    type Params = BoxedMontyParams;
165    type Multiplier<'a> = BoxedMontyMultiplier<'a>;
166
167    fn new_params_vartime(modulus: Odd<Self::Integer>) -> Self::Params {
168        BoxedMontyParams::new_vartime(modulus)
169    }
170
171    fn new(value: Self::Integer, params: &Self::Params) -> Self {
172        BoxedMontyForm::new(value, params)
173    }
174
175    fn zero(params: &Self::Params) -> Self {
176        BoxedMontyForm::zero(params)
177    }
178
179    fn one(params: &Self::Params) -> Self {
180        BoxedMontyForm::one(params)
181    }
182
183    fn params(&self) -> &Self::Params {
184        &self.params
185    }
186
187    fn as_montgomery(&self) -> &Self::Integer {
188        &self.montgomery_form
189    }
190
191    fn copy_montgomery_from(&mut self, other: &Self) {
192        debug_assert_eq!(
193            self.montgomery_form.bits_precision(),
194            other.montgomery_form.bits_precision()
195        );
196        debug_assert_eq!(self.params, other.params);
197        self.montgomery_form
198            .limbs
199            .copy_from_slice(&other.montgomery_form.limbs);
200    }
201
202    fn into_montgomery(self) -> Self::Integer {
203        self.montgomery_form
204    }
205
206    fn double(&self) -> Self {
207        BoxedMontyForm::double(self)
208    }
209
210    fn div_by_2(&self) -> Self {
211        BoxedMontyForm::div_by_2(self)
212    }
213
214    fn div_by_2_assign(&mut self) {
215        BoxedMontyForm::div_by_2_assign(self);
216    }
217
218    fn lincomb_vartime(products: &[(&Self, &Self)]) -> Self {
219        BoxedMontyForm::lincomb_vartime(products)
220    }
221}
222
223/// NOTE: This zeroizes the value, but _not_ the associated parameters!
224#[cfg(feature = "zeroize")]
225impl Zeroize for BoxedMontyForm {
226    fn zeroize(&mut self) {
227        self.montgomery_form.zeroize();
228    }
229}
230
231/// Convert the given integer into the Montgomery domain.
232#[inline]
233fn convert_to_montgomery(integer: &mut BoxedUint, params: &BoxedMontyParams) {
234    let mut mm = BoxedMontyMultiplier::from(params);
235    mm.mul_assign(integer, params.r2());
236}
237
238#[cfg(test)]
239mod tests {
240    use super::{BoxedMontyForm, BoxedMontyParams};
241    use crate::{BoxedUint, Limb, Odd};
242
243    #[test]
244    fn new_params_with_valid_modulus() {
245        let modulus = Odd::new(BoxedUint::from(3u8)).unwrap();
246        let params = BoxedMontyParams::new(modulus);
247
248        assert_eq!(params.mod_leading_zeros(), Limb::BITS - 2);
249    }
250
251    #[test]
252    fn div_by_2() {
253        let modulus = Odd::new(BoxedUint::from(9u8)).unwrap();
254        let params = BoxedMontyParams::new(modulus);
255        let zero = BoxedMontyForm::zero(&params);
256        let one = BoxedMontyForm::one(&params);
257        let two = one.add(&one);
258
259        assert_eq!(zero.div_by_2(), zero);
260        assert_eq!(one.div_by_2().mul(&two), one);
261    }
262
263    #[test]
264    fn as_montgomery_mut() {
265        let modulus = Odd::new(BoxedUint::from(9u8)).unwrap();
266        let params = BoxedMontyParams::new(modulus);
267        let one = BoxedMontyForm::one(&params);
268        let two = one.add(&one);
269        let four = two.mul(&two);
270        let mut x = two.clone();
271
272        *x.as_montgomery_mut() = four.as_montgomery().clone();
273
274        assert_eq!(x, four);
275    }
276}
crypto_bigint/modular/boxed_monty_form.rs

crypto_bigint/modular/
boxed_monty_form.rs
