crypto_bigint/uint/boxed/
add_mod.rs

1//! [`BoxedUint`] modular addition operations.
2
3use crate::{AddMod, BoxedUint, Limb, NonZero};
4
5impl BoxedUint {
6    /// Computes `self + rhs mod p`.
7    ///
8    /// Assumes `self + rhs` as unbounded integer is `< 2p`.
9    #[must_use]
10    pub fn add_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
11        let mut result = self.clone();
12        result.add_mod_assign(rhs, p);
13        result
14    }
15
16    /// Computes `self + rhs mod p` and writes the result in `self`.
17    ///
18    /// Assumes `self + rhs` as unbounded integer is `< 2p`.
19    pub fn add_mod_assign(&mut self, rhs: &Self, p: &NonZero<Self>) {
20        debug_assert_eq!(self.bits_precision(), p.bits_precision());
21        debug_assert_eq!(rhs.bits_precision(), p.bits_precision());
22        debug_assert!(*self < p.as_ref());
23        debug_assert!(rhs < p.as_ref());
24
25        let carry = self.carrying_add_assign(rhs, Limb::ZERO);
26        self.sub_assign_mod_with_carry(carry, p, p);
27    }
28
29    /// Computes `self + self mod p`.
30    ///
31    /// Assumes `self` as unbounded integer is `< p`.
32    #[must_use]
33    pub fn double_mod(&self, p: &NonZero<Self>) -> Self {
34        let (mut w, carry) = self.shl1();
35        w.sub_assign_mod_with_carry(carry, p, p);
36        w
37    }
38
39    /// Computes `self + rhs mod p` for the special modulus
40    /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
41    ///
42    /// Assumes `self + rhs` as unbounded integer is `< 2p`.
43    #[must_use]
44    pub fn add_mod_special(&self, rhs: &Self, c: Limb) -> Self {
45        // `BoxedUint::carrying_add` also works with a carry greater than 1.
46        let (mut out, carry) = self.carrying_add(rhs, c);
47
48        // If overflow occurred, then above addition of `c` already accounts
49        // for the overflow. Otherwise, we need to subtract `c` again, which
50        // in that case cannot underflow.
51        let l = carry.wrapping_sub(Limb::ONE) & c;
52        out.wrapping_sub_assign(l);
53        out
54    }
55}
56
57impl AddMod for BoxedUint {
58    type Output = Self;
59
60    fn add_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
61        self.add_mod(rhs, p)
62    }
63}
64
65#[cfg(test)]
66mod tests {
67    use super::BoxedUint;
68    use hex_literal::hex;
69
70    #[cfg(feature = "rand_core")]
71    use crate::{Limb, NonZero, Random, RandomMod};
72    #[cfg(feature = "rand_core")]
73    use rand_core::SeedableRng;
74
75    // TODO(tarcieri): proptests
76
77    #[test]
78    fn add_mod_nist_p256() {
79        let a = BoxedUint::from_be_slice(
80            &hex!("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"),
81            256,
82        )
83        .unwrap();
84        let b = BoxedUint::from_be_slice(
85            &hex!("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"),
86            256,
87        )
88        .unwrap();
89        let n = BoxedUint::from_be_slice(
90            &hex!("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"),
91            256,
92        )
93        .unwrap()
94        .to_nz()
95        .unwrap();
96
97        let actual = a.add_mod(&b, &n);
98        let expected = BoxedUint::from_be_slice(
99            &hex!("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956"),
100            256,
101        )
102        .unwrap();
103
104        assert_eq!(expected, actual);
105    }
106
107    #[test]
108    fn double_mod_expected() {
109        let a = BoxedUint::from_be_hex(
110            "44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56",
111            256,
112        )
113        .unwrap();
114        let n = BoxedUint::from_be_hex(
115            "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
116            256,
117        )
118        .unwrap()
119        .to_nz()
120        .unwrap();
121
122        assert_eq!(a.add_mod(&a, &n), a.double_mod(&n));
123    }
124
125    #[test]
126    #[cfg(feature = "rand_core")]
127    fn add_mod_special() {
128        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
129        let moduli = [
130            NonZero::<Limb>::random_from_rng(&mut rng),
131            NonZero::<Limb>::random_from_rng(&mut rng),
132        ];
133        let sizes = if cfg!(miri) {
134            &[1, 2, 3][..]
135        } else {
136            &[1, 2, 3, 4, 8, 16][..]
137        };
138
139        for size in sizes.iter().copied() {
140            let bits = size * Limb::BITS;
141
142            for special in &moduli {
143                let zero = BoxedUint::zero_with_precision(bits);
144                let one = BoxedUint::one_with_precision(bits);
145                let p = NonZero::new(zero.wrapping_sub(special.get())).unwrap();
146                let minus_one = p.wrapping_sub(Limb::ONE);
147
148                let base_cases = [
149                    (&zero, &zero, &zero),
150                    (&one, &zero, &one),
151                    (&zero, &one, &one),
152                    (&minus_one, &one, &zero),
153                    (&one, &minus_one, &zero),
154                ];
155
156                for (a, b, c) in base_cases {
157                    let x = a.add_mod_special(b, *special.as_ref());
158                    assert_eq!(&x, c, "{} - {} mod {} = {} != {}", a, b, p, x, c);
159                }
160
161                for _i in 0..100 {
162                    let a = BoxedUint::random_mod_vartime(&mut rng, &p);
163                    let b = BoxedUint::random_mod_vartime(&mut rng, &p);
164
165                    let c = a.add_mod_special(&b, *special.as_ref());
166                    assert!(c < *p, "not reduced: {} >= {} ", c, p);
167
168                    let expected = a.add_mod(&b, &p);
169                    assert_eq!(c, expected, "incorrect result");
170                }
171            }
172        }
173    }
174}
crypto_bigint/uint/boxed/add_mod.rs

crypto_bigint/uint/boxed/
add_mod.rs
