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    modular::reduction::montgomery_reduction_boxed_mut, uint::mul::mul_limbs, BoxedUint, Limb,
11    Square, SquareAssign, Word, Zero,
12};
13use core::{
14    borrow::Borrow,
15    ops::{Mul, MulAssign},
16};
17use subtle::{ConditionallySelectable, ConstantTimeLess};
18
19#[cfg(feature = "zeroize")]
20use zeroize::Zeroize;
21
22impl BoxedMontyForm {
23    /// Multiplies by `rhs`.
24    pub fn mul(&self, rhs: &Self) -> Self {
25        debug_assert_eq!(&self.params, &rhs.params);
26        let montgomery_form = MontyMultiplier::from(self.params.borrow())
27            .mul(&self.montgomery_form, &rhs.montgomery_form);
28
29        Self {
30            montgomery_form,
31            params: self.params.clone(),
32        }
33    }
34
35    /// Computes the (reduced) square.
36    pub fn square(&self) -> Self {
37        let montgomery_form =
38            MontyMultiplier::from(self.params.borrow()).square(&self.montgomery_form);
39
40        Self {
41            montgomery_form,
42            params: self.params.clone(),
43        }
44    }
45}
46
47impl Mul<&BoxedMontyForm> for &BoxedMontyForm {
48    type Output = BoxedMontyForm;
49    fn mul(self, rhs: &BoxedMontyForm) -> BoxedMontyForm {
50        self.mul(rhs)
51    }
52}
53
54impl Mul<BoxedMontyForm> for &BoxedMontyForm {
55    type Output = BoxedMontyForm;
56    #[allow(clippy::op_ref)]
57    fn mul(self, rhs: BoxedMontyForm) -> BoxedMontyForm {
58        self * &rhs
59    }
60}
61
62impl Mul<&BoxedMontyForm> for BoxedMontyForm {
63    type Output = BoxedMontyForm;
64    #[allow(clippy::op_ref)]
65    fn mul(self, rhs: &BoxedMontyForm) -> BoxedMontyForm {
66        &self * rhs
67    }
68}
69
70impl Mul<BoxedMontyForm> for BoxedMontyForm {
71    type Output = BoxedMontyForm;
72    fn mul(self, rhs: BoxedMontyForm) -> BoxedMontyForm {
73        &self * &rhs
74    }
75}
76
77impl MulAssign<BoxedMontyForm> for BoxedMontyForm {
78    fn mul_assign(&mut self, rhs: BoxedMontyForm) {
79        Self::mul_assign(self, &rhs)
80    }
81}
82
83impl MulAssign<&BoxedMontyForm> for BoxedMontyForm {
84    fn mul_assign(&mut self, rhs: &BoxedMontyForm) {
85        debug_assert_eq!(&self.params, &rhs.params);
86        MontyMultiplier::from(self.params.borrow())
87            .mul_assign(&mut self.montgomery_form, &rhs.montgomery_form);
88    }
89}
90
91impl Square for BoxedMontyForm {
92    fn square(&self) -> Self {
93        BoxedMontyForm::square(self)
94    }
95}
96
97impl SquareAssign for BoxedMontyForm {
98    fn square_assign(&mut self) {
99        MontyMultiplier::from(self.params.borrow()).square_assign(&mut self.montgomery_form);
100    }
101}
102
103impl<'a> From<&'a BoxedMontyParams> for MontyMultiplier<'a> {
104    fn from(params: &'a BoxedMontyParams) -> MontyMultiplier<'a> {
105        MontyMultiplier::new(&params.modulus, params.mod_neg_inv)
106    }
107}
108
109/// Montgomery multiplier with a pre-allocated internal buffer to avoid additional allocations.
110pub(super) struct MontyMultiplier<'a> {
111    product: BoxedUint,
112    modulus: &'a BoxedUint,
113    mod_neg_inv: Limb,
114}
115
116impl<'a> MontyMultiplier<'a> {
117    /// Create a new Montgomery multiplier.
118    pub(super) fn new(modulus: &'a BoxedUint, mod_neg_inv: Limb) -> Self {
119        Self {
120            product: BoxedUint::zero_with_precision(modulus.bits_precision() * 2),
121            modulus,
122            mod_neg_inv,
123        }
124    }
125
126    /// Perform a Montgomery multiplication, returning a fully reduced result.
127    pub(super) fn mul(&mut self, a: &BoxedUint, b: &BoxedUint) -> BoxedUint {
128        let mut ret = a.clone();
129        self.mul_assign(&mut ret, b);
130        ret
131    }
132
133    /// Perform a Montgomery multiplication, assigning a fully reduced result to `a`.
134    pub(super) fn mul_assign(&mut self, a: &mut BoxedUint, b: &BoxedUint) {
135        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
136        debug_assert_eq!(b.bits_precision(), self.modulus.bits_precision());
137
138        mul_limbs(&a.limbs, &b.limbs, &mut self.product.limbs);
139        montgomery_reduction_boxed_mut(&mut self.product, self.modulus, self.mod_neg_inv, a);
140
141        debug_assert!(&*a < self.modulus);
142    }
143
144    /// Perform a squaring using Montgomery multiplication, returning a fully reduced result.
145    pub(super) fn square(&mut self, a: &BoxedUint) -> BoxedUint {
146        let mut ret = a.clone();
147        self.square_assign(&mut ret);
148        ret
149    }
150
151    /// Perform a squaring using Montgomery multiplication, assigning a fully reduced result to `a`.
152    pub(super) fn square_assign(&mut self, a: &mut BoxedUint) {
153        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
154
155        // TODO(tarcieri): optimized implementation
156        mul_limbs(&a.limbs, &a.limbs, &mut self.product.limbs);
157        montgomery_reduction_boxed_mut(&mut self.product, self.modulus, self.mod_neg_inv, a);
158
159        debug_assert!(&*a < self.modulus);
160    }
161
162    /// Perform an "Almost Montgomery Multiplication".
163    ///
164    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
165    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
166    /// exposed outside the internals of this crate.
167    pub(super) fn mul_amm(&mut self, a: &BoxedUint, b: &BoxedUint) -> BoxedUint {
168        let mut ret = a.clone();
169        self.mul_amm_assign(&mut ret, b);
170        ret
171    }
172
173    /// Perform an "Almost Montgomery Multiplication", assigning the product to `a`.
174    ///
175    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
176    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
177    /// exposed outside the internals of this crate.
178    pub(super) fn mul_amm_assign(&mut self, a: &mut BoxedUint, b: &BoxedUint) {
179        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
180        debug_assert_eq!(b.bits_precision(), self.modulus.bits_precision());
181
182        self.clear_product();
183        almost_montgomery_mul(
184            self.product.as_limbs_mut(),
185            a.as_limbs(),
186            b.as_limbs(),
187            self.modulus.as_limbs(),
188            self.mod_neg_inv,
189        );
190        a.limbs
191            .copy_from_slice(&self.product.limbs[..a.limbs.len()]);
192    }
193
194    /// Perform a squaring using "Almost Montgomery Multiplication".
195    ///
196    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
197    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
198    /// exposed outside the internals of this crate.
199    #[allow(dead_code)] // TODO(tarcieri): use this?
200    pub(super) fn square_amm(&mut self, a: &BoxedUint) -> BoxedUint {
201        let mut ret = a.clone();
202        self.square_amm_assign(&mut ret);
203        ret
204    }
205
206    /// Perform a squaring using "Almost Montgomery Multiplication", assigning the result to `a`.
207    ///
208    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
209    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
210    /// exposed outside the internals of this crate.
211    pub(super) fn square_amm_assign(&mut self, a: &mut BoxedUint) {
212        debug_assert_eq!(a.bits_precision(), self.modulus.bits_precision());
213
214        self.clear_product();
215        almost_montgomery_mul(
216            self.product.as_limbs_mut(),
217            a.as_limbs(),
218            a.as_limbs(),
219            self.modulus.as_limbs(),
220            self.mod_neg_inv,
221        );
222        a.limbs
223            .copy_from_slice(&self.product.limbs[..a.limbs.len()]);
224    }
225
226    /// Clear the internal product buffer.
227    fn clear_product(&mut self) {
228        self.product
229            .limbs
230            .iter_mut()
231            .for_each(|limb| *limb = Limb::ZERO);
232    }
233}
234
235#[cfg(feature = "zeroize")]
236impl Drop for MontyMultiplier<'_> {
237    fn drop(&mut self) {
238        self.product.zeroize();
239    }
240}
241
242/// Compute an "Almost Montgomery Multiplication (AMM)" as described in the paper
243/// "Efficient Software Implementations of Modular Exponentiation"
244/// <https://eprint.iacr.org/2011/239.pdf>
245///
246/// Computes z mod m = x * y * 2 ** (-n*_W) mod m assuming k = -1/m mod 2**_W.
247///
248/// x and y are required to satisfy 0 <= z < 2**(n*_W) and then the result z is guaranteed to
249/// satisfy 0 <= z < 2**(n*_W), but it may not be < m.
250///
251/// Output is written into the lower (i.e. first) half of `z`.
252///
253/// Note: this was adapted from an implementation in `num-bigint`'s `monty.rs`.
254// TODO(tarcieri): refactor into `reduction.rs`, share impl with `MontyForm`?
255fn almost_montgomery_mul(z: &mut [Limb], x: &[Limb], y: &[Limb], m: &[Limb], k: Limb) {
256    // This code assumes x, y, m are all the same length (required by addMulVVW and the for loop).
257    // It also assumes that x, y are already reduced mod m, or else the result will not be properly
258    // reduced.
259    let n = m.len();
260
261    // This preconditions check allows compiler to remove bound checks later in the code.
262    // `z.len() > n && z[n..].len() == n` is used intentionally instead of `z.len() == 2* n`
263    // since the latter prevents compiler from removing some bound checks.
264    let pre_cond = z.len() > n && z[n..].len() == n && x.len() == n && y.len() == n && m.len() == n;
265    if !pre_cond {
266        panic!("Failed preconditions in montgomery_mul");
267    }
268
269    let mut c = Limb::ZERO;
270
271    for i in 0..n {
272        let c2 = add_mul_vvw(&mut z[i..n + i], x, y[i]);
273        let t = z[i].wrapping_mul(k);
274        let c3 = add_mul_vvw(&mut z[i..n + i], m, t);
275        let cx = c.wrapping_add(c2);
276        let cy = cx.wrapping_add(c3);
277        z[n + i] = cy;
278        c = Limb((cx.ct_lt(&c2) | cy.ct_lt(&c3)).unwrap_u8() as Word);
279    }
280
281    let (lower, upper) = z.split_at_mut(n);
282    sub_vv(lower, upper, m);
283
284    let is_zero = c.is_zero();
285    for (a, b) in lower.iter_mut().zip(upper.iter()) {
286        a.conditional_assign(b, is_zero);
287    }
288}
289
290#[inline]
291fn add_mul_vvw(z: &mut [Limb], x: &[Limb], y: Limb) -> Limb {
292    let mut c = Limb::ZERO;
293    for (zi, xi) in z.iter_mut().zip(x.iter()) {
294        let (z0, z1) = zi.mac(*xi, y, Limb::ZERO);
295        let (zi_, c_) = z0.overflowing_add(c);
296        *zi = zi_;
297        c = c_.wrapping_add(z1);
298    }
299
300    c
301}
302
303#[inline(always)]
304fn sub_vv(z: &mut [Limb], x: &[Limb], y: &[Limb]) {
305    let mut borrow = Limb::ZERO;
306    for (i, (&xi, &yi)) in x.iter().zip(y.iter()).enumerate().take(z.len()) {
307        let (zi, new_borrow) = xi.sbb(yi, borrow);
308        z[i] = zi;
309        borrow = new_borrow;
310    }
311}
312
313#[cfg(test)]
314mod tests {
315    use super::{BoxedMontyForm, BoxedMontyParams, BoxedUint};
316
317    /// Regression test for RustCrypto/crypto-bigint#441
318    #[test]
319    fn square() {
320        let x = 0x20u128;
321        let modulus = 0xB44677037A7DBDE04814256570DCBD8Du128;
322
323        let boxed_modulus = BoxedUint::from(modulus);
324        let boxed_params = BoxedMontyParams::new(boxed_modulus.to_odd().unwrap());
325        let boxed_monty = BoxedMontyForm::new(BoxedUint::from(x), boxed_params);
326        let boxed_square = boxed_monty.square();
327
328        // TODO(tarcieri): test for correct output
329        assert!(boxed_square.as_montgomery() < boxed_square.params().modulus());
330    }
331}
crypto_bigint/modular/boxed_monty_form/mul.rs

crypto_bigint/modular/boxed_monty_form/
mul.rs
