crypto_bigint/modular/
const_monty_form.rs

1//! Implements `ConstMontyForm`s, supporting modular arithmetic with a constant modulus.
2
3mod add;
4pub(super) mod inv;
5mod lincomb;
6mod mul;
7mod neg;
8mod pow;
9mod sub;
10
11use self::inv::ConstMontyFormInverter;
12use super::{div_by_2::div_by_2, reduction::montgomery_reduction, Retrieve, SafeGcdInverter};
13use crate::{ConstZero, Limb, Odd, PrecomputeInverter, Uint};
14use core::{fmt::Debug, marker::PhantomData};
15use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
16
17#[cfg(feature = "rand_core")]
18use crate::{rand_core::RngCore, Random, RandomMod};
19
20#[cfg(feature = "serde")]
21use {
22    crate::Encoding,
23    serdect::serde::de::Error,
24    serdect::serde::{Deserialize, Deserializer, Serialize, Serializer},
25};
26
27/// Macros to remove the boilerplate code when dealing with constant moduli.
28#[macro_use]
29mod macros;
30
31/// The parameters to efficiently go to and from the Montgomery form for a given odd modulus.
32///
33/// An easy way to generate these parameters is using the [`impl_modulus!`][`crate::impl_modulus`]
34/// macro. These parameters are constant, so they cannot be set at runtime.
35///
36/// Unfortunately, `LIMBS` must be generic for now until const generics are stabilized.
37pub trait ConstMontyParams<const LIMBS: usize>:
38    Copy + Debug + Default + Eq + Send + Sync + 'static
39{
40    /// Number of limbs required to encode the Montgomery form
41    const LIMBS: usize;
42
43    /// The constant modulus
44    const MODULUS: Odd<Uint<LIMBS>>;
45    /// 1 in Montgomery form
46    const ONE: Uint<LIMBS>;
47    /// `R^2 mod MODULUS`, used to move into Montgomery form
48    const R2: Uint<LIMBS>;
49    /// `R^3 mod MODULUS`, used to perform a multiplicative inverse
50    const R3: Uint<LIMBS>;
51    /// The lowest limbs of -(MODULUS^-1) mod R
52    // We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS.
53    const MOD_NEG_INV: Limb;
54    /// Leading zeros in the modulus, used to choose optimized algorithms
55    const MOD_LEADING_ZEROS: u32;
56
57    /// Precompute a Bernstein-Yang inverter for this modulus.
58    ///
59    /// Use [`ConstMontyFormInverter::new`] if you need `const fn` access.
60    fn precompute_inverter<const UNSAT_LIMBS: usize>() -> ConstMontyFormInverter<Self, LIMBS>
61    where
62        Odd<Uint<LIMBS>>: PrecomputeInverter<
63            Inverter = SafeGcdInverter<LIMBS, UNSAT_LIMBS>,
64            Output = Uint<LIMBS>,
65        >,
66    {
67        ConstMontyFormInverter::new()
68    }
69}
70
71/// An integer in Montgomery form modulo `MOD`, represented using `LIMBS` limbs.
72/// The modulus is constant, so it cannot be set at runtime.
73///
74/// Internally, the value is stored in Montgomery form (multiplied by MOD::ONE) until it is retrieved.
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub struct ConstMontyForm<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> {
77    montgomery_form: Uint<LIMBS>,
78    phantom: PhantomData<MOD>,
79}
80
81#[cfg(feature = "zeroize")]
82impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> zeroize::DefaultIsZeroes
83    for ConstMontyForm<MOD, LIMBS>
84{
85}
86
87impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstMontyForm<MOD, LIMBS> {
88    /// The representation of 0 mod `MOD`.
89    pub const ZERO: Self = Self {
90        montgomery_form: Uint::<LIMBS>::ZERO,
91        phantom: PhantomData,
92    };
93
94    /// The representation of 1 mod `MOD`.
95    pub const ONE: Self = Self {
96        montgomery_form: MOD::ONE,
97        phantom: PhantomData,
98    };
99
100    /// Internal helper function to convert to Montgomery form;
101    /// this lets us cleanly wrap the constructors.
102    const fn from_integer(integer: &Uint<LIMBS>) -> Self {
103        let product = integer.split_mul(&MOD::R2);
104        let montgomery_form =
105            montgomery_reduction::<LIMBS>(&product, &MOD::MODULUS, MOD::MOD_NEG_INV);
106
107        Self {
108            montgomery_form,
109            phantom: PhantomData,
110        }
111    }
112
113    /// Instantiates a new [`ConstMontyForm`] that represents this `integer` mod `MOD`.
114    pub const fn new(integer: &Uint<LIMBS>) -> Self {
115        Self::from_integer(integer)
116    }
117
118    /// Retrieves the integer currently encoded in this [`ConstMontyForm`], guaranteed to be reduced.
119    pub const fn retrieve(&self) -> Uint<LIMBS> {
120        montgomery_reduction::<LIMBS>(
121            &(self.montgomery_form, Uint::ZERO),
122            &MOD::MODULUS,
123            MOD::MOD_NEG_INV,
124        )
125    }
126
127    /// Access the `ConstMontyForm` value in Montgomery form.
128    pub const fn as_montgomery(&self) -> &Uint<LIMBS> {
129        &self.montgomery_form
130    }
131
132    /// Mutably access the `ConstMontyForm` value in Montgomery form.
133    pub fn as_montgomery_mut(&mut self) -> &mut Uint<LIMBS> {
134        &mut self.montgomery_form
135    }
136
137    /// Create a `ConstMontyForm` from a value in Montgomery form.
138    pub const fn from_montgomery(integer: Uint<LIMBS>) -> Self {
139        Self {
140            montgomery_form: integer,
141            phantom: PhantomData,
142        }
143    }
144
145    /// Extract the value from the `ConstMontyForm` in Montgomery form.
146    pub const fn to_montgomery(&self) -> Uint<LIMBS> {
147        self.montgomery_form
148    }
149
150    /// Performs division by 2, that is returns `x` such that `x + x = self`.
151    pub const fn div_by_2(&self) -> Self {
152        Self {
153            montgomery_form: div_by_2(&self.montgomery_form, &MOD::MODULUS),
154            phantom: PhantomData,
155        }
156    }
157}
158
159impl<MOD: ConstMontyParams<LIMBS> + Copy, const LIMBS: usize> ConditionallySelectable
160    for ConstMontyForm<MOD, LIMBS>
161{
162    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
163        ConstMontyForm {
164            montgomery_form: Uint::conditional_select(
165                &a.montgomery_form,
166                &b.montgomery_form,
167                choice,
168            ),
169            phantom: PhantomData,
170        }
171    }
172}
173
174impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstantTimeEq
175    for ConstMontyForm<MOD, LIMBS>
176{
177    fn ct_eq(&self, other: &Self) -> Choice {
178        ConstantTimeEq::ct_eq(&self.montgomery_form, &other.montgomery_form)
179    }
180}
181
182impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Default for ConstMontyForm<MOD, LIMBS> {
183    fn default() -> Self {
184        Self::ZERO
185    }
186}
187
188impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstZero for ConstMontyForm<MOD, LIMBS> {
189    const ZERO: Self = Self::ZERO;
190}
191
192impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> num_traits::Zero
193    for ConstMontyForm<MOD, LIMBS>
194{
195    fn zero() -> Self {
196        Self::ZERO
197    }
198
199    fn is_zero(&self) -> bool {
200        self.ct_eq(&Self::ZERO).into()
201    }
202}
203
204#[cfg(feature = "rand_core")]
205impl<MOD, const LIMBS: usize> Random for ConstMontyForm<MOD, LIMBS>
206where
207    MOD: ConstMontyParams<LIMBS>,
208{
209    #[inline]
210    fn random(rng: &mut (impl RngCore + ?Sized)) -> Self {
211        Self::new(&Uint::random_mod(rng, MOD::MODULUS.as_nz_ref()))
212    }
213}
214
215impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Retrieve for ConstMontyForm<MOD, LIMBS> {
216    type Output = Uint<LIMBS>;
217    fn retrieve(&self) -> Self::Output {
218        self.retrieve()
219    }
220}
221
222#[cfg(feature = "serde")]
223impl<'de, MOD, const LIMBS: usize> Deserialize<'de> for ConstMontyForm<MOD, LIMBS>
224where
225    MOD: ConstMontyParams<LIMBS>,
226    Uint<LIMBS>: Encoding,
227{
228    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
229    where
230        D: Deserializer<'de>,
231    {
232        Uint::<LIMBS>::deserialize(deserializer).and_then(|montgomery_form| {
233            if montgomery_form < MOD::MODULUS.0 {
234                Ok(Self {
235                    montgomery_form,
236                    phantom: PhantomData,
237                })
238            } else {
239                Err(D::Error::custom("montgomery form must be reduced"))
240            }
241        })
242    }
243}
244
245#[cfg(feature = "serde")]
246impl<MOD, const LIMBS: usize> Serialize for ConstMontyForm<MOD, LIMBS>
247where
248    MOD: ConstMontyParams<LIMBS>,
249    Uint<LIMBS>: Encoding,
250{
251    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
252    where
253        S: Serializer,
254    {
255        self.montgomery_form.serialize(serializer)
256    }
257}
crypto_bigint/modular/const_monty_form.rs

crypto_bigint/modular/
const_monty_form.rs
