crypto_bigint/modular/
monty_params.rs

1//! Modulus-specific Montgomery form parameters.
2
3use crate::{Choice, CtAssign, CtEq, Limb, Odd, U64, Uint, Unsigned, Word};
4use core::fmt::{self, Debug};
5use ctutils::{CtAssignSlice, CtEqSlice, CtSelectUsingCtAssign};
6
7#[cfg(feature = "subtle")]
8use crate::CtSelect;
9#[cfg(feature = "zeroize")]
10use zeroize::Zeroize;
11
12/// Parameters to efficiently go to/from the Montgomery form for an odd modulus provided at runtime.
13///
14/// This version is generic over the underlying unsigned integer type.
15#[derive(Clone, Copy, PartialEq, Eq)]
16pub struct MontyParams<U: Unsigned> {
17    /// The constant modulus.
18    pub(super) modulus: Odd<U>,
19
20    /// 1 in Montgomery form (a.k.a. `R`).
21    pub(super) one: U,
22
23    /// `R^2 mod modulus`, used to move into Montgomery form.
24    pub(super) r2: U,
25
26    /// The lowest limbs of `MODULUS^-1 mod 2**64`.
27    ///
28    /// This value is used in Montgomery reduction and modular inversion.
29    pub(super) mod_inv: U64,
30
31    /// Leading zeros in the modulus, used to choose optimized algorithms.
32    pub(super) mod_leading_zeros: u32,
33}
34
35impl<U: Unsigned> MontyParams<U> {
36    /// Returns the modulus which was used to initialize these parameters.
37    pub const fn modulus(&self) -> &Odd<U> {
38        &self.modulus
39    }
40
41    /// 1 in Montgomery form (a.k.a. `R`).
42    pub const fn one(&self) -> &U {
43        &self.one
44    }
45
46    /// `R^2 mod modulus`, used to move into Montgomery form.
47    pub const fn r2(&self) -> &U {
48        &self.r2
49    }
50
51    /// Returns the lowest limbs of `MODULUS^-1 mod 2**64`.
52    ///
53    /// This value is used in Montgomery reduction and modular inversion.
54    pub const fn mod_inv(&self) -> &U64 {
55        &self.mod_inv
56    }
57
58    /// Returns wrapping negation of first limb of `mod_inv`.
59    #[inline(always)]
60    pub const fn mod_neg_inv(&self) -> Limb {
61        self.mod_inv.limbs[0].wrapping_neg()
62    }
63
64    /// Returns leading zeros in the modulus, used to choose optimized algorithms.
65    pub const fn mod_leading_zeros(&self) -> u32 {
66        self.mod_leading_zeros
67    }
68
69    /// Core implementation of the debug impl which lets us customize it for various types/type
70    /// aliases.
71    pub(crate) fn debug_struct(&self, mut debug: fmt::DebugStruct<'_, '_>) -> fmt::Result {
72        debug
73            .field("modulus", &self.modulus)
74            .field("one", &self.one)
75            .field("r2", &self.r2)
76            .field("mod_inv", &self.mod_inv)
77            .field("mod_leading_zeros", &self.mod_leading_zeros)
78            .finish()
79    }
80}
81
82impl<U: Unsigned> AsRef<Self> for MontyParams<U> {
83    fn as_ref(&self) -> &Self {
84        self
85    }
86}
87
88impl<U: Unsigned> CtAssign for MontyParams<U> {
89    fn ct_assign(&mut self, other: &Self, choice: Choice) {
90        self.modulus.ct_assign(&other.modulus, choice);
91        self.one.ct_assign(&other.one, choice);
92        self.r2.ct_assign(&other.r2, choice);
93        self.mod_inv.ct_assign(&other.mod_inv, choice);
94        self.mod_leading_zeros
95            .ct_assign(&other.mod_leading_zeros, choice);
96    }
97}
98impl<U: Unsigned> CtAssignSlice for MontyParams<U> {}
99impl<U: Unsigned> CtSelectUsingCtAssign for MontyParams<U> {}
100
101impl<U: Unsigned> CtEq for MontyParams<U> {
102    fn ct_eq(&self, other: &Self) -> Choice {
103        self.modulus.ct_eq(&other.modulus)
104            & self.one.ct_eq(&other.one)
105            & self.r2.ct_eq(&other.r2)
106            & self.mod_inv.ct_eq(&other.mod_inv)
107            & self.mod_leading_zeros.ct_eq(&other.mod_leading_zeros)
108    }
109}
110impl<U: Unsigned> CtEqSlice for MontyParams<U> {}
111
112impl<const LIMBS: usize> Debug for FixedMontyParams<LIMBS> {
113    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
114        self.debug_struct(f.debug_struct("MontyParams"))
115    }
116}
117
118#[cfg(feature = "subtle")]
119impl<U: Unsigned> subtle::ConstantTimeEq for MontyParams<U> {
120    fn ct_eq(&self, other: &Self) -> subtle::Choice {
121        CtEq::ct_eq(self, other).into()
122    }
123}
124
125#[cfg(feature = "subtle")]
126impl<U: Unsigned + Copy> subtle::ConditionallySelectable for MontyParams<U> {
127    fn conditional_assign(&mut self, src: &Self, choice: subtle::Choice) {
128        self.ct_assign(src, choice.into());
129    }
130
131    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
132        a.ct_select(b, choice.into())
133    }
134}
135
136#[cfg(feature = "zeroize")]
137impl<U: Unsigned + Zeroize> Zeroize for MontyParams<U> {
138    fn zeroize(&mut self) {
139        self.modulus.zeroize();
140        self.one.zeroize();
141        self.r2.zeroize();
142        self.mod_inv.zeroize();
143        self.mod_leading_zeros.zeroize();
144    }
145}
146
147/// Parameters to efficiently go to/from the Montgomery form for an odd modulus provided at runtime.
148pub type FixedMontyParams<const LIMBS: usize> = MontyParams<Uint<LIMBS>>;
149
150impl<const LIMBS: usize> FixedMontyParams<LIMBS> {
151    /// Instantiates a new set of `MontyParams` representing the given odd `modulus`.
152    #[must_use]
153    pub const fn new(modulus: Odd<Uint<LIMBS>>) -> Self {
154        // `R mod modulus` where `R = 2^BITS`.
155        // Represents 1 in Montgomery form.
156        let one = Uint::<LIMBS>::MAX
157            .rem(modulus.as_nz_ref())
158            .wrapping_add(&Uint::ONE);
159        let one = Uint::select(&one, &Uint::ZERO, Uint::eq(&one, modulus.as_ref()));
160
161        // `R^2 mod modulus`, used to convert integers to Montgomery form.
162        let r2 = one.square_mod(modulus.as_nz_ref());
163
164        // The inverse of the modulus modulo 2**64
165        let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
166
167        let mod_leading_zeros = modulus.as_ref().leading_zeros();
168        let mod_leading_zeros = Choice::from_u32_lt(mod_leading_zeros, Word::BITS - 1)
169            .select_u32(Word::BITS - 1, mod_leading_zeros);
170
171        Self {
172            modulus,
173            one,
174            r2,
175            mod_inv,
176            mod_leading_zeros,
177        }
178    }
179}
180
181impl<const LIMBS: usize> FixedMontyParams<LIMBS> {
182    /// Instantiates a new set of `MontyParams` representing the given odd `modulus`.
183    #[must_use]
184    pub const fn new_vartime(modulus: Odd<Uint<LIMBS>>) -> Self {
185        // `R mod modulus` where `R = 2^BITS`.
186        // Represents 1 in Montgomery form.
187        let one = Uint::<LIMBS>::MAX
188            .rem_vartime(modulus.as_nz_ref())
189            .wrapping_add(&Uint::ONE);
190        let one = Uint::select(&one, &Uint::ZERO, Uint::eq(&one, modulus.as_ref()));
191
192        // `R^2 mod modulus`, used to convert integers to Montgomery form.
193        let r2 = one.square_mod_vartime(modulus.as_nz_ref());
194
195        // The inverse of the modulus modulo 2**64
196        let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
197
198        let mod_leading_zeros = modulus.as_ref().leading_zeros_vartime();
199        let mod_leading_zeros = if mod_leading_zeros < Word::BITS - 1 {
200            mod_leading_zeros
201        } else {
202            Word::BITS - 1
203        };
204
205        Self {
206            modulus,
207            one,
208            r2,
209            mod_inv,
210            mod_leading_zeros,
211        }
212    }
213}
214
215#[cfg(feature = "alloc")]
216pub(crate) mod boxed {
217    use super::MontyParams;
218    use crate::{Limb, Odd, U64, Word};
219    use alloc::sync::Arc;
220    use core::fmt::{self, Debug};
221
222    /// Parameters to efficiently go to/from the Montgomery form for an odd modulus whose size and value
223    /// are both chosen at runtime.
224    #[derive(Clone, Eq, PartialEq)]
225    pub struct BoxedMontyParams(Arc<MontyParams<crate::uint::boxed::BoxedUint>>);
226
227    impl BoxedMontyParams {
228        /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`.
229        ///
230        /// TODO(tarcieri): DRY out with `MontyParams::new`?
231        #[must_use]
232        pub fn new(modulus: Odd<crate::uint::boxed::BoxedUint>) -> Self {
233            let bits_precision = modulus.bits_precision();
234
235            // `R mod modulus` where `R = 2^BITS`.
236            // Represents 1 in Montgomery form.
237            let mut one = crate::uint::boxed::BoxedUint::max(bits_precision)
238                .rem(modulus.as_nz_ref())
239                .wrapping_add(Limb::ONE);
240            if one == *modulus.as_ref() {
241                one = crate::uint::boxed::BoxedUint::zero_with_precision(bits_precision);
242            }
243
244            // `R^2 mod modulus`, used to convert integers to Montgomery form.
245            let r2 = one.square_mod(modulus.as_nz_ref());
246
247            // The inverse of the modulus modulo 2**64
248            let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
249
250            let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
251
252            Self(
253                MontyParams {
254                    modulus,
255                    one,
256                    r2,
257                    mod_inv,
258                    mod_leading_zeros,
259                }
260                .into(),
261            )
262        }
263
264        /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`.
265        /// This version operates in variable-time with respect to the modulus.
266        ///
267        /// TODO(tarcieri): DRY out with `MontyParams::new_vartime`?
268        #[must_use]
269        pub fn new_vartime(modulus: Odd<crate::uint::boxed::BoxedUint>) -> Self {
270            let bits_precision = modulus.bits_precision();
271
272            // `R mod modulus` where `R = 2^BITS`.
273            // Represents 1 in Montgomery form.
274            let mut one = crate::uint::boxed::BoxedUint::max(bits_precision)
275                .rem_vartime(modulus.as_nz_ref())
276                .wrapping_add(Limb::ONE);
277            if one == *modulus.as_ref() {
278                one = crate::uint::boxed::BoxedUint::zero_with_precision(bits_precision);
279            }
280
281            // `R^2 mod modulus`, used to convert integers to Montgomery form.
282            let r2 = one.square_mod_vartime(modulus.as_nz_ref());
283
284            // The inverse of the modulus modulo 2**64
285            let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
286
287            let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
288
289            Self(
290                MontyParams {
291                    modulus,
292                    one,
293                    r2,
294                    mod_inv,
295                    mod_leading_zeros,
296                }
297                .into(),
298            )
299        }
300
301        /// Modulus value.
302        #[must_use]
303        pub fn modulus(&self) -> &Odd<crate::uint::boxed::BoxedUint> {
304            &self.0.modulus
305        }
306
307        /// Bits of precision in the modulus.
308        #[must_use]
309        pub fn bits_precision(&self) -> u32 {
310            self.0.modulus.bits_precision()
311        }
312
313        pub(crate) fn r2(&self) -> &crate::uint::boxed::BoxedUint {
314            &self.0.r2
315        }
316
317        pub(crate) fn one(&self) -> &crate::uint::boxed::BoxedUint {
318            &self.0.one
319        }
320
321        pub(crate) fn mod_inv(&self) -> U64 {
322            self.0.mod_inv
323        }
324
325        pub(crate) fn mod_neg_inv(&self) -> Limb {
326            self.0.mod_inv.limbs[0].wrapping_neg()
327        }
328
329        pub(crate) fn mod_leading_zeros(&self) -> u32 {
330            self.0.mod_leading_zeros
331        }
332    }
333
334    impl AsRef<MontyParams<crate::uint::boxed::BoxedUint>> for BoxedMontyParams {
335        fn as_ref(&self) -> &MontyParams<crate::uint::boxed::BoxedUint> {
336            &self.0
337        }
338    }
339
340    impl Debug for BoxedMontyParams {
341        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
342            self.0.debug_struct(f.debug_struct("BoxedMontyParams"))
343        }
344    }
345
346    impl From<MontyParams<crate::uint::boxed::BoxedUint>> for BoxedMontyParams {
347        fn from(params: MontyParams<crate::uint::boxed::BoxedUint>) -> Self {
348            Self(params.into())
349        }
350    }
351}
352
353#[cfg(test)]
354mod tests {
355    use super::FixedMontyParams;
356    use crate::{CtEq, Odd, U128};
357
358    #[cfg(feature = "alloc")]
359    use super::boxed::BoxedMontyParams;
360    #[cfg(feature = "alloc")]
361    use crate::{BoxedUint, Resize};
362
363    #[test]
364    fn ct_eq_matches_partial_eq_for_mod_leading_zeros() {
365        let params = FixedMontyParams::new_vartime(Odd::new(U128::from(3u8)).unwrap());
366        let mut other = params;
367        other.mod_leading_zeros = 0;
368
369        assert_ne!(params, other);
370        assert!(!CtEq::ct_eq(&params, &other).to_bool_vartime());
371    }
372
373    #[cfg(feature = "alloc")]
374    #[test]
375    fn boxed_ct_eq_matches_partial_eq_for_mod_leading_zeros() {
376        let modulus = Odd::new(BoxedUint::from(3u8).resize(128)).unwrap();
377        let params = BoxedMontyParams::new_vartime(modulus);
378        let mut other = params.as_ref().clone();
379        other.mod_leading_zeros = 0;
380        let other = BoxedMontyParams::from(other);
381
382        assert_ne!(params, other);
383        assert!(!CtEq::ct_eq(&params, &other).to_bool_vartime());
384    }
385}
crypto_bigint/modular/monty_params.rs

crypto_bigint/modular/
monty_params.rs
