primeorder/
point_arithmetic.rs

1//! Point arithmetic implementation optimised for different curve equations
2//!
3//! Support for formulas specialized to the short Weierstrass equation's
4//! 𝒂-coefficient.
5
6use elliptic_curve::{Field, subtle::ConditionallySelectable};
7
8use crate::{AffinePoint, PrimeCurveParams, ProjectivePoint};
9
10mod sealed {
11    use crate::{AffinePoint, PrimeCurveParams, ProjectivePoint};
12
13    /// Elliptic point arithmetic implementation
14    ///
15    /// Provides implementation of point arithmetic (point addition, point doubling) which
16    /// might be optimized for the curve.
17    pub trait PointArithmetic<C: PrimeCurveParams> {
18        /// Assigns `lhs + rhs` to `lhs`.
19        fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>);
20
21        /// Assigns `lhs + rhs` to `lhs`.
22        fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>);
23
24        /// Computes `point + point` and assigns it to `point`.
25        fn double_in_place(point: &mut ProjectivePoint<C>);
26    }
27}
28
29/// Allow crate-local visibility
30pub(crate) use sealed::PointArithmetic;
31
32// Debug-only checks to ensure we don't accidentally use formulas specialized for a different `a`.
33#[inline(always)]
34fn debug_assert_equation_a_is_minus_three<C: PrimeCurveParams>() {
35    debug_assert_eq!(
36        C::EQUATION_A,
37        -C::FieldElement::from(3),
38        "this implementation is only valid for C::EQUATION_A = -3"
39    );
40}
41
42#[inline(always)]
43fn debug_assert_equation_a_is_zero<C: PrimeCurveParams>() {
44    debug_assert_eq!(
45        C::EQUATION_A,
46        C::FieldElement::ZERO,
47        "this implementation is only valid for C::EQUATION_A = 0"
48    );
49}
50
51/// The 𝒂-coefficient of the short Weierstrass equation does not have specific properties which
52/// allow for an optimized implementation.
53#[derive(Clone, Copy, Debug)]
54pub struct EquationAIsGeneric;
55
56impl<C: PrimeCurveParams> PointArithmetic<C> for EquationAIsGeneric {
57    /// Implements complete addition for any curve
58    ///
59    /// Implements the complete addition formula from [Renes-Costello-Batina 2015]
60    /// (Algorithm 1). The comments after each line indicate which algorithm steps
61    /// are being performed.
62    ///
63    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
64    fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>) {
65        let b3 = C::FieldElement::from(3) * C::EQUATION_B;
66
67        let t0 = lhs.x * rhs.x; // 1
68        let t1 = lhs.y * rhs.y; // 2
69        let t2 = lhs.z * rhs.z; // 3
70        let t3 = lhs.x + lhs.y; // 4
71        let t4 = rhs.x + rhs.y; // 5
72        let t3 = t3 * t4; // 6
73        let t4 = t0 + t1; // 7
74        let t3 = t3 - t4; // 8
75        let t4 = lhs.x + lhs.z; // 9
76        let t5 = rhs.x + rhs.z; // 10
77        let t4 = t4 * t5; // 11
78        let t5 = t0 + t2; // 12
79        let t4 = t4 - t5; // 13
80        let t5 = lhs.y + lhs.z; // 14
81        let x3 = rhs.y + rhs.z; // 15
82        let t5 = t5 * x3; // 16
83        let x3 = t1 + t2; // 17
84        let t5 = t5 - x3; // 18
85        let z3 = C::EQUATION_A * t4; // 19
86        let x3 = b3 * t2; // 20
87        let z3 = x3 + z3; // 21
88        let x3 = t1 - z3; // 22
89        let z3 = t1 + z3; // 23
90        let y3 = x3 * z3; // 24
91        let t1 = t0 + t0; // 25
92        let t1 = t1 + t0; // 26
93        let t2 = C::EQUATION_A * t2; // 27
94        let t4 = b3 * t4; // 28
95        let t1 = t1 + t2; // 29
96        let t2 = t0 - t2; // 30
97        let t2 = C::EQUATION_A * t2; // 31
98        let t4 = t4 + t2; // 32
99        let t0 = t1 * t4; // 33
100        let y3 = y3 + t0; // 34
101        let t0 = t5 * t4; // 35
102        let x3 = t3 * x3; // 36
103        let x3 = x3 - t0; // 37
104        let t0 = t3 * t1; // 38
105        let z3 = t5 * z3; // 39
106        let z3 = z3 + t0; // 40
107
108        lhs.x = x3;
109        lhs.y = y3;
110        lhs.z = z3;
111    }
112
113    /// Implements complete mixed addition for curves with any `a`
114    ///
115    /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015]
116    /// (Algorithm 2). The comments after each line indicate which algorithm
117    /// steps are being performed.
118    ///
119    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
120    fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>) {
121        let b3 = C::EQUATION_B * C::FieldElement::from(3);
122
123        let t0 = lhs.x * rhs.x; // 1
124        let t1 = lhs.y * rhs.y; // 2
125        let t3 = rhs.x + rhs.y; // 3
126        let t4 = lhs.x + lhs.y; // 4
127        let t3 = t3 * t4; // 5
128        let t4 = t0 + t1; // 6
129        let t3 = t3 - t4; // 7
130        let t4 = rhs.x * lhs.z; // 8
131        let t4 = t4 + lhs.x; // 9
132        let t5 = rhs.y * lhs.z; // 10
133        let t5 = t5 + lhs.y; // 11
134        let z3 = C::EQUATION_A * t4; // 12
135        let x3 = b3 * lhs.z; // 13
136        let z3 = x3 + z3; // 14
137        let x3 = t1 - z3; // 15
138        let z3 = t1 + z3; // 16
139        let y3 = x3 * z3; // 17
140        let t1 = t0 + t0; // 18
141        let t1 = t1 + t0; // 19
142        let t2 = C::EQUATION_A * lhs.z; // 20
143        let t4 = b3 * t4; // 21
144        let t1 = t1 + t2; // 22
145        let t2 = t0 - t2; // 23
146        let t2 = C::EQUATION_A * t2; // 24
147        let t4 = t4 + t2; // 25
148        let t0 = t1 * t4; // 26
149        let y3 = y3 + t0; // 27
150        let t0 = t5 * t4; // 28
151        let x3 = t3 * x3; // 29
152        let x3 = x3 - t0; // 30
153        let t0 = t3 * t1; // 31
154        let z3 = t5 * z3; // 32
155        let z3 = z3 + t0; // 33
156
157        lhs.x.conditional_assign(&x3, !rhs.is_identity());
158        lhs.y.conditional_assign(&y3, !rhs.is_identity());
159        lhs.z.conditional_assign(&z3, !rhs.is_identity());
160    }
161
162    /// Implements point doubling for curves with any `a`
163    ///
164    /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015]
165    /// (Algorithm 3). The comments after each line indicate which algorithm
166    /// steps are being performed.
167    ///
168    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
169    fn double_in_place(point: &mut ProjectivePoint<C>) {
170        let b3 = C::EQUATION_B * C::FieldElement::from(3);
171
172        let t0 = point.x.square(); // 1
173        let t1 = point.y.square(); // 2
174        let t2 = point.z.square(); // 3
175        let t3 = point.x * point.y; // 4
176        let t3 = t3 + t3; // 5
177        let z3 = point.x * point.z; // 6
178        let z3 = z3 + z3; // 7
179        let x3 = C::EQUATION_A * z3; // 8
180        let y3 = b3 * t2; // 9
181        let y3 = x3 + y3; // 10
182        let x3 = t1 - y3; // 11
183        let y3 = t1 + y3; // 12
184        let y3 = x3 * y3; // 13
185        let x3 = t3 * x3; // 14
186        let z3 = b3 * z3; // 15
187        let t2 = C::EQUATION_A * t2; // 16
188        let t3 = t0 - t2; // 17
189        let t3 = C::EQUATION_A * t3; // 18
190        let t3 = t3 + z3; // 19
191        let z3 = t0 + t0; // 20
192        let t0 = z3 + t0; // 21
193        let t0 = t0 + t2; // 22
194        let t0 = t0 * t3; // 23
195        let y3 = y3 + t0; // 24
196        let t2 = point.y * point.z; // 25
197        let t2 = t2 + t2; // 26
198        let t0 = t2 * t3; // 27
199        let x3 = x3 - t0; // 28
200        let z3 = t2 * t1; // 29
201        let z3 = z3 + z3; // 30
202        let z3 = z3 + z3; // 31
203
204        point.x = x3;
205        point.y = y3;
206        point.z = z3;
207    }
208}
209
210/// The 𝒂-coefficient of the short Weierstrass equation is `-3`.
211#[derive(Clone, Copy, Debug)]
212pub struct EquationAIsMinusThree;
213
214impl<C: PrimeCurveParams> PointArithmetic<C> for EquationAIsMinusThree {
215    /// Implements complete addition for curves with `a = -3`
216    ///
217    /// Implements the complete addition formula from [Renes-Costello-Batina 2015]
218    /// (Algorithm 4). The comments after each line indicate which algorithm steps
219    /// are being performed.
220    ///
221    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
222    fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>) {
223        debug_assert_equation_a_is_minus_three::<C>();
224
225        let xx = lhs.x * rhs.x; // 1
226        let yy = lhs.y * rhs.y; // 2
227        let zz = lhs.z * rhs.z; // 3
228        let xy_pairs = ((lhs.x + lhs.y) * (rhs.x + rhs.y)) - (xx + yy); // 4, 5, 6, 7, 8
229        let yz_pairs = ((lhs.y + lhs.z) * (rhs.y + rhs.z)) - (yy + zz); // 9, 10, 11, 12, 13
230        let xz_pairs = ((lhs.x + lhs.z) * (rhs.x + rhs.z)) - (xx + zz); // 14, 15, 16, 17, 18
231
232        let bzz_part = xz_pairs - (C::EQUATION_B * zz); // 19, 20
233        let bzz3_part = bzz_part.double() + bzz_part; // 21, 22
234        let yy_m_bzz3 = yy - bzz3_part; // 23
235        let yy_p_bzz3 = yy + bzz3_part; // 24
236
237        let zz3 = zz.double() + zz; // 26, 27
238        let bxz_part = (C::EQUATION_B * xz_pairs) - (zz3 + xx); // 25, 28, 29
239        let bxz3_part = bxz_part.double() + bxz_part; // 30, 31
240        let xx3_m_zz3 = xx.double() + xx - zz3; // 32, 33, 34
241
242        lhs.x = (yy_p_bzz3 * xy_pairs) - (yz_pairs * bxz3_part); // 35, 39, 40
243        lhs.y = (yy_p_bzz3 * yy_m_bzz3) + (xx3_m_zz3 * bxz3_part); // 36, 37, 38
244        lhs.z = (yy_m_bzz3 * yz_pairs) + (xy_pairs * xx3_m_zz3); // 41, 42, 43
245    }
246
247    /// Implements complete mixed addition for curves with `a = -3`
248    ///
249    /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015]
250    /// (Algorithm 5). The comments after each line indicate which algorithm
251    /// steps are being performed.
252    ///
253    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
254    fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>) {
255        debug_assert_equation_a_is_minus_three::<C>();
256
257        let xx = lhs.x * rhs.x; // 1
258        let yy = lhs.y * rhs.y; // 2
259        let xy_pairs = ((lhs.x + lhs.y) * (rhs.x + rhs.y)) - (xx + yy); // 3, 4, 5, 6, 7
260        let yz_pairs = (rhs.y * lhs.z) + lhs.y; // 8, 9 (t4)
261        let xz_pairs = (rhs.x * lhs.z) + lhs.x; // 10, 11 (y3)
262
263        let bz_part = xz_pairs - (C::EQUATION_B * lhs.z); // 12, 13
264        let bz3_part = bz_part.double() + bz_part; // 14, 15
265        let yy_m_bzz3 = yy - bz3_part; // 16
266        let yy_p_bzz3 = yy + bz3_part; // 17
267
268        let z3 = lhs.z.double() + lhs.z; // 19, 20
269        let bxz_part = (C::EQUATION_B * xz_pairs) - (z3 + xx); // 18, 21, 22
270        let bxz3_part = bxz_part.double() + bxz_part; // 23, 24
271        let xx3_m_zz3 = xx.double() + xx - z3; // 25, 26, 27
272
273        let x = (yy_p_bzz3 * xy_pairs) - (yz_pairs * bxz3_part); // 28, 32, 33
274        let y = (yy_p_bzz3 * yy_m_bzz3) + (xx3_m_zz3 * bxz3_part); // 29, 30, 31
275        let z = (yy_m_bzz3 * yz_pairs) + (xy_pairs * xx3_m_zz3); // 34, 35, 36
276
277        lhs.x.conditional_assign(&x, !rhs.is_identity());
278        lhs.y.conditional_assign(&y, !rhs.is_identity());
279        lhs.z.conditional_assign(&z, !rhs.is_identity());
280    }
281
282    /// Implements point doubling for curves with `a = -3`
283    ///
284    /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015]
285    /// (Algorithm 6). The comments after each line indicate which algorithm
286    /// steps are being performed.
287    ///
288    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
289    fn double_in_place(point: &mut ProjectivePoint<C>) {
290        debug_assert_equation_a_is_minus_three::<C>();
291
292        let xx = point.x.square(); // 1
293        let yy = point.y.square(); // 2
294        let zz = point.z.square(); // 3
295        let xy2 = (point.x * point.y).double(); // 4, 5
296        let xz2 = (point.x * point.z).double(); // 6, 7
297
298        let bzz_part = (C::EQUATION_B * zz) - xz2; // 8, 9
299        let bzz3_part = bzz_part.double() + bzz_part; // 10, 11
300        let yy_m_bzz3 = yy - bzz3_part; // 12
301        let yy_p_bzz3 = yy + bzz3_part; // 13
302        let y_frag = yy_p_bzz3 * yy_m_bzz3; // 14
303        let x_frag = yy_m_bzz3 * xy2; // 15
304
305        let zz3 = zz.double() + zz; // 16, 17
306        let bxz2_part = (C::EQUATION_B * xz2) - (zz3 + xx); // 18, 19, 20
307        let bxz6_part = bxz2_part.double() + bxz2_part; // 21, 22
308        let xx3_m_zz3 = xx.double() + xx - zz3; // 23, 24, 25
309
310        let y = y_frag + (xx3_m_zz3 * bxz6_part); // 26, 27
311        let yz2 = (point.y * point.z).double(); // 28, 29
312        let x = x_frag - (bxz6_part * yz2); // 30, 31
313        let z = (yz2 * yy).double().double(); // 32, 33, 34
314
315        point.x = x;
316        point.y = y;
317        point.z = z;
318    }
319}
320
321/// The 𝒂-coefficient of the short Weierstrass equation is `0`.
322#[derive(Clone, Copy, Debug)]
323pub struct EquationAIsZero;
324
325impl<C: PrimeCurveParams> PointArithmetic<C> for EquationAIsZero {
326    /// Implements complete addition for curves with `a = 0`
327    ///
328    /// Implements the complete addition formula from [Renes-Costello-Batina 2015]
329    /// (Algorithm 7). The comments after each line indicate which algorithm steps
330    /// are being performed.
331    ///
332    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
333    fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>) {
334        debug_assert_equation_a_is_zero::<C>();
335
336        let b3 = C::FieldElement::from(3) * C::EQUATION_B;
337
338        let t0 = lhs.x * rhs.x; // 1
339        let t1 = lhs.y * rhs.y; // 2
340        let t2 = lhs.z * rhs.z; // 3
341        let t3 = lhs.x + lhs.y; // 4
342        let t4 = rhs.x + rhs.y; // 5
343        let t3 = t3 * t4; // 6
344        let t4 = t0 + t1; // 7
345        let t3 = t3 - t4; // 8
346        let t4 = lhs.y + lhs.z; // 9
347        let x3 = rhs.y + rhs.z; // 10
348        let t4 = t4 * x3; // 11
349        let x3 = t1 + t2; // 12
350        let t4 = t4 - x3; // 13
351        let x3 = lhs.x + lhs.z; // 14
352        let y3 = rhs.x + rhs.z; // 15
353        let x3 = x3 * y3; // 16
354        let y3 = t0 + t2; // 17
355        let y3 = x3 - y3; // 18
356        let x3 = t0.double(); // 19
357        let t0 = x3 + t0; // 20
358        let t2 = b3 * t2; // 21
359        let z3 = t1 + t2; // 22
360        let t1 = t1 - t2; // 23
361        let y3 = b3 * y3; // 24
362        let x3 = t4 * y3; // 25
363        let t2 = t3 * t1; // 26
364        let x3 = t2 - x3; // 27
365        let y3 = y3 * t0; // 28
366        let t1 = t1 * z3; // 29
367        let y3 = t1 + y3; // 30
368        let t0 = t0 * t3; // 31
369        let z3 = z3 * t4; // 32
370        let z3 = z3 + t0; // 33
371
372        lhs.x = x3;
373        lhs.y = y3;
374        lhs.z = z3;
375    }
376
377    /// Implements complete mixed addition for curves with `a = 0`
378    ///
379    /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015]
380    /// (Algorithm 8). The comments after each line indicate which algorithm
381    /// steps are being performed.
382    ///
383    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
384    fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>) {
385        debug_assert_equation_a_is_zero::<C>();
386
387        let b3 = C::EQUATION_B * C::FieldElement::from(3);
388
389        let t0 = lhs.x * rhs.x; // 1
390        let t1 = lhs.y * rhs.y; // 2
391        let t3 = rhs.x + rhs.y; // 3
392        let t4 = lhs.x + lhs.y; // 4
393        let t3 = t3 * t4; // 5
394        let t4 = t0 + t1; // 6
395        let t3 = t3 - t4; // 7
396        let t4 = rhs.y * lhs.z; // 8
397        let t4 = t4 + lhs.y; // 9
398        let y3 = rhs.x * lhs.z; // 10
399        let y3 = y3 + lhs.x; // 11
400        let x3 = t0.double(); // 12
401        let t0 = x3 + t0; // 13
402        let t2 = b3 * lhs.z; // 14
403        let z3 = t1 + t2; // 15
404        let t1 = t1 - t2; // 16
405        let y3 = b3 * y3; // 17
406        let x3 = t4 * y3; // 18
407        let t2 = t3 * t1; // 19
408        let x3 = t2 - x3; // 20
409        let y3 = y3 * t0; // 21
410        let t1 = t1 * z3; // 22
411        let y3 = t1 + y3; // 23
412        let t0 = t0 * t3; // 24
413        let z3 = z3 * t4; // 25
414        let z3 = z3 + t0; // 26
415
416        lhs.x.conditional_assign(&x3, !rhs.is_identity());
417        lhs.y.conditional_assign(&y3, !rhs.is_identity());
418        lhs.z.conditional_assign(&z3, !rhs.is_identity());
419    }
420
421    /// Implements point doubling for curves with `a = 0`
422    ///
423    /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015]
424    /// (Algorithm 9). The comments after each line indicate which algorithm
425    /// steps are being performed.
426    ///
427    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
428    fn double_in_place(point: &mut ProjectivePoint<C>) {
429        debug_assert_equation_a_is_zero::<C>();
430
431        let b3 = C::EQUATION_B * C::FieldElement::from(3);
432
433        let t0 = point.y.square(); // 1
434        let z3 = t0.double(); // 2
435        let z3 = z3.double(); // 3
436        let z3 = z3.double(); // 4
437        let t1 = point.y * point.z; // 5
438        let t2 = point.z.square(); // 6
439        let t2 = b3 * t2; // 7
440        let x3 = t2 * z3; // 8
441        let y3 = t0 + t2; // 9
442        let z3 = t1 * z3; // 10
443        let t1 = t2.double(); // 11
444        let t2 = t1 + t2; // 12
445        let t0 = t0 - t2; // 13
446        let y3 = t0 * y3; // 14
447        let y3 = x3 + y3; // 15
448        let t1 = point.x * point.y; // 16
449        let x3 = t0 * t1; // 17
450        let x3 = x3.double(); // 18
451
452        point.x = x3;
453        point.y = y3;
454        point.z = z3;
455    }
456}
primeorder/point_arithmetic.rs

primeorder/
point_arithmetic.rs
