8#include <botan/internal/curve448_gf.h>
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/loadstor.h>
12#include <botan/internal/mp_asmi.h>
13#include <botan/internal/mp_core.h>
27void reduce_after_add(std::span<uint64_t, WORDS_448> h_3, std::span<const uint64_t, 8> h_1) {
28 std::array<uint64_t, 8> h_2;
31 constexpr uint64_t zero = 0;
53 h_3[3] = h_2[3] + (h_2[7] << 32) +
carry;
66void reduce_after_mul(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, 14> in) {
67 std::array<uint64_t, 8> r;
68 std::array<uint64_t, 8> s;
69 std::array<uint64_t, 8> t_0;
70 std::array<uint64_t, 8> h_1;
78 for(
size_t i = 1; i < 7; ++i) {
89 for(
size_t i = 4; i < 7; ++i) {
95 for(
size_t i = 0; i < 3; ++i) {
96 t_0[i] = (in[i + 11] << 32) | (in[i + 10] >> 32);
99 t_0[3] = (in[7] << 32) | (in[13] >> 32);
101 for(
size_t i = 4; i < 7; ++i) {
102 t_0[i] = (in[i + 4] << 32) | (in[i + 3] >> 32);
106 for(
size_t i = 0; i < 7; ++i) {
109 h_1[7] = s[7] +
carry;
111 reduce_after_add(out, h_1);
114void gf_mul(std::span<uint64_t, WORDS_448> out,
115 std::span<const uint64_t, WORDS_448> a,
116 std::span<const uint64_t, WORDS_448> b) {
117 std::array<uint64_t, 14> ws;
119 reduce_after_mul(out, ws);
122void gf_square(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {
123 std::array<uint64_t, 14> ws;
125 reduce_after_mul(out, ws);
128void gf_add(std::span<uint64_t, WORDS_448> out,
129 std::span<const uint64_t, WORDS_448> a,
130 std::span<const uint64_t, WORDS_448> b) {
131 std::array<uint64_t, WORDS_448 + 1> ws;
139 reduce_after_add(out, ws);
147void gf_sub(std::span<uint64_t, WORDS_448> out,
148 std::span<const uint64_t, WORDS_448> a,
149 std::span<const uint64_t, WORDS_448> b) {
150 std::array<uint64_t, WORDS_448> h_0;
151 std::array<uint64_t, WORDS_448> h_1;
155 h_0[i] =
word_sub(a[i], b[i], &borrow);
157 uint64_t delta = borrow;
158 uint64_t delta_p = delta << 32;
161 constexpr uint64_t zero = 0;
163 h_1[0] =
word_sub(h_0[0], delta, &borrow);
164 h_1[1] =
word_sub(h_0[1], zero, &borrow);
165 h_1[2] =
word_sub(h_0[2], zero, &borrow);
166 h_1[3] =
word_sub(h_0[3], delta_p, &borrow);
167 h_1[4] =
word_sub(h_0[4], zero, &borrow);
168 h_1[5] =
word_sub(h_0[5], zero, &borrow);
169 h_1[6] =
word_sub(h_0[6], zero, &borrow);
172 delta_p = delta << 32;
175 out[0] =
word_sub(h_1[0], delta, &borrow);
176 out[1] =
word_sub(h_1[1], zero, &borrow);
177 out[2] =
word_sub(h_1[2], zero, &borrow);
178 out[3] =
word_sub(h_1[3], delta_p, &borrow);
188void gf_inv(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {
192 for(int16_t t = 448; t >= 0; --t) {
195 if(t != 448 && t != 224 && t != 1) {
207std::array<uint64_t, WORDS_448> to_canonical(std::span<const uint64_t, WORDS_448> in) {
208 const std::array<uint64_t, WORDS_448> p = {0xffffffffffffffff,
216 std::array<uint64_t, WORDS_448> in_minus_p;
219 in_minus_p[i] =
word_sub(in[i], p[i], &borrow);
221 std::array<uint64_t, WORDS_448> out;
234 m_x[0] = least_sig_word;
242 std::array<uint8_t, BYTES_448> bytes{};
259 gf_add(res.m_x, m_x, other.m_x);
265 gf_sub(res.m_x, m_x, other.m_x);
271 gf_sub(res.m_x, res.m_x, m_x);
277 gf_mul(res.m_x, m_x, other.m_x);
283 gf_inv(res.m_x, other.m_x);
284 gf_mul(res.m_x, m_x, res.m_x);
289 const auto canonical_form_this = to_canonical(m_x);
290 const auto canonical_form_other = to_canonical(other.m_x);
295 const auto canonical_form = to_canonical(m_x);
301 const auto canonical_form = to_canonical(m_x);
302 return (canonical_form[0] & 1) == 1;
307 const auto x_words_canonical = to_canonical(x_words);
321 for(int16_t t = 445; t >= 0; --t) {
static constexpr Mask< T > expand(T v)
Gf448Elem operator*(const Gf448Elem &other) const
Gf448Elem operator-() const
void ct_cond_swap(bool b, Gf448Elem &other)
Swap this and other if b == true. Constant time for any b.
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,...
void ct_cond_assign(bool b, const Gf448Elem &other)
Set this to other if b is true. Constant time for any b.
std::array< uint8_t, BYTES_448 > to_bytes() const
Return the canonical representation of the GF element as 56 bytes in little-endian order.
Gf448Elem operator/(const Gf448Elem &other) const
bool is_odd() const
Return true iff this element is odd. Constant time.
Gf448Elem operator+(const Gf448Elem &other) const
bool operator==(const Gf448Elem &other) const
std::span< uint64_t, WORDS_448 > words()
Accessor to the internal words of the GF element.
Gf448Elem(std::span< const uint8_t, BYTES_448 > x)
Construct a GF element from a 448-bit integer gives as 56 bytes x in little-endian order.
bool is_zero() const
Return true iff this element is zero. Constant time.
constexpr void conditional_swap(bool cnd, T &x, T &y)
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
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)
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
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])
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
BigInt square(const BigInt &x)
constexpr auto store_le(ParamTs &&... params)
void carry(int64_t &h0, int64_t &h1)
constexpr auto load_le(ParamTs &&... params)
constexpr void clear_mem(T *ptr, size_t n)
constexpr size_t WORDS_448