7#include <botan/internal/pcurves_generic.h>
9#include <botan/bigint.h>
10#include <botan/exceptn.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>
28constexpr std::optional<std::array<word, N>>
bytes_to_words(std::span<const uint8_t> bytes) {
29 if(bytes.size() > WordInfo<word>::bytes * N) {
33 std::array<word, N> r{};
35 const size_t full_words = bytes.size() / WordInfo<word>::bytes;
36 const size_t extra_bytes = bytes.size() % WordInfo<word>::bytes;
38 for(
size_t i = 0; i != full_words; ++i) {
43 const size_t shift = extra_bytes * 8;
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)));
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;
60 const size_t Windows = (bits + WindowBits - 1) / WindowBits;
63 tbl.reserve(WindowElements);
67 for(
size_t i = 1; i != WindowElements; ++i) {
69 tbl.push_back(tbl[i / 2].
square());
71 tbl.push_back(tbl[i - 1] * tbl[0]);
83 for(
size_t i = 1; i != Windows; ++i) {
84 for(
size_t j = 0; j != WindowBits; ++j) {
99class GenericCurveParams final {
104 GenericCurveParams(
const BigInt& p,
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),
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()),
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()),
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));
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));
145 size_t words()
const {
return m_words; }
147 size_t order_bits()
const {
return m_order_bits; }
149 size_t order_bytes()
const {
return m_order_bytes; }
151 size_t field_bits()
const {
return m_field_bits; }
153 size_t field_bytes()
const {
return m_field_bytes; }
155 const Montgomery_Params& monty_order()
const {
return m_monty_order; }
157 const Montgomery_Params& monty_field()
const {
return m_monty_field; }
159 const StorageUnit& field()
const {
return m_field; }
161 const StorageUnit& field_minus_2()
const {
return m_field_minus_2; }
163 const StorageUnit& field_monty_r1()
const {
return m_field_monty_r1; }
165 const StorageUnit& field_monty_r2()
const {
return m_field_monty_r2; }
167 const StorageUnit& field_monty_r3()
const {
return m_field_monty_r3; }
169 const StorageUnit& field_p_plus_1_over_4()
const {
return m_field_p_plus_1_over_4; }
171 const StorageUnit& field_inv_2()
const {
return m_field_inv_2; }
173 word field_p_dash()
const {
return m_field_p_dash; }
175 const StorageUnit& order()
const {
return m_order; }
177 const StorageUnit& order_minus_2()
const {
return m_order_minus_2; }
179 const StorageUnit& order_monty_r1()
const {
return m_order_monty_r1; }
181 const StorageUnit& order_monty_r2()
const {
return m_order_monty_r2; }
183 const StorageUnit& order_monty_r3()
const {
return m_order_monty_r3; }
185 const StorageUnit& order_inv_2()
const {
return m_order_inv_2; }
187 word order_p_dash()
const {
return m_order_p_dash; }
189 const StorageUnit& monty_curve_a()
const {
return m_monty_curve_a; }
191 const StorageUnit& monty_curve_b()
const {
return m_monty_curve_b; }
193 const StorageUnit& base_x()
const {
return m_base_x; }
195 const StorageUnit& base_y()
const {
return m_base_y; }
197 bool a_is_minus_3()
const {
return m_a_is_minus_3; }
199 bool a_is_zero()
const {
return m_a_is_zero; }
201 bool order_is_less_than_field()
const {
return m_order_is_lt_field; }
203 void mul(std::array<word, 2 * N>& z,
const std::array<word, N>& x,
const std::array<word, N>& y)
const {
208 }
else if(m_words == 6) {
210 }
else if(m_words == 8) {
212 }
else if(m_words == 9) {
215 bigint_mul(z.data(), z.size(), x.data(), m_words, m_words, y.data(), m_words, m_words,
nullptr, 0);
219 void sqr(std::array<word, 2 * N>& z,
const std::array<word, N>& x)
const {
224 }
else if(m_words == 6) {
226 }
else if(m_words == 8) {
228 }
else if(m_words == 9) {
231 bigint_sqr(z.data(), z.size(), x.data(), m_words, m_words,
nullptr, 0);
236 static std::array<word, PrimeOrderCurve::StorageWords> bn_to_fixed(
const BigInt& n) {
237 const size_t n_words = n.sig_words();
240 std::array<word, PrimeOrderCurve::StorageWords> r{};
241 copy_mem(std::span{r}.first(n_words), n._as_span().first(n_words));
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());
254 size_t m_order_bytes;
256 size_t m_field_bytes;
258 Montgomery_Params m_monty_order;
259 Montgomery_Params m_monty_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;
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;
278 StorageUnit m_monty_curve_a{};
279 StorageUnit m_monty_curve_b{};
281 StorageUnit m_base_x{};
282 StorageUnit m_base_y{};
286 bool m_order_is_lt_field;
289class GenericScalar final {
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();
299 if(bytes.size() > 2 * mlen) {
303 std::array<uint8_t, 2 *
sizeof(
word) * N> padded_bytes{};
304 copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
308 const auto in_rep = wide_to_rep(curve, words.value());
309 return GenericScalar(curve, in_rep);
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();
319 if(bytes.size() != len) {
326 if(!
bigint_ct_is_lt(words->data(), N, curve->_params().order().data(), N).as_bool()) {
331 return GenericScalar(curve, to_rep(curve, *words));
337 static GenericScalar zero(
const GenericPrimeOrderCurve* curve) {
338 const StorageUnit zeros{};
339 return GenericScalar(curve, zeros);
342 static GenericScalar one(
const GenericPrimeOrderCurve* curve) {
343 return GenericScalar(curve, curve->_params().order_monty_r1());
346 static GenericScalar random(
const GenericPrimeOrderCurve* curve, RandomNumberGenerator& rng) {
347 constexpr size_t MAX_ATTEMPTS = 1000;
349 const size_t bits = curve->_params().order_bits();
351 std::vector<uint8_t> buf(curve->_params().order_bytes());
353 for(
size_t i = 0; i != MAX_ATTEMPTS; ++i) {
359 const uint8_t mask = 0xFF >> (8 - (bits % 8));
363 if(
auto s = GenericScalar::deserialize(curve, buf)) {
364 if(s.value().is_nonzero().as_bool()) {
370 throw Internal_Error(
"Failed to generate random Scalar within bounded number of attempts");
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();
378 const W carry =
bigint_add3(t.data(), a.data(), words, b.data(), words);
382 return GenericScalar(curve, r);
385 friend GenericScalar operator-(
const GenericScalar& a,
const GenericScalar& b) {
return a + b.negate(); }
387 friend GenericScalar operator*(
const GenericScalar& a,
const GenericScalar& b) {
388 const auto* curve = check_curve(a, b);
390 std::array<W, 2 * N> z;
391 curve->_params().mul(z, a.value(), b.value());
392 return GenericScalar(curve, redc(curve, z));
395 GenericScalar& operator*=(
const GenericScalar& other) {
396 const auto* curve = check_curve(*
this, other);
398 std::array<W, 2 * N> z;
399 curve->_params().mul(z, value(), other.value());
400 m_val = redc(curve, z);
404 GenericScalar square()
const {
405 const auto* curve = this->m_curve;
407 std::array<W, 2 * N> z;
408 curve->_params().sqr(z, value());
409 return GenericScalar(curve, redc(curve, z));
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));
419 GenericScalar negate()
const {
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);
428 GenericScalar invert()
const {
return pow_vartime(m_curve->_params().order_minus_2()); }
437 static void _invert_vartime_div2_helper(GenericScalar& a, GenericScalar& x) {
438 const auto& inv_2 = a.curve()->_params().order_inv_2();
441 while((a.m_val[0] & 1) != 1) {
456 GenericScalar invert_vartime()
const {
457 if(this->is_zero().as_bool()) {
461 auto x = GenericScalar(m_curve, std::array<W, N>{1});
462 auto b = GenericScalar(m_curve, from_rep(m_curve, m_val));
465 GenericScalar::_invert_vartime_div2_helper(b, x);
472 GenericScalar::_invert_vartime_div2_helper(a, y);
476 if(a.m_val == b.m_val) {
478 const auto r = y.negate();
481 return GenericScalar(curve(), to_rep(curve(), r.m_val));
484 const auto nx = x + y;
495 std::array<W, N> r{};
503 GenericScalar::_invert_vartime_div2_helper(b, x);
509 GenericScalar::_invert_vartime_div2_helper(a, y);
514 template <concepts::resizable_
byte_buffer T>
515 T serialize()
const {
516 T bytes(m_curve->_params().order_bytes());
517 this->serialize_to(bytes);
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());
525 const size_t flen = m_curve->_params().order_bytes();
526 BOTAN_ARG_CHECK(bytes.size() == flen,
"Expected output span provided");
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));
534 CT::Choice is_zero()
const {
return CT::all_zeros(m_val.data(), m_curve->_params().words()).as_choice(); }
536 CT::Choice is_nonzero()
const {
return !is_zero(); }
538 CT::Choice operator==(
const GenericScalar& other)
const {
539 if(this->m_curve != other.m_curve) {
543 return CT::is_equal(m_val.data(), other.m_val.data(), m_curve->_params().words()).as_choice();
549 StorageUnit to_words()
const {
return from_rep(m_curve, m_val); }
551 const StorageUnit& stash_value()
const {
return m_val; }
553 const GenericPrimeOrderCurve* curve()
const {
return m_curve; }
555 GenericScalar(
const GenericPrimeOrderCurve* curve, StorageUnit val) : m_curve(curve), m_val(val) {}
558 const StorageUnit& value()
const {
return m_val; }
560 const W* data()
const {
return m_val.data(); }
562 static const GenericPrimeOrderCurve* check_curve(
const GenericScalar& a,
const GenericScalar& b) {
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();
573 r.data(), z.data(), mod.data(), words, curve->_params().order_p_dash(), ws.data(), ws.size());
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);
583 static StorageUnit to_rep(
const GenericPrimeOrderCurve* curve, StorageUnit x) {
584 std::array<W, 2 * N> z;
585 curve->_params().mul(z, x, curve->_params().order_monty_r2());
586 return redc(curve, z);
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;
592 curve->_params().mul(z, redc_x, curve->_params().order_monty_r3());
593 return redc(curve, z);
596 const GenericPrimeOrderCurve* m_curve;
602class GenericField final {
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();
612 if(bytes.size() != len) {
619 if(!
bigint_ct_is_lt(words->data(), N, curve->_params().field().data(), N).as_bool()) {
624 return GenericField::from_words(curve, *words);
630 static GenericField from_words(
const GenericPrimeOrderCurve* curve,
const std::array<word, N>& words) {
631 return GenericField(curve, to_rep(curve, words));
634 static GenericField zero(
const GenericPrimeOrderCurve* curve) {
635 const StorageUnit zeros{};
636 return GenericField(curve, zeros);
639 static GenericField one(
const GenericPrimeOrderCurve* curve) {
640 return GenericField(curve, curve->_params().field_monty_r1());
643 static GenericField curve_a(
const GenericPrimeOrderCurve* curve) {
644 return GenericField(curve, curve->_params().monty_curve_a());
647 static GenericField curve_b(
const GenericPrimeOrderCurve* curve) {
648 return GenericField(curve, curve->_params().monty_curve_b());
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");
660 std::array<uint8_t, 2 *
sizeof(
word) * N> padded_bytes{};
661 copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
666 return GenericField(curve, wide_to_rep(curve, words.value()));
669 static GenericField random(
const GenericPrimeOrderCurve* curve, RandomNumberGenerator& rng) {
670 constexpr size_t MAX_ATTEMPTS = 1000;
672 const size_t bits = curve->_params().field_bits();
674 std::vector<uint8_t> buf(curve->_params().field_bytes());
676 for(
size_t i = 0; i != MAX_ATTEMPTS; ++i) {
682 const uint8_t mask = 0xFF >> (8 - (bits % 8));
686 if(
auto s = GenericField::deserialize(curve, buf)) {
687 if(s.value().is_nonzero().as_bool()) {
693 throw Internal_Error(
"Failed to generate random Scalar within bounded number of attempts");
699 GenericField div2()
const {
700 StorageUnit t = value();
704 bigint_cnd_add(borrow, t.data(), m_curve->_params().field_inv_2().data(), N);
706 return GenericField(m_curve, t);
710 GenericField mul2()
const {
711 StorageUnit t = value();
716 return GenericField(m_curve, r);
720 GenericField mul3()
const {
return mul2() + (*this); }
723 GenericField mul4()
const {
return mul2().mul2(); }
726 GenericField mul8()
const {
return mul2().mul2().mul2(); }
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();
733 const W carry =
bigint_add3(t.data(), a.data(), words, b.data(), words);
737 return GenericField(curve, r);
740 friend GenericField
operator-(
const GenericField& a,
const GenericField& b) {
return a + b.negate(); }
742 friend GenericField
operator*(
const GenericField& a,
const GenericField& b) {
743 const auto* curve = check_curve(a, b);
745 std::array<W, 2 * N> z;
746 curve->_params().mul(z, a.value(), b.value());
747 return GenericField(curve, redc(curve, z));
750 GenericField&
operator*=(
const GenericField& other) {
751 const auto* curve = check_curve(*
this, other);
753 std::array<W, 2 * N> z;
754 curve->_params().mul(z, value(), other.value());
755 m_val = redc(curve, z);
759 GenericField
square()
const {
760 std::array<W, 2 * N> z;
761 m_curve->_params().sqr(z, value());
762 return GenericField(m_curve, redc(m_curve, z));
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));
772 GenericField negate()
const {
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);
781 GenericField invert()
const {
return pow_vartime(m_curve->_params().field_minus_2()); }
783 GenericField invert_vartime()
const {
789 template <concepts::resizable_
byte_buffer T>
790 T serialize()
const {
791 T bytes(m_curve->_params().field_bytes());
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());
800 const size_t flen = m_curve->_params().field_bytes();
801 BOTAN_ARG_CHECK(bytes.size() == flen,
"Expected output span provided");
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));
809 CT::Choice is_zero()
const {
return CT::all_zeros(m_val.data(), m_curve->_params().words()).as_choice(); }
811 CT::Choice is_nonzero()
const {
return !is_zero(); }
813 CT::Choice
operator==(
const GenericField& other)
const {
814 if(this->m_curve != other.m_curve) {
818 return CT::is_equal(m_val.data(), other.m_val.data(), m_curve->_params().words()).as_choice();
821 const StorageUnit& stash_value()
const {
return m_val; }
823 const GenericPrimeOrderCurve* curve()
const {
return m_curve; }
825 CT::Choice is_even()
const {
826 auto v = from_rep(m_curve, m_val);
833 StorageUnit to_words()
const {
return from_rep(m_curve, m_val); }
835 void _const_time_poison()
const {
CT::poison(m_val); }
837 void _const_time_unpoison()
const {
CT::unpoison(m_val); }
839 static void conditional_swap(CT::Choice cond, GenericField& x, GenericField& y) {
840 const W mask = cond.into_bitmask<W>();
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]);
850 void conditional_assign(CT::Choice cond,
const GenericField& nx) {
851 const W mask = cond.into_bitmask<W>();
853 for(
size_t i = 0; i != N; ++i) {
854 m_val[i] =
choose(mask, nx.m_val[i], m_val[i]);
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>();
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]);
878 static void conditional_assign(GenericField& x,
882 const GenericField& nx,
883 const GenericField& ny,
884 const GenericField& nz) {
885 const W mask = cond.into_bitmask<W>();
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]);
894 std::pair<GenericField, CT::Choice> sqrt()
const {
897 auto z = pow_vartime(m_curve->_params().field_p_plus_1_over_4());
898 const CT::Choice correct = (z.square() == *
this);
900 z.conditional_assign(!correct, zero(m_curve));
904 GenericField(
const GenericPrimeOrderCurve* curve, StorageUnit val) : m_curve(curve), m_val(val) {}
907 const StorageUnit& value()
const {
return m_val; }
909 const W* data()
const {
return m_val.data(); }
911 static const GenericPrimeOrderCurve* check_curve(
const GenericField& a,
const GenericField& b) {
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();
922 r.data(), z.data(), mod.data(), words, curve->_params().field_p_dash(), ws.data(), ws.size());
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);
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);
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);
945 const GenericPrimeOrderCurve* m_curve;
956class GenericAffinePoint final {
958 GenericAffinePoint(
const GenericField& x,
const GenericField& y) : m_x(x), m_y(y) {}
960 explicit GenericAffinePoint(
const GenericPrimeOrderCurve* curve) :
961 m_x(GenericField::zero(curve)), m_y(GenericField::zero(curve)) {}
963 static GenericAffinePoint identity(
const GenericPrimeOrderCurve* curve) {
964 return GenericAffinePoint(GenericField::zero(curve), GenericField::zero(curve));
967 static GenericAffinePoint identity(
const GenericAffinePoint& pt) {
return identity(pt.curve()); }
969 CT::Choice is_identity()
const {
return x().is_zero() && y().is_zero(); }
971 GenericAffinePoint negate()
const {
return GenericAffinePoint(x(), y().negate()); }
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");
980 BufferStuffer
pack(bytes);
982 x().serialize_to(
pack.next(fe_bytes));
983 y().serialize_to(
pack.next(fe_bytes));
992 static auto ct_select(std::span<const GenericAffinePoint> pts,
size_t idx) {
994 auto result = GenericAffinePoint::identity(pts[0].curve());
997 const size_t idx1 = idx - 1;
998 for(
size_t i = 0; i != pts.size(); ++i) {
1000 result.conditional_assign(found, pts[i]);
1009 static GenericField x3_ax_b(
const GenericField& x) {
1010 return (x.square() + GenericField::curve_a(x.curve())) * x + GenericField::curve_b(x.curve());
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();
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));
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);
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();
1043 if(bytes.size() == 1 + fe_bytes && (bytes[0] == 0x02 || bytes[0] == 0x03)) {
1046 if(
auto x = GenericField::deserialize(curve, bytes.subspan(1, fe_bytes))) {
1047 auto [y, is_square] = x3_ax_b(*x).sqrt();
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);
1063 const GenericField& x()
const {
return m_x; }
1068 const GenericField& y()
const {
return m_y; }
1073 void conditional_assign(CT::Choice cond,
const GenericAffinePoint& pt) {
1074 GenericField::conditional_assign(m_x, m_y, cond, pt.x(), pt.y());
1077 const GenericPrimeOrderCurve* curve()
const {
return m_x.curve(); }
1088class GenericProjectivePoint final {
1090 typedef GenericProjectivePoint Self;
1092 using FieldElement = GenericField;
1097 static Self from_affine(
const GenericAffinePoint& pt) {
1098 const auto x = pt.x();
1100 auto z = GenericField::one(x.curve());
1103 GenericField::conditional_swap(pt.is_identity(), y, z);
1104 return GenericProjectivePoint(x, y, z);
1110 static Self identity(
const GenericPrimeOrderCurve* curve) {
1111 return Self(GenericField::zero(curve), GenericField::one(curve), GenericField::zero(curve));
1117 explicit GenericProjectivePoint(
const GenericPrimeOrderCurve* curve) :
1118 m_x(GenericField::zero(curve)), m_y(GenericField::one(curve)), m_z(GenericField::zero(curve)) {}
1123 GenericProjectivePoint(
const GenericField& x,
const GenericField& y) :
1124 m_x(x), m_y(y), m_z(GenericField::one(m_x.curve())) {}
1129 GenericProjectivePoint(
const GenericField& x,
const GenericField& y,
const GenericField& z) :
1130 m_x(x), m_y(y), m_z(z) {}
1132 friend Self operator+(
const Self& a,
const Self& b) {
return Self::add(a, b); }
1134 friend Self operator+(
const Self& a,
const GenericAffinePoint& b) {
return Self::add_mixed(a, b); }
1136 friend Self operator+(
const GenericAffinePoint& a,
const Self& b) {
return Self::add_mixed(b, a); }
1138 Self& operator+=(
const Self& other) {
1139 (*this) = (*this) + other;
1143 Self& operator+=(
const GenericAffinePoint& other) {
1144 (*this) = (*this) + other;
1148 CT::Choice is_identity()
const {
return z().is_zero(); }
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());
1157 static Self add_mixed(
const Self& a,
const GenericAffinePoint& b) {
1159 a, b, GenericField::one(a.curve()), GenericField::curve_a(a.curve()));
1165 static Self add_mixed_iso(
const Self& a,
const GenericAffinePoint& b,
const GenericField& curve_a) {
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()));
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()));
1185 static Self add_or_sub_iso(
const Self& a,
1186 const GenericAffinePoint& b,
1188 const GenericField& curve_a) {
1190 a, b, sub, GenericField::one(a.curve()), curve_a);
1201 Self dbl_n(
size_t n)
const {
1202 if(curve()->_params().a_is_minus_3()) {
1204 }
else if(curve()->_params().a_is_zero()) {
1207 const auto A = GenericField::curve_a(curve());
1218 Self dbl_n_iso(
const GenericField& a,
size_t n)
const {
1219 if(curve()->_params().a_is_zero()) {
1229 Self dbl_iso(
const GenericField& a)
const {
1230 if(curve()->_params().a_is_zero()) {
1241 if(curve()->_params().a_is_minus_3()) {
1243 }
else if(curve()->_params().a_is_zero()) {
1246 const auto A = GenericField::curve_a(curve());
1254 Self negate()
const {
return Self(x(), y().negate(), z()); }
1262 void randomize_rep(
const GenericField& r) {
1263 const auto r2 = r.square();
1264 const auto r3 = r2 * r;
1274 const GenericField& x()
const {
return m_x; }
1279 const GenericField& y()
const {
return m_y; }
1284 const GenericField& z()
const {
return m_z; }
1286 const GenericPrimeOrderCurve* curve()
const {
return m_x.curve(); }
1288 void _const_time_poison()
const {
CT::poison_all(m_x, m_y, m_z); }
1300class GenericCurve final {
1302 typedef GenericField FieldElement;
1303 typedef GenericScalar Scalar;
1304 typedef GenericAffinePoint AffinePoint;
1305 typedef GenericProjectivePoint ProjectivePoint;
1307 typedef word WordType;
1320class GenericBlindingRandomness final {
1323 static constexpr size_t Rerandomizations = 4;
1325 GenericBlindingRandomness(
const GenericPrimeOrderCurve* curve, RandomNumberGenerator& rng,
size_t scalars) :
1326 m_seeded(rng.is_seeded()),
1328 m_mask_bytes(mask_bytes(curve->_params().order_bits())),
1329 m_isomorphism(GenericField::one(curve)) {
1333 const size_t wide_bytes = curve->_params().field_bytes() + 8;
1338 m_masks.assign(buf.begin(), buf.begin() + m_scalars * m_mask_bytes);
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));
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));
1353 bool seeded()
const {
return m_seeded; }
1355 std::span<const uint8_t> mask(
size_t idx)
const {
1357 return std::span{m_masks}.subspan(idx * m_mask_bytes, m_mask_bytes);
1363 void randomize_rep(GenericProjectivePoint& pt,
size_t idx)
const {
1367 pt.randomize_rep(m_rerandomizers[idx]);
1374 const GenericField& isomorphism()
const {
return m_isomorphism; }
1377 static size_t mask_bytes(
size_t order_bits) {
1379 const size_t mask_words = (blinder_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
1380 return mask_words * WordInfo<word>::bytes;
1385 size_t m_mask_bytes;
1387 std::vector<GenericField> m_rerandomizers;
1388 GenericField m_isomorphism;
1391class GenericBlindedScalarBits final {
1396 GenericBlindedScalarBits(
const GenericScalar& scalar,
1397 const GenericBlindingRandomness& randomness,
1400 BOTAN_ASSERT_NOMSG(wb == 1 || wb == 2 || wb == 3 || wb == 4 || wb == 5 || wb == 6 || wb == 7);
1402 const auto& params = scalar.curve()->_params();
1404 const size_t order_bits = params.order_bits();
1410 if(blinder_bits > 0 && randomness.seeded()) {
1411 const size_t mask_words = (blinder_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
1413 const size_t words = params.words();
1415 const auto maskb = randomness.mask(idx);
1418 std::array<word, PrimeOrderCurve::StorageWords> mask{};
1419 load_le(mask.data(), maskb.data(), mask_words);
1422 const size_t excess = mask_words * WordInfo<word>::bits - blinder_bits;
1424 mask[mask_words - 1] &= (
static_cast<word>(1) << (WordInfo<word>::bits - excess)) - 1;
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;
1430 std::array<word, 2 * PrimeOrderCurve::StorageWords> mask_n{};
1432 const auto sw = scalar.to_words();
1435 params.mul(mask_n, mask, params.order());
1436 bigint_add2(mask_n.data(), 2 * words, sw.data(), words);
1438 std::reverse(mask_n.begin(), mask_n.end());
1440 m_bits = order_bits + blinder_bits;
1443 m_bytes = scalar.serialize<std::vector<uint8_t>>();
1444 m_bits = order_bits;
1447 m_windows = (m_bits + wb - 1) / wb;
1450 size_t windows()
const {
return m_windows; }
1452 size_t bits()
const {
return m_bits; }
1454 size_t get_window(
size_t offset)
const {
1455 if(m_window_bits == 1) {
1457 }
else if(m_window_bits == 2) {
1459 }
else if(m_window_bits == 3) {
1461 }
else if(m_window_bits == 4) {
1463 }
else if(m_window_bits == 5) {
1465 }
else if(m_window_bits == 6) {
1467 }
else if(m_window_bits == 7) {
1475 std::vector<uint8_t> m_bytes;
1478 size_t m_window_bits;
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;
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);
1503class GenericBaseMulTable final {
1505 static constexpr size_t WindowBits = BasePointWindowBits;
1508 explicit GenericBaseMulTable(
const GenericAffinePoint& pt) :
1509 m_table(
basemul_booth_setup<GenericCurve, WindowBits>(pt, blinded_scalar_bits(*pt.curve()) + 1)) {}
1511 GenericProjectivePoint mul(
const GenericScalar& s, RandomNumberGenerator& rng) {
1512 const GenericBlindingRandomness blinding(s.curve(), rng, 1);
1514 const GenericBlindedScalarBits scalar(s, blinding, 0, WindowBits + 1);
1519 static size_t blinded_scalar_bits(
const GenericPrimeOrderCurve& curve) {
1520 const size_t order_bits = curve.order_bits();
1524 std::vector<GenericAffinePoint> m_table;
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;
1539 const GenericBlindingRandomness blinding(x.curve(), rng, 2);
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);
1552 static constexpr size_t WindowBits = Mul2PrecompWindowBits;
1554 GenericVartimeWindowedMul2(
const GenericVartimeWindowedMul2& other) =
delete;
1555 GenericVartimeWindowedMul2(GenericVartimeWindowedMul2&& other) =
delete;
1556 GenericVartimeWindowedMul2& operator=(
const GenericVartimeWindowedMul2& other) =
delete;
1557 GenericVartimeWindowedMul2& operator=(GenericVartimeWindowedMul2&& other) =
delete;
1559 ~GenericVartimeWindowedMul2()
override =
default;
1561 GenericVartimeWindowedMul2(
const GenericAffinePoint& p,
const GenericAffinePoint& q) :
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>>();
1568 const auto& curve = m_table[0].curve();
1569 auto accum = GenericProjectivePoint(curve);
1571 const size_t order_bits = curve->order_bits();
1573 const size_t windows = (order_bits + WindowBits - 1) / WindowBits;
1575 for(
size_t i = 0; i != windows; ++i) {
1580 accum = accum.dbl_n(WindowBits);
1583 const size_t idx = (y_i << WindowBits) + x_i;
1586 accum += m_table[idx - 1];
1594 std::vector<GenericAffinePoint> m_table;
1601 m_params(std::make_unique<GenericCurveParams>(p, a, b, base_x, base_y, order)) {}
1605 m_basemul = std::make_unique<GenericBaseMulTable>(from_stash(
generator()));
1609 return _params().order_bits();
1613 return _params().order_bytes();
1617 return _params().field_bytes();
1623 return stash(m_basemul->mul(from_stash(scalar), rng));
1629 const auto pt_s = m_basemul->mul(from_stash(scalar), rng);
1632 if(
auto s = GenericScalar::from_wide_bytes(
this, x_bytes)) {
1635 throw Internal_Error(
"Failed to convert x coordinate to integer modulo scalar");
1642 return stash(
varpoint_mul(from_stash(pt), from_stash(scalar), rng));
1648 const auto pt_s =
varpoint_mul(from_stash(pt), from_stash(scalar), rng);
1655 return std::make_unique<GenericVartimeWindowedMul2>(from_stash(
generator()), from_stash(q));
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()) {
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()) {
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));
1687 if(!pt.is_identity().as_bool()) {
1688 const auto z2 = pt.z().square();
1690 const auto v_bytes = from_stash(v).serialize<std::vector<uint8_t>>();
1692 if(
auto fe_v = GenericField::deserialize(
this, v_bytes)) {
1693 if((*fe_v * z2 == pt.x()).as_bool()) {
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();
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();
1717 return stash(GenericAffinePoint::identity(
this));
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);
1727 BOTAN_ASSERT(valid_point.as_bool(),
"Computed point is on the curve");
1729 return stash(affine);
1733 return stash(GenericProjectivePoint::from_affine(from_stash(a)) + from_stash(b));
1737 return stash(from_stash(pt).negate());
1741 return from_stash(pt).is_identity().as_bool();
1745 from_stash(pt).serialize_to(bytes);
1750 from_stash(scalar).serialize_to(bytes);
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());
1765 std::span<const uint8_t> bytes)
const {
1766 if(
auto s = GenericScalar::from_wide_bytes(
this, bytes)) {
1767 return stash(s.value());
1774 std::span<const uint8_t> bytes)
const {
1775 if(
auto pt = GenericAffinePoint::deserialize_uncompressed(
this, bytes)) {
1776 return stash(pt.value());
1783 std::span<const uint8_t> bytes)
const {
1784 if(
auto pt = GenericAffinePoint::deserialize_compressed(
this, bytes)) {
1785 return stash(pt.value());
1792 return stash(from_stash(a) + from_stash(b));
1796 return stash(from_stash(a) - from_stash(b));
1800 return stash(from_stash(a) * from_stash(b));
1804 return stash(from_stash(s).
square());
1808 return stash(from_stash(s).invert());
1812 return stash(from_stash(s).invert_vartime());
1816 return stash(from_stash(s).negate());
1820 return from_stash(s).is_zero().as_bool();
1824 return (from_stash(a) == from_stash(b)).as_bool();
1828 return stash(GenericScalar::one(
this));
1832 return stash(GenericScalar::random(
this, rng));
1836 return Scalar::_create(shared_from_this(), s.stash_value());
1839GenericScalar GenericPrimeOrderCurve::from_stash(
const PrimeOrderCurve::Scalar& s)
const {
1841 return GenericScalar(
this, s._value());
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);
1852 const auto x = GenericField(
this, pt._x());
1853 const auto y = GenericField(
this, pt._y());
1854 return GenericAffinePoint(x, y);
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);
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);
1877 std::function<
void(std::span<uint8_t>)> expand_message)
const {
1879 throw Not_Implemented(
"Hash to curve is not implemented for this curve");
1883 std::function<
void(std::span<uint8_t>)> expand_message)
const {
1885 throw Not_Implemented(
"Hash to curve is not implemented for this curve");
1888std::shared_ptr<const PrimeOrderCurve> PCurveInstance::from_params(
1898 const size_t p_bits = p.
bits();
1907 if(p_bits != 521 && p_bits != 239 && (p_bits < 128 || p_bits > 512 || p_bits % 32 != 0)) {
1917 if(p_bits != order.
bits()) {
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);
1929 auto gpoc = std::make_shared<GenericPrimeOrderCurve>(p, a, b, base_x, base_y, order);
1939 gpoc->_precompute_base_mul();
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_STATE_CHECK(expr)
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT(expr, assertion_made)
#define BOTAN_ASSERT_UNREACHABLE()
static Barrett_Reduction for_public_modulus(const BigInt &m)
static constexpr Choice from_int(T v)
static constexpr Choice no()
static constexpr Mask< T > is_equal(T x, T y)
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
void _precompute_base_mul()
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
bool supports_hash_to_curve() const override
AffinePoint point_identity() const override
Return the identity element (aka the point at infinity).
size_t field_element_bytes() const override
ProjectivePoint mul(const AffinePoint &pt, const Scalar &scalar, RandomNumberGenerator &rng) const override
Scalar scalar_one() 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)
static constexpr size_t StorageWords
Number of words used to store MaximumByteLength.
std::array< word, StorageWords > StorageUnit
constexpr void pack(const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)
constexpr void conditional_swap(bool cnd, T &x, T &y)
constexpr void poison_all(const Ts &... ts)
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
constexpr void unpoison_all(const Ts &... ts)
constexpr void unpoison(const T *p, size_t n)
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
constexpr void poison(const T *p, size_t n)
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
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
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)
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)
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
void bigint_comba_sqr4(word z[8], const word x[4])
void bigint_comba_sqr6(word z[12], const word x[6])
constexpr ProjectivePoint dbl_a_minus_3(const ProjectivePoint &pt)
constexpr size_t scalar_blinding_bits(size_t scalar_bits)
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
BigInt square(const BigInt &x)
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)
OctetString operator+(const OctetString &k1, const OctetString &k2)
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
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)
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
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)
BigInt operator-(const BigInt &x, const BigInt &y)
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)
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)
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)
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)
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
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)
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
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)
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 >
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
void bigint_comba_sqr8(word z[16], const word x[8])
void bigint_comba_sqr9(word z[18], const word x[9])
constexpr ProjectivePoint dbl_generic(const ProjectivePoint &pt, const FieldElement &A)
bool operator==(const AlgorithmIdentifier &x, const AlgorithmIdentifier &y)
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.
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
constexpr auto store_be(ParamTs &&... params)
constexpr void clear_mem(T *ptr, size_t n)
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)
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)