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>
25inline uint64_t u64_add(uint64_t a, uint64_t b,
bool*
carry) {
27 const uint64_t sum = a + b;
36inline uint64_t u64_add_with_carry(uint64_t a, uint64_t b,
bool*
carry) {
39 const bool carry_a_plus_b = (sum < a);
40 sum +=
static_cast<uint64_t
>(*carry);
41 *
carry =
static_cast<uint64_t
>(carry_a_plus_b) |
static_cast<uint64_t
>(sum <
static_cast<uint64_t
>(*
carry));
50inline uint64_t u64_sub_with_borrow(uint64_t a, uint64_t b,
bool* borrow) {
52 const uint64_t diff = a - b;
53 const bool borrow_a_min_b = diff > a;
54 const uint64_t z = diff -
static_cast<uint64_t
>(*borrow);
55 *borrow =
static_cast<uint64_t
>(borrow_a_min_b) |
static_cast<uint64_t
>(z > diff);
67void reduce_after_add(std::span<uint64_t, WORDS_448> h_3, std::span<const uint64_t, 8> h_1) {
68 std::array<uint64_t, 8> h_2;
72 h_2[0] = u64_add(h_1[0], h_1[7], &
carry);
78 h_2[3] = u64_add_with_carry(h_1[3], h_1[7] << 32, &
carry);
87 h_3[0] = u64_add(h_2[0], h_2[7], &
carry);
91 h_3[3] = h_2[3] + (h_2[7] << 32) +
carry;
104void reduce_after_mul(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, 14> in) {
105 std::array<uint64_t, 8> r;
106 std::array<uint64_t, 8> s;
107 std::array<uint64_t, 8> t_0;
108 std::array<uint64_t, 8> h_1;
113 r[0] = u64_add(in[0], in[7], &
carry);
116 for(
size_t i = 1; i < 7; ++i) {
117 r[i] = u64_add_with_carry(in[i], in[i + 7], &
carry);
124 s[3] = u64_add(r[3], in[10] & 0xFFFFFFFF00000000, &
carry);
126 for(
size_t i = 4; i < 7; ++i) {
127 s[i] = u64_add_with_carry(r[i], in[i + 7], &
carry);
132 for(
size_t i = 0; i < 3; ++i) {
133 t_0[i] = (in[i + 11] << 32) | (in[i + 10] >> 32);
136 t_0[3] = (in[7] << 32) | (in[13] >> 32);
138 for(
size_t i = 4; i < 7; ++i) {
139 t_0[i] = (in[i + 4] << 32) | (in[i + 3] >> 32);
141 h_1[0] = u64_add(s[0], t_0[0], &
carry);
143 for(
size_t i = 1; i < 7; ++i) {
144 h_1[i] = u64_add_with_carry(s[i], t_0[i], &
carry);
146 h_1[7] = s[7] +
carry;
148 reduce_after_add(out, h_1);
151void gf_mul(std::span<uint64_t, WORDS_448> out,
152 std::span<const uint64_t, WORDS_448> a,
153 std::span<const uint64_t, WORDS_448> b) {
154 std::array<uint64_t, 14> ws;
156 reduce_after_mul(out, ws);
159void gf_square(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {
160 std::array<uint64_t, 14> ws;
162 reduce_after_mul(out, ws);
165void gf_add(std::span<uint64_t, WORDS_448> out,
166 std::span<const uint64_t, WORDS_448> a,
167 std::span<const uint64_t, WORDS_448> b) {
168 std::array<uint64_t, WORDS_448 + 1> ws;
169 copy_mem(std::span(ws).first<WORDS_448>(), a);
174 ws[i] = u64_add_with_carry(a[i], b[i], &
carry);
178 reduce_after_add(out, ws);
186void gf_sub(std::span<uint64_t, WORDS_448> out,
187 std::span<const uint64_t, WORDS_448> a,
188 std::span<const uint64_t, WORDS_448> b) {
189 std::array<uint64_t, WORDS_448> h_0;
190 std::array<uint64_t, WORDS_448> h_1;
194 h_0[i] = u64_sub_with_borrow(a[i], b[i], &borrow);
196 uint64_t delta = borrow;
197 uint64_t delta_p = delta << 32;
200 h_1[0] = u64_sub_with_borrow(h_0[0], delta, &borrow);
201 h_1[1] = u64_sub_with_borrow(h_0[1], 0, &borrow);
202 h_1[2] = u64_sub_with_borrow(h_0[2], 0, &borrow);
203 h_1[3] = u64_sub_with_borrow(h_0[3], delta_p, &borrow);
204 h_1[4] = u64_sub_with_borrow(h_0[4], 0, &borrow);
205 h_1[5] = u64_sub_with_borrow(h_0[5], 0, &borrow);
206 h_1[6] = u64_sub_with_borrow(h_0[6], 0, &borrow);
209 delta_p = delta << 32;
212 out[0] = u64_sub_with_borrow(h_1[0], delta, &borrow);
213 out[1] = u64_sub_with_borrow(h_1[1], 0, &borrow);
214 out[2] = u64_sub_with_borrow(h_1[2], 0, &borrow);
215 out[3] = u64_sub_with_borrow(h_1[3], delta_p, &borrow);
225void gf_inv(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {
229 for(int16_t t = 448; t >= 0; --t) {
232 if(t != 448 && t != 224 && t != 1) {
244std::array<uint64_t, WORDS_448> to_canonical(std::span<const uint64_t, WORDS_448> in) {
245 const std::array<uint64_t, WORDS_448> p = {0xffffffffffffffff,
253 std::array<uint64_t, WORDS_448> in_minus_p;
256 in_minus_p[i] = u64_sub_with_borrow(in[i], p[i], &borrow);
258 std::array<uint64_t, WORDS_448> out;
271 m_x[0] = least_sig_word;
279 std::array<uint8_t, BYTES_448> bytes;
296 gf_add(res.m_x, m_x, other.m_x);
302 gf_sub(res.m_x, m_x, other.m_x);
308 gf_sub(res.m_x, res.m_x, m_x);
314 gf_mul(res.m_x, m_x, other.m_x);
320 gf_inv(res.m_x, other.m_x);
321 gf_mul(res.m_x, m_x, res.m_x);
326 const auto canonical_form_this = to_canonical(m_x);
327 const auto canonical_form_other = to_canonical(other.m_x);
332 const auto canonical_form = to_canonical(m_x);
338 const auto canonical_form = to_canonical(m_x);
339 return (canonical_form[0] & 1) == 1;
344 const auto x_words_canonical = to_canonical(x_words);
358 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 Mask< T > conditional_assign_mem(T cnd, T *sink, const T *src, size_t elems)
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)
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
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 copy_mem(T *out, const T *in, size_t n)
constexpr void clear_mem(T *ptr, size_t n)
constexpr size_t WORDS_448