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