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

primeorder/
point_arithmetic.rs
