crypto_bigint/uint/modular/
runtime_mod.rs

1use crate::{Limb, Uint, Word};
2
3use super::{
4    constant_mod::{Residue, ResidueParams},
5    div_by_2::div_by_2,
6    reduction::montgomery_reduction,
7    Retrieve,
8};
9
10use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
11
12/// Additions between residues with a modulus set at runtime
13mod runtime_add;
14/// Multiplicative inverses of residues with a modulus set at runtime
15mod runtime_inv;
16/// Multiplications between residues with a modulus set at runtime
17mod runtime_mul;
18/// Negations of residues with a modulus set at runtime
19mod runtime_neg;
20/// Exponentiation of residues with a modulus set at runtime
21mod runtime_pow;
22/// Subtractions between residues with a modulus set at runtime
23mod runtime_sub;
24
25/// The parameters to efficiently go to and from the Montgomery form for an odd modulus provided at runtime.
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
27pub struct DynResidueParams<const LIMBS: usize> {
28    // The constant modulus
29    modulus: Uint<LIMBS>,
30    // Parameter used in Montgomery reduction
31    r: Uint<LIMBS>,
32    // R^2, used to move into Montgomery form
33    r2: Uint<LIMBS>,
34    // R^3, used to compute the multiplicative inverse
35    r3: Uint<LIMBS>,
36    // The lowest limbs of -(MODULUS^-1) mod R
37    // We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS.
38    mod_neg_inv: Limb,
39}
40
41impl<const LIMBS: usize> DynResidueParams<LIMBS> {
42    // Internal helper function to generate parameters; this lets us wrap the constructors more cleanly
43    const fn generate_params(modulus: &Uint<LIMBS>) -> Self {
44        let r = Uint::MAX.const_rem(modulus).0.wrapping_add(&Uint::ONE);
45        let r2 = Uint::const_rem_wide(r.square_wide(), modulus).0;
46
47        // Since we are calculating the inverse modulo (Word::MAX+1),
48        // we can take the modulo right away and calculate the inverse of the first limb only.
49        let modulus_lo = Uint::<1>::from_words([modulus.limbs[0].0]);
50        let mod_neg_inv = Limb(
51            Word::MIN.wrapping_sub(modulus_lo.inv_mod2k_vartime(Word::BITS as usize).limbs[0].0),
52        );
53
54        let r3 = montgomery_reduction(&r2.square_wide(), modulus, mod_neg_inv);
55
56        Self {
57            modulus: *modulus,
58            r,
59            r2,
60            r3,
61            mod_neg_inv,
62        }
63    }
64
65    /// Instantiates a new set of `ResidueParams` representing the given `modulus`, which _must_ be odd.
66    /// If `modulus` is not odd, this function will panic; use [`new_checked`][`DynResidueParams::new_checked`] if you want to be able to detect an invalid modulus.
67    pub const fn new(modulus: &Uint<LIMBS>) -> Self {
68        // A valid modulus must be odd
69        if modulus.ct_is_odd().to_u8() == 0 {
70            panic!("modulus must be odd");
71        }
72
73        Self::generate_params(modulus)
74    }
75
76    /// Instantiates a new set of `ResidueParams` representing the given `modulus` if it is odd.
77    /// Returns a `CtOption` that is `None` if the provided modulus is not odd; this is a safer version of [`new`][`DynResidueParams::new`], which can panic.
78    #[deprecated(
79        since = "0.5.3",
80        note = "This functionality will be moved to `new` in a future release."
81    )]
82    pub fn new_checked(modulus: &Uint<LIMBS>) -> CtOption<Self> {
83        // A valid modulus must be odd.
84        CtOption::new(Self::generate_params(modulus), modulus.ct_is_odd().into())
85    }
86
87    /// Returns the modulus which was used to initialize these parameters.
88    pub const fn modulus(&self) -> &Uint<LIMBS> {
89        &self.modulus
90    }
91
92    /// Create `DynResidueParams` corresponding to a `ResidueParams`.
93    pub const fn from_residue_params<P>() -> Self
94    where
95        P: ResidueParams<LIMBS>,
96    {
97        Self {
98            modulus: P::MODULUS,
99            r: P::R,
100            r2: P::R2,
101            r3: P::R3,
102            mod_neg_inv: P::MOD_NEG_INV,
103        }
104    }
105}
106
107impl<const LIMBS: usize> ConditionallySelectable for DynResidueParams<LIMBS> {
108    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
109        Self {
110            modulus: Uint::conditional_select(&a.modulus, &b.modulus, choice),
111            r: Uint::conditional_select(&a.r, &b.r, choice),
112            r2: Uint::conditional_select(&a.r2, &b.r2, choice),
113            r3: Uint::conditional_select(&a.r3, &b.r3, choice),
114            mod_neg_inv: Limb::conditional_select(&a.mod_neg_inv, &b.mod_neg_inv, choice),
115        }
116    }
117}
118
119impl<const LIMBS: usize> ConstantTimeEq for DynResidueParams<LIMBS> {
120    fn ct_eq(&self, other: &Self) -> Choice {
121        self.modulus.ct_eq(&other.modulus)
122            & self.r.ct_eq(&other.r)
123            & self.r2.ct_eq(&other.r2)
124            & self.r3.ct_eq(&other.r3)
125            & self.mod_neg_inv.ct_eq(&other.mod_neg_inv)
126    }
127}
128
129/// A residue represented using `LIMBS` limbs. The odd modulus of this residue is set at runtime.
130#[derive(Debug, Clone, Copy, PartialEq, Eq)]
131pub struct DynResidue<const LIMBS: usize> {
132    montgomery_form: Uint<LIMBS>,
133    residue_params: DynResidueParams<LIMBS>,
134}
135
136impl<const LIMBS: usize> DynResidue<LIMBS> {
137    /// Instantiates a new `Residue` that represents this `integer` mod `MOD`.
138    pub const fn new(integer: &Uint<LIMBS>, residue_params: DynResidueParams<LIMBS>) -> Self {
139        let product = integer.mul_wide(&residue_params.r2);
140        let montgomery_form = montgomery_reduction(
141            &product,
142            &residue_params.modulus,
143            residue_params.mod_neg_inv,
144        );
145
146        Self {
147            montgomery_form,
148            residue_params,
149        }
150    }
151
152    /// Retrieves the integer currently encoded in this `Residue`, guaranteed to be reduced.
153    pub const fn retrieve(&self) -> Uint<LIMBS> {
154        montgomery_reduction(
155            &(self.montgomery_form, Uint::ZERO),
156            &self.residue_params.modulus,
157            self.residue_params.mod_neg_inv,
158        )
159    }
160
161    /// Instantiates a new `Residue` that represents zero.
162    pub const fn zero(residue_params: DynResidueParams<LIMBS>) -> Self {
163        Self {
164            montgomery_form: Uint::<LIMBS>::ZERO,
165            residue_params,
166        }
167    }
168
169    /// Instantiates a new `Residue` that represents 1.
170    pub const fn one(residue_params: DynResidueParams<LIMBS>) -> Self {
171        Self {
172            montgomery_form: residue_params.r,
173            residue_params,
174        }
175    }
176
177    /// Returns the parameter struct used to initialize this residue.
178    pub const fn params(&self) -> &DynResidueParams<LIMBS> {
179        &self.residue_params
180    }
181
182    /// Access the `DynResidue` value in Montgomery form.
183    pub const fn as_montgomery(&self) -> &Uint<LIMBS> {
184        &self.montgomery_form
185    }
186
187    /// Mutably access the `DynResidue` value in Montgomery form.
188    pub fn as_montgomery_mut(&mut self) -> &mut Uint<LIMBS> {
189        &mut self.montgomery_form
190    }
191
192    /// Create a `DynResidue` from a value in Montgomery form.
193    pub const fn from_montgomery(
194        integer: Uint<LIMBS>,
195        residue_params: DynResidueParams<LIMBS>,
196    ) -> Self {
197        Self {
198            montgomery_form: integer,
199            residue_params,
200        }
201    }
202
203    /// Extract the value from the `DynResidue` in Montgomery form.
204    pub const fn to_montgomery(&self) -> Uint<LIMBS> {
205        self.montgomery_form
206    }
207
208    /// Performs the modular division by 2, that is for given `x` returns `y`
209    /// such that `y * 2 = x mod p`. This means:
210    /// - if `x` is even, returns `x / 2`,
211    /// - if `x` is odd, returns `(x + p) / 2`
212    ///   (since the modulus `p` in Montgomery form is always odd, this divides entirely).
213    pub fn div_by_2(&self) -> Self {
214        Self {
215            montgomery_form: div_by_2(&self.montgomery_form, &self.residue_params.modulus),
216            residue_params: self.residue_params,
217        }
218    }
219}
220
221impl<const LIMBS: usize> Retrieve for DynResidue<LIMBS> {
222    type Output = Uint<LIMBS>;
223    fn retrieve(&self) -> Self::Output {
224        self.retrieve()
225    }
226}
227
228impl<const LIMBS: usize, P: ResidueParams<LIMBS>> From<&Residue<P, LIMBS>> for DynResidue<LIMBS> {
229    fn from(residue: &Residue<P, LIMBS>) -> Self {
230        Self {
231            montgomery_form: residue.to_montgomery(),
232            residue_params: DynResidueParams::from_residue_params::<P>(),
233        }
234    }
235}
236
237impl<const LIMBS: usize> ConditionallySelectable for DynResidue<LIMBS> {
238    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
239        Self {
240            montgomery_form: Uint::conditional_select(
241                &a.montgomery_form,
242                &b.montgomery_form,
243                choice,
244            ),
245            residue_params: DynResidueParams::conditional_select(
246                &a.residue_params,
247                &b.residue_params,
248                choice,
249            ),
250        }
251    }
252}
253
254impl<const LIMBS: usize> ConstantTimeEq for DynResidue<LIMBS> {
255    fn ct_eq(&self, other: &Self) -> Choice {
256        self.montgomery_form.ct_eq(&other.montgomery_form)
257            & self.residue_params.ct_eq(&other.residue_params)
258    }
259}
260
261/// NOTE: this does _not_ zeroize the parameters, in order to maintain some form of type consistency
262#[cfg(feature = "zeroize")]
263impl<const LIMBS: usize> zeroize::Zeroize for DynResidue<LIMBS> {
264    fn zeroize(&mut self) {
265        self.montgomery_form.zeroize()
266    }
267}
268
269#[cfg(test)]
270mod test {
271    use super::*;
272
273    const LIMBS: usize = nlimbs!(64);
274
275    #[test]
276    #[allow(deprecated)]
277    // Test that a valid modulus yields `DynResidueParams`
278    fn test_valid_modulus() {
279        let valid_modulus = Uint::<LIMBS>::from(3u8);
280
281        DynResidueParams::<LIMBS>::new_checked(&valid_modulus).unwrap();
282        DynResidueParams::<LIMBS>::new(&valid_modulus);
283    }
284
285    #[test]
286    #[allow(deprecated)]
287    // Test that an invalid checked modulus does not yield `DynResidueParams`
288    fn test_invalid_checked_modulus() {
289        assert!(bool::from(
290            DynResidueParams::<LIMBS>::new_checked(&Uint::from(2u8)).is_none()
291        ))
292    }
293
294    #[test]
295    #[should_panic]
296    // Tets that an invalid modulus panics
297    fn test_invalid_modulus() {
298        DynResidueParams::<LIMBS>::new(&Uint::from(2u8));
299    }
300}
crypto_bigint/uint/modular/runtime_mod.rs

crypto_bigint/uint/modular/
runtime_mod.rs
