openzeppelin_crypto/curve/te/
projective.rs

1//! Projective coordinates for a point on a Twisted Edwards curve
2//! ([Homogeneous coordinates]).
3//!
4//! [Homogeneous coordinates]: https://en.wikipedia.org/wiki/Homogeneous_coordinates
5use alloc::vec::Vec;
6use core::{
7    borrow::Borrow,
8    fmt::{Display, Formatter},
9    hash::{Hash, Hasher},
10    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
11};
12
13use educe::Educe;
14use num_traits::{One, Zero};
15use zeroize::Zeroize;
16
17use super::{Affine, TECurveConfig};
18use crate::{
19    bits::BitIteratorBE,
20    curve::{batch_inversion, AffineRepr, CurveGroup, PrimeGroup},
21    field::{group::AdditiveGroup, prime::PrimeField, Field},
22    impl_additive_ops_from_ref,
23};
24
25/// `Projective` implements Extended Twisted Edwards Coordinates
26/// as described in [\[HKCD08\]](https://eprint.iacr.org/2008/522.pdf).
27///
28/// This implementation uses the unified addition formulae from that paper (see
29/// Section 3.1).
30#[derive(Educe)]
31#[educe(Copy, Clone, Eq(bound(P: TECurveConfig)), Debug)]
32#[must_use]
33pub struct Projective<P: TECurveConfig> {
34    /// The x-coordinate of the point in projective coordinates.
35    pub x: P::BaseField,
36    /// The y-coordinate of the point in projective coordinates.
37    pub y: P::BaseField,
38    /// The t-coordinate of the point in projective coordinates.
39    pub t: P::BaseField,
40    /// The z-coordinate of the point in projective coordinates.
41    pub z: P::BaseField,
42}
43
44impl<P: TECurveConfig> PartialEq<Affine<P>> for Projective<P> {
45    fn eq(&self, other: &Affine<P>) -> bool {
46        self == &other.into_group()
47    }
48}
49
50impl<P: TECurveConfig> Display for Projective<P> {
51    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
52        write!(f, "{}", Affine::from(*self))
53    }
54}
55
56impl<P: TECurveConfig> PartialEq for Projective<P> {
57    fn eq(&self, other: &Self) -> bool {
58        if self.is_zero() {
59            return other.is_zero();
60        }
61
62        if other.is_zero() {
63            return false;
64        }
65
66        // Checking equality without multiplication,
67        // e.g. x1/z1 == x2/z2 <==> x1 * z2 == x2 * z1.
68        (self.x * other.z) == (other.x * self.z)
69            && (self.y * other.z) == (other.y * self.z)
70    }
71}
72
73impl<P: TECurveConfig> Hash for Projective<P> {
74    fn hash<H: Hasher>(&self, state: &mut H) {
75        self.into_affine().hash(state);
76    }
77}
78
79impl<P: TECurveConfig> Default for Projective<P> {
80    #[inline]
81    fn default() -> Self {
82        Self::zero()
83    }
84}
85
86impl<P: TECurveConfig> Projective<P> {
87    /// Construct a new group element without checking whether the coordinates
88    /// specify a point in the subgroup.
89    pub const fn new_unchecked(
90        x: P::BaseField,
91        y: P::BaseField,
92        t: P::BaseField,
93        z: P::BaseField,
94    ) -> Self {
95        Self { x, y, t, z }
96    }
97
98    /// Construct a new group element in a way while enforcing that points are
99    /// in the prime-order subgroup.
100    ///
101    /// # Panics
102    ///
103    /// * If point is not on curve.
104    /// * If point is not in the prime-order subgroup.
105    pub fn new(
106        x: P::BaseField,
107        y: P::BaseField,
108        t: P::BaseField,
109        z: P::BaseField,
110    ) -> Self {
111        let p = Self::new_unchecked(x, y, t, z).into_affine();
112        assert!(p.is_on_curve());
113        assert!(p.is_in_prime_order_subgroup());
114        p.into()
115    }
116}
117impl<P: TECurveConfig> Zeroize for Projective<P> {
118    fn zeroize(&mut self) {
119        self.x.zeroize();
120        self.y.zeroize();
121        self.t.zeroize();
122        self.z.zeroize();
123    }
124}
125
126impl<P: TECurveConfig> Zero for Projective<P> {
127    fn zero() -> Self {
128        Projective::<P>::ZERO
129    }
130
131    fn is_zero(&self) -> bool {
132        self.x.is_zero()
133            && self.y == self.z
134            && !self.y.is_zero()
135            && self.t.is_zero()
136    }
137}
138
139impl<P: TECurveConfig> AdditiveGroup for Projective<P> {
140    type Scalar = P::ScalarField;
141
142    const ZERO: Self = Self::new_unchecked(
143        P::BaseField::ZERO,
144        P::BaseField::ONE,
145        P::BaseField::ZERO,
146        P::BaseField::ONE,
147    );
148
149    // See "Twisted Edwards Curves Revisited"
150    // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
151    // 3.3 Doubling in E^e
152    // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/doubling/dbl-2008-hwcd
153    fn double_in_place(&mut self) -> &mut Self {
154        // A = X1^2
155        let a = self.x.square();
156        // B = Y1^2
157        let b = self.y.square();
158        // C = 2 * Z1^2
159        let c = self.z.square().double();
160        // D = a * A
161        let d = P::mul_by_a(a);
162        // E = (X1 + Y1)^2 - A - B
163        let e = (self.x + self.y).square() - a - b;
164        // G = D + B
165        let g = d + b;
166        // F = G - C
167        let f = g - c;
168        // H = D - B
169        let h = d - b;
170        // X3 = E * F
171        self.x = e * f;
172        // Y3 = G * H
173        self.y = g * h;
174        // T3 = E * H
175        self.t = e * h;
176        // Z3 = F * G
177        self.z = f * g;
178
179        self
180    }
181}
182
183impl<P: TECurveConfig> PrimeGroup for Projective<P> {
184    type ScalarField = P::ScalarField;
185
186    fn generator() -> Self {
187        Affine::generator().into()
188    }
189
190    #[inline]
191    fn mul_bigint(&self, other: impl BitIteratorBE) -> Self {
192        P::mul_projective(self, other)
193    }
194}
195
196impl<P: TECurveConfig> CurveGroup for Projective<P> {
197    type Affine = Affine<P>;
198    type BaseField = P::BaseField;
199    type Config = P;
200    type FullGroup = Affine<P>;
201
202    /// A projective curve element `(x, y, t, z)` is normalized
203    /// to its affine representation, by the conversion
204    /// (x, y, t, z) -> (x/z, y/z, t/z, 1).
205    ///
206    /// Batch normalizing N twisted edwards curve elements costs: 1 inversion +
207    /// 6N field multiplications (batch inversion requires 3N multiplications +
208    /// 1 inversion).
209    ///
210    /// # Panics
211    ///
212    /// * If any `Z` coordinate of input `v` elements is zero.
213    fn normalize_batch(v: &[Self]) -> Vec<Self::Affine> {
214        assert!(
215            !v.iter().any(|v| v.z.is_zero()),
216            "projective Z coordinate should not be zero"
217        );
218
219        let mut z_s = v.iter().map(|g| g.z).collect::<Vec<_>>();
220
221        batch_inversion(&mut z_s);
222
223        // Perform affine transformations.
224        v.iter()
225            .zip(z_s)
226            .map(|(g, z)| {
227                if g.is_zero() {
228                    Affine::zero()
229                } else {
230                    let x = g.x * z;
231                    let y = g.y * z;
232                    Affine::new_unchecked(x, y)
233                }
234            })
235            .collect()
236    }
237}
238
239impl<P: TECurveConfig> Neg for Projective<P> {
240    type Output = Self;
241
242    fn neg(mut self) -> Self {
243        self.x = -self.x;
244        self.t = -self.t;
245        self
246    }
247}
248
249impl<P: TECurveConfig, T: Borrow<Affine<P>>> AddAssign<T> for Projective<P> {
250    // See "Twisted Edwards Curves Revisited"
251    // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
252    // 3.1 Unified Addition in E^e
253    // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/addition/madd-2008-hwcd
254    fn add_assign(&mut self, other: T) {
255        let other = other.borrow();
256        // A = X1*X2
257        let a = self.x * other.x;
258        // B = Y1*Y2
259        let b = self.y * other.y;
260        // C = T1*d*T2
261        let c = P::COEFF_D * self.t * other.x * other.y;
262
263        // D = Z1
264        let d = self.z;
265        // E = (X1+Y1)*(X2+Y2)-A-B
266        let e = (self.x + self.y) * (other.x + other.y) - a - b;
267        // F = D-C
268        let f = d - c;
269        // G = D+C
270        let g = d + c;
271        // H = B-a*A
272        let h = b - P::mul_by_a(a);
273        // X3 = E*F
274        self.x = e * f;
275        // Y3 = G*H
276        self.y = g * h;
277        // T3 = E*H
278        self.t = e * h;
279        // Z3 = F*G
280        self.z = f * g;
281    }
282}
283
284impl<P: TECurveConfig, T: Borrow<Affine<P>>> Add<T> for Projective<P> {
285    type Output = Self;
286
287    fn add(mut self, other: T) -> Self {
288        let other = other.borrow();
289        self += other;
290        self
291    }
292}
293
294impl<P: TECurveConfig, T: Borrow<Affine<P>>> SubAssign<T> for Projective<P> {
295    fn sub_assign(&mut self, other: T) {
296        *self += -(*other.borrow());
297    }
298}
299
300impl<P: TECurveConfig, T: Borrow<Affine<P>>> Sub<T> for Projective<P> {
301    type Output = Self;
302
303    fn sub(mut self, other: T) -> Self {
304        self -= other.borrow();
305        self
306    }
307}
308
309impl_additive_ops_from_ref!(Projective, TECurveConfig);
310
311impl<'a, P: TECurveConfig> Add<&'a Self> for Projective<P> {
312    type Output = Self;
313
314    fn add(mut self, other: &'a Self) -> Self {
315        self += other;
316        self
317    }
318}
319
320impl<'a, P: TECurveConfig> Sub<&'a Self> for Projective<P> {
321    type Output = Self;
322
323    fn sub(mut self, other: &'a Self) -> Self {
324        self -= other;
325        self
326    }
327}
328
329impl<'a, P: TECurveConfig> AddAssign<&'a Self> for Projective<P> {
330    // See "Twisted Edwards Curves Revisited" (https://eprint.iacr.org/2008/522.pdf)
331    // by Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
332    // 3.1 Unified Addition in E^e
333    fn add_assign(&mut self, other: &'a Self) {
334        // A = x1 * x2
335        let a = self.x * other.x;
336
337        // B = y1 * y2
338        let b = self.y * other.y;
339
340        // C = d * t1 * t2
341        let c = P::COEFF_D * self.t * other.t;
342
343        // D = z1 * z2
344        let d = self.z * other.z;
345
346        // H = B - aA
347        let h = b - P::mul_by_a(a);
348
349        // E = (x1 + y1) * (x2 + y2) - A - B
350        let e = (self.x + self.y) * (other.x + other.y) - a - b;
351
352        // F = D - C
353        let f = d - c;
354
355        // G = D + C
356        let g = d + c;
357
358        // x3 = E * F
359        self.x = e * f;
360
361        // y3 = G * H
362        self.y = g * h;
363
364        // t3 = E * H
365        self.t = e * h;
366
367        // z3 = F * G
368        self.z = f * g;
369    }
370}
371
372impl<'a, P: TECurveConfig> SubAssign<&'a Self> for Projective<P> {
373    fn sub_assign(&mut self, other: &'a Self) {
374        *self += -(*other);
375    }
376}
377
378impl<P: TECurveConfig, T: Borrow<P::ScalarField>> MulAssign<T>
379    for Projective<P>
380{
381    fn mul_assign(&mut self, other: T) {
382        *self = self.mul_bigint(other.borrow().into_bigint());
383    }
384}
385
386impl<P: TECurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Projective<P> {
387    type Output = Self;
388
389    #[inline]
390    fn mul(mut self, other: T) -> Self {
391        self *= other;
392        self
393    }
394}
395
396impl<P: TECurveConfig, T: Borrow<Affine<P>>> core::iter::Sum<T>
397    for Projective<P>
398{
399    fn sum<I>(iter: I) -> Self
400    where
401        I: Iterator<Item = T>,
402    {
403        iter.fold(Self::zero(), |acc, x| acc + x.borrow())
404    }
405}
406
407// The affine point (X, Y) is represented in the Extended Projective coordinates
408// with Z = 1.
409impl<P: TECurveConfig> From<Affine<P>> for Projective<P> {
410    fn from(p: Affine<P>) -> Projective<P> {
411        Self::new_unchecked(p.x, p.y, p.x * p.y, P::BaseField::one())
412    }
413}
openzeppelin_crypto/curve/te/projective.rs

openzeppelin_crypto/curve/te/
projective.rs
