7#ifndef BOTAN_PCURVES_IMPL_H_
8#define BOTAN_PCURVES_IMPL_H_
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/loadstor.h>
13#include <botan/internal/pcurves_util.h>
14#include <botan/internal/stl_util.h>
17#if defined(BOTAN_HAS_XMD)
18 #include <botan/internal/xmd.h>
61template <
typename Params>
62class MontgomeryRep
final {
64 using Self = MontgomeryRep<Params>;
66 static constexpr auto P = Params::P;
67 static constexpr size_t N = Params::N;
68 typedef typename Params::W W;
70 static_assert(N > 0 && (Params::P[0] & 1) == 1,
"Invalid Montgomery modulus");
74 static constexpr auto R1 = montygomery_r(P);
75 static constexpr auto R2 = mul_mod(R1, R1, P);
76 static constexpr auto R3 = mul_mod(R1, R2, P);
81 constexpr static std::array<W, N> one() {
return R1; }
86 constexpr static std::array<W, N> redc(
const std::array<W, 2 * N>& z) {
87 if constexpr(P_dash == 1) {
88 return monty_redc_pdash1(z, P);
90 return monty_redc(z, P, P_dash);
97 constexpr static std::array<W, N> to_rep(
const std::array<W, N>& x) {
98 std::array<W, 2 * N> z;
100 return Self::redc(z);
109 constexpr static std::array<W, N> wide_to_rep(
const std::array<W, 2 * N>& x) {
110 auto redc_x = Self::redc(x);
111 std::array<W, 2 * N> z;
113 return Self::redc(z);
119 constexpr static std::array<W, N> from_rep(
const std::array<W, N>& z) {
120 std::array<W, 2 * N> ze = {};
121 copy_mem(std::span{ze}.template first<N>(), z);
122 return Self::redc(ze);
144template <
typename Rep>
147 static constexpr auto P = Rep::P;
148 static constexpr size_t N = Rep::N;
149 typedef typename Rep::W W;
151 static constexpr auto P_MINUS_2 = p_minus<2>(P);
154 static constexpr size_t BITS = count_bits(P);
155 static constexpr size_t BYTES = (BITS + 7) / 8;
157 static constexpr auto P_MOD_4 = P[0] % 4;
159 using Self = IntMod<Rep>;
162 constexpr IntMod() : m_val({}) {}
164 IntMod(
const Self& other) =
default;
165 IntMod(Self&& other) =
default;
166 IntMod& operator=(
const Self& other) =
default;
167 IntMod& operator=(Self&& other) =
default;
176 static constexpr Self zero() {
return Self(std::array<W, N>{0}); }
181 static constexpr Self one() {
return Self(Rep::one()); }
192 static constexpr Self from_words(std::array<W, L> w) {
193 if constexpr(L == N) {
194 return Self(Rep::to_rep(w));
196 static_assert(L < N);
197 std::array<W, N> ew = {};
198 copy_mem(std::span{ew}.template first<L>(), w);
199 return Self(Rep::to_rep(ew));
206 constexpr CT::Choice is_zero()
const {
return CT::all_zeros(m_val.data(), m_val.size()).as_choice(); }
211 constexpr CT::Choice is_nonzero()
const {
return !is_zero(); }
216 constexpr CT::Choice is_one()
const {
return (*
this == Self::one()); }
221 constexpr CT::Choice is_even()
const {
222 auto v = Rep::from_rep(m_val);
229 friend constexpr Self
operator+(
const Self& a,
const Self&
b) {
241 friend constexpr Self
operator-(
const Self& a,
const Self&
b) {
254 constexpr auto INV_2 = p_div_2_plus_1(Rep::P);
258 std::array<W, N> t = value();
268 constexpr Self mul2()
const {
269 std::array<W, N> t = value();
278 constexpr Self mul3()
const {
return mul2() + (*this); }
281 constexpr Self mul4()
const {
return mul2().mul2(); }
284 constexpr Self mul8()
const {
return mul2().mul2().mul2(); }
289 friend constexpr Self
operator*(
const Self& a,
const Self&
b) {
290 std::array<W, 2 * N> z;
292 return Self(Rep::redc(z));
298 constexpr Self&
operator*=(
const Self& other) {
299 std::array<W, 2 * N> z;
301 m_val = Rep::redc(z);
310 static constexpr void conditional_assign(Self& x, CT::Choice cond,
const Self& nx) {
313 for(
size_t i = 0; i != N; ++i) {
314 x.m_val[i] =
choose(mask, nx.m_val[i], x.m_val[i]);
323 static constexpr void conditional_assign(Self& x, Self& y, CT::Choice cond,
const Self& nx,
const Self& ny) {
326 for(
size_t i = 0; i != N; ++i) {
327 x.m_val[i] =
choose(mask, nx.m_val[i], x.m_val[i]);
328 y.m_val[i] =
choose(mask, ny.m_val[i], y.m_val[i]);
337 static constexpr void conditional_assign(
338 Self& x, Self& y, Self& z, CT::Choice cond,
const Self& nx,
const Self& ny,
const Self& nz) {
341 for(
size_t i = 0; i != N; ++i) {
342 x.m_val[i] =
choose(mask, nx.m_val[i], x.m_val[i]);
343 y.m_val[i] =
choose(mask, ny.m_val[i], y.m_val[i]);
344 z.m_val[i] =
choose(mask, nz.m_val[i], z.m_val[i]);
353 constexpr Self
square()
const {
354 std::array<W, 2 * N> z;
356 return Self(Rep::redc(z));
366 constexpr void square_n(
size_t n) {
367 std::array<W, 2 * N> z;
368 for(
size_t i = 0; i != n; ++i) {
370 m_val = Rep::redc(z);
379 constexpr Self negate()
const {
383 bigint_sub3(r.data(), P.data(), N, this->data(), N);
384 x_is_zero.if_set_zero_out(r.data(), N);
401 constexpr Self pow_vartime(
const std::array<W, N>& exp)
const {
402 constexpr size_t WindowBits = (Self::BITS <= 256) ? 4 : 5;
403 constexpr size_t WindowElements = (1 << WindowBits) - 1;
405 constexpr size_t Windows = (Self::BITS + WindowBits - 1) / WindowBits;
413 std::array<Self, WindowElements> tbl;
417 for(
size_t i = 1; i != WindowElements; ++i) {
419 tbl[i] = tbl[i / 2].square();
421 tbl[i] = tbl[i - 1] * tbl[0];
425 auto r = Self::one();
427 const size_t w0 = read_window_bits<WindowBits>(std::span{exp}, (Windows - 1) * WindowBits);
433 for(
size_t i = 1; i != Windows; ++i) {
434 r.square_n(WindowBits);
436 const size_t w = read_window_bits<WindowBits>(std::span{exp}, (Windows - i - 1) * WindowBits);
459 constexpr Self invert()
const {
return pow_vartime(Self::P_MINUS_2); }
466 constexpr std::pair<Self, CT::Choice> sqrt()
const {
467 if constexpr(Self::P_MOD_4 == 3) {
470 constexpr auto P_PLUS_1_OVER_4 = p_plus_1_over_4(P);
471 auto z = pow_vartime(P_PLUS_1_OVER_4);
472 const CT::Choice correct = (z.square() == *
this);
474 Self::conditional_assign(z, !correct, Self::zero());
487 constexpr auto C1_C2 = shanks_tonelli_c1c2(Self::P);
488 constexpr std::array<W, N> C3 = shanks_tonelli_c3(C1_C2.second);
489 constexpr std::array<W, N> P_MINUS_1_OVER_2 = p_minus_1_over_2(Self::P);
490 constexpr Self C4 = shanks_tonelli_c4<Self>(P_MINUS_1_OVER_2);
491 constexpr Self C5 = C4.pow_vartime(C1_C2.second);
493 const Self& x = (*this);
495 auto z = x.pow_vartime(C3);
502 for(
size_t i = C1_C2.first; i >= 2; i--) {
504 const CT::Choice e =
b.is_one();
505 Self::conditional_assign(z, !e, z * c);
507 Self::conditional_assign(t, !e, t * c);
511 const CT::Choice correct = (z.square() == *
this);
512 Self::conditional_assign(z, !correct, Self::zero());
523 constexpr CT::Choice
operator==(
const Self& other)
const {
524 return CT::is_equal(this->data(), other.data(), N).as_choice();
530 constexpr CT::Choice
operator!=(
const Self& other)
const {
return !(*
this == other); }
535 constexpr std::array<W, Self::N> to_words()
const {
return Rep::from_rep(m_val); }
540 constexpr void serialize_to(std::span<uint8_t, Self::BYTES> bytes)
const {
541 auto v = Rep::from_rep(m_val);
542 std::reverse(v.begin(), v.end());
544 if constexpr(Self::BYTES == N * WordInfo<W>::bytes) {
548 const auto padded_bytes =
store_be(v);
549 constexpr size_t extra = N * WordInfo<W>::bytes - Self::BYTES;
550 copy_mem(bytes, std::span{padded_bytes}.template subspan<extra, Self::BYTES>());
560 std::array<W, L> stash_value()
const {
561 static_assert(L >= N);
562 std::array<W, L> stash = {};
563 for(
size_t i = 0; i != N; ++i) {
575 static Self from_stash(
const std::array<W, L>& stash) {
576 static_assert(L >= N);
577 std::array<W, N> val = {};
578 for(
size_t i = 0; i != N; ++i) {
593 static std::optional<Self> deserialize(std::span<const uint8_t> bytes) {
594 if(bytes.size() != Self::BYTES) {
598 const auto words = bytes_to_words<W, N, BYTES>(bytes.first<Self::BYTES>());
605 return Self::from_words(words);
615 static constexpr Self from_wide_bytes(std::span<const uint8_t, L> bytes) {
616 static_assert(8 * L <= 2 * Self::BITS);
617 std::array<uint8_t, 2 * BYTES> padded_bytes = {};
618 copy_mem(std::span{padded_bytes}.template last<L>(), bytes);
619 return Self(Rep::wide_to_rep(bytes_to_words<W, 2 * N, 2 * BYTES>(std::span{padded_bytes})));
628 static constexpr std::optional<Self> from_wide_bytes_varlen(std::span<const uint8_t> bytes) {
629 if(bytes.size() > 2 * Self::BYTES) {
633 std::array<uint8_t, 2 * Self::BYTES> padded_bytes = {};
634 copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
635 return Self(Rep::wide_to_rep(bytes_to_words<W, 2 * N, 2 * BYTES>(std::span{padded_bytes})));
649 static Self random(RandomNumberGenerator& rng) {
650 constexpr size_t MAX_ATTEMPTS = 1000;
652 std::array<uint8_t, Self::BYTES> buf;
654 for(
size_t i = 0; i != MAX_ATTEMPTS; ++i) {
659 if constexpr(Self::BITS % 8 != 0) {
660 constexpr uint8_t mask = 0xFF >> (8 - (Self::BITS % 8));
664 if(
auto s = Self::deserialize(buf)) {
665 if(s.value().is_nonzero().as_bool()) {
671 throw Internal_Error(
"Failed to generate random Scalar within bounded number of attempts");
679 static consteval Self constant(int8_t x) {
681 v[0] = (x >= 0) ? x : -x;
682 auto s = Self::from_words(v);
683 return (x >= 0) ? s : s.negate();
686 constexpr void _const_time_poison()
const {
CT::poison(m_val); }
688 constexpr void _const_time_unpoison()
const {
CT::unpoison(m_val); }
691 constexpr const std::array<W, N>& value()
const {
return m_val; }
693 constexpr const W* data()
const {
return m_val.data(); }
695 explicit constexpr IntMod(std::array<W, N> v) : m_val(v) {}
697 std::array<W, N> m_val;
705template <
typename FieldElement,
typename Params>
706class AffineCurvePoint
final {
711 static constexpr FieldElement A = FieldElement::from_words(Params::AW);
712 static constexpr FieldElement B = FieldElement::from_words(Params::BW);
714 static constexpr size_t BYTES = 1 + 2 * FieldElement::BYTES;
715 static constexpr size_t COMPRESSED_BYTES = 1 + FieldElement::BYTES;
717 using Self = AffineCurvePoint<FieldElement, Params>;
719 constexpr AffineCurvePoint(
const FieldElement& x,
const FieldElement& y) : m_x(x), m_y(y) {}
721 constexpr AffineCurvePoint() : m_x(FieldElement::zero()), m_y(FieldElement::zero()) {}
723 static constexpr Self identity() {
return Self(FieldElement::zero(), FieldElement::zero()); }
725 constexpr CT::Choice is_identity()
const {
return x().is_zero() && y().is_zero(); }
727 AffineCurvePoint(
const Self& other) =
default;
728 AffineCurvePoint(Self&& other) =
default;
729 AffineCurvePoint& operator=(
const Self& other) =
default;
730 AffineCurvePoint& operator=(Self&& other) =
default;
732 constexpr Self negate()
const {
return Self(x(), y().negate()); }
737 constexpr void serialize_to(std::span<uint8_t, Self::BYTES> bytes)
const {
739 BufferStuffer
pack(bytes);
741 x().serialize_to(
pack.next<FieldElement::BYTES>());
742 y().serialize_to(
pack.next<FieldElement::BYTES>());
749 constexpr void serialize_compressed_to(std::span<uint8_t, Self::COMPRESSED_BYTES> bytes)
const {
753 BufferStuffer
pack(bytes);
755 x().serialize_to(
pack.next<FieldElement::BYTES>());
762 constexpr void serialize_x_to(std::span<uint8_t, FieldElement::BYTES> bytes)
const {
764 x().serialize_to(bytes);
772 static constexpr auto ct_select(std::span<const Self> pts,
size_t idx) {
773 auto result = Self::identity();
776 const size_t idx1 =
static_cast<size_t>(idx - 1);
777 for(
size_t i = 0; i != pts.size(); ++i) {
779 result.conditional_assign(found, pts[i]);
788 static constexpr FieldElement x3_ax_b(
const FieldElement& x) {
return (x.square() + Self::A) * x + Self::B; }
798 static std::optional<Self> deserialize(std::span<const uint8_t> bytes) {
799 if(bytes.size() == Self::BYTES) {
800 if(bytes[0] == 0x04) {
801 auto x = FieldElement::deserialize(bytes.subspan(1, FieldElement::BYTES));
802 auto y = FieldElement::deserialize(bytes.subspan(1 + FieldElement::BYTES, FieldElement::BYTES));
805 const auto lhs = (*y).square();
806 const auto rhs = Self::x3_ax_b(*x);
807 if((lhs == rhs).as_bool()) {
811 }
else if(bytes[0] == 0x06 || bytes[0] == 0x07) {
814 auto x = FieldElement::deserialize(bytes.subspan(1, FieldElement::BYTES));
815 auto y = FieldElement::deserialize(bytes.subspan(1 + FieldElement::BYTES, FieldElement::BYTES));
817 if(x && y && (y_is_even == y->is_even()).as_bool()) {
818 const auto lhs = (*y).square();
819 const auto rhs = Self::x3_ax_b(*x);
820 if((lhs == rhs).as_bool()) {
825 }
else if(bytes.size() == Self::COMPRESSED_BYTES) {
826 if(bytes[0] == 0x02 || bytes[0] == 0x03) {
829 if(
auto x = FieldElement::deserialize(bytes.subspan(1, FieldElement::BYTES))) {
830 auto [y, is_square] = x3_ax_b(*x).sqrt();
832 if(is_square.as_bool()) {
833 const auto flip_y = y_is_even != y.is_even();
834 FieldElement::conditional_assign(y, flip_y, y.negate());
839 }
else if(bytes.size() == 1 && bytes[0] == 0x00) {
841 return Self::identity();
850 constexpr const FieldElement& x()
const {
return m_x; }
855 constexpr const FieldElement& y()
const {
return m_y; }
860 constexpr void conditional_assign(CT::Choice cond,
const Self& pt) {
861 FieldElement::conditional_assign(m_x, m_y, cond, pt.x(), pt.y());
864 constexpr void _const_time_poison()
const {
CT::poison_all(m_x, m_y); }
878template <
typename FieldElement,
typename Params>
879class ProjectiveCurvePoint {
884 static constexpr FieldElement A = FieldElement::from_words(Params::AW);
886 static constexpr bool A_is_zero = A.is_zero().as_bool();
887 static constexpr bool A_is_minus_3 = (A == FieldElement::constant(-3)).as_bool();
889 using Self = ProjectiveCurvePoint<FieldElement, Params>;
890 using AffinePoint = AffineCurvePoint<FieldElement, Params>;
895 static constexpr Self from_affine(
const AffinePoint& pt) {
896 if(pt.is_identity().as_bool()) {
897 return Self::identity();
899 return ProjectiveCurvePoint(pt.x(), pt.y());
906 static constexpr Self identity() {
return Self(FieldElement::zero(), FieldElement::one(), FieldElement::zero()); }
911 constexpr ProjectiveCurvePoint() :
912 m_x(FieldElement::zero()), m_y(FieldElement::one()), m_z(FieldElement::zero()) {}
917 constexpr ProjectiveCurvePoint(
const FieldElement& x,
const FieldElement& y) :
918 m_x(x), m_y(y), m_z(FieldElement::one()) {}
923 constexpr ProjectiveCurvePoint(
const FieldElement& x,
const FieldElement& y,
const FieldElement& z) :
924 m_x(x), m_y(y), m_z(z) {}
926 ProjectiveCurvePoint(
const Self& other) =
default;
927 ProjectiveCurvePoint(Self&& other) =
default;
928 ProjectiveCurvePoint& operator=(
const Self& other) =
default;
929 ProjectiveCurvePoint& operator=(Self&& other) =
default;
931 friend constexpr Self
operator+(
const Self& a,
const Self&
b) {
return Self::add(a,
b); }
933 friend constexpr Self
operator+(
const Self& a,
const AffinePoint&
b) {
return Self::add_mixed(a,
b); }
935 friend constexpr Self
operator+(
const AffinePoint& a,
const Self&
b) {
return Self::add_mixed(
b, a); }
937 constexpr Self&
operator+=(
const Self& other) {
938 (*this) = (*this) + other;
942 constexpr Self&
operator+=(
const AffinePoint& other) {
943 (*this) = (*this) + other;
947 friend constexpr Self
operator-(
const Self& a,
const Self&
b) {
return a +
b.negate(); }
949 constexpr CT::Choice is_identity()
const {
return z().is_zero(); }
951 constexpr void conditional_assign(CT::Choice cond,
const Self& pt) {
952 FieldElement::conditional_assign(m_x, m_y, m_z, cond, pt.x(), pt.y(), pt.z());
958 constexpr static Self add_mixed(
const Self& a,
const AffinePoint&
b) {
959 const auto a_is_identity = a.is_identity();
960 const auto b_is_identity =
b.is_identity();
961 if((a_is_identity && b_is_identity).as_bool()) {
962 return Self::identity();
971 const auto Z1Z1 = a.z().square();
972 const auto U2 =
b.x() * Z1Z1;
973 const auto S2 =
b.y() * a.z() * Z1Z1;
974 const auto H = U2 - a.x();
975 const auto r = S2 - a.y();
980 if((r.is_zero() && H.is_zero()).as_bool()) {
984 const auto HH = H.square();
985 const auto HHH = H * HH;
986 const auto V = a.x() * HH;
987 const auto t2 = r.square();
988 const auto t3 = V + V;
989 const auto t4 = t2 - HHH;
991 const auto t5 = V - X3;
992 const auto t6 = a.y() * HHH;
993 const auto t7 = r * t5;
998 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity,
b.x(),
b.y(), FieldElement::one());
1001 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
1003 return Self(X3, Y3, Z3);
1009 constexpr static Self add(
const Self& a,
const Self&
b) {
1010 const auto a_is_identity = a.is_identity();
1011 const auto b_is_identity =
b.is_identity();
1013 if((a_is_identity && b_is_identity).as_bool()) {
1014 return Self::identity();
1023 const auto Z1Z1 = a.z().square();
1024 const auto Z2Z2 =
b.z().square();
1025 const auto U1 = a.x() * Z2Z2;
1026 const auto U2 =
b.x() * Z1Z1;
1027 const auto S1 = a.y() *
b.z() * Z2Z2;
1028 const auto S2 =
b.y() * a.z() * Z1Z1;
1029 const auto H = U2 - U1;
1030 const auto r = S2 - S1;
1035 if((r.is_zero() && H.is_zero()).as_bool()) {
1039 const auto HH = H.square();
1040 const auto HHH = H * HH;
1041 const auto V = U1 * HH;
1042 const auto t2 = r.square();
1043 const auto t3 = V + V;
1044 const auto t4 = t2 - HHH;
1046 const auto t5 = V - X3;
1047 const auto t6 = S1 * HHH;
1048 const auto t7 = r * t5;
1050 const auto t8 =
b.z() * H;
1051 auto Z3 = a.z() * t8;
1054 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity,
b.x(),
b.y(),
b.z());
1057 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
1059 return Self(X3, Y3, Z3);
1065 constexpr Self dbl_n(
size_t n)
const {
1084 if constexpr(Self::A_is_zero) {
1086 auto ny = y().mul2();
1090 const auto ny2 = ny.square();
1091 const auto ny4 = ny2.square();
1092 const auto t1 = nx.square().mul3();
1093 const auto t2 = nx * ny2;
1094 nx = t1.square() - t2.mul2();
1096 ny = t1 * (t2 - nx).mul2() - ny4;
1099 return Self(nx, ny.div2(), nz);
1102 auto ny = y().mul2();
1104 auto w = nz.square().square();
1106 if constexpr(!Self::A_is_minus_3) {
1111 const auto ny2 = ny.square();
1112 const auto ny4 = ny2.square();
1114 if constexpr(Self::A_is_minus_3) {
1115 t1 = (nx.square() - w).mul3();
1117 t1 = nx.square().mul3() + w;
1119 const auto t2 = nx * ny2;
1120 nx = t1.square() - t2.mul2();
1122 ny = t1 * (t2 - nx).mul2() - ny4;
1128 return Self(nx, ny.div2(), nz);
1135 constexpr Self dbl()
const {
1144 FieldElement m = FieldElement::zero();
1146 if constexpr(Self::A_is_minus_3) {
1153 const auto z2 = z().square();
1154 m = (x() - z2).mul3() * (x() + z2);
1155 }
else if constexpr(Self::A_is_zero) {
1158 m = x().square().mul3();
1161 const auto z2 = z().square();
1162 m = x().square().mul3() + A * z2.square();
1166 const auto y2 = y().square();
1167 const auto s = x().mul4() * y2;
1168 const auto nx = m.square() - s.mul2();
1169 const auto ny = m * (s - nx) - y2.square().mul8();
1170 const auto nz = y().mul2() * z();
1172 return Self(nx, ny, nz);
1178 constexpr Self negate()
const {
return Self(x(), y().negate(), z()); }
1186 void randomize_rep(RandomNumberGenerator& rng) {
1190 if(rng.is_seeded()) {
1191 auto r = FieldElement::random(rng);
1193 auto r2 = r.square();
1205 constexpr const FieldElement& x()
const {
return m_x; }
1210 constexpr const FieldElement& y()
const {
return m_y; }
1215 constexpr const FieldElement& z()
const {
return m_z; }
1217 constexpr void _const_time_poison()
const {
CT::poison_all(m_x, m_y, m_z); }
1219 constexpr void _const_time_unpoison()
const {
CT::unpoison_all(m_x, m_y, m_z); }
1233template <StringLiteral PS,
1240class EllipticCurveParameters {
1251 static constexpr int8_t Z = ZI;
1257template <WordType WI,
size_t NI, std::array<WI, NI> PI>
1261 static constexpr size_t N = NI;
1262 static constexpr auto P = PI;
1270template <
typename Params,
template <
typename FieldParamsT>
typename FieldRep = MontgomeryRep>
1271class EllipticCurve {
1273 typedef typename Params::W W;
1275 static constexpr auto PW = Params::PW;
1276 static constexpr auto NW = Params::NW;
1277 static constexpr auto AW = Params::AW;
1280 static_assert(PW.size() == NW.size());
1282 class ScalarParams
final :
public IntParams<W, NW.size(), NW> {};
1284 using Scalar = IntMod<MontgomeryRep<ScalarParams>>;
1286 class FieldParams
final :
public IntParams<W, PW.size(), PW> {};
1288 using FieldElement = IntMod<FieldRep<FieldParams>>;
1290 using AffinePoint = AffineCurvePoint<FieldElement, Params>;
1291 using ProjectivePoint = ProjectiveCurvePoint<FieldElement, Params>;
1293 static constexpr size_t OrderBits = Scalar::BITS;
1294 static constexpr size_t PrimeFieldBits = FieldElement::BITS;
1296 static constexpr FieldElement A = FieldElement::from_words(Params::AW);
1297 static constexpr FieldElement B = FieldElement::from_words(Params::BW);
1299 static_assert(B.is_nonzero().as_bool(),
"B must be non-zero");
1301 static constexpr AffinePoint G =
1302 AffinePoint(FieldElement::from_words(Params::GXW), FieldElement::from_words(Params::GYW));
1304 static constexpr FieldElement SSWU_Z = FieldElement::constant(Params::Z);
1306 static constexpr bool ValidForSswuHash =
1307 (Params::Z != 0 && A.is_nonzero().as_bool() && B.is_nonzero().as_bool() && FieldElement::P_MOD_4 == 3);
1309 static constexpr bool OrderIsLessThanField =
bigint_cmp(NW.data(), NW.size(), PW.data(), PW.size()) == -1;
1317template <
typename C>
1319 { C::fe_invert2(
fe) } -> std::same_as<typename C::FieldElement>;
1328template <
typename C>
1329inline constexpr auto invert_field_element(
const typename C::FieldElement&
fe) {
1331 return C::fe_invert2(
fe) *
fe;
1340template <
typename C>
1341auto to_affine(
const typename C::ProjectivePoint& pt) {
1344 if(pt.is_identity().as_bool()) {
1345 return C::AffinePoint::identity();
1348 if constexpr(curve_supports_fe_invert2<C>) {
1349 const auto z2_inv = C::fe_invert2(pt.z());
1350 const auto z3_inv = z2_inv.square() * pt.z();
1351 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
1353 const auto z_inv = invert_field_element<C>(pt.z());
1354 const auto z2_inv = z_inv.square();
1355 const auto z3_inv = z_inv * z2_inv;
1356 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
1363template <
typename C>
1364auto to_affine_x(
const typename C::ProjectivePoint& pt) {
1365 if constexpr(curve_supports_fe_invert2<C>) {
1366 return pt.x() * C::fe_invert2(pt.z());
1368 const auto z_inv = invert_field_element<C>(pt.z());
1369 const auto z2_inv = z_inv.square();
1370 return pt.x() * z2_inv;
1377template <
typename C>
1378auto to_affine_batch(std::span<const typename C::ProjectivePoint> projective) {
1379 typedef typename C::AffinePoint AffinePoint;
1380 typedef typename C::FieldElement FieldElement;
1382 const size_t N = projective.size();
1383 std::vector<AffinePoint> affine(N, AffinePoint::identity());
1387 for(
const auto& pt : projective) {
1388 any_identity = any_identity || pt.is_identity();
1391 if(N <= 2 || any_identity.as_bool()) {
1395 for(
size_t i = 0; i != N; ++i) {
1396 affine[i] = to_affine<C>(projective[i]);
1399 std::vector<FieldElement> c(N);
1408 c[0] = projective[0].z();
1409 for(
size_t i = 1; i != N; ++i) {
1410 c[i] = c[i - 1] * projective[i].z();
1413 auto s_inv = invert_field_element<C>(c[N - 1]);
1415 for(
size_t i = N - 1; i > 0; --i) {
1416 const auto& p = projective[i];
1418 const auto z_inv = s_inv * c[i - 1];
1419 const auto z2_inv = z_inv.square();
1420 const auto z3_inv = z_inv * z2_inv;
1422 s_inv = s_inv * p.z();
1424 affine[i] = AffinePoint(p.x() * z2_inv, p.y() * z3_inv);
1427 const auto z2_inv = s_inv.square();
1428 const auto z3_inv = s_inv * z2_inv;
1429 affine[0] = AffinePoint(projective[0].x() * z2_inv, projective[0].y() * z3_inv);
1449template <
typename C,
size_t WindowBits>
1450class BlindedScalarBits
final {
1452 typedef typename C::W W;
1454 static constexpr bool BlindingEnabled =
true;
1460 static constexpr size_t blinding_bits(
size_t sb) {
1461 constexpr size_t wb = WordInfo<W>::bits;
1463 static_assert(wb == 32 || wb == 64,
"Unexpected W size");
1471 return blinding_bits(512);
1474 return ((sb / 4 + wb - 1) / wb) * wb;
1478 static constexpr size_t BlindingBits = blinding_bits(C::OrderBits);
1480 static_assert(BlindingBits % WordInfo<W>::bits == 0);
1481 static_assert(BlindingBits < C::Scalar::BITS);
1484 static constexpr size_t Bits = C::Scalar::BITS + (BlindingEnabled ? BlindingBits : 0);
1485 static constexpr size_t Bytes = (Bits + 7) / 8;
1487 BlindedScalarBits(
const typename C::Scalar& scalar, RandomNumberGenerator& rng) {
1488 if constexpr(BlindingEnabled) {
1489 constexpr size_t mask_words = BlindingBits / WordInfo<W>::bits;
1490 constexpr size_t mask_bytes = mask_words * WordInfo<W>::bytes;
1492 constexpr size_t n_words = C::NW.size();
1494 uint8_t maskb[mask_bytes] = {0};
1495 if(rng.is_seeded()) {
1496 rng.randomize(maskb, mask_bytes);
1505 std::array<uint8_t, C::Scalar::BYTES> sbytes;
1506 scalar.serialize_to(sbytes);
1507 for(
size_t i = 0; i != sbytes.size(); ++i) {
1508 maskb[i % mask_bytes] ^= sbytes[i];
1512 W mask[n_words] = {0};
1513 load_le(mask, maskb, mask_words);
1514 mask[mask_words - 1] |= WordInfo<W>::top_bit;
1517 W mask_n[2 * n_words] = {0};
1519 const auto sw = scalar.to_words();
1525 std::reverse(mask_n, mask_n + 2 * n_words);
1528 static_assert(Bytes == C::Scalar::BYTES);
1529 m_bytes.resize(Bytes);
1530 scalar.serialize_to(std::span{m_bytes}.template first<Bytes>());
1536 size_t get_window(
size_t offset)
const {
1538 return read_window_bits<WindowBits>(std::span{m_bytes}, offset);
1541 ~BlindedScalarBits() {
1548 std::vector<uint8_t> m_bytes;
1551template <
typename C,
size_t WindowBits>
1552class UnblindedScalarBits
final {
1554 static constexpr size_t Bits = C::Scalar::BITS;
1556 UnblindedScalarBits(
const typename C::Scalar& scalar) { scalar.serialize_to(std::span{m_bytes}); }
1558 size_t get_window(
size_t offset)
const {
1560 return read_window_bits<WindowBits>(std::span{m_bytes}, offset);
1564 std::array<uint8_t, C::Scalar::BYTES> m_bytes;
1604template <
typename C,
size_t W>
1605class PrecomputedBaseMulTable
final {
1607 typedef typename C::Scalar Scalar;
1608 typedef typename C::AffinePoint AffinePoint;
1609 typedef typename C::ProjectivePoint ProjectivePoint;
1611 static constexpr size_t WindowBits = W;
1612 static_assert(WindowBits >= 1 && WindowBits <= 8);
1614 using BlindedScalar = BlindedScalarBits<C, WindowBits>;
1616 static constexpr size_t Windows = (BlindedScalar::Bits + WindowBits - 1) / WindowBits;
1618 static_assert(Windows > 1);
1621 static constexpr size_t WindowElements = (1 << WindowBits) - 1;
1623 static constexpr size_t TableSize = Windows * WindowElements;
1625 PrecomputedBaseMulTable(
const AffinePoint& p) : m_table{} {
1626 std::vector<ProjectivePoint> table;
1627 table.reserve(TableSize);
1629 auto accum = ProjectivePoint::from_affine(p);
1631 for(
size_t i = 0; i != TableSize; i += WindowElements) {
1632 table.push_back(accum);
1634 for(
size_t j = 1; j != WindowElements; ++j) {
1636 table.emplace_back(table[i + j / 2].dbl());
1638 table.emplace_back(table[i + j - 1] + table[i]);
1642 accum = table[i + (WindowElements / 2)].dbl();
1645 m_table = to_affine_batch<C>(table);
1648 ProjectivePoint mul(
const Scalar& s, RandomNumberGenerator& rng)
const {
1649 const BlindedScalar bits(s, rng);
1652 auto table = std::span{m_table};
1654 auto accum = [&]() {
1655 const size_t w_0 = bits.get_window(0);
1656 const auto tbl_0 = table.first(WindowElements);
1657 auto pt = ProjectivePoint::from_affine(AffinePoint::ct_select(tbl_0, w_0));
1659 pt.randomize_rep(rng);
1663 for(
size_t i = 1; i != Windows; ++i) {
1664 const size_t w_i = bits.get_window(WindowBits * i);
1665 const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
1672 accum += AffinePoint::ct_select(tbl_i, w_i);
1675 accum.randomize_rep(rng);
1684 std::vector<AffinePoint> m_table;
1692template <
typename C,
size_t W>
1693class WindowedMulTable
final {
1695 typedef typename C::Scalar Scalar;
1696 typedef typename C::AffinePoint AffinePoint;
1697 typedef typename C::ProjectivePoint ProjectivePoint;
1699 static constexpr size_t WindowBits = W;
1700 static_assert(WindowBits >= 1 && WindowBits <= 8);
1702 using BlindedScalar = BlindedScalarBits<C, WindowBits>;
1704 static constexpr size_t Windows = (BlindedScalar::Bits + WindowBits - 1) / WindowBits;
1706 static_assert(Windows > 1);
1709 static constexpr size_t TableSize = (1 << WindowBits) - 1;
1711 WindowedMulTable(
const AffinePoint& p) : m_table{} {
1712 std::vector<ProjectivePoint> table;
1713 table.reserve(TableSize);
1715 table.push_back(ProjectivePoint::from_affine(p));
1716 for(
size_t i = 1; i != TableSize; ++i) {
1718 table.push_back(table[i / 2].dbl());
1720 table.push_back(table[i - 1] + p);
1724 m_table = to_affine_batch<C>(table);
1727 ProjectivePoint mul(
const Scalar& s, RandomNumberGenerator& rng)
const {
1728 const BlindedScalar bits(s, rng);
1730 auto accum = [&]() {
1731 const size_t w_0 = bits.get_window((Windows - 1) * WindowBits);
1734 auto pt = ProjectivePoint::from_affine(AffinePoint::ct_select(m_table, w_0));
1736 pt.randomize_rep(rng);
1740 for(
size_t i = 1; i != Windows; ++i) {
1741 accum = accum.dbl_n(WindowBits);
1742 const size_t w_i = bits.get_window((Windows - i - 1) * WindowBits);
1769 accum += AffinePoint::ct_select(m_table, w_i);
1772 accum.randomize_rep(rng);
1781 std::vector<AffinePoint> m_table;
1804template <
typename C,
size_t W>
1805class WindowedMul2Table
final {
1808 static_assert(W >= 1 && W <= 4);
1810 typedef typename C::Scalar Scalar;
1811 typedef typename C::AffinePoint AffinePoint;
1812 typedef typename C::ProjectivePoint ProjectivePoint;
1814 static constexpr size_t WindowBits = W;
1816 static constexpr size_t WindowSize = (1 << WindowBits);
1819 static constexpr size_t TableSize = (1 << (2 * WindowBits)) - 1;
1821 WindowedMul2Table(
const AffinePoint& x,
const AffinePoint& y) {
1822 std::vector<ProjectivePoint> table;
1823 table.reserve(TableSize);
1825 for(
size_t i = 0; i != TableSize; ++i) {
1826 const size_t t_i = (i + 1);
1827 const size_t x_i = t_i % WindowSize;
1828 const size_t y_i = (t_i >> WindowBits) % WindowSize;
1831 auto next_tbl_e = [&]() {
1832 if(x_i % 2 == 0 && y_i % 2 == 0) {
1835 return table[(t_i / 2) - 1].dbl();
1836 }
else if(x_i > 0 && y_i > 0) {
1839 return x + table[(y_i << WindowBits) - 1];
1840 }
else if(y_i == 1) {
1841 return table[x_i - 1] + y;
1843 return table[x_i - 1] + table[(y_i << WindowBits) - 1];
1845 }
else if(x_i > 0 && y_i == 0) {
1849 return ProjectivePoint::from_affine(x);
1852 return x + table[x_i - 1 - 1];
1854 }
else if(x_i == 0 && y_i > 0) {
1857 return ProjectivePoint::from_affine(y);
1860 return y + table[((y_i - 1) << WindowBits) - 1];
1867 table.emplace_back(next_tbl_e());
1870 m_table = to_affine_batch<C>(table);
1876 ProjectivePoint mul2(
const Scalar& s1,
const Scalar& s2, RandomNumberGenerator& rng)
const {
1877 using BlindedScalar = BlindedScalarBits<C, WindowBits>;
1879 BlindedScalar bits1(s1, rng);
1880 BlindedScalar bits2(s2, rng);
1882 constexpr size_t Windows = (BlindedScalar::Bits + WindowBits - 1) / WindowBits;
1884 auto accum = ProjectivePoint::identity();
1886 for(
size_t i = 0; i != Windows; ++i) {
1888 accum = accum.dbl_n(WindowBits);
1891 const size_t w_1 = bits1.get_window((Windows - i - 1) * WindowBits);
1892 const size_t w_2 = bits2.get_window((Windows - i - 1) * WindowBits);
1893 const size_t window = w_1 + (w_2 << WindowBits);
1894 accum += AffinePoint::ct_select(m_table, window);
1897 accum.randomize_rep(rng);
1913 ProjectivePoint mul2_vartime(
const Scalar& s1,
const Scalar& s2)
const {
1914 constexpr size_t Windows = (Scalar::BITS + WindowBits - 1) / WindowBits;
1916 const UnblindedScalarBits<C, W> bits1(s1);
1917 const UnblindedScalarBits<C, W> bits2(s2);
1919 auto accum = ProjectivePoint::identity();
1921 for(
size_t i = 0; i != Windows; ++i) {
1923 accum = accum.dbl_n(WindowBits);
1926 const size_t w_1 = bits1.get_window((Windows - i - 1) * WindowBits);
1927 const size_t w_2 = bits2.get_window((Windows - i - 1) * WindowBits);
1929 const size_t window = w_1 + (w_2 << WindowBits);
1932 accum += m_table[window - 1];
1940 std::vector<AffinePoint> m_table;
1948template <
typename C>
1949const auto& SSWU_C2()
1950 requires C::ValidForSswuHash
1953 static const typename C::FieldElement C2 = C::B * invert_field_element<C>(C::SSWU_Z * C::A);
1962template <
typename C>
1963const auto& SSWU_C1()
1964 requires C::ValidForSswuHash
1968 static const typename C::FieldElement C1 = (SSWU_C2<C>() * C::SSWU_Z).negate();
1977template <
typename C>
1978inline auto map_to_curve_sswu(
const typename C::FieldElement& u) ->
typename C::AffinePoint {
1980 const auto z_u2 = C::SSWU_Z * u.square();
1981 const auto z2_u4 = z_u2.square();
1982 const auto tv1 = invert_field_element<C>(z2_u4 + z_u2);
1983 auto x1 = SSWU_C1<C>() * (C::FieldElement::one() + tv1);
1984 C::FieldElement::conditional_assign(x1, tv1.is_zero(), SSWU_C2<C>());
1985 const auto gx1 = C::AffinePoint::x3_ax_b(x1);
1987 const auto x2 = z_u2 * x1;
1988 const auto gx2 = C::AffinePoint::x3_ax_b(x2);
1991 const auto [gx1_sqrt, gx1_is_square] = gx1.sqrt();
1995 auto y = gx2.sqrt().first;
1997 C::FieldElement::conditional_assign(x, y, gx1_is_square, x1, gx1_sqrt);
1999 const auto flip_y = y.is_even() != u.is_even();
2000 C::FieldElement::conditional_assign(y, flip_y, y.negate());
2002 auto pt =
typename C::AffinePoint(x, y);
2016template <
typename C,
bool RO>
2017 requires C::ValidForSswuHash
2018inline auto hash_to_curve_sswu(std::string_view hash, std::span<const uint8_t> pw, std::span<const uint8_t> dst)
2019 -> std::conditional_t<RO, typename C::ProjectivePoint, typename C::AffinePoint> {
2020#if defined(BOTAN_HAS_XMD)
2021 constexpr size_t SecurityLevel = (C::OrderBits + 1) / 2;
2022 constexpr size_t L = (C::PrimeFieldBits + SecurityLevel + 7) / 8;
2023 constexpr size_t Cnt = RO ? 2 : 1;
2025 std::array<uint8_t, L * Cnt> xmd;
2030 const auto u0 = C::FieldElement::from_wide_bytes(std::span<const uint8_t, L>(xmd.data(), L));
2031 const auto u1 = C::FieldElement::from_wide_bytes(std::span<const uint8_t, L>(xmd.data() + L, L));
2033 auto accum = C::ProjectivePoint::from_affine(map_to_curve_sswu<C>(u0));
2034 accum += map_to_curve_sswu<C>(u1);
2037 const auto u = C::FieldElement::from_wide_bytes(std::span<const uint8_t, L>(xmd.data(), L));
2038 return map_to_curve_sswu<C>(u);
2042 throw Not_Implemented(
"Hash to curve not available due to missing XMD");
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_STATE_CHECK(expr)
#define BOTAN_ASSERT_UNREACHABLE()
static constexpr Choice from_int(T v)
static constexpr Choice no()
static constexpr Mask< T > from_choice(Choice c)
static constexpr Mask< T > is_equal(T x, T y)
static FE_25519 invert(const FE_25519 &a)
int(* final)(unsigned char *, CTX *)
constexpr void pack(const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)
constexpr void unpoison_all(Ts &&... ts)
constexpr void poison_all(Ts &&... ts)
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
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_add(std::span< W, N > z, std::span< const W, N > x, std::span< const W, N > y) -> W
constexpr W shift_left(std::array< W, N > &x)
constexpr void comba_sqr(W z[2 *N], const W x[N])
BigInt operator*(const BigInt &x, const BigInt &y)
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
BigInt square(const BigInt &x)
OctetString operator+(const OctetString &k1, const OctetString &k2)
constexpr T choose(T mask, T a, T b)
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr auto monty_inverse(W a) -> W
BigInt operator-(const BigInt &x, const BigInt &y)
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
void secure_scrub_memory(void *ptr, size_t n)
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
void expand_message_xmd(std::string_view hash_fn, std::span< uint8_t > output, std::span< const uint8_t > input, std::span< const uint8_t > domain_sep)
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
constexpr W bigint_cnd_add(W cnd, W x[], size_t x_size, const W y[], size_t y_size)
void carry(int64_t &h0, int64_t &h1)
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
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 >
constexpr auto hex_to_words(const char(&s)[N])
constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr void copy_mem(T *out, const T *in, size_t n)
constexpr auto store_be(ParamTs &&... params)
constexpr W shift_right(std::array< W, N > &x)
constexpr auto operator*=(Strong< T1, Tags... > &a, T2 b)