9#ifndef BOTAN_ED25519_FE_H_
10#define BOTAN_ED25519_FE_H_
12#include <botan/assert.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/loadstor.h>
15#include <botan/internal/mp_core.h>
29 p[p.size() - 1] >>= 1;
57 constexpr void fold_carry(W carry) {
58 for(
size_t fold = 0; fold != 2; ++fold) {
60 m_val[0] =
word_add(m_val[0], carry * 38, &c);
61 for(
size_t i = 1; i != N; ++i) {
62 m_val[i] =
word_add(m_val[i],
static_cast<W
>(0), &c);
71 constexpr void fold_borrow(W borrow) {
72 for(
size_t fold = 0; fold != 2; ++fold) {
74 m_val[0] =
word_sub(m_val[0], borrow * 38, &b);
75 for(
size_t i = 1; i != N; ++i) {
76 m_val[i] =
word_sub(m_val[i],
static_cast<W
>(0), &b);
88 constexpr void reduce_wide(
const std::array<W, 2 * N>& z) {
91 for(
size_t i = 0; i != N; ++i) {
92 m_val[i] =
word_madd3(z[i + N], W(38), z[i], &carry);
98 for(
size_t fold = 0; fold != 2; ++fold) {
99 const W top = (carry << 1) | (m_val[N - 1] >> TOP_BIT);
100 m_val[N - 1] &= TOP_MASK;
104 m_val[0] =
word_add(m_val[0],
static_cast<W
>(top * 19), &c);
105 for(
size_t i = 1; i != N; ++i) {
106 m_val[i] =
word_add(m_val[i],
static_cast<W
>(0), &c);
118 constexpr std::array<W, N> canonical()
const {
121 std::array<W, N> t = m_val;
123 const W top = t[N - 1] >> TOP_BIT;
124 t[N - 1] &= TOP_MASK;
126 t[0] =
word_add(t[0],
static_cast<W
>(top * 19), &c);
127 for(
size_t i = 1; i != N; ++i) {
128 t[i] =
word_add(t[i],
static_cast<W
>(0), &c);
131 std::array<W, N> r{};
133 for(
size_t i = 0; i != N; ++i) {
134 r[i] =
word_sub(t[i], P[i], &borrow);
167 static std::optional<Ed25519_FieldElement>
deserialize(
const uint8_t b[32]) {
169 for(
size_t i = 0; i != N; ++i) {
172 r.m_val[N - 1] &= TOP_MASK;
176 for(
size_t i = 0; i != N; ++i) {
177 (void)
word_sub(r.m_val[i], P[i], &borrow);
187 const auto w = canonical();
188 for(
size_t i = 0; i != N; ++i) {
189 store_le(w[i], b.data() +
sizeof(W) * i);
194 const auto w = canonical();
195 if(std::is_constant_evaluated()) {
196 for(
const auto x : w) {
210 constexpr bool is_negative()
const {
return (canonical()[0] & 1) == 1; }
215 for(
size_t i = 0; i != N; ++i) {
216 z.m_val[i] =
word_add(a.m_val[i], b.m_val[i], &carry);
225 for(
size_t i = 0; i != N; ++i) {
226 z.m_val[i] =
word_sub(a.m_val[i], b.m_val[i], &borrow);
228 z.fold_borrow(borrow);
236 for(
size_t i = 0; i != N; ++i) {
243 std::array<W, 2 * N> z;
251 std::array<W, 2 * N> z;
260 std::array<W, 2 * N> z;
261 for(
size_t i = 0; i != iter; ++i) {
270 const auto z =
sqr();
283 for(
size_t i = 0; i != N; ++i) {
284 m_val[i] =
choose(mask, other.m_val[i], m_val[i]);
293 for(
size_t i = 0; i != N; ++i) {
294 const W nx =
choose(mask, y.m_val[i], x.m_val[i]);
295 const W ny =
choose(mask, x.m_val[i], y.m_val[i]);
302 std::array<W, N> m_val;
322 auto t0 = this->
sqr();
323 auto t1 = t0.sqr_iter(2);
330 t2 = t1.sqr_iter(10);
332 auto t3 = t2.sqr_iter(20);
334 t2 = t2.sqr_iter(10);
336 t2 = t1.sqr_iter(50);
338 t3 = t2.sqr_iter(100);
340 t2 = t2.sqr_iter(50);
349 auto t0 = this->
sqr();
350 auto t1 = t0.sqr_iter(2);
357 t1 = t0.sqr_iter(10);
359 auto t2 = t1.sqr_iter(20);
361 t1 = t1.sqr_iter(10);
363 t1 = t0.sqr_iter(50);
365 t2 = t1.sqr_iter(100);
367 t1 = t1.sqr_iter(50);
#define BOTAN_DEBUG_ASSERT(expr)
constexpr T into_bitmask() const
constexpr void conditional_assign(CT::Choice cond, const Ed25519_FieldElement &other)
static constexpr Ed25519_FieldElement add(const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
static constexpr Ed25519_FieldElement from_word(word x)
constexpr Ed25519_FieldElement sqr2() const
static constexpr Ed25519_FieldElement sub(const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
static constexpr Ed25519_FieldElement negate(const Ed25519_FieldElement &a)
constexpr Ed25519_FieldElement sqr_iter(size_t iter) const
constexpr Ed25519_FieldElement pow_22523() const
static std::optional< Ed25519_FieldElement > deserialize(const uint8_t b[32])
constexpr Ed25519_FieldElement invert() const
static constexpr Ed25519_FieldElement mul(const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
constexpr Ed25519_FieldElement sqr() const
static constexpr void conditional_swap(CT::Choice cond, Ed25519_FieldElement &x, Ed25519_FieldElement &y)
constexpr bool is_zero() const
constexpr bool is_negative() const
void serialize_to(std::span< uint8_t, 32 > b) const
static constexpr Ed25519_FieldElement one()
constexpr Ed25519_FieldElement()
static constexpr Ed25519_FieldElement zero()
constexpr T value_barrier(T x)
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
constexpr auto word_sub(W x, W y, W *carry) -> W
constexpr auto word_add(W x, W y, W *carry) -> W
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])
OctetString operator+(const OctetString &k1, const OctetString &k2)
BigInt operator-(const BigInt &x, const BigInt &y)
constexpr auto store_le(ParamTs &&... params)
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
constexpr auto load_le(ParamTs &&... params)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
consteval std::array< word, 256/WordInfo< word >::bits > ed25519_fp_words()
constexpr auto word_madd3(W a, W b, W c, W *d) -> W