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    }
108}
109impl<U: Unsigned> CtEqSlice for MontyParams<U> {}
110
111impl<const LIMBS: usize> Debug for FixedMontyParams<LIMBS> {
112    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
113        self.debug_struct(f.debug_struct("MontyParams"))
114    }
115}
116
117#[cfg(feature = "subtle")]
118impl<U: Unsigned> subtle::ConstantTimeEq for MontyParams<U> {
119    fn ct_eq(&self, other: &Self) -> subtle::Choice {
120        CtEq::ct_eq(self, other).into()
121    }
122}
123
124#[cfg(feature = "subtle")]
125impl<U: Unsigned + Copy> subtle::ConditionallySelectable for MontyParams<U> {
126    fn conditional_assign(&mut self, src: &Self, choice: subtle::Choice) {
127        self.ct_assign(src, choice.into());
128    }
129
130    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
131        a.ct_select(b, choice.into())
132    }
133}
134
135#[cfg(feature = "zeroize")]
136impl<U: Unsigned + Zeroize> Zeroize for MontyParams<U> {
137    fn zeroize(&mut self) {
138        self.modulus.zeroize();
139        self.one.zeroize();
140        self.r2.zeroize();
141        self.mod_inv.zeroize();
142        self.mod_leading_zeros.zeroize();
143    }
144}
145
146/// Parameters to efficiently go to/from the Montgomery form for an odd modulus provided at runtime.
147pub type FixedMontyParams<const LIMBS: usize> = MontyParams<Uint<LIMBS>>;
148
149impl<const LIMBS: usize> FixedMontyParams<LIMBS> {
150    /// Instantiates a new set of `MontyParams` representing the given odd `modulus`.
151    #[must_use]
152    pub const fn new(modulus: Odd<Uint<LIMBS>>) -> Self {
153        // `R mod modulus` where `R = 2^BITS`.
154        // Represents 1 in Montgomery form.
155        let one = Uint::<LIMBS>::MAX
156            .rem(modulus.as_nz_ref())
157            .wrapping_add(&Uint::ONE);
158
159        // `R^2 mod modulus`, used to convert integers to Montgomery form.
160        let r2 = one.square_mod(modulus.as_nz_ref());
161
162        // The inverse of the modulus modulo 2**64
163        let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
164
165        let mod_leading_zeros = modulus.as_ref().leading_zeros();
166        let mod_leading_zeros = Choice::from_u32_lt(mod_leading_zeros, Word::BITS - 1)
167            .select_u32(Word::BITS - 1, mod_leading_zeros);
168
169        Self {
170            modulus,
171            one,
172            r2,
173            mod_inv,
174            mod_leading_zeros,
175        }
176    }
177}
178
179impl<const LIMBS: usize> FixedMontyParams<LIMBS> {
180    /// Instantiates a new set of `MontyParams` representing the given odd `modulus`.
181    #[must_use]
182    pub const fn new_vartime(modulus: Odd<Uint<LIMBS>>) -> Self {
183        // `R mod modulus` where `R = 2^BITS`.
184        // Represents 1 in Montgomery form.
185        let one = Uint::<LIMBS>::MAX
186            .rem_vartime(modulus.as_nz_ref())
187            .wrapping_add(&Uint::ONE);
188
189        // `R^2 mod modulus`, used to convert integers to Montgomery form.
190        let r2 = one.square_mod_vartime(modulus.as_nz_ref());
191
192        // The inverse of the modulus modulo 2**64
193        let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
194
195        let mod_leading_zeros = modulus.as_ref().leading_zeros_vartime();
196        let mod_leading_zeros = if mod_leading_zeros < Word::BITS - 1 {
197            mod_leading_zeros
198        } else {
199            Word::BITS - 1
200        };
201
202        Self {
203            modulus,
204            one,
205            r2,
206            mod_inv,
207            mod_leading_zeros,
208        }
209    }
210}
211
212#[cfg(feature = "alloc")]
213pub(crate) mod boxed {
214    use super::MontyParams;
215    use crate::{Limb, Odd, U64, Word};
216    use alloc::sync::Arc;
217    use core::fmt::{self, Debug};
218
219    /// Parameters to efficiently go to/from the Montgomery form for an odd modulus whose size and value
220    /// are both chosen at runtime.
221    #[derive(Clone, Eq, PartialEq)]
222    pub struct BoxedMontyParams(Arc<MontyParams<crate::uint::boxed::BoxedUint>>);
223
224    impl BoxedMontyParams {
225        /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`.
226        ///
227        /// TODO(tarcieri): DRY out with `MontyParams::new`?
228        #[must_use]
229        pub fn new(modulus: Odd<crate::uint::boxed::BoxedUint>) -> Self {
230            let bits_precision = modulus.bits_precision();
231
232            // `R mod modulus` where `R = 2^BITS`.
233            // Represents 1 in Montgomery form.
234            let one = crate::uint::boxed::BoxedUint::max(bits_precision)
235                .rem(modulus.as_nz_ref())
236                .wrapping_add(Limb::ONE);
237
238            // `R^2 mod modulus`, used to convert integers to Montgomery form.
239            let r2 = one.square_mod(modulus.as_nz_ref());
240
241            // The inverse of the modulus modulo 2**64
242            let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
243
244            let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
245
246            Self(
247                MontyParams {
248                    modulus,
249                    one,
250                    r2,
251                    mod_inv,
252                    mod_leading_zeros,
253                }
254                .into(),
255            )
256        }
257
258        /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`.
259        /// This version operates in variable-time with respect to the modulus.
260        ///
261        /// TODO(tarcieri): DRY out with `MontyParams::new_vartime`?
262        #[must_use]
263        pub fn new_vartime(modulus: Odd<crate::uint::boxed::BoxedUint>) -> Self {
264            let bits_precision = modulus.bits_precision();
265
266            // `R mod modulus` where `R = 2^BITS`.
267            // Represents 1 in Montgomery form.
268            let one = crate::uint::boxed::BoxedUint::max(bits_precision)
269                .rem_vartime(modulus.as_nz_ref())
270                .wrapping_add(Limb::ONE);
271
272            // `R^2 mod modulus`, used to convert integers to Montgomery form.
273            let r2 = one.square_mod_vartime(modulus.as_nz_ref());
274
275            // The inverse of the modulus modulo 2**64
276            let mod_inv = U64::from_u64(modulus.as_uint_ref().invert_mod_u64());
277
278            let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
279
280            Self(
281                MontyParams {
282                    modulus,
283                    one,
284                    r2,
285                    mod_inv,
286                    mod_leading_zeros,
287                }
288                .into(),
289            )
290        }
291
292        /// Modulus value.
293        #[must_use]
294        pub fn modulus(&self) -> &Odd<crate::uint::boxed::BoxedUint> {
295            &self.0.modulus
296        }
297
298        /// Bits of precision in the modulus.
299        #[must_use]
300        pub fn bits_precision(&self) -> u32 {
301            self.0.modulus.bits_precision()
302        }
303
304        pub(crate) fn r2(&self) -> &crate::uint::boxed::BoxedUint {
305            &self.0.r2
306        }
307
308        pub(crate) fn one(&self) -> &crate::uint::boxed::BoxedUint {
309            &self.0.one
310        }
311
312        pub(crate) fn mod_inv(&self) -> U64 {
313            self.0.mod_inv
314        }
315
316        pub(crate) fn mod_neg_inv(&self) -> Limb {
317            self.0.mod_inv.limbs[0].wrapping_neg()
318        }
319
320        pub(crate) fn mod_leading_zeros(&self) -> u32 {
321            self.0.mod_leading_zeros
322        }
323    }
324
325    impl AsRef<MontyParams<crate::uint::boxed::BoxedUint>> for BoxedMontyParams {
326        fn as_ref(&self) -> &MontyParams<crate::uint::boxed::BoxedUint> {
327            &self.0
328        }
329    }
330
331    impl Debug for BoxedMontyParams {
332        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
333            self.0.debug_struct(f.debug_struct("BoxedMontyParams"))
334        }
335    }
336
337    impl From<MontyParams<crate::uint::boxed::BoxedUint>> for BoxedMontyParams {
338        fn from(params: MontyParams<crate::uint::boxed::BoxedUint>) -> Self {
339            Self(params.into())
340        }
341    }
342}
crypto_bigint/modular/monty_params.rs

crypto_bigint/modular/
monty_params.rs
