ed448_goldilocks/edwards/
extended.rs

1use core::{
2    borrow::Borrow,
3    fmt::{Display, Formatter, LowerHex, Result as FmtResult, UpperHex},
4    iter::Sum,
5};
6use elliptic_curve::ops::{
7    Add, AddAssign, Mul, MulAssign, MulByGeneratorVartime, MulVartime, Neg, Sub, SubAssign,
8};
9
10use crate::{
11    GOLDILOCKS_BASE_POINT, MontgomeryPoint, U57, U448,
12    curve::{
13        scalar_mul::variable_base,
14        twedwards::{
15            IsogenyMap, IsogenyMapResult, extensible::ExtensiblePoint as TwistedExtensiblePoint,
16        },
17    },
18    edwards::{
19        CompressedEdwardsY,
20        affine::{AffinePoint, PointBytes},
21        scalar::EdwardsScalar,
22    },
23    field::{ConstMontyType, FieldElement},
24};
25use elliptic_curve::{
26    BatchNormalize, CurveGroup, Error, Generate,
27    array::Array,
28    ctutils,
29    group::{Group, GroupEncoding, cofactor::CofactorGroup, prime::PrimeGroup},
30    ops::{BatchInvert, LinearCombination},
31    point::NonIdentity,
32};
33use rand_core::{TryCryptoRng, TryRng};
34use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
35
36#[cfg(feature = "alloc")]
37use alloc::{boxed::Box, vec::Vec};
38
39/// Represent points on the (untwisted) edwards curve using Extended Homogenous Projective Co-ordinates
40/// (x, y) -> (X/Z, Y/Z, Z, T)
41/// a = 1, d = -39081
42/// XXX: Make this more descriptive
43/// Should this be renamed to EdwardsPoint so that we are consistent with Dalek crypto? Necessary as ExtendedPoint is not regular lingo?
44#[derive(Copy, Clone, Debug)]
45pub struct EdwardsPoint {
46    pub(crate) X: FieldElement,
47    pub(crate) Y: FieldElement,
48    pub(crate) Z: FieldElement,
49    pub(crate) T: FieldElement,
50}
51
52impl Default for EdwardsPoint {
53    fn default() -> Self {
54        Self::IDENTITY
55    }
56}
57
58impl Display for EdwardsPoint {
59    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
60        write!(
61            f,
62            "{{ X: {}, Y: {}, Z: {}, T: {} }}",
63            self.X, self.Y, self.Z, self.T
64        )
65    }
66}
67
68impl LowerHex for EdwardsPoint {
69    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
70        write!(
71            f,
72            "{{ X: {:x}, Y: {:x}, Z: {:x}, T: {:x} }}",
73            self.X, self.Y, self.Z, self.T
74        )
75    }
76}
77
78impl UpperHex for EdwardsPoint {
79    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
80        write!(
81            f,
82            "{{ X: {:X}, Y: {:X}, Z: {:X}, T: {:X} }}",
83            self.X, self.Y, self.Z, self.T
84        )
85    }
86}
87
88impl ConditionallySelectable for EdwardsPoint {
89    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
90        EdwardsPoint {
91            X: FieldElement::conditional_select(&a.X, &b.X, choice),
92            Y: FieldElement::conditional_select(&a.Y, &b.Y, choice),
93            Z: FieldElement::conditional_select(&a.Z, &b.Z, choice),
94            T: FieldElement::conditional_select(&a.T, &b.T, choice),
95        }
96    }
97}
98
99impl ConstantTimeEq for EdwardsPoint {
100    fn ct_eq(&self, other: &Self) -> Choice {
101        let XZ = self.X * other.Z;
102        let ZX = self.Z * other.X;
103
104        let YZ = self.Y * other.Z;
105        let ZY = self.Z * other.Y;
106
107        (XZ.ct_eq(&ZX)) & (YZ.ct_eq(&ZY))
108    }
109}
110
111impl ctutils::CtEq for EdwardsPoint {
112    fn ct_eq(&self, other: &Self) -> ctutils::Choice {
113        ConstantTimeEq::ct_eq(self, other).into()
114    }
115}
116
117impl ctutils::CtSelect for EdwardsPoint {
118    fn ct_select(&self, other: &Self, choice: ctutils::Choice) -> Self {
119        ConditionallySelectable::conditional_select(self, other, choice.into())
120    }
121}
122
123impl Eq for EdwardsPoint {}
124impl PartialEq for EdwardsPoint {
125    fn eq(&self, other: &EdwardsPoint) -> bool {
126        self.ct_eq(other).into()
127    }
128}
129
130impl Generate for EdwardsPoint {
131    fn try_generate_from_rng<R: TryCryptoRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
132        Self::try_random(rng)
133    }
134}
135
136impl Group for EdwardsPoint {
137    type Scalar = EdwardsScalar;
138
139    fn try_random<R>(rng: &mut R) -> Result<Self, R::Error>
140    where
141        R: TryRng + ?Sized,
142    {
143        loop {
144            let point = AffinePoint::try_random(rng)?;
145            if point != AffinePoint::IDENTITY {
146                break Ok(point.into());
147            }
148        }
149    }
150
151    fn identity() -> Self {
152        Self::IDENTITY
153    }
154
155    fn generator() -> Self {
156        Self::GENERATOR
157    }
158
159    fn is_identity(&self) -> Choice {
160        self.ct_eq(&Self::IDENTITY)
161    }
162
163    fn double(&self) -> Self {
164        self.double()
165    }
166}
167
168impl GroupEncoding for EdwardsPoint {
169    type Repr = Array<u8, U57>;
170
171    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
172        AffinePoint::from_bytes(bytes).map(|point| point.to_edwards())
173    }
174
175    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
176        // No unchecked conversion possible for compressed points
177        Self::from_bytes(bytes)
178    }
179
180    fn to_bytes(&self) -> Self::Repr {
181        self.to_affine().to_bytes()
182    }
183}
184
185impl CofactorGroup for EdwardsPoint {
186    type Subgroup = EdwardsPoint;
187
188    fn clear_cofactor(&self) -> Self::Subgroup {
189        self.double().double()
190    }
191
192    fn into_subgroup(self) -> CtOption<Self::Subgroup> {
193        CtOption::new(self.clear_cofactor(), self.is_torsion_free())
194    }
195
196    fn is_torsion_free(&self) -> Choice {
197        self.is_torsion_free()
198    }
199}
200
201impl PrimeGroup for EdwardsPoint {}
202
203#[cfg(feature = "alloc")]
204impl From<EdwardsPoint> for Vec<u8> {
205    fn from(value: EdwardsPoint) -> Self {
206        Self::from(&value)
207    }
208}
209
210#[cfg(feature = "alloc")]
211impl From<&EdwardsPoint> for Vec<u8> {
212    fn from(value: &EdwardsPoint) -> Self {
213        value.to_affine().compress().0.to_vec()
214    }
215}
216
217#[cfg(feature = "alloc")]
218impl TryFrom<Vec<u8>> for EdwardsPoint {
219    type Error = &'static str;
220
221    fn try_from(value: Vec<u8>) -> Result<Self, Self::Error> {
222        Self::try_from(&value)
223    }
224}
225
226#[cfg(feature = "alloc")]
227impl TryFrom<&Vec<u8>> for EdwardsPoint {
228    type Error = &'static str;
229
230    fn try_from(value: &Vec<u8>) -> Result<Self, Self::Error> {
231        Self::try_from(value.as_slice())
232    }
233}
234
235impl TryFrom<&[u8]> for EdwardsPoint {
236    type Error = &'static str;
237
238    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
239        let bytes =
240            <PointBytes>::try_from(value).map_err(|_| "Invalid length, expected 57 bytes")?;
241        Self::try_from(bytes)
242    }
243}
244
245#[cfg(feature = "alloc")]
246impl TryFrom<Box<[u8]>> for EdwardsPoint {
247    type Error = &'static str;
248
249    fn try_from(value: Box<[u8]>) -> Result<Self, Self::Error> {
250        Self::try_from(value.as_ref())
251    }
252}
253
254impl TryFrom<PointBytes> for EdwardsPoint {
255    type Error = &'static str;
256
257    fn try_from(value: PointBytes) -> Result<Self, Self::Error> {
258        CompressedEdwardsY(value)
259            .decompress()
260            .into_option()
261            .map(|point| point.to_edwards())
262            .ok_or("Invalid point")
263    }
264}
265
266impl TryFrom<&PointBytes> for EdwardsPoint {
267    type Error = &'static str;
268
269    fn try_from(value: &PointBytes) -> Result<Self, Self::Error> {
270        Self::try_from(*value)
271    }
272}
273
274impl From<EdwardsPoint> for PointBytes {
275    fn from(value: EdwardsPoint) -> Self {
276        value.to_affine().compress().into()
277    }
278}
279
280impl From<&EdwardsPoint> for PointBytes {
281    fn from(value: &EdwardsPoint) -> Self {
282        Self::from(*value)
283    }
284}
285
286impl From<EdwardsPoint> for AffinePoint {
287    fn from(value: EdwardsPoint) -> Self {
288        value.to_affine()
289    }
290}
291
292impl From<&AffinePoint> for EdwardsPoint {
293    fn from(value: &AffinePoint) -> Self {
294        value.to_edwards()
295    }
296}
297
298impl From<AffinePoint> for EdwardsPoint {
299    fn from(value: AffinePoint) -> Self {
300        value.to_edwards()
301    }
302}
303
304impl From<&EdwardsPoint> for AffinePoint {
305    fn from(value: &EdwardsPoint) -> Self {
306        value.to_affine()
307    }
308}
309
310impl<const N: usize> LinearCombination<[(EdwardsPoint, EdwardsScalar); N]> for EdwardsPoint {}
311
312impl LinearCombination<[(EdwardsPoint, EdwardsScalar)]> for EdwardsPoint {}
313
314impl CurveGroup for EdwardsPoint {
315    type Affine = AffinePoint;
316
317    fn to_affine(&self) -> AffinePoint {
318        self.to_affine()
319    }
320
321    #[cfg(feature = "alloc")]
322    #[inline]
323    fn batch_normalize(projective: &[Self], affine: &mut [Self::Affine]) {
324        assert_eq!(projective.len(), affine.len());
325        let mut zs = vec![FieldElement::ZERO; projective.len()];
326        let mut scratch = vec![FieldElement::ZERO; projective.len()];
327        batch_normalize_generic(projective, &mut zs, &mut scratch, affine);
328    }
329}
330
331impl EdwardsPoint {
332    /// Generator for the prime subgroup
333    pub const GENERATOR: Self = GOLDILOCKS_BASE_POINT;
334    /// Identity point
335    pub const IDENTITY: Self = Self {
336        X: FieldElement::ZERO,
337        Y: FieldElement::ONE,
338        Z: FieldElement::ONE,
339        T: FieldElement::ZERO,
340    };
341
342    /// Convert this point to [`MontgomeryPoint`]
343    pub fn to_montgomery(&self) -> MontgomeryPoint {
344        // u = y^2 * [(1-dy^2)/(1-y^2)]
345
346        let affine = self.to_affine();
347
348        let yy = affine.y.square();
349        let dyy = FieldElement::EDWARDS_D * yy;
350
351        let u = yy * (FieldElement::ONE - dyy) * (FieldElement::ONE - yy).invert();
352
353        MontgomeryPoint(u.to_bytes())
354    }
355
356    /// Generic scalar multiplication to compute s*P
357    pub fn scalar_mul(&self, scalar: &EdwardsScalar) -> Self {
358        // Compute floor(s/4)
359        let scalar_div_four = scalar.div_by_2().div_by_2();
360
361        // Use isogeny and dual isogeny to compute phi^-1((s/4) * phi(P))
362        variable_base(&self.to_twisted().to_extended(), &scalar_div_four)
363            .to_extended()
364            .to_untwisted()
365    }
366
367    /// Add two points
368    //https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf (3.1)
369    // These formulas are unified, so for now we can use it for doubling. Will refactor later for speed
370    pub fn add(&self, other: &EdwardsPoint) -> Self {
371        let aXX = self.X * other.X; // aX1X2
372        let dTT = FieldElement::EDWARDS_D * self.T * other.T; // dT1T2
373        let ZZ = self.Z * other.Z; // Z1Z2
374        let YY = self.Y * other.Y;
375
376        let X = {
377            let x_1 = (self.X * other.Y) + (self.Y * other.X);
378            let x_2 = ZZ - dTT;
379            x_1 * x_2
380        };
381        let Y = {
382            let y_1 = YY - aXX;
383            let y_2 = ZZ + dTT;
384            y_1 * y_2
385        };
386
387        let T = {
388            let t_1 = YY - aXX;
389            let t_2 = (self.X * other.Y) + (self.Y * other.X);
390            t_1 * t_2
391        };
392
393        let Z = { (ZZ - dTT) * (ZZ + dTT) };
394
395        EdwardsPoint { X, Y, Z, T }
396    }
397
398    /// Double this point
399    // XXX: See comment on addition, the formula is unified, so this will do for now
400    //https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf (3.1)
401    pub fn double(&self) -> Self {
402        self.add(self)
403    }
404
405    /// Check if this point is on the curve
406    pub fn is_on_curve(&self) -> Choice {
407        let XY = self.X * self.Y;
408        let ZT = self.Z * self.T;
409
410        // Y^2 + X^2 == Z^2 - T^2 * D
411
412        let YY = self.Y.square();
413        let XX = self.X.square();
414        let ZZ = self.Z.square();
415        let TT = self.T.square();
416        let lhs = YY + XX;
417        let rhs = ZZ + TT * FieldElement::EDWARDS_D;
418
419        XY.ct_eq(&ZT) & lhs.ct_eq(&rhs)
420    }
421
422    /// Convert this point to an [`AffinePoint`].
423    pub fn to_affine(&self) -> AffinePoint {
424        let INV_Z = self.Z.invert();
425
426        let x = self.X * INV_Z;
427        let y = self.Y * INV_Z;
428
429        AffinePoint { x, y }
430    }
431
432    pub(crate) fn to_twisted(self) -> TwistedExtensiblePoint {
433        let IsogenyMapResult { X, Y, Z, T1, T2 } = IsogenyMap {
434            X: self.X,
435            Y: self.Y,
436            Z: self.Z,
437            T: self.T,
438        }
439        .map(|f| f);
440
441        TwistedExtensiblePoint { X, Y, Z, T1, T2 }
442    }
443
444    /// Compute the negation of this point's `x`-coordinate.
445    pub fn negate(&self) -> Self {
446        EdwardsPoint {
447            X: -self.X,
448            Y: self.Y,
449            Z: self.Z,
450            T: -self.T,
451        }
452    }
453
454    /// Compute the negation of this point's `y`-coordinate.
455    pub fn torque(&self) -> Self {
456        EdwardsPoint {
457            X: -self.X,
458            Y: -self.Y,
459            Z: self.Z,
460            T: self.T,
461        }
462    }
463
464    /// Determine if this point is “torsion-free”, i.e., is contained in
465    /// the prime-order subgroup.
466    ///
467    /// # Return
468    ///
469    /// * `true` if `self` has zero torsion component and is in the
470    ///   prime-order subgroup;
471    /// * `false` if `self` has a nonzero torsion component and is not
472    ///   in the prime-order subgroup.
473    // See https://eprint.iacr.org/2022/1164.
474    pub fn is_torsion_free(&self) -> Choice {
475        const A: FieldElement = FieldElement(ConstMontyType::new(&U448::from_be_hex(
476            "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffffffffffffffffffffffffffffffffffffffffffffffffeceaf",
477        )));
478        const A1: FieldElement = FieldElement(ConstMontyType::new(&U448::from_u64(156320)));
479        const MINUS_SQRT_B1: FieldElement = FieldElement(ConstMontyType::new(&U448::from_be_hex(
480            "749a7410536c225f1025ca374176557d7839611d691caad26d74a1fca5cfad15f196642c0a4484b67f321025577cc6b5a6f443c2eaa36327",
481        )));
482
483        let mut e = self.X * (self.Z - self.Y);
484        let ee = e.square();
485        let mut u = FieldElement::A_PLUS_TWO_OVER_FOUR * (self.Z + self.Y) * e * self.X;
486        let w = self.Z.double() * (self.Z - self.Y);
487
488        let u2 = u.double().double();
489        let w2 = w.double();
490
491        let mut w1 = u2.unchecked_sqrt();
492        let mut ok = w1.square().ct_eq(&u2);
493        let u1 = (u2 - A1 * ee - w1 * w2).div_by_2();
494
495        // If `u1` happens not to be a square, then `sqrt(u1)` returns `sqrt(-u1)`
496        // in that case (since we are in a finite field GF(q) with q = 3 mod 4,
497        // if `u1` is not a square then `-u1` must be a square). In such a case, we
498        // should replace `(u1,w1)` with `((B1*e^4)/u1, -w1)`. To avoid the division,
499        // we instead switch to an isomorphic curve; namely:
500        //   u2 = B1*(e^4)*u1
501        //   w2 = -w1*u1
502        //   e2 = e*u1
503        // Then:
504        //   w = sqrt(u2) = sqrt(-B1)*(e^2)*sqrt(-u1)
505        //   u = (w^2 - A*e^2 - w*w1)/2
506        let mut w = u1.unchecked_sqrt();
507        let u1_is_square = w.square().ct_eq(&u1);
508        w1.conditional_assign(&-(w1 * u1), !u1_is_square);
509        e.conditional_assign(&(e * u1), !u1_is_square);
510        w.conditional_assign(&(MINUS_SQRT_B1 * ee * w), !u1_is_square);
511        u = (w.square() - A * e.square() - w * w1).div_by_2();
512
513        ok &= u.is_square();
514
515        // If the source point was a low-order point, then the computations
516        // above are incorrect. We handle this case here; among the
517        // low-order points, only the neutral point is in the prime-order
518        // subgroup.
519        let is_low_order = self.X.is_zero() | self.Y.is_zero();
520        let is_neutral = self.Y.ct_eq(&self.Z);
521        ok ^= is_low_order & (ok ^ is_neutral);
522
523        ok
524    }
525}
526
527impl From<NonIdentity<EdwardsPoint>> for EdwardsPoint {
528    fn from(p: NonIdentity<EdwardsPoint>) -> Self {
529        p.to_point()
530    }
531}
532
533/// The constant-time alternative is available at [`NonIdentity::new()`].
534impl TryFrom<EdwardsPoint> for NonIdentity<EdwardsPoint> {
535    type Error = Error;
536
537    fn try_from(point: EdwardsPoint) -> Result<Self, Error> {
538        NonIdentity::new(point).into_option().ok_or(Error)
539    }
540}
541
542// ------------------------------------------------------------------------
543// Addition and Subtraction
544// ------------------------------------------------------------------------
545
546impl Add<&EdwardsPoint> for &EdwardsPoint {
547    type Output = EdwardsPoint;
548
549    fn add(self, other: &EdwardsPoint) -> EdwardsPoint {
550        self.add(other)
551    }
552}
553
554define_add_variants!(
555    LHS = EdwardsPoint,
556    RHS = EdwardsPoint,
557    Output = EdwardsPoint
558);
559
560define_add_variants!(LHS = EdwardsPoint, RHS = AffinePoint, Output = EdwardsPoint);
561
562define_add_variants!(LHS = AffinePoint, RHS = EdwardsPoint, Output = EdwardsPoint);
563
564impl Add<&AffinePoint> for &EdwardsPoint {
565    type Output = EdwardsPoint;
566
567    fn add(self, other: &AffinePoint) -> EdwardsPoint {
568        *self + *other
569    }
570}
571
572impl Add<&EdwardsPoint> for &AffinePoint {
573    type Output = EdwardsPoint;
574
575    fn add(self, other: &EdwardsPoint) -> EdwardsPoint {
576        *other + *self
577    }
578}
579
580impl<'b> AddAssign<&'b EdwardsPoint> for EdwardsPoint {
581    fn add_assign(&mut self, _rhs: &'b EdwardsPoint) {
582        *self = *self + _rhs;
583    }
584}
585
586define_add_assign_variants!(LHS = EdwardsPoint, RHS = EdwardsPoint);
587
588impl AddAssign<&AffinePoint> for EdwardsPoint {
589    fn add_assign(&mut self, rhs: &AffinePoint) {
590        *self += rhs.to_edwards();
591    }
592}
593
594define_add_assign_variants!(LHS = EdwardsPoint, RHS = AffinePoint);
595
596impl AddAssign<&EdwardsPoint> for AffinePoint {
597    fn add_assign(&mut self, rhs: &EdwardsPoint) {
598        *self = (self.to_edwards() + rhs).to_affine();
599    }
600}
601
602define_add_assign_variants!(LHS = AffinePoint, RHS = EdwardsPoint);
603
604impl Sub<&EdwardsPoint> for &EdwardsPoint {
605    type Output = EdwardsPoint;
606
607    fn sub(self, other: &EdwardsPoint) -> EdwardsPoint {
608        self.add(&other.negate())
609    }
610}
611
612define_sub_variants!(
613    LHS = EdwardsPoint,
614    RHS = EdwardsPoint,
615    Output = EdwardsPoint
616);
617
618impl Sub<&AffinePoint> for &EdwardsPoint {
619    type Output = EdwardsPoint;
620
621    fn sub(self, other: &AffinePoint) -> EdwardsPoint {
622        *self - other.to_edwards()
623    }
624}
625
626define_sub_variants!(LHS = EdwardsPoint, RHS = AffinePoint, Output = EdwardsPoint);
627
628impl Sub<&EdwardsPoint> for &AffinePoint {
629    type Output = EdwardsPoint;
630
631    fn sub(self, other: &EdwardsPoint) -> EdwardsPoint {
632        *self - other
633    }
634}
635
636define_sub_variants!(LHS = AffinePoint, RHS = EdwardsPoint, Output = EdwardsPoint);
637
638impl<'b> SubAssign<&'b EdwardsPoint> for EdwardsPoint {
639    fn sub_assign(&mut self, _rhs: &'b EdwardsPoint) {
640        *self = *self - _rhs;
641    }
642}
643
644define_sub_assign_variants!(LHS = EdwardsPoint, RHS = EdwardsPoint);
645
646impl SubAssign<&AffinePoint> for EdwardsPoint {
647    fn sub_assign(&mut self, rhs: &AffinePoint) {
648        *self -= rhs.to_edwards();
649    }
650}
651
652define_sub_assign_variants!(LHS = EdwardsPoint, RHS = AffinePoint);
653
654impl SubAssign<&EdwardsPoint> for AffinePoint {
655    fn sub_assign(&mut self, rhs: &EdwardsPoint) {
656        *self = (self.to_edwards() - rhs).to_affine();
657    }
658}
659
660define_sub_assign_variants!(LHS = AffinePoint, RHS = EdwardsPoint);
661
662impl<T> Sum<T> for EdwardsPoint
663where
664    T: Borrow<EdwardsPoint>,
665{
666    fn sum<I>(iter: I) -> Self
667    where
668        I: Iterator<Item = T>,
669    {
670        iter.fold(Self::IDENTITY, |acc, item| acc + item.borrow())
671    }
672}
673
674// ------------------------------------------------------------------------
675// Negation
676// ------------------------------------------------------------------------
677
678impl Neg for &EdwardsPoint {
679    type Output = EdwardsPoint;
680
681    fn neg(self) -> EdwardsPoint {
682        self.negate()
683    }
684}
685
686impl Neg for EdwardsPoint {
687    type Output = EdwardsPoint;
688
689    fn neg(self) -> EdwardsPoint {
690        -&self
691    }
692}
693
694// ------------------------------------------------------------------------
695// Scalar multiplication
696// ------------------------------------------------------------------------
697
698impl<'b> MulAssign<&'b EdwardsScalar> for EdwardsPoint {
699    fn mul_assign(&mut self, scalar: &'b EdwardsScalar) {
700        let result = *self * scalar;
701        *self = result;
702    }
703}
704
705define_mul_assign_variants!(LHS = EdwardsPoint, RHS = EdwardsScalar);
706
707define_mul_variants!(
708    LHS = EdwardsPoint,
709    RHS = EdwardsScalar,
710    Output = EdwardsPoint
711);
712
713impl Mul<&EdwardsScalar> for &EdwardsPoint {
714    type Output = EdwardsPoint;
715
716    /// Scalar multiplication: compute `scalar * self`.
717    fn mul(self, scalar: &EdwardsScalar) -> EdwardsPoint {
718        self.scalar_mul(scalar)
719    }
720}
721
722impl MulVartime<EdwardsScalar> for EdwardsPoint {
723    fn mul_vartime(self, scalar: EdwardsScalar) -> EdwardsPoint {
724        self.mul_vartime(&scalar)
725    }
726}
727
728impl MulVartime<&EdwardsScalar> for EdwardsPoint {
729    fn mul_vartime(self, scalar: &EdwardsScalar) -> EdwardsPoint {
730        MulVartime::mul_vartime(&self, scalar)
731    }
732}
733
734impl MulVartime<&EdwardsScalar> for &EdwardsPoint {
735    fn mul_vartime(self, scalar: &EdwardsScalar) -> EdwardsPoint {
736        // TODO(tarcieri): optimized vartime implementation
737        self.scalar_mul(scalar)
738    }
739}
740
741impl MulByGeneratorVartime for EdwardsPoint {}
742
743#[cfg(feature = "serde")]
744impl serdect::serde::Serialize for EdwardsPoint {
745    fn serialize<S: serdect::serde::Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
746        self.to_affine().compress().serialize(s)
747    }
748}
749
750#[cfg(feature = "serde")]
751impl<'de> serdect::serde::Deserialize<'de> for EdwardsPoint {
752    fn deserialize<D>(d: D) -> Result<Self, D::Error>
753    where
754        D: serdect::serde::Deserializer<'de>,
755    {
756        let compressed = CompressedEdwardsY::deserialize(d)?;
757        compressed
758            .decompress()
759            .into_option()
760            .map(|point| point.to_edwards())
761            .ok_or_else(|| serdect::serde::de::Error::custom("invalid point"))
762    }
763}
764
765impl elliptic_curve::zeroize::DefaultIsZeroes for EdwardsPoint {}
766
767impl<const N: usize> BatchNormalize<[EdwardsPoint; N]> for EdwardsPoint {
768    type Output = [<Self as CurveGroup>::Affine; N];
769
770    #[inline]
771    fn batch_normalize(points: &[Self; N]) -> [<Self as CurveGroup>::Affine; N] {
772        let mut zs = [FieldElement::ZERO; N];
773        let mut scratch = [FieldElement::ZERO; N];
774        let mut affine_points = [AffinePoint::IDENTITY; N];
775        batch_normalize_generic(points, &mut zs, &mut scratch, &mut affine_points);
776        affine_points
777    }
778}
779
780#[cfg(feature = "alloc")]
781impl BatchNormalize<[EdwardsPoint]> for EdwardsPoint {
782    type Output = Vec<<Self as CurveGroup>::Affine>;
783
784    #[inline]
785    fn batch_normalize(points: &[Self]) -> Vec<<Self as CurveGroup>::Affine> {
786        use alloc::vec;
787
788        let mut zs = vec![FieldElement::ZERO; points.len()];
789        let mut scratch = vec![FieldElement::ZERO; points.len()];
790        let mut affine_points = vec![AffinePoint::IDENTITY; points.len()];
791        batch_normalize_generic(points, &mut zs, &mut scratch, &mut affine_points);
792        affine_points
793    }
794}
795
796fn batch_normalize_generic(
797    points: &[EdwardsPoint],
798    zs: &mut [FieldElement],
799    scratch: &mut [FieldElement],
800    out: &mut [AffinePoint],
801) {
802    debug_assert_eq!(points.len(), zs.len());
803    debug_assert_eq!(points.len(), scratch.len());
804    debug_assert_eq!(points.len(), out.len());
805
806    for (z, point) in zs.iter_mut().zip(points) {
807        *z = point.Z;
808    }
809
810    // Zero `zs` (identity) are handled explicitly below, so the `Choice` here is informational only
811    let _ = FieldElement::batch_invert_in_place(zs, scratch);
812
813    for i in 0..out.len() {
814        out[i] = AffinePoint::conditional_select(
815            &AffinePoint {
816                x: points[i].X * zs[i],
817                y: points[i].Y * zs[i],
818            },
819            &AffinePoint::IDENTITY,
820            points[i].Z.ct_eq(&FieldElement::ZERO),
821        );
822    }
823}
824
825#[cfg(test)]
826mod tests {
827    use super::*;
828    use crate::Ed448;
829    use elliptic_curve::Field;
830    use hash2curve::{ExpandMsgXof, GroupDigest};
831    use hex_literal::hex;
832    use proptest::{prop_assert_eq, property_test};
833
834    #[cfg(feature = "getrandom")]
835    use elliptic_curve::common::getrandom::SysRng;
836
837    fn hex_to_field(hex: &'static str) -> FieldElement {
838        assert_eq!(hex.len(), 56 * 2);
839        let mut bytes =
840            hex_literal::decode(&[hex.as_bytes()]).expect("Output array length should be correct");
841        bytes.reverse();
842        FieldElement::from_bytes(&bytes)
843    }
844
845    #[test]
846    fn test_isogeny() {
847        let x = hex_to_field(
848            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555",
849        );
850        let y = hex_to_field(
851            "ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed",
852        );
853        let a = AffinePoint { x, y }.to_edwards();
854        let twist_a = a.to_twisted().to_extended().to_untwisted();
855        assert!(twist_a == a.double().double())
856    }
857
858    // XXX: Move this to constants folder to test all global constants
859    #[test]
860    fn derive_base_points() {
861        use crate::{GOLDILOCKS_BASE_POINT, TWISTED_EDWARDS_BASE_POINT};
862
863        // This was the original basepoint which had order 2q;
864        let old_x = hex_to_field(
865            "4F1970C66BED0DED221D15A622BF36DA9E146570470F1767EA6DE324A3D3A46412AE1AF72AB66511433B80E18B00938E2626A82BC70CC05E",
866        );
867        let old_y = hex_to_field(
868            "693F46716EB6BC248876203756C9C7624BEA73736CA3984087789C1E05A0C2D73AD3FF1CE67C39C4FDBD132C4ED7C8AD9808795BF230FA14",
869        );
870        let old_bp = AffinePoint { x: old_x, y: old_y }.to_edwards();
871
872        // This is the new basepoint, that is in the ed448 paper
873        let new_x = hex_to_field(
874            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555",
875        );
876        let new_y = hex_to_field(
877            "ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed",
878        );
879        let new_bp = AffinePoint { x: new_x, y: new_y }.to_edwards();
880
881        // Doubling the old basepoint, should give us the new basepoint
882        assert_eq!(old_bp.double(), new_bp);
883
884        // XXX: Unfortunately, the test vectors in libdecaf currently use the old basepoint.
885        // We need to update this. But for now, I use the old basepoint so that I can check against libdecaf
886
887        assert_eq!(GOLDILOCKS_BASE_POINT, old_bp);
888
889        // The Twisted basepoint can be derived by using the isogeny
890        assert_eq!(old_bp.to_twisted(), TWISTED_EDWARDS_BASE_POINT)
891    }
892
893    #[test]
894    fn test_is_on_curve() {
895        let x = hex_to_field(
896            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555",
897        );
898        let y = hex_to_field(
899            "ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed",
900        );
901        let generated = AffinePoint { x, y }.to_edwards();
902        assert_eq!(generated.is_on_curve().unwrap_u8(), 1u8);
903    }
904    #[test]
905    fn test_compress_decompress() {
906        let x = hex_to_field(
907            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa955555555555555555555555555555555555555555555555555555555",
908        );
909        let y = hex_to_field(
910            "ae05e9634ad7048db359d6205086c2b0036ed7a035884dd7b7e36d728ad8c4b80d6565833a2a3098bbbcb2bed1cda06bdaeafbcdea9386ed",
911        );
912        let generated = AffinePoint { x, y };
913
914        let decompressed_point = generated.compress().decompress();
915        assert!(<Choice as Into<bool>>::into(decompressed_point.is_some()));
916
917        assert!(generated == decompressed_point.unwrap());
918    }
919    #[test]
920    fn test_decompress_compress() {
921        let bytes = hex!(
922            "649c6a53b109897d962d033f23d01fd4e1053dddf3746d2ddce9bd66aea38ccfc3df061df03ca399eb806312ab3037c0c31523142956ada780"
923        );
924        let compressed = CompressedEdwardsY(bytes);
925        let decompressed = compressed.decompress().unwrap();
926
927        let recompressed = decompressed.compress();
928
929        assert_eq!(bytes, recompressed.0);
930    }
931    #[test]
932    fn test_just_decompress() {
933        let bytes = hex!(
934            "649c6a53b109897d962d033f23d01fd4e1053dddf3746d2ddce9bd66aea38ccfc3df061df03ca399eb806312ab3037c0c31523142956ada780"
935        );
936        let compressed = CompressedEdwardsY(bytes);
937        let decompressed = compressed.decompress().unwrap();
938
939        assert_eq!(
940            decompressed.x,
941            hex_to_field(
942                "39c41cea305d737df00de8223a0d5f4d48c8e098e16e9b4b2f38ac353262e119cb5ff2afd6d02464702d9d01c9921243fc572f9c718e2527"
943            )
944        );
945        assert_eq!(
946            decompressed.y,
947            hex_to_field(
948                "a7ad5629142315c3c03730ab126380eb99a33cf01d06dfc3cf8ca3ae66bde9dc2d6d74f3dd3d05e1d41fd0233f032d967d8909b1536a9c64"
949            )
950        );
951
952        let bytes = hex!(
953            "010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
954        );
955        let compressed = CompressedEdwardsY(bytes);
956        let decompressed = compressed.decompress().unwrap();
957
958        assert_eq!(
959            decompressed.x,
960            hex_to_field(
961                "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
962            )
963        );
964        assert_eq!(
965            decompressed.y,
966            hex_to_field(
967                "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001"
968            )
969        );
970    }
971    #[test]
972    fn test_is_torsion_free() {
973        assert_eq!(EdwardsPoint::GENERATOR.is_torsion_free().unwrap_u8(), 1u8);
974        assert_eq!(EdwardsPoint::IDENTITY.is_torsion_free().unwrap_u8(), 1u8);
975
976        let bytes = hex!(
977            "13b6714c7a5f53101bbec88f2f17cd30f42e37fae363a5474efb4197ed6005df5861ae178a0c2c16ad378b7befed0d0904b7ced35e9f674180"
978        );
979        let compressed = CompressedEdwardsY(bytes);
980        let decompressed = compressed.decompress();
981        assert_eq!(decompressed.is_none().unwrap_u8(), 1u8);
982    }
983
984    #[test]
985    fn hash_with_test_vectors() {
986        const DST: &[u8] = b"QUUX-V01-CS02-with-edwards448_XOF:SHAKE256_ELL2_RO_";
987        const MSGS: &[(&[u8], [u8; 56], [u8; 56])] = &[
988            (b"", hex!("73036d4a88949c032f01507005c133884e2f0d81f9a950826245dda9e844fc78186c39daaa7147ead3e462cff60e9c6340b58134480b4d17"), hex!("94c1d61b43728e5d784ef4fcb1f38e1075f3aef5e99866911de5a234f1aafdc26b554344742e6ba0420b71b298671bbeb2b7736618634610")),
989            (b"abc", hex!("4e0158acacffa545adb818a6ed8e0b870e6abc24dfc1dc45cf9a052e98469275d9ff0c168d6a5ac7ec05b742412ee090581f12aa398f9f8c"), hex!("894d3fa437b2d2e28cdc3bfaade035430f350ec5239b6b406b5501da6f6d6210ff26719cad83b63e97ab26a12df6dec851d6bf38e294af9a")),
990            (b"abcdef0123456789", hex!("2c25b4503fadc94b27391933b557abdecc601c13ed51c5de68389484f93dbd6c22e5f962d9babf7a39f39f994312f8ca23344847e1fbf176"), hex!("d5e6f5350f430e53a110f5ac7fcc82a96cb865aeca982029522d32601e41c042a9dfbdfbefa2b0bdcdc3bc58cca8a7cd546803083d3a8548")),
991            (b"q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq", hex!("a1861a9464ae31249a0e60bf38791f3663049a3f5378998499a83292e159a2fecff838eb9bc6939e5c6ae76eb074ad4aae39b55b72ca0b9a"), hex!("580a2798c5b904f8adfec5bd29fb49b4633cd9f8c2935eb4a0f12e5dfa0285680880296bb729c6405337525fb5ed3dff930c137314f60401")),
992            (b"a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", hex!("987c5ac19dd4b47835466a50b2d9feba7c8491b8885a04edf577e15a9f2c98b203ec2cd3e5390b3d20bba0fa6fc3eecefb5029a317234401"), hex!("5e273fcfff6b007bb6771e90509275a71ff1480c459ded26fc7b10664db0a68aaa98bc7ecb07e49cf05b80ae5ac653fbdd14276bbd35ccbc")),
993        ];
994
995        for (msg, x, y) in MSGS {
996            let p =
997                hash2curve::hash_from_bytes::<Ed448, ExpandMsgXof<shake::Shake256>>(&[msg], &[DST])
998                    .unwrap();
999            assert_eq!(p.is_on_curve().unwrap_u8(), 1u8);
1000            let p = p.to_affine();
1001            let mut xx = [0u8; 56];
1002            xx.copy_from_slice(&x[..]);
1003            xx.reverse();
1004            let mut yy = [0u8; 56];
1005            yy.copy_from_slice(&y[..]);
1006            yy.reverse();
1007            assert_eq!(p.x.to_bytes(), xx);
1008            assert_eq!(p.y.to_bytes(), yy);
1009        }
1010    }
1011
1012    #[test]
1013    #[cfg(feature = "getrandom")]
1014    fn hash_fuzzing() {
1015        for _ in 0..25 {
1016            let mut msg = [0u8; 64];
1017            SysRng.try_fill_bytes(&mut msg).unwrap();
1018            let p = Ed448::hash_from_bytes(&[&msg], &[b"test DST"]).unwrap();
1019            assert_eq!(p.is_on_curve().unwrap_u8(), 1u8);
1020            assert_eq!(p.is_torsion_free().unwrap_u8(), 1u8);
1021        }
1022    }
1023
1024    #[test]
1025    fn encode() {
1026        const DST: &[u8] = b"QUUX-V01-CS02-with-edwards448_XOF:SHAKE256_ELL2_NU_";
1027        const MSGS: &[(&[u8], [u8; 56], [u8; 56])] = &[
1028            (b"", hex!("eb5a1fc376fd73230af2de0f3374087cc7f279f0460114cf0a6c12d6d044c16de34ec2350c34b26bf110377655ab77936869d085406af71e"), hex!("df5dcea6d42e8f494b279a500d09e895d26ac703d75ca6d118e8ca58bf6f608a2a383f292fce1563ff995dce75aede1fdc8e7c0c737ae9ad")),
1029            (b"abc", hex!("4623a64bceaba3202df76cd8b6e3daf70164f3fcbda6d6e340f7fab5cdf89140d955f722524f5fe4d968fef6ba2853ff4ea086c2f67d8110"), hex!("abaac321a169761a8802ab5b5d10061fec1a83c670ac6bc95954700317ee5f82870120e0e2c5a21b12a0c7ad17ebd343363604c4bcecafd1")),
1030            (b"abcdef0123456789", hex!("e9eb562e76db093baa43a31b7edd04ec4aadcef3389a7b9c58a19cf87f8ae3d154e134b6b3ed45847a741e33df51903da681629a4b8bcc2e"), hex!("0cf6606927ad7eb15dbc193993bc7e4dda744b311a8ec4274c8f738f74f605934582474c79260f60280fe35bd37d4347e59184cbfa12cbc4")),
1031            (b"q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq", hex!("122a3234d34b26c69749f23356452bf9501efa2d94859d5ef741fef024156d9d191a03a2ad24c38186f93e02d05572575968b083d8a39738"), hex!("ddf55e74eb4414c2c1fa4aa6bc37c4ab470a3fed6bb5af1e43570309b162fb61879bb15f9ea49c712efd42d0a71666430f9f0d4a20505050")),
1032            (b"a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", hex!("221704949b1ce1ab8dd174dc9b8c56fcffa27179569ce9219c0c2fe183d3d23343a4c42a0e2e9d6b9d0feb1df3883ec489b6671d1fa64089"), hex!("ebdecfdc87142d1a919034bf22ecfad934c9a85effff14b594ae2c00943ca62a39d6ee3be9df0bb504ce8a9e1669bc6959c42ad6a1d3b686")),
1033        ];
1034
1035        for (msg, x, y) in MSGS {
1036            let p = hash2curve::encode_from_bytes::<Ed448, ExpandMsgXof<shake::Shake256>>(
1037                &[msg],
1038                &[DST],
1039            )
1040            .unwrap();
1041            assert_eq!(p.is_on_curve().unwrap_u8(), 1u8);
1042            let p = p.to_affine();
1043            let mut xx = [0u8; 56];
1044            xx.copy_from_slice(&x[..]);
1045            xx.reverse();
1046            let mut yy = [0u8; 56];
1047            yy.copy_from_slice(&y[..]);
1048            yy.reverse();
1049            assert_eq!(p.x.to_bytes(), xx);
1050            assert_eq!(p.y.to_bytes(), yy);
1051        }
1052    }
1053
1054    // TODO: uncomment once elliptic-curve-tools is updated to match elliptic-curve 0.14
1055    // #[test]
1056    // fn test_sum_of_products() {
1057    //     use elliptic_curve_tools::SumOfProducts;
1058    //     let values = [
1059    //         (Scalar::from(8u8), EdwardsPoint::GENERATOR),
1060    //         (Scalar::from(9u8), EdwardsPoint::GENERATOR),
1061    //         (Scalar::from(10u8), EdwardsPoint::GENERATOR),
1062    //         (Scalar::from(11u8), EdwardsPoint::GENERATOR),
1063    //         (Scalar::from(12u8), EdwardsPoint::GENERATOR),
1064    //     ];
1065    //
1066    //     let expected = EdwardsPoint::GENERATOR * Scalar::from(50u8);
1067    //     let result = EdwardsPoint::sum_of_products(&values);
1068    //     assert_eq!(result, expected);
1069    // }
1070    //
1071    // #[test]
1072    // fn test_sum_of_products2() {
1073    //     use elliptic_curve_tools::SumOfProducts;
1074    //     use rand_core::SeedableRng;
1075    //
1076    //     const TESTS: usize = 5;
1077    //     const CHUNKS: usize = 10;
1078    //     let mut rng = chacha20::ChaCha8Rng::from_seed([3u8; 32]);
1079    //
1080    //     for _ in 0..TESTS {
1081    //         let scalars = (0..CHUNKS)
1082    //             .map(|_| Scalar::random(&mut rng))
1083    //             .collect::<Vec<_>>();
1084    //         let points = (0..CHUNKS)
1085    //             .map(|_| EdwardsPoint::random(&mut rng))
1086    //             .collect::<Vec<_>>();
1087    //
1088    //         let input = scalars
1089    //             .iter()
1090    //             .zip(points.iter())
1091    //             .map(|(&s, &p)| (s, p))
1092    //             .collect::<Vec<_>>();
1093    //         let rhs = EdwardsPoint::sum_of_products(&input);
1094    //
1095    //         let expected = points
1096    //             .iter()
1097    //             .zip(scalars.iter())
1098    //             .fold(EdwardsPoint::IDENTITY, |acc, (&p, &s)| acc + (p * s));
1099    //
1100    //         assert_eq!(rhs, expected);
1101    //     }
1102    // }
1103
1104    #[test]
1105    fn test_pow_add_mul() {
1106        use rand_core::SeedableRng;
1107
1108        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(0);
1109        let x = EdwardsScalar::random(&mut rng);
1110        let b = EdwardsScalar::random(&mut rng);
1111
1112        let g1 = EdwardsPoint::GENERATOR;
1113        let g2 = Ed448::hash_from_bytes(&[b"test_pow_add_mul"], &[b"test DST"]).unwrap();
1114
1115        let expected_commitment = g1 * x + g2 * b;
1116
1117        let shift = EdwardsScalar::from(256u16);
1118        let x_bytes = x.to_bytes_rfc_8032();
1119        let mut sum = EdwardsScalar::ZERO;
1120        let mut components = [EdwardsPoint::IDENTITY; 57];
1121        for i in 1..57 {
1122            let r = EdwardsScalar::random(&mut rng);
1123            sum += r * shift.pow([i as u64]);
1124            components[i] = g1 * EdwardsScalar::from(x_bytes[i]) + g2 * r;
1125        }
1126        components[0] = g1 * EdwardsScalar::from(x_bytes[0]) + g2 * (b - sum);
1127
1128        let mut computed_commitment = EdwardsPoint::IDENTITY;
1129        for i in (0..57).rev() {
1130            computed_commitment *= shift;
1131            computed_commitment += components[i];
1132        }
1133
1134        assert_eq!(computed_commitment, expected_commitment);
1135    }
1136
1137    // TODO(tarcieri): use proptest
1138    #[test]
1139    #[cfg(feature = "getrandom")]
1140    fn batch_normalize() {
1141        let points: [EdwardsPoint; 2] = [EdwardsPoint::generate(), EdwardsPoint::generate()];
1142        let affine_points = <EdwardsPoint as BatchNormalize<_>>::batch_normalize(&points);
1143
1144        for (point, affine_point) in points.into_iter().zip(affine_points) {
1145            assert_eq!(affine_point, point.to_affine());
1146        }
1147    }
1148
1149    // TODO(tarcieri): use proptest
1150    #[test]
1151    #[cfg(all(feature = "alloc", feature = "getrandom"))]
1152    fn batch_normalize_alloc() {
1153        let points = alloc::vec![EdwardsPoint::generate(), EdwardsPoint::generate(),];
1154        let affine_points = <EdwardsPoint as BatchNormalize<_>>::batch_normalize(points.as_slice());
1155
1156        for (point, affine_point) in points.into_iter().zip(affine_points) {
1157            assert_eq!(affine_point, point.to_affine());
1158        }
1159    }
1160
1161    #[property_test]
1162    fn fuzz_is_torsion_free(bytes: [u8; 57]) {
1163        let scalar = EdwardsScalar::from_bytes_mod_order(&bytes.into());
1164        let mut point = EdwardsPoint::mul_by_generator(&scalar);
1165        prop_assert_eq!(point.is_torsion_free().unwrap_u8(), 1);
1166
1167        let T4 = CompressedEdwardsY([0u8; 57])
1168            .decompress_unchecked()
1169            .unwrap();
1170
1171        for _ in 0..3 {
1172            point += T4;
1173            assert!(bool::from(!point.is_torsion_free()));
1174        }
1175    }
1176}
ed448_goldilocks/edwards/extended.rs

ed448_goldilocks/edwards/
extended.rs
