ec/
point_hessian.rs

1//! Projective points on a generalized Hessian curve.
2//!
3//! We represent points on
4//!
5//! $$X^3 + Y^3 + cZ^3 = dXYZ$$
6//!
7//! by projective triples `(X:Y:Z)`.
8//!
9//! This choice is important for Hessian curves because the neutral element is a
10//! point at infinity:
11//!
12//! $$O = (1 : -1 : 0).$$
13//!
14//! The formulas implemented here follow:
15//!
16//! - Farashahi--Joye, §2--§4 for the generalized Hessian model,
17//! - the EFD projective Hessian formulas for the ordinary Hessian case.
18//!
19//! In particular:
20//!
21//! - negation is `-(X:Y:Z) = (Y:X:Z)`,
22//! - doubling uses the projective formulas from equation (6) in the paper,
23//! - addition uses the unified formulas (9), with formulas (10) as a fallback
24//!   for the exceptional cases described in §4.
25
26use core::fmt;
27
28use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
29
30use crate::curve_hessian::HessianCurve;
31use crate::point_ops::{PointAdd, PointOps};
32use fp::field_ops::FieldOps;
33
34/// A projective point `(X:Y:Z)` on a generalized Hessian curve.
35#[derive(Debug, Clone, Copy)]
36pub struct HessianPoint<F: FieldOps> {
37    /// Projective `X` coordinate.
38    pub x: F,
39    /// Projective `Y` coordinate.
40    pub y: F,
41    /// Projective `Z` coordinate.
42    pub z: F,
43}
44
45impl<F> fmt::Display for HessianPoint<F>
46where
47    F: FieldOps + fmt::Display,
48{
49    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50        if self.is_identity() {
51            if f.alternate() {
52                write!(f, "HessianPoint {{ O = (1:-1:0) }}")
53            } else {
54                write!(f, "O")
55            }
56        } else if self.is_zero_projective() {
57            if f.alternate() {
58                write!(f, "HessianPoint {{ invalid = (0:0:0) }}")
59            } else {
60                write!(f, "(0:0:0)")
61            }
62        } else if let Some((x_aff, y_aff)) = self.to_affine() {
63            if f.alternate() {
64                write!(
65                    f,
66                    "HessianPoint {{ X:Y:Z = ({}:{}:{}), x = {}, y = {} }}",
67                    self.x, self.y, self.z, x_aff, y_aff
68                )
69            } else {
70                write!(f, "({}, {})", x_aff, y_aff)
71            }
72        } else if f.alternate() {
73            write!(f, "HessianPoint {{ X:Y:Z = ({}:{}:{}) }}", self.x, self.y, self.z)
74        } else {
75            write!(f, "({}:{}:{})", self.x, self.y, self.z)
76        }
77    }
78}
79
80impl<F: FieldOps> PartialEq for HessianPoint<F> {
81    /// Equality of projective points.
82    fn eq(&self, other: &Self) -> bool {
83        let self_zero = self.is_zero_projective();
84        let other_zero = other.is_zero_projective();
85        if self_zero || other_zero {
86            return self_zero && other_zero;
87        }
88
89        self.x * other.y == other.x * self.y
90            && self.x * other.z == other.x * self.z
91            && self.y * other.z == other.y * self.z
92    }
93}
94
95impl<F: FieldOps> Eq for HessianPoint<F> {}
96
97impl<F: FieldOps> HessianPoint<F> {
98    /// Construct a projective Hessian point without validation.
99    pub fn new(x: F, y: F, z: F) -> Self {
100        Self { x, y, z }
101    }
102
103    /// Construct the finite affine point `(x, y)`, represented as `(x:y:1)`.
104    pub fn from_affine(x: F, y: F) -> Self {
105        Self { x, y, z: F::one() }
106    }
107
108    /// Return the neutral element `(1:-1:0)`.
109    pub fn identity() -> Self {
110        Self {
111            x: F::one(),
112            y: -F::one(),
113            z: F::zero(),
114        }
115    }
116
117    /// Return `true` when the point is the neutral element.
118    pub fn is_identity(&self) -> bool {
119        if !bool::from(self.z.is_zero()) {
120            return false;
121        }
122
123        if bool::from(self.x.is_zero()) && bool::from(self.y.is_zero()) {
124            return false;
125        }
126
127        self.x + self.y == F::zero()
128    }
129
130    /// Return `true` if the point lies on the line at infinity.
131    pub fn is_at_infinity(&self) -> bool {
132        bool::from(self.z.is_zero()) && !self.is_zero_projective()
133    }
134
135    /// Return `true` if this is the invalid projective triple `(0:0:0)`.
136    pub fn is_zero_projective(&self) -> bool {
137        bool::from(self.x.is_zero())
138            && bool::from(self.y.is_zero())
139            && bool::from(self.z.is_zero())
140    }
141
142    /// Convert a finite projective point to affine coordinates.
143    pub fn to_affine(&self) -> Option<(F, F)> {
144        self.z
145            .invert()
146            .into_option()
147            .map(|zinv| (self.x * zinv, self.y * zinv))
148    }
149}
150
151impl<F> ConditionallySelectable for HessianPoint<F>
152where
153    F: FieldOps + Copy,
154{
155    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
156        Self {
157            x: F::conditional_select(&a.x, &b.x, choice),
158            y: F::conditional_select(&a.y, &b.y, choice),
159            z: F::conditional_select(&a.z, &b.z, choice),
160        }
161    }
162
163    fn conditional_assign(&mut self, other: &Self, choice: Choice) {
164        self.x.conditional_assign(&other.x, choice);
165        self.y.conditional_assign(&other.y, choice);
166        self.z.conditional_assign(&other.z, choice);
167    }
168
169    fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice) {
170        F::conditional_swap(&mut a.x, &mut b.x, choice);
171        F::conditional_swap(&mut a.y, &mut b.y, choice);
172        F::conditional_swap(&mut a.z, &mut b.z, choice);
173    }
174}
175
176impl<F> ConstantTimeEq for HessianPoint<F>
177where
178    F: FieldOps + Copy + ConstantTimeEq,
179{
180    fn ct_eq(&self, other: &Self) -> Choice {
181        let self_zero = self.is_zero_projective();
182        let other_zero = other.is_zero_projective();
183        if self_zero || other_zero {
184            return Choice::from((self_zero && other_zero) as u8);
185        }
186
187        (self.x * other.y).ct_eq(&(other.x * self.y))
188            & (self.x * other.z).ct_eq(&(other.x * self.z))
189            & (self.y * other.z).ct_eq(&(other.y * self.z))
190    }
191
192    fn ct_ne(&self, other: &Self) -> Choice {
193        !self.ct_eq(other)
194    }
195}
196
197impl<F: FieldOps> HessianPoint<F> {
198    /// Negation on a Hessian curve:
199    ///
200    /// $$-(X:Y:Z) = (Y:X:Z).$$
201    pub fn negate(&self, _curve: &HessianCurve<F>) -> Self {
202        Self::new(self.y, self.x, self.z)
203    }
204
205    /// Projective point doubling.
206    ///
207    /// This implements Farashahi--Joye equation (6):
208    ///
209    /// ```text
210    /// X3 = Y1 (c Z1^3 - X1^3)
211    /// Y3 = X1 (Y1^3 - c Z1^3)
212    /// Z3 = Z1 (X1^3 - Y1^3)
213    /// ```
214    pub fn double(&self, curve: &HessianCurve<F>) -> Self {
215        if self.is_identity() {
216            return *self;
217        }
218
219        let x2 = <F as FieldOps>::square(&self.x);
220        let y2 = <F as FieldOps>::square(&self.y);
221        let z2 = <F as FieldOps>::square(&self.z);
222
223        let x3 = self.x * x2;
224        let y3 = self.y * y2;
225        let z3 = self.z * z2;
226        let cz3 = curve.c * z3;
227
228        Self::new(
229            self.y * (cz3 - x3),
230            self.x * (y3 - cz3),
231            self.z * (x3 - y3),
232        )
233    }
234
235    /// Unified projective addition formula (9) from Farashahi--Joye §3.
236    fn add_formula_9(&self, other: &Self, curve: &HessianCurve<F>) -> Self {
237        let x1_sq = <F as FieldOps>::square(&self.x);
238        let y1_sq = <F as FieldOps>::square(&self.y);
239        let z1_sq = <F as FieldOps>::square(&self.z);
240        let x2_sq = <F as FieldOps>::square(&other.x);
241        let y2_sq = <F as FieldOps>::square(&other.y);
242        let z2_sq = <F as FieldOps>::square(&other.z);
243
244        let x3 = curve.c * other.y * other.z * z1_sq - self.x * self.y * x2_sq;
245        let y3 = other.x * other.y * y1_sq - curve.c * self.x * self.z * z2_sq;
246        let z3 = other.x * other.z * x1_sq - self.y * self.z * y2_sq;
247
248        Self::new(x3, y3, z3)
249    }
250
251    /// Unified projective addition formula (10) from Farashahi--Joye §3.
252    fn add_formula_10(&self, other: &Self, curve: &HessianCurve<F>) -> Self {
253        let x1_sq = <F as FieldOps>::square(&self.x);
254        let y1_sq = <F as FieldOps>::square(&self.y);
255        let z1_sq = <F as FieldOps>::square(&self.z);
256        let x2_sq = <F as FieldOps>::square(&other.x);
257        let y2_sq = <F as FieldOps>::square(&other.y);
258        let z2_sq = <F as FieldOps>::square(&other.z);
259
260        let x3 = curve.c * self.y * self.z * z2_sq - other.x * other.y * x1_sq;
261        let y3 = self.x * self.y * y2_sq - curve.c * other.x * other.z * z1_sq;
262        let z3 = self.x * self.z * x2_sq - other.y * other.z * y1_sq;
263
264        Self::new(x3, y3, z3)
265    }
266
267    /// Add two projective Hessian points.
268    ///
269    /// We first evaluate the unified formulas (9). If they produce the invalid
270    /// triple `(0:0:0)`, we fall back to formulas (10), which cover the
271    /// complementary exceptional set described in Farashahi--Joye §4.
272    pub fn add(&self, other: &Self, curve: &HessianCurve<F>) -> Self {
273        if self.is_identity() {
274            return *other;
275        }
276        if other.is_identity() {
277            return *self;
278        }
279
280        let r = self.add_formula_9(other, curve);
281        if !r.is_zero_projective() {
282            return r;
283        }
284
285        let s = self.add_formula_10(other, curve);
286        if !s.is_zero_projective() {
287            return s;
288        }
289
290        if *other == self.negate(curve) {
291            return Self::identity();
292        }
293
294        panic!("Hessian addition failed for valid-looking inputs; both unified formula branches vanished");
295    }
296
297    /// Variable-time double-and-add scalar multiplication.
298    pub fn scalar_mul(&self, k: &[u64], curve: &HessianCurve<F>) -> Self {
299        let mut result = Self::identity();
300
301        for &limb in k.iter().rev() {
302            for bit in (0..64).rev() {
303                let doubled = result.double(curve);
304                let added = doubled.add(self, curve);
305                let choice = Choice::from(((limb >> bit) & 1) as u8);
306                result = Self::conditional_select(&doubled, &added, choice);
307            }
308        }
309
310        result
311    }
312}
313
314impl<F: FieldOps> PointOps for HessianPoint<F> {
315    type BaseField = F;
316    type Curve = HessianCurve<F>;
317
318    fn identity(_curve: &Self::Curve) -> Self {
319        HessianPoint::<F>::identity()
320    }
321
322    fn is_identity(&self) -> bool {
323        HessianPoint::<F>::is_identity(self)
324    }
325
326    fn negate(&self, curve: &Self::Curve) -> Self {
327        HessianPoint::<F>::negate(self, curve)
328    }
329
330    fn scalar_mul(&self, k: &[u64], curve: &Self::Curve) -> Self {
331        HessianPoint::<F>::scalar_mul(self, k, curve)
332    }
333}
334
335impl<F: FieldOps> PointAdd for HessianPoint<F> {
336    fn add(&self, other: &Self, curve: &Self::Curve) -> Self {
337        HessianPoint::<F>::add(self, other, curve)
338    }
339}
ec/point_hessian.rs

ec/
point_hessian.rs
