12#include <botan/internal/ed25519_internal.h>
14#include <botan/internal/ed25519_fe.h>
34 return -(n * m.invert());
45 return two.pow_22523().sqr() * two;
53class Ed25519_Point_Completed final {
55 Ed25519_FieldElement X;
56 Ed25519_FieldElement Y;
57 Ed25519_FieldElement Z;
58 Ed25519_FieldElement T;
66class Ed25519_Point_Projective final {
68 Ed25519_FieldElement X;
69 Ed25519_FieldElement Y;
70 Ed25519_FieldElement Z;
75 static constexpr Ed25519_Point_Projective from(
const Ed25519_Point_Completed& p) {
76 Ed25519_Point_Projective r;
83 static constexpr Ed25519_Point_Projective identity() {
84 Ed25519_Point_Projective h;
91 void serialize_to(std::span<uint8_t, 32> s)
const {
92 const auto recip = this->Z.invert();
93 const auto x = this->X * recip;
94 const auto y = this->Y * recip;
96 s[31] ^= x.is_negative() ? 0x80 : 0x00;
99 constexpr Ed25519_Point_Completed dbl()
const;
102constexpr Ed25519_Point_Completed Ed25519_Point_Projective::dbl()
const {
103 Ed25519_Point_Completed r;
108 const auto t0 = r.Y.sqr();
121class Ed25519_Point_Extended final {
123 Ed25519_FieldElement X;
124 Ed25519_FieldElement Y;
125 Ed25519_FieldElement Z;
126 Ed25519_FieldElement T;
128 static constexpr Ed25519_Point_Extended identity() {
129 Ed25519_Point_Extended h;
130 h.X = Ed25519_FieldElement::zero();
131 h.Y = Ed25519_FieldElement::one();
132 h.Z = Ed25519_FieldElement::one();
133 h.T = Ed25519_FieldElement::zero();
137 constexpr Ed25519_Point_Completed dbl()
const {
138 Ed25519_Point_Projective q;
148 static constexpr Ed25519_Point_Extended from(
const Ed25519_Point_Completed& p) {
149 Ed25519_Point_Extended r;
157 void serialize_to(std::span<uint8_t, 32> out)
const {
158 const auto recip = this->Z.invert();
159 const auto x = this->X * recip;
160 const auto y = this->Y * recip;
162 out[31] ^= x.is_negative() ? 0x80 : 0x00;
173class Ed25519_Point_Niels final {
175 Ed25519_FieldElement yplusx;
176 Ed25519_FieldElement yminusx;
177 Ed25519_FieldElement xy2d;
179 static constexpr Ed25519_Point_Niels identity() {
180 Ed25519_Point_Niels h;
181 h.yplusx = Ed25519_FieldElement::one();
182 h.yminusx = Ed25519_FieldElement::one();
183 h.xy2d = Ed25519_FieldElement::zero();
188class Ed25519_Point_Cached final {
190 Ed25519_FieldElement YplusX;
191 Ed25519_FieldElement YminusX;
192 Ed25519_FieldElement Z;
193 Ed25519_FieldElement T2d;
198 static constexpr Ed25519_Point_Cached from(
const Ed25519_Point_Extended& p) {
199 Ed25519_Point_Cached r;
200 r.YplusX = p.Y + p.X;
201 r.YminusX = p.Y - p.X;
203 r.T2d = p.T * ED25519_D2;
210 static constexpr Ed25519_Point_Cached from(
const Ed25519_Point_Completed& p) {
211 return Ed25519_Point_Cached::from(Ed25519_Point_Extended::from(p));
218inline constexpr Ed25519_Point_Completed
operator+(
const Ed25519_Point_Extended& p,
const Ed25519_Point_Cached& q) {
219 Ed25519_Point_Completed r;
222 r.Z = r.X * q.YplusX;
223 r.Y = r.Y * q.YminusX;
226 const auto t0 = r.X + r.X;
237inline constexpr Ed25519_Point_Completed
operator+(
const Ed25519_Point_Extended& p,
const Ed25519_Point_Niels& q) {
238 Ed25519_Point_Completed r;
241 r.Z = r.X * q.yplusx;
242 r.Y = r.Y * q.yminusx;
244 const auto t0 = p.Z + p.Z;
255inline constexpr Ed25519_Point_Completed
operator-(
const Ed25519_Point_Extended& p,
const Ed25519_Point_Niels& q) {
256 Ed25519_Point_Completed r;
259 r.Z = r.X * q.yminusx;
260 r.Y = r.Y * q.yplusx;
262 const auto t0 = p.Z + p.Z;
273inline constexpr Ed25519_Point_Completed
operator-(
const Ed25519_Point_Extended& p,
const Ed25519_Point_Cached& q) {
274 Ed25519_Point_Completed r;
277 r.Z = r.X * q.YminusX;
278 r.Y = r.Y * q.YplusX;
281 const auto t0 = r.X + r.X;
289std::array<int8_t, 256> slide(std::span<const uint8_t, 32> a) {
290 std::array<int8_t, 256> r{};
291 for(
size_t i = 0; i < 256; ++i) {
292 r[i] = 1 & (a[i >> 3] >> (i & 7));
295 for(
size_t i = 0; i < 256; ++i) {
297 for(
size_t b = 1; b <= 6 && i + b < 256; ++b) {
299 if(r[i] + (r[i + b] << b) <= 15) {
300 r[i] += r[i + b] << b;
302 }
else if(r[i] - (r[i + b] << b) >= -15) {
303 r[i] -= r[i + b] << b;
304 for(
size_t k = i + b; k < 256; ++k) {
325Ed25519_Point_Extended ed25519_derive_basepoint() {
329 const auto yy = y.
sqr();
332 const auto v3 = v.sqr() * v;
333 const auto v7 = v3.sqr() * v;
334 auto x = (u * v3) * (u * v7).pow_22523();
336 if(!(x.sqr() * v - u).is_zero()) {
337 x = x * ED25519_SQRTM1;
339 if(x.is_negative()) {
343 Ed25519_Point_Extended b;
351const Ed25519_Point_Extended& ed25519_basepoint() {
352 static const Ed25519_Point_Extended b = ed25519_derive_basepoint();
360std::array<std::array<Ed25519_Point_Niels, 8>, 32> ed25519_base_precomp() {
361 constexpr size_t PTS = 32 * 8;
363 auto pts_storage = std::make_unique<std::array<Ed25519_Point_Extended, PTS>>();
364 auto& pts = *pts_storage;
366 auto base = ed25519_basepoint();
367 for(
size_t i = 0; i != 32; ++i) {
369 const auto base_c = Ed25519_Point_Cached::from(base);
370 for(
size_t j = 1; j != 8; ++j) {
371 pts[8 * i + j] = Ed25519_Point_Extended::from(pts[8 * i + j - 1] + base_c);
375 base = pts[8 * i + 7];
376 for(
size_t k = 0; k != 5; ++k) {
377 base = Ed25519_Point_Extended::from(base.dbl());
381 auto prod_storage = std::make_unique<std::array<Ed25519_FieldElement, PTS>>();
382 auto& prod = *prod_storage;
385 for(
size_t i = 1; i != PTS; ++i) {
386 prod[i] = prod[i - 1] * pts[i].Z;
389 auto inv = prod[PTS - 1].invert();
391 std::array<std::array<Ed25519_Point_Niels, 8>, 32> table;
392 for(
size_t i = PTS; i-- > 0;) {
393 const auto z_inv = (i == 0) ? inv : inv * prod[i - 1];
394 inv = inv * pts[i].Z;
396 const auto x = pts[i].X * z_inv;
397 const auto y = pts[i].Y * z_inv;
398 auto& n = table[i / 8][i % 8];
401 n.xy2d = ED25519_D2 * (x * y);
410std::array<Ed25519_Point_Niels, 8> ed25519_base_odd_multiples() {
411 std::array<Ed25519_Point_Extended, 8> m;
412 m[0] = ed25519_basepoint();
413 const auto base_2 = Ed25519_Point_Cached::from(Ed25519_Point_Extended::from(m[0].dbl()));
414 for(
size_t i = 1; i != 8; ++i) {
415 m[i] = Ed25519_Point_Extended::from(m[i - 1] + base_2);
418 std::array<Ed25519_FieldElement, 8> prod;
420 for(
size_t i = 1; i != 8; ++i) {
421 prod[i] = prod[i - 1] * m[i].Z;
424 auto inv = prod[7].invert();
426 std::array<Ed25519_Point_Niels, 8> r;
427 for(
size_t i = 8; i-- > 0;) {
428 const auto z_inv = (i == 0) ? inv : inv * prod[i - 1];
431 const auto x = m[i].X * z_inv;
432 const auto y = m[i].Y * z_inv;
434 r[i].yminusx = y - x;
435 r[i].xy2d = ED25519_D2 * (x * y);
440std::optional<Ed25519_Point_Extended> frombytes_negate_vartime(std::span<const uint8_t, 32> s) {
447 auto h = Ed25519_Point_Extended::identity();
451 auto v = u * ED25519_D;
455 const auto v3 = v.sqr() * v;
460 h.X = h.X.pow_22523();
464 auto vxx = h.X.sqr();
466 auto check = vxx - u;
467 if(!check.is_zero()) {
469 if(!check.is_zero()) {
472 h.X = h.X * ED25519_SQRTM1;
475 if(h.X.is_negative() ==
bool(s[31] >> 7)) {
486 if(h.X.is_zero() &&
bool(s[31] >> 7)) {
501void ge_double_scalarmult_vartime(std::span<uint8_t, 32> out,
502 const Ed25519_Scalar& a,
503 const Ed25519_Point_Extended& A,
504 const Ed25519_Scalar& b) {
505 static const std::array<Ed25519_Point_Niels, 8> Bi = ed25519_base_odd_multiples();
507 auto aslide = slide(a.to_bytes());
508 auto bslide = slide(b.to_bytes());
510 Ed25519_Point_Cached Ai[8];
511 Ai[0] = Ed25519_Point_Cached::from(A);
512 const auto A2 = Ed25519_Point_Extended::from(A.dbl());
514 for(
size_t i = 1; i != 8; ++i) {
515 Ai[i] = Ed25519_Point_Cached::from(A2 + Ai[i - 1]);
518 auto r = Ed25519_Point_Projective::identity();
520 int i = [&]() ->
int {
523 if(aslide[w] != 0 || bslide[w] != 0) {
536 t = Ed25519_Point_Extended::from(t) + Ai[aslide[i] >> 1];
537 }
else if(aslide[i] < 0) {
538 t = Ed25519_Point_Extended::from(t) - Ai[(-aslide[i]) >> 1];
542 t = Ed25519_Point_Extended::from(t) + Bi[bslide[i] >> 1];
543 }
else if(bslide[i] < 0) {
544 t = Ed25519_Point_Extended::from(t) - Bi[(-bslide[i]) >> 1];
547 r = Ed25519_Point_Projective::from(t);
550 r.serialize_to(std::span<uint8_t, 32>{out});
553Ed25519_Point_Niels select(
const Ed25519_Point_Niels base[8], int8_t b) {
554 const uint8_t bnegative =
static_cast<uint8_t
>(b) >> 7;
555 const uint8_t babs = b - ((-
static_cast<int>(bnegative) & b) * 2);
557 auto t = Ed25519_Point_Niels::identity();
559 for(
size_t i = 0; i != 8; ++i) {
561 t.yplusx.conditional_assign(b_is_i1, base[i].yplusx);
562 t.yminusx.conditional_assign(b_is_i1, base[i].yminusx);
563 t.xy2d.conditional_assign(b_is_i1, base[i].xy2d);
569 t.xy2d.conditional_assign(is_negative, -t.xy2d);
582Ed25519_Point_Extended basepoint_mul(
const Ed25519_Scalar& scalar) {
583 static const std::array<std::array<Ed25519_Point_Niels, 8>, 32> B_precomp = ed25519_base_precomp();
585 const auto a = scalar.to_bytes();
587 std::array<int8_t, 64> e{};
590 for(
size_t i = 0; i != 32; ++i) {
591 e[2 * i + 0] = (a[i] >> 0) & 0x0F;
592 e[2 * i + 1] = (a[i] >> 4) & 0x0F;
596 for(
size_t i = 0; i < 63; ++i) {
605 auto h = Ed25519_Point_Extended::identity();
606 for(
size_t i = 1; i < 64; i += 2) {
607 h = Ed25519_Point_Extended::from(h + select(B_precomp[i / 2].data(), e[i]));
610 auto s = Ed25519_Point_Projective::from(h.dbl());
611 s = Ed25519_Point_Projective::from(s.dbl());
612 s = Ed25519_Point_Projective::from(s.dbl());
613 h = Ed25519_Point_Extended::from(s.dbl());
615 for(
size_t i = 0; i != 64; i += 2) {
616 h = Ed25519_Point_Extended::from(h + select(B_precomp[i / 2].data(), e[i]));
625 const auto h = basepoint_mul(scalar);
630 const auto h = basepoint_mul(scalar);
644 const auto u = (h.Z + h.Y) * (h.Z - h.Y).invert();
652 if(
auto A = frombytes_negate_vartime(pk)) {
653 std::array<uint8_t, 32> rcheck{};
654 ge_double_scalarmult_vartime(rcheck, h, *A, s);
661 if(
auto A = frombytes_negate_vartime(pk)) {
679 std::array<uint8_t, 32> acheck{};
680 neg_A.serialize_to(acheck);
682 std::array<uint8_t, 32> rcheck{};
685 return CT::is_equal(rcheck.data(), acheck.data(), 32).as_bool();
static constexpr Mask< T > expand(T v)
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Ed25519_FieldElement from_word(word x)
static std::optional< Ed25519_FieldElement > deserialize(const uint8_t b[32])
constexpr Ed25519_FieldElement invert() const
constexpr Ed25519_FieldElement sqr() const
static constexpr void conditional_swap(CT::Choice cond, Ed25519_FieldElement &x, Ed25519_FieldElement &y)
static constexpr Ed25519_FieldElement one()
static constexpr Ed25519_FieldElement zero()
static Ed25519_Scalar zero()
static Ed25519_Scalar one()
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
void ed25519_basepoint_mul_to_x25519(std::span< uint8_t, 32 > out, const Ed25519_Scalar &scalar)
bool ed25519_valid_public_key_point(std::span< const uint8_t, 32 > pk)
OctetString operator+(const OctetString &k1, const OctetString &k2)
bool ed25519_check_signature(std::span< const uint8_t, 32 > pk, const Ed25519_Scalar &h, const uint8_t r[32], const Ed25519_Scalar &s)
BigInt operator-(const BigInt &x, const BigInt &y)
void ed25519_basepoint_mul(std::span< uint8_t, 32 > out, const Ed25519_Scalar &scalar)