Botan 3.14.1
Crypto and TLS for C&
ed25519_fe.h
Go to the documentation of this file.
1/*
2* Ed25519 field element
3* (C) 2017 Ribose Inc
4* 2025,2026 Jack Lloyd
5*
6* Botan is released under the Simplified BSD License (see license.txt)
7*/
8
9#ifndef BOTAN_ED25519_FE_H_
10#define BOTAN_ED25519_FE_H_
11
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>
16#include <array>
17#include <optional>
18#include <span>
19
20namespace Botan {
21
22consteval std::array<word, 256 / WordInfo<word>::bits> ed25519_fp_words() {
23 // 2^255 - 19
24 std::array<word, 256 / WordInfo<word>::bits> p{};
25 for(auto& w : p) {
27 }
28 p[0] -= 18;
29 p[p.size() - 1] >>= 1;
30 return p;
31}
32
33/**
34* An element of the field Z/(2^255-19)
35*
36* The value is stored as saturated words. Aside from a value being reduced
37* below 2^256 (rather than below p), there are no per-word bounds to track:
38* additions and subtractions fold their carry or borrow back in immediately
39* using 2^256 == 38 (mod p), and multiplications reduce below 2^255 using
40* the same identity. Only serialization produces the canonical value.
41*/
43 private:
44 typedef word W;
45
46 static constexpr size_t N = 256 / WordInfo<W>::bits;
47 static constexpr size_t TOP_BIT = WordInfo<W>::bits - 1;
48 static constexpr W TOP_MASK = WordInfo<W>::max >> 1;
49
50 static constexpr std::array<W, N> P = ed25519_fp_words();
51
52 /*
53 * Fold a carry out of an addition back in using 2^256 == 38 (mod p).
54 * The first fold can itself carry (only if the value was at least
55 * 2^256 - 38); the second cannot.
56 */
57 constexpr void fold_carry(W carry) {
58 for(size_t fold = 0; fold != 2; ++fold) {
59 W c = 0;
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);
63 }
64 carry = c;
65 }
66 }
67
68 /*
69 * Fold a borrow out of a subtraction back in; as above but subtracting
70 */
71 constexpr void fold_borrow(W borrow) {
72 for(size_t fold = 0; fold != 2; ++fold) {
73 W b = 0;
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);
77 }
78 borrow = b;
79 }
80 }
81
82 /*
83 * Reduce a full product below 2^255 using 2^256 == 38 and 2^255 == 19
84 * (mod p). Follows the same approach as redc_crandall (mp_core.h) with
85 * an extra folding step since the prime is one bit short of a word
86 * multiple.
87 */
88 constexpr void reduce_wide(const std::array<W, 2 * N>& z) {
89 // t = lo + 38 * hi < 39 * 2^256, so carry <= 38
90 W carry = 0;
91 for(size_t i = 0; i != N; ++i) {
92 m_val[i] = word_madd3(z[i + N], W(38), z[i], &carry);
93 }
94 BOTAN_DEBUG_ASSERT(carry <= 38);
95
96 // Fold the bits at and above 2^255 back in by 19. The first fold
97 // leaves at most 19*77 above 2^255, the second leaves none.
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;
101 carry = 0;
102
103 W c = 0;
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);
107 }
108 // The top word was masked below 2^(bits-1) so this cannot carry out
109 BOTAN_DEBUG_ASSERT(c == 0);
110 }
111
112 BOTAN_DEBUG_ASSERT((m_val[N - 1] >> TOP_BIT) == 0);
113 }
114
115 /*
116 * Return the canonical value in [0,p)
117 */
118 constexpr std::array<W, N> canonical() const {
119 // Fold the bit at 2^255, leaving a value below 2^255 + 19, then
120 // conditionally subtract p once
121 std::array<W, N> t = m_val;
122
123 const W top = t[N - 1] >> TOP_BIT;
124 t[N - 1] &= TOP_MASK;
125 W c = 0;
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);
129 }
130
131 std::array<W, N> r{};
132 W borrow = 0;
133 for(size_t i = 0; i != N; ++i) {
134 r[i] = word_sub(t[i], P[i], &borrow);
135 }
136 CT::conditional_assign_mem(borrow, r.data(), t.data(), N);
137 return r;
138 }
139
140 public:
141 /**
142 * Default zero initialization
143 */
144 constexpr Ed25519_FieldElement() : m_val{} {}
145
146 constexpr static Ed25519_FieldElement zero() { return Ed25519_FieldElement(); }
147
148 constexpr static Ed25519_FieldElement one() {
150 o.m_val[0] = 1;
151 return o;
152 }
153
154 constexpr static Ed25519_FieldElement from_word(word x) {
156 r.m_val[0] = x;
157 return r;
158 }
159
160 /**
161 * Deserialize 32 little endian bytes, ignoring the high bit
162 *
163 * RFC 8032 5.1.3 requires that the encoded value (with the sign bit
164 * cleared) is already less than p; a value in [p, 2^255) is rejected
165 * rather than reduced.
166 */
167 static std::optional<Ed25519_FieldElement> deserialize(const uint8_t b[32]) {
169 for(size_t i = 0; i != N; ++i) {
170 r.m_val[i] = load_le<W>(b, i);
171 }
172 r.m_val[N - 1] &= TOP_MASK;
173
174 // Reject unless the value is already reduced, ie subtracting p borrows
175 W borrow = 0;
176 for(size_t i = 0; i != N; ++i) {
177 (void)word_sub(r.m_val[i], P[i], &borrow);
178 }
179 if(borrow == 0) {
180 return std::nullopt;
181 }
182
183 return r;
184 }
185
186 void serialize_to(std::span<uint8_t, 32> b) const {
187 const auto w = canonical();
188 for(size_t i = 0; i != N; ++i) {
189 store_le(w[i], b.data() + sizeof(W) * i);
190 }
191 }
192
193 constexpr bool is_zero() const {
194 const auto w = canonical();
195 if(std::is_constant_evaluated()) {
196 for(const auto x : w) {
197 if(x != 0) {
198 return false;
199 }
200 }
201 return true;
202 }
203 return CT::all_zeros(w.data(), w.size()).as_bool();
204 }
205
206 /*
207 return true if f is in {1,3,5,...,q-2}
208 return false if f is in {0,2,4,...,q-1}
209 */
210 constexpr bool is_negative() const { return (canonical()[0] & 1) == 1; }
211
214 W carry = 0;
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);
217 }
218 z.fold_carry(carry);
219 return z;
220 }
221
224 W borrow = 0;
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);
227 }
228 z.fold_borrow(borrow);
229 return z;
230 }
231
233 // Hide the zero, since subtracting from a constant zero GCC 14 at -O1
234 // emits a branch on the borrow
236 for(size_t i = 0; i != N; ++i) {
237 z.m_val[i] = CT::value_barrier<W>(0);
238 }
239 return sub(z, a);
240 }
241
243 std::array<W, 2 * N> z; // NOLINT(*-member-init)
244 comba_mul<N>(z.data(), a.m_val.data(), b.m_val.data());
246 r.reduce_wide(z);
247 return r;
248 }
249
250 constexpr Ed25519_FieldElement sqr() const {
251 std::array<W, 2 * N> z; // NOLINT(*-member-init)
252 comba_sqr<N>(z.data(), m_val.data());
254 r.reduce_wide(z);
255 return r;
256 }
257
258 constexpr Ed25519_FieldElement sqr_iter(size_t iter) const {
259 auto r = *this;
260 std::array<W, 2 * N> z; // NOLINT(*-member-init)
261 for(size_t i = 0; i != iter; ++i) {
262 comba_sqr<N>(z.data(), r.m_val.data());
263 r.reduce_wide(z);
264 }
265 return r;
266 }
267
268 // Return 2*a^2
269 constexpr Ed25519_FieldElement sqr2() const {
270 const auto z = sqr();
271 return add(z, z);
272 }
273
274 constexpr Ed25519_FieldElement invert() const;
275
276 constexpr Ed25519_FieldElement pow_22523() const;
277
278 /**
279 * If cond is set, assign other to this
280 */
281 constexpr void conditional_assign(CT::Choice cond, const Ed25519_FieldElement& other) {
282 const W mask = cond.into_bitmask<W>();
283 for(size_t i = 0; i != N; ++i) {
284 m_val[i] = choose(mask, other.m_val[i], m_val[i]);
285 }
286 }
287
288 /**
289 * If cond is set, swap x and y
290 */
292 const W mask = cond.into_bitmask<W>();
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]);
296 x.m_val[i] = nx;
297 y.m_val[i] = ny;
298 }
299 }
300
301 private:
302 std::array<W, N> m_val;
303};
304
306 return Ed25519_FieldElement::add(x, y);
307}
308
310 return Ed25519_FieldElement::sub(x, y);
311}
312
314 return Ed25519_FieldElement::mul(x, y);
315}
316
320
322 auto t0 = this->sqr();
323 auto t1 = t0.sqr_iter(2);
324 t1 = *this * t1;
325 t0 = t0 * t1;
326 auto t2 = t0.sqr();
327 t1 = t1 * t2;
328 t2 = t1.sqr_iter(5);
329 t1 = t2 * t1;
330 t2 = t1.sqr_iter(10);
331 t2 = t2 * t1;
332 auto t3 = t2.sqr_iter(20);
333 t2 = t3 * t2;
334 t2 = t2.sqr_iter(10);
335 t1 = t2 * t1;
336 t2 = t1.sqr_iter(50);
337 t2 = t2 * t1;
338 t3 = t2.sqr_iter(100);
339 t2 = t3 * t2;
340 t2 = t2.sqr_iter(50);
341 t1 = t2 * t1;
342 t1 = t1.sqr_iter(5);
343
344 t0 = t1 * t0;
345 return t0;
346}
347
349 auto t0 = this->sqr();
350 auto t1 = t0.sqr_iter(2);
351 t1 = (*this) * t1;
352 t0 = t0 * t1;
353 t0 = t0.sqr();
354 t0 = t1 * t0;
355 t1 = t0.sqr_iter(5);
356 t0 = t1 * t0;
357 t1 = t0.sqr_iter(10);
358 t1 = t1 * t0;
359 auto t2 = t1.sqr_iter(20);
360 t1 = t2 * t1;
361 t1 = t1.sqr_iter(10);
362 t0 = t1 * t0;
363 t1 = t0.sqr_iter(50);
364 t1 = t1 * t0;
365 t2 = t1.sqr_iter(100);
366 t1 = t2 * t1;
367 t1 = t1.sqr_iter(50);
368 t0 = t1 * t0;
369 t0 = t0.sqr_iter(2);
370
371 t0 = t0 * (*this);
372 return t0;
373}
374
375} // namespace Botan
376
377#endif
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
constexpr T into_bitmask() const
Definition ct_utils.h:291
constexpr void conditional_assign(CT::Choice cond, const Ed25519_FieldElement &other)
Definition ed25519_fe.h:281
static constexpr Ed25519_FieldElement add(const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
Definition ed25519_fe.h:212
static constexpr Ed25519_FieldElement from_word(word x)
Definition ed25519_fe.h:154
constexpr Ed25519_FieldElement sqr2() const
Definition ed25519_fe.h:269
static constexpr Ed25519_FieldElement sub(const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
Definition ed25519_fe.h:222
static constexpr Ed25519_FieldElement negate(const Ed25519_FieldElement &a)
Definition ed25519_fe.h:232
constexpr Ed25519_FieldElement sqr_iter(size_t iter) const
Definition ed25519_fe.h:258
constexpr Ed25519_FieldElement pow_22523() const
Definition ed25519_fe.h:348
static std::optional< Ed25519_FieldElement > deserialize(const uint8_t b[32])
Definition ed25519_fe.h:167
constexpr Ed25519_FieldElement invert() const
Definition ed25519_fe.h:321
static constexpr Ed25519_FieldElement mul(const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
Definition ed25519_fe.h:242
constexpr Ed25519_FieldElement sqr() const
Definition ed25519_fe.h:250
static constexpr void conditional_swap(CT::Choice cond, Ed25519_FieldElement &x, Ed25519_FieldElement &y)
Definition ed25519_fe.h:291
constexpr bool is_zero() const
Definition ed25519_fe.h:193
constexpr bool is_negative() const
Definition ed25519_fe.h:210
void serialize_to(std::span< uint8_t, 32 > b) const
Definition ed25519_fe.h:186
static constexpr Ed25519_FieldElement one()
Definition ed25519_fe.h:148
static constexpr Ed25519_FieldElement zero()
Definition ed25519_fe.h:146
constexpr T value_barrier(T x)
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
constexpr void comba_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:1017
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:57
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:1216
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:217
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
consteval std::array< word, 256/WordInfo< word >::bits > ed25519_fp_words()
Definition ed25519_fe.h:22
constexpr auto word_madd3(W a, W b, W c, W *d) -> W
Definition mp_asmi.h:158