primeorder/tables/
basepoint.rs

1//! Precomputed basepoint tables for accelerating fixed-base scalar multiplication.
2
3#![allow(clippy::cast_possible_truncation, clippy::needless_range_loop)]
4
5#[cfg(not(any(feature = "critical-section", feature = "std")))]
6compile_error!("`basepoint-table` feature requires either `critical-section` or `std`");
7
8use super::LookupTable;
9use crate::{PrimeCurveParams, ProjectivePoint, Radix16Decomposition, Radix16Digits, Scalar};
10use core::ops::Deref;
11use elliptic_curve::{
12    FieldBytesSize, array::typenum::Unsigned, ff::PrimeField, group::Group,
13    subtle::ConditionallySelectable,
14};
15
16#[cfg(feature = "critical-section")]
17use once_cell::sync::Lazy as LazyLock;
18#[cfg(all(feature = "std", not(feature = "critical-section")))]
19use std::sync::LazyLock;
20
21/// Precomputed lookup table of multiples of a base point, a.k.a. generator.
22///
23/// This type leverages lazy computation, and requires one of the following crate features to be
24/// enabled in order to work:
25/// - `std`: leverages `std::sync::LazyLock`
26/// - `critical-section`: leverages `once_cell::sync::Lazy` via the `critical-section` crate,
27///   enabling the feature to be used in `no_std` contexts.
28#[derive(Debug)]
29pub struct BasepointTable<Point, const WINDOW_SIZE: usize> {
30    tables: LazyLock<[LookupTable<Point>; WINDOW_SIZE]>,
31}
32
33impl<Point, const WINDOW_SIZE: usize> BasepointTable<Point, WINDOW_SIZE>
34where
35    Point: ConditionallySelectable + Default + Group,
36{
37    /// Create a new [`BasepointTable`] which is lazily initialized on first use and can be bound
38    /// to a constant.
39    ///
40    /// Computed using the `Point`'s [`Group::generator`] as the base point.
41    pub const fn new() -> Self {
42        /// Inner function to initialize the table.
43        fn init_table<Point, const N: usize>() -> [LookupTable<Point>; N]
44        where
45            Point: ConditionallySelectable + Default + Group,
46        {
47            // Ensure basepoint table contains the expected number of entries for the scalar's size
48            const {
49                assert!(
50                    N as u32 == 1 + Point::Scalar::NUM_BITS.div_ceil(8),
51                    "incorrectly sized basepoint table"
52                );
53            }
54
55            let mut generator = Point::generator();
56            let mut res = [LookupTable::<Point>::default(); N];
57
58            for i in 0..N {
59                res[i] = LookupTable::new(generator);
60
61                // We are storing tables spaced by two radix steps,
62                // to decrease the size of the precomputed data.
63                for _ in 0..8 {
64                    generator = generator.double();
65                }
66            }
67
68            res
69        }
70
71        Self {
72            tables: LazyLock::new(init_table),
73        }
74    }
75}
76
77impl<C: PrimeCurveParams, const WINDOW_SIZE: usize>
78    BasepointTable<ProjectivePoint<C>, WINDOW_SIZE>
79{
80    /// Multiply `Point::generator` by the given scalar in constant-time, using the precomputed
81    /// basepoint table to accelerate the scalar multiplication.
82    pub fn mul(&self, k: &Scalar<C>) -> ProjectivePoint<C> {
83        let digits = Radix16Decomposition::<Radix16Digits<C>>::new(k);
84        let len = FieldBytesSize::<C>::USIZE;
85        let mut acc = self[len].select(digits[len * 2]);
86        let mut acc2 = ProjectivePoint::<C>::IDENTITY;
87        for i in (0..len).rev() {
88            acc2 += &self[i].select(digits[i * 2 + 1]);
89            acc += &self[i].select(digits[i * 2]);
90        }
91
92        // This is the price of halving the precomputed table size.
93        for _ in 0..4 {
94            acc2 = acc2.double();
95        }
96
97        acc + acc2
98    }
99
100    /// Multiply `Point::generator` by the given scalar in constant-time, using the precomputed
101    /// basepoint table to accelerate the scalar multiplication.
102    ///
103    /// <div class = "warning">
104    /// <b>Security Warning</b>
105    ///
106    /// Variable-time scalar multiplication can potentially leak secret values and should NOT be
107    /// used with them.
108    /// </div>
109    pub fn mul_vartime(&self, k: &Scalar<C>) -> ProjectivePoint<C> {
110        let digits = Radix16Decomposition::<Radix16Digits<C>>::new(k);
111        let len = FieldBytesSize::<C>::USIZE;
112        let mut acc = self[len].select_vartime(digits[len * 2]);
113        let mut acc2 = ProjectivePoint::<C>::IDENTITY;
114        for i in (0..len).rev() {
115            acc2 += &self[i].select_vartime(digits[i * 2 + 1]);
116            acc += &self[i].select_vartime(digits[i * 2]);
117        }
118
119        // This is the price of halving the precomputed table size.
120        for _ in 0..4 {
121            acc2 = acc2.double();
122        }
123
124        acc + acc2
125    }
126}
127
128impl<Point, const WINDOW_SIZE: usize> Default for BasepointTable<Point, WINDOW_SIZE>
129where
130    Point: ConditionallySelectable + Default + Group,
131{
132    fn default() -> Self {
133        Self::new()
134    }
135}
136
137impl<Point, const WINDOW_SIZE: usize> Deref for BasepointTable<Point, WINDOW_SIZE> {
138    type Target = [LookupTable<Point>; WINDOW_SIZE];
139
140    #[inline]
141    fn deref(&self) -> &[LookupTable<Point>; WINDOW_SIZE] {
142        &self.tables
143    }
144}
primeorder/tables/basepoint.rs

primeorder/tables/
basepoint.rs
