18#ifndef BOTAN_X25519_FE_H_
19#define BOTAN_X25519_FE_H_
21#include <botan/types.h>
22#include <botan/internal/ct_utils.h>
23#include <botan/internal/donna128.h>
24#include <botan/internal/loadstor.h>
36#if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
94 for(
size_t i = 0; i != 2; ++i) {
103 t0 += (t4 >> 51U) * 19;
120 t0 += (t4 >> 51U) * 19;
125 t0 += 0x8000000000000 - 19;
126 t1 += 0x8000000000000 - 1;
127 t2 += 0x8000000000000 - 1;
128 t3 += 0x8000000000000 - 1;
129 t4 += 0x8000000000000 - 1;
152 for(
size_t i = 0; i != 5; ++i) {
153 r.m_v[i] = a.m_v[i] + b.m_v[i];
163 constexpr uint64_t two54m152 = (
static_cast<uint64_t
>(1) << 54) - 152;
164 constexpr uint64_t two54m8 = (
static_cast<uint64_t
>(1) << 54) - 8;
167 r.m_v[0] = a.m_v[0] + two54m152 - b.m_v[0];
168 r.m_v[1] = a.m_v[1] + two54m8 - b.m_v[1];
169 r.m_v[2] = a.m_v[2] + two54m8 - b.m_v[2];
170 r.m_v[3] = a.m_v[3] + two54m8 - b.m_v[3];
171 r.m_v[4] = a.m_v[4] + two54m8 - b.m_v[4];
176 const uint64_t a0 = a.m_v[0];
177 const uint64_t a1 = a.m_v[1];
178 const uint64_t a2 = a.m_v[2];
179 const uint64_t a3 = a.m_v[3];
180 const uint64_t a4 = a.m_v[4];
182 const uint64_t b0 = b.m_v[0];
183 const uint64_t b1 = b.m_v[1];
184 const uint64_t b2 = b.m_v[2];
185 const uint64_t b3 = b.m_v[3];
186 const uint64_t b4 = b.m_v[4];
189 const uint64_t b1_19 = b1 * 19;
190 const uint64_t b2_19 = b2 * 19;
191 const uint64_t b3_19 = b3 * 19;
192 const uint64_t b4_19 = b4 * 19;
194 const uint128_t t0 = mul(a0, b0) + mul(a1, b4_19) + mul(a2, b3_19) + mul(a3, b2_19) + mul(a4, b1_19);
195 const uint128_t t1 = mul(a0, b1) + mul(a1, b0) + mul(a2, b4_19) + mul(a3, b3_19) + mul(a4, b2_19);
196 const uint128_t t2 = mul(a0, b2) + mul(a1, b1) + mul(a2, b0) + mul(a3, b4_19) + mul(a4, b3_19);
197 const uint128_t t3 = mul(a0, b3) + mul(a1, b2) + mul(a2, b1) + mul(a3, b0) + mul(a4, b4_19);
198 const uint128_t t4 = mul(a0, b4) + mul(a1, b3) + mul(a2, b2) + mul(a3, b1) + mul(a4, b0);
200 return carry(t0, t1, t2, t3, t4);
204 const uint64_t a0 = m_v[0];
205 const uint64_t a1 = m_v[1];
206 const uint64_t a2 = m_v[2];
207 const uint64_t a3 = m_v[3];
208 const uint64_t a4 = m_v[4];
210 const uint64_t a0_2 = a0 * 2;
211 const uint64_t a1_2 = a1 * 2;
212 const uint64_t a2_38 = a2 * 38;
213 const uint64_t a3_19 = a3 * 19;
214 const uint64_t a4_19 = a4 * 19;
215 const uint64_t a4_38 = a4_19 * 2;
217 const uint128_t t0 = mul(a0, a0) + mul(a1, a4_38) + mul(a3, a2_38);
218 const uint128_t t1 = mul(a0_2, a1) + mul(a2, a4_38) + mul(a3, a3_19);
219 const uint128_t t2 = mul(a0_2, a2) + mul(a1, a1) + mul(a3, a4_38);
220 const uint128_t t3 = mul(a0_2, a3) + mul(a1_2, a2) + mul(a4, a4_19);
221 const uint128_t t4 = mul(a0_2, a4) + mul(a1_2, a3) + mul(a2, a2);
223 return carry(t0, t1, t2, t3, t4);
228 for(
size_t i = 0; i != n; ++i) {
238 constexpr uint64_t a24 = 121665;
243 r.m_v[0] = t & MASK_51;
246 r.m_v[1] = t & MASK_51;
249 r.m_v[2] = t & MASK_51;
252 r.m_v[3] = t & MASK_51;
255 r.m_v[4] = t & MASK_51;
269 const auto& z = *
this;
299 for(
size_t i = 0; i != 5; ++i) {
307 static constexpr uint64_t MASK_51 = (
static_cast<uint64_t
>(1) << 51) - 1;
318 r.m_v[0] = t0 & MASK_51;
320 r.m_v[1] = t1 & MASK_51;
322 r.m_v[2] = t2 & MASK_51;
324 r.m_v[3] = t3 & MASK_51;
326 r.m_v[4] = t4 & MASK_51;
330 r.m_v[1] += r.m_v[0] >> 51;
336 std::array<uint64_t, 5> m_v;
346 std::span<const uint8_t, 32> k,
347 std::span<const uint8_t, 32> u) {
358 for(
size_t t = 255; t-- > 0;) {
365 const auto A = x2 + z2;
366 const auto B = x2 - z2;
367 const auto C = x3 + z3;
368 const auto D = x3 - z3;
369 const auto AA = A.sqr();
370 const auto BB = B.sqr();
371 const auto E = AA - BB;
372 const auto DA = D * A;
373 const auto CB = C * B;
375 x3 = (DA + CB).sqr();
376 z3 = x1 * (DA - CB).sqr();
378 z2 = E * (AA + E.mul_a24());
384 const auto result = x2 * z2.invert();
static constexpr Mask< T > expand_bit(T v, size_t bit)
constexpr T if_set_return(T x) const
static constexpr Mask< T > cleared()
BOTAN_FORCE_INLINE friend X25519_FE operator-(const X25519_FE &a, const X25519_FE &b)
static constexpr X25519_FE one()
constexpr X25519_FE()
The zero element.
BOTAN_FORCE_INLINE void encode(std::span< uint8_t, 32 > out) const
static BOTAN_FORCE_INLINE void conditional_swap(CT::Mask< uint64_t > swap, X25519_FE &a, X25519_FE &b)
BOTAN_FORCE_INLINE X25519_FE invert() const
BOTAN_FORCE_INLINE friend X25519_FE operator*(const X25519_FE &a, const X25519_FE &b)
BOTAN_FORCE_INLINE X25519_FE sqr_n(size_t n) const
BOTAN_FORCE_INLINE X25519_FE sqr() const
BOTAN_FORCE_INLINE friend X25519_FE operator+(const X25519_FE &a, const X25519_FE &b)
static BOTAN_FORCE_INLINE X25519_FE decode(std::span< const uint8_t, 32 > in)
BOTAN_FORCE_INLINE X25519_FE mul_a24() const
#define BOTAN_FORCE_INLINE
constexpr uint64_t carry_shift(const donna128 &a, size_t shift)
constexpr auto store_le(ParamTs &&... params)
constexpr auto load_le(ParamTs &&... params)
BOTAN_FORCE_INLINE void x25519_ladder(std::span< uint8_t, 32 > out, std::span< const uint8_t, 32 > k, std::span< const uint8_t, 32 > u)
constexpr uint64_t combine_lower(const donna128 &a, size_t s1, const donna128 &b, size_t s2)