a/math/ec/
curve.rs

1//! What every form of curve offers, and the operations on stored points each form implements.
2
3use super::field::{Base, limbs_of};
4use super::group::Table;
5use super::point::Point;
6use crate::math::numbers::{ByteOrder, Number};
7use core::fmt;
8
9/// Why a curve can't be built from its parameters.
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub enum CurveError {
12    /// The modulus is not a prime above 3.
13    NotPrime,
14    /// The curve has a singular point: its discriminant is zero modulo the prime.
15    Singular,
16    /// The twisted Edwards addition law is not complete: `a` must be a square and `d` not.
17    NotComplete,
18    /// The generator of a [`Domain`](super::Domain) is not on its curve.
19    NotOnCurve,
20    /// The order given for a [`Domain`](super::Domain) is not a multiple of its generator's.
21    WrongOrder,
22}
23
24impl fmt::Display for CurveError {
25    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
26        f.write_str(match self {
27            CurveError::NotPrime => "the modulus is not a prime above 3",
28            CurveError::Singular => "the curve is singular",
29            CurveError::NotComplete => {
30                "the addition law is not complete: a must be a square and d not"
31            }
32            CurveError::NotOnCurve => "the generator is not on the curve",
33            CurveError::WrongOrder => "the order times the generator is not the neutral element",
34        })
35    }
36}
37
38impl core::error::Error for CurveError {}
39
40/// The error of [`Curve::point`] for coordinates that don't satisfy the curve's equation.
41#[derive(Clone, Copy, Debug, PartialEq, Eq)]
42pub struct NotOnCurve;
43
44impl fmt::Display for NotOnCurve {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        f.write_str("the point is not on the curve")
47    }
48}
49
50impl core::error::Error for NotOnCurve {}
51
52/// The operations on points held as the limbs of their coordinates in the field's form, which each
53/// form compiles for each field. Not nameable outside the crate, which seals [`Curve`].
54pub trait Arithmetic: Sized {
55    /// The coordinates a point is stored with.
56    const COORDINATES: usize;
57
58    /// The field.
59    fn base(&self) -> &Base;
60    /// Whether the two are the same curve.
61    fn same_curve(&self, other: &Self) -> bool;
62    /// Whether `(x, y)` satisfies the curve's equation.
63    fn satisfied(&self, x: &Number, y: &Number) -> bool;
64    /// The point with the given coordinate, whose other coordinate has the parity `odd`.
65    fn lift_limbs(&self, coordinate: &Number, odd: bool) -> Option<Vec<u64>>;
66    /// The bytes of the point with the affine coordinates `xy`.
67    fn encode(&self, xy: Option<(&Number, &Number)>, compressed: bool) -> Vec<u8>;
68    /// The point the bytes stand for.
69    fn decode(&self, bytes: &[u8]) -> Option<Vec<u64>>;
70
71    /// The neutral element.
72    fn identity_limbs(&self) -> Vec<u64>;
73    /// The point `(x, y)`.
74    fn affine_limbs(&self, x: &Number, y: &Number) -> Vec<u64>;
75    /// Whether `p` is the neutral element.
76    fn is_identity_limbs(&self, p: &[u64]) -> bool;
77    /// `p += q`.
78    fn add_limbs(&self, p: &mut [u64], q: &[u64]);
79    /// `p -= q`.
80    fn sub_limbs(&self, p: &mut [u64], q: &[u64]);
81    /// `p = 2 p`.
82    fn double_limbs(&self, p: &mut [u64]);
83    /// `p = -p`.
84    fn neg_limbs(&self, p: &mut [u64]);
85    /// `p = k p`, for the magnitude `k` with the sign `negative`.
86    fn mul_limbs(&self, p: &mut [u64], k: &[u64], negative: bool);
87    /// `r` is the sum of the terms, each a magnitude, its sign and a point.
88    fn multi_limbs(&self, r: &mut [u64], terms: &[(&[u64], bool, &[u64])]);
89    /// Whether `p` and `q` are the same point.
90    fn equal_limbs(&self, p: &[u64], q: &[u64]) -> bool;
91    /// The affine coordinates of each point, `None` for one at infinity.
92    fn coordinates_limbs(&self, p: &[&[u64]]) -> Vec<Option<(Number, Number)>>;
93    /// The table of `p` for scalars of up to `bits` bits.
94    fn prepare_limbs(&self, p: &[u64], bits: usize) -> Table;
95    /// `r = k p` from the table of `p`.
96    fn prepared_limbs(&self, r: &mut [u64], table: &Table, k: &[u64], negative: bool);
97}
98
99/// Implements the operations of [`Arithmetic`] that all forms write the same way, given the macro
100/// that binds a curve's group.
101macro_rules! arithmetic {
102    ($with:ident) => {
103        fn identity_limbs(&self) -> Vec<u64> {
104            $with!(self, g => {
105                let mut r = vec![0; Self::COORDINATES * g.field().limbs()];
106                g.store(&g.identity(), &mut r);
107                r
108            })
109        }
110
111        fn affine_limbs(&self, x: &Number, y: &Number) -> Vec<u64> {
112            $with!(self, g => {
113                let f = g.field();
114                let mut r = vec![0; Self::COORDINATES * f.limbs()];
115                g.store(&g.of_affine(&f.enter(x), &f.enter(y)), &mut r);
116                r
117            })
118        }
119
120        fn is_identity_limbs(&self, p: &[u64]) -> bool {
121            $with!(self, g => g.is_identity(&g.load(p)))
122        }
123
124        fn add_limbs(&self, p: &mut [u64], q: &[u64]) {
125            $with!(self, g => {
126                let s = g.add(&g.load(p), &g.load(q));
127                g.store(&s, p)
128            })
129        }
130
131        fn sub_limbs(&self, p: &mut [u64], q: &[u64]) {
132            $with!(self, g => {
133                let s = g.add(&g.load(p), &g.neg(&g.load(q)));
134                g.store(&s, p)
135            })
136        }
137
138        fn double_limbs(&self, p: &mut [u64]) {
139            $with!(self, g => {
140                let s = g.double(&g.load(p));
141                g.store(&s, p)
142            })
143        }
144
145        fn neg_limbs(&self, p: &mut [u64]) {
146            $with!(self, g => {
147                let s = g.neg(&g.load(p));
148                g.store(&s, p)
149            })
150        }
151
152        fn mul_limbs(&self, p: &mut [u64], k: &[u64], negative: bool) {
153            $with!(self, g => {
154                let s = Group::mul(&g, &g.load(p), k, negative);
155                g.store(&s, p)
156            })
157        }
158
159        fn multi_limbs(&self, r: &mut [u64], terms: &[(&[u64], bool, &[u64])]) {
160            $with!(self, g => {
161                let loaded: Vec<_> = terms
162                    .iter()
163                    .map(|&(k, negative, p)| (k, negative, g.load(p)))
164                    .collect();
165                g.store(&$crate::math::ec::group::multi_mul(&g, &loaded), r)
166            })
167        }
168
169        fn equal_limbs(&self, p: &[u64], q: &[u64]) -> bool {
170            $with!(self, g => g.equal(&g.load(p), &g.load(q)))
171        }
172
173        fn coordinates_limbs(&self, p: &[&[u64]]) -> Vec<Option<(Number, Number)>> {
174            $with!(self, g => {
175                let f = g.field();
176                let loaded: Vec<_> = p.iter().map(|q| g.load(q)).collect();
177                g.affine_all(&loaded)
178                    .iter()
179                    .map(|a| a.as_ref().map(|(x, y)| (f.leave(x), f.leave(y))))
180                    .collect()
181            })
182        }
183
184        fn prepare_limbs(&self, p: &[u64], bits: usize) -> $crate::math::ec::group::Table {
185            $with!(self, g => $crate::math::ec::group::prepare(&g, &g.load(p), bits))
186        }
187
188        fn prepared_limbs(
189            &self,
190            r: &mut [u64],
191            table: &$crate::math::ec::group::Table,
192            k: &[u64],
193            negative: bool,
194        ) {
195            $with!(self, g => {
196                g.store(&$crate::math::ec::group::prepared_mul(&g, table, k, negative), r)
197            })
198        }
199    };
200}
201pub(super) use arithmetic;
202
203/// An elliptic curve over a prime field: [`Weierstrass`](super::Weierstrass),
204/// [`Montgomery`](super::Montgomery) or [`Edwards`](super::Edwards). The trait is sealed.
205///
206/// Numbers come back in the byte order of the curve's prime, reduced below it.
207pub trait Curve: Arithmetic {
208    /// The discriminant of the curve modulo `p`, not zero as the curve is not singular.
209    fn discriminant(&self) -> Number;
210
211    /// The `j`-invariant modulo `p`: two curves with the same one are isomorphic over the
212    /// algebraic closure of the field.
213    fn j_invariant(&self) -> Number;
214
215    /// The prime of the field.
216    fn modulus(&self) -> &Number {
217        &self.base().p
218    }
219
220    /// The neutral element of the curve's group: the point at infinity, or `(0, 1)` on an Edwards
221    /// curve.
222    fn identity(&self) -> Point<'_, Self> {
223        Point::from_limbs(self, self.identity_limbs())
224    }
225
226    /// The point `(x, y)`, reduced modulo `p`.
227    ///
228    /// # Errors
229    ///
230    /// [`NotOnCurve`] when it doesn't satisfy the curve's equation.
231    fn point(&self, x: &Number, y: &Number) -> Result<Point<'_, Self>, NotOnCurve> {
232        if !self.satisfied(x, y) {
233            return Err(NotOnCurve);
234        }
235        Ok(Point::from_limbs(self, self.affine_limbs(x, y)))
236    }
237
238    /// The point with the given coordinate, reduced modulo `p`, whose other coordinate has the
239    /// parity `odd`: `x` is given and `y` computed on Weierstrass and Montgomery curves, and the
240    /// other way round on Edwards curves, or `None` when there is no such point.
241    fn lift(&self, coordinate: &Number, odd: bool) -> Option<Point<'_, Self>> {
242        self.lift_limbs(coordinate, odd)
243            .map(|l| Point::from_limbs(self, l))
244    }
245
246    /// The point in the bytes of [`Point::compress`] or [`Point::to_bytes`], or `None` when they
247    /// are not the encoding of a point of this curve.
248    fn point_from_bytes(&self, bytes: &[u8]) -> Option<Point<'_, Self>> {
249        self.decode(bytes).map(|l| Point::from_limbs(self, l))
250    }
251
252    /// The sum of `k p` over the terms: Straus's method for a few, Pippenger's for many, much
253    /// faster than as many products.
254    ///
255    /// # Panics
256    ///
257    /// Panics if a point is not on this curve.
258    fn multi_mul<'c>(&'c self, terms: &[(&Number, &Point<'c, Self>)]) -> Point<'c, Self> {
259        let scalars: Vec<Vec<u64>> = terms.iter().map(|t| limbs_of(t.0)).collect();
260        let mut stored = Vec::with_capacity(terms.len());
261        for (k, t) in scalars.iter().zip(terms.iter()) {
262            t.1.check_curve(self);
263            stored.push((&k[..], t.0.is_negative(), &t.1.limbs[..]));
264        }
265        let mut r = self.identity_limbs();
266        self.multi_limbs(&mut r, &stored);
267        Point::from_limbs(self, r)
268    }
269}
270
271/// `y` or `-y`, whichever has the parity `odd`, or `None` for `y = 0` and an odd parity.
272pub(super) fn choose_root<F: super::field::Field>(f: &F, y: F::E, odd: bool) -> Option<F::E> {
273    if f.leave(&y).bit(0) == odd {
274        return Some(y);
275    }
276    let y = f.neg(&y);
277    (f.leave(&y).bit(0) == odd).then_some(y)
278}
279
280/// The `len` bytes of `x` in big-endian order.
281pub(super) fn fixed_be(x: &Number, len: usize) -> Vec<u8> {
282    let mut out = vec![0; len];
283    for (i, l) in limbs_of(x).iter().enumerate() {
284        for (j, b) in l.to_le_bytes().iter().enumerate() {
285            let at = 8 * i + j;
286            if at < len {
287                out[len - 1 - at] = *b;
288            }
289        }
290    }
291    out
292}
293
294/// The encoding of SEC 1: `0` for the point at infinity, `2` or `3`, by the parity of `y`, then
295/// `x`, or `4` then `x` and `y`, in big-endian order and the `len` bytes of the field.
296pub(super) fn sec1_encode(len: usize, xy: Option<(&Number, &Number)>, compressed: bool) -> Vec<u8> {
297    let Some((x, y)) = xy else {
298        return vec![0];
299    };
300    let mut out = Vec::with_capacity(1 + 2 * len);
301    if compressed {
302        out.push(2 + u8::from(y.bit(0)));
303        out.extend_from_slice(&fixed_be(x, len));
304    } else {
305        out.push(4);
306        out.extend_from_slice(&fixed_be(x, len));
307        out.extend_from_slice(&fixed_be(y, len));
308    }
309    out
310}
311
312/// The point in the encoding of SEC 1, on `curve`, if the bytes are one of a point on it.
313pub(super) fn sec1_decode<C: Arithmetic>(curve: &C, bytes: &[u8]) -> Option<Vec<u64>> {
314    let len = curve.base().bytes();
315    let (&tag, rest) = bytes.split_first()?;
316    let order = curve.base().p.byte_order;
317    let number = |b: &[u8]| {
318        let mut n = Number::new(b.to_vec(), ByteOrder::BigEndian);
319        if order == ByteOrder::LittleEndian {
320            n.value.reverse();
321            n.byte_order = order;
322        }
323        (n < curve.base().p).then_some(n)
324    };
325    match tag {
326        0 if rest.is_empty() => Some(curve.identity_limbs()),
327        2 | 3 if rest.len() == len => curve.lift_limbs(&number(rest)?, tag == 3),
328        4 if rest.len() == 2 * len => {
329            let (x, y) = (number(&rest[..len])?, number(&rest[len..])?);
330            curve.satisfied(&x, &y).then(|| curve.affine_limbs(&x, &y))
331        }
332        _ => None,
333    }
334}
a/math/ec/curve.rs

a/math/ec/
curve.rs
