Botan 3.14.1
Crypto and TLS for C&
pcurves_algos.h
Go to the documentation of this file.
1/*
2* (C) 2024,2025 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_PCURVES_ALGOS_H_
8#define BOTAN_PCURVES_ALGOS_H_
9
10#include <botan/types.h>
11#include <botan/internal/ct_utils.h>
12#include <algorithm>
13#include <span>
14#include <utility>
15#include <vector>
16
17namespace Botan {
18
19/**
20* Field inversion concept
21*
22* This concept checks if the curve class supports fe_invert2
23*/
24template <typename C>
25concept curve_supports_fe_invert2 = requires(const typename C::FieldElement& fe) {
26 { C::fe_invert2(fe) } -> std::same_as<typename C::FieldElement>;
27};
28
29/**
30* Field inversion
31*
32* Uses the specialized fe_invert2 if available, or otherwise the standard
33* (FLT-based) field inversion.
34*/
35template <typename C>
36inline constexpr auto invert_field_element(const typename C::FieldElement& fe) {
37 if constexpr(curve_supports_fe_invert2<C>) {
38 return C::fe_invert2(fe) * fe;
39 } else {
40 return fe.invert();
41 }
42}
43
44/**
45* Field square root
46*
47* This concept checks if the curve class supports fe_sqrt
48*/
49template <typename C>
50concept curve_supports_fe_sqrt = requires(const typename C::FieldElement& fe) {
51 { C::fe_sqrt(fe) } -> std::same_as<typename C::FieldElement>;
52};
53
54/**
55* Field square root
56*
57* Uses the specialized fe_sqrt if available, or otherwise the standard
58* square root
59*/
60template <typename C>
61inline constexpr CT::Option<typename C::FieldElement> sqrt_field_element(const typename C::FieldElement& fe) {
62 if constexpr(curve_supports_fe_sqrt<C>) {
63 auto z = C::fe_sqrt(fe);
64 // Zero out the return value if it would otherwise be incorrect
65 const CT::Choice correct = (z.square() == fe);
66 z.conditional_assign(!correct, C::FieldElement::zero());
67 return CT::Option(z, correct);
68 } else {
69 return fe.sqrt();
70 }
71}
72
73/**
74* Convert a projective point into affine
75*/
76template <typename C>
77inline constexpr auto to_affine(const typename C::ProjectivePoint& pt) {
78 // Not strictly required right? - default should work as long
79 // as (0,0) is identity and invert returns 0 on 0
80
81 if constexpr(curve_supports_fe_invert2<C>) {
82 const auto z2_inv = C::fe_invert2(pt.z());
83 const auto z3_inv = z2_inv.square() * pt.z();
84 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
85 } else {
86 const auto z_inv = invert_field_element<C>(pt.z());
87 const auto z2_inv = z_inv.square();
88 const auto z3_inv = z_inv * z2_inv;
89 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
90 }
91}
92
93/**
94* Convert a projective point into affine and return x coordinate only
95*/
96template <typename C>
97auto to_affine_x(const typename C::ProjectivePoint& pt) {
98 if constexpr(curve_supports_fe_invert2<C>) {
99 return pt.x() * C::fe_invert2(pt.z());
100 } else {
101 const auto z_inv = invert_field_element<C>(pt.z());
102 const auto z2_inv = z_inv.square();
103 return pt.x() * z2_inv;
104 }
105}
106
107template <typename C, bool VariableTime = false>
108auto to_affine_batch(std::span<const typename C::ProjectivePoint> projective) {
109 using AffinePoint = typename C::AffinePoint;
110
111 const size_t N = projective.size();
112 std::vector<AffinePoint> affine;
113 affine.reserve(N);
114
115 CT::Choice any_identity = CT::Choice::no();
116
117 for(const auto& pt : projective) {
118 any_identity = any_identity || pt.is_identity();
119 }
120
121 // Conditional acceptable: N is public. State of points is not necessarily
122 // public, but we don't leak which point was the identity. In practice with
123 // the algorithms currently in use, the only time an identity can occur is
124 // during mul2 where the two points g/h have a small relation (ie h = g*k for
125 // some k < 16)
126
127 if(N <= 2 || any_identity.as_bool()) {
128 // If there are identity elements, using the batch inversion gets
129 // tricky. It can be done, but this should be a rare situation so
130 // just punt to the serial conversion if it occurs
131 for(size_t i = 0; i != N; ++i) {
132 affine.push_back(to_affine<C>(projective[i]));
133 }
134 } else {
135 std::vector<typename C::FieldElement> c;
136 c.reserve(N);
137
138 /*
139 Batch projective->affine using Montgomery's trick
140
141 See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
142 (Hankerson, Menezes, Vanstone)
143 */
144
145 c.push_back(projective[0].z());
146 for(size_t i = 1; i != N; ++i) {
147 c.push_back(c[i - 1] * projective[i].z());
148 }
149
150 auto s_inv = [&]() {
151 if constexpr(VariableTime) {
152 return c[N - 1].invert_vartime();
153 } else {
154 return invert_field_element<C>(c[N - 1]);
155 }
156 }();
157
158 for(size_t i = N - 1; i > 0; --i) {
159 const auto& p = projective[i];
160
161 const auto z_inv = s_inv * c[i - 1];
162 const auto z2_inv = z_inv.square();
163 const auto z3_inv = z_inv * z2_inv;
164
165 s_inv = s_inv * p.z();
166
167 affine.push_back(AffinePoint(p.x() * z2_inv, p.y() * z3_inv));
168 }
169
170 const auto z2_inv = s_inv.square();
171 const auto z3_inv = s_inv * z2_inv;
172 affine.push_back(AffinePoint(projective[0].x() * z2_inv, projective[0].y() * z3_inv));
173 std::reverse(affine.begin(), affine.end());
174 return affine;
175 }
176
177 return affine;
178}
179
180/*
181Projective point addition
182
183https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
184
185Cost: 12M + 4S + 6add + 1*2
186*/
187template <typename ProjectivePoint, typename FieldElement>
188inline constexpr ProjectivePoint point_add(const ProjectivePoint& a, const ProjectivePoint& b) {
189 const auto a_is_identity = a.is_identity();
190 const auto b_is_identity = b.is_identity();
191
192 const auto Z1Z1 = a.z().square();
193 const auto Z2Z2 = b.z().square();
194 const auto U1 = a.x() * Z2Z2;
195 const auto U2 = b.x() * Z1Z1;
196 const auto S1 = a.y() * b.z() * Z2Z2;
197 const auto S2 = b.y() * a.z() * Z1Z1;
198 const auto H = U2 - U1;
199 const auto r = S2 - S1;
200
201 /* Risky conditional
202 *
203 * This implementation uses projective coordinates, which do not have an efficient complete
204 * addition formula. We rely on the design of the multiplication algorithms to avoid doublings.
205 *
206 * This conditional only comes into play for the actual doubling case, not x + (-x) which
207 * is another exceptional case in some circumstances. Here if a == -b then H == 0 && r != 0,
208 * in which case at the end we'll set z to a.z * b.z * H = 0, resulting in the correct
209 * output (the identity element)
210 */
211 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
212 return a.dbl();
213 }
214
215 const auto HH = H.square();
216 const auto HHH = H * HH;
217 const auto V = U1 * HH;
218 const auto t2 = r.square();
219 const auto t3 = V + V;
220 const auto t4 = t2 - HHH;
221 auto X3 = t4 - t3;
222 const auto t5 = V - X3;
223 const auto t6 = S1 * HHH;
224 const auto t7 = r * t5;
225 auto Y3 = t7 - t6;
226 const auto t8 = b.z() * H;
227 auto Z3 = a.z() * t8;
228
229 // if a is identity then return b
230 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), b.y(), b.z());
231
232 // if b is identity then return a
233 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
234
235 return ProjectivePoint(X3, Y3, Z3);
236}
237
238/*
239* Mixed (projective + affine) point addition, additionally returning H
240*
241* If neither input is the identity, the Z coordinate of the sum is a.z * H
242*
243* The parameter curve_a is the a coefficient of the curve the points are on; it
244* is only used in the exceptional case where the addition is a doubling.
245*/
246template <typename ProjectivePoint, typename AffinePoint, typename FieldElement>
247inline constexpr std::pair<ProjectivePoint, FieldElement> point_add_mixed_h(const ProjectivePoint& a,
248 const AffinePoint& b,
249 const FieldElement& one,
250 const FieldElement& curve_a) {
251 const auto a_is_identity = a.is_identity();
252 const auto b_is_identity = b.is_identity();
253
254 /*
255 https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
256
257 Cost: 8M + 3S + 6add + 1*2
258 */
259
260 const auto Z1Z1 = a.z().square();
261 const auto U2 = b.x() * Z1Z1;
262 const auto S2 = b.y() * a.z() * Z1Z1;
263 const auto H = U2 - a.x();
264 const auto r = S2 - a.y();
265
266 /* Risky conditional
267 *
268 * This implementation uses projective coordinates, which do not have an efficient complete
269 * addition formula. We rely on the design of the multiplication algorithms to avoid doublings.
270 *
271 * This conditional only comes into play for the actual doubling case, not x + (-x) which
272 * is another exceptional case in some circumstances. Here if a == -b then H == 0 && r != 0,
273 * in which case at the end we'll set z to a.z * H = 0, resulting in the correct output
274 * (the identity element)
275 */
276 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
277 return {a.dbl_iso(curve_a), H};
278 }
279
280 const auto HH = H.square();
281 const auto HHH = H * HH;
282 const auto V = a.x() * HH;
283 const auto t2 = r.square();
284 const auto t3 = V + V;
285 const auto t4 = t2 - HHH;
286 auto X3 = t4 - t3;
287 const auto t5 = V - X3;
288 const auto t6 = a.y() * HHH;
289 const auto t7 = r * t5;
290 auto Y3 = t7 - t6;
291 auto Z3 = a.z() * H;
292
293 // if a is identity then return b
294 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), b.y(), one);
295
296 // if b is identity then return a
297 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
298
299 return {ProjectivePoint(X3, Y3, Z3), H};
300}
301
302template <typename ProjectivePoint, typename AffinePoint, typename FieldElement>
303inline constexpr ProjectivePoint point_add_mixed(const ProjectivePoint& a,
304 const AffinePoint& b,
305 const FieldElement& one,
306 const FieldElement& curve_a) {
308}
309
310/*
311* As with point_add_mixed_h, curve_a is only used if the addition is a doubling
312*/
313template <typename ProjectivePoint, typename AffinePoint, typename FieldElement>
314inline constexpr ProjectivePoint point_add_or_sub_mixed(const ProjectivePoint& a,
315 const AffinePoint& b,
316 CT::Choice sub,
317 const FieldElement& one,
318 const FieldElement& curve_a) {
319 const auto a_is_identity = a.is_identity();
320 const auto b_is_identity = b.is_identity();
321
322 /*
323 https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
324
325 Cost: 8M + 3S + 6add + 1*2
326 */
327
328 auto by = b.y();
329 by.conditional_assign(sub, by.negate());
330
331 const auto Z1Z1 = a.z().square();
332 const auto U2 = b.x() * Z1Z1;
333 const auto S2 = by * a.z() * Z1Z1;
334 const auto H = U2 - a.x();
335 const auto r = S2 - a.y();
336
337 /* Risky conditional
338 *
339 * This implementation uses projective coordinates, which do not have an efficient complete
340 * addition formula. We rely on the design of the multiplication algorithms to avoid doublings.
341 *
342 * This conditional only comes into play for the actual doubling case, not x + (-x) which
343 * is another exceptional case in some circumstances. Here if a == -b then H == 0 && r != 0,
344 * in which case at the end we'll set z to a.z * H = 0, resulting in the correct output
345 * (the identity element)
346 */
347 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
348 return a.dbl_iso(curve_a);
349 }
350
351 const auto HH = H.square();
352 const auto HHH = H * HH;
353 const auto V = a.x() * HH;
354 const auto t2 = r.square();
355 const auto t3 = V + V;
356 const auto t4 = t2 - HHH;
357 auto X3 = t4 - t3;
358 const auto t5 = V - X3;
359 const auto t6 = a.y() * HHH;
360 const auto t7 = r * t5;
361 auto Y3 = t7 - t6;
362 auto Z3 = a.z() * H;
363
364 // if a is identity then return b
365 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), by, one);
366
367 // if b is identity then return a
368 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
369
370 return ProjectivePoint(X3, Y3, Z3);
371}
372
373/*
374Point doubling
375
376Using https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2
377
378Cost (generic A): 4M + 6S + 4A + 2*2 + 1*3 + 1*4 + 1*8
379Cost (A == -3): 4M + 4S + 5A + 2*2 + 1*3 + 1*4 + 1*8
380Cost (A == 0): 3M + 4S + 3A + 2*2 + 1*3 + 1*4 + 1*8
381*/
382
383template <typename ProjectivePoint>
384inline constexpr ProjectivePoint dbl_a_minus_3(const ProjectivePoint& pt) {
385 /*
386 if a == -3 then
387 3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2)
388 */
389 const auto z2 = pt.z().square();
390 const auto m = (pt.x() - z2).mul3() * (pt.x() + z2);
391
392 // Remaining cost: 3M + 3S + 3A + 2*2 + 1*4 + 1*8
393 const auto y2 = pt.y().square();
394 const auto s = pt.x().mul4() * y2;
395 const auto nx = m.square() - s.mul2();
396 const auto ny = m * (s - nx) - y2.square().mul8();
397 const auto nz = pt.y().mul2() * pt.z();
398
399 return ProjectivePoint(nx, ny, nz);
400}
401
402template <typename ProjectivePoint>
403inline constexpr ProjectivePoint dbl_a_zero(const ProjectivePoint& pt) {
404 // If a == 0 then 3*x^2 + a*z^4 == 3*x^2
405 // Cost: 1S + 1*3
406 const auto m = pt.x().square().mul3();
407
408 // Remaining cost: 3M + 3S + 3A + 2*2 + 1*4 + 1*8
409 const auto y2 = pt.y().square();
410 const auto s = pt.x().mul4() * y2;
411 const auto nx = m.square() - s.mul2();
412 const auto ny = m * (s - nx) - y2.square().mul8();
413 const auto nz = pt.y().mul2() * pt.z();
414
415 return ProjectivePoint(nx, ny, nz);
416}
417
418template <typename ProjectivePoint, typename FieldElement>
419inline constexpr ProjectivePoint dbl_generic(const ProjectivePoint& pt, const FieldElement& A) {
420 // Cost: 1M + 3S + 1A + 1*3
421 const auto z2 = pt.z().square();
422 const auto m = pt.x().square().mul3() + A * z2.square();
423
424 // Remaining cost: 3M + 3S + 3A + 2*2 + 1*4 + 1*8
425 const auto y2 = pt.y().square();
426 const auto s = pt.x().mul4() * y2;
427 const auto nx = m.square() - s.mul2();
428 const auto ny = m * (s - nx) - y2.square().mul8();
429 const auto nz = pt.y().mul2() * pt.z();
430
431 return ProjectivePoint(nx, ny, nz);
432}
433
434/*
435Repeated doubling using an adaptation of Algorithm 3.23 in
436"Guide To Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone)
437
438Curiously the book gives the algorithm only for A == -3, but
439the largest gains come from applying it to the generic A case,
440where it saves 2 squarings per iteration.
441
442For A == 0
443Pay 1*2 + 1half to save n*(1*4 + 1*8)
444
445For A == -3:
446Pay 2S + 1*2 + 1half to save n*(1A + 1*4 + 1*8) + 1M
447
448For generic A:
449Pay 2S + 1*2 + 1half to save n*(2S + 1*4 + 1*8)
450
451The value of n is assumed to be public and should be a constant
452*/
453template <typename ProjectivePoint>
454inline constexpr ProjectivePoint dbl_n_a_minus_3(const ProjectivePoint& pt, size_t n) {
455 auto nx = pt.x();
456 auto ny = pt.y().mul2();
457 auto nz = pt.z();
458 auto w = nz.square().square();
459
460 // Conditional ok: loop iteration count is public
461 while(n > 0) {
462 const auto ny2 = ny.square();
463 const auto ny4 = ny2.square();
464 const auto t1 = (nx.square() - w).mul3();
465 const auto t2 = nx * ny2;
466 nx = t1.square() - t2.mul2();
467 nz *= ny;
468 ny = t1 * (t2 - nx).mul2() - ny4;
469 n--;
470 // Conditional ok: loop iteration count is public
471 if(n > 0) {
472 w *= ny4;
473 }
474 }
475 return ProjectivePoint(nx, ny.div2(), nz);
476}
477
478template <typename ProjectivePoint>
479inline constexpr ProjectivePoint dbl_n_a_zero(const ProjectivePoint& pt, size_t n) {
480 auto nx = pt.x();
481 auto ny = pt.y().mul2();
482 auto nz = pt.z();
483
484 // Conditional ok: loop iteration count is public
485 while(n > 0) {
486 const auto ny2 = ny.square();
487 const auto ny4 = ny2.square();
488 const auto t1 = nx.square().mul3();
489 const auto t2 = nx * ny2;
490 nx = t1.square() - t2.mul2();
491 nz *= ny;
492 ny = t1 * (t2 - nx).mul2() - ny4;
493 n--;
494 }
495 return ProjectivePoint(nx, ny.div2(), nz);
496}
497
498template <typename ProjectivePoint, typename FieldElement>
499inline constexpr ProjectivePoint dbl_n_generic(const ProjectivePoint& pt, const FieldElement& A, size_t n) {
500 auto nx = pt.x();
501 auto ny = pt.y().mul2();
502 auto nz = pt.z();
503 auto w = nz.square().square() * A;
504
505 // Conditional ok: loop iteration count is public
506 while(n > 0) {
507 const auto ny2 = ny.square();
508 const auto ny4 = ny2.square();
509 const auto t1 = nx.square().mul3() + w;
510 const auto t2 = nx * ny2;
511 nx = t1.square() - t2.mul2();
512 nz *= ny;
513 ny = t1 * (t2 - nx).mul2() - ny4;
514 n--;
515 // Conditional ok: loop iteration count is public
516 if(n > 0) {
517 w *= ny4;
518 }
519 }
520 return ProjectivePoint(nx, ny.div2(), nz);
521}
522
523} // namespace Botan
524
525#endif
static constexpr Choice no()
Definition ct_utils.h:307
constexpr bool as_bool() const
Definition ct_utils.h:329
auto to_affine_x(const typename C::ProjectivePoint &pt)
constexpr CT::Option< typename C::FieldElement > sqrt_field_element(const typename C::FieldElement &fe)
constexpr ProjectivePoint dbl_n_generic(const ProjectivePoint &pt, const FieldElement &A, size_t n)
constexpr ProjectivePoint dbl_a_minus_3(const ProjectivePoint &pt)
constexpr ProjectivePoint dbl_n_a_zero(const ProjectivePoint &pt, size_t n)
auto to_affine_batch(std::span< const typename C::ProjectivePoint > projective)
constexpr ProjectivePoint dbl_a_zero(const ProjectivePoint &pt)
constexpr auto to_affine(const typename C::ProjectivePoint &pt)
constexpr auto invert_field_element(const typename C::FieldElement &fe)
constexpr ProjectivePoint point_add_or_sub_mixed(const ProjectivePoint &a, const AffinePoint &b, CT::Choice sub, const FieldElement &one, const FieldElement &curve_a)
constexpr ProjectivePoint dbl_n_a_minus_3(const ProjectivePoint &pt, size_t n)
constexpr ProjectivePoint dbl_generic(const ProjectivePoint &pt, const FieldElement &A)
constexpr ProjectivePoint point_add(const ProjectivePoint &a, const ProjectivePoint &b)
constexpr std::pair< ProjectivePoint, FieldElement > point_add_mixed_h(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one, const FieldElement &curve_a)
constexpr ProjectivePoint point_add_mixed(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one, const FieldElement &curve_a)