ed448_goldilocks/curve/twedwards/
extended.rs

1#![allow(non_snake_case)]
2#![allow(dead_code)]
3
4use super::IsogenyMap;
5use super::extensible::ExtensiblePoint;
6use super::projective::ProjectiveNielsPoint;
7use super::{IsogenyMapResult, affine::AffineNielsPoint};
8use crate::edwards::EdwardsPoint as EdwardsExtendedPoint;
9use crate::field::FieldElement;
10use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
11
12#[derive(Copy, Clone, Debug)]
13pub struct ExtendedPoint {
14    pub(crate) X: FieldElement,
15    pub(crate) Y: FieldElement,
16    pub(crate) Z: FieldElement,
17    pub(crate) T: FieldElement,
18}
19
20impl ConstantTimeEq for ExtendedPoint {
21    fn ct_eq(&self, other: &Self) -> Choice {
22        let XZ = self.X * other.Z;
23        let ZX = self.Z * other.X;
24
25        let YZ = self.Y * other.Z;
26        let ZY = self.Z * other.Y;
27
28        (XZ.ct_eq(&ZX)) & (YZ.ct_eq(&ZY))
29    }
30}
31
32impl ConditionallySelectable for ExtendedPoint {
33    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
34        ExtendedPoint {
35            X: FieldElement::conditional_select(&a.X, &b.X, choice),
36            Y: FieldElement::conditional_select(&a.Y, &b.Y, choice),
37            Z: FieldElement::conditional_select(&a.Z, &b.Z, choice),
38            T: FieldElement::conditional_select(&a.T, &b.T, choice),
39        }
40    }
41}
42
43impl PartialEq for ExtendedPoint {
44    fn eq(&self, other: &ExtendedPoint) -> bool {
45        self.ct_eq(other).into()
46    }
47}
48impl PartialEq<ExtensiblePoint> for ExtendedPoint {
49    fn eq(&self, other: &ExtensiblePoint) -> bool {
50        self.to_extensible().ct_eq(other).into()
51    }
52}
53impl Eq for ExtendedPoint {}
54
55impl Default for ExtendedPoint {
56    fn default() -> ExtendedPoint {
57        ExtendedPoint::IDENTITY
58    }
59}
60
61impl elliptic_curve::zeroize::DefaultIsZeroes for ExtendedPoint {}
62
63impl ExtendedPoint {
64    /// Generator for the prime subgroup
65    pub const GENERATOR: ExtendedPoint = ExtendedPoint {
66        X: crate::TWISTED_EDWARDS_BASE_POINT.X,
67        Y: crate::TWISTED_EDWARDS_BASE_POINT.Y,
68        Z: crate::TWISTED_EDWARDS_BASE_POINT.Z,
69        T: crate::TWISTED_EDWARDS_BASE_POINT.T,
70    };
71    /// Identity point
72    pub const IDENTITY: ExtendedPoint = ExtendedPoint {
73        X: FieldElement::ZERO,
74        Y: FieldElement::ONE,
75        Z: FieldElement::ONE,
76        T: FieldElement::ZERO,
77    };
78
79    /// Adds an extensible point to an extended point
80    /// Returns an extensible point
81    /// (3.1) https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf
82    pub fn add_extended(&self, other: &ExtendedPoint) -> ExtensiblePoint {
83        let A = self.X * other.X;
84        let B = self.Y * other.Y;
85        let C = self.T * other.T * FieldElement::TWISTED_D;
86        let D = self.Z * other.Z;
87        let E = (self.X + self.Y) * (other.X + other.Y) - A - B;
88        let F = D - C;
89        let G = D + C;
90        let H = B + A;
91        ExtensiblePoint {
92            X: E * F,
93            Y: G * H,
94            T1: E,
95            T2: H,
96            Z: F * G,
97        }
98    }
99
100    /// Subtracts an extensible point from an extended point
101    /// Returns an extensible point
102    /// This is a direct modification of the addition formula to the negation of `other`
103    pub fn sub_extended(&self, other: &ExtendedPoint) -> ExtensiblePoint {
104        let A = self.X * other.X;
105        let B = self.Y * other.Y;
106        let C = self.T * other.T * FieldElement::TWISTED_D;
107        let D = self.Z * other.Z;
108        let E = (self.X + self.Y) * (other.Y - other.X) + A - B;
109        let F = D + C;
110        let G = D - C;
111        let H = B - A;
112        ExtensiblePoint {
113            X: E * F,
114            Y: G * H,
115            T1: E,
116            T2: H,
117            Z: F * G,
118        }
119    }
120
121    /// Adds an extensible point to an AffineNiels point
122    /// Returns an Extensible point
123    pub fn add_affine_niels(&self, other: AffineNielsPoint) -> ExtensiblePoint {
124        let A = other.y_minus_x * (self.Y - self.X);
125        let B = other.y_plus_x * (self.X + self.Y);
126        let C = other.td * self.T;
127        let D = B + A;
128        let E = B - A;
129        let F = self.Z - C;
130        let G = self.Z + C;
131        ExtensiblePoint {
132            X: E * F,
133            Y: G * D,
134            Z: F * G,
135            T1: E,
136            T2: D,
137        }
138    }
139
140    /// Adds an extensible point to a ProjectiveNiels point
141    /// Returns an extensible point
142    /// (3.1)[Last set of formulas] https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf
143    /// This differs from the formula above by a factor of 2. Saving 1 Double
144    /// Cost 8M
145    pub fn add_projective_niels(&self, other: &ProjectiveNielsPoint) -> ExtensiblePoint {
146        // This is the only step which makes it different than adding an AffineNielsPoint
147        let Z = self.Z * other.Z;
148
149        let A = (self.Y - self.X) * other.Y_minus_X;
150        let B = (self.Y + self.X) * other.Y_plus_X;
151        let C = other.Td * self.T;
152        let D = B + A;
153        let E = B - A;
154        let F = Z - C;
155        let G = Z + C;
156        ExtensiblePoint {
157            X: E * F,
158            Y: G * D,
159            Z: F * G,
160            T1: E,
161            T2: D,
162        }
163    }
164
165    /// Converts an ExtendedPoint to an ExtensiblePoint
166    pub fn to_extensible(self) -> ExtensiblePoint {
167        ExtensiblePoint {
168            X: self.X,
169            Y: self.Y,
170            Z: self.Z,
171            T1: self.T,
172            T2: FieldElement::ONE,
173        }
174    }
175
176    /// Uses a 2-isogeny to map the point to the Ed448-Goldilocks
177    pub fn to_untwisted(self) -> EdwardsExtendedPoint {
178        let IsogenyMapResult { X, Y, Z, T1, T2 } = IsogenyMap {
179            X: self.X,
180            Y: self.Y,
181            Z: self.Z,
182            T: self.T,
183        }
184        .map(|f| -f);
185
186        EdwardsExtendedPoint {
187            X,
188            Y,
189            Z,
190            T: T1 * T2,
191        }
192    }
193
194    /// Converts an Extensible point to a ProjectiveNiels Point
195    pub fn to_projective_niels(self) -> ProjectiveNielsPoint {
196        ProjectiveNielsPoint {
197            Y_plus_X: self.X + self.Y,
198            Y_minus_X: self.Y - self.X,
199            Z: self.Z.double(),
200            Td: self.T * FieldElement::TWO_TIMES_TWISTED_D,
201        }
202    }
203
204    /// Checks if the point is on the curve
205    pub(crate) fn is_on_curve(&self) -> Choice {
206        let XY = self.X * self.Y;
207        let ZT = self.Z * self.T;
208
209        // Y^2 - X^2 == Z^2 + T^2 * (TWISTED_D)
210
211        let YY = self.Y.square();
212        let XX = self.X.square();
213        let ZZ = self.Z.square();
214        let TT = self.T.square();
215        let lhs = YY - XX;
216        let rhs = ZZ + TT * FieldElement::TWISTED_D;
217
218        XY.ct_eq(&ZT) & lhs.ct_eq(&rhs)
219    }
220
221    /// Negates a point
222    pub fn negate(&self) -> ExtendedPoint {
223        ExtendedPoint {
224            X: -self.X,
225            Y: self.Y,
226            Z: self.Z,
227            T: -self.T,
228        }
229    }
230
231    /// Torques a point
232    pub fn torque(&self) -> ExtendedPoint {
233        ExtendedPoint {
234            X: -self.X,
235            Y: -self.Y,
236            Z: self.Z,
237            T: self.T,
238        }
239    }
240}
241
242#[cfg(test)]
243mod tests {
244    use super::*;
245    use crate::curve::twedwards::affine::AffinePoint;
246    use crate::{GOLDILOCKS_BASE_POINT, TWISTED_EDWARDS_BASE_POINT};
247
248    fn hex_to_field(hex: &'static str) -> FieldElement {
249        assert_eq!(hex.len(), 56 * 2);
250        let mut bytes =
251            hex_literal::decode(&[hex.as_bytes()]).expect("Output array length should be correct");
252        bytes.reverse();
253        FieldElement::from_bytes(&bytes)
254    }
255
256    #[test]
257    fn test_isogeny() {
258        let x = hex_to_field(
259            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555",
260        );
261        let y = hex_to_field(
262            "ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed",
263        );
264        let a = AffinePoint { x, y }.to_extensible();
265        let twist_a = a.to_extended().to_untwisted().to_twisted();
266        assert_eq!(twist_a, a.double().double())
267    }
268
269    #[test]
270    fn test_is_on_curve() {
271        // The twisted edwards basepoint should be on the curve
272        // twisted edwards curve
273        assert_eq!(TWISTED_EDWARDS_BASE_POINT.is_on_curve().unwrap_u8(), 1u8);
274
275        // The goldilocks basepoint should not be
276        let invalid_point = ExtendedPoint {
277            X: GOLDILOCKS_BASE_POINT.X,
278            Y: GOLDILOCKS_BASE_POINT.Y,
279            Z: GOLDILOCKS_BASE_POINT.Z,
280            T: GOLDILOCKS_BASE_POINT.T,
281        };
282        assert_eq!(invalid_point.is_on_curve().unwrap_u8(), 0u8);
283    }
284
285    #[test]
286    fn test_point_add() {
287        let a = TWISTED_EDWARDS_BASE_POINT;
288        let b = a.to_extensible().double().to_extended();
289
290        // A + B = B + A = C
291        let c_1 = a.add_extended(&b).to_extended();
292        let c_2 = b.add_extended(&a).to_extended();
293        assert!(c_1 == c_2);
294
295        // Adding identity point should not change result
296        let c = c_1.add_extended(&ExtendedPoint::IDENTITY);
297        assert!(c == c_1);
298    }
299
300    #[test]
301    fn test_point_sub() {
302        let a = TWISTED_EDWARDS_BASE_POINT;
303        let b = a.to_extensible().double().to_extended();
304
305        // A - B = C
306        let c_1 = a.sub_extended(&b).to_extended();
307
308        // -B + A = C
309        let c_2 = b.negate().add_extended(&a).to_extended();
310        assert!(c_1 == c_2);
311    }
312
313    #[test]
314    fn test_negate() {
315        let a = TWISTED_EDWARDS_BASE_POINT;
316        let neg_a = a.negate();
317
318        assert!(a.add_extended(&neg_a) == ExtensiblePoint::IDENTITY);
319    }
320}
ed448_goldilocks/curve/twedwards/extended.rs

ed448_goldilocks/curve/twedwards/
extended.rs
