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 16 use core::fmt::Debug; 17 18 use subtle::ConditionallyNegatable; 19 use subtle::ConditionallySelectable; 20 use subtle::ConstantTimeEq; 21 use subtle::Choice; 22 23 use traits::Identity; 24 25 use edwards::EdwardsPoint; 26 use backend::serial::curve_models::ProjectiveNielsPoint; 27 use backend::serial::curve_models::AffineNielsPoint; 28 29 use zeroize::Zeroize; 30 31 macro_rules! impl_lookup_table { 32 (Name = $name:ident, Size = $size:expr, SizeNeg = $neg:expr, SizeRange = $range:expr, ConversionRange = $conv_range:expr) => { 33 34 /// A lookup table of precomputed multiples of a point \\(P\\), used to 35 /// compute \\( xP \\) for \\( -8 \leq x \leq 8 \\). 36 /// 37 /// The computation of \\( xP \\) is done in constant time by the `select` function. 38 /// 39 /// Since `LookupTable` does not implement `Index`, it's more difficult 40 /// to accidentally use the table directly. Unfortunately the table is 41 /// only `pub(crate)` so that we can write hardcoded constants, so it's 42 /// still technically possible. It would be nice to prevent direct 43 /// access to the table. 44 #[derive(Copy, Clone)] 45 pub struct $name<T>(pub(crate) [T; $size]); 46 47 impl<T> $name<T> 48 where 49 T: Identity + ConditionallySelectable + ConditionallyNegatable, 50 { 51 /// Given \\(-8 \leq x \leq 8\\), return \\(xP\\) in constant time. 52 pub fn select(&self, x: i8) -> T { 53 debug_assert!(x >= $neg); 54 debug_assert!(x as i16 <= $size as i16); // XXX We have to convert to i16s here for the radix-256 case.. this is wrong. 55 56 // Compute xabs = |x| 57 let xmask = x as i16 >> 7; 58 let xabs = (x as i16 + xmask) ^ xmask; 59 60 // Set t = 0 * P = identity 61 let mut t = T::identity(); 62 for j in $range { 63 // Copy `points[j-1] == j*P` onto `t` in constant time if `|x| == j`. 64 let c = (xabs as u16).ct_eq(&(j as u16)); 65 t.conditional_assign(&self.0[j - 1], c); 66 } 67 // Now t == |x| * P. 68 69 let neg_mask = Choice::from((xmask & 1) as u8); 70 t.conditional_negate(neg_mask); 71 // Now t == x * P. 72 73 t 74 } 75 } 76 77 impl<T: Copy + Default> Default for $name<T> { 78 fn default() -> $name<T> { 79 $name([T::default(); $size]) 80 } 81 } 82 83 impl<T: Debug> Debug for $name<T> { 84 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 85 write!(f, "{:?}(", stringify!($name))?; 86 87 for x in self.0.iter() { 88 write!(f, "{:?}", x)?; 89 } 90 91 write!(f, ")") 92 } 93 } 94 95 impl<'a> From<&'a EdwardsPoint> for $name<ProjectiveNielsPoint> { 96 fn from(P: &'a EdwardsPoint) -> Self { 97 let mut points = [P.to_projective_niels(); $size]; 98 for j in $conv_range { 99 points[j + 1] = (P + &points[j]).to_extended().to_projective_niels(); 100 } 101 $name(points) 102 } 103 } 104 105 impl<'a> From<&'a EdwardsPoint> for $name<AffineNielsPoint> { 106 fn from(P: &'a EdwardsPoint) -> Self { 107 let mut points = [P.to_affine_niels(); $size]; 108 // XXX batch inversion would be good if perf mattered here 109 for j in $conv_range { 110 points[j + 1] = (P + &points[j]).to_extended().to_affine_niels() 111 } 112 $name(points) 113 } 114 } 115 116 impl<T> Zeroize for $name<T> 117 where 118 T: Copy + Default + Zeroize 119 { 120 fn zeroize(&mut self) { 121 for x in self.0.iter_mut() { 122 x.zeroize(); 123 } 124 } 125 } 126 127 }} // End macro_rules! impl_lookup_table 128 129 // The first one has to be named "LookupTable" because it's used as a constructor for consts. 130 impl_lookup_table! {Name = LookupTable, Size = 8, SizeNeg = -8, SizeRange = 1 .. 9, ConversionRange = 0 .. 7} // radix-16 131 impl_lookup_table! {Name = LookupTableRadix32, Size = 16, SizeNeg = -16, SizeRange = 1 .. 17, ConversionRange = 0 .. 15} // radix-32 132 impl_lookup_table! {Name = LookupTableRadix64, Size = 32, SizeNeg = -32, SizeRange = 1 .. 33, ConversionRange = 0 .. 31} // radix-64 133 impl_lookup_table! {Name = LookupTableRadix128, Size = 64, SizeNeg = -64, SizeRange = 1 .. 65, ConversionRange = 0 .. 63} // radix-128 134 impl_lookup_table! {Name = LookupTableRadix256, Size = 128, SizeNeg = -128, SizeRange = 1 .. 129, ConversionRange = 0 .. 127} // radix-256 135 136 // For homogeneity we then alias it to "LookupTableRadix16". 137 pub type LookupTableRadix16<T> = LookupTable<T>; 138 139 /// Holds odd multiples 1A, 3A, ..., 15A of a point A. 140 #[derive(Copy, Clone)] 141 pub(crate) struct NafLookupTable5<T>(pub(crate) [T; 8]); 142 143 impl<T: Copy> NafLookupTable5<T> { 144 /// Given public, odd \\( x \\) with \\( 0 < x < 2^4 \\), return \\(xA\\). select(&self, x: usize) -> T145 pub fn select(&self, x: usize) -> T { 146 debug_assert_eq!(x & 1, 1); 147 debug_assert!(x < 16); 148 149 self.0[x / 2] 150 } 151 } 152 153 impl<T: Debug> Debug for NafLookupTable5<T> { fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result154 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 155 write!(f, "NafLookupTable5({:?})", self.0) 156 } 157 } 158 159 impl<'a> From<&'a EdwardsPoint> for NafLookupTable5<ProjectiveNielsPoint> { from(A: &'a EdwardsPoint) -> Self160 fn from(A: &'a EdwardsPoint) -> Self { 161 let mut Ai = [A.to_projective_niels(); 8]; 162 let A2 = A.double(); 163 for i in 0..7 { 164 Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_projective_niels(); 165 } 166 // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A] 167 NafLookupTable5(Ai) 168 } 169 } 170 171 impl<'a> From<&'a EdwardsPoint> for NafLookupTable5<AffineNielsPoint> { from(A: &'a EdwardsPoint) -> Self172 fn from(A: &'a EdwardsPoint) -> Self { 173 let mut Ai = [A.to_affine_niels(); 8]; 174 let A2 = A.double(); 175 for i in 0..7 { 176 Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_affine_niels(); 177 } 178 // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A] 179 NafLookupTable5(Ai) 180 } 181 } 182 183 /// Holds stuff up to 8. 184 #[derive(Copy, Clone)] 185 pub(crate) struct NafLookupTable8<T>(pub(crate) [T; 64]); 186 187 impl<T: Copy> NafLookupTable8<T> { select(&self, x: usize) -> T188 pub fn select(&self, x: usize) -> T { 189 debug_assert_eq!(x & 1, 1); 190 debug_assert!(x < 128); 191 192 self.0[x / 2] 193 } 194 } 195 196 impl<T: Debug> Debug for NafLookupTable8<T> { fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result197 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 198 write!(f, "NafLookupTable8([\n")?; 199 for i in 0..64 { 200 write!(f, "\t{:?},\n", &self.0[i])?; 201 } 202 write!(f, "])") 203 } 204 } 205 206 impl<'a> From<&'a EdwardsPoint> for NafLookupTable8<ProjectiveNielsPoint> { from(A: &'a EdwardsPoint) -> Self207 fn from(A: &'a EdwardsPoint) -> Self { 208 let mut Ai = [A.to_projective_niels(); 64]; 209 let A2 = A.double(); 210 for i in 0..63 { 211 Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_projective_niels(); 212 } 213 // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A] 214 NafLookupTable8(Ai) 215 } 216 } 217 218 impl<'a> From<&'a EdwardsPoint> for NafLookupTable8<AffineNielsPoint> { from(A: &'a EdwardsPoint) -> Self219 fn from(A: &'a EdwardsPoint) -> Self { 220 let mut Ai = [A.to_affine_niels(); 64]; 221 let A2 = A.double(); 222 for i in 0..63 { 223 Ai[i + 1] = (&A2 + &Ai[i]).to_extended().to_affine_niels(); 224 } 225 // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A] 226 NafLookupTable8(Ai) 227 } 228 } 229