Botan 3.14.1
Crypto and TLS for C&
pcurves_mul.h
Go to the documentation of this file.
1/*
2* (C) 2024,2025,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_PCURVES_MUL_H_
8#define BOTAN_PCURVES_MUL_H_
9
10#include <botan/types.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/mp_core.h>
13#include <botan/internal/pcurves_algos.h>
14#include <span>
15#include <vector>
16
17namespace Botan {
18
19/*
20* Multiplication algorithm window size parameters
21*/
22
23static constexpr size_t BasePointWindowBits = 6;
24static constexpr size_t VarPointWindowBits = 4;
25static constexpr size_t Mul2VartimeWindowBits = 5;
26static constexpr size_t Mul2PrecompWindowBits = 3;
27static constexpr size_t Mul2WindowBits = 2;
28
29/**
30* Return number of blinding bits to use
31*
32* This can return any value between 0 and the scalar bit length.
33*
34* The field arithmetic and scalar multiplication algorithms are anyway written and tested
35* to be constant time; blinding is just used as a safety net in the case that the compiler
36* rewrites constant time code to include variable time behavior. If utmost performance is
37* of concern and you are in a position to test that your specific compiler for your
38* specific architecture is not inserting variable time behavior where not expected (for
39* example by using the existing valgrind-based CT checking) it is safe to modify this
40* function to just return 0, or some very small blinding factor of 1-4 bits.
41*/
42constexpr size_t scalar_blinding_bits(size_t scalar_bits) {
43 // For blinding use 1/8 the order length for most curves; for P-521 we round down a bit
44 // so the masked scalar fits exactly in 9 or 18 words.
45
46 if(scalar_bits == 521) {
47 return 55;
48 } else {
49 return scalar_bits / 8;
50 }
51}
52
53/*
54* Base point precomputation table
55*
56* This algorithm works by precomputing a set of points such that
57* the online phase of the point multiplication can be effected by
58* a sequence of point additions.
59*
60* The tables, even for W = 1, are large and costly to precompute, so
61* this is only used for the base point.
62*
63* The online phase of the algorithm uess `ceil(SB/W)` additions,
64* and no point doublings. The table is of size
65* `ceil(SB + W - 1)/W * ((1 << W) - 1)`
66* where SB is the bit length of the (blinded) scalar.
67*
68* Each window of the scalar is associated with a window in the table.
69* The table windows are unique to that offset within the scalar.
70*
71* The simplest version to understand is when W = 1. There the table
72* consists of [P, 2*P, 4*P, ..., 2^N*P] where N is the bit length of
73* the group order. The online phase consists of conditionally adding
74* table[i] depending on if bit i of the scalar is set or not.
75*
76* When W = 2, the scalar is examined 2 bits at a time, and the table
77* for a window index `I` is [(2^I)*P, (2^(I+1))*P, (2^I+2^(I+1))*P].
78*
79* This extends similarly for larger W
80*
81* At a certain point, the side channel silent table lookup becomes the
82* dominating cost
83*
84* For all W, each window in the table has an implicit element of
85* the identity element which is used if the scalar bits were all zero.
86* This is omitted to save space; AffinePoint::ct_select is designed
87* to assist in this by returning the identity element if its index
88* argument is zero, or otherwise it returns table[idx - 1]
89*/
90template <typename C, size_t WindowBits>
91std::vector<typename C::AffinePoint> basemul_setup(const typename C::AffinePoint& p, size_t max_scalar_bits) {
92 static_assert(WindowBits >= 1 && WindowBits <= 8);
93
94 // 2^W elements, less the identity element
95 constexpr size_t WindowElements = (1 << WindowBits) - 1;
96
97 const size_t Windows = (max_scalar_bits + WindowBits - 1) / WindowBits;
98
99 const size_t TableSize = Windows * WindowElements;
100
101 std::vector<typename C::ProjectivePoint> table;
102 table.reserve(TableSize);
103
104 auto accum = C::ProjectivePoint::from_affine(p);
105
106 for(size_t i = 0; i != TableSize; i += WindowElements) {
107 table.push_back(accum);
108
109 for(size_t j = 1; j != WindowElements; ++j) {
110 // Conditional ok: loop iteration count is public
111 if(j % 2 == 1) {
112 table.emplace_back(table[i + j / 2].dbl());
113 } else {
114 table.emplace_back(table[i + j - 1] + table[i]);
115 }
116 }
117
118 accum = table[i + (WindowElements / 2)].dbl();
119 }
120
121 // Variable time batch conversion is fine since generator is public
122 return to_affine_batch<C, true>(table);
123}
124
125template <typename C, size_t WindowBits, typename BlindedScalar, typename Blinding>
126typename C::ProjectivePoint basemul_exec(std::span<const typename C::AffinePoint> table,
127 const BlindedScalar& scalar,
128 const Blinding& blinding) {
129 // 2^W elements, less the identity element
130 static constexpr size_t WindowElements = (1 << WindowBits) - 1;
131
132 // TODO: C++23 - use std::mdspan to access table?
133
134 auto accum = [&]() {
135 const size_t w_0 = scalar.get_window(0);
136 const auto tbl_0 = table.first(WindowElements);
137 auto pt = C::ProjectivePoint::from_affine(C::AffinePoint::ct_select(tbl_0, w_0));
138 blinding.randomize_rep(pt, 0);
139 return pt;
140 }();
141
142 const size_t windows = (scalar.bits() + WindowBits - 1) / WindowBits;
143
144 for(size_t i = 1; i != windows; ++i) {
145 const size_t w_i = scalar.get_window(WindowBits * i);
146 const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
147
148 /*
149 None of these additions can be doublings, because in each iteration, the
150 discrete logarithms of the points we're selecting out of the table are
151 larger than the largest possible dlog of accum.
152 */
153 accum += C::AffinePoint::ct_select(tbl_i, w_i);
154
155 // Conditional ok: loop iteration count is public
156 if(i < Blinding::Rerandomizations) {
157 blinding.randomize_rep(accum, i);
158 }
159 }
160
161 return accum;
162}
163
164/*
165* Base point precomputation table with Booth recoding
166*
167* Same structure as basemul, but uses Booth recoding to halve the
168* table size per window. Instead of storing 2^W - 1 entries per
169* window, we store 2^(W-1) entries (multiples 1..2^(W-1) of the
170* window base point). The sign is handled by conditional negation
171* after the constant-time table lookup.
172*
173* The scalar is prepared with one extra blinding bit (WindowBits+1),
174* and windows overlap by one bit to allow carry propagation from
175* the Booth encoding.
176*/
177template <typename C, size_t WindowBits>
178std::vector<typename C::AffinePoint> basemul_booth_setup(const typename C::AffinePoint& p, size_t max_scalar_bits) {
179 static_assert(WindowBits >= 1 && WindowBits <= 8);
180
181 // 2^(W-1) elements per window [1*base .. 2^(W-1)*base]
182 constexpr size_t WindowElements = 1 << (WindowBits - 1);
183
184 const size_t Windows = (max_scalar_bits + WindowBits - 1) / WindowBits;
185
186 const size_t TableSize = Windows * WindowElements;
187
188 std::vector<typename C::ProjectivePoint> table;
189 table.reserve(TableSize);
190
191 auto accum = C::ProjectivePoint::from_affine(p);
192
193 for(size_t i = 0; i != TableSize; i += WindowElements) {
194 table.push_back(accum);
195
196 for(size_t j = 1; j != WindowElements; ++j) {
197 // Conditional ok: loop iteration count is public
198 if(j % 2 == 1) {
199 table.emplace_back(table[i + j / 2].dbl());
200 } else {
201 table.emplace_back(table[i + j - 1] + table[i]);
202 }
203 }
204
205 // Advance to next window's base: 2^W * current_base
206 // The last entry is 2^(W-1) * base, so doubling gives 2^W * base
207 accum = table[i + WindowElements - 1].dbl();
208 }
209
210 // Variable time batch conversion is fine since generator is public
211 return to_affine_batch<C, true>(table);
212}
213
214template <typename C, size_t WindowBits, typename BlindedScalar, typename Blinding>
215typename C::ProjectivePoint basemul_booth_exec(std::span<const typename C::AffinePoint> table,
216 const BlindedScalar& scalar,
217 const Blinding& blinding) {
218 static constexpr size_t WindowElements = 1 << (WindowBits - 1);
219
220 const size_t windows = (scalar.bits() + WindowBits) / WindowBits;
221
222 auto accum = [&]() {
223 // First window: extract W bits, shift left 1 to insert implicit carry in of zero
224 const size_t w_bits = scalar.get_window(0) & ((1 << WindowBits) - 1);
225 const size_t raw = w_bits << 1;
226 const auto [tidx, tneg] = booth_recode<WindowBits>(raw);
227 const auto tbl_0 = table.first(WindowElements);
228
229 auto pt = C::ProjectivePoint::from_affine(C::AffinePoint::ct_select(tbl_0, tidx));
230 pt.conditional_assign(tneg, pt.negate());
231 blinding.randomize_rep(pt, 0);
232 return pt;
233 }();
234
235 for(size_t i = 1; i != windows; ++i) {
236 // Extract W+1 bits overlapping by 1 with the previous window
237 const size_t bit_pos = WindowBits * i - 1;
238 const size_t raw = scalar.get_window(bit_pos);
239 const auto [tidx, tneg] = booth_recode<WindowBits>(raw);
240
241 const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
242
243 accum = C::ProjectivePoint::add_or_sub(accum, C::AffinePoint::ct_select(tbl_i, tidx), tneg);
244
245 // Conditional ok: loop iteration count is public
246 if(i < Blinding::Rerandomizations) {
247 blinding.randomize_rep(accum, i);
248 }
249 }
250
251 return accum;
252}
253
254/*
255* Variable time base point multiplication using the Booth table
256*
257* Returns accum + s*P. The scalar is read directly, without blinding or
258* constant time table lookups, so this is only usable when s is public
259* (eg during signature verification).
260*/
261template <typename C, size_t WindowBits, typename ScalarBits>
262typename C::ProjectivePoint basemul_booth_exec_vartime(std::span<const typename C::AffinePoint> table,
263 const ScalarBits& scalar,
264 typename C::ProjectivePoint accum) {
265 static constexpr size_t WindowElements = 1 << (WindowBits - 1);
266
267 const size_t windows = (scalar.bits() + WindowBits) / WindowBits;
268 BOTAN_DEBUG_ASSERT(windows * WindowElements <= table.size());
269
270 for(size_t i = 0; i != windows; ++i) {
271 // Extract W+1 bits overlapping by 1 with the previous window; the
272 // first window has an implicit carry in of zero
273 const size_t raw =
274 (i == 0) ? ((scalar.get_window(0) & ((1 << WindowBits) - 1)) << 1) : scalar.get_window(WindowBits * i - 1);
275
276 const auto [tidx, tneg] = booth_recode<WindowBits>(raw);
277
278 // Conditional ok: this function is variable time
279 if(tidx > 0) {
280 accum = C::ProjectivePoint::add_or_sub(accum, table[WindowElements * i + tidx - 1], tneg);
281 }
282 }
283
284 return accum;
285}
286
287/*
288* Point table with a shared Z coordinate
289*
290* Using table points in mixed additions requires affine coordinates, but
291* converting to affine requires a field inversion. Instead the points are
292* rescaled so that they all share a single Z coordinate Zt, which needs only
293* multiplications.
294*
295* The map (x,y) -> (Zt^2*x, Zt^3*y) is an isomorphism from the curve
296* y^2 = x^3 + a*x + b onto the curve y^2 = x^3 + (a*Zt^4)*x + (b*Zt^6), and
297* under this map the Jacobian point (X, Y, Zt) becomes the affine point (X, Y).
298* So the table entries can be used directly as affine points, provided that
299* all doublings use the coefficient a*Zt^4 (see dbl_n_iso and add_or_sub_iso,
300* which covers the doubling fallback inside the addition formula). A result
301* (X, Y, Z) on the isomorphic curve maps back to (X, Y, Z*Zt) on the original
302* curve.
303*
304* Zt includes a random factor u, so the table entries and the isomorphic curve
305* differ between multiplications even for a fixed input point. This is the
306* random curve isomorphism countermeasure of Joye and Tymen (CHES 2001).
307*/
308template <typename C>
309class SharedZPointTable final {
310 public:
311 using AffinePoint = typename C::AffinePoint;
312 using ProjectivePoint = typename C::ProjectivePoint;
313 using FieldElement = typename C::FieldElement;
314
315 /**
316 * Table of the multiples [P, 2*P, ..., n*P]
317 *
318 * The multiples are computed as a chain of mixed additions, each of which
319 * multiplies Z by a known value H, so the rescaling factors Zt/Z_i are
320 * products of H values.
321 *
322 * @param p the point whose multiples are tabulated
323 * @param n the number of multiples
324 * @param a the a coefficient of the curve
325 * @param u the random isomorphism parameter, which must be nonzero
326 */
327 SharedZPointTable(const AffinePoint& p, size_t n, const FieldElement& a, const FieldElement& u) :
328 SharedZPointTable(build(p, n, a, u)) {}
329
330 /**
331 * Table of arbitrary points
332 *
333 * Here Zt is the product of the Z coordinates, and the rescaling factors
334 * Zt/Z_i are computed using prefix and suffix products. Identity elements
335 * are excluded from the product and remain the identity.
336 *
337 * @param pts the points to tabulate
338 * @param a the a coefficient of the curve
339 * @param one the field element 1
340 * @param u the random isomorphism parameter, which must be nonzero
341 */
342 SharedZPointTable(std::span<const ProjectivePoint> pts,
343 const FieldElement& a,
344 const FieldElement& one,
345 const FieldElement& u) :
346 SharedZPointTable(build(pts, a, one, u)) {}
347
348 /**
349 * If idx is zero then return the identity element. Otherwise return pts[idx - 1]
350 */
351 AffinePoint ct_select(size_t idx) const { return AffinePoint::ct_select(m_table, idx); }
352
353 /**
354 * Return the shared Z coordinate
355 */
356 const FieldElement& z() const { return m_z; }
357
358 /**
359 * Return the a coefficient of the isomorphic curve, a*z^4
360 */
361 const FieldElement& a() const { return m_a; }
362
363 private:
364 struct Table {
365 std::vector<AffinePoint> pts;
368 };
369
370 explicit SharedZPointTable(Table t) : m_table(std::move(t.pts)), m_z(t.z), m_a(t.a) {}
371
372 // Return the affine point corresponding to pt after multiplying its Z by f
373 static AffinePoint rescale(const ProjectivePoint& pt, const FieldElement& f) {
374 const auto f2 = f.square();
375 const auto f3 = f2 * f;
376 return AffinePoint(pt.x() * f2, pt.y() * f3);
377 }
378
379 static Table finish(std::vector<AffinePoint> pts, const FieldElement& zt, const FieldElement& a) {
380 const auto zt2 = zt.square();
381 return Table{std::move(pts), zt, a * zt2.square()};
382 }
383
384 static Table build(const AffinePoint& p, size_t n, const FieldElement& a, const FieldElement& u) {
385 BOTAN_ASSERT_NOMSG(n > 2);
386
387 // Chain P, 2*P, 3*P, ... where Z_i = Z_{i-1} * H_i for i >= 2
388 std::vector<ProjectivePoint> chain;
389 chain.reserve(n);
390 // h[i - 2] = H_i
391 std::vector<FieldElement> h;
392 h.reserve(n - 2);
393
394 chain.push_back(ProjectivePoint::from_affine(p));
395 chain.push_back(chain[0].dbl());
396 for(size_t i = 2; i != n; ++i) {
397 const auto pt_h = ProjectivePoint::add_mixed_h(chain[i - 1], p);
398 chain.push_back(pt_h.first);
399 h.push_back(pt_h.second);
400 }
401
402 // The shared Z is u * Z_{n-1}
403 const FieldElement zt = u * chain[n - 1].z();
404
405 // Built in reverse order since the scaling factors are suffix products
406 std::vector<AffinePoint> pts;
407 pts.reserve(n);
408
409 // The last entry is scaled by u alone
410 pts.push_back(rescale(chain[n - 1], u));
411
412 // Entry i is scaled by Zt/Z_i = u * H_{i+1} * ... * H_{n-1}
413 FieldElement mu = u * h[n - 3];
414 for(size_t i = n - 2; i > 0; --i) {
415 // Conditional ok: loop iteration count is public
416 if(i != n - 2) {
417 mu *= h[i - 1];
418 }
419 pts.push_back(rescale(chain[i], mu));
420 }
421
422 // Entry 0 is P itself with Z = 1, so it is scaled by Zt
423 pts.push_back(rescale(chain[0], zt));
424
425 std::reverse(pts.begin(), pts.end());
426
427 return finish(std::move(pts), zt, a);
428 }
429
430 static Table build(std::span<const ProjectivePoint> pts,
431 const FieldElement& a,
432 const FieldElement& one,
433 const FieldElement& u) {
434 const size_t n = pts.size();
435 BOTAN_ASSERT_NOMSG(n > 0);
436
437 // Identity elements have Z = 0; use 1 instead so they do not zero the products
438 std::vector<FieldElement> z;
439 z.reserve(n);
440 for(const auto& pt : pts) {
441 auto z_i = pt.z();
442 z_i.conditional_assign(pt.is_identity(), one);
443 z.push_back(z_i);
444 }
445
446 // prefix[i] = z_0 * ... * z_i
447 std::vector<FieldElement> prefix;
448 prefix.reserve(n);
449 prefix.push_back(z[0]);
450 for(size_t i = 1; i != n; ++i) {
451 prefix.push_back(prefix[i - 1] * z[i]);
452 }
453
454 // The shared Z is u * z_0 * ... * z_{n-1}
455 const FieldElement zt = u * prefix[n - 1];
456
457 // Entry i is scaled by Zt/Z_i = u * prefix[i-1] * z_{i+1} * ... * z_{n-1};
458 // built in reverse order since the second part is a suffix product
459 std::vector<AffinePoint> scaled;
460 scaled.reserve(n);
461
462 FieldElement suffix = u;
463 for(size_t i = n; i > 0; --i) {
464 const size_t idx = i - 1;
465
466 auto pt = [&]() {
467 // Conditional ok: idx is public
468 if(idx == 0) {
469 return rescale(pts[idx], suffix);
470 } else {
471 return rescale(pts[idx], prefix[idx - 1] * suffix);
472 }
473 }();
474 pt.conditional_assign(pts[idx].is_identity(), AffinePoint::identity(pt));
475 scaled.push_back(pt);
476
477 suffix *= z[idx];
478 }
479
480 std::reverse(scaled.begin(), scaled.end());
481
482 return finish(std::move(scaled), zt, a);
483 }
484
485 std::vector<AffinePoint> m_table;
486 FieldElement m_z;
487 FieldElement m_a;
488};
489
490/*
491* Variable point table mul online phase
492*/
493template <typename C, size_t WindowBits, typename BlindedScalar, typename Blinding>
494typename C::ProjectivePoint varpoint_exec(const SharedZPointTable<C>& table,
495 const BlindedScalar& scalar,
496 const Blinding& blinding) {
497 const size_t windows = (scalar.bits() + WindowBits - 1) / WindowBits;
498
499 auto accum = [&]() {
500 const size_t w_0 = scalar.get_window((windows - 1) * WindowBits);
501 auto pt = C::ProjectivePoint::from_affine(table.ct_select(w_0));
502 blinding.randomize_rep(pt, 0);
503 return pt;
504 }();
505
506 for(size_t i = 1; i != windows; ++i) {
507 accum = accum.dbl_n_iso(table.a(), WindowBits);
508 auto w_i = scalar.get_window((windows - i - 1) * WindowBits);
509
510 /*
511 This point addition cannot be a doubling (except once)
512
513 Consider the sequence of points that are operated on, and specifically
514 their discrete logarithms. We start out at the point at infinity
515 (dlog 0) and then add the initial window which is precisely P*w_0
516
517 We then perform WindowBits doublings, so accum's dlog at the point
518 of the addition in the first iteration of the loop (when i == 1) is
519 at least 2^W * w_0.
520
521 Since we know w_0 > 0, then in every iteration of the loop, accums
522 dlog will always be greater than the dlog of the table element we
523 just looked up (something between 0 and 2^W-1), and thus the
524 addition into accum cannot be a doubling.
525
526 However due to blinding this argument fails, since we perform
527 multiplications using a scalar that is larger than the group
528 order. In this case it's possible that the dlog of accum becomes
529 `order + x` (or, effectively, `x`) and `x` is smaller than 2^W.
530 In this case, a doubling may occur. Future iterations of the loop
531 cannot be doublings by the same argument above. Since the blinding
532 factor is always less than the group order (substantially so),
533 it is not possible for the dlog of accum to overflow a second time.
534 */
535
536 accum = C::ProjectivePoint::add_mixed_iso(accum, table.ct_select(w_i), table.a());
537
538 // Conditional ok: loop iteration count is public
539 if(i < Blinding::Rerandomizations) {
540 blinding.randomize_rep(accum, i);
541 }
542 }
543
544 // Map back from the isomorphic curve
545 return typename C::ProjectivePoint(accum.x(), accum.y(), accum.z() * table.z());
546}
547
548/*
549* Variable time table of odd multiples of a point
550*
551* Returns [P, 3*P, 5*P, ..., (2^(W-1) - 1)*P], which covers the digits of a
552* width W non-adjacent form.
553*/
554template <typename C, size_t W>
555std::vector<typename C::AffinePoint> odd_multiples_setup_vartime(const typename C::AffinePoint& p) {
556 static_assert(W >= 2 && W <= 7);
557
558 constexpr size_t TableSize = 1 << (W - 2);
559
560 std::vector<typename C::ProjectivePoint> table;
561 table.reserve(TableSize);
562
563 const auto p2 = C::ProjectivePoint::from_affine(p).dbl();
564
565 table.push_back(C::ProjectivePoint::from_affine(p));
566 for(size_t i = 1; i != TableSize; ++i) {
567 table.push_back(table[i - 1] + p2);
568 }
569
570 // Variable time batch conversion is fine since the point is public
571 return to_affine_batch<C, true>(table);
572}
573
574/*
575* Effect 2-ary multiplication ie x*G + y*H
576*
577* This is done using a windowed variant of what is usually called
578* Shamir's trick.
579*
580* The W = 1 case is simple; we precompute an extra point GH = G + H,
581* and then examine 1 bit in each of x and y. If one or the other bits
582* are set then add G or H resp. If both bits are set, add GH.
583*
584* The example below is a precomputed table for W=2. The flattened table
585* begins at (x_i,y_i) = (1,0), i.e. the identity element is omitted.
586* The indices in each cell refer to the cell's location in m_table.
587*
588* x-> 0 1 2 3
589* 0 |/ (ident) |0 x |1 2x |2 3x |
590* 1 |3 y |4 x+y |5 2x+y |6 3x+y |
591* y = 2 |7 2y |8 x+2y |9 2(x+y) |10 3x+2y |
592* 3 |11 3y |12 x+3y |13 2x+3y |14 3x+3y |
593*/
594
595template <typename C, size_t WindowBits>
596std::vector<typename C::ProjectivePoint> mul2_setup(const typename C::AffinePoint& p,
597 const typename C::AffinePoint& q) {
598 static_assert(WindowBits >= 1 && WindowBits <= 4);
599
600 // 2^(2*W) elements, less the identity element
601 constexpr size_t TableSize = (1 << (2 * WindowBits)) - 1;
602 constexpr size_t WindowSize = (1 << WindowBits);
603
604 std::vector<typename C::ProjectivePoint> table;
605 table.reserve(TableSize);
606
607 for(size_t i = 0; i != TableSize; ++i) {
608 const size_t t_i = (i + 1);
609 const size_t p_i = t_i % WindowSize;
610 const size_t q_i = (t_i >> WindowBits) % WindowSize;
611
612 // Conditionals ok: all based on t_i/p_i/q_i which in turn are derived from public i
613
614 // Returns x_i * x + y_i * y
615 const auto next_tbl_e = [&]() {
616 if(p_i % 2 == 0 && q_i % 2 == 0) {
617 // Where possible using doubling (eg indices 1, 7, 9 in
618 // the table above)
619 return table[(t_i / 2) - 1].dbl();
620 } else if(p_i > 0 && q_i > 0) {
621 // A combination of p and q
622 if(p_i == 1) {
623 return p + table[(q_i << WindowBits) - 1];
624 } else if(q_i == 1) {
625 return table[p_i - 1] + q;
626 } else {
627 return table[p_i - 1] + table[(q_i << WindowBits) - 1];
628 }
629 } else if(p_i > 0 && q_i == 0) {
630 // A multiple of p without a q component
631 if(p_i == 1) {
632 // Just p
633 return C::ProjectivePoint::from_affine(p);
634 } else {
635 // p * p_{i-1}
636 return p + table[p_i - 1 - 1];
637 }
638 } else if(p_i == 0 && q_i > 0) {
639 if(q_i == 1) {
640 // Just q
641 return C::ProjectivePoint::from_affine(q);
642 } else {
643 // q * q_{i-1}
644 return q + table[((q_i - 1) << WindowBits) - 1];
645 }
646 } else {
648 }
649 };
650
651 table.emplace_back(next_tbl_e());
652 }
653
654 return table;
655}
656
657template <typename C, size_t WindowBits, typename BlindedScalar, typename Blinding>
658typename C::ProjectivePoint mul2_exec(const SharedZPointTable<C>& table,
659 const BlindedScalar& x,
660 const BlindedScalar& y,
661 const Blinding& blinding) {
662 const size_t Windows = (x.bits() + WindowBits - 1) / WindowBits;
663
664 auto accum = [&]() {
665 const size_t w_1 = x.get_window((Windows - 1) * WindowBits);
666 const size_t w_2 = y.get_window((Windows - 1) * WindowBits);
667 const size_t window = w_1 + (w_2 << WindowBits);
668 auto pt = C::ProjectivePoint::from_affine(table.ct_select(window));
669 blinding.randomize_rep(pt, 0);
670 return pt;
671 }();
672
673 for(size_t i = 1; i != Windows; ++i) {
674 accum = accum.dbl_n_iso(table.a(), WindowBits);
675
676 const size_t w_1 = x.get_window((Windows - i - 1) * WindowBits);
677 const size_t w_2 = y.get_window((Windows - i - 1) * WindowBits);
678 const size_t window = w_1 + (w_2 << WindowBits);
679 accum = C::ProjectivePoint::add_mixed_iso(accum, table.ct_select(window), table.a());
680
681 // Conditional ok: loop iteration count is public
682 if(i < Blinding::Rerandomizations) {
683 blinding.randomize_rep(accum, i);
684 }
685 }
686
687 // Map back from the isomorphic curve
688 return typename C::ProjectivePoint(accum.x(), accum.y(), accum.z() * table.z());
689}
690
691} // namespace Botan
692
693#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:173
typename C::AffinePoint AffinePoint
typename C::FieldElement FieldElement
const FieldElement & z() const
AffinePoint ct_select(size_t idx) const
SharedZPointTable(std::span< const ProjectivePoint > pts, const FieldElement &a, const FieldElement &one, const FieldElement &u)
SharedZPointTable(const AffinePoint &p, size_t n, const FieldElement &a, const FieldElement &u)
typename C::ProjectivePoint ProjectivePoint
const FieldElement & a() const
C::ProjectivePoint basemul_booth_exec(std::span< const typename C::AffinePoint > table, const BlindedScalar &scalar, const Blinding &blinding)
constexpr size_t scalar_blinding_bits(size_t scalar_bits)
Definition pcurves_mul.h:42
constexpr std::pair< size_t, CT::Choice > booth_recode(size_t x, size_t window_bits)
Definition mp_core.h:1312
C::ProjectivePoint basemul_exec(std::span< const typename C::AffinePoint > table, const BlindedScalar &scalar, const Blinding &blinding)
C::ProjectivePoint mul2_exec(const SharedZPointTable< C > &table, const BlindedScalar &x, const BlindedScalar &y, const Blinding &blinding)
auto to_affine_batch(std::span< const typename C::ProjectivePoint > projective)
std::vector< typename C::ProjectivePoint > mul2_setup(const typename C::AffinePoint &p, const typename C::AffinePoint &q)
std::vector< typename C::AffinePoint > odd_multiples_setup_vartime(const typename C::AffinePoint &p)
C::ProjectivePoint varpoint_exec(const SharedZPointTable< C > &table, const BlindedScalar &scalar, const Blinding &blinding)
std::vector< typename C::AffinePoint > basemul_booth_setup(const typename C::AffinePoint &p, size_t max_scalar_bits)
C::ProjectivePoint basemul_booth_exec_vartime(std::span< const typename C::AffinePoint > table, const ScalarBits &scalar, typename C::ProjectivePoint accum)
std::vector< typename C::AffinePoint > basemul_setup(const typename C::AffinePoint &p, size_t max_scalar_bits)
Definition pcurves_mul.h:91