crypto_bigint/uint/boxed/
cmp.rs

1//! [`BoxedUint`] comparisons.
2//!
3//! By default these are all constant-time and use the `subtle` crate.
4
5pub(super) use core::cmp::{max, Ordering};
6
7use super::BoxedUint;
8use crate::{ConstChoice, Limb};
9use subtle::{
10    Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess,
11};
12
13impl BoxedUint {
14    /// Returns the Ordering between `self` and `rhs` in variable time.
15    pub fn cmp_vartime(&self, rhs: &Self) -> Ordering {
16        debug_assert_eq!(self.limbs.len(), rhs.limbs.len());
17        let mut i = self.limbs.len() - 1;
18        loop {
19            // TODO: investigate if directly comparing limbs is faster than performing a
20            // subtraction between limbs
21            let (val, borrow) = self.limbs[i].sbb(rhs.limbs[i], Limb::ZERO);
22            if val.0 != 0 {
23                return if borrow.0 != 0 {
24                    Ordering::Less
25                } else {
26                    Ordering::Greater
27                };
28            }
29            if i == 0 {
30                return Ordering::Equal;
31            }
32            i -= 1;
33        }
34    }
35}
36
37impl ConstantTimeEq for BoxedUint {
38    #[inline]
39    fn ct_eq(&self, other: &Self) -> Choice {
40        let limbs = max(self.nlimbs(), other.nlimbs());
41        let mut ret = Choice::from(1u8);
42
43        for i in 0..limbs {
44            let a = self.limbs.get(i).unwrap_or(&Limb::ZERO);
45            let b = other.limbs.get(i).unwrap_or(&Limb::ZERO);
46            ret &= a.ct_eq(b);
47        }
48
49        ret
50    }
51}
52
53impl ConstantTimeGreater for BoxedUint {
54    #[inline]
55    fn ct_gt(&self, other: &Self) -> Choice {
56        let (_, borrow) = other.sbb(self, Limb::ZERO);
57        ConstChoice::from_word_mask(borrow.0).into()
58    }
59}
60
61impl ConstantTimeLess for BoxedUint {
62    #[inline]
63    fn ct_lt(&self, other: &Self) -> Choice {
64        let (_, borrow) = self.sbb(other, Limb::ZERO);
65        ConstChoice::from_word_mask(borrow.0).into()
66    }
67}
68
69impl Eq for BoxedUint {}
70impl PartialEq for BoxedUint {
71    fn eq(&self, other: &Self) -> bool {
72        self.ct_eq(other).into()
73    }
74}
75
76impl Ord for BoxedUint {
77    fn cmp(&self, other: &Self) -> Ordering {
78        let mut ret = Ordering::Equal;
79        ret.conditional_assign(&Ordering::Greater, self.ct_gt(other));
80        ret.conditional_assign(&Ordering::Less, self.ct_lt(other));
81
82        #[cfg(debug_assertions)]
83        if ret == Ordering::Equal {
84            debug_assert_eq!(self, other);
85        }
86
87        ret
88    }
89}
90
91impl PartialOrd for BoxedUint {
92    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
93        Some(self.cmp(other))
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::BoxedUint;
100    use core::cmp::Ordering;
101    use subtle::{ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
102
103    #[test]
104    fn ct_eq() {
105        let a = BoxedUint::zero();
106        let b = BoxedUint::one();
107
108        assert!(bool::from(a.ct_eq(&a)));
109        assert!(!bool::from(a.ct_eq(&b)));
110        assert!(!bool::from(b.ct_eq(&a)));
111        assert!(bool::from(b.ct_eq(&b)));
112    }
113
114    #[test]
115    fn ct_gt() {
116        let a = BoxedUint::zero();
117        let b = BoxedUint::one();
118        let c = BoxedUint::max(64);
119
120        assert!(bool::from(b.ct_gt(&a)));
121        assert!(bool::from(c.ct_gt(&a)));
122        assert!(bool::from(c.ct_gt(&b)));
123
124        assert!(!bool::from(a.ct_gt(&a)));
125        assert!(!bool::from(b.ct_gt(&b)));
126        assert!(!bool::from(c.ct_gt(&c)));
127
128        assert!(!bool::from(a.ct_gt(&b)));
129        assert!(!bool::from(a.ct_gt(&c)));
130        assert!(!bool::from(b.ct_gt(&c)));
131    }
132
133    #[test]
134    fn ct_lt() {
135        let a = BoxedUint::zero();
136        let b = BoxedUint::one();
137        let c = BoxedUint::max(64);
138
139        assert!(bool::from(a.ct_lt(&b)));
140        assert!(bool::from(a.ct_lt(&c)));
141        assert!(bool::from(b.ct_lt(&c)));
142
143        assert!(!bool::from(a.ct_lt(&a)));
144        assert!(!bool::from(b.ct_lt(&b)));
145        assert!(!bool::from(c.ct_lt(&c)));
146
147        assert!(!bool::from(b.ct_lt(&a)));
148        assert!(!bool::from(c.ct_lt(&a)));
149        assert!(!bool::from(c.ct_lt(&b)));
150    }
151
152    #[test]
153    fn cmp() {
154        let a = BoxedUint::zero();
155        let b = BoxedUint::one();
156        let c = BoxedUint::max(64);
157
158        assert_eq!(a.cmp(&b), Ordering::Less);
159        assert_eq!(a.cmp(&c), Ordering::Less);
160        assert_eq!(b.cmp(&c), Ordering::Less);
161
162        assert_eq!(a.cmp(&a), Ordering::Equal);
163        assert_eq!(b.cmp(&b), Ordering::Equal);
164        assert_eq!(c.cmp(&c), Ordering::Equal);
165
166        assert_eq!(b.cmp(&a), Ordering::Greater);
167        assert_eq!(c.cmp(&a), Ordering::Greater);
168        assert_eq!(c.cmp(&b), Ordering::Greater);
169    }
170}
crypto_bigint/uint/boxed/cmp.rs

crypto_bigint/uint/boxed/
cmp.rs
