ed448_goldilocks/curve/edwards/
extended.rs

1use std::borrow::Borrow;
2use std::iter::Sum;
3use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
4
5use crate::constants::{BASEPOINT_ORDER, EDWARDS_D};
6use crate::curve::edwards::affine::AffinePoint;
7use crate::curve::montgomery::montgomery::MontgomeryPoint; // XXX: need to fix this path
8use crate::curve::scalar_mul::variable_base;
9use crate::curve::twedwards::extended::ExtendedPoint as TwistedExtendedPoint;
10use crate::field::{FieldElement, Scalar};
11use subtle::{Choice, ConditionallyNegatable, ConditionallySelectable, ConstantTimeEq};
12#[allow(non_snake_case)]
13
14/// Represent points on the (untwisted) edwards curve using Extended Homogenous Projective Co-ordinates
15/// (x, y) -> (X/Z, Y/Z, Z, T)
16/// a = 1, d = -39081
17/// XXX: Make this more descriptive
18/// Should this be renamed to EdwardsPoint so that we are consistent with Dalek crypto? Necessary as ExtendedPoint is not regular lingo?
19#[derive(Copy, Clone, Debug)]
20pub struct ExtendedPoint {
21    pub(crate) X: FieldElement,
22    pub(crate) Y: FieldElement,
23    pub(crate) Z: FieldElement,
24    pub(crate) T: FieldElement,
25}
26
27impl ConditionallySelectable for ExtendedPoint {
28    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
29        ExtendedPoint {
30            X: FieldElement::conditional_select(&a.X, &b.X, choice),
31            Y: FieldElement::conditional_select(&a.Y, &b.Y, choice),
32            Z: FieldElement::conditional_select(&a.Z, &b.Z, choice),
33            T: FieldElement::conditional_select(&a.T, &b.T, choice),
34        }
35    }
36}
37
38pub struct CompressedEdwardsY(pub [u8; 57]);
39
40impl CompressedEdwardsY {
41    pub fn decompress(&self) -> Option<ExtendedPoint> {
42        // Safe to unwrap here as the underlying data structure is a slice
43        let (sign, b) = self.0.split_last().unwrap();
44
45        let mut y_bytes: [u8; 56] = [0; 56];
46        y_bytes.copy_from_slice(&b);
47
48        // Recover x using y
49        let y = FieldElement::from_bytes(&y_bytes);
50        let yy = y.square();
51        let dyy = EDWARDS_D * yy;
52        let numerator = FieldElement::one() - yy;
53        let denominator = FieldElement::one() - dyy;
54
55        let (mut x, is_res) = FieldElement::sqrt_ratio(&numerator, &denominator);
56        if is_res.unwrap_u8() != 1 {
57            return None;
58        }
59
60        // Compute correct sign of x
61        let compressed_sign_bit = Choice::from(sign >> 7);
62        let is_negative = x.is_negative();
63        x.conditional_negate(compressed_sign_bit ^ is_negative);
64
65        return Some(AffinePoint { x, y }.to_extended());
66    }
67}
68
69impl ConstantTimeEq for ExtendedPoint {
70    fn ct_eq(&self, other: &Self) -> Choice {
71        let XZ = self.X * other.Z;
72        let ZX = self.Z * other.X;
73
74        let YZ = self.Y * other.Z;
75        let ZY = self.Z * other.Y;
76
77        (XZ.ct_eq(&ZX)) & (YZ.ct_eq(&ZY))
78    }
79}
80
81impl PartialEq for ExtendedPoint {
82    fn eq(&self, other: &ExtendedPoint) -> bool {
83        self.ct_eq(other).into()
84    }
85}
86impl Eq for ExtendedPoint {}
87
88impl Default for ExtendedPoint {
89    fn default() -> ExtendedPoint {
90        ExtendedPoint::identity()
91    }
92}
93
94impl ExtendedPoint {
95    /// Identity point
96    pub fn identity() -> ExtendedPoint {
97        ExtendedPoint {
98            X: FieldElement::zero(),
99            Y: FieldElement::one(),
100            Z: FieldElement::one(),
101            T: FieldElement::zero(),
102        }
103    }
104    /// Generator for the prime subgroup
105    pub const fn generator() -> ExtendedPoint {
106        crate::constants::GOLDILOCKS_BASE_POINT
107    }
108
109    pub fn to_montgomery(&self) -> MontgomeryPoint {
110        // u = y^2 * [(1-dy^2)/(1-y^2)]
111
112        let affine = self.to_affine();
113
114        let yy = affine.y.square();
115        let dyy = EDWARDS_D * yy;
116
117        let u = yy * (FieldElement::one() - dyy) * (FieldElement::one() - yy).invert();
118
119        MontgomeryPoint(u.to_bytes())
120    }
121    /// Generic scalar multiplication to compute s*P
122    pub fn scalar_mul(&self, scalar: &Scalar) -> ExtendedPoint {
123        // Compute floor(s/4)
124        let mut scalar_div_four = scalar.clone();
125        scalar_div_four.div_by_four();
126
127        // Use isogeny and dual isogeny to compute phi^-1((s/4) * phi(P))
128        let partial_result = variable_base(&self.to_twisted(), &scalar_div_four).to_untwisted();
129        // Add partial result to (scalar mod 4) * P
130        partial_result.add(&self.scalar_mod_four(&scalar))
131    }
132
133    /// Returns (scalar mod 4) * P in constant time
134    pub fn scalar_mod_four(&self, scalar: &Scalar) -> ExtendedPoint {
135        // Compute compute (scalar mod 4)
136        let s_mod_four = scalar[0] & 3;
137
138        // Compute all possible values of (scalar mod 4) * P
139        let zero_p = ExtendedPoint::identity();
140        let one_p = self.clone();
141        let two_p = one_p.double();
142        let three_p = two_p.add(self);
143
144        // Under the reasonable assumption that `==` is constant time
145        // Then the whole function is constant time.
146        // This should be cheaper than calling double_and_add or a scalar mul operation
147        // as the number of possibilities are so small.
148        // XXX: This claim has not been tested (although it sounds intuitive to me)
149        let mut result = ExtendedPoint::identity();
150        result.conditional_assign(&zero_p, Choice::from((s_mod_four == 0) as u8));
151        result.conditional_assign(&one_p, Choice::from((s_mod_four == 1) as u8));
152        result.conditional_assign(&two_p, Choice::from((s_mod_four == 2) as u8));
153        result.conditional_assign(&three_p, Choice::from((s_mod_four == 3) as u8));
154
155        result
156    }
157
158    // Standard compression; store Y and sign of X
159    // XXX: This needs more docs and is `compress` the conventional function name? I think to_bytes/encode is?
160    pub fn compress(&self) -> CompressedEdwardsY {
161        let affine = self.to_affine();
162
163        let affine_x = affine.x;
164        let affine_y = affine.y;
165
166        let mut compressed_bytes = [0u8; 57];
167
168        let sign = affine_x.is_negative().unwrap_u8();
169
170        let y_bytes = affine_y.to_bytes();
171        for i in 0..y_bytes.len() {
172            compressed_bytes[i] = y_bytes[i]
173        }
174        *compressed_bytes.last_mut().unwrap() = (sign as u8) << 7;
175        CompressedEdwardsY(compressed_bytes)
176    }
177
178    //https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf (3.1)
179    // These formulas are unified, so for now we can use it for doubling. Will refactor later for speed
180    pub fn add(&self, other: &ExtendedPoint) -> ExtendedPoint {
181        let aXX = self.X * other.X; // aX1X2
182        let dTT = EDWARDS_D * self.T * other.T; // dT1T2
183        let ZZ = self.Z * other.Z; // Z1Z2
184        let YY = self.Y * other.Y;
185
186        let X = {
187            let x_1 = (self.X * other.Y) + (self.Y * other.X);
188            let x_2 = ZZ - dTT;
189            x_1 * x_2
190        };
191        let Y = {
192            let y_1 = YY - aXX;
193            let y_2 = ZZ + dTT;
194            y_1 * y_2
195        };
196
197        let T = {
198            let t_1 = YY - aXX;
199            let t_2 = (self.X * other.Y) + (self.Y * other.X);
200            t_1 * t_2
201        };
202
203        let Z = { (ZZ - dTT) * (ZZ + dTT) };
204
205        ExtendedPoint { X, Y, Z, T }
206    }
207
208    // XXX: See comment on addition, the formula is unified, so this will do for now
209    //https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf (3.1)
210    pub fn double(&self) -> ExtendedPoint {
211        self.add(&self)
212    }
213
214    pub(crate) fn is_on_curve(&self) -> bool {
215        let XY = self.X * self.Y;
216        let ZT = self.Z * self.T;
217
218        // Y^2 + X^2 == Z^2 - T^2 * D
219
220        let YY = self.Y.square();
221        let XX = self.X.square();
222        let ZZ = self.Z.square();
223        let TT = self.T.square();
224        let lhs = YY + XX;
225        let rhs = ZZ + TT * EDWARDS_D;
226
227        (XY == ZT) && (lhs == rhs)
228    }
229
230    pub fn to_affine(&self) -> AffinePoint {
231        let INV_Z = self.Z.invert();
232
233        let mut x = self.X * INV_Z;
234        x.strong_reduce();
235
236        let mut y = self.Y * INV_Z;
237        y.strong_reduce();
238
239        AffinePoint { x, y }
240    }
241    /// Edwards_Isogeny is derived from the doubling formula
242    /// XXX: There is a duplicate method in the twisted edwards module to compute the dual isogeny
243    /// XXX: Not much point trying to make it generic I think. So what we can do is optimise each respective isogeny method for a=1 or a = -1 (currently, I just made it really slow and simple)
244    fn edwards_isogeny(&self, a: FieldElement) -> TwistedExtendedPoint {
245        // Convert to affine now, then derive extended version later
246        let affine = self.to_affine();
247        let x = affine.x;
248        let y = affine.y;
249
250        // Compute x
251        let xy = x * y;
252        let x_numerator = xy + xy;
253        let x_denom = y.square() - (a * x.square());
254        let new_x = x_numerator * x_denom.invert();
255
256        // Compute y
257        let y_numerator = y.square() + (a * x.square());
258        let y_denom = (FieldElement::one() + FieldElement::one()) - y.square() - (a * x.square());
259        let new_y = y_numerator * y_denom.invert();
260
261        TwistedExtendedPoint {
262            X: new_x,
263            Y: new_y,
264            Z: FieldElement::one(),
265            T: new_x * new_y,
266        }
267    }
268    pub fn to_twisted(&self) -> TwistedExtendedPoint {
269        self.edwards_isogeny(FieldElement::one())
270    }
271
272    pub fn negate(&self) -> ExtendedPoint {
273        ExtendedPoint {
274            X: self.X.negate(),
275            Y: self.Y,
276            Z: self.Z,
277            T: self.T.negate(),
278        }
279    }
280
281    pub fn torque(&self) -> ExtendedPoint {
282        ExtendedPoint {
283            X: self.X.negate(),
284            Y: self.Y.negate(),
285            Z: self.Z,
286            T: self.T,
287        }
288    }
289
290    /// Determine if this point is “torsion-free”, i.e., is contained in
291    /// the prime-order subgroup.
292    ///
293    /// # Return
294    ///
295    /// * `true` if `self` has zero torsion component and is in the
296    /// prime-order subgroup;
297    /// * `false` if `self` has a nonzero torsion component and is not
298    /// in the prime-order subgroup.
299    pub fn is_torsion_free(&self) -> bool {
300        (self * BASEPOINT_ORDER) == Self::identity()
301    }
302}
303
304// ------------------------------------------------------------------------
305// Addition and Subtraction
306// ------------------------------------------------------------------------
307
308impl<'a, 'b> Add<&'b ExtendedPoint> for &'a ExtendedPoint {
309    type Output = ExtendedPoint;
310    fn add(self, other: &'b ExtendedPoint) -> ExtendedPoint {
311        self.add(other)
312    }
313}
314
315define_add_variants!(
316    LHS = ExtendedPoint,
317    RHS = ExtendedPoint,
318    Output = ExtendedPoint
319);
320
321impl<'b> AddAssign<&'b ExtendedPoint> for ExtendedPoint {
322    fn add_assign(&mut self, _rhs: &'b ExtendedPoint) {
323        *self = (self as &ExtendedPoint) + _rhs;
324    }
325}
326
327define_add_assign_variants!(LHS = ExtendedPoint, RHS = ExtendedPoint);
328
329impl<'a, 'b> Sub<&'b ExtendedPoint> for &'a ExtendedPoint {
330    type Output = ExtendedPoint;
331    fn sub(self, other: &'b ExtendedPoint) -> ExtendedPoint {
332        self.add(&other.negate())
333    }
334}
335
336define_sub_variants!(
337    LHS = ExtendedPoint,
338    RHS = ExtendedPoint,
339    Output = ExtendedPoint
340);
341
342impl<'b> SubAssign<&'b ExtendedPoint> for ExtendedPoint {
343    fn sub_assign(&mut self, _rhs: &'b ExtendedPoint) {
344        *self = (self as &ExtendedPoint) - _rhs;
345    }
346}
347
348define_sub_assign_variants!(LHS = ExtendedPoint, RHS = ExtendedPoint);
349
350impl<T> Sum<T> for ExtendedPoint
351where
352    T: Borrow<ExtendedPoint>,
353{
354    fn sum<I>(iter: I) -> Self
355    where
356        I: Iterator<Item = T>,
357    {
358        iter.fold(ExtendedPoint::identity(), |acc, item| acc + item.borrow())
359    }
360}
361
362// ------------------------------------------------------------------------
363// Negation
364// ------------------------------------------------------------------------
365
366impl<'a> Neg for &'a ExtendedPoint {
367    type Output = ExtendedPoint;
368
369    fn neg(self) -> ExtendedPoint {
370        self.negate()
371    }
372}
373
374impl Neg for ExtendedPoint {
375    type Output = ExtendedPoint;
376
377    fn neg(self) -> ExtendedPoint {
378        -&self
379    }
380}
381
382// ------------------------------------------------------------------------
383// Scalar multiplication
384// ------------------------------------------------------------------------
385
386impl<'b> MulAssign<&'b Scalar> for ExtendedPoint {
387    fn mul_assign(&mut self, scalar: &'b Scalar) {
388        let result = (self as &ExtendedPoint) * scalar;
389        *self = result;
390    }
391}
392
393define_mul_assign_variants!(LHS = ExtendedPoint, RHS = Scalar);
394
395define_mul_variants!(LHS = ExtendedPoint, RHS = Scalar, Output = ExtendedPoint);
396define_mul_variants!(LHS = Scalar, RHS = ExtendedPoint, Output = ExtendedPoint);
397
398impl<'a, 'b> Mul<&'b Scalar> for &'a ExtendedPoint {
399    type Output = ExtendedPoint;
400    /// Scalar multiplication: compute `scalar * self`.
401    fn mul(self, scalar: &'b Scalar) -> ExtendedPoint {
402        self.scalar_mul(scalar)
403    }
404}
405
406impl<'a, 'b> Mul<&'b ExtendedPoint> for &'a Scalar {
407    type Output = ExtendedPoint;
408
409    /// Scalar multiplication: compute `scalar * self`.
410    fn mul(self, point: &'b ExtendedPoint) -> ExtendedPoint {
411        point * self
412    }
413}
414
415#[cfg(test)]
416mod tests {
417    use super::*;
418    use hex::decode as hex_decode;
419    use std::convert::TryInto;
420    fn slice_to_fixed_array(b: &[u8]) -> [u8; 56] {
421        let mut a: [u8; 56] = [0; 56];
422        a.copy_from_slice(&b);
423        a
424    }
425
426    fn hex_to_field(data: &str) -> FieldElement {
427        let mut bytes = hex_decode(data).unwrap();
428        bytes.reverse();
429        FieldElement::from_bytes(&slice_to_fixed_array(&bytes))
430    }
431
432    fn field_to_hex(f: &FieldElement) -> String {
433        let mut buf = f.to_bytes();
434        buf.reverse();
435        hex::encode(buf)
436    }
437
438    #[test]
439    fn test_isogeny() {
440        let x = hex_to_field("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555");
441        let y = hex_to_field("ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed");
442        let a = AffinePoint { x, y }.to_extended();
443        let twist_a = a.to_twisted().to_untwisted();
444        assert!(twist_a == a.double().double())
445    }
446
447    // XXX: Move this to constants folder to test all global constants
448    #[test]
449    fn derive_base_points() {
450        use crate::constants::{GOLDILOCKS_BASE_POINT, TWISTED_EDWARDS_BASE_POINT};
451
452        // This was the original basepoint which had order 2q;
453        let old_x = hex_to_field("4F1970C66BED0DED221D15A622BF36DA9E146570470F1767EA6DE324A3D3A46412AE1AF72AB66511433B80E18B00938E2626A82BC70CC05E");
454        let old_y = hex_to_field("693F46716EB6BC248876203756C9C7624BEA73736CA3984087789C1E05A0C2D73AD3FF1CE67C39C4FDBD132C4ED7C8AD9808795BF230FA14");
455        let old_bp = AffinePoint { x: old_x, y: old_y }.to_extended();
456
457        // This is the new basepoint, that is in the ed448 paper
458        let new_x = hex_to_field("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555");
459        let new_y = hex_to_field("ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed");
460        let new_bp = AffinePoint { x: new_x, y: new_y }.to_extended();
461
462        // Doubling the old basepoint, should give us the new basepoint
463        assert_eq!(old_bp.double(), new_bp);
464
465        // XXX: Unfortunately, the test vectors in libdecaf currently use the old basepoint.
466        // We need to update this. But for now, I use the old basepoint so that I can check against libdecaf
467
468        assert_eq!(GOLDILOCKS_BASE_POINT, old_bp);
469
470        // The Twisted basepoint can be derived by using the isogeny
471        assert_eq!(old_bp.to_twisted(), TWISTED_EDWARDS_BASE_POINT)
472    }
473
474    #[test]
475    fn test_is_on_curve() {
476        let x  = hex_to_field("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555");
477        let y  = hex_to_field("ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed");
478        let gen = AffinePoint { x, y }.to_extended();
479        assert!(gen.is_on_curve());
480    }
481    #[test]
482    fn test_compress_decompress() {
483        let x  = hex_to_field("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555");
484        let y  = hex_to_field("ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed");
485        let gen = AffinePoint { x, y }.to_extended();
486
487        let decompressed_point = gen.compress().decompress();
488        assert!(decompressed_point.is_some());
489
490        assert!(gen == decompressed_point.unwrap());
491    }
492    #[test]
493    fn test_decompress_compress() {
494        let bytes: [u8; 57] = hex::decode("649c6a53b109897d962d033f23d01fd4e1053dddf3746d2ddce9bd66aea38ccfc3df061df03ca399eb806312ab3037c0c31523142956ada780").unwrap().try_into().unwrap();
495        let compressed = CompressedEdwardsY(bytes);
496        let decompressed = compressed.decompress().unwrap();
497
498        let recompressed = decompressed.compress();
499
500        assert_eq!(bytes, recompressed.0);
501    }
502    #[test]
503    fn test_just_decompress() {
504        let bytes: [u8; 57] = hex::decode("649c6a53b109897d962d033f23d01fd4e1053dddf3746d2ddce9bd66aea38ccfc3df061df03ca399eb806312ab3037c0c31523142956ada780").unwrap().try_into().unwrap();
505        let compressed = CompressedEdwardsY(bytes);
506        let decompressed = compressed.decompress().unwrap();
507
508        assert_eq!(field_to_hex(&decompressed.X), "39c41cea305d737df00de8223a0d5f4d48c8e098e16e9b4b2f38ac353262e119cb5ff2afd6d02464702d9d01c9921243fc572f9c718e2527");
509        assert_eq!(field_to_hex(&decompressed.Y), "a7ad5629142315c3c03730ab126380eb99a33cf01d06dfc3cf8ca3ae66bde9dc2d6d74f3dd3d05e1d41fd0233f032d967d8909b1536a9c64");
510
511        let bytes: [u8; 57] = hex::decode("010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000").unwrap().try_into().unwrap();
512        let compressed = CompressedEdwardsY(bytes);
513        let decompressed = compressed.decompress().unwrap();
514
515        assert_eq!(field_to_hex(&decompressed.X), "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
516        assert_eq!(field_to_hex(&decompressed.Y), "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001");
517    }
518    #[test]
519    fn test_is_torsion_free() {
520        assert!(ExtendedPoint::generator().is_torsion_free());
521        assert!(ExtendedPoint::identity().is_torsion_free());
522
523        let bytes: [u8; 57] = hex::decode("13b6714c7a5f53101bbec88f2f17cd30f42e37fae363a5474efb4197ed6005df5861ae178a0c2c16ad378b7befed0d0904b7ced35e9f674180").unwrap().try_into().unwrap();
524        let compressed = CompressedEdwardsY(bytes);
525        let decompressed = compressed.decompress().unwrap();
526        assert!(!decompressed.is_torsion_free());
527    }
528}
ed448_goldilocks/curve/edwards/extended.rs

ed448_goldilocks/curve/edwards/
extended.rs
