Botan 3.9.0
Crypto and TLS for C&
pcurves_generic.cpp
Go to the documentation of this file.
1/*
2* (C) 2025 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/pcurves_generic.h>
8
9#include <botan/bigint.h>
10#include <botan/exceptn.h>
11#include <botan/rng.h>
12#include <botan/internal/ct_utils.h>
13#include <botan/internal/loadstor.h>
14#include <botan/internal/mp_core.h>
15#include <botan/internal/pcurves_algos.h>
16#include <botan/internal/pcurves_instance.h>
17#include <botan/internal/pcurves_mul.h>
18#include <botan/internal/primality.h>
19#include <algorithm>
20
21namespace Botan::PCurve {
22
23namespace {
24
25template <size_t N>
26constexpr std::optional<std::array<word, N>> bytes_to_words(std::span<const uint8_t> bytes) {
27 if(bytes.size() > WordInfo<word>::bytes * N) {
28 return std::nullopt;
29 }
30
31 std::array<word, N> r{};
32
33 const size_t full_words = bytes.size() / WordInfo<word>::bytes;
34 const size_t extra_bytes = bytes.size() % WordInfo<word>::bytes;
35
36 for(size_t i = 0; i != full_words; ++i) {
37 r[i] = load_be<word>(bytes.data(), full_words - 1 - i);
38 }
39
40 if(extra_bytes > 0) {
41 const size_t shift = extra_bytes * 8;
42 bigint_shl1(r.data(), r.size(), r.size(), shift);
43
44 for(size_t i = 0; i != extra_bytes; ++i) {
45 const word b0 = bytes[WordInfo<word>::bytes * full_words + i];
46 r[0] |= (b0 << (8 * (extra_bytes - 1 - i)));
47 }
48 }
49
50 return r;
51}
52
53template <typename T>
54T impl_pow_vartime(const T& elem, const T& one, size_t bits, std::span<const word> exp) {
55 constexpr size_t WindowBits = 4;
56 constexpr size_t WindowElements = (1 << WindowBits) - 1;
57
58 const size_t Windows = (bits + WindowBits - 1) / WindowBits;
59
60 std::vector<T> tbl;
61 tbl.reserve(WindowElements);
62
63 tbl.push_back(elem);
64
65 for(size_t i = 1; i != WindowElements; ++i) {
66 if(i % 2 == 1) {
67 tbl.push_back(tbl[i / 2].square());
68 } else {
69 tbl.push_back(tbl[i - 1] * tbl[0]);
70 }
71 }
72
73 auto r = one;
74
75 const size_t w0 = read_window_bits<WindowBits>(exp, (Windows - 1) * WindowBits);
76
77 if(w0 > 0) {
78 r = tbl[w0 - 1];
79 }
80
81 for(size_t i = 1; i != Windows; ++i) {
82 for(size_t j = 0; j != WindowBits; ++j) {
83 r = r.square();
84 }
85 const size_t w = read_window_bits<WindowBits>(exp, (Windows - i - 1) * WindowBits);
86
87 if(w > 0) {
88 r *= tbl[w - 1];
89 }
90 }
91
92 return r;
93}
94
95} // namespace
96
97class GenericCurveParams final {
98 public:
99 typedef PrimeOrderCurve::StorageUnit StorageUnit;
100 static constexpr size_t N = PrimeOrderCurve::StorageWords;
101
102 GenericCurveParams(const BigInt& p,
103 const BigInt& a,
104 const BigInt& b,
105 const BigInt& base_x,
106 const BigInt& base_y,
107 const BigInt& order) :
108 m_words(p.sig_words()),
109 m_order_bits(order.bits()),
110 m_order_bytes(order.bytes()),
111 m_field_bits(p.bits()),
112 m_field_bytes(p.bytes()),
113 m_monty_order(order),
114 m_monty_field(p),
115 m_field(bn_to_fixed(p)),
116 m_field_minus_2(bn_to_fixed_rev(p - 2)),
117 m_field_monty_r1(bn_to_fixed(m_monty_field.R1())),
118 m_field_monty_r2(bn_to_fixed(m_monty_field.R2())),
119 m_field_p_plus_1_over_4(bn_to_fixed_rev((p + 1) / 4)),
120 m_field_inv_2(bn_to_fixed((p / 2) + 1)),
121 m_field_p_dash(m_monty_field.p_dash()),
122
123 m_order(bn_to_fixed(order)),
124 m_order_minus_2(bn_to_fixed_rev(order - 2)),
125 m_order_monty_r1(bn_to_fixed(m_monty_order.R1())),
126 m_order_monty_r2(bn_to_fixed(m_monty_order.R2())),
127 m_order_monty_r3(bn_to_fixed(m_monty_order.R3())),
128 m_order_inv_2(bn_to_fixed((order / 2) + 1)),
129 m_order_p_dash(m_monty_order.p_dash()),
130
131 m_a_is_minus_3(a + 3 == p),
132 m_a_is_zero(a.is_zero()),
133 m_order_is_lt_field(order < p) {
135 m_monty_curve_a = bn_to_fixed(m_monty_field.mul(a, m_monty_field.R2(), ws));
136 m_monty_curve_b = bn_to_fixed(m_monty_field.mul(b, m_monty_field.R2(), ws));
137
138 m_base_x = bn_to_fixed(m_monty_field.mul(base_x, m_monty_field.R2(), ws));
139 m_base_y = bn_to_fixed(m_monty_field.mul(base_y, m_monty_field.R2(), ws));
140 }
141
142 size_t words() const { return m_words; }
143
144 size_t order_bits() const { return m_order_bits; }
145
146 size_t order_bytes() const { return m_order_bytes; }
147
148 size_t field_bits() const { return m_field_bits; }
149
150 size_t field_bytes() const { return m_field_bytes; }
151
152 const Montgomery_Params& monty_order() const { return m_monty_order; }
153
154 const Montgomery_Params& monty_field() const { return m_monty_field; }
155
156 const StorageUnit& field() const { return m_field; }
157
158 const StorageUnit& field_minus_2() const { return m_field_minus_2; }
159
160 const StorageUnit& field_monty_r1() const { return m_field_monty_r1; }
161
162 const StorageUnit& field_monty_r2() const { return m_field_monty_r2; }
163
164 const StorageUnit& field_p_plus_1_over_4() const { return m_field_p_plus_1_over_4; }
165
166 const StorageUnit& field_inv_2() const { return m_field_inv_2; }
167
168 word field_p_dash() const { return m_field_p_dash; }
169
170 const StorageUnit& order() const { return m_order; }
171
172 const StorageUnit& order_minus_2() const { return m_order_minus_2; }
173
174 const StorageUnit& order_monty_r1() const { return m_order_monty_r1; }
175
176 const StorageUnit& order_monty_r2() const { return m_order_monty_r2; }
177
178 const StorageUnit& order_monty_r3() const { return m_order_monty_r3; }
179
180 const StorageUnit& order_inv_2() const { return m_order_inv_2; }
181
182 word order_p_dash() const { return m_order_p_dash; }
183
184 const StorageUnit& monty_curve_a() const { return m_monty_curve_a; }
185
186 const StorageUnit& monty_curve_b() const { return m_monty_curve_b; }
187
188 const StorageUnit& base_x() const { return m_base_x; }
189
190 const StorageUnit& base_y() const { return m_base_y; }
191
192 bool a_is_minus_3() const { return m_a_is_minus_3; }
193
194 bool a_is_zero() const { return m_a_is_zero; }
195
196 bool order_is_less_than_field() const { return m_order_is_lt_field; }
197
198 void mul(std::array<word, 2 * N>& z, const std::array<word, N>& x, const std::array<word, N>& y) const {
199 clear_mem(z);
200
201 if(m_words == 4) {
202 bigint_comba_mul4(z.data(), x.data(), y.data());
203 } else if(m_words == 6) {
204 bigint_comba_mul6(z.data(), x.data(), y.data());
205 } else if(m_words == 8) {
206 bigint_comba_mul8(z.data(), x.data(), y.data());
207 } else if(m_words == 9) {
208 bigint_comba_mul9(z.data(), x.data(), y.data());
209 } else {
210 bigint_mul(z.data(), z.size(), x.data(), m_words, m_words, y.data(), m_words, m_words, nullptr, 0);
211 }
212 }
213
214 void sqr(std::array<word, 2 * N>& z, const std::array<word, N>& x) const {
215 clear_mem(z);
216
217 if(m_words == 4) {
218 bigint_comba_sqr4(z.data(), x.data());
219 } else if(m_words == 6) {
220 bigint_comba_sqr6(z.data(), x.data());
221 } else if(m_words == 8) {
222 bigint_comba_sqr8(z.data(), x.data());
223 } else if(m_words == 9) {
224 bigint_comba_sqr9(z.data(), x.data());
225 } else {
226 bigint_sqr(z.data(), z.size(), x.data(), m_words, m_words, nullptr, 0);
227 }
228 }
229
230 private:
231 static std::array<word, PrimeOrderCurve::StorageWords> bn_to_fixed(const BigInt& n) {
232 const size_t n_words = n.sig_words();
234
235 std::array<word, PrimeOrderCurve::StorageWords> r{};
236 copy_mem(std::span{r}.first(n_words), n._as_span().first(n_words));
237 return r;
238 }
239
240 static std::array<word, PrimeOrderCurve::StorageWords> bn_to_fixed_rev(const BigInt& n) {
241 auto v = bn_to_fixed(n);
242 std::reverse(v.begin(), v.end());
243 return v;
244 }
245
246 private:
247 size_t m_words;
248 size_t m_order_bits;
249 size_t m_order_bytes;
250 size_t m_field_bits;
251 size_t m_field_bytes;
252
253 Montgomery_Params m_monty_order;
254 Montgomery_Params m_monty_field;
255
256 StorageUnit m_field;
257 StorageUnit m_field_minus_2;
258 StorageUnit m_field_monty_r1;
259 StorageUnit m_field_monty_r2;
260 StorageUnit m_field_p_plus_1_over_4;
261 StorageUnit m_field_inv_2;
262 word m_field_p_dash;
263
264 StorageUnit m_order;
265 StorageUnit m_order_minus_2;
266 StorageUnit m_order_monty_r1;
267 StorageUnit m_order_monty_r2;
268 StorageUnit m_order_monty_r3;
269 StorageUnit m_order_inv_2;
270 word m_order_p_dash;
271
272 StorageUnit m_monty_curve_a{};
273 StorageUnit m_monty_curve_b{};
274
275 StorageUnit m_base_x{};
276 StorageUnit m_base_y{};
277
278 bool m_a_is_minus_3;
279 bool m_a_is_zero;
280 bool m_order_is_lt_field;
281};
282
283class GenericScalar final {
284 public:
285 typedef word W;
286 typedef PrimeOrderCurve::StorageUnit StorageUnit;
287 static constexpr size_t N = PrimeOrderCurve::StorageWords;
288
289 static std::optional<GenericScalar> from_wide_bytes(const GenericPrimeOrderCurve* curve,
290 std::span<const uint8_t> bytes) {
291 const size_t mlen = curve->_params().order_bytes();
292
293 if(bytes.size() > 2 * mlen) {
294 return {};
295 }
296
297 std::array<uint8_t, 2 * sizeof(word) * N> padded_bytes{};
298 copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
299
300 auto words = bytes_to_words<2 * N>(std::span{padded_bytes});
301 if(words) {
302 auto in_rep = wide_to_rep(curve, words.value());
303 return GenericScalar(curve, in_rep);
304 } else {
305 return {};
306 }
307 }
308
309 static std::optional<GenericScalar> deserialize(const GenericPrimeOrderCurve* curve,
310 std::span<const uint8_t> bytes) {
311 const size_t len = curve->_params().order_bytes();
312
313 if(bytes.size() != len) {
314 return {};
315 }
316
317 const auto words = bytes_to_words<N>(bytes);
318
319 if(words) {
320 if(!bigint_ct_is_lt(words->data(), N, curve->_params().order().data(), N).as_bool()) {
321 return {};
322 }
323
324 // Safe because we checked above that words is an integer < P
325 return GenericScalar(curve, to_rep(curve, *words));
326 } else {
327 return {};
328 }
329 }
330
331 static GenericScalar zero(const GenericPrimeOrderCurve* curve) {
332 StorageUnit zeros{};
333 return GenericScalar(curve, zeros);
334 }
335
336 static GenericScalar one(const GenericPrimeOrderCurve* curve) {
337 return GenericScalar(curve, curve->_params().order_monty_r1());
338 }
339
340 static GenericScalar random(const GenericPrimeOrderCurve* curve, RandomNumberGenerator& rng) {
341 constexpr size_t MAX_ATTEMPTS = 1000;
342
343 const size_t bits = curve->_params().order_bits();
344
345 std::vector<uint8_t> buf(curve->_params().order_bytes());
346
347 for(size_t i = 0; i != MAX_ATTEMPTS; ++i) {
348 rng.randomize(buf);
349
350 // Zero off high bits that if set would certainly cause us
351 // to be out of range
352 if(bits % 8 != 0) {
353 const uint8_t mask = 0xFF >> (8 - (bits % 8));
354 buf[0] &= mask;
355 }
356
357 if(auto s = GenericScalar::deserialize(curve, buf)) {
358 if(s.value().is_nonzero().as_bool()) {
359 return s.value();
360 }
361 }
362 }
363
364 throw Internal_Error("Failed to generate random Scalar within bounded number of attempts");
365 }
366
367 friend GenericScalar operator+(const GenericScalar& a, const GenericScalar& b) {
368 const auto* curve = check_curve(a, b);
369 const size_t words = curve->_params().words();
370
371 StorageUnit t{};
372 W carry = bigint_add3(t.data(), a.data(), words, b.data(), words);
373
374 StorageUnit r{};
375 bigint_monty_maybe_sub(words, r.data(), carry, t.data(), curve->_params().order().data());
376 return GenericScalar(curve, r);
377 }
378
379 friend GenericScalar operator-(const GenericScalar& a, const GenericScalar& b) { return a + b.negate(); }
380
381 friend GenericScalar operator*(const GenericScalar& a, const GenericScalar& b) {
382 const auto* curve = check_curve(a, b);
383
384 std::array<W, 2 * N> z; // NOLINT(*-member-init)
385 curve->_params().mul(z, a.value(), b.value());
386 return GenericScalar(curve, redc(curve, z));
387 }
388
389 GenericScalar& operator*=(const GenericScalar& other) {
390 const auto* curve = check_curve(*this, other);
391
392 std::array<W, 2 * N> z; // NOLINT(*-member-init)
393 curve->_params().mul(z, value(), other.value());
394 m_val = redc(curve, z);
395 return (*this);
396 }
397
398 GenericScalar square() const {
399 const auto* curve = this->m_curve;
400
401 std::array<W, 2 * N> z; // NOLINT(*-member-init)
402 curve->_params().sqr(z, value());
403 return GenericScalar(curve, redc(curve, z));
404 }
405
406 GenericScalar pow_vartime(const StorageUnit& exp) const {
407 auto one = GenericScalar::one(curve());
408 auto bits = curve()->_params().order_bits();
409 auto words = curve()->_params().words();
410 return impl_pow_vartime(*this, one, bits, std::span{exp}.last(words));
411 }
412
413 GenericScalar negate() const {
414 auto x_is_zero = CT::all_zeros(this->data(), N);
415
416 StorageUnit r;
417 bigint_sub3(r.data(), m_curve->_params().order().data(), N, this->data(), N);
418 x_is_zero.if_set_zero_out(r.data(), N);
419 return GenericScalar(m_curve, r);
420 }
421
422 GenericScalar invert() const { return pow_vartime(m_curve->_params().order_minus_2()); }
423
424 /**
425 * Helper for variable time BEEA
426 *
427 * Note this function assumes that its arguments are in the standard
428 * domain, not the Montgomery domain. invert_vartime converts its argument
429 * out of Montgomery, and then back to Montgomery when returning the result.
430 */
431 static void _invert_vartime_div2_helper(GenericScalar& a, GenericScalar& x) {
432 const auto& inv_2 = a.curve()->_params().order_inv_2();
433
434 // Conditional ok: this function is variable time
435 while((a.m_val[0] & 1) != 1) {
436 shift_right<1>(a.m_val);
437
438 W borrow = shift_right<1>(x.m_val);
439
440 // Conditional ok: this function is variable time
441 if(borrow > 0) {
442 bigint_add2(x.m_val.data(), N, inv_2.data(), N);
443 }
444 }
445 }
446
447 /*
448 * See the comments on invert_vartime in pcurves_impl.h for background
449 */
450 GenericScalar invert_vartime() const {
451 if(this->is_zero().as_bool()) {
452 return (*this);
453 }
454
455 auto x = GenericScalar(m_curve, std::array<W, N>{1});
456 auto b = GenericScalar(m_curve, from_rep(m_curve, m_val));
457
458 // First loop iteration
459 GenericScalar::_invert_vartime_div2_helper(b, x);
460
461 auto a = b.negate();
462 // y += x but y is zero at the outset
463 auto y = x;
464
465 // First half of second loop iteration
466 GenericScalar::_invert_vartime_div2_helper(a, y);
467
468 for(;;) {
469 // Conditional ok: this function is variable time
470 if(a.m_val == b.m_val) {
471 // At this point it should be that a == b == 1
472 auto r = y.negate();
473
474 // Convert back to Montgomery
475 return GenericScalar(curve(), to_rep(curve(), r.m_val));
476 }
477
478 auto nx = x + y;
479
480 /*
481 * Otherwise either b > a or a > b
482 *
483 * If b > a we want to set b to b - a
484 * Otherwise we want to set a to a - b
485 *
486 * Compute r = b - a and check if it underflowed
487 * If it did not then we are in the b > a path
488 */
489 std::array<W, N> r{};
490 word carry = bigint_sub3(r.data(), b.data(), N, a.data(), N);
491
492 // Conditional ok: this function is variable time
493 if(carry == 0) {
494 // b > a
495 b.m_val = r;
496 x = nx;
497 GenericScalar::_invert_vartime_div2_helper(b, x);
498 } else {
499 // We know this can't underflow because a > b
500 bigint_sub3(r.data(), a.data(), N, b.data(), N);
501 a.m_val = r;
502 y = nx;
503 GenericScalar::_invert_vartime_div2_helper(a, y);
504 }
505 }
506 }
507
508 template <concepts::resizable_byte_buffer T>
509 T serialize() const {
510 T bytes(m_curve->_params().order_bytes());
511 this->serialize_to(bytes);
512 return bytes;
513 }
514
515 void serialize_to(std::span<uint8_t> bytes) const {
516 auto v = from_rep(m_curve, m_val);
517 std::reverse(v.begin(), v.end());
518
519 const size_t flen = m_curve->_params().order_bytes();
520 BOTAN_ARG_CHECK(bytes.size() == flen, "Expected output span provided");
521
522 // Remove leading zero bytes
523 const auto padded_bytes = store_be(v);
524 const size_t extra = N * WordInfo<W>::bytes - flen;
525 copy_mem(bytes, std::span{padded_bytes}.subspan(extra, flen));
526 }
527
528 CT::Choice is_zero() const { return CT::all_zeros(m_val.data(), m_curve->_params().words()).as_choice(); }
529
530 CT::Choice is_nonzero() const { return !is_zero(); }
531
532 CT::Choice operator==(const GenericScalar& other) const {
533 if(this->m_curve != other.m_curve) {
534 return CT::Choice::no();
535 }
536
537 return CT::is_equal(m_val.data(), other.m_val.data(), m_curve->_params().words()).as_choice();
538 }
539
540 /**
541 * Convert the integer to standard representation and return the sequence of words
542 */
543 StorageUnit to_words() const { return from_rep(m_curve, m_val); }
544
545 const StorageUnit& stash_value() const { return m_val; }
546
547 const GenericPrimeOrderCurve* curve() const { return m_curve; }
548
549 GenericScalar(const GenericPrimeOrderCurve* curve, StorageUnit val) : m_curve(curve), m_val(val) {}
550
551 private:
552 const StorageUnit& value() const { return m_val; }
553
554 const W* data() const { return m_val.data(); }
555
556 static const GenericPrimeOrderCurve* check_curve(const GenericScalar& a, const GenericScalar& b) {
557 BOTAN_STATE_CHECK(a.m_curve == b.m_curve);
558 return a.m_curve;
559 }
560
561 static StorageUnit redc(const GenericPrimeOrderCurve* curve, std::array<W, 2 * N> z) {
562 const auto& mod = curve->_params().order();
563 const size_t words = curve->_params().words();
564 StorageUnit r{};
565 StorageUnit ws{};
567 r.data(), z.data(), mod.data(), words, curve->_params().order_p_dash(), ws.data(), ws.size());
568 return r;
569 }
570
571 static StorageUnit from_rep(const GenericPrimeOrderCurve* curve, StorageUnit z) {
572 std::array<W, 2 * N> ze{};
573 copy_mem(std::span{ze}.template first<N>(), z);
574 return redc(curve, ze);
575 }
576
577 static StorageUnit to_rep(const GenericPrimeOrderCurve* curve, StorageUnit x) {
578 std::array<W, 2 * N> z; // NOLINT(*-member-init)
579 curve->_params().mul(z, x, curve->_params().order_monty_r2());
580 return redc(curve, z);
581 }
582
583 static StorageUnit wide_to_rep(const GenericPrimeOrderCurve* curve, std::array<W, 2 * N> x) {
584 auto redc_x = redc(curve, x);
585 std::array<W, 2 * N> z; // NOLINT(*-member-init)
586 curve->_params().mul(z, redc_x, curve->_params().order_monty_r3());
587 return redc(curve, z);
588 }
589
590 const GenericPrimeOrderCurve* m_curve;
591 StorageUnit m_val;
592};
593
594class GenericField final {
595 public:
596 typedef word W;
597 typedef PrimeOrderCurve::StorageUnit StorageUnit;
598 static constexpr size_t N = PrimeOrderCurve::StorageWords;
599
600 static std::optional<GenericField> deserialize(const GenericPrimeOrderCurve* curve,
601 std::span<const uint8_t> bytes) {
602 const size_t len = curve->_params().field_bytes();
603
604 if(bytes.size() != len) {
605 return {};
606 }
607
608 const auto words = bytes_to_words<N>(bytes);
609
610 if(words) {
611 if(!bigint_ct_is_lt(words->data(), N, curve->_params().field().data(), N).as_bool()) {
612 return {};
613 }
614
615 // Safe because we checked above that words is an integer < P
616 return GenericField::from_words(curve, *words);
617 } else {
618 return {};
619 }
620 }
621
622 static GenericField from_words(const GenericPrimeOrderCurve* curve, const std::array<word, N>& words) {
623 return GenericField(curve, to_rep(curve, words));
624 }
625
626 static GenericField zero(const GenericPrimeOrderCurve* curve) {
627 StorageUnit zeros{};
628 return GenericField(curve, zeros);
629 }
630
631 static GenericField one(const GenericPrimeOrderCurve* curve) {
632 return GenericField(curve, curve->_params().field_monty_r1());
633 }
634
635 static GenericField curve_a(const GenericPrimeOrderCurve* curve) {
636 return GenericField(curve, curve->_params().monty_curve_a());
637 }
638
639 static GenericField curve_b(const GenericPrimeOrderCurve* curve) {
640 return GenericField(curve, curve->_params().monty_curve_b());
641 }
642
643 static GenericField random(const GenericPrimeOrderCurve* curve, RandomNumberGenerator& rng) {
644 constexpr size_t MAX_ATTEMPTS = 1000;
645
646 const size_t bits = curve->_params().field_bits();
647
648 std::vector<uint8_t> buf(curve->_params().field_bytes());
649
650 for(size_t i = 0; i != MAX_ATTEMPTS; ++i) {
651 rng.randomize(buf);
652
653 // Zero off high bits that if set would certainly cause us
654 // to be out of range
655 if(bits % 8 != 0) {
656 const uint8_t mask = 0xFF >> (8 - (bits % 8));
657 buf[0] &= mask;
658 }
659
660 if(auto s = GenericField::deserialize(curve, buf)) {
661 if(s.value().is_nonzero().as_bool()) {
662 return s.value();
663 }
664 }
665 }
666
667 throw Internal_Error("Failed to generate random Scalar within bounded number of attempts");
668 }
669
670 /**
671 * Return the value of this divided by 2
672 */
673 GenericField div2() const {
674 StorageUnit t = value();
675 W borrow = shift_right<1>(t);
676
677 // If value was odd, add (P/2)+1
678 bigint_cnd_add(borrow, t.data(), m_curve->_params().field_inv_2().data(), N);
679
680 return GenericField(m_curve, t);
681 }
682
683 /// Return (*this) multiplied by 2
684 GenericField mul2() const {
685 StorageUnit t = value();
686 W carry = shift_left<1>(t);
687
688 StorageUnit r;
689 bigint_monty_maybe_sub<N>(r.data(), carry, t.data(), m_curve->_params().field().data());
690 return GenericField(m_curve, r);
691 }
692
693 /// Return (*this) multiplied by 3
694 GenericField mul3() const { return mul2() + (*this); }
695
696 /// Return (*this) multiplied by 4
697 GenericField mul4() const { return mul2().mul2(); }
698
699 /// Return (*this) multiplied by 8
700 GenericField mul8() const { return mul2().mul2().mul2(); }
701
702 friend GenericField operator+(const GenericField& a, const GenericField& b) {
703 const auto* curve = check_curve(a, b);
704 const size_t words = curve->_params().words();
705
706 StorageUnit t{};
707 W carry = bigint_add3(t.data(), a.data(), words, b.data(), words);
708
709 StorageUnit r{};
710 bigint_monty_maybe_sub(words, r.data(), carry, t.data(), curve->_params().field().data());
711 return GenericField(curve, r);
712 }
713
714 friend GenericField operator-(const GenericField& a, const GenericField& b) { return a + b.negate(); }
715
716 friend GenericField operator*(const GenericField& a, const GenericField& b) {
717 const auto* curve = check_curve(a, b);
718
719 std::array<W, 2 * N> z; // NOLINT(*-member-init)
720 curve->_params().mul(z, a.value(), b.value());
721 return GenericField(curve, redc(curve, z));
722 }
723
724 GenericField& operator*=(const GenericField& other) {
725 const auto* curve = check_curve(*this, other);
726
727 std::array<W, 2 * N> z; // NOLINT(*-member-init)
728 curve->_params().mul(z, value(), other.value());
729 m_val = redc(curve, z);
730 return (*this);
731 }
732
733 GenericField square() const {
734 std::array<W, 2 * N> z; // NOLINT(*-member-init)
735 m_curve->_params().sqr(z, value());
736 return GenericField(m_curve, redc(m_curve, z));
737 }
738
739 GenericField pow_vartime(const StorageUnit& exp) const {
740 auto one = GenericField::one(curve());
741 auto bits = curve()->_params().field_bits();
742 auto words = curve()->_params().words();
743 return impl_pow_vartime(*this, one, bits, std::span{exp}.last(words));
744 }
745
746 GenericField negate() const {
747 auto x_is_zero = CT::all_zeros(this->data(), N);
748
749 StorageUnit r;
750 bigint_sub3(r.data(), m_curve->_params().field().data(), N, this->data(), N);
751 x_is_zero.if_set_zero_out(r.data(), N);
752 return GenericField(m_curve, r);
753 }
754
755 GenericField invert() const { return pow_vartime(m_curve->_params().field_minus_2()); }
756
757 template <concepts::resizable_byte_buffer T>
758 T serialize() const {
759 T bytes(m_curve->_params().field_bytes());
760 serialize_to(bytes);
761 return bytes;
762 }
763
764 void serialize_to(std::span<uint8_t> bytes) const {
765 auto v = from_rep(m_curve, m_val);
766 std::reverse(v.begin(), v.end());
767
768 const size_t flen = m_curve->_params().field_bytes();
769 BOTAN_ARG_CHECK(bytes.size() == flen, "Expected output span provided");
770
771 // Remove leading zero bytes
772 const auto padded_bytes = store_be(v);
773 const size_t extra = N * WordInfo<W>::bytes - flen;
774 copy_mem(bytes, std::span{padded_bytes}.subspan(extra, flen));
775 }
776
777 CT::Choice is_zero() const { return CT::all_zeros(m_val.data(), m_curve->_params().words()).as_choice(); }
778
779 CT::Choice is_nonzero() const { return !is_zero(); }
780
781 CT::Choice operator==(const GenericField& other) const {
782 if(this->m_curve != other.m_curve) {
783 return CT::Choice::no();
784 }
785
786 return CT::is_equal(m_val.data(), other.m_val.data(), m_curve->_params().words()).as_choice();
787 }
788
789 const StorageUnit& stash_value() const { return m_val; }
790
791 const GenericPrimeOrderCurve* curve() const { return m_curve; }
792
793 CT::Choice is_even() const {
794 auto v = from_rep(m_curve, m_val);
795 return !CT::Choice::from_int(v[0] & 0x01);
796 }
797
798 /**
799 * Convert the integer to standard representation and return the sequence of words
800 */
801 StorageUnit to_words() const { return from_rep(m_curve, m_val); }
802
803 void _const_time_poison() const { CT::poison(m_val); }
804
805 void _const_time_unpoison() const { CT::unpoison(m_val); }
806
807 static void conditional_swap(CT::Choice cond, GenericField& x, GenericField& y) {
808 const W mask = CT::Mask<W>::from_choice(cond).value();
809
810 for(size_t i = 0; i != N; ++i) {
811 auto nx = choose(mask, y.m_val[i], x.m_val[i]);
812 auto ny = choose(mask, x.m_val[i], y.m_val[i]);
813 x.m_val[i] = nx;
814 y.m_val[i] = ny;
815 }
816 }
817
818 void conditional_assign(CT::Choice cond, const GenericField& nx) {
819 const W mask = CT::Mask<W>::from_choice(cond).value();
820
821 for(size_t i = 0; i != N; ++i) {
822 m_val[i] = choose(mask, nx.m_val[i], m_val[i]);
823 }
824 }
825
826 /**
827 * Conditional assignment
828 *
829 * If `cond` is true, sets `x` to `nx` and `y` to `ny`
830 */
831 static void conditional_assign(
832 GenericField& x, GenericField& y, CT::Choice cond, const GenericField& nx, const GenericField& ny) {
833 const W mask = CT::Mask<W>::from_choice(cond).value();
834
835 for(size_t i = 0; i != N; ++i) {
836 x.m_val[i] = choose(mask, nx.m_val[i], x.m_val[i]);
837 y.m_val[i] = choose(mask, ny.m_val[i], y.m_val[i]);
838 }
839 }
840
841 /**
842 * Conditional assignment
843 *
844 * If `cond` is true, sets `x` to `nx`, `y` to `ny`, and `z` to `nz`
845 */
846 static void conditional_assign(GenericField& x,
847 GenericField& y,
848 GenericField& z,
849 CT::Choice cond,
850 const GenericField& nx,
851 const GenericField& ny,
852 const GenericField& nz) {
853 const W mask = CT::Mask<W>::from_choice(cond).value();
854
855 for(size_t i = 0; i != N; ++i) {
856 x.m_val[i] = choose(mask, nx.m_val[i], x.m_val[i]);
857 y.m_val[i] = choose(mask, ny.m_val[i], y.m_val[i]);
858 z.m_val[i] = choose(mask, nz.m_val[i], z.m_val[i]);
859 }
860 }
861
862 std::pair<GenericField, CT::Choice> sqrt() const {
863 BOTAN_STATE_CHECK(m_curve->_params().field()[0] % 4 == 3);
864
865 auto z = pow_vartime(m_curve->_params().field_p_plus_1_over_4());
866 const CT::Choice correct = (z.square() == *this);
867 // Zero out the return value if it would otherwise be incorrect
868 z.conditional_assign(!correct, zero(m_curve));
869 return {z, correct};
870 }
871
872 GenericField(const GenericPrimeOrderCurve* curve, StorageUnit val) : m_curve(curve), m_val(val) {}
873
874 private:
875 const StorageUnit& value() const { return m_val; }
876
877 const W* data() const { return m_val.data(); }
878
879 static const GenericPrimeOrderCurve* check_curve(const GenericField& a, const GenericField& b) {
880 BOTAN_STATE_CHECK(a.m_curve == b.m_curve);
881 return a.m_curve;
882 }
883
884 static StorageUnit redc(const GenericPrimeOrderCurve* curve, std::array<W, 2 * N> z) {
885 const auto& mod = curve->_params().field();
886 const size_t words = curve->_params().words();
887 StorageUnit r{};
888 StorageUnit ws{};
890 r.data(), z.data(), mod.data(), words, curve->_params().field_p_dash(), ws.data(), ws.size());
891 return r;
892 }
893
894 static StorageUnit from_rep(const GenericPrimeOrderCurve* curve, StorageUnit z) {
895 std::array<W, 2 * N> ze{};
896 copy_mem(std::span{ze}.template first<N>(), z);
897 return redc(curve, ze);
898 }
899
900 static StorageUnit to_rep(const GenericPrimeOrderCurve* curve, StorageUnit x) {
901 std::array<W, 2 * N> z{};
902 curve->_params().mul(z, x, curve->_params().field_monty_r2());
903 return redc(curve, z);
904 }
905
906 const GenericPrimeOrderCurve* m_curve;
907 StorageUnit m_val;
908};
909
910/**
911* Affine Curve Point
912*
913* This contains a pair of integers (x,y) which satisfy the curve equation
914*/
915class GenericAffinePoint final {
916 public:
917 GenericAffinePoint(const GenericField& x, const GenericField& y) : m_x(x), m_y(y) {}
918
919 explicit GenericAffinePoint(const GenericPrimeOrderCurve* curve) :
920 m_x(GenericField::zero(curve)), m_y(GenericField::zero(curve)) {}
921
922 static GenericAffinePoint identity(const GenericPrimeOrderCurve* curve) {
923 return GenericAffinePoint(GenericField::zero(curve), GenericField::zero(curve));
924 }
925
926 static GenericAffinePoint identity(const GenericAffinePoint& pt) { return identity(pt.curve()); }
927
928 CT::Choice is_identity() const { return x().is_zero() && y().is_zero(); }
929
930 GenericAffinePoint negate() const { return GenericAffinePoint(x(), y().negate()); }
931
932 /**
933 * Serialize the point in uncompressed format
934 */
935 void serialize_to(std::span<uint8_t> bytes) const {
936 const size_t fe_bytes = curve()->_params().field_bytes();
937 BOTAN_ARG_CHECK(bytes.size() == 1 + 2 * fe_bytes, "Buffer size incorrect");
938 BOTAN_STATE_CHECK(this->is_identity().as_bool() == false);
939 BufferStuffer pack(bytes);
940 pack.append(0x04);
941 x().serialize_to(pack.next(fe_bytes));
942 y().serialize_to(pack.next(fe_bytes));
943 BOTAN_DEBUG_ASSERT(pack.full());
944 }
945
946 /**
947 * If idx is zero then return the identity element. Otherwise return pts[idx - 1]
948 *
949 * Returns the identity element also if idx is out of range
950 */
951 static auto ct_select(std::span<const GenericAffinePoint> pts, size_t idx) {
952 BOTAN_ARG_CHECK(!pts.empty(), "Cannot select from an empty set");
953 auto result = GenericAffinePoint::identity(pts[0].curve());
954
955 // Intentionally wrapping; set to maximum size_t if idx == 0
956 const size_t idx1 = static_cast<size_t>(idx - 1);
957 for(size_t i = 0; i != pts.size(); ++i) {
958 const auto found = CT::Mask<size_t>::is_equal(idx1, i).as_choice();
959 result.conditional_assign(found, pts[i]);
960 }
961
962 return result;
963 }
964
965 /**
966 * Return (x^3 + A*x + B) mod p
967 */
968 static GenericField x3_ax_b(const GenericField& x) {
969 return (x.square() + GenericField::curve_a(x.curve())) * x + GenericField::curve_b(x.curve());
970 }
971
972 /**
973 * Point deserialization
974 *
975 * This accepts compressed or uncompressed formats.
976 */
977 static std::optional<GenericAffinePoint> deserialize(const GenericPrimeOrderCurve* curve,
978 std::span<const uint8_t> bytes) {
979 const size_t fe_bytes = curve->_params().field_bytes();
980
981 if(bytes.size() == 1 + 2 * fe_bytes && bytes[0] == 0x04) {
982 auto x = GenericField::deserialize(curve, bytes.subspan(1, fe_bytes));
983 auto y = GenericField::deserialize(curve, bytes.subspan(1 + fe_bytes, fe_bytes));
984
985 if(x && y) {
986 const auto lhs = (*y).square();
987 const auto rhs = GenericAffinePoint::x3_ax_b(*x);
988 if((lhs == rhs).as_bool()) {
989 return GenericAffinePoint(*x, *y);
990 }
991 }
992 } else if(bytes.size() == 1 + fe_bytes && (bytes[0] == 0x02 || bytes[0] == 0x03)) {
993 const CT::Choice y_is_even = CT::Mask<uint8_t>::is_equal(bytes[0], 0x02).as_choice();
994
995 if(auto x = GenericField::deserialize(curve, bytes.subspan(1, fe_bytes))) {
996 auto [y, is_square] = x3_ax_b(*x).sqrt();
997
998 if(is_square.as_bool()) {
999 const auto flip_y = y_is_even != y.is_even();
1000 y.conditional_assign(flip_y, y.negate());
1001 return GenericAffinePoint(*x, y);
1002 }
1003 }
1004 } else if(bytes.size() == 1 && bytes[0] == 0x00) {
1005 // See SEC1 section 2.3.4
1006 return GenericAffinePoint::identity(curve);
1007 }
1008
1009 return {};
1010 }
1011
1012 /**
1013 * Return the affine x coordinate
1014 */
1015 const GenericField& x() const { return m_x; }
1016
1017 /**
1018 * Return the affine y coordinate
1019 */
1020 const GenericField& y() const { return m_y; }
1021
1022 /**
1023 * Conditional assignment of an affine point
1024 */
1025 void conditional_assign(CT::Choice cond, const GenericAffinePoint& pt) {
1026 GenericField::conditional_assign(m_x, m_y, cond, pt.x(), pt.y());
1027 }
1028
1029 const GenericPrimeOrderCurve* curve() const { return m_x.curve(); }
1030
1031 void _const_time_poison() const { CT::poison_all(m_x, m_y); }
1032
1033 void _const_time_unpoison() const { CT::unpoison_all(m_x, m_y); }
1034
1035 private:
1036 GenericField m_x;
1037 GenericField m_y;
1038};
1039
1040class GenericProjectivePoint final {
1041 public:
1042 typedef GenericProjectivePoint Self;
1043
1044 using FieldElement = GenericField;
1045
1046 /**
1047 * Convert a point from affine to projective form
1048 */
1049 static Self from_affine(const GenericAffinePoint& pt) {
1050 auto x = pt.x();
1051 auto y = pt.y();
1052 auto z = GenericField::one(x.curve());
1053
1054 // If pt is identity (0,0) swap y/z to convert (0,0,1) into (0,1,0)
1055 GenericField::conditional_swap(pt.is_identity(), y, z);
1056 return GenericProjectivePoint(x, y, z);
1057 }
1058
1059 /**
1060 * Return the identity element
1061 */
1062 static Self identity(const GenericPrimeOrderCurve* curve) {
1063 return Self(GenericField::zero(curve), GenericField::one(curve), GenericField::zero(curve));
1064 }
1065
1066 /**
1067 * Default constructor: the identity element
1068 */
1069 explicit GenericProjectivePoint(const GenericPrimeOrderCurve* curve) :
1070 m_x(GenericField::zero(curve)), m_y(GenericField::one(curve)), m_z(GenericField::zero(curve)) {}
1071
1072 /**
1073 * Affine constructor: take x/y coordinates
1074 */
1075 GenericProjectivePoint(const GenericField& x, const GenericField& y) :
1076 m_x(x), m_y(y), m_z(GenericField::one(m_x.curve())) {}
1077
1078 /**
1079 * Projective constructor: take x/y/z coordinates
1080 */
1081 GenericProjectivePoint(const GenericField& x, const GenericField& y, const GenericField& z) :
1082 m_x(x), m_y(y), m_z(z) {}
1083
1084 friend Self operator+(const Self& a, const Self& b) { return Self::add(a, b); }
1085
1086 friend Self operator+(const Self& a, const GenericAffinePoint& b) { return Self::add_mixed(a, b); }
1087
1088 friend Self operator+(const GenericAffinePoint& a, const Self& b) { return Self::add_mixed(b, a); }
1089
1090 Self& operator+=(const Self& other) {
1091 (*this) = (*this) + other;
1092 return (*this);
1093 }
1094
1095 Self& operator+=(const GenericAffinePoint& other) {
1096 (*this) = (*this) + other;
1097 return (*this);
1098 }
1099
1100 CT::Choice is_identity() const { return z().is_zero(); }
1101
1102 /**
1103 * Mixed (projective + affine) point addition
1104 */
1105 static Self add_mixed(const Self& a, const GenericAffinePoint& b) {
1106 return point_add_mixed<Self, GenericAffinePoint, GenericField>(a, b, GenericField::one(a.curve()));
1107 }
1108
1109 /**
1110 * Projective point addition
1111 */
1112 static Self add(const Self& a, const Self& b) { return point_add<Self, GenericField>(a, b); }
1113
1114 /**
1115 * Iterated point doubling
1116 */
1117 Self dbl_n(size_t n) const {
1118 if(curve()->_params().a_is_minus_3()) {
1119 return dbl_n_a_minus_3(*this, n);
1120 } else if(curve()->_params().a_is_zero()) {
1121 return dbl_n_a_zero(*this, n);
1122 } else {
1123 const auto A = GenericField::curve_a(curve());
1124 return dbl_n_generic(*this, A, n);
1125 }
1126 }
1127
1128 /**
1129 * Point doubling
1130 */
1131 Self dbl() const {
1132 if(curve()->_params().a_is_minus_3()) {
1133 return dbl_a_minus_3(*this);
1134 } else if(curve()->_params().a_is_zero()) {
1135 return dbl_a_zero(*this);
1136 } else {
1137 const auto A = GenericField::curve_a(curve());
1138 return dbl_generic(*this, A);
1139 }
1140 }
1141
1142 /**
1143 * Point negation
1144 */
1145 Self negate() const { return Self(x(), y().negate(), z()); }
1146
1147 /**
1148 * Randomize the point representation
1149 *
1150 * Projective coordinates are redundant; if (x,y,z) is a projective
1151 * point then so is (x*r^2,y*r^3,z*r) for any non-zero r.
1152 */
1153 void randomize_rep(RandomNumberGenerator& rng) {
1154 // In certain contexts we may be called with a Null_RNG; in that case the
1155 // caller is accepting that randomization will not occur
1156
1157 if(rng.is_seeded()) {
1158 auto r = GenericField::random(curve(), rng);
1159
1160 auto r2 = r.square();
1161 auto r3 = r2 * r;
1162
1163 m_x *= r2;
1164 m_y *= r3;
1165 m_z *= r;
1166 }
1167 }
1168
1169 /**
1170 * Return the projective x coordinate
1171 */
1172 const GenericField& x() const { return m_x; }
1173
1174 /**
1175 * Return the projective y coordinate
1176 */
1177 const GenericField& y() const { return m_y; }
1178
1179 /**
1180 * Return the projective z coordinate
1181 */
1182 const GenericField& z() const { return m_z; }
1183
1184 const GenericPrimeOrderCurve* curve() const { return m_x.curve(); }
1185
1186 void _const_time_poison() const { CT::poison_all(m_x, m_y, m_z); }
1187
1188 void _const_time_unpoison() const { CT::unpoison_all(m_x, m_y, m_z); }
1189
1190 private:
1191 GenericField m_x;
1192 GenericField m_y;
1193 GenericField m_z;
1194};
1195
1196class GenericCurve final {
1197 public:
1198 typedef GenericField FieldElement;
1199 typedef GenericScalar Scalar;
1200 typedef GenericAffinePoint AffinePoint;
1201 typedef GenericProjectivePoint ProjectivePoint;
1202
1203 typedef word WordType;
1204 static constexpr size_t Words = PCurve::PrimeOrderCurve::StorageWords;
1205};
1206
1207class GenericBlindedScalarBits final {
1208 public:
1209 GenericBlindedScalarBits(const GenericScalar& scalar, RandomNumberGenerator& rng, size_t wb) {
1210 // Just a simplifying assumption for get_window, can extend to 1..7 as required
1211 BOTAN_ASSERT_NOMSG(wb == 3 || wb == 4 || wb == 5);
1212
1213 const auto& params = scalar.curve()->_params();
1214
1215 const size_t order_bits = params.order_bits();
1216 const size_t blinder_bits = blinding_bits(order_bits);
1217
1218 const size_t mask_words = blinder_bits / WordInfo<word>::bits;
1219 const size_t mask_bytes = mask_words * WordInfo<word>::bytes;
1220
1221 const size_t words = params.words();
1222
1223 secure_vector<uint8_t> maskb(mask_bytes);
1224 if(rng.is_seeded()) {
1225 rng.randomize(maskb);
1226 } else {
1227 auto sbytes = scalar.serialize<std::vector<uint8_t>>();
1228 for(size_t i = 0; i != sbytes.size(); ++i) {
1229 maskb[i % mask_bytes] ^= sbytes[i];
1230 }
1231 }
1232
1233 std::array<word, PrimeOrderCurve::StorageWords> mask{};
1234 load_le(mask.data(), maskb.data(), mask_words);
1235 mask[mask_words - 1] |= WordInfo<word>::top_bit;
1236 mask[0] |= 1;
1237
1238 std::array<word, 2 * PrimeOrderCurve::StorageWords> mask_n{};
1239
1240 const auto sw = scalar.to_words();
1241
1242 // Compute masked scalar s + k*n
1243 params.mul(mask_n, mask, params.order());
1244 bigint_add2(mask_n.data(), 2 * words, sw.data(), words);
1245
1246 std::reverse(mask_n.begin(), mask_n.end());
1247 m_bytes = store_be<std::vector<uint8_t>>(mask_n);
1248 m_bits = order_bits + blinder_bits;
1249 m_window_bits = wb;
1250 m_windows = (order_bits + blinder_bits + wb - 1) / wb;
1251 }
1252
1253 size_t windows() const { return m_windows; }
1254
1255 size_t bits() const { return m_bits; }
1256
1257 size_t get_window(size_t offset) const {
1258 if(m_window_bits == 3) {
1259 return read_window_bits<3>(std::span{m_bytes}, offset);
1260 } else if(m_window_bits == 4) {
1261 return read_window_bits<4>(std::span{m_bytes}, offset);
1262 } else if(m_window_bits == 5) {
1263 return read_window_bits<5>(std::span{m_bytes}, offset);
1264 } else {
1266 }
1267 }
1268
1269 static size_t blinding_bits(size_t order_bits) {
1270 if(order_bits > 512) {
1271 return blinding_bits(512);
1272 }
1273
1274 const size_t wb = sizeof(word) * 8;
1275 return ((order_bits / 4 + wb - 1) / wb) * wb;
1276 }
1277
1278 private:
1279 std::vector<uint8_t> m_bytes;
1280 size_t m_bits;
1281 size_t m_windows;
1282 size_t m_window_bits;
1283};
1284
1285class GenericWindowedMul final {
1286 public:
1287 static constexpr size_t WindowBits = VarPointWindowBits;
1288 static constexpr size_t TableSize = (1 << WindowBits) - 1;
1289
1290 explicit GenericWindowedMul(const GenericAffinePoint& pt) :
1291 m_table(varpoint_setup<GenericCurve, TableSize>(pt)) {}
1292
1293 GenericProjectivePoint mul(const GenericScalar& s, RandomNumberGenerator& rng) {
1294 GenericBlindedScalarBits bits(s, rng, WindowBits);
1295
1296 return varpoint_exec<GenericCurve, WindowBits>(m_table, bits, rng);
1297 }
1298
1299 private:
1300 AffinePointTable<GenericCurve> m_table;
1301};
1302
1303class GenericBaseMulTable final {
1304 public:
1305 static constexpr size_t WindowBits = BasePointWindowBits;
1306
1307 static constexpr size_t WindowElements = (1 << WindowBits) - 1;
1308
1309 explicit GenericBaseMulTable(const GenericAffinePoint& pt) :
1310 m_table(basemul_setup<GenericCurve, WindowBits>(pt, blinded_scalar_bits(*pt.curve()))) {}
1311
1312 GenericProjectivePoint mul(const GenericScalar& s, RandomNumberGenerator& rng) {
1313 GenericBlindedScalarBits scalar(s, rng, WindowBits);
1314 return basemul_exec<GenericCurve, WindowBits>(m_table, scalar, rng);
1315 }
1316
1317 private:
1318 static size_t blinded_scalar_bits(const GenericPrimeOrderCurve& curve) {
1319 const size_t order_bits = curve.order_bits();
1320 return order_bits + GenericBlindedScalarBits::blinding_bits(order_bits);
1321 }
1322
1323 std::vector<GenericAffinePoint> m_table;
1324};
1325
1326class GenericWindowedMul2 final {
1327 public:
1328 static constexpr size_t WindowBits = Mul2PrecompWindowBits;
1329
1330 GenericWindowedMul2(const GenericWindowedMul2& other) = delete;
1331 GenericWindowedMul2(GenericWindowedMul2&& other) = delete;
1332 GenericWindowedMul2& operator=(const GenericWindowedMul2& other) = delete;
1333 GenericWindowedMul2& operator=(GenericWindowedMul2&& other) = delete;
1334
1335 ~GenericWindowedMul2() = default;
1336
1337 GenericWindowedMul2(const GenericAffinePoint& p, const GenericAffinePoint& q) :
1338 m_table(mul2_setup<GenericCurve, WindowBits>(p, q)) {}
1339
1340 GenericProjectivePoint mul2(const GenericScalar& x, const GenericScalar& y, RandomNumberGenerator& rng) const {
1341 GenericBlindedScalarBits x_bits(x, rng, WindowBits);
1342 GenericBlindedScalarBits y_bits(y, rng, WindowBits);
1343 return mul2_exec<GenericCurve, WindowBits>(m_table, x_bits, y_bits, rng);
1344 }
1345
1346 private:
1347 AffinePointTable<GenericCurve> m_table;
1348};
1349
1350class GenericVartimeWindowedMul2 final : public PrimeOrderCurve::PrecomputedMul2Table {
1351 public:
1352 static constexpr size_t WindowBits = Mul2PrecompWindowBits;
1353
1354 GenericVartimeWindowedMul2(const GenericVartimeWindowedMul2& other) = delete;
1355 GenericVartimeWindowedMul2(GenericVartimeWindowedMul2&& other) = delete;
1356 GenericVartimeWindowedMul2& operator=(const GenericVartimeWindowedMul2& other) = delete;
1357 GenericVartimeWindowedMul2& operator=(GenericVartimeWindowedMul2&& other) = delete;
1358
1359 ~GenericVartimeWindowedMul2() override = default;
1360
1361 GenericVartimeWindowedMul2(const GenericAffinePoint& p, const GenericAffinePoint& q) :
1362 m_table(to_affine_batch<GenericCurve>(mul2_setup<GenericCurve, WindowBits>(p, q))) {}
1363
1364 GenericProjectivePoint mul2_vartime(const GenericScalar& x, const GenericScalar& y) const {
1365 const auto x_bits = x.serialize<std::vector<uint8_t>>();
1366 const auto y_bits = y.serialize<std::vector<uint8_t>>();
1367
1368 const auto& curve = m_table[0].curve();
1369 auto accum = GenericProjectivePoint(curve);
1370
1371 const size_t order_bits = curve->order_bits();
1372
1373 const size_t windows = (order_bits + WindowBits - 1) / WindowBits;
1374
1375 for(size_t i = 0; i != windows; ++i) {
1376 auto x_i = read_window_bits<WindowBits>(std::span{x_bits}, (windows - i - 1) * WindowBits);
1377 auto y_i = read_window_bits<WindowBits>(std::span{y_bits}, (windows - i - 1) * WindowBits);
1378
1379 if(i > 0) {
1380 accum = accum.dbl_n(WindowBits);
1381 }
1382
1383 const size_t idx = (y_i << WindowBits) + x_i;
1384
1385 if(idx > 0) {
1386 accum += m_table[idx - 1];
1387 }
1388 }
1389
1390 return accum;
1391 }
1392
1393 private:
1394 std::vector<GenericAffinePoint> m_table;
1395};
1396
1398 const BigInt& p, const BigInt& a, const BigInt& b, const BigInt& base_x, const BigInt& base_y, const BigInt& order) :
1399 m_params(std::make_unique<GenericCurveParams>(p, a, b, base_x, base_y, order)) {}
1400
1402 BOTAN_STATE_CHECK(m_basemul == nullptr);
1403 m_basemul = std::make_unique<GenericBaseMulTable>(from_stash(generator()));
1404}
1405
1407 return _params().order_bits();
1408}
1409
1411 return _params().order_bytes();
1412}
1413
1415 return _params().field_bytes();
1416}
1417
1419 RandomNumberGenerator& rng) const {
1420 BOTAN_STATE_CHECK(m_basemul != nullptr);
1421 return stash(m_basemul->mul(from_stash(scalar), rng));
1422}
1423
1425 RandomNumberGenerator& rng) const {
1426 BOTAN_STATE_CHECK(m_basemul != nullptr);
1427 auto pt_s = m_basemul->mul(from_stash(scalar), rng);
1428 const auto x_bytes = to_affine_x<GenericCurve>(pt_s).serialize<secure_vector<uint8_t>>();
1429 if(auto s = GenericScalar::from_wide_bytes(this, x_bytes)) {
1430 return stash(*s);
1431 } else {
1432 throw Internal_Error("Failed to convert x coordinate to integer modulo scalar");
1433 }
1434}
1435
1437 const Scalar& scalar,
1438 RandomNumberGenerator& rng) const {
1439 GenericWindowedMul pt_table(from_stash(pt));
1440 return stash(pt_table.mul(from_stash(scalar), rng));
1441}
1442
1444 const Scalar& scalar,
1445 RandomNumberGenerator& rng) const {
1446 GenericWindowedMul pt_table(from_stash(pt));
1447 auto pt_s = pt_table.mul(from_stash(scalar), rng);
1448 return to_affine_x<GenericCurve>(pt_s).serialize<secure_vector<uint8_t>>();
1449}
1450
1451std::unique_ptr<const PrimeOrderCurve::PrecomputedMul2Table> GenericPrimeOrderCurve::mul2_setup_g(
1452 const AffinePoint& q) const {
1453 return std::make_unique<GenericVartimeWindowedMul2>(from_stash(generator()), from_stash(q));
1454}
1455
1456std::optional<PrimeOrderCurve::ProjectivePoint> GenericPrimeOrderCurve::mul2_vartime(const PrecomputedMul2Table& tableb,
1457 const Scalar& s1,
1458 const Scalar& s2) const {
1459 const auto& tbl = dynamic_cast<const GenericVartimeWindowedMul2&>(tableb);
1460 auto pt = tbl.mul2_vartime(from_stash(s1), from_stash(s2));
1461 if(pt.is_identity().as_bool()) {
1462 return {};
1463 } else {
1464 return stash(pt);
1465 }
1466}
1467
1468std::optional<PrimeOrderCurve::ProjectivePoint> GenericPrimeOrderCurve::mul_px_qy(
1469 const AffinePoint& p, const Scalar& x, const AffinePoint& q, const Scalar& y, RandomNumberGenerator& rng) const {
1470 GenericWindowedMul2 table(from_stash(p), from_stash(q));
1471 auto pt = table.mul2(from_stash(x), from_stash(y), rng);
1472 if(pt.is_identity().as_bool()) {
1473 return {};
1474 } else {
1475 return stash(pt);
1476 }
1477}
1478
1480 const Scalar& v,
1481 const Scalar& s1,
1482 const Scalar& s2) const {
1483 const auto& tbl = dynamic_cast<const GenericVartimeWindowedMul2&>(tableb);
1484 auto pt = tbl.mul2_vartime(from_stash(s1), from_stash(s2));
1485
1486 if(!pt.is_identity().as_bool()) {
1487 const auto z2 = pt.z().square();
1488
1489 const auto v_bytes = from_stash(v).serialize<std::vector<uint8_t>>();
1490
1491 if(auto fe_v = GenericField::deserialize(this, v_bytes)) {
1492 if((*fe_v * z2 == pt.x()).as_bool()) {
1493 return true;
1494 }
1495
1496 if(_params().order_is_less_than_field()) {
1497 const auto n = GenericField::from_words(this, _params().order());
1498 const auto neg_n = n.negate().to_words();
1499
1500 const auto vw = fe_v->to_words();
1501 if(bigint_ct_is_lt(vw.data(), vw.size(), neg_n.data(), neg_n.size()).as_bool()) {
1502 return (((*fe_v + n) * z2) == pt.x()).as_bool();
1503 }
1504 }
1505 }
1506 }
1507
1508 return false;
1509}
1510
1512 return PrimeOrderCurve::AffinePoint::_create(shared_from_this(), _params().base_x(), _params().base_y());
1513}
1514
1516 auto affine = to_affine<GenericCurve>(from_stash(pt));
1517
1518 const auto y2 = affine.y().square();
1519 const auto x3_ax_b = GenericCurve::AffinePoint::x3_ax_b(affine.x());
1520 const auto valid_point = affine.is_identity() || (y2 == x3_ax_b);
1521
1522 BOTAN_ASSERT(valid_point.as_bool(), "Computed point is on the curve");
1523
1524 return stash(affine);
1525}
1526
1528 return stash(GenericProjectivePoint::from_affine(from_stash(a)) + from_stash(b));
1529}
1530
1532 return stash(from_stash(pt).negate());
1533}
1534
1536 return from_stash(pt).is_identity().as_bool();
1537}
1538
1539void GenericPrimeOrderCurve::serialize_point(std::span<uint8_t> bytes, const AffinePoint& pt) const {
1540 from_stash(pt).serialize_to(bytes);
1541}
1542
1543void GenericPrimeOrderCurve::serialize_scalar(std::span<uint8_t> bytes, const Scalar& scalar) const {
1544 BOTAN_ARG_CHECK(bytes.size() == _params().order_bytes(), "Invalid length to serialize_scalar");
1545 from_stash(scalar).serialize_to(bytes);
1546}
1547
1548std::optional<PrimeOrderCurve::Scalar> GenericPrimeOrderCurve::deserialize_scalar(
1549 std::span<const uint8_t> bytes) const {
1550 if(auto s = GenericScalar::deserialize(this, bytes)) {
1551 return stash(s.value());
1552 } else {
1553 return {};
1554 }
1555}
1556
1557std::optional<PrimeOrderCurve::Scalar> GenericPrimeOrderCurve::scalar_from_wide_bytes(
1558 std::span<const uint8_t> bytes) const {
1559 if(auto s = GenericScalar::from_wide_bytes(this, bytes)) {
1560 return stash(s.value());
1561 } else {
1562 return {};
1563 }
1564}
1565
1566std::optional<PrimeOrderCurve::AffinePoint> GenericPrimeOrderCurve::deserialize_point(
1567 std::span<const uint8_t> bytes) const {
1568 if(auto pt = GenericAffinePoint::deserialize(this, bytes)) {
1569 return stash(pt.value());
1570 } else {
1571 return {};
1572 }
1573}
1574
1576 return stash(from_stash(a) + from_stash(b));
1577}
1578
1580 return stash(from_stash(a) - from_stash(b));
1581}
1582
1584 return stash(from_stash(a) * from_stash(b));
1585}
1586
1588 return stash(from_stash(s).square());
1589}
1590
1592 return stash(from_stash(s).invert());
1593}
1594
1596 return stash(from_stash(s).invert_vartime());
1597}
1598
1600 return stash(from_stash(s).negate());
1601}
1602
1604 return from_stash(s).is_zero().as_bool();
1605}
1606
1608 return (from_stash(a) == from_stash(b)).as_bool();
1609}
1610
1612 return stash(GenericScalar::one(this));
1613}
1614
1616 return stash(GenericScalar::random(this, rng));
1617}
1618
1619PrimeOrderCurve::Scalar GenericPrimeOrderCurve::stash(const GenericScalar& s) const {
1620 return Scalar::_create(shared_from_this(), s.stash_value());
1621}
1622
1623GenericScalar GenericPrimeOrderCurve::from_stash(const PrimeOrderCurve::Scalar& s) const {
1624 BOTAN_ARG_CHECK(s._curve().get() == this, "Curve mismatch");
1625 return GenericScalar(this, s._value());
1626}
1627
1628PrimeOrderCurve::AffinePoint GenericPrimeOrderCurve::stash(const GenericAffinePoint& pt) const {
1629 auto x_w = pt.x().stash_value();
1630 auto y_w = pt.y().stash_value();
1631 return AffinePoint::_create(shared_from_this(), x_w, y_w);
1632}
1633
1634GenericAffinePoint GenericPrimeOrderCurve::from_stash(const PrimeOrderCurve::AffinePoint& pt) const {
1635 BOTAN_ARG_CHECK(pt._curve().get() == this, "Curve mismatch");
1636 auto x = GenericField(this, pt._x());
1637 auto y = GenericField(this, pt._y());
1638 return GenericAffinePoint(x, y);
1639}
1640
1641PrimeOrderCurve::ProjectivePoint GenericPrimeOrderCurve::stash(const GenericProjectivePoint& pt) const {
1642 auto x_w = pt.x().stash_value();
1643 auto y_w = pt.y().stash_value();
1644 auto z_w = pt.z().stash_value();
1645 return ProjectivePoint::_create(shared_from_this(), x_w, y_w, z_w);
1646}
1647
1648GenericProjectivePoint GenericPrimeOrderCurve::from_stash(const PrimeOrderCurve::ProjectivePoint& pt) const {
1649 BOTAN_ARG_CHECK(pt._curve().get() == this, "Curve mismatch");
1650 auto x = GenericField(this, pt._x());
1651 auto y = GenericField(this, pt._y());
1652 auto z = GenericField(this, pt._z());
1653 return GenericProjectivePoint(x, y, z);
1654}
1655
1657 std::function<void(std::span<uint8_t>)> expand_message) const {
1658 BOTAN_UNUSED(expand_message);
1659 throw Not_Implemented("Hash to curve is not implemented for this curve");
1660}
1661
1663 std::function<void(std::span<uint8_t>)> expand_message) const {
1664 BOTAN_UNUSED(expand_message);
1665 throw Not_Implemented("Hash to curve is not implemented for this curve");
1666}
1667
1668std::shared_ptr<const PrimeOrderCurve> PCurveInstance::from_params(
1669 const BigInt& p, const BigInt& a, const BigInt& b, const BigInt& base_x, const BigInt& base_y, const BigInt& order) {
1670 // We don't check that p and order are prime here on the assumption this has
1671 // been checked already by EC_Group
1672
1673 BOTAN_ARG_CHECK(a >= 0 && a < p, "a is invalid");
1674 BOTAN_ARG_CHECK(b > 0 && b < p, "b is invalid");
1675 BOTAN_ARG_CHECK(base_x >= 0 && base_x < p, "base_x is invalid");
1676 BOTAN_ARG_CHECK(base_y >= 0 && base_y < p, "base_y is invalid");
1677
1678 const size_t p_bits = p.bits();
1679
1680 // Same size restrictions as EC_Group however here we do not require
1681 // exactly the primes for the 521 or 239 bit exceptions; this code
1682 // should work fine with any such prime and we are relying on the higher
1683 // levels to prevent creating such a group in the first place
1684 //
1685 // TODO(Botan4) increase the 128 here to 192 when the cooresponding EC_Group constructor is changed
1686 //
1687 if(p_bits != 521 && p_bits != 239 && (p_bits < 128 || p_bits > 512 || p_bits % 32 != 0)) {
1688 return {};
1689 }
1690
1691 // We don't want to deal with Shanks-Tonelli in the generic case
1692 if(p % 4 != 3) {
1693 return {};
1694 }
1695
1696 // The bit length of the field and order being the same simplifies things
1697 if(p_bits != order.bits()) {
1698 return {};
1699 }
1700
1701 auto gpoc = std::make_shared<GenericPrimeOrderCurve>(p, a, b, base_x, base_y, order);
1702 /*
1703 The implementation of this needs to call shared_from_this which is not usable
1704 until after the constructor has completed, so we have to do a two-stage
1705 construction process. This is certainly not so clean but it is contained to
1706 this single file so seems tolerable.
1707
1708 Alternately we could lazily compute the base mul table but this brings in
1709 locking issues which seem a worse alternative overall.
1710 */
1711 gpoc->_precompute_base_mul();
1712 return gpoc;
1713}
1714
1715} // namespace Botan::PCurve
#define BOTAN_UNUSED
Definition assert.h:144
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:62
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:163
size_t bits() const
Definition bigint.cpp:311
static constexpr Choice from_int(T v)
Definition ct_utils.h:314
static constexpr Choice no()
Definition ct_utils.h:335
static constexpr Mask< T > from_choice(Choice c)
Definition ct_utils.h:430
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:470
Scalar random_scalar(RandomNumberGenerator &rng) const override
AffinePoint point_negate(const AffinePoint &pt) const override
bool mul2_vartime_x_mod_order_eq(const PrecomputedMul2Table &tableb, const Scalar &v, const Scalar &s1, const Scalar &s2) const override
ProjectivePoint mul_by_g(const Scalar &scalar, RandomNumberGenerator &rng) const override
std::optional< ProjectivePoint > mul_px_qy(const AffinePoint &p, const Scalar &x, const AffinePoint &q, const Scalar &y, RandomNumberGenerator &rng) const override
ProjectivePoint hash_to_curve_ro(std::function< void(std::span< uint8_t >)> expand_message) const override
void serialize_scalar(std::span< uint8_t > bytes, const Scalar &scalar) const override
Scalar scalar_square(const Scalar &s) const override
Scalar squaring.
std::optional< Scalar > deserialize_scalar(std::span< const uint8_t > bytes) const override
std::optional< Scalar > scalar_from_wide_bytes(std::span< const uint8_t > bytes) const override
std::unique_ptr< const PrecomputedMul2Table > mul2_setup_g(const AffinePoint &q) const override
Setup a table for 2-ary multiplication where the first point is the generator.
GenericPrimeOrderCurve(const BigInt &p, const BigInt &a, const BigInt &b, const BigInt &base_x, const BigInt &base_y, const BigInt &order)
AffinePoint generator() const override
Return the standard generator.
const GenericCurveParams & _params() const
AffinePoint hash_to_curve_nu(std::function< void(std::span< uint8_t >)> expand_message) const override
ProjectivePoint point_add(const AffinePoint &a, const AffinePoint &b) const override
Scalar scalar_mul(const Scalar &a, const Scalar &b) const override
Scalar multiplication.
Scalar scalar_invert(const Scalar &s) const override
Scalar inversion.
std::optional< AffinePoint > deserialize_point(std::span< const uint8_t > bytes) const override
std::optional< ProjectivePoint > mul2_vartime(const PrecomputedMul2Table &tableb, const Scalar &x, const Scalar &y) const override
void serialize_point(std::span< uint8_t > bytes, const AffinePoint &pt) const override
bool scalar_is_zero(const Scalar &s) const override
Test if scalar is zero.
Scalar scalar_negate(const Scalar &s) const override
Scalar negation.
secure_vector< uint8_t > mul_x_only(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const override
ProjectivePoint mul(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const override
Scalar base_point_mul_x_mod_order(const Scalar &scalar, RandomNumberGenerator &rng) const override
Scalar scalar_invert_vartime(const Scalar &s) const override
Scalar inversion (variable time)
bool affine_point_is_identity(const AffinePoint &pt) const override
size_t scalar_bytes() const override
Return the byte length of the scalar element.
Scalar scalar_sub(const Scalar &a, const Scalar &b) const override
Scalar subtraction.
AffinePoint point_to_affine(const ProjectivePoint &pt) const override
bool scalar_equal(const Scalar &a, const Scalar &b) const override
Test if two scalars are equal.
Scalar scalar_add(const Scalar &a, const Scalar &b) const override
Scalar addition.
size_t order_bits() const override
Return the bit length of the group order.
static AffinePoint _create(CurvePtr curve, StorageUnit x, StorageUnit y)
Definition pcurves.h:114
static constexpr size_t StorageWords
Number of words used to store MaximumByteLength.
Definition pcurves.h:43
std::array< word, StorageWords > StorageUnit
Definition pcurves.h:60
constexpr void pack(const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)
constexpr void poison_all(const Ts &... ts)
Definition ct_utils.h:199
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:205
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:826
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:65
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:813
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:54
C::ProjectivePoint varpoint_exec(const AffinePointTable< C > &table, const BlindedScalar &scalar, RandomNumberGenerator &rng)
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:96
auto to_affine_batch(std::span< const typename C::ProjectivePoint > projective)
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:122
auto to_affine_x(const typename C::ProjectivePoint &pt)
constexpr auto bytes_to_words(std::span< const uint8_t, L > bytes)
constexpr W shift_left(std::array< W, N > &x)
Definition mp_core.h:612
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:145
constexpr ProjectivePoint dbl_n_generic(const ProjectivePoint &pt, const FieldElement &A, size_t n)
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
Definition mp_core.h:952
void bigint_comba_sqr4(word z[8], const word x[4])
Definition mp_comba.cpp:16
void bigint_comba_sqr6(word z[12], const word x[6])
Definition mp_comba.cpp:74
constexpr ProjectivePoint dbl_a_minus_3(const ProjectivePoint &pt)
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition mp_comba.cpp:42
BigInt square(const BigInt &x)
Definition numthry.cpp:157
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:327
C::ProjectivePoint mul2_exec(const AffinePointTable< C > &table, const BlindedScalar &x, const BlindedScalar &y, RandomNumberGenerator &rng)
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:194
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
Definition mp_comba.cpp:115
constexpr ProjectivePoint dbl_n_a_zero(const ProjectivePoint &pt, size_t n)
constexpr ProjectivePoint dbl_a_zero(const ProjectivePoint &pt)
C::ProjectivePoint basemul_exec(std::span< const typename C::AffinePoint > table, const BlindedScalar &scalar, RandomNumberGenerator &rng)
std::vector< typename C::ProjectivePoint > mul2_setup(const typename C::AffinePoint &p, const typename C::AffinePoint &q)
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:309
constexpr auto to_affine(const typename C::ProjectivePoint &pt)
constexpr ProjectivePoint point_add_mixed(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one)
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:804
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:47
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:227
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
Definition mp_comba.cpp:511
void carry(int64_t &h0, int64_t &h1)
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:196
constexpr ProjectivePoint dbl_n_a_minus_3(const ProjectivePoint &pt, size_t n)
AffinePointTable< C > varpoint_setup(const typename C::AffinePoint &p)
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:475
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
void bigint_comba_sqr8(word z[16], const word x[8])
Definition mp_comba.cpp:292
void bigint_comba_sqr9(word z[18], const word x[9])
Definition mp_comba.cpp:440
constexpr ProjectivePoint dbl_generic(const ProjectivePoint &pt, const FieldElement &A)
std::vector< typename C::AffinePoint > basemul_setup(const typename C::AffinePoint &p, size_t max_scalar_bits)
constexpr ProjectivePoint point_add(const ProjectivePoint &a, const ProjectivePoint &b)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
Definition mp_comba.cpp:352
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:119
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:504
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:626