crypto_bigint/uint/modular/
constant_mod.rs

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

crypto_bigint/uint/modular/
constant_mod.rs
