primeorder/tables/
lookup.rs

1//! Precomputed lookup tables which allow multiples of an elliptic curve point to be selected in
2//! constant time.
3
4use elliptic_curve::{
5    group::Group,
6    subtle::{Choice, ConditionallySelectable, ConstantTimeEq},
7};
8
9/// Internal constant for the number of entries in a [`LookupTable`].
10///
11/// This is defined separately from `LookupTable::SIZE` because we can't use an inherent associated
12/// constant of a generic type in generic contexts, and this doesn't vary depending on `Point`.
13const LUT_SIZE: usize = 8;
14
15/// Lookup table containing precomputed values `[p, 2p, 3p, ..., 8p]`
16#[derive(Clone, Copy, Debug, Default)]
17pub struct LookupTable<Point> {
18    points: [Point; LUT_SIZE],
19}
20
21impl<Point> LookupTable<Point>
22where
23    Point: ConditionallySelectable + Group,
24{
25    /// Number of entries in the lookup table.
26    pub const SIZE: usize = LUT_SIZE;
27
28    /// Compute a new lookup table from the given point.
29    #[inline]
30    pub fn new(p: Point) -> Self {
31        let mut points = [p; LUT_SIZE];
32
33        for j in 0..(LUT_SIZE - 1) {
34            points[j + 1] = p + points[j];
35        }
36
37        Self { points }
38    }
39
40    /// Given `-8 <= x <= 8`, returns `x * p` in constant time.
41    #[allow(clippy::cast_sign_loss)]
42    #[inline]
43    pub fn select(&self, x: i8) -> Point {
44        debug_assert!((-8..=8).contains(&x));
45
46        // Compute xabs = |x|
47        let xmask = x >> 7;
48        let xabs = (x + xmask) ^ xmask;
49
50        // Get an array element in constant time
51        let mut t = Point::identity();
52
53        #[allow(clippy::cast_possible_truncation)]
54        for j in 1..(LUT_SIZE + 1) {
55            let c = (xabs as u8).ct_eq(&(j as u8));
56            t.conditional_assign(&self.points[j - 1], c);
57        }
58        // Now t == |x| * p.
59
60        let neg_mask = Choice::from((xmask & 1) as u8);
61        t.conditional_assign(&-t, neg_mask);
62        // Now t == x * p.
63
64        t
65    }
66
67    /// Given `-8 <= x <= 8`, returns `x * p` in variable time.
68    #[allow(clippy::cast_sign_loss)]
69    #[inline]
70    pub fn select_vartime(&self, x: i8) -> Point {
71        debug_assert!((-8..=8).contains(&x));
72
73        let xabs = x.unsigned_abs();
74        let t = if xabs == 0 {
75            Point::identity()
76        } else {
77            self.points[xabs as usize - 1]
78        };
79
80        if x < 0 { -t } else { t }
81    }
82}
primeorder/tables/lookup.rs

primeorder/tables/
lookup.rs
