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 inv;
5mod lincomb;
6mod mul;
7mod neg;
8mod pow;
9mod sub;
10
11use super::{
12    div_by_2,
13    reduction::{montgomery_reduction_boxed, montgomery_reduction_boxed_mut},
14    ConstMontyParams, Retrieve,
15};
16use crate::{BoxedUint, Limb, Monty, Odd, Word};
17use alloc::sync::Arc;
18use subtle::Choice;
19
20#[cfg(feature = "zeroize")]
21use zeroize::Zeroize;
22
23/// Parameters to efficiently go to/from the Montgomery form for an odd modulus whose size and value
24/// are both chosen at runtime.
25#[derive(Clone, Debug, Eq, PartialEq)]
26pub struct BoxedMontyParams {
27    /// The constant modulus
28    modulus: Odd<BoxedUint>,
29    /// Parameter used in Montgomery reduction
30    one: BoxedUint,
31    /// R^2, used to move into Montgomery form
32    r2: BoxedUint,
33    /// R^3, used to compute the multiplicative inverse
34    r3: BoxedUint,
35    /// The lowest limbs of -(MODULUS^-1) mod R
36    /// We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS.
37    mod_neg_inv: Limb,
38    /// Leading zeros in the modulus, used to choose optimized algorithms
39    mod_leading_zeros: u32,
40}
41
42impl BoxedMontyParams {
43    /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`, which
44    /// must be odd.
45    ///
46    /// Returns a `CtOption` that is `None` if the provided modulus is not odd.
47    /// TODO(tarcieri): DRY out with `MontyParams::new`?
48    pub fn new(modulus: Odd<BoxedUint>) -> Self {
49        let bits_precision = modulus.bits_precision();
50
51        // `R mod modulus` where `R = 2^BITS`.
52        // Represents 1 in Montgomery form.
53        let one = BoxedUint::max(bits_precision)
54            .rem(modulus.as_nz_ref())
55            .wrapping_add(&BoxedUint::one());
56
57        // `R^2 mod modulus`, used to convert integers to Montgomery form.
58        let r2 = one
59            .square()
60            .rem(&modulus.as_nz_ref().widen(bits_precision * 2))
61            .shorten(bits_precision);
62
63        Self::new_inner(modulus, one, r2)
64    }
65
66    /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`, which
67    /// must be odd. This version operates in variable-time with respect to the modulus.
68    ///
69    /// Returns `None` if the provided modulus is not odd.
70    /// TODO(tarcieri): DRY out with `MontyParams::new`?
71    pub fn new_vartime(modulus: Odd<BoxedUint>) -> Self {
72        let bits_precision = modulus.bits_precision();
73
74        // `R mod modulus` where `R = 2^BITS`.
75        // Represents 1 in Montgomery form.
76        let one = BoxedUint::max(bits_precision)
77            .rem_vartime(modulus.as_nz_ref())
78            .wrapping_add(&BoxedUint::one());
79
80        // `R^2 mod modulus`, used to convert integers to Montgomery form.
81        let r2 = one
82            .square()
83            .rem_vartime(&modulus.as_nz_ref().widen(bits_precision * 2))
84            .shorten(bits_precision);
85
86        Self::new_inner(modulus, one, r2)
87    }
88
89    /// Common functionality of `new` and `new_vartime`.
90    fn new_inner(modulus: Odd<BoxedUint>, one: BoxedUint, r2: BoxedUint) -> Self {
91        debug_assert_eq!(one.bits_precision(), modulus.bits_precision());
92        debug_assert_eq!(r2.bits_precision(), modulus.bits_precision());
93
94        // If the inverse exists, it means the modulus is odd.
95        let (inv_mod_limb, modulus_is_odd) = modulus.inv_mod2k(Word::BITS);
96        debug_assert!(bool::from(modulus_is_odd));
97
98        let mod_neg_inv = Limb(Word::MIN.wrapping_sub(inv_mod_limb.limbs[0].0));
99
100        let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
101
102        let r3 = montgomery_reduction_boxed(&mut r2.square(), &modulus, mod_neg_inv);
103
104        Self {
105            modulus,
106            one,
107            r2,
108            r3,
109            mod_neg_inv,
110            mod_leading_zeros,
111        }
112    }
113
114    /// Modulus value.
115    pub fn modulus(&self) -> &Odd<BoxedUint> {
116        &self.modulus
117    }
118
119    /// Bits of precision in the modulus.
120    pub fn bits_precision(&self) -> u32 {
121        self.modulus.bits_precision()
122    }
123
124    /// Create from a set of [`ConstMontyParams`].
125    pub fn from_const_params<const LIMBS: usize, P: ConstMontyParams<LIMBS>>() -> Self {
126        Self {
127            modulus: P::MODULUS.into(),
128            one: P::ONE.into(),
129            r2: P::R2.into(),
130            r3: P::R3.into(),
131            mod_neg_inv: P::MOD_NEG_INV,
132            mod_leading_zeros: P::MOD_LEADING_ZEROS,
133        }
134    }
135}
136
137/// An integer in Montgomery form represented using heap-allocated limbs.
138#[derive(Clone, Debug, Eq, PartialEq)]
139pub struct BoxedMontyForm {
140    /// Value in the Montgomery form.
141    montgomery_form: BoxedUint,
142
143    /// Montgomery form parameters.
144    params: Arc<BoxedMontyParams>,
145}
146
147impl BoxedMontyForm {
148    /// Instantiates a new [`BoxedMontyForm`] that represents an integer modulo the provided params.
149    pub fn new(mut integer: BoxedUint, params: BoxedMontyParams) -> Self {
150        debug_assert_eq!(integer.bits_precision(), params.bits_precision());
151        convert_to_montgomery(&mut integer, &params);
152
153        #[allow(clippy::useless_conversion)]
154        Self {
155            montgomery_form: integer,
156            params: params.into(),
157        }
158    }
159
160    /// Instantiates a new [`BoxedMontyForm`] that represents an integer modulo the provided params.
161    pub fn new_with_arc(mut integer: BoxedUint, params: Arc<BoxedMontyParams>) -> Self {
162        debug_assert_eq!(integer.bits_precision(), params.bits_precision());
163        convert_to_montgomery(&mut integer, &params);
164        Self {
165            montgomery_form: integer,
166            params,
167        }
168    }
169
170    /// Bits of precision in the modulus.
171    pub fn bits_precision(&self) -> u32 {
172        self.params.bits_precision()
173    }
174
175    /// Retrieves the integer currently encoded in this [`BoxedMontyForm`], guaranteed to be reduced.
176    pub fn retrieve(&self) -> BoxedUint {
177        let mut montgomery_form = self.montgomery_form.widen(self.bits_precision() * 2);
178
179        let ret = montgomery_reduction_boxed(
180            &mut montgomery_form,
181            &self.params.modulus,
182            self.params.mod_neg_inv,
183        );
184
185        #[cfg(feature = "zeroize")]
186        montgomery_form.zeroize();
187
188        debug_assert!(ret < self.params.modulus);
189        ret
190    }
191
192    /// Instantiates a new `ConstMontyForm` that represents zero.
193    pub fn zero(params: BoxedMontyParams) -> Self {
194        Self {
195            montgomery_form: BoxedUint::zero_with_precision(params.bits_precision()),
196            params: params.into(),
197        }
198    }
199
200    /// Instantiates a new `ConstMontyForm` that represents 1.
201    pub fn one(params: BoxedMontyParams) -> Self {
202        Self {
203            montgomery_form: params.one.clone(),
204            params: params.into(),
205        }
206    }
207
208    /// Determine if this value is equal to zero.
209    ///
210    /// # Returns
211    ///
212    /// If zero, returns `Choice(1)`. Otherwise, returns `Choice(0)`.
213    pub fn is_zero(&self) -> Choice {
214        self.montgomery_form.is_zero()
215    }
216
217    /// Determine if this value is not equal to zero.
218    ///
219    /// # Returns
220    ///
221    /// If zero, returns `Choice(0)`. Otherwise, returns `Choice(1)`.
222    #[inline]
223    pub fn is_nonzero(&self) -> Choice {
224        !self.is_zero()
225    }
226
227    /// Returns the parameter struct used to initialize this object.
228    pub fn params(&self) -> &BoxedMontyParams {
229        &self.params
230    }
231
232    /// Access the [`BoxedMontyForm`] value in Montgomery form.
233    pub fn as_montgomery(&self) -> &BoxedUint {
234        debug_assert!(self.montgomery_form < self.params.modulus);
235        &self.montgomery_form
236    }
237
238    /// Create a [`BoxedMontyForm`] from a value in Montgomery form.
239    pub fn from_montgomery(integer: BoxedUint, params: BoxedMontyParams) -> Self {
240        debug_assert_eq!(integer.bits_precision(), params.bits_precision());
241        Self {
242            montgomery_form: integer,
243            params: params.into(),
244        }
245    }
246
247    /// Extract the value from the [`BoxedMontyForm`] in Montgomery form.
248    pub fn to_montgomery(&self) -> BoxedUint {
249        debug_assert!(self.montgomery_form < self.params.modulus);
250        self.montgomery_form.clone()
251    }
252
253    /// Performs division by 2, that is returns `x` such that `x + x = self`.
254    pub fn div_by_2(&self) -> Self {
255        Self {
256            montgomery_form: div_by_2::div_by_2_boxed(&self.montgomery_form, &self.params.modulus),
257            params: self.params.clone(),
258        }
259    }
260}
261
262impl Retrieve for BoxedMontyForm {
263    type Output = BoxedUint;
264    fn retrieve(&self) -> BoxedUint {
265        self.retrieve()
266    }
267}
268
269impl Monty for BoxedMontyForm {
270    type Integer = BoxedUint;
271    type Params = BoxedMontyParams;
272
273    fn new_params_vartime(modulus: Odd<Self::Integer>) -> Self::Params {
274        BoxedMontyParams::new_vartime(modulus)
275    }
276
277    fn new(value: Self::Integer, params: Self::Params) -> Self {
278        BoxedMontyForm::new(value, params)
279    }
280
281    fn zero(params: Self::Params) -> Self {
282        BoxedMontyForm::zero(params)
283    }
284
285    fn one(params: Self::Params) -> Self {
286        BoxedMontyForm::one(params)
287    }
288
289    fn params(&self) -> &Self::Params {
290        &self.params
291    }
292
293    fn as_montgomery(&self) -> &Self::Integer {
294        &self.montgomery_form
295    }
296
297    fn double(&self) -> Self {
298        BoxedMontyForm::double(self)
299    }
300
301    fn div_by_2(&self) -> Self {
302        BoxedMontyForm::div_by_2(self)
303    }
304
305    fn lincomb_vartime(products: &[(&Self, &Self)]) -> Self {
306        BoxedMontyForm::lincomb_vartime(products)
307    }
308}
309
310/// NOTE: This zeroizes the value, but _not_ the associated parameters!
311#[cfg(feature = "zeroize")]
312impl Zeroize for BoxedMontyForm {
313    fn zeroize(&mut self) {
314        self.montgomery_form.zeroize();
315    }
316}
317
318/// Convert the given integer into the Montgomery domain.
319#[inline]
320fn convert_to_montgomery(integer: &mut BoxedUint, params: &BoxedMontyParams) {
321    let mut product = integer.mul(&params.r2);
322    montgomery_reduction_boxed_mut(&mut product, &params.modulus, params.mod_neg_inv, integer);
323
324    #[cfg(feature = "zeroize")]
325    product.zeroize();
326}
327
328#[cfg(test)]
329mod tests {
330    use super::{BoxedMontyForm, BoxedMontyParams, BoxedUint, Limb, Odd};
331
332    #[test]
333    fn new_params_with_valid_modulus() {
334        let modulus = Odd::new(BoxedUint::from(3u8)).unwrap();
335        let params = BoxedMontyParams::new(modulus);
336
337        assert_eq!(params.mod_leading_zeros, Limb::BITS - 2);
338    }
339
340    #[test]
341    fn div_by_2() {
342        let modulus = Odd::new(BoxedUint::from(9u8)).unwrap();
343        let params = BoxedMontyParams::new(modulus);
344        let zero = BoxedMontyForm::zero(params.clone());
345        let one = BoxedMontyForm::one(params.clone());
346        let two = one.add(&one);
347
348        assert_eq!(zero.div_by_2(), zero);
349        assert_eq!(one.div_by_2().mul(&two), one);
350    }
351}
crypto_bigint/modular/boxed_monty_form.rs

crypto_bigint/modular/
boxed_monty_form.rs
