curve25519_dalek/backend/vector/ifma/
edwards.rs

1// -*- mode: rust; -*-
2//
3// This file is part of curve25519-dalek.
4// Copyright (c) 2018-2019 Henry de Valence
5// See LICENSE for licensing information.
6//
7// Authors:
8// - Henry de Valence <hdevalence@hdevalence.ca>
9
10#![allow(non_snake_case)]
11
12use crate::traits::Identity;
13
14use core::ops::{Add, Neg, Sub};
15
16use subtle::Choice;
17use subtle::ConditionallySelectable;
18
19use curve25519_dalek_derive::unsafe_target_feature;
20
21use crate::edwards;
22use crate::window::{LookupTable, NafLookupTable5};
23
24#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
25use crate::window::NafLookupTable8;
26
27use super::constants;
28use super::field::{F51x4Reduced, F51x4Unreduced, Lanes, Shuffle};
29
30#[derive(Copy, Clone, Debug)]
31pub struct ExtendedPoint(pub(super) F51x4Unreduced);
32
33#[derive(Copy, Clone, Debug)]
34pub struct CachedPoint(pub(super) F51x4Reduced);
35
36#[unsafe_target_feature("avx512ifma,avx512vl")]
37impl From<edwards::EdwardsPoint> for ExtendedPoint {
38    fn from(P: edwards::EdwardsPoint) -> ExtendedPoint {
39        ExtendedPoint(F51x4Unreduced::new(&P.X, &P.Y, &P.Z, &P.T))
40    }
41}
42
43#[unsafe_target_feature("avx512ifma,avx512vl")]
44impl From<ExtendedPoint> for edwards::EdwardsPoint {
45    fn from(P: ExtendedPoint) -> edwards::EdwardsPoint {
46        let reduced = F51x4Reduced::from(P.0);
47        let tmp = F51x4Unreduced::from(reduced).split();
48        edwards::EdwardsPoint {
49            X: tmp[0],
50            Y: tmp[1],
51            Z: tmp[2],
52            T: tmp[3],
53        }
54    }
55}
56
57#[unsafe_target_feature("avx512ifma,avx512vl")]
58impl From<ExtendedPoint> for CachedPoint {
59    fn from(P: ExtendedPoint) -> CachedPoint {
60        let mut x = P.0;
61
62        x = x.blend(&x.diff_sum(), Lanes::AB);
63        x = &F51x4Reduced::from(x) * (121666, 121666, 2 * 121666, 2 * 121665);
64        x = x.blend(&x.negate_lazy(), Lanes::D);
65
66        CachedPoint(F51x4Reduced::from(x))
67    }
68}
69
70#[unsafe_target_feature("avx512ifma,avx512vl")]
71impl Default for ExtendedPoint {
72    fn default() -> ExtendedPoint {
73        ExtendedPoint::identity()
74    }
75}
76
77#[unsafe_target_feature("avx512ifma,avx512vl")]
78impl Identity for ExtendedPoint {
79    fn identity() -> ExtendedPoint {
80        constants::EXTENDEDPOINT_IDENTITY
81    }
82}
83
84#[unsafe_target_feature("avx512ifma,avx512vl")]
85impl ExtendedPoint {
86    pub fn double(&self) -> ExtendedPoint {
87        // (Y1 X1 T1 Z1) -- uses vpshufd (1c latency @ 1/c)
88        let mut tmp0 = self.0.shuffle(Shuffle::BADC);
89
90        // (X1+Y1 X1+Y1 X1+Y1 X1+Y1) -- can use vpinserti128
91        let mut tmp1 = (self.0 + tmp0).shuffle(Shuffle::ABAB);
92
93        // (X1 Y1 Z1 X1+Y1)
94        tmp0 = self.0.blend(&tmp1, Lanes::D);
95
96        tmp1 = F51x4Reduced::from(tmp0).square();
97        // Now tmp1 = (S1 S2 S3 S4)
98
99        // We want to compute
100        //
101        //    + | S1 | S1 | S1 | S1 |
102        //    + | S2 |    |    | S2 |
103        //    + |    |    | S3 |    |
104        //    + |    |    | S3 |    |
105        //    + |    |16p |16p |16p |
106        //    - |    | S2 | S2 |    |
107        //    - |    |    |    | S4 |
108        //    =======================
109        //        S5   S6   S8   S9
110
111        let zero = F51x4Unreduced::ZERO;
112
113        let S1_S1_S1_S1 = tmp1.shuffle(Shuffle::AAAA);
114        let S2_S2_S2_S2 = tmp1.shuffle(Shuffle::BBBB);
115
116        let S2_S2_S2_S4 = S2_S2_S2_S2.blend(&tmp1, Lanes::D).negate_lazy();
117
118        tmp0 = S1_S1_S1_S1 + zero.blend(&(tmp1 + tmp1), Lanes::C);
119        tmp0 = tmp0 + zero.blend(&S2_S2_S2_S2, Lanes::AD);
120        tmp0 = tmp0 + zero.blend(&S2_S2_S2_S4, Lanes::BCD);
121
122        let tmp2 = F51x4Reduced::from(tmp0);
123
124        ExtendedPoint(&tmp2.shuffle(Shuffle::DBBD) * &tmp2.shuffle(Shuffle::CACA))
125    }
126
127    pub fn mul_by_pow_2(&self, k: u32) -> ExtendedPoint {
128        let mut tmp: ExtendedPoint = *self;
129        for _ in 0..k {
130            tmp = tmp.double();
131        }
132        tmp
133    }
134}
135
136#[unsafe_target_feature("avx512ifma,avx512vl")]
137impl<'a, 'b> Add<&'b CachedPoint> for &'a ExtendedPoint {
138    type Output = ExtendedPoint;
139
140    /// Add an `ExtendedPoint` and a `CachedPoint`.
141    fn add(self, other: &'b CachedPoint) -> ExtendedPoint {
142        let mut tmp = self.0;
143
144        tmp = tmp.blend(&tmp.diff_sum(), Lanes::AB);
145        // tmp = (Y1-X1 Y1+X1 Z1 T1) = (S0 S1 Z1 T1)
146
147        tmp = &F51x4Reduced::from(tmp) * &other.0;
148        // tmp = (S0*S2' S1*S3' Z1*Z2' T1*T2') = (S8 S9 S10 S11)
149
150        tmp = tmp.shuffle(Shuffle::ABDC);
151        // tmp = (S8 S9 S11 S10)
152
153        let tmp = F51x4Reduced::from(tmp.diff_sum());
154        // tmp = (S9-S8 S9+S8 S10-S11 S10+S11) = (S12 S13 S14 S15)
155
156        let t0 = tmp.shuffle(Shuffle::ADDA);
157        // t0 = (S12 S15 S15 S12)
158        let t1 = tmp.shuffle(Shuffle::CBCB);
159        // t1 = (S14 S13 S14 S13)
160
161        // Return (S12*S14 S15*S13 S15*S14 S12*S13) = (X3 Y3 Z3 T3)
162        ExtendedPoint(&t0 * &t1)
163    }
164}
165
166#[unsafe_target_feature("avx512ifma,avx512vl")]
167impl Default for CachedPoint {
168    fn default() -> CachedPoint {
169        CachedPoint::identity()
170    }
171}
172
173#[unsafe_target_feature("avx512ifma,avx512vl")]
174impl Identity for CachedPoint {
175    fn identity() -> CachedPoint {
176        constants::CACHEDPOINT_IDENTITY
177    }
178}
179
180#[unsafe_target_feature("avx512ifma,avx512vl")]
181impl ConditionallySelectable for CachedPoint {
182    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
183        CachedPoint(F51x4Reduced::conditional_select(&a.0, &b.0, choice))
184    }
185
186    fn conditional_assign(&mut self, other: &Self, choice: Choice) {
187        self.0.conditional_assign(&other.0, choice);
188    }
189}
190
191#[unsafe_target_feature("avx512ifma,avx512vl")]
192impl<'a> Neg for &'a CachedPoint {
193    type Output = CachedPoint;
194
195    fn neg(self) -> CachedPoint {
196        let swapped = self.0.shuffle(Shuffle::BACD);
197        CachedPoint(swapped.blend(&(-self.0), Lanes::D))
198    }
199}
200
201#[unsafe_target_feature("avx512ifma,avx512vl")]
202impl<'a, 'b> Sub<&'b CachedPoint> for &'a ExtendedPoint {
203    type Output = ExtendedPoint;
204
205    /// Implement subtraction by negating the point and adding.
206    fn sub(self, other: &'b CachedPoint) -> ExtendedPoint {
207        self + &(-other)
208    }
209}
210
211#[unsafe_target_feature("avx512ifma,avx512vl")]
212impl<'a> From<&'a edwards::EdwardsPoint> for LookupTable<CachedPoint> {
213    fn from(point: &'a edwards::EdwardsPoint) -> Self {
214        let P = ExtendedPoint::from(*point);
215        let mut points = [CachedPoint::from(P); 8];
216        for i in 0..7 {
217            points[i + 1] = (&P + &points[i]).into();
218        }
219        LookupTable(points)
220    }
221}
222
223#[unsafe_target_feature("avx512ifma,avx512vl")]
224impl<'a> From<&'a edwards::EdwardsPoint> for NafLookupTable5<CachedPoint> {
225    fn from(point: &'a edwards::EdwardsPoint) -> Self {
226        let A = ExtendedPoint::from(*point);
227        let mut Ai = [CachedPoint::from(A); 8];
228        let A2 = A.double();
229        for i in 0..7 {
230            Ai[i + 1] = (&A2 + &Ai[i]).into();
231        }
232        // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A]
233        NafLookupTable5(Ai)
234    }
235}
236
237#[cfg(any(feature = "precomputed-tables", feature = "alloc"))]
238#[unsafe_target_feature("avx512ifma,avx512vl")]
239impl<'a> From<&'a edwards::EdwardsPoint> for NafLookupTable8<CachedPoint> {
240    fn from(point: &'a edwards::EdwardsPoint) -> Self {
241        let A = ExtendedPoint::from(*point);
242        let mut Ai = [CachedPoint::from(A); 64];
243        let A2 = A.double();
244        for i in 0..63 {
245            Ai[i + 1] = (&A2 + &Ai[i]).into();
246        }
247        // Now Ai = [A, 3A, 5A, 7A, 9A, 11A, 13A, 15A, ..., 127A]
248        NafLookupTable8(Ai)
249    }
250}
251
252#[cfg(target_feature = "avx512ifma,avx512vl")]
253#[cfg(test)]
254mod test {
255    use super::*;
256
257    fn addition_test_helper(P: edwards::EdwardsPoint, Q: edwards::EdwardsPoint) {
258        // Test the serial implementation of the parallel addition formulas
259        //let R_serial: edwards::EdwardsPoint = serial_add(P.into(), Q.into()).into();
260
261        // Test the vector implementation of the parallel readdition formulas
262        let cached_Q = CachedPoint::from(ExtendedPoint::from(Q));
263        let R_vector: edwards::EdwardsPoint = (&ExtendedPoint::from(P) + &cached_Q).into();
264        let S_vector: edwards::EdwardsPoint = (&ExtendedPoint::from(P) - &cached_Q).into();
265
266        println!("Testing point addition:");
267        println!("P = {:?}", P);
268        println!("Q = {:?}", Q);
269        println!("cached Q = {:?}", cached_Q);
270        println!("R = P + Q = {:?}", &P + &Q);
271        //println!("R_serial = {:?}", R_serial);
272        println!("R_vector = {:?}", R_vector);
273        println!("S = P - Q = {:?}", &P - &Q);
274        println!("S_vector = {:?}", S_vector);
275        //assert_eq!(R_serial.compress(), (&P + &Q).compress());
276        assert_eq!(R_vector.compress(), (&P + &Q).compress());
277        assert_eq!(S_vector.compress(), (&P - &Q).compress());
278        println!("OK!\n");
279    }
280
281    #[test]
282    fn vector_addition_vs_serial_addition_vs_edwards_extendedpoint() {
283        use crate::constants;
284        use crate::scalar::Scalar;
285
286        println!("Testing id +- id");
287        let P = edwards::EdwardsPoint::identity();
288        let Q = edwards::EdwardsPoint::identity();
289        addition_test_helper(P, Q);
290
291        println!("Testing id +- B");
292        let P = edwards::EdwardsPoint::identity();
293        let Q = constants::ED25519_BASEPOINT_POINT;
294        addition_test_helper(P, Q);
295
296        println!("Testing B +- B");
297        let P = constants::ED25519_BASEPOINT_POINT;
298        let Q = constants::ED25519_BASEPOINT_POINT;
299        addition_test_helper(P, Q);
300
301        println!("Testing B +- kB");
302        let P = constants::ED25519_BASEPOINT_POINT;
303        let Q = constants::ED25519_BASEPOINT_TABLE * &Scalar::from(8475983829u64);
304        addition_test_helper(P, Q);
305    }
306
307    fn doubling_test_helper(P: edwards::EdwardsPoint) {
308        //let R1: edwards::EdwardsPoint = serial_double(P.into()).into();
309        let R2: edwards::EdwardsPoint = ExtendedPoint::from(P).double().into();
310        println!("Testing point doubling:");
311        println!("P = {:?}", P);
312        //println!("(serial) R1 = {:?}", R1);
313        println!("(vector) R2 = {:?}", R2);
314        println!("P + P = {:?}", &P + &P);
315        //assert_eq!(R1.compress(), (&P + &P).compress());
316        assert_eq!(R2.compress(), (&P + &P).compress());
317        println!("OK!\n");
318    }
319
320    #[test]
321    fn vector_doubling_vs_serial_doubling_vs_edwards_extendedpoint() {
322        use crate::constants;
323        use crate::scalar::Scalar;
324
325        println!("Testing [2]id");
326        let P = edwards::EdwardsPoint::identity();
327        doubling_test_helper(P);
328
329        println!("Testing [2]B");
330        let P = constants::ED25519_BASEPOINT_POINT;
331        doubling_test_helper(P);
332
333        println!("Testing [2]([k]B)");
334        let P = constants::ED25519_BASEPOINT_TABLE * &Scalar::from(8475983829u64);
335        doubling_test_helper(P);
336    }
337}
curve25519_dalek/backend/vector/ifma/edwards.rs

curve25519_dalek/backend/vector/ifma/
edwards.rs
