crypto_bigint/uint/
mul_mod.rs

1//! [`Uint`] modular multiplication operations.
2
3use crate::{Limb, MulMod, NonZero, SquareMod, Uint, WideWord, div_limb::mul_rem};
4
5impl<const LIMBS: usize> Uint<LIMBS> {
6    /// Computes `self * rhs mod p`.
7    #[must_use]
8    pub fn mul_mod(&self, rhs: &Uint<LIMBS>, p: &NonZero<Uint<LIMBS>>) -> Uint<LIMBS> {
9        let lo_hi = self.widening_mul(rhs);
10        Self::rem_wide(lo_hi, p)
11    }
12
13    /// Computes `self * rhs mod p` in variable time with respect to `p`.
14    #[must_use]
15    pub fn mul_mod_vartime(&self, rhs: &Uint<LIMBS>, p: &NonZero<Uint<LIMBS>>) -> Uint<LIMBS> {
16        let lo_hi = self.widening_mul(rhs);
17        Self::rem_wide_vartime(lo_hi, p)
18    }
19
20    /// Computes `self * rhs mod p` for the special modulus
21    /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
22    ///
23    /// When `c` is zero, `p = MAX+1` and the result is wrapping multiplication.
24    ///
25    /// For the modulus reduction, this function implements Algorithm 14.47 from
26    /// the "Handbook of Applied Cryptography", by A. Menezes, P. van Oorschot,
27    /// and S. Vanstone, CRC Press, 1996.
28    #[must_use]
29    pub const fn mul_mod_special(&self, rhs: &Self, c: Limb) -> Self {
30        // We implicitly assume `LIMBS > 0`, because `Uint<0>` doesn't compile.
31        // Still the case `LIMBS == 1` needs special handling.
32        if LIMBS == 1 {
33            let a = self.limbs[0];
34            let b = rhs.limbs[0];
35
36            // For c = 0, use a nonzero placeholder divisor and select the
37            // wrapping product in constant time.
38            let (p, c_is_nonzero) = Limb::ZERO.wrapping_sub(c).to_nz_or_one();
39            let reduced = mul_rem(a, b, p);
40            let reduced = Limb::select(a.wrapping_mul(b), reduced, c_is_nonzero);
41            return Self::from_word(reduced.0);
42        }
43
44        let (lo, hi) = self.widening_mul(rhs);
45
46        // Now use Algorithm 14.47 for the reduction
47        let (lo, carry) = mac_by_limb(&lo, &hi, c, Limb::ZERO);
48
49        let (lo, carry) = {
50            // Widen before adding: carry can equal Limb::MAX.
51            let rhs = (carry.0 as WideWord + 1) * c.0 as WideWord;
52            lo.carrying_add(&Self::from_wide_word(rhs), Limb::ZERO)
53        };
54
55        let (lo, _) = {
56            let rhs = carry.0.wrapping_sub(1) & c.0;
57            lo.borrowing_sub(&Self::from_word(rhs), Limb::ZERO)
58        };
59
60        lo
61    }
62
63    /// Computes `self * self mod p`.
64    #[must_use]
65    pub const fn square_mod(&self, p: &NonZero<Uint<LIMBS>>) -> Self {
66        let lo_hi = self.widening_square();
67        Self::rem_wide(lo_hi, p)
68    }
69
70    /// Computes `self * self mod p` in variable time with respect to `p`.
71    #[must_use]
72    pub const fn square_mod_vartime(&self, p: &NonZero<Uint<LIMBS>>) -> Self {
73        let lo_hi = self.widening_square();
74        Self::rem_wide_vartime(lo_hi, p)
75    }
76}
77
78impl<const LIMBS: usize> MulMod for Uint<LIMBS> {
79    type Output = Self;
80
81    fn mul_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
82        self.mul_mod(rhs, p)
83    }
84}
85
86impl<const LIMBS: usize> SquareMod for Uint<LIMBS> {
87    type Output = Self;
88
89    fn square_mod(&self, p: &NonZero<Self>) -> Self {
90        self.square_mod(p)
91    }
92}
93
94/// Computes `a + (b * c) + carry`, returning the result along with the new carry.
95const fn mac_by_limb<const LIMBS: usize>(
96    a: &Uint<LIMBS>,
97    b: &Uint<LIMBS>,
98    c: Limb,
99    carry: Limb,
100) -> (Uint<LIMBS>, Limb) {
101    let mut i = 0;
102    let mut a = *a;
103    let mut carry = carry;
104
105    while i < LIMBS {
106        (a.limbs[i], carry) = b.limbs[i].carrying_mul_add(c, a.limbs[i], carry);
107        i += 1;
108    }
109
110    (a, carry)
111}
112
113#[cfg(all(test, feature = "rand_core"))]
114mod tests {
115    use crate::{Limb, NonZero, Random, RandomMod, Uint};
116    use rand_core::SeedableRng;
117
118    #[test]
119    fn mul_mod_special_zero_c() {
120        fn test_size<const LIMBS: usize>() {
121            let values = [Uint::<LIMBS>::ZERO, Uint::ONE, Uint::MAX];
122            for a in values {
123                for b in values {
124                    assert_eq!(a.mul_mod_special(&b, Limb::ZERO), a.wrapping_mul(&b));
125                }
126            }
127        }
128
129        test_size::<1>();
130        test_size::<2>();
131        test_size::<3>();
132        test_size::<4>();
133    }
134
135    #[test]
136    fn mul_mod_special_max_c() {
137        fn test_size<const LIMBS: usize>() {
138            let c = Uint::<LIMBS>::from(Limb::MAX);
139            let p = NonZero::new(Uint::ZERO.wrapping_sub(&c)).unwrap();
140            let a = p.wrapping_sub(&c);
141
142            // (p - c)^2 mod p = c^2. With at least three limbs, the first
143            // reduction produces a carry of Limb::MAX, so carry + 1 overflows.
144            let expected = c.wrapping_mul(&c);
145            assert_eq!(a.mul_mod_special(&a, Limb::MAX), expected);
146            assert_eq!(a.mul_mod(&a, &p), expected);
147        }
148
149        test_size::<3>();
150        test_size::<4>();
151    }
152
153    #[test]
154    fn mul_mod_special() {
155        fn test_size<const LIMBS: usize>() {
156            let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
157            let moduli = [
158                NonZero::<Limb>::random_from_rng(&mut rng),
159                NonZero::<Limb>::random_from_rng(&mut rng),
160            ];
161
162            for special in &moduli {
163                let p = &NonZero::new(Uint::ZERO.wrapping_sub(&Uint::from(special.get()))).unwrap();
164
165                let minus_one = p.wrapping_sub(&Uint::ONE);
166
167                let base_cases = [
168                    (Uint::ZERO, Uint::ZERO, Uint::ZERO),
169                    (Uint::ONE, Uint::ZERO, Uint::ZERO),
170                    (Uint::ZERO, Uint::ONE, Uint::ZERO),
171                    (Uint::ONE, Uint::ONE, Uint::ONE),
172                    (minus_one, minus_one, Uint::ONE),
173                    (minus_one, Uint::ONE, minus_one),
174                    (Uint::ONE, minus_one, minus_one),
175                ];
176                for (a, b, c) in &base_cases {
177                    let x = a.mul_mod_special(b, *special.as_ref());
178                    assert_eq!(*c, x, "{} * {} mod {} = {} != {}", a, b, p, x, c);
179                }
180
181                let rounds = if cfg!(miri) { 10 } else { 100 };
182                for _i in 0..rounds {
183                    let a = Uint::<LIMBS>::random_mod_vartime(&mut rng, p);
184                    let b = Uint::<LIMBS>::random_mod_vartime(&mut rng, p);
185
186                    let c = a.mul_mod_special(&b, *special.as_ref());
187                    assert!(c < **p, "not reduced: {} >= {} ", c, p);
188
189                    let expected = {
190                        let prod = a.widening_mul(&b);
191                        Uint::rem_wide_vartime(prod, p)
192                    };
193                    assert_eq!(c, expected, "incorrect result");
194                }
195            }
196        }
197
198        test_size::<1>();
199        test_size::<2>();
200        test_size::<3>();
201        if cfg!(not(miri)) {
202            test_size::<4>();
203            test_size::<8>();
204            test_size::<16>();
205        }
206    }
207}
crypto_bigint/uint/mul_mod.rs

crypto_bigint/uint/
mul_mod.rs
