curve25519_dalek/
window.rs

1// -*- mode: rust; -*-
2//
3// This file is part of curve25519-dalek.
4// Copyright (c) 2016-2021 isis lovecruft
5// Copyright (c) 2016-2019 Henry de Valence
6// See LICENSE for licensing information.
7//
8// Authors:
9// - isis agora lovecruft <isis@patternsinthevoid.net>
10// - Henry de Valence <hdevalence@hdevalence.ca>
11
12//! Code for fixed- and sliding-window functionality
13
14#![allow(non_snake_case)]
15
16use core::fmt::Debug;
17
18use cfg_if::cfg_if;
19
20use subtle::Choice;
21use subtle::ConditionallyNegatable;
22use subtle::ConditionallySelectable;
23use subtle::ConstantTimeEq;
24
25use crate::traits::Identity;
26
27use crate::backend::serial::curve_models::AffineNielsPoint;
28use crate::backend::serial::curve_models::ProjectiveNielsPoint;
29use crate::edwards::EdwardsPoint;
30
31#[cfg(feature = "zeroize")]
32use zeroize::Zeroize;
33
34macro_rules! impl_lookup_table {
35    (Name = $name:ident, Size = $size:expr, SizeNeg = $neg:expr, SizeRange = $range:expr, ConversionRange = $conv_range:expr) => {
36        /// A lookup table of precomputed multiples of a point \\(P\\), used to
37        /// compute \\( xP \\) for \\( -8 \leq x \leq 8 \\).
38        ///
39        /// The computation of \\( xP \\) is done in constant time by the `select` function.
40        ///
41        /// Since `LookupTable` does not implement `Index`, it's more difficult
42        /// to accidentally use the table directly.  Unfortunately the table is
43        /// only `pub(crate)` so that we can write hardcoded constants, so it's
44        /// still technically possible.  It would be nice to prevent direct
45        /// access to the table.
46        #[derive(Copy, Clone)]
47        pub struct $name<T>(pub(crate) [T; $size]);
48
49        impl<T> $name<T>
50        where
51            T: Identity + ConditionallySelectable + ConditionallyNegatable,
52        {
53            /// Given \\(-8 \leq x \leq 8\\), return \\(xP\\) in constant time.
54            pub fn select(&self, x: i8) -> T {
55                debug_assert!(x >= $neg);
56                debug_assert!(x as i16 <= $size as i16); // XXX We have to convert to i16s here for the radix-256 case.. this is wrong.
57
58                // Compute xabs = |x|
59                let xmask = x as i16 >> 7;
60                let xabs = (x as i16 + xmask) ^ xmask;
61
62                // Set t = 0 * P = identity
63                let mut t = T::identity();
64                for j in $range {
65                    // Copy `points[j-1] == j*P` onto `t` in constant time if `|x| == j`.
66                    let c = (xabs as u16).ct_eq(&(j as u16));
67                    t.conditional_assign(&self.0[j - 1], c);
68                }
69                // Now t == |x| * P.
70
71                let neg_mask = Choice::from((xmask & 1) as u8);
72                t.conditional_negate(neg_mask);
73                // Now t == x * P.
74
75                t
76            }
77        }
78
79        impl<T: Copy + Default> Default for $name<T> {
80            fn default() -> $name<T> {
81                $name([T::default(); $size])
82            }
83        }
84
85        impl<T: Debug> Debug for $name<T> {
86            fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
87                write!(f, "{:?}(", stringify!($name))?;
88
89                for x in self.0.iter() {
90                    write!(f, "{:?}", x)?;
91                }
92
93                write!(f, ")")
94            }
95        }
96
97        impl<'a> From<&'a EdwardsPoint> for $name<ProjectiveNielsPoint> {
98            fn from(P: &'a EdwardsPoint) -> Self {
99                let mut points = [P.as_projective_niels(); $size];
100                for j in $conv_range {
101                    points[j + 1] = (P + &points[j]).as_extended().as_projective_niels();
102                }
103                $name(points)
104            }
105        }
106
107        impl<'a> From<&'a EdwardsPoint> for $name<AffineNielsPoint> {
108            fn from(P: &'a EdwardsPoint) -> Self {
109                let mut points = [P.as_affine_niels(); $size];
110                // XXX batch inversion would be good if perf mattered here
111                for j in $conv_range {
112                    points[j + 1] = (P + &points[j]).as_extended().as_affine_niels()
113                }
114                $name(points)
115            }
116        }
117
118        #[cfg(feature = "zeroize")]
119        impl<T> Zeroize for $name<T>
120        where
121            T: Copy + Default + Zeroize,
122        {
123            fn zeroize(&mut self) {
124                self.0.iter_mut().zeroize();
125            }
126        }
127    };
128} // End macro_rules! impl_lookup_table
129
130// The first one has to be named "LookupTable" because it's used as a constructor for consts.
131// This is radix-16
132impl_lookup_table! {
133    Name = LookupTable,
134    Size = 8,
135    SizeNeg = -8,
136    SizeRange = 1..9,
137    ConversionRange = 0..7
138}
139
140// The rest only get used to make basepoint tables
141cfg_if! {
142    if #[cfg(feature = "precomputed-tables")] {
143        // radix-32
144        impl_lookup_table! {
145            Name = LookupTableRadix32,
146            Size = 16,
147            SizeNeg = -16,
148            SizeRange = 1..17,
149            ConversionRange = 0..15
150        }
151        // radix-64
152        impl_lookup_table! {
153            Name = LookupTableRadix64,
154            Size = 32,
155            SizeNeg = -32,
156            SizeRange = 1..33,
157            ConversionRange = 0..31
158        }
159        // radix-128
160        impl_lookup_table! {
161            Name = LookupTableRadix128,
162            Size = 64,
163            SizeNeg = -64,
164            SizeRange = 1..65,
165            ConversionRange = 0..63
166        }
167        // radix-256
168        impl_lookup_table! {
169            Name = LookupTableRadix256,
170            Size = 128,
171            SizeNeg = -128,
172            SizeRange = 1..129,
173            ConversionRange = 0..127
174        }
175
176        // For homogeneity we then alias it to "LookupTableRadix16".
177        pub(crate) type LookupTableRadix16<T> = LookupTable<T>;
178    }
179}
180
181/// Holds odd multiples 1A, 3A, ..., 15A of a point A.
182#[derive(Copy, Clone)]
183pub(crate) struct NafLookupTable5<T>(pub(crate) [T; 8]);
184
185impl<T: Copy> NafLookupTable5<T> {
186    /// Given public, odd \\( x \\) with \\( 0 < x < 2^4 \\), return \\(xA\\).
187    pub fn select(&self, x: usize) -> T {
188        debug_assert_eq!(x & 1, 1);
189        debug_assert!(x < 16);
190
191        self.0[x / 2]
192    }
193}
194
195impl<T: Debug> Debug for NafLookupTable5<T> {
196    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
197        write!(f, "NafLookupTable5({:?})", self.0)
198    }
199}
200
201impl<'a> From<&'a EdwardsPoint> for NafLookupTable5<ProjectiveNielsPoint> {
202    fn from(A: &'a EdwardsPoint) -> Self {
203        let mut Ai = [A.as_projective_niels(); 8];
204        let A2 = A.double();
205        for i in 0..7 {
206            Ai[i + 1] = (&A2 + &Ai[i]).as_extended().as_projective_niels();
207        }
208        // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A]
209        NafLookupTable5(Ai)
210    }
211}
212
213impl<'a> From<&'a EdwardsPoint> for NafLookupTable5<AffineNielsPoint> {
214    fn from(A: &'a EdwardsPoint) -> Self {
215        let mut Ai = [A.as_affine_niels(); 8];
216        let A2 = A.double();
217        for i in 0..7 {
218            Ai[i + 1] = (&A2 + &Ai[i]).as_extended().as_affine_niels();
219        }
220        // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A]
221        NafLookupTable5(Ai)
222    }
223}
224
225/// Holds stuff up to 8. The only time we use tables this big is for precomputed basepoint tables
226/// and multiscalar multiplication (which requires alloc).
227#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
228#[derive(Copy, Clone)]
229pub(crate) struct NafLookupTable8<T>(pub(crate) [T; 64]);
230
231#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
232impl<T: Copy> NafLookupTable8<T> {
233    pub fn select(&self, x: usize) -> T {
234        debug_assert_eq!(x & 1, 1);
235        debug_assert!(x < 128);
236
237        self.0[x / 2]
238    }
239}
240
241#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
242impl<T: Debug> Debug for NafLookupTable8<T> {
243    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
244        writeln!(f, "NafLookupTable8([")?;
245        for i in 0..64 {
246            writeln!(f, "\t{:?},", &self.0[i])?;
247        }
248        write!(f, "])")
249    }
250}
251
252#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
253impl<'a> From<&'a EdwardsPoint> for NafLookupTable8<ProjectiveNielsPoint> {
254    fn from(A: &'a EdwardsPoint) -> Self {
255        let mut Ai = [A.as_projective_niels(); 64];
256        let A2 = A.double();
257        for i in 0..63 {
258            Ai[i + 1] = (&A2 + &Ai[i]).as_extended().as_projective_niels();
259        }
260        // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A]
261        NafLookupTable8(Ai)
262    }
263}
264
265#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
266impl<'a> From<&'a EdwardsPoint> for NafLookupTable8<AffineNielsPoint> {
267    fn from(A: &'a EdwardsPoint) -> Self {
268        let mut Ai = [A.as_affine_niels(); 64];
269        let A2 = A.double();
270        for i in 0..63 {
271            Ai[i + 1] = (&A2 + &Ai[i]).as_extended().as_affine_niels();
272        }
273        // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A]
274        NafLookupTable8(Ai)
275    }
276}
curve25519_dalek/window.rs

curve25519_dalek/
window.rs
