crypto_bigint/uint/boxed/
sub_mod.rs

1//! [`BoxedUint`] modular subtraction operations.
2
3use crate::{BoxedUint, Limb, NonZero, SubMod};
4
5impl BoxedUint {
6    /// Computes `self - rhs mod p`.
7    ///
8    /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
9    #[must_use]
10    pub fn sub_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
11        debug_assert_eq!(self.bits_precision(), p.bits_precision());
12        debug_assert_eq!(rhs.bits_precision(), p.bits_precision());
13        debug_assert!(self < p.as_ref());
14        debug_assert!(rhs < p.as_ref());
15
16        let (mut out, borrow) = self.borrowing_sub(rhs, Limb::ZERO);
17
18        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
19        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
20        out.conditional_carrying_add_assign(p, !borrow.is_zero());
21        out
22    }
23
24    /// Returns `(self..., carry) - (rhs...) mod (p...)`, where `carry <= 1`.
25    /// Assumes `-(p...) <= (self..., carry) - (rhs...) < (p...)`.
26    #[inline(always)]
27    pub(crate) fn sub_assign_mod_with_carry(&mut self, carry: Limb, rhs: &Self, p: &Self) {
28        debug_assert!(carry.0 <= 1);
29
30        let borrow = self.borrowing_sub_assign(rhs, Limb::ZERO);
31
32        // The new `borrow = Word::MAX` iff `carry == 0` and `borrow == Word::MAX`.
33        let mask = carry.wrapping_neg().not().bitand(borrow);
34
35        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
36        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
37        self.conditional_carrying_add_assign(p, !mask.is_zero());
38    }
39
40    /// Computes `self - rhs mod p` for the special modulus
41    /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
42    ///
43    /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
44    #[must_use]
45    pub fn sub_mod_special(&self, rhs: &Self, c: Limb) -> Self {
46        let (mut out, borrow) = self.borrowing_sub(rhs, Limb::ZERO);
47
48        // If underflow occurred, then we need to subtract `c` to account for
49        // the underflow. This cannot underflow due to the assumption
50        // `self - rhs >= -p`.
51        out.wrapping_sub_assign(borrow & c);
52        out
53    }
54}
55
56impl SubMod for BoxedUint {
57    type Output = Self;
58
59    fn sub_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
60        self.sub_mod(rhs, p)
61    }
62}
63
64#[cfg(test)]
65mod tests {
66    use super::BoxedUint;
67    use hex_literal::hex;
68
69    #[cfg(feature = "rand_core")]
70    use crate::{Limb, NonZero, Random, RandomMod};
71    #[cfg(feature = "rand_core")]
72    use rand_core::SeedableRng;
73
74    #[test]
75    fn sub_mod_nist_p256() {
76        let a = BoxedUint::from_be_slice(
77            &hex!("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956"),
78            256,
79        )
80        .unwrap();
81        let b = BoxedUint::from_be_slice(
82            &hex!("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"),
83            256,
84        )
85        .unwrap();
86        let n = BoxedUint::from_be_slice(
87            &hex!("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"),
88            256,
89        )
90        .unwrap()
91        .to_nz()
92        .unwrap();
93
94        let actual = a.sub_mod(&b, &n);
95        let expected = BoxedUint::from_be_slice(
96            &hex!("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"),
97            256,
98        )
99        .unwrap();
100
101        assert_eq!(expected, actual);
102    }
103
104    #[test]
105    #[cfg(feature = "rand_core")]
106    fn sub_mod_special() {
107        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
108        let moduli = [
109            NonZero::<Limb>::random_from_rng(&mut rng),
110            NonZero::<Limb>::random_from_rng(&mut rng),
111        ];
112        let sizes = if cfg!(miri) {
113            &[1, 2, 3][..]
114        } else {
115            &[1, 2, 3, 4, 8, 16][..]
116        };
117
118        for size in sizes.iter().copied() {
119            let bits = size * Limb::BITS;
120
121            for special in &moduli {
122                let zero = BoxedUint::zero_with_precision(bits);
123                let one = BoxedUint::one_with_precision(bits);
124                let p = NonZero::new(zero.wrapping_sub(special.get())).unwrap();
125                let minus_one = p.wrapping_sub(Limb::ONE);
126
127                let base_cases = [
128                    (&zero, &zero, &zero),
129                    (&one, &zero, &one),
130                    (&zero, &one, &minus_one),
131                    (&minus_one, &minus_one, &zero),
132                    (&zero, &minus_one, &one),
133                ];
134                for (a, b, c) in base_cases {
135                    let x = a.sub_mod_special(b, *special.as_ref());
136                    assert_eq!(&x, c, "{} - {} mod {} = {} != {}", a, b, p, x, c);
137                }
138
139                for _i in 0..100 {
140                    let a = BoxedUint::random_mod_vartime(&mut rng, &p);
141                    let b = BoxedUint::random_mod_vartime(&mut rng, &p);
142
143                    let c = a.sub_mod_special(&b, *special.as_ref());
144                    assert!(c < *p, "not reduced: {} >= {} ", c, p);
145
146                    let expected = a.sub_mod(&b, &p);
147                    assert_eq!(c, expected, "incorrect result");
148                }
149            }
150        }
151    }
152}
crypto_bigint/uint/boxed/sub_mod.rs

crypto_bigint/uint/boxed/
sub_mod.rs
