1 // -*- mode: rust; -*-
2 //
3 // This file is part of curve25519-dalek.
4 // Copyright (c) 2016-2019 Isis Lovecruft, Henry de Valence
5 // See LICENSE for licensing information.
6 //
7 // Authors:
8 // - Isis Agora Lovecruft <isis@patternsinthevoid.net>
9 // - Henry de Valence <hdevalence@hdevalence.ca>
10 
11 //! Code for fixed- and sliding-window functionality
12 
13 #![allow(non_snake_case)]
14 
15 use core::fmt::Debug;
16 
17 use subtle::ConditionallyNegatable;
18 use subtle::ConditionallySelectable;
19 use subtle::ConstantTimeEq;
20 use subtle::Choice;
21 
22 use traits::Identity;
23 
24 use edwards::EdwardsPoint;
25 use backend::serial::curve_models::ProjectiveNielsPoint;
26 use backend::serial::curve_models::AffineNielsPoint;
27 
28 use zeroize::Zeroize;
29 
30 /// A lookup table of precomputed multiples of a point \\(P\\), used to
31 /// compute \\( xP \\) for \\( -8 \leq x \leq 8 \\).
32 ///
33 /// The computation of \\( xP \\) is done in constant time by the `select` function.
34 ///
35 /// Since `LookupTable` does not implement `Index`, it's more difficult
36 /// to accidentally use the table directly.  Unfortunately the table is
37 /// only `pub(crate)` so that we can write hardcoded constants, so it's
38 /// still technically possible.  It would be nice to prevent direct
39 /// access to the table.
40 ///
41 /// XXX make this generic with respect to table size
42 #[derive(Copy, Clone)]
43 pub struct LookupTable<T>(pub(crate) [T; 8]);
44 
45 impl<T> LookupTable<T>
46 where
47     T: Identity + ConditionallySelectable + ConditionallyNegatable,
48 {
49     /// Given \\(-8 \leq x \leq 8\\), return \\(xP\\) in constant time.
select(&self, x: i8) -> T50     pub fn select(&self, x: i8) -> T {
51         debug_assert!(x >= -8);
52         debug_assert!(x <= 8);
53 
54         // Compute xabs = |x|
55         let xmask = x >> 7;
56         let xabs = (x + xmask) ^ xmask;
57 
58         // Set t = 0 * P = identity
59         let mut t = T::identity();
60         for j in 1..9 {
61             // Copy `points[j-1] == j*P` onto `t` in constant time if `|x| == j`.
62             let c = (xabs as u8).ct_eq(&(j as u8));
63             t.conditional_assign(&self.0[j - 1], c);
64         }
65         // Now t == |x| * P.
66 
67         let neg_mask = Choice::from((xmask & 1) as u8);
68         t.conditional_negate(neg_mask);
69         // Now t == x * P.
70 
71         t
72     }
73 }
74 
75 impl<T: Copy + Default> Default for LookupTable<T> {
default() -> LookupTable<T>76     fn default() -> LookupTable<T> {
77         LookupTable([T::default(); 8])
78     }
79 }
80 
81 impl<T: Debug> Debug for LookupTable<T> {
fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result82     fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
83         write!(f, "LookupTable({:?})", self.0)
84     }
85 }
86 
87 impl<'a> From<&'a EdwardsPoint> for LookupTable<ProjectiveNielsPoint> {
from(P: &'a EdwardsPoint) -> Self88     fn from(P: &'a EdwardsPoint) -> Self {
89         let mut points = [P.to_projective_niels(); 8];
90         for j in 0..7 {
91             points[j + 1] = (P + &points[j]).to_extended().to_projective_niels();
92         }
93         LookupTable(points)
94     }
95 }
96 
97 impl<'a> From<&'a EdwardsPoint> for LookupTable<AffineNielsPoint> {
from(P: &'a EdwardsPoint) -> Self98     fn from(P: &'a EdwardsPoint) -> Self {
99         let mut points = [P.to_affine_niels(); 8];
100         // XXX batch inversion would be good if perf mattered here
101         for j in 0..7 {
102             points[j + 1] = (P + &points[j]).to_extended().to_affine_niels()
103         }
104         LookupTable(points)
105     }
106 }
107 
108 impl<T> Zeroize for LookupTable<T>
109 where
110     T: Copy + Default + Zeroize
111 {
zeroize(&mut self)112     fn zeroize(&mut self) {
113         self.0.zeroize();
114     }
115 }
116 
117 /// Holds odd multiples 1A, 3A, ..., 15A of a point A.
118 #[derive(Copy, Clone)]
119 pub(crate) struct NafLookupTable5<T>(pub(crate) [T; 8]);
120 
121 impl<T: Copy> NafLookupTable5<T> {
122     /// Given public, odd \\( x \\) with \\( 0 < x < 2^4 \\), return \\(xA\\).
select(&self, x: usize) -> T123     pub fn select(&self, x: usize) -> T {
124         debug_assert_eq!(x & 1, 1);
125         debug_assert!(x < 16);
126 
127         self.0[x / 2]
128     }
129 }
130 
131 impl<T: Debug> Debug for NafLookupTable5<T> {
fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result132     fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
133         write!(f, "NafLookupTable5({:?})", self.0)
134     }
135 }
136 
137 impl<'a> From<&'a EdwardsPoint> for NafLookupTable5<ProjectiveNielsPoint> {
from(A: &'a EdwardsPoint) -> Self138     fn from(A: &'a EdwardsPoint) -> Self {
139         let mut Ai = [A.to_projective_niels(); 8];
140         let A2 = A.double();
141         for i in 0..7 {
142             Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_projective_niels();
143         }
144         // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A]
145         NafLookupTable5(Ai)
146     }
147 }
148 
149 impl<'a> From<&'a EdwardsPoint> for NafLookupTable5<AffineNielsPoint> {
from(A: &'a EdwardsPoint) -> Self150     fn from(A: &'a EdwardsPoint) -> Self {
151         let mut Ai = [A.to_affine_niels(); 8];
152         let A2 = A.double();
153         for i in 0..7 {
154             Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_affine_niels();
155         }
156         // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A]
157         NafLookupTable5(Ai)
158     }
159 }
160 
161 /// Holds stuff up to 8.
162 #[derive(Copy, Clone)]
163 pub(crate) struct NafLookupTable8<T>(pub(crate) [T; 64]);
164 
165 impl<T: Copy> NafLookupTable8<T> {
select(&self, x: usize) -> T166     pub fn select(&self, x: usize) -> T {
167         debug_assert_eq!(x & 1, 1);
168         debug_assert!(x < 128);
169 
170         self.0[x / 2]
171     }
172 }
173 
174 impl<T: Debug> Debug for NafLookupTable8<T> {
fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result175     fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
176         write!(f, "NafLookupTable8([\n")?;
177         for i in 0..64 {
178             write!(f, "\t{:?},\n", &self.0[i])?;
179         }
180         write!(f, "])")
181     }
182 }
183 
184 impl<'a> From<&'a EdwardsPoint> for NafLookupTable8<ProjectiveNielsPoint> {
from(A: &'a EdwardsPoint) -> Self185     fn from(A: &'a EdwardsPoint) -> Self {
186         let mut Ai = [A.to_projective_niels(); 64];
187         let A2 = A.double();
188         for i in 0..63 {
189             Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_projective_niels();
190         }
191         // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A]
192         NafLookupTable8(Ai)
193     }
194 }
195 
196 impl<'a> From<&'a EdwardsPoint> for NafLookupTable8<AffineNielsPoint> {
from(A: &'a EdwardsPoint) -> Self197     fn from(A: &'a EdwardsPoint) -> Self {
198         let mut Ai = [A.to_affine_niels(); 64];
199         let A2 = A.double();
200         for i in 0..63 {
201             Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_affine_niels();
202         }
203         // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A]
204         NafLookupTable8(Ai)
205     }
206 }
207