crypto_bigint/modular/boxed_monty_form/
mul.rs

1//! Multiplication between boxed integers in Montgomery form (i.e. Montgomery multiplication).
2//!
3//! Some parts adapted from `monty.rs` in `num-bigint`:
4//! <https://github.com/rust-num/num-bigint/blob/2cea7f4/src/biguint/monty.rs>
5//!
6//! Originally (c) 2014 The Rust Project Developers, dual licensed Apache 2.0+MIT.
7
8use super::{BoxedMontyForm, BoxedMontyParams};
9use crate::{
10    AmmMultiplier, BoxedUint, Limb, MontyMultiplier, Mul, MulAssign, Square, SquareAssign, Zero,
11    modular::mul::{almost_montgomery_mul, montgomery_multiply_inner},
12};
13
14#[cfg(feature = "zeroize")]
15use zeroize::Zeroize;
16
17impl BoxedMontyForm {
18    /// Multiplies by `rhs`.
19    #[must_use]
20    pub fn mul(&self, rhs: &Self) -> Self {
21        debug_assert_eq!(&self.params, &rhs.params);
22        let mut out = BoxedUint::zero_with_precision(self.bits_precision());
23        montgomery_mul(
24            &self.montgomery_form,
25            &rhs.montgomery_form,
26            &mut out,
27            self.params.modulus(),
28            self.params.mod_neg_inv(),
29        );
30        Self {
31            montgomery_form: out,
32            params: self.params.clone(),
33        }
34    }
35
36    /// Computes the (reduced) square.
37    #[must_use]
38    pub fn square(&self) -> Self {
39        let mut out = BoxedUint::zero_with_precision(self.bits_precision());
40        montgomery_mul(
41            &self.montgomery_form,
42            &self.montgomery_form,
43            &mut out,
44            self.params.modulus(),
45            self.params.mod_neg_inv(),
46        );
47        Self {
48            montgomery_form: out,
49            params: self.params.clone(),
50        }
51    }
52}
53
54impl Mul<&BoxedMontyForm> for &BoxedMontyForm {
55    type Output = BoxedMontyForm;
56    fn mul(self, rhs: &BoxedMontyForm) -> BoxedMontyForm {
57        self.mul(rhs)
58    }
59}
60
61impl Mul<BoxedMontyForm> for &BoxedMontyForm {
62    type Output = BoxedMontyForm;
63    #[allow(clippy::op_ref)]
64    fn mul(self, rhs: BoxedMontyForm) -> BoxedMontyForm {
65        self * &rhs
66    }
67}
68
69impl Mul<&BoxedMontyForm> for BoxedMontyForm {
70    type Output = BoxedMontyForm;
71    #[allow(clippy::op_ref)]
72    fn mul(self, rhs: &BoxedMontyForm) -> BoxedMontyForm {
73        &self * rhs
74    }
75}
76
77impl Mul<BoxedMontyForm> for BoxedMontyForm {
78    type Output = BoxedMontyForm;
79    fn mul(self, rhs: BoxedMontyForm) -> BoxedMontyForm {
80        &self * &rhs
81    }
82}
83
84impl MulAssign<BoxedMontyForm> for BoxedMontyForm {
85    fn mul_assign(&mut self, rhs: BoxedMontyForm) {
86        Self::mul_assign(self, &rhs);
87    }
88}
89
90impl MulAssign<&BoxedMontyForm> for BoxedMontyForm {
91    fn mul_assign(&mut self, rhs: &BoxedMontyForm) {
92        *self = Self::mul(self, rhs);
93    }
94}
95
96impl Square for BoxedMontyForm {
97    fn square(&self) -> Self {
98        BoxedMontyForm::square(self)
99    }
100}
101
102impl SquareAssign for BoxedMontyForm {
103    fn square_assign(&mut self) {
104        *self = Self::square(self);
105    }
106}
107
108/// Montgomery multiplier with a pre-allocated internal buffer to avoid additional allocations.
109#[derive(Debug, Clone)]
110pub struct BoxedMontyMultiplier<'a> {
111    product: BoxedUint,
112    modulus: &'a BoxedUint,
113    mod_neg_inv: Limb,
114}
115
116impl<'a> From<&'a BoxedMontyParams> for BoxedMontyMultiplier<'a> {
117    #[inline]
118    fn from(params: &'a BoxedMontyParams) -> BoxedMontyMultiplier<'a> {
119        BoxedMontyMultiplier::new(params.modulus(), params.mod_neg_inv())
120    }
121}
122
123impl<'a> MontyMultiplier<'a> for BoxedMontyMultiplier<'a> {
124    type Monty = BoxedMontyForm;
125
126    /// Performs a Montgomery multiplication, assigning a fully reduced result to `lhs`.
127    #[inline]
128    fn mul_assign(&mut self, lhs: &mut BoxedMontyForm, rhs: &BoxedMontyForm) {
129        self.mul_assign(&mut lhs.montgomery_form, &rhs.montgomery_form);
130    }
131
132    /// Performs a Montgomery squaring, assigning a fully reduced result to `lhs`.
133    #[inline]
134    fn square_assign(&mut self, lhs: &mut BoxedMontyForm) {
135        self.square_assign(&mut lhs.montgomery_form);
136    }
137}
138
139impl<'a> AmmMultiplier<'a> for BoxedMontyMultiplier<'a> {
140    #[inline]
141    fn mul_amm_assign(&mut self, a: &mut BoxedUint, b: &BoxedUint) {
142        self.mul_amm_assign(a, b);
143    }
144
145    #[inline]
146    fn square_amm_assign(&mut self, a: &mut BoxedUint) {
147        self.square_amm_assign(a);
148    }
149}
150
151impl<'a> BoxedMontyMultiplier<'a> {
152    /// Create a new Montgomery multiplier.
153    pub(super) fn new(modulus: &'a BoxedUint, mod_neg_inv: Limb) -> Self {
154        Self {
155            product: BoxedUint::zero_with_precision(modulus.bits_precision()),
156            modulus,
157            mod_neg_inv,
158        }
159    }
160
161    /// Perform a Montgomery multiplication, assigning a fully reduced result to `a`.
162    pub(super) fn mul_assign(&mut self, a: &mut BoxedUint, b: &BoxedUint) {
163        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
164        debug_assert_eq!(b.bits_precision(), self.modulus.bits_precision());
165
166        self.product.set_zero();
167        montgomery_mul(a, b, &mut self.product, self.modulus, self.mod_neg_inv);
168        a.limbs.copy_from_slice(&self.product.limbs);
169        debug_assert!(*a < self.modulus);
170    }
171
172    /// Perform a squaring using Montgomery multiplication, assigning a fully reduced result to `a`.
173    pub(super) fn square_assign(&mut self, a: &mut BoxedUint) {
174        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
175
176        self.product.set_zero();
177        montgomery_mul(a, a, &mut self.product, self.modulus, self.mod_neg_inv);
178        a.limbs.copy_from_slice(&self.product.limbs);
179
180        debug_assert!(*a < self.modulus);
181    }
182
183    /// Perform an "Almost Montgomery Multiplication", assigning the product to `a`.
184    ///
185    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
186    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
187    /// exposed outside the internals of this crate.
188    pub(super) fn mul_amm_assign(&mut self, a: &mut BoxedUint, b: &BoxedUint) {
189        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
190        debug_assert_eq!(b.bits_precision(), self.modulus.bits_precision());
191
192        self.product.set_zero();
193        almost_montgomery_mul(
194            a.as_uint_ref(),
195            b.as_uint_ref(),
196            self.product.as_mut_uint_ref(),
197            self.modulus.as_uint_ref(),
198            self.mod_neg_inv,
199        );
200        a.limbs.copy_from_slice(&self.product.limbs);
201    }
202
203    /// Perform a squaring using "Almost Montgomery Multiplication", assigning the result to `a`.
204    ///
205    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
206    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
207    /// exposed outside the internals of this crate.
208    pub(super) fn square_amm_assign(&mut self, a: &mut BoxedUint) {
209        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
210
211        // TODO(tarcieri): optimized implementation
212        self.product.set_zero();
213        almost_montgomery_mul(
214            a.as_uint_ref(),
215            a.as_uint_ref(),
216            self.product.as_mut_uint_ref(),
217            self.modulus.as_uint_ref(),
218            self.mod_neg_inv,
219        );
220        a.limbs.copy_from_slice(&self.product.limbs);
221    }
222}
223
224#[cfg(feature = "zeroize")]
225impl Drop for BoxedMontyMultiplier<'_> {
226    fn drop(&mut self) {
227        self.product.zeroize();
228    }
229}
230
231/// Computes Montgomery multiplication of `x` and `y` into `out`, that is
232/// `out = x * y * 2^(-n*W) mod m` assuming `k = -1/m mod 2^W`,
233/// where `W` is the bit size of the limb, and `n * W` is the full bit size of the integer.
234///
235/// NOTE: `out` is assumed to be pre-zeroized.
236#[inline]
237pub(crate) fn montgomery_mul(
238    x: &BoxedUint,
239    y: &BoxedUint,
240    out: &mut BoxedUint,
241    modulus: &BoxedUint,
242    mod_neg_inv: Limb,
243) {
244    let carry = montgomery_multiply_inner(
245        x.as_limbs(),
246        y.as_limbs(),
247        out.as_mut_limbs(),
248        modulus.as_limbs(),
249        mod_neg_inv,
250    );
251    out.sub_assign_mod_with_carry(carry, modulus, modulus);
252}
253
254#[cfg(test)]
255mod tests {
256    use super::{BoxedMontyForm, BoxedMontyParams, BoxedUint};
257    use crate::SquareAssign;
258
259    /// Regression test for RustCrypto/crypto-bigint#441
260    #[test]
261    fn square() {
262        let x = 0x20u128;
263        let modulus = 0xB44677037A7DBDE04814256570DCBD8Du128;
264
265        let boxed_modulus = BoxedUint::from(modulus);
266        let boxed_params = BoxedMontyParams::new(boxed_modulus.to_odd().unwrap());
267        let boxed_monty = BoxedMontyForm::new(BoxedUint::from(x), &boxed_params);
268        let boxed_square = boxed_monty.square();
269
270        // TODO(tarcieri): test for correct output
271        assert!(boxed_square.as_montgomery() < boxed_square.params().modulus());
272
273        // Check mul_assign
274        let mut boxed_mut = boxed_monty.clone();
275        boxed_mut *= &boxed_monty;
276        assert_eq!(boxed_mut, boxed_square);
277
278        // Check square_assign
279        let mut boxed_mut = boxed_monty.clone();
280        boxed_mut.square_assign();
281        assert_eq!(boxed_mut, boxed_square);
282    }
283}
crypto_bigint/modular/boxed_monty_form/mul.rs

crypto_bigint/modular/boxed_monty_form/
mul.rs
