9#include <botan/internal/ed448_internal.h>
11#include <botan/exceptn.h>
12#include <botan/types.h>
14#include <botan/internal/buffer_slicer.h>
15#include <botan/internal/buffer_stuffer.h>
16#include <botan/internal/concat_util.h>
17#include <botan/internal/ct_utils.h>
18#include <botan/internal/loadstor.h>
23std::vector<uint8_t> dom4(uint8_t x, std::span<const uint8_t> y) {
32 store_le(
static_cast<uint8_t
>(y.size())),
37std::array<uint8_t, 2 * ED448_LEN> shake(
bool f, std::span<const uint8_t> context, Ts... xs) {
39 shake_xof->update(dom4(
static_cast<uint8_t
>(f), context));
40 (shake_xof->update(std::span(xs)), ...);
41 std::array<uint8_t, 2 * ED448_LEN> res{};
42 shake_xof->output(res);
46std::pair<std::span<const uint8_t, 57>, std::span<const uint8_t, 57>> split(std::span<const uint8_t, 114> arr) {
48 const auto lhs = bs.take<57>();
49 const auto rhs = bs.take<57>();
59 std::array<uint8_t, ED448_LEN> raw_s{};
60 shake_xof.output(raw_s);
80 if((enc.back() & 0x7F) != 0) {
81 throw Decoding_Error(
"Ed448 point has unacceptable x-distinguisher");
83 const bool x_distinguisher = enc.back() != 0;
84 const auto y_data = std::span(enc).first<56>();
105 if(v *
square(maybe_x) != u) {
111 if(maybe_x.is_zero() && x_distinguisher) {
114 const bool maybe_x_parity = maybe_x.
is_odd();
115 std::array<uint64_t, WORDS_448> x_data{};
117 .select_n(x_data.data(), maybe_x.words().data(), (-maybe_x).words().data(),
WORDS_448);
123 constexpr std::array<const uint64_t, WORDS_448>
x = {0x2626a82bc70cc05e,
130 constexpr std::array<const uint64_t, WORDS_448>
y = {0x9808795bf230fa14,
141 std::array<uint8_t, ED448_LEN> res_buf = {0};
145 const auto x = m_x * z_inv;
146 const auto y = m_y * z_inv;
153 y.to_bytes(std::span(res_buf).first<56>());
157 res_buf.back() = (
static_cast<uint8_t
>(
x.is_odd()) << 7);
171 const Gf448Elem H = (m_x + m_y) * (other.m_x + other.m_y);
172 const Gf448Elem X3 = A * F * (H - C - D);
213 for(
size_t i = 2; i < 16; ++i) {
215 table[i] = table[i / 2].double_point();
217 table[i] = table[i - 1] + *
this;
224 for(
int window = 111; window >= 0; --window) {
226 res = res.double_point();
227 res = res.double_point();
228 res = res.double_point();
229 res = res.double_point();
232 const uint64_t w = s.
get_window(
static_cast<size_t>(window) * 4, 4);
236 for(
size_t i = 0; i < 16; ++i) {
238 selected.ct_conditional_assign(correct_idx, table[i]);
241 res = res + selected;
253 constexpr size_t W = 4;
254 constexpr size_t WindowElements = (1 << W) - 1;
255 constexpr size_t Windows = (448 + W - 1) / W;
256 constexpr size_t TableSize = Windows * WindowElements;
258 static const auto table = []() {
263 for(
size_t i = 0; i < TableSize; i += WindowElements) {
266 for(
size_t j = 1; j < WindowElements; ++j) {
268 tbl[i + j] = tbl[i + j / 2].double_point();
270 tbl[i + j] = tbl[i + j - 1] + tbl[i];
282 for(
size_t i = 0; i != Windows; ++i) {
283 const uint8_t w =
static_cast<uint8_t
>(scalar.
get_window(i * W, W));
287 for(
size_t j = 0; j != WindowElements; ++j) {
289 selected.ct_conditional_assign(assign, table[i * WindowElements + j]);
292 res = res + selected;
308 const auto p1x3 = p1x2 + p1;
310 const auto p2x3 = p2x2 + p2;
313 const std::array<Ed448Point, 15> table = {
334 for(
int window = 222; window >= 0; --window) {
335 res = res.double_point();
336 res = res.double_point();
338 const size_t bit_pos =
static_cast<size_t>(window) * 2;
342 res = res + table[idx - 1];
353 const auto lhs_x = m_x * other.m_z;
354 const auto rhs_x = other.m_x * m_z;
355 const auto lhs_y = m_y * other.m_z;
356 const auto rhs_y = other.m_y * m_z;
361 return (mask_x & mask_y).as_bool();
365 m_x.ct_cond_assign(mask, other.m_x);
366 m_y.ct_cond_assign(mask, other.m_y);
367 m_z.ct_cond_assign(mask, other.m_z);
378 shake_xof->update(sk);
380 const Scalar448 s = scalar_from_xof(*shake_xof);
387std::array<uint8_t, 2 * ED448_LEN>
sign_message(std::span<const uint8_t, ED448_LEN> sk,
388 std::span<const uint8_t, ED448_LEN> pk,
390 std::span<const uint8_t> context,
391 std::span<const uint8_t> msg) {
402 shake_xof->update(sk);
403 const Scalar448 s = scalar_from_xof(*shake_xof);
404 std::array<uint8_t, ED448_LEN> prefix{};
405 shake_xof->output(prefix);
410 const Scalar448 r(shake(pgflag, context, prefix, msg));
417 const Scalar448 k(shake(pgflag, context, big_r, pk, msg));
420 const auto big_s = r + k * s;
424 std::array<uint8_t, 2 * ED448_LEN> sig{};
435 std::span<const uint8_t> context,
436 std::span<const uint8_t> sig,
437 std::span<const uint8_t> msg) {
450 const auto [big_r_bytes, big_s_bytes] = split(sig.first<2 *
ED448_LEN>());
460 const Scalar448 k(shake(phflag, context, big_r_bytes, pk, msg));
471 if(A.is_identity()) {
480 constexpr std::array<uint8_t, 56> L_minus_1 = {
481 0xf2, 0x44, 0x58, 0xab, 0x92, 0xc2, 0x78, 0x23, 0x55, 0x8f, 0xc5, 0x8d, 0x72, 0xc2, 0x6c, 0x21, 0x90, 0x36, 0xd6,
482 0xae, 0x49, 0xdb, 0x4e, 0xc4, 0xe9, 0x23, 0xca, 0x7c, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
483 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f};
485 if((
Scalar448(L_minus_1) * A) != A.negate()) {
486 throw Decoding_Error(
"Ed448 public key is not in the prime order subgroup");
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT(expr, assertion_made)
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr void append(std::span< const uint8_t > buffer)
constexpr bool full() const
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > expand_bool(bool v)
Representation of a point on the Ed448 curve.
Ed448Point negate() const
Negate the point.
Gf448Elem y() const
Getter for point coordinate y.
static Ed448Point identity()
Return the identity element.
static Ed448Point base_point_mul(const Scalar448 &scalar)
Fixed base point scalar multiplication (precomputed table, no doublings).
Ed448Point(const Gf448Elem &x, const Gf448Elem &y, const Gf448Elem &z)
Create a point from its projective coordinates X, Y, Z.
static Ed448Point double_scalar_mul_vartime(const Scalar448 &s1, const Ed448Point &p1, const Scalar448 &s2, const Ed448Point &p2)
Variable-time double scalar multiplication using Shamir's trick: [s1]P + [s2]Q.
static Ed448Point decode(std::span< const uint8_t, ED448_LEN > enc)
Decode a point from its 57-byte encoding (RFC 8032 5.2.3).
Ed448Point scalar_mul(const Scalar448 &scalar) const
Scalar multiplication.
Ed448Point double_point() const
Double a point (RFC 8032 5.2.4).
static Ed448Point base_point()
Create the curve's base point ('B' in RFC 8032 5.2).
void ct_conditional_assign(CT::Mask< uint64_t > mask, const Ed448Point &other)
Assign other to this if mask is set (constant time).
bool operator==(const Ed448Point &other) const
Check if two points are equal (constant time).
Ed448Point operator+(const Ed448Point &other) const
Add two points (RFC 8032 5.2.4).
Gf448Elem x() const
Getter for point coordinate x.
std::array< uint8_t, ED448_LEN > encode() const
Encode the point to its 57-byte representation (RFC 8032 5.2.2).
static bool bytes_are_canonical_representation(std::span< const uint8_t, BYTES_448 > x)
Given 56 bytes, checks that the (little endian) number from this bytes is a valid GF element,...
bool is_odd() const
Return true iff this element is odd. Constant time.
Representation of a scalar for X448.
uint32_t get_window(size_t starting_pos, size_t width) const
Extract a window of width bits starting at bit position starting_pos. Bits beyond position 445 are tr...
static bool bytes_are_reduced(std::span< const uint8_t > x)
static std::unique_ptr< XOF > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Gf448Elem mul_a24(const Gf448Elem &a)
Multiply a field element by the Curve448 constant a24 = 39081.
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
BigInt operator*(const BigInt &x, const BigInt &y)
void ed448_validate_public_key_point(std::span< const uint8_t, ED448_LEN > pk)
std::array< uint8_t, ED448_LEN > create_pk_from_sk(std::span< const uint8_t, ED448_LEN > sk)
Create a public key point from a secret key (RFC 8032 5.2.5).
BigInt square(const BigInt &x)
constexpr size_t ED448_LEN
constexpr auto store_le(ParamTs &&... params)
constexpr auto concat(Rs &&... ranges)
bool verify_signature(std::span< const uint8_t, ED448_LEN > pk, bool phflag, std::span< const uint8_t > context, std::span< const uint8_t > sig, std::span< const uint8_t > msg)
Verify a signature(RFC 8032 5.2.7).
constexpr size_t WORDS_448
std::array< uint8_t, 2 *ED448_LEN > sign_message(std::span< const uint8_t, ED448_LEN > sk, std::span< const uint8_t, ED448_LEN > pk, bool pgflag, std::span< const uint8_t > context, std::span< const uint8_t > msg)
Sign a message using a keypair (RFC 8032 5.2.6).