a/math/ec/
point.rs

1//! Points of a curve.
2
3use super::curve::Curve;
4use super::field::limbs_of;
5use super::group::Table;
6use crate::math::numbers::Number;
7use core::fmt;
8use core::hash::{Hash, Hasher};
9use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
10
11/// A point of the curve `C`, which it borrows: always on the curve, as every way to get one
12/// checks.
13///
14/// It is held in a projective form in the field's own representation, so the group's operations
15/// take no inversion, and [`coordinates`](Point::coordinates) makes the one inversion they need
16/// when they are asked for. Every operator takes the points owned or borrowed; `+=`, `-=` and
17/// `*=`, and the operators on an owned left operand, keep its vector.
18///
19/// Scalars are numbers of any sign and length. **Nothing here is constant-time**: the times of the
20/// additions and doublings, and of a product, depend on the bits of the scalar, so it is not meant
21/// for secret scalars, such as private keys, where whoever can time it could learn them.
22///
23/// # Panics
24///
25/// The operators panic for two points of different curves.
26///
27/// # Examples
28///
29/// ```
30/// use a::math::ec::{Curve, Weierstrass};
31/// use a::math::numbers::{ByteOrder, Number};
32///
33/// let n = |x| Number::new_from_u32(x, ByteOrder::BigEndian);
34/// let curve = Weierstrass::new(&n(2), &n(3), &n(97)).unwrap();
35/// let p = curve.point(&n(3), &n(6)).unwrap();
36///
37/// // The point has order 5.
38/// assert_eq!(&p * &n(2) + &p * &n(3), curve.identity());
39/// assert!((&p * &n(5)).is_identity());
40/// assert_eq!(-&p, &p * &n(4));
41/// ```
42pub struct Point<'c, C: Curve> {
43    /// The curve.
44    curve: &'c C,
45    /// The coordinates in the field's form, one after another.
46    pub(super) limbs: Vec<u64>,
47}
48
49impl<'c, C: Curve> Point<'c, C> {
50    /// The point on `curve` with the stored coordinates `limbs`.
51    #[inline]
52    pub(super) fn from_limbs(curve: &'c C, limbs: Vec<u64>) -> Self {
53        Point { curve, limbs }
54    }
55
56    /// Whether the point is on `curve`: that value, or one of the same curve.
57    #[inline(always)]
58    pub(super) fn belongs_to(&self, curve: &C) -> bool {
59        core::ptr::eq(self.curve, curve) || self.curve.same_curve(curve)
60    }
61
62    /// Panics unless the point is on `curve`.
63    #[inline(always)]
64    #[track_caller]
65    pub(super) fn check_curve(&self, curve: &C) {
66        if !self.belongs_to(curve) {
67            different_curves();
68        }
69    }
70
71    /// The curve of the point.
72    #[inline]
73    pub fn curve(&self) -> &'c C {
74        self.curve
75    }
76
77    /// Whether this is the neutral element of the curve's group.
78    pub fn is_identity(&self) -> bool {
79        self.curve.is_identity_limbs(&self.limbs)
80    }
81
82    /// The affine coordinates `(x, y)`, below the prime, or `None` for the point at infinity. An
83    /// Edwards curve has none: its neutral element is `(0, 1)`.
84    ///
85    /// This is the one inversion that the group's operations leave for the end. For many points,
86    /// [`coordinates_of`](Point::coordinates_of) shares it.
87    pub fn coordinates(&self) -> Option<(Number, Number)> {
88        self.curve
89            .coordinates_limbs(&[&self.limbs])
90            .pop()
91            .unwrap_or(None)
92    }
93
94    /// The affine coordinates of each of the points, as
95    /// [`coordinates`](Point::coordinates) gives them, with one inversion for all of them and
96    /// about three products for each.
97    ///
98    /// # Panics
99    ///
100    /// Panics for points of different curves.
101    pub fn coordinates_of(points: &[Point<'c, C>]) -> Vec<Option<(Number, Number)>> {
102        let Some(first) = points.first() else {
103            return Vec::new();
104        };
105        let stored: Vec<&[u64]> = points
106            .iter()
107            .map(|p| {
108                p.check_curve(first.curve);
109                &p.limbs[..]
110            })
111            .collect();
112        first.curve.coordinates_limbs(&stored)
113    }
114
115    /// `2 p`, which costs less than `p + p`.
116    pub fn double(&self) -> Self {
117        let mut r = self.clone();
118        self.curve.double_limbs(&mut r.limbs);
119        r
120    }
121
122    /// The point in its shortest encoding, which [`Curve::point_from_bytes`] reads: SEC 1's compressed
123    /// form on Weierstrass and Montgomery curves, a byte for the parity of `y` and then `x` in
124    /// big-endian order, a single zero byte for the point at infinity; on Edwards curves that of
125    /// RFC 8032, `y` in little-endian order, with the parity of `x` in the top bit.
126    pub fn compress(&self) -> Vec<u8> {
127        let xy = self.coordinates();
128        self.curve.encode(xy.as_ref().map(|(x, y)| (x, y)), true)
129    }
130
131    /// The point in the encoding with both coordinates, which [`Curve::point_from_bytes`] reads: SEC 1's
132    /// uncompressed form on Weierstrass and Montgomery curves, on Edwards curves `x` and then `y`
133    /// in little-endian order.
134    pub fn to_bytes(&self) -> Vec<u8> {
135        let xy = self.coordinates();
136        self.curve.encode(xy.as_ref().map(|(x, y)| (x, y)), false)
137    }
138
139    /// The multiples of this point computed once for all, for scalars of up to `bits` bits, as a
140    /// [`Divisor`](crate::math::numbers::Divisor) is for divisions. Measured on an Apple M4 Max on
141    /// P-256, building the table for 256 bits took the time of 30 products, and each product
142    /// afterwards an eighth of the time of one of [`Mul`].
143    pub fn prepare(&self, bits: usize) -> Prepared<'c, C> {
144        Prepared {
145            curve: self.curve,
146            table: self.curve.prepare_limbs(&self.limbs, bits),
147            point: self.limbs.clone(),
148        }
149    }
150}
151
152/// Panics for points of different curves.
153#[cold]
154#[inline(never)]
155#[track_caller]
156fn different_curves() -> ! {
157    panic!("the points are on different curves")
158}
159
160/// The multiples of a point computed once, from [`Point::prepare`].
161pub struct Prepared<'c, C: Curve> {
162    /// The curve.
163    curve: &'c C,
164    /// The multiples.
165    table: Table,
166    /// The point, for scalars longer than the table.
167    point: Vec<u64>,
168}
169
170impl<'c, C: Curve> Prepared<'c, C> {
171    /// `k` times the point, from the table when `k` is not longer than what it was built for.
172    pub fn mul(&self, k: &Number) -> Point<'c, C> {
173        let scalar = limbs_of(k);
174        let mut limbs = self.point.clone();
175        if k.bits() as usize <= self.table.bits {
176            self.curve
177                .prepared_limbs(&mut limbs, &self.table, &scalar, k.is_negative());
178        } else {
179            self.curve.mul_limbs(&mut limbs, &scalar, k.is_negative());
180        }
181        Point::from_limbs(self.curve, limbs)
182    }
183}
184
185impl<C: Curve> Clone for Point<'_, C> {
186    fn clone(&self) -> Self {
187        Point {
188            curve: self.curve,
189            limbs: self.limbs.clone(),
190        }
191    }
192
193    fn clone_from(&mut self, source: &Self) {
194        self.curve = source.curve;
195        self.limbs.clone_from(&source.limbs);
196    }
197}
198
199/// Two points are equal when they are the same point, in whatever projective form each is held.
200/// This needs no inversion.
201impl<C: Curve> PartialEq for Point<'_, C> {
202    #[track_caller]
203    fn eq(&self, other: &Self) -> bool {
204        other.check_curve(self.curve);
205        self.curve.equal_limbs(&self.limbs, &other.limbs)
206    }
207}
208
209impl<C: Curve> Eq for Point<'_, C> {}
210
211/// By the affine coordinates, the same for equal points: each hash takes an inversion.
212impl<C: Curve> Hash for Point<'_, C> {
213    fn hash<H: Hasher>(&self, state: &mut H) {
214        self.coordinates().hash(state);
215    }
216}
217
218impl<C: Curve> fmt::Debug for Point<'_, C> {
219    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
220        fmt::Display::fmt(self, f)
221    }
222}
223
224/// `(x, y)` in decimal, or `infinity`.
225impl<C: Curve> fmt::Display for Point<'_, C> {
226    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
227        match self.coordinates() {
228            Some((x, y)) => write!(f, "({x}, {y})"),
229            None => f.write_str("infinity"),
230        }
231    }
232}
233
234impl<'c, C: Curve> Neg for &Point<'c, C> {
235    type Output = Point<'c, C>;
236
237    fn neg(self) -> Point<'c, C> {
238        -self.clone()
239    }
240}
241
242impl<'c, C: Curve> Neg for Point<'c, C> {
243    type Output = Point<'c, C>;
244
245    fn neg(mut self) -> Point<'c, C> {
246        self.curve.neg_limbs(&mut self.limbs);
247        self
248    }
249}
250
251/// Implements a binary operator for every mix of owned and borrowed operands, from its assignment
252/// on the left operand's coordinates, reusing an owned left operand's vector.
253macro_rules! operators {
254    ($trait:ident, $method:ident, $assign:ident, $assign_method:ident, $limbs:ident) => {
255        impl<'c, C: Curve> $assign<&Point<'c, C>> for Point<'c, C> {
256            #[track_caller]
257            fn $assign_method(&mut self, rhs: &Point<'c, C>) {
258                rhs.check_curve(self.curve);
259                self.curve.$limbs(&mut self.limbs, &rhs.limbs);
260            }
261        }
262
263        impl<'c, C: Curve> $assign<Point<'c, C>> for Point<'c, C> {
264            #[track_caller]
265            fn $assign_method(&mut self, rhs: Point<'c, C>) {
266                self.$assign_method(&rhs);
267            }
268        }
269
270        impl<'c, C: Curve> $trait<&Point<'c, C>> for Point<'c, C> {
271            type Output = Point<'c, C>;
272
273            #[track_caller]
274            fn $method(mut self, rhs: &Point<'c, C>) -> Point<'c, C> {
275                self.$assign_method(rhs);
276                self
277            }
278        }
279
280        impl<'c, C: Curve> $trait<Point<'c, C>> for Point<'c, C> {
281            type Output = Point<'c, C>;
282
283            #[track_caller]
284            fn $method(self, rhs: Point<'c, C>) -> Point<'c, C> {
285                self.$method(&rhs)
286            }
287        }
288
289        impl<'c, C: Curve> $trait<&Point<'c, C>> for &Point<'c, C> {
290            type Output = Point<'c, C>;
291
292            #[track_caller]
293            fn $method(self, rhs: &Point<'c, C>) -> Point<'c, C> {
294                self.clone().$method(rhs)
295            }
296        }
297
298        impl<'c, C: Curve> $trait<Point<'c, C>> for &Point<'c, C> {
299            type Output = Point<'c, C>;
300
301            #[track_caller]
302            fn $method(self, rhs: Point<'c, C>) -> Point<'c, C> {
303                self.clone().$method(&rhs)
304            }
305        }
306    };
307}
308operators!(Add, add, AddAssign, add_assign, add_limbs);
309operators!(Sub, sub, SubAssign, sub_assign, sub_limbs);
310
311impl<C: Curve> MulAssign<&Number> for Point<'_, C> {
312    fn mul_assign(&mut self, k: &Number) {
313        self.curve
314            .mul_limbs(&mut self.limbs, &limbs_of(k), k.is_negative());
315    }
316}
317
318impl<C: Curve> MulAssign<Number> for Point<'_, C> {
319    fn mul_assign(&mut self, k: Number) {
320        *self *= &k;
321    }
322}
323
324impl<'c, C: Curve> Mul<&Number> for Point<'c, C> {
325    type Output = Point<'c, C>;
326
327    fn mul(mut self, k: &Number) -> Point<'c, C> {
328        self *= k;
329        self
330    }
331}
332
333impl<'c, C: Curve> Mul<Number> for Point<'c, C> {
334    type Output = Point<'c, C>;
335
336    fn mul(self, k: Number) -> Point<'c, C> {
337        self * &k
338    }
339}
340
341impl<'c, C: Curve> Mul<&Number> for &Point<'c, C> {
342    type Output = Point<'c, C>;
343
344    fn mul(self, k: &Number) -> Point<'c, C> {
345        self.clone() * k
346    }
347}
348
349impl<'c, C: Curve> Mul<Number> for &Point<'c, C> {
350    type Output = Point<'c, C>;
351
352    fn mul(self, k: Number) -> Point<'c, C> {
353        self.clone() * &k
354    }
355}
356
357impl<'c, C: Curve> Mul<&Point<'c, C>> for &Number {
358    type Output = Point<'c, C>;
359
360    fn mul(self, p: &Point<'c, C>) -> Point<'c, C> {
361        p * self
362    }
363}
364
365impl<'c, C: Curve> Mul<Point<'c, C>> for &Number {
366    type Output = Point<'c, C>;
367
368    fn mul(self, p: Point<'c, C>) -> Point<'c, C> {
369        p * self
370    }
371}
372
373impl<'c, C: Curve> Mul<&Point<'c, C>> for Number {
374    type Output = Point<'c, C>;
375
376    fn mul(self, p: &Point<'c, C>) -> Point<'c, C> {
377        p * &self
378    }
379}
380
381impl<'c, C: Curve> Mul<Point<'c, C>> for Number {
382    type Output = Point<'c, C>;
383
384    fn mul(self, p: Point<'c, C>) -> Point<'c, C> {
385        p * &self
386    }
387}
a/math/ec/point.rs

a/math/ec/
point.rs
