crypto_bigint/uint/boxed/
add_mod.rs

1//! [`BoxedUint`] modular addition operations.
2
3use crate::{AddMod, BoxedUint, Limb, Zero};
4
5impl BoxedUint {
6    /// Computes `self + rhs mod p`.
7    ///
8    /// Assumes `self + rhs` as unbounded integer is `< 2p`.
9    pub fn add_mod(&self, rhs: &Self, p: &Self) -> Self {
10        debug_assert_eq!(self.bits_precision(), p.bits_precision());
11        debug_assert_eq!(rhs.bits_precision(), p.bits_precision());
12        debug_assert!(self < p);
13        debug_assert!(rhs < p);
14
15        let (mut w, carry) = self.adc(rhs, Limb::ZERO);
16
17        // Attempt to subtract the modulus, to ensure the result is in the field.
18        let borrow = w.sbb_assign(p, Limb::ZERO);
19        let (_, borrow) = carry.sbb(Limb::ZERO, borrow);
20
21        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
22        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the
23        // modulus.
24        w.conditional_adc_assign(p, !borrow.is_zero());
25        w
26    }
27
28    /// Computes `self + self mod p`.
29    ///
30    /// Assumes `self` as unbounded integer is `< p`.
31    pub fn double_mod(&self, p: &Self) -> Self {
32        let (mut w, carry) = self.overflowing_shl1();
33
34        // Attempt to subtract the modulus, to ensure the result is in the field.
35        let borrow = w.sbb_assign(p, Limb::ZERO);
36        let (_, borrow) = carry.sbb(Limb::ZERO, borrow);
37
38        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
39        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the
40        // modulus.
41        w.conditional_adc_assign(p, !borrow.is_zero());
42        w
43    }
44}
45
46impl AddMod for BoxedUint {
47    type Output = Self;
48
49    fn add_mod(&self, rhs: &Self, p: &Self) -> Self {
50        self.add_mod(rhs, p)
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::BoxedUint;
57    use hex_literal::hex;
58
59    // TODO(tarcieri): proptests
60
61    #[test]
62    fn add_mod_nist_p256() {
63        let a = BoxedUint::from_be_slice(
64            &hex!("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"),
65            256,
66        )
67        .unwrap();
68        let b = BoxedUint::from_be_slice(
69            &hex!("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"),
70            256,
71        )
72        .unwrap();
73        let n = BoxedUint::from_be_slice(
74            &hex!("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"),
75            256,
76        )
77        .unwrap();
78
79        let actual = a.add_mod(&b, &n);
80        let expected = BoxedUint::from_be_slice(
81            &hex!("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956"),
82            256,
83        )
84        .unwrap();
85
86        assert_eq!(expected, actual);
87    }
88
89    #[test]
90    fn double_mod_expected() {
91        let a = BoxedUint::from_be_hex(
92            "44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56",
93            256,
94        )
95        .unwrap();
96        let n = BoxedUint::from_be_hex(
97            "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
98            256,
99        )
100        .unwrap();
101
102        assert_eq!(a.add_mod(&a, &n), a.double_mod(&n));
103    }
104}
crypto_bigint/uint/boxed/add_mod.rs

crypto_bigint/uint/boxed/
add_mod.rs
