lambdaworks_math/elliptic_curve/short_weierstrass/
point.rs

1use crate::{
2    cyclic_group::IsGroup,
3    elliptic_curve::{
4        point::{JacobianPoint, ProjectivePoint},
5        traits::{EllipticCurveError, FromAffine, IsEllipticCurve},
6    },
7    errors::DeserializationError,
8    field::element::FieldElement,
9    traits::{ByteConversion, Deserializable},
10};
11
12use super::traits::IsShortWeierstrass;
13
14#[cfg(feature = "alloc")]
15use crate::traits::AsBytes;
16#[cfg(feature = "alloc")]
17use alloc::vec::Vec;
18
19#[derive(Clone, Debug)]
20pub struct ShortWeierstrassProjectivePoint<E: IsEllipticCurve>(ProjectivePoint<E>);
21
22impl<E: IsShortWeierstrass> ShortWeierstrassProjectivePoint<E> {
23    /// Creates an elliptic curve point giving the projective [x: y: z] coordinates.
24    pub fn new(value: [FieldElement<E::BaseField>; 3]) -> Result<Self, EllipticCurveError> {
25        let (x, y, z) = (&value[0], &value[1], &value[2]);
26        if z != &FieldElement::<E::BaseField>::zero()
27            && E::defining_equation_projective(x, y, z) == FieldElement::<E::BaseField>::zero()
28        {
29            Ok(Self(ProjectivePoint::new(value)))
30        // The point at infinity is (0, 1, 0)
31        // We convert every (0, _, 0) into the infinity.
32        } else if x == &FieldElement::<E::BaseField>::zero()
33            && z == &FieldElement::<E::BaseField>::zero()
34        {
35            Ok(Self(ProjectivePoint::new([
36                FieldElement::<E::BaseField>::zero(),
37                FieldElement::<E::BaseField>::one(),
38                FieldElement::<E::BaseField>::zero(),
39            ])))
40        } else {
41            Err(EllipticCurveError::InvalidPoint)
42        }
43    }
44
45    /// Creates an elliptic curve point giving the projective [x: y: z] coordinates without
46    /// checking that the point satisfies the curve equation.
47    pub const fn new_unchecked(value: [FieldElement<E::BaseField>; 3]) -> Self {
48        // SAFETY: The caller MUST ensure that [x:y:z] represents valid point on the
49        // curve. Passing arbitrary coordinates here can violate the invariant
50        // and produce silently incorrect results in subsequent operations.
51        Self(ProjectivePoint::new(value))
52    }
53
54    /// Changes the point coordinates without checking that it satisfies the curve equation.
55    pub fn set_unchecked(&mut self, value: [FieldElement<E::BaseField>; 3]) {
56        // SAFETY: The caller MUST ensure that the provided coordinates represent a valid curve
57        // point. Setting invalid coordinates may lead to silently incorrect computations later on.
58        self.0.value = value
59    }
60
61    /// Returns the `x` coordinate of the point.
62    pub fn x(&self) -> &FieldElement<E::BaseField> {
63        self.0.x()
64    }
65
66    /// Returns the `y` coordinate of the point.
67    pub fn y(&self) -> &FieldElement<E::BaseField> {
68        self.0.y()
69    }
70
71    /// Returns the `z` coordinate of the point.
72    pub fn z(&self) -> &FieldElement<E::BaseField> {
73        self.0.z()
74    }
75
76    /// Returns a tuple [x, y, z] with the coordinates of the point.
77    pub fn coordinates(&self) -> &[FieldElement<E::BaseField>; 3] {
78        self.0.coordinates()
79    }
80
81    /// Returns the affine representation of the point [x, y, 1]
82    pub fn to_affine(&self) -> Self {
83        Self(self.0.to_affine())
84    }
85
86    /// Performs the group operation between a point and itself a + a = 2a in
87    /// additive notation
88    pub fn double(&self) -> Self {
89        if self.is_neutral_element() {
90            return self.clone();
91        }
92        let [px, py, pz] = self.coordinates();
93
94        let px_square = px * px;
95        let three_px_square = &px_square + &px_square + &px_square;
96        let w = E::a() * pz * pz + three_px_square;
97        let w_square = &w * &w;
98
99        let s = py * pz;
100        let s_square = &s * &s;
101        let s_cube = &s * &s_square;
102        let two_s_cube = &s_cube + &s_cube;
103        let four_s_cube = &two_s_cube + &two_s_cube;
104        let eight_s_cube = &four_s_cube + &four_s_cube;
105
106        let b = px * py * &s;
107        let two_b = &b + &b;
108        let four_b = &two_b + &two_b;
109        let eight_b = &four_b + &four_b;
110
111        let h = &w_square - eight_b;
112        let hs = &h * &s;
113
114        let pys_square = py * py * s_square;
115        let two_pys_square = &pys_square + &pys_square;
116        let four_pys_square = &two_pys_square + &two_pys_square;
117        let eight_pys_square = &four_pys_square + &four_pys_square;
118
119        let xp = &hs + &hs;
120        let yp = w * (four_b - &h) - eight_pys_square;
121        let zp = eight_s_cube;
122
123        debug_assert_eq!(
124            E::defining_equation_projective(&xp, &yp, &zp),
125            FieldElement::<E::BaseField>::zero()
126        );
127        // SAFETY: The values `x_p, y_p, z_p` are computed correctly to be on the curve.
128        // The assertion above verifies that the resulting point is valid.
129        Self::new_unchecked([xp, yp, zp])
130    }
131    // https://hyperelliptic.org/EFD/g1p/data/shortw/projective/addition/madd-1998-cmo
132    /// More efficient than operate_with, but must ensure that other is in affine form
133    pub fn operate_with_affine(&self, other: &Self) -> Self {
134        if self.is_neutral_element() {
135            return other.clone();
136        }
137        if other.is_neutral_element() {
138            return self.clone();
139        }
140
141        let [px, py, pz] = self.coordinates();
142        let [qx, qy, _qz] = other.coordinates();
143        let u = qy * pz;
144        let v = qx * pz;
145
146        if u == *py {
147            if v != *px || *py == FieldElement::zero() {
148                // SAFETY: The point (0, 1, 0) is defined as the point at infinity.
149                return Self::new_unchecked([
150                    FieldElement::zero(),
151                    FieldElement::one(),
152                    FieldElement::zero(),
153                ]);
154            } else {
155                return self.double();
156            }
157        }
158
159        let u = &u - py;
160        let v = &v - px;
161        let vv = &v * &v;
162        let uu = &u * &u;
163        let vvv = &v * &vv;
164        let r = &vv * px;
165        let a = &uu * pz - &vvv - &r - &r;
166
167        let x = &v * &a;
168        let y = &u * (&r - &a) - &vvv * py;
169        let z = &vvv * pz;
170
171        debug_assert_eq!(
172            E::defining_equation_projective(&x, &y, &z),
173            FieldElement::<E::BaseField>::zero()
174        );
175        // SAFETY: The values `x, y, z` are computed correctly to be on the curve.
176        // The assertion above verifies that the resulting point is valid.
177        Self::new_unchecked([x, y, z])
178    }
179}
180
181impl<E: IsEllipticCurve> PartialEq for ShortWeierstrassProjectivePoint<E> {
182    fn eq(&self, other: &Self) -> bool {
183        self.0 == other.0
184    }
185}
186
187impl<E: IsEllipticCurve> Eq for ShortWeierstrassProjectivePoint<E> {}
188
189impl<E: IsShortWeierstrass> FromAffine<E::BaseField> for ShortWeierstrassProjectivePoint<E> {
190    fn from_affine(
191        x: FieldElement<E::BaseField>,
192        y: FieldElement<E::BaseField>,
193    ) -> Result<Self, EllipticCurveError> {
194        let coordinates = [x, y, FieldElement::one()];
195        ShortWeierstrassProjectivePoint::new(coordinates)
196    }
197}
198
199impl<E: IsShortWeierstrass> IsGroup for ShortWeierstrassProjectivePoint<E> {
200    /// The point at infinity.
201    fn neutral_element() -> Self {
202        // SAFETY:
203        // - `(0, 1, 0)` is **mathematically valid** as the neutral element.
204        Self::new_unchecked([
205            FieldElement::zero(),
206            FieldElement::one(),
207            FieldElement::zero(),
208        ])
209    }
210
211    fn is_neutral_element(&self) -> bool {
212        let pz = self.z();
213        pz == &FieldElement::zero()
214    }
215
216    /// Computes the addition of `self` and `other`.
217    /// Taken from "Moonmath" (Algorithm 7, page 89)
218    fn operate_with(&self, other: &Self) -> Self {
219        if other.is_neutral_element() {
220            self.clone()
221        } else if self.is_neutral_element() {
222            other.clone()
223        } else {
224            let [px, py, pz] = self.coordinates();
225            let [qx, qy, qz] = other.coordinates();
226            let u1 = qy * pz;
227            let u2 = py * qz;
228            let v1 = qx * pz;
229            let v2 = px * qz;
230            if v1 == v2 {
231                if u1 != u2 || *py == FieldElement::zero() {
232                    Self::neutral_element()
233                } else {
234                    self.double()
235                }
236            } else {
237                let u = u1 - &u2;
238                let v = v1 - &v2;
239                let w = pz * qz;
240
241                let u_square = &u * &u;
242                let v_square = &v * &v;
243                let v_cube = &v * &v_square;
244                let v_square_v2 = &v_square * &v2;
245
246                let a = &u_square * &w - &v_cube - (&v_square_v2 + &v_square_v2);
247
248                let xp = &v * &a;
249                let yp = u * (&v_square_v2 - a) - &v_cube * u2;
250                let zp = &v_cube * w;
251
252                debug_assert_eq!(
253                    E::defining_equation_projective(&xp, &yp, &zp),
254                    FieldElement::<E::BaseField>::zero()
255                );
256                // SAFETY: The values `x_p, y_p, z_p` are computed correctly to be on the curve.
257                // The assertion above verifies that the resulting point is valid.
258                Self::new_unchecked([xp, yp, zp])
259            }
260        }
261    }
262
263    /// Returns the additive inverse of the projective point `p`
264    fn neg(&self) -> Self {
265        let [px, py, pz] = self.coordinates();
266        // SAFETY:
267        // - Negating `y` maintains the curve structure.
268        Self::new_unchecked([px.clone(), -py, pz.clone()])
269    }
270}
271
272#[derive(PartialEq)]
273pub enum PointFormat {
274    Projective,
275    Uncompressed,
276    // Compressed,
277}
278
279#[derive(PartialEq)]
280/// Describes the endianess of the internal types of the types
281/// For example, in a field made with limbs of u64
282/// this is the endianess of those u64
283pub enum Endianness {
284    BigEndian,
285    LittleEndian,
286}
287
288impl<E> ShortWeierstrassProjectivePoint<E>
289where
290    E: IsShortWeierstrass,
291    FieldElement<E::BaseField>: ByteConversion,
292{
293    /// Serialize the points in the given format
294    #[cfg(feature = "alloc")]
295    pub fn serialize(&self, point_format: PointFormat, endianness: Endianness) -> Vec<u8> {
296        // TODO: Add more compact serialization formats
297        // Uncompressed affine / Compressed
298
299        let mut bytes: Vec<u8> = Vec::new();
300        let x_bytes: Vec<u8>;
301        let y_bytes: Vec<u8>;
302        let z_bytes: Vec<u8>;
303
304        match point_format {
305            PointFormat::Projective => {
306                let [x, y, z] = self.coordinates();
307                if endianness == Endianness::BigEndian {
308                    x_bytes = x.to_bytes_be();
309                    y_bytes = y.to_bytes_be();
310                    z_bytes = z.to_bytes_be();
311                } else {
312                    x_bytes = x.to_bytes_le();
313                    y_bytes = y.to_bytes_le();
314                    z_bytes = z.to_bytes_le();
315                }
316                bytes.extend(&x_bytes);
317                bytes.extend(&y_bytes);
318                bytes.extend(&z_bytes);
319            }
320            PointFormat::Uncompressed => {
321                let affine_representation = self.to_affine();
322                let [x, y, _z] = affine_representation.coordinates();
323                if endianness == Endianness::BigEndian {
324                    x_bytes = x.to_bytes_be();
325                    y_bytes = y.to_bytes_be();
326                } else {
327                    x_bytes = x.to_bytes_le();
328                    y_bytes = y.to_bytes_le();
329                }
330                bytes.extend(&x_bytes);
331                bytes.extend(&y_bytes);
332            }
333        }
334        bytes
335    }
336
337    pub fn deserialize(
338        bytes: &[u8],
339        point_format: PointFormat,
340        endianness: Endianness,
341    ) -> Result<Self, DeserializationError> {
342        match point_format {
343            PointFormat::Projective => {
344                if !bytes.len().is_multiple_of(3) {
345                    return Err(DeserializationError::InvalidAmountOfBytes);
346                }
347
348                let len = bytes.len() / 3;
349                let x: FieldElement<E::BaseField>;
350                let y: FieldElement<E::BaseField>;
351                let z: FieldElement<E::BaseField>;
352
353                if endianness == Endianness::BigEndian {
354                    x = ByteConversion::from_bytes_be(&bytes[..len])?;
355                    y = ByteConversion::from_bytes_be(&bytes[len..len * 2])?;
356                    z = ByteConversion::from_bytes_be(&bytes[len * 2..])?;
357                } else {
358                    x = ByteConversion::from_bytes_le(&bytes[..len])?;
359                    y = ByteConversion::from_bytes_le(&bytes[len..len * 2])?;
360                    z = ByteConversion::from_bytes_le(&bytes[len * 2..])?;
361                }
362
363                let Ok(z_inv) = z.inv() else {
364                    let point = Self::new([x, y, z])
365                        .map_err(|_| DeserializationError::FieldFromBytesError)?;
366                    return if point.is_neutral_element() {
367                        Ok(point)
368                    } else {
369                        Err(DeserializationError::FieldFromBytesError)
370                    };
371                };
372                let x_affine = &x * &z_inv;
373                let y_affine = &y * &z_inv;
374                if E::defining_equation(&x_affine, &y_affine) == FieldElement::zero() {
375                    Self::new([x, y, z]).map_err(|_| DeserializationError::FieldFromBytesError)
376                } else {
377                    Err(DeserializationError::FieldFromBytesError)
378                }
379            }
380            PointFormat::Uncompressed => {
381                if !bytes.len().is_multiple_of(2) {
382                    return Err(DeserializationError::InvalidAmountOfBytes);
383                }
384
385                let len = bytes.len() / 2;
386                let x: FieldElement<E::BaseField>;
387                let y: FieldElement<E::BaseField>;
388
389                if endianness == Endianness::BigEndian {
390                    x = ByteConversion::from_bytes_be(&bytes[..len])?;
391                    y = ByteConversion::from_bytes_be(&bytes[len..])?;
392                } else {
393                    x = ByteConversion::from_bytes_le(&bytes[..len])?;
394                    y = ByteConversion::from_bytes_le(&bytes[len..])?;
395                }
396
397                let z = FieldElement::<E::BaseField>::one();
398                let point =
399                    Self::new([x, y, z]).map_err(|_| DeserializationError::FieldFromBytesError)?;
400                Ok(point)
401            }
402        }
403    }
404}
405
406#[cfg(feature = "alloc")]
407impl<E> AsBytes for ShortWeierstrassProjectivePoint<E>
408where
409    E: IsShortWeierstrass,
410    FieldElement<E::BaseField>: ByteConversion,
411{
412    fn as_bytes(&self) -> alloc::vec::Vec<u8> {
413        self.serialize(PointFormat::Projective, Endianness::LittleEndian)
414    }
415}
416
417#[cfg(feature = "alloc")]
418impl<E> From<ShortWeierstrassProjectivePoint<E>> for alloc::vec::Vec<u8>
419where
420    E: IsShortWeierstrass,
421    FieldElement<E::BaseField>: ByteConversion,
422{
423    fn from(value: ShortWeierstrassProjectivePoint<E>) -> Self {
424        value.as_bytes()
425    }
426}
427
428impl<E> Deserializable for ShortWeierstrassProjectivePoint<E>
429where
430    E: IsShortWeierstrass,
431    FieldElement<E::BaseField>: ByteConversion,
432{
433    fn deserialize(bytes: &[u8]) -> Result<Self, DeserializationError>
434    where
435        Self: Sized,
436    {
437        Self::deserialize(bytes, PointFormat::Projective, Endianness::LittleEndian)
438    }
439}
440
441#[derive(Clone, Debug)]
442pub struct ShortWeierstrassJacobianPoint<E: IsEllipticCurve>(pub JacobianPoint<E>);
443
444impl<E: IsShortWeierstrass> ShortWeierstrassJacobianPoint<E> {
445    /// Creates an elliptic curve point giving the jacobian [x: y: z] coordinates.
446    pub fn new(value: [FieldElement<E::BaseField>; 3]) -> Result<Self, EllipticCurveError> {
447        let (x, y, z) = (&value[0], &value[1], &value[2]);
448
449        if z != &FieldElement::<E::BaseField>::zero()
450            && E::defining_equation_jacobian(x, y, z) == FieldElement::<E::BaseField>::zero()
451        {
452            Ok(Self(JacobianPoint::new(value)))
453        // The point at infinity is (1, 1, 0)
454        // We convert every (x, x, 0) into the infinity.
455        } else if z == &FieldElement::<E::BaseField>::zero() && x == y {
456            Ok(Self(JacobianPoint::new([
457                FieldElement::<E::BaseField>::one(),
458                FieldElement::<E::BaseField>::one(),
459                FieldElement::<E::BaseField>::zero(),
460            ])))
461        } else {
462            Err(EllipticCurveError::InvalidPoint)
463        }
464    }
465
466    /// Creates an elliptic curve point giving the projective [x: y: z] coordinates without
467    /// checking that the point satisfies the curve equation.
468    pub const fn new_unchecked(value: [FieldElement<E::BaseField>; 3]) -> Self {
469        // SAFETY: The caller MUST ensure that [x:y:z] represents either a valid point on the
470        // curve. Passing arbitrary coordinates here can violate the invariant
471        // and produce silently incorrect results in subsequent operations.
472        Self(JacobianPoint::new(value))
473    }
474
475    /// Returns the `x` coordinate of the point.
476    pub fn x(&self) -> &FieldElement<E::BaseField> {
477        self.0.x()
478    }
479
480    /// Returns the `y` coordinate of the point.
481    pub fn y(&self) -> &FieldElement<E::BaseField> {
482        self.0.y()
483    }
484
485    /// Returns the `z` coordinate of the point.
486    pub fn z(&self) -> &FieldElement<E::BaseField> {
487        self.0.z()
488    }
489
490    /// Returns a tuple [x, y, z] with the coordinates of the point.
491    pub fn coordinates(&self) -> &[FieldElement<E::BaseField>; 3] {
492        self.0.coordinates()
493    }
494
495    /// Creates the same point in affine coordinates. That is,
496    /// returns [x / z^2: y / z^3: 1] where `self` is [x: y: z].
497    /// Panics if `self` is the point at infinity.
498    pub fn to_affine(&self) -> Self {
499        Self(self.0.to_affine())
500    }
501
502    /// Applies the group operation between a point and itself
503    pub fn double(&self) -> Self {
504        if self.is_neutral_element() {
505            return self.clone();
506        }
507        let [x1, y1, z1] = self.coordinates();
508        //http://www.hyperelliptic.org/EFD/g1p/data/shortw/jacobian-0/doubling/dbl-2009-l
509
510        if E::a() == FieldElement::zero() {
511            let a = x1.square(); // A = x1^2
512            let b = y1.square(); // B = y1^2
513            let c = b.square(); // C = B^2
514            let x1_plus_b = x1 + &b; // (X1 + B)
515            let x1_plus_b_square = x1_plus_b.square(); // (X1 + B)^2
516            let d = (&x1_plus_b_square - &a - &c).double(); // D = 2 * ((X1 + B)^2 - A - C)
517            let e = &a.double() + &a; // E = 3 * A
518            let f = e.square(); // F = E^2
519            let x3 = &f - &d.double(); // X3 = F - 2 * D
520            let y3 = &e * (&d - &x3) - &c.double().double().double(); // Y3 = E * (D - X3) - 8 * C
521            let z3 = (y1 * z1).double(); // Z3 = 2 * Y1 * Z1
522
523            debug_assert_eq!(
524                E::defining_equation_jacobian(&x3, &y3, &z3),
525                FieldElement::<E::BaseField>::zero()
526            );
527            // SAFETY: The values `x_3, y_3, z_3` are computed correctly to be on the curve.
528            // The assertion above verifies that the resulting point is valid.
529            Self::new_unchecked([x3, y3, z3])
530        } else {
531            // http://www.hyperelliptic.org/EFD/g1p/data/shortw/jacobian-0/doubling/dbl-2009-alnr
532            // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
533            let xx = x1.square(); // XX = X1^2
534            let yy = y1.square(); // YY = Y1^2
535            let yyyy = yy.square(); // YYYY = YY^2
536            let zz = z1.square(); // ZZ = Z1^2
537            let s = ((x1 + &yy).square() - &xx - &yyyy).double(); // S = 2 * ((X1 + YY)^2 - XX - YYYY)
538            let m = &xx.double() + &xx + &E::a() * &zz.square(); // M = 3 * XX + a * ZZ^2
539            let x3 = m.square() - &s.double(); // X3 = M^2 - 2 * S
540            let y3 = m * (&s - &x3) - &yyyy.double().double().double(); // Y3 = M * (S - X3) - 8 * YYYY
541            let z3 = (y1 + z1).square() - &yy - &zz; // Z3 = (Y1 + Z1)^2 - YY - ZZ
542
543            debug_assert_eq!(
544                E::defining_equation_jacobian(&x3, &y3, &z3),
545                FieldElement::<E::BaseField>::zero()
546            );
547            // SAFETY: The values `x_3, y_3, z_3` are computed correctly to be on the curve.
548            // The assertion above verifies that the resulting point is valid.
549            Self::new_unchecked([x3, y3, z3])
550        }
551    }
552
553    /// More efficient than operate_with. Other should be in affine form!
554    pub fn operate_with_affine(&self, other: &Self) -> Self {
555        let [x1, y1, z1] = self.coordinates();
556        let [x2, y2, _z2] = other.coordinates();
557
558        if self.is_neutral_element() {
559            return other.clone();
560        }
561        if other.is_neutral_element() {
562            return self.clone();
563        }
564
565        let z1z1 = z1.square();
566        let u1 = x1;
567        let u2 = x2 * &z1z1;
568        let s1 = y1;
569        let s2 = y2 * z1 * &z1z1;
570
571        if *u1 == u2 {
572            if *s1 == s2 {
573                self.double() // Is the same point
574            } else {
575                Self::neutral_element() // P + (-P) = 0
576            }
577        } else {
578            let h = &u2 - u1;
579            let hh = h.square();
580            let hhh = &h * &hh;
581            let r = &s2 - s1;
582            let v = u1 * &hh;
583            let x3 = r.square() - (&hhh + &v + &v);
584            let y3 = r * (&v - &x3) - s1 * &hhh;
585            let z3 = z1 * &h;
586
587            debug_assert_eq!(
588                E::defining_equation_jacobian(&x3, &y3, &z3),
589                FieldElement::<E::BaseField>::zero()
590            );
591            // SAFETY: The values `x_3, y_3, z_3` are computed correctly to be on the curve.
592            // The assertion above verifies that the resulting point is valid.
593            Self::new_unchecked([x3, y3, z3])
594        }
595    }
596}
597
598impl<E: IsEllipticCurve> PartialEq for ShortWeierstrassJacobianPoint<E> {
599    fn eq(&self, other: &Self) -> bool {
600        self.0 == other.0
601    }
602}
603
604impl<E: IsEllipticCurve> Eq for ShortWeierstrassJacobianPoint<E> {}
605
606impl<E: IsShortWeierstrass> FromAffine<E::BaseField> for ShortWeierstrassJacobianPoint<E> {
607    fn from_affine(
608        x: FieldElement<E::BaseField>,
609        y: FieldElement<E::BaseField>,
610    ) -> Result<Self, EllipticCurveError> {
611        let coordinates = [x, y, FieldElement::one()];
612        ShortWeierstrassJacobianPoint::new(coordinates)
613    }
614}
615
616impl<E: IsShortWeierstrass> IsGroup for ShortWeierstrassJacobianPoint<E> {
617    /// The point at infinity.
618    fn neutral_element() -> Self {
619        // SAFETY:
620        // - `(1, 1, 0)` is **mathematically valid** as the neutral element.
621        Self::new_unchecked([
622            FieldElement::one(),
623            FieldElement::one(),
624            FieldElement::zero(),
625        ])
626    }
627
628    fn is_neutral_element(&self) -> bool {
629        let pz = self.z();
630        pz == &FieldElement::zero()
631    }
632
633    /// Computes the addition of `self` and `other`.
634    /// https://github.com/mratsim/constantine/blob/65147ed815d96fa94a05d307c1d9980877b7d0e8/constantine/math/elliptic/ec_shortweierstrass_jacobian.md
635    fn operate_with(&self, other: &Self) -> Self {
636        if self.is_neutral_element() {
637            return other.clone();
638        }
639
640        if other.is_neutral_element() {
641            return self.clone();
642        }
643
644        let [x1, y1, z1] = self.coordinates();
645        let [x2, y2, z2] = other.coordinates();
646
647        let z1_sq = z1.square(); // Z1^2
648        let z2_sq = z2.square(); // Z2^2
649
650        let u1 = x1 * &z2_sq; // U1 = X1 * Z2^2
651        let u2 = x2 * &z1_sq; // U2 = X2 * Z1^2
652
653        let z1_cu = z1 * &z1_sq; // Z1^3
654        let z2_cu = z2 * &z2_sq; // Z2^3
655
656        let s1 = y1 * &z2_cu; // S1 = Y1 * Z2^3
657        let s2 = y2 * &z1_cu; // S2 = Y2 * Z1^3
658
659        if u1 == u2 {
660            if s1 == s2 {
661                return self.double(); // P + P = 2P
662            } else {
663                return Self::neutral_element(); // P + (-P) = 0
664            }
665        }
666        // H = U2 - U1
667        let h = u2 - &u1;
668        // I = (2 * H)^2
669        let i = h.double().square();
670        // J = H * I
671        let j = -(&h * &i);
672
673        // R = 2 * (S2 - S1)
674        let r = (s2 - &s1).double();
675
676        // V = U1 * I
677        let v = u1 * &i;
678
679        // X3 = R^2 + J - 2 * V
680        let x3 = r.square() + &j - v.double();
681
682        // Y3 = R * (V - X3) + 2 * S1 * J
683        let y3 = r * (v - &x3) + (s1 * &j.double());
684
685        // Z3 = 2 * Z1 * Z2 * H
686        let z3 = z1 * z2;
687        let z3 = z3.double() * h;
688
689        debug_assert_eq!(
690            E::defining_equation_jacobian(&x3, &y3, &z3),
691            FieldElement::<E::BaseField>::zero()
692        );
693        // SAFETY: The values `x_3, y_3, z_3` are computed correctly to be on the curve.
694        // The assertion above verifies that the resulting point is valid.
695        Self::new_unchecked([x3, y3, z3])
696    }
697
698    /// Returns the additive inverse of the jacobian point `p`
699    fn neg(&self) -> Self {
700        let [x, y, z] = self.coordinates();
701        // SAFETY:
702        // - The negation formula for Short Weierstrass curves is well-defined.
703        // - The result remains a valid curve point.
704        Self::new_unchecked([x.clone(), -y, z.clone()])
705    }
706}
707
708#[cfg(test)]
709mod tests {
710    use super::*;
711    use crate::elliptic_curve::short_weierstrass::curves::bls12_381::curve::BLS12381Curve;
712
713    use crate::elliptic_curve::short_weierstrass::curves::bls12_381::curve::{
714        CURVE_COFACTOR, SUBGROUP_ORDER,
715    };
716    #[cfg(feature = "alloc")]
717    use crate::{
718        elliptic_curve::short_weierstrass::curves::bls12_381::field_extension::BLS12381PrimeField,
719        field::element::FieldElement,
720    };
721
722    #[cfg(feature = "alloc")]
723    #[allow(clippy::upper_case_acronyms)]
724    type FEE = FieldElement<BLS12381PrimeField>;
725
726    #[cfg(feature = "alloc")]
727    fn point() -> ShortWeierstrassProjectivePoint<BLS12381Curve> {
728        let x = FEE::new_base("36bb494facde72d0da5c770c4b16d9b2d45cfdc27604a25a1a80b020798e5b0dbd4c6d939a8f8820f042a29ce552ee5");
729        let y = FEE::new_base("7acf6e49cc000ff53b06ee1d27056734019c0a1edfa16684da41ebb0c56750f73bc1b0eae4c6c241808a5e485af0ba0");
730        BLS12381Curve::create_point_from_affine(x, y).unwrap()
731    }
732
733    #[cfg(feature = "alloc")]
734    #[test]
735    fn operate_with_works_jacobian() {
736        let x = FEE::new_base("36bb494facde72d0da5c770c4b16d9b2d45cfdc27604a25a1a80b020798e5b0dbd4c6d939a8f8820f042a29ce552ee5");
737        let y = FEE::new_base("7acf6e49cc000ff53b06ee1d27056734019c0a1edfa16684da41ebb0c56750f73bc1b0eae4c6c241808a5e485af0ba0");
738        let p = ShortWeierstrassJacobianPoint::<BLS12381Curve>::from_affine(x, y).unwrap();
739
740        assert_eq!(p.operate_with(&p), p.double());
741    }
742
743    #[cfg(feature = "alloc")]
744    #[test]
745    fn operate_with_self_works_jacobian() {
746        let x = FEE::new_base("36bb494facde72d0da5c770c4b16d9b2d45cfdc27604a25a1a80b020798e5b0dbd4c6d939a8f8820f042a29ce552ee5");
747        let y = FEE::new_base("7acf6e49cc000ff53b06ee1d27056734019c0a1edfa16684da41ebb0c56750f73bc1b0eae4c6c241808a5e485af0ba0");
748        let p = ShortWeierstrassJacobianPoint::<BLS12381Curve>::from_affine(x, y).unwrap();
749
750        assert_eq!(
751            p.operate_with_self(5_u16),
752            p.double().double().operate_with(&p)
753        );
754    }
755    #[cfg(feature = "alloc")]
756    #[test]
757    fn byte_conversion_from_and_to_be_projective() {
758        let expected_point = point();
759        let bytes_be = expected_point.serialize(PointFormat::Projective, Endianness::BigEndian);
760
761        let result = ShortWeierstrassProjectivePoint::deserialize(
762            &bytes_be,
763            PointFormat::Projective,
764            Endianness::BigEndian,
765        );
766        assert_eq!(expected_point, result.unwrap());
767    }
768
769    #[cfg(feature = "alloc")]
770    #[test]
771    fn byte_conversion_from_and_to_be_uncompressed() {
772        let expected_point = point();
773        let bytes_be = expected_point.serialize(PointFormat::Uncompressed, Endianness::BigEndian);
774        let result = ShortWeierstrassProjectivePoint::deserialize(
775            &bytes_be,
776            PointFormat::Uncompressed,
777            Endianness::BigEndian,
778        );
779        assert_eq!(expected_point, result.unwrap());
780    }
781
782    #[cfg(feature = "alloc")]
783    #[test]
784    fn byte_conversion_from_and_to_le_projective() {
785        let expected_point = point();
786        let bytes_be = expected_point.serialize(PointFormat::Projective, Endianness::LittleEndian);
787
788        let result = ShortWeierstrassProjectivePoint::deserialize(
789            &bytes_be,
790            PointFormat::Projective,
791            Endianness::LittleEndian,
792        );
793        assert_eq!(expected_point, result.unwrap());
794    }
795
796    #[cfg(feature = "alloc")]
797    #[test]
798    fn byte_conversion_from_and_to_le_uncompressed() {
799        let expected_point = point();
800        let bytes_be =
801            expected_point.serialize(PointFormat::Uncompressed, Endianness::LittleEndian);
802
803        let result = ShortWeierstrassProjectivePoint::deserialize(
804            &bytes_be,
805            PointFormat::Uncompressed,
806            Endianness::LittleEndian,
807        );
808        assert_eq!(expected_point, result.unwrap());
809    }
810
811    #[cfg(feature = "alloc")]
812    #[test]
813    fn byte_conversion_from_and_to_with_mixed_le_and_be_does_not_work_projective() {
814        let bytes = point().serialize(PointFormat::Projective, Endianness::LittleEndian);
815
816        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
817            &bytes,
818            PointFormat::Projective,
819            Endianness::BigEndian,
820        );
821
822        assert_eq!(
823            result.unwrap_err(),
824            DeserializationError::FieldFromBytesError
825        );
826    }
827
828    #[cfg(feature = "alloc")]
829    #[test]
830    fn byte_conversion_from_and_to_with_mixed_le_and_be_does_not_work_uncompressed() {
831        let bytes = point().serialize(PointFormat::Uncompressed, Endianness::LittleEndian);
832
833        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
834            &bytes,
835            PointFormat::Uncompressed,
836            Endianness::BigEndian,
837        );
838
839        assert_eq!(
840            result.unwrap_err(),
841            DeserializationError::FieldFromBytesError
842        );
843    }
844
845    #[cfg(feature = "alloc")]
846    #[test]
847    fn byte_conversion_from_and_to_with_mixed_be_and_le_does_not_work_projective() {
848        let bytes = point().serialize(PointFormat::Projective, Endianness::BigEndian);
849
850        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
851            &bytes,
852            PointFormat::Projective,
853            Endianness::LittleEndian,
854        );
855
856        assert_eq!(
857            result.unwrap_err(),
858            DeserializationError::FieldFromBytesError
859        );
860    }
861
862    #[cfg(feature = "alloc")]
863    #[test]
864    fn byte_conversion_from_and_to_with_mixed_be_and_le_does_not_work_uncompressed() {
865        let bytes = point().serialize(PointFormat::Uncompressed, Endianness::BigEndian);
866
867        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
868            &bytes,
869            PointFormat::Uncompressed,
870            Endianness::LittleEndian,
871        );
872
873        assert_eq!(
874            result.unwrap_err(),
875            DeserializationError::FieldFromBytesError
876        );
877    }
878
879    #[test]
880    fn cannot_create_point_from_wrong_number_of_bytes_le_projective() {
881        let bytes = &[0_u8; 13];
882
883        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
884            bytes,
885            PointFormat::Projective,
886            Endianness::LittleEndian,
887        );
888
889        assert_eq!(
890            result.unwrap_err(),
891            DeserializationError::InvalidAmountOfBytes
892        );
893    }
894
895    #[test]
896    fn cannot_create_point_from_wrong_number_of_bytes_le_uncompressed() {
897        let bytes = &[0_u8; 13];
898
899        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
900            bytes,
901            PointFormat::Uncompressed,
902            Endianness::LittleEndian,
903        );
904
905        assert_eq!(
906            result.unwrap_err(),
907            DeserializationError::InvalidAmountOfBytes
908        );
909    }
910
911    #[test]
912    fn cannot_create_point_from_wrong_number_of_bytes_be_projective() {
913        let bytes = &[0_u8; 13];
914
915        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
916            bytes,
917            PointFormat::Projective,
918            Endianness::BigEndian,
919        );
920
921        assert_eq!(
922            result.unwrap_err(),
923            DeserializationError::InvalidAmountOfBytes
924        );
925    }
926
927    #[test]
928    fn cannot_create_point_from_wrong_number_of_bytes_be_uncompressed() {
929        let bytes = &[0_u8; 13];
930
931        let result = ShortWeierstrassProjectivePoint::<BLS12381Curve>::deserialize(
932            bytes,
933            PointFormat::Uncompressed,
934            Endianness::BigEndian,
935        );
936
937        assert_eq!(
938            result.unwrap_err(),
939            DeserializationError::InvalidAmountOfBytes
940        );
941    }
942
943    #[test]
944    fn test_jacobian_vs_projective_operation() {
945        let x = FEE::new_base("36bb494facde72d0da5c770c4b16d9b2d45cfdc27604a25a1a80b020798e5b0dbd4c6d939a8f8820f042a29ce552ee5");
946        let y = FEE::new_base("7acf6e49cc000ff53b06ee1d27056734019c0a1edfa16684da41ebb0c56750f73bc1b0eae4c6c241808a5e485af0ba0");
947
948        let p = ShortWeierstrassJacobianPoint::<BLS12381Curve>::from_affine(x.clone(), y.clone())
949            .unwrap();
950        let q = ShortWeierstrassProjectivePoint::<BLS12381Curve>::from_affine(x, y).unwrap();
951
952        let sum_jacobian = p.operate_with_self(7_u16);
953        let sum_projective = q.operate_with_self(7_u16);
954
955        // Convert the result to affine coordinates
956        let sum_jacobian_affine = sum_jacobian.to_affine();
957        let [x_j, y_j, _] = sum_jacobian_affine.coordinates();
958
959        // Convert the result to affine coordinates
960        let binding = sum_projective.to_affine();
961        let [x_p, y_p, _] = binding.coordinates();
962
963        assert_eq!(x_j, x_p, "x coordintates do not match");
964        assert_eq!(y_j, y_p, "y coordinates do not match");
965    }
966
967    #[test]
968    fn test_multiplication_by_order_projective() {
969        let x = FEE::new_base("36bb494facde72d0da5c770c4b16d9b2d45cfdc27604a25a1a80b020798e5b0dbd4c6d939a8f8820f042a29ce552ee5");
970        let y = FEE::new_base("7acf6e49cc000ff53b06ee1d27056734019c0a1edfa16684da41ebb0c56750f73bc1b0eae4c6c241808a5e485af0ba0");
971
972        let p = ShortWeierstrassProjectivePoint::<BLS12381Curve>::from_affine(x.clone(), y.clone())
973            .unwrap();
974
975        let g = p
976            .operate_with_self(SUBGROUP_ORDER)
977            .operate_with_self(CURVE_COFACTOR);
978
979        assert!(
980            g.is_neutral_element(),
981            "Multiplication by order should result in the neutral element"
982        );
983    }
984
985    #[test]
986    fn test_multiplication_by_order_jacobian() {
987        let x = FEE::new_base("36bb494facde72d0da5c770c4b16d9b2d45cfdc27604a25a1a80b020798e5b0dbd4c6d939a8f8820f042a29ce552ee5");
988        let y = FEE::new_base("7acf6e49cc000ff53b06ee1d27056734019c0a1edfa16684da41ebb0c56750f73bc1b0eae4c6c241808a5e485af0ba0");
989
990        let p = ShortWeierstrassJacobianPoint::<BLS12381Curve>::from_affine(x.clone(), y.clone())
991            .unwrap();
992        let g = p
993            .operate_with_self(SUBGROUP_ORDER)
994            .operate_with_self(CURVE_COFACTOR);
995
996        assert!(
997            g.is_neutral_element(),
998            "Multiplication by order should result in the neutral element"
999        );
1000    }
1001}
lambdaworks_math/elliptic_curve/short_weierstrass/point.rs

lambdaworks_math/elliptic_curve/short_weierstrass/
point.rs
