ed448_goldilocks/edwards/
affine.rs

1use crate::{field::FieldElement, *};
2use core::fmt::{Display, Formatter, LowerHex, Result as FmtResult, UpperHex};
3use elliptic_curve::array::Array;
4use elliptic_curve::{
5    Error, Generate, ctutils,
6    group::{CurveAffine, Group, GroupEncoding},
7    ops::{Mul, MulVartime, Neg},
8    point::{AffineCoordinates, NonIdentity},
9    zeroize::DefaultIsZeroes,
10};
11use rand_core::{TryCryptoRng, TryRng};
12use subtle::{Choice, ConditionallyNegatable, ConditionallySelectable, ConstantTimeEq, CtOption};
13
14/// Affine point on untwisted curve
15#[derive(Copy, Clone, Debug)]
16pub struct AffinePoint {
17    pub(crate) x: FieldElement,
18    pub(crate) y: FieldElement,
19}
20
21impl AffinePoint {
22    /// The identity point
23    pub const IDENTITY: AffinePoint = AffinePoint {
24        x: FieldElement::ZERO,
25        y: FieldElement::ONE,
26    };
27
28    /// Standard compression; store Y and sign of X
29    pub fn compress(&self) -> CompressedEdwardsY {
30        let affine_x = self.x;
31        let affine_y = self.y;
32
33        let mut compressed_bytes = [0u8; 57];
34
35        let sign = affine_x.is_negative().unwrap_u8();
36
37        let y_bytes = affine_y.to_bytes();
38        compressed_bytes[..y_bytes.len()].copy_from_slice(&y_bytes[..]);
39        *compressed_bytes.last_mut().expect("at least one byte") = sign << 7;
40        CompressedEdwardsY(compressed_bytes)
41    }
42
43    /// Check if this point is on the curve
44    pub fn is_on_curve(&self) -> Choice {
45        // X^2 + Y^2 == 1 + D * X^2 * Y^2
46
47        let XX = self.x.square();
48        let YY = self.y.square();
49        let lhs = YY + XX;
50        let rhs = FieldElement::ONE + FieldElement::EDWARDS_D * XX * YY;
51
52        lhs.ct_eq(&rhs)
53    }
54
55    /// Convert to edwards extended point
56    pub fn to_edwards(&self) -> EdwardsPoint {
57        EdwardsPoint {
58            X: self.x,
59            Y: self.y,
60            Z: FieldElement::ONE,
61            T: self.x * self.y,
62        }
63    }
64
65    /// The X coordinate
66    pub fn x(&self) -> [u8; 56] {
67        self.x.to_bytes()
68    }
69
70    /// The Y coordinate
71    pub fn y(&self) -> [u8; 56] {
72        self.y.to_bytes()
73    }
74
75    pub(crate) fn isogeny(&self) -> Self {
76        let x = self.x;
77        let y = self.y;
78        let mut t0 = x.square(); // x^2
79        let t1 = t0 + FieldElement::ONE; // x^2+1
80        t0 -= FieldElement::ONE; // x^2-1
81        let mut t2 = y.square(); // y^2
82        t2 = t2.double(); // 2y^2
83        let t3 = x.double(); // 2x
84
85        let mut t4 = t0 * y; // y(x^2-1)
86        t4 = t4.double(); // 2y(x^2-1)
87        let xNum = t4.double(); // xNum = 4y(x^2-1)
88
89        let mut t5 = t0.square(); // x^4-2x^2+1
90        t4 = t5 + t2; // x^4-2x^2+1+2y^2
91        let xDen = t4 + t2; // xDen = x^4-2x^2+1+4y^2
92
93        t5 *= x; // x^5-2x^3+x
94        t4 = t2 * t3; // 4xy^2
95        let yNum = t4 - t5; // yNum = -(x^5-2x^3+x-4xy^2)
96
97        t4 = t1 * t2; // 2x^2y^2+2y^2
98        let yDen = t5 - t4; // yDen = x^5-2x^3+x-2x^2y^2-2y^2
99
100        Self {
101            x: xNum * xDen.invert(),
102            y: yNum * yDen.invert(),
103        }
104    }
105
106    /// Generate a random [`AffinePoint`].
107    ///
108    /// Helper method that has `TryRng` bounds so `ProjectivePoint` can call it for its `group`
109    /// impls, otherwise end users should use the `Generate` trait.
110    pub(crate) fn try_random<R>(rng: &mut R) -> Result<Self, R::Error>
111    where
112        R: TryRng + ?Sized,
113    {
114        let mut bytes = CompressedEdwardsY::default();
115
116        loop {
117            rng.try_fill_bytes(&mut bytes.0)?;
118            if let Some(point) = bytes.decompress().into() {
119                return Ok(point);
120            }
121        }
122    }
123}
124
125impl AffineCoordinates for AffinePoint {
126    type FieldRepr = Ed448FieldBytes;
127
128    fn from_coordinates(x: &Self::FieldRepr, y: &Self::FieldRepr) -> CtOption<Self> {
129        let point = Self {
130            x: FieldElement::from_bytes_extended(&x.0),
131            y: FieldElement::from_bytes_extended(&y.0),
132        };
133
134        CtOption::new(point, point.is_on_curve())
135    }
136
137    fn x(&self) -> Self::FieldRepr {
138        Ed448FieldBytes::from(self.x.to_bytes_extended())
139    }
140
141    fn y(&self) -> Self::FieldRepr {
142        Ed448FieldBytes::from(self.y.to_bytes_extended())
143    }
144
145    fn x_is_odd(&self) -> Choice {
146        self.x.is_negative()
147    }
148
149    fn y_is_odd(&self) -> Choice {
150        self.y.is_negative()
151    }
152}
153
154impl CurveAffine for AffinePoint {
155    type Curve = EdwardsPoint;
156    type Scalar = EdwardsScalar;
157
158    fn identity() -> AffinePoint {
159        Self::IDENTITY
160    }
161
162    fn generator() -> AffinePoint {
163        EdwardsPoint::GENERATOR.to_affine()
164    }
165
166    fn is_identity(&self) -> Choice {
167        self.to_edwards().is_identity()
168    }
169
170    fn to_curve(&self) -> EdwardsPoint {
171        self.into()
172    }
173}
174
175impl Default for AffinePoint {
176    fn default() -> Self {
177        Self::IDENTITY
178    }
179}
180
181impl ConstantTimeEq for AffinePoint {
182    fn ct_eq(&self, other: &Self) -> Choice {
183        self.x.ct_eq(&other.x) & self.y.ct_eq(&other.y)
184    }
185}
186
187impl ConditionallySelectable for AffinePoint {
188    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
189        Self {
190            x: FieldElement::conditional_select(&a.x, &b.x, choice),
191            y: FieldElement::conditional_select(&a.y, &b.y, choice),
192        }
193    }
194}
195
196impl ctutils::CtEq for AffinePoint {
197    fn ct_eq(&self, other: &Self) -> ctutils::Choice {
198        (self.x.ct_eq(&other.x) & self.y.ct_eq(&other.y)).into()
199    }
200}
201
202impl ctutils::CtSelect for AffinePoint {
203    fn ct_select(&self, other: &Self, choice: ctutils::Choice) -> Self {
204        Self {
205            x: FieldElement::conditional_select(&self.x, &other.x, choice.into()),
206            y: FieldElement::conditional_select(&self.y, &other.y, choice.into()),
207        }
208    }
209}
210
211impl DefaultIsZeroes for AffinePoint {}
212
213impl Eq for AffinePoint {}
214impl PartialEq for AffinePoint {
215    fn eq(&self, other: &Self) -> bool {
216        self.ct_eq(other).into()
217    }
218}
219
220impl Generate for AffinePoint {
221    fn try_generate_from_rng<R: TryCryptoRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
222        Self::try_random(rng)
223    }
224}
225
226impl GroupEncoding for AffinePoint {
227    type Repr = Array<u8, U57>;
228
229    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
230        CompressedEdwardsY((*bytes).into()).decompress()
231    }
232
233    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
234        // No unchecked conversion possible for compressed points
235        Self::from_bytes(bytes)
236    }
237
238    fn to_bytes(&self) -> Self::Repr {
239        self.compress().0.into()
240    }
241}
242
243impl From<NonIdentity<AffinePoint>> for AffinePoint {
244    fn from(affine: NonIdentity<AffinePoint>) -> Self {
245        affine.to_point()
246    }
247}
248
249impl TryFrom<AffinePoint> for NonIdentity<AffinePoint> {
250    type Error = Error;
251
252    fn try_from(affine_point: AffinePoint) -> Result<Self, Error> {
253        NonIdentity::new(affine_point).into_option().ok_or(Error)
254    }
255}
256
257impl Mul<&EdwardsScalar> for &AffinePoint {
258    type Output = EdwardsPoint;
259
260    #[inline]
261    fn mul(self, scalar: &EdwardsScalar) -> Self::Output {
262        self.to_edwards() * scalar
263    }
264}
265
266impl MulVartime<EdwardsScalar> for AffinePoint {
267    #[inline]
268    fn mul_vartime(self, scalar: EdwardsScalar) -> Self::Output {
269        self.mul_vartime(&scalar)
270    }
271}
272
273impl MulVartime<&EdwardsScalar> for AffinePoint {
274    #[inline]
275    fn mul_vartime(self, scalar: &EdwardsScalar) -> Self::Output {
276        MulVartime::mul_vartime(&self, scalar)
277    }
278}
279
280impl MulVartime<&EdwardsScalar> for &AffinePoint {
281    #[inline]
282    fn mul_vartime(self, scalar: &EdwardsScalar) -> Self::Output {
283        // TODO(tarcieri): optimized vartime implementation
284        self * scalar
285    }
286}
287
288define_mul_variants!(
289    LHS = AffinePoint,
290    RHS = EdwardsScalar,
291    Output = EdwardsPoint
292);
293
294impl Neg for AffinePoint {
295    type Output = AffinePoint;
296
297    fn neg(self) -> Self::Output {
298        self.to_edwards().neg().to_affine()
299    }
300}
301
302/// The compressed internal representation of a point on the Twisted Edwards Curve
303pub type PointBytes = [u8; 57];
304
305/// Represents a point on the Compressed Twisted Edwards Curve
306/// in little endian format where the most significant bit is the sign bit
307/// and the remaining 448 bits represent the y-coordinate
308#[derive(Copy, Clone, Debug)]
309pub struct CompressedEdwardsY(pub PointBytes);
310
311impl elliptic_curve::zeroize::Zeroize for CompressedEdwardsY {
312    fn zeroize(&mut self) {
313        self.0.zeroize()
314    }
315}
316
317impl Display for CompressedEdwardsY {
318    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
319        for b in &self.0[..] {
320            write!(f, "{b:02x}")?;
321        }
322        Ok(())
323    }
324}
325
326impl LowerHex for CompressedEdwardsY {
327    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
328        for b in &self.0[..] {
329            write!(f, "{b:02x}")?;
330        }
331        Ok(())
332    }
333}
334
335impl UpperHex for CompressedEdwardsY {
336    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
337        for b in &self.0[..] {
338            write!(f, "{b:02X}")?;
339        }
340        Ok(())
341    }
342}
343
344impl Default for CompressedEdwardsY {
345    fn default() -> Self {
346        Self([0u8; 57])
347    }
348}
349
350impl ConditionallySelectable for CompressedEdwardsY {
351    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
352        let mut bytes = [0u8; 57];
353        for (i, byte) in bytes.iter_mut().enumerate() {
354            *byte = u8::conditional_select(&a.0[i], &b.0[i], choice);
355        }
356        Self(bytes)
357    }
358}
359
360impl ConstantTimeEq for CompressedEdwardsY {
361    fn ct_eq(&self, other: &Self) -> Choice {
362        self.0.ct_eq(&other.0)
363    }
364}
365
366impl PartialEq for CompressedEdwardsY {
367    fn eq(&self, other: &CompressedEdwardsY) -> bool {
368        self.ct_eq(other).into()
369    }
370}
371
372impl Eq for CompressedEdwardsY {}
373
374impl AsRef<[u8]> for CompressedEdwardsY {
375    fn as_ref(&self) -> &[u8] {
376        &self.0[..]
377    }
378}
379
380impl AsRef<PointBytes> for CompressedEdwardsY {
381    fn as_ref(&self) -> &PointBytes {
382        &self.0
383    }
384}
385
386#[cfg(feature = "alloc")]
387impl From<CompressedEdwardsY> for Vec<u8> {
388    fn from(value: CompressedEdwardsY) -> Self {
389        Self::from(&value)
390    }
391}
392
393#[cfg(feature = "alloc")]
394impl From<&CompressedEdwardsY> for Vec<u8> {
395    fn from(value: &CompressedEdwardsY) -> Self {
396        value.0.to_vec()
397    }
398}
399
400#[cfg(feature = "alloc")]
401impl TryFrom<Vec<u8>> for CompressedEdwardsY {
402    type Error = &'static str;
403
404    fn try_from(value: Vec<u8>) -> Result<Self, Self::Error> {
405        Self::try_from(&value)
406    }
407}
408
409#[cfg(feature = "alloc")]
410impl TryFrom<&Vec<u8>> for CompressedEdwardsY {
411    type Error = &'static str;
412
413    fn try_from(value: &Vec<u8>) -> Result<Self, Self::Error> {
414        Self::try_from(value.as_slice())
415    }
416}
417
418impl TryFrom<&[u8]> for CompressedEdwardsY {
419    type Error = &'static str;
420
421    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
422        let bytes = <PointBytes>::try_from(value).map_err(|_| "Invalid length")?;
423        Ok(CompressedEdwardsY(bytes))
424    }
425}
426
427#[cfg(feature = "alloc")]
428impl TryFrom<Box<[u8]>> for CompressedEdwardsY {
429    type Error = &'static str;
430
431    fn try_from(value: Box<[u8]>) -> Result<Self, Self::Error> {
432        Self::try_from(value.as_ref())
433    }
434}
435
436impl From<CompressedEdwardsY> for PointBytes {
437    fn from(value: CompressedEdwardsY) -> Self {
438        value.0
439    }
440}
441
442impl From<&CompressedEdwardsY> for PointBytes {
443    fn from(value: &CompressedEdwardsY) -> Self {
444        Self::from(*value)
445    }
446}
447
448#[cfg(feature = "serde")]
449impl serdect::serde::Serialize for CompressedEdwardsY {
450    fn serialize<S: serdect::serde::Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
451        serdect::array::serialize_hex_lower_or_bin(&self.0, s)
452    }
453}
454
455#[cfg(feature = "serde")]
456impl<'de> serdect::serde::Deserialize<'de> for CompressedEdwardsY {
457    fn deserialize<D>(d: D) -> Result<Self, D::Error>
458    where
459        D: serdect::serde::Deserializer<'de>,
460    {
461        let mut arr = [0u8; 57];
462        serdect::array::deserialize_hex_or_bin(&mut arr, d)?;
463        Ok(CompressedEdwardsY(arr))
464    }
465}
466
467impl From<PointBytes> for CompressedEdwardsY {
468    fn from(point: PointBytes) -> Self {
469        Self(point)
470    }
471}
472
473impl CompressedEdwardsY {
474    /// The compressed generator point
475    pub const GENERATOR: Self = Self([
476        20, 250, 48, 242, 91, 121, 8, 152, 173, 200, 215, 78, 44, 19, 189, 253, 196, 57, 124, 230,
477        28, 255, 211, 58, 215, 194, 160, 5, 30, 156, 120, 135, 64, 152, 163, 108, 115, 115, 234,
478        75, 98, 199, 201, 86, 55, 32, 118, 136, 36, 188, 182, 110, 113, 70, 63, 105, 0,
479    ]);
480    /// The compressed identity point
481    pub const IDENTITY: Self = Self([0u8; 57]);
482
483    /// Attempt to decompress to an `AffinePoint`.
484    ///
485    /// Returns `None` if the input is not the \\(y\\)-coordinate of a
486    /// curve point.
487    pub fn decompress_unchecked(&self) -> CtOption<AffinePoint> {
488        // Safe to unwrap here as the underlying data structure is a slice
489        let (sign, b) = self.0.split_last().expect("slice is non-empty");
490
491        let mut y_bytes: [u8; 56] = [0; 56];
492        y_bytes.copy_from_slice(b);
493
494        // Recover x using y
495        let y = FieldElement::from_bytes(&y_bytes);
496        let yy = y.square();
497        let dyy = FieldElement::EDWARDS_D * yy;
498        let numerator = FieldElement::ONE - yy;
499        let denominator = FieldElement::ONE - dyy;
500
501        let (mut x, is_res) = FieldElement::sqrt_ratio(&numerator, &denominator);
502
503        // Compute correct sign of x
504        let compressed_sign_bit = Choice::from(sign >> 7);
505        let is_negative = x.is_negative();
506        x.conditional_negate(compressed_sign_bit ^ is_negative);
507
508        CtOption::new(AffinePoint { x, y }, is_res)
509    }
510
511    /// Attempt to decompress to an `AffinePoint`.
512    ///
513    /// Returns `None`:
514    /// - if the input is not the \\(y\\)-coordinate of a curve point.
515    /// - if the input point is not on the curve.
516    /// - if the input point has nonzero torsion component.
517    pub fn decompress(&self) -> CtOption<AffinePoint> {
518        self.decompress_unchecked()
519            .and_then(|pt| CtOption::new(pt, pt.is_on_curve() & pt.to_edwards().is_torsion_free()))
520    }
521
522    /// View this `CompressedEdwardsY` as an array of bytes.
523    pub const fn as_bytes(&self) -> &PointBytes {
524        &self.0
525    }
526
527    /// Copy this `CompressedEdwardsY` to an array of bytes.
528    pub const fn to_bytes(&self) -> PointBytes {
529        self.0
530    }
531}
ed448_goldilocks/edwards/affine.rs

ed448_goldilocks/edwards/
affine.rs
