Botan 3.5.0
Crypto and TLS for C&
curve448_gf.cpp
Go to the documentation of this file.
1/*
2* X448 Gf Modulo 2^448 - 2^224 - 1
3* (C) 2024 Jack Lloyd
4* 2024 Fabian Albert - Rohde & Schwarz Cybersecurity
5*
6* Botan is released under the Simplified BSD License (see license.txt)
7*/
8#include <botan/internal/curve448_gf.h>
9
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>
14
15#include <algorithm>
16
17namespace Botan {
18
19namespace {
20
21/**
22 * @brief Compute (a + b). The carry is returned in the carry parameter.
23 * The carry is not included for the addition.
24 */
25inline uint64_t u64_add(uint64_t a, uint64_t b, bool* carry) {
26 // Let the compiler optimize this into fancy instructions
27 const uint64_t sum = a + b;
28 *carry = sum < a;
29 return sum;
30}
31
32/**
33 * @brief Compute (a + b + carry), where carry is in {0, 1}. The carry of this computation
34 * is store in the in/out @p carry parameter.
35 */
36inline uint64_t u64_add_with_carry(uint64_t a, uint64_t b, bool* carry) {
37 // Let the compiler optimize this into fancy instructions
38 uint64_t sum = a + b;
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));
42 return sum;
43}
44
45/**
46 * @brief Compute (a - (b + borrow)). The borrow is returned in the carry parameter.
47 *
48 * I.e. borrow = 1 if a < b + borrow, else 0.
49 */
50inline uint64_t u64_sub_with_borrow(uint64_t a, uint64_t b, bool* borrow) {
51 // Let the compiler optimize this into fancy instructions
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);
56 return z;
57}
58
59/**
60 * @brief Reduce the result of a addition modulo 2^448 - 2^224 - 1.
61 *
62 * Algorithm 1 of paper "Reduction Modulo 2^448 - 2^224 - 1", from line 27.
63 *
64 * @param h_3 Output
65 * @param h_1 Input
66 */
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;
69 bool carry;
70
71 // Line 27+ (of the paper's algorithm 1)
72 h_2[0] = u64_add(h_1[0], h_1[7], &carry);
73
74 h_2[1] = u64_add(h_1[1], carry, &carry);
75 h_2[2] = u64_add(h_1[2], carry, &carry);
76
77 // Line 30
78 h_2[3] = u64_add_with_carry(h_1[3], h_1[7] << 32, &carry);
79
80 // Line 31+
81 h_2[4] = u64_add(h_1[4], carry, &carry);
82 h_2[5] = u64_add(h_1[5], carry, &carry);
83 h_2[6] = u64_add(h_1[6], carry, &carry);
84
85 h_2[7] = carry;
86
87 h_3[0] = u64_add(h_2[0], h_2[7], &carry);
88 h_3[1] = u64_add(h_2[1], carry, &carry);
89 h_3[2] = u64_add(h_2[2], carry, &carry);
90 // Line 37
91 h_3[3] = h_2[3] + (h_2[7] << 32) + carry;
92
93 // Line 38
94 h_3[4] = h_2[4];
95 h_3[5] = h_2[5];
96 h_3[6] = h_2[6];
97}
98
99/**
100 * @brief Reduce the result of a addition modulo 2^448 - 2^224 - 1.
101 *
102 * Algorithm 1 of paper "Reduction Modulo 2^448 - 2^224 - 1".
103 */
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;
109
110 bool carry;
111
112 // Line 4 (of the paper's algorithm 1)
113 r[0] = u64_add(in[0], in[7], &carry);
114
115 // Line 5-7
116 for(size_t i = 1; i < 7; ++i) {
117 r[i] = u64_add_with_carry(in[i], in[i + 7], &carry);
118 }
119 r[7] = carry;
120 s[0] = r[0];
121 s[1] = r[1];
122 s[2] = r[2];
123 // Line 10
124 s[3] = u64_add(r[3], in[10] & 0xFFFFFFFF00000000, &carry);
125 // Line 11-13
126 for(size_t i = 4; i < 7; ++i) {
127 s[i] = u64_add_with_carry(r[i], in[i + 7], &carry);
128 }
129 s[7] = r[7] + carry;
130
131 // Line 15-17
132 for(size_t i = 0; i < 3; ++i) {
133 t_0[i] = (in[i + 11] << 32) | (in[i + 10] >> 32);
134 }
135 // Line 18
136 t_0[3] = (in[7] << 32) | (in[13] >> 32);
137 // Line 19-21
138 for(size_t i = 4; i < 7; ++i) {
139 t_0[i] = (in[i + 4] << 32) | (in[i + 3] >> 32);
140 }
141 h_1[0] = u64_add(s[0], t_0[0], &carry);
142 // Line 23-25
143 for(size_t i = 1; i < 7; ++i) {
144 h_1[i] = u64_add_with_carry(s[i], t_0[i], &carry);
145 }
146 h_1[7] = s[7] + carry;
147
148 reduce_after_add(out, h_1);
149}
150
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;
155 comba_mul<7>(ws.data(), a.data(), b.data());
156 reduce_after_mul(out, ws);
157}
158
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;
161 comba_sqr<7>(ws.data(), a.data());
162 reduce_after_mul(out, ws);
163}
164
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);
170 ws[WORDS_448] = 0;
171
172 bool carry = false;
173 for(size_t i = 0; i < WORDS_448; ++i) {
174 ws[i] = u64_add_with_carry(a[i], b[i], &carry);
175 }
176 ws[WORDS_448] = carry;
177
178 reduce_after_add(out, ws);
179}
180
181/**
182 * @brief Subtract two elements in GF(P). out = a - b
183 *
184 * Algorithm 2 of paper: "Reduction Modulo 2^448 - 2^224 - 1"
185 */
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;
191
192 bool borrow = false;
193 for(size_t i = 0; i < WORDS_448; ++i) {
194 h_0[i] = u64_sub_with_borrow(a[i], b[i], &borrow);
195 }
196 uint64_t delta = borrow;
197 uint64_t delta_p = delta << 32;
198 borrow = false;
199
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);
207
208 delta = borrow;
209 delta_p = delta << 32;
210 borrow = false;
211
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);
216 out[4] = h_1[4];
217 out[5] = h_1[5];
218 out[6] = h_1[6];
219}
220
221/**
222 * @brief Inversion in GF(P) using Fermat's little theorem:
223 * x^-1 = x^(P-2) mod P
224 */
225void gf_inv(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {
226 clear_mem(out);
227 out[0] = 1;
228 // Square and multiply
229 for(int16_t t = 448; t >= 0; --t) {
230 gf_square(out, out);
231 // (P-2) has zero bits at indices 1, 224, 448. All others are one.
232 if(t != 448 && t != 224 && t != 1) {
233 gf_mul(out, out, a);
234 }
235 }
236}
237
238/**
239 * @brief Convert a number to its canonical representation.
240 *
241 * I.e. if the number is greater than P, subtract P. The number cannot be >= 2P
242 * since 2*P > 2^(7*64).
243 */
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,
246 0xffffffffffffffff,
247 0xffffffffffffffff,
248 0xfffffffeffffffff,
249 0xffffffffffffffff,
250 0xffffffffffffffff,
251 0xffffffffffffffff};
252
253 std::array<uint64_t, WORDS_448> in_minus_p;
254 bool borrow = false;
255 for(size_t i = 0; i < WORDS_448; ++i) {
256 in_minus_p[i] = u64_sub_with_borrow(in[i], p[i], &borrow);
257 }
258 std::array<uint64_t, WORDS_448> out;
259 CT::Mask<uint64_t>::expand(borrow).select_n(out.data(), in.data(), in_minus_p.data(), WORDS_448);
260 return out;
261}
262
263} // namespace
264
265Gf448Elem::Gf448Elem(std::span<const uint8_t, BYTES_448> x) {
266 load_le(m_x, x);
267}
268
269Gf448Elem::Gf448Elem(uint64_t least_sig_word) {
270 clear_mem(m_x);
271 m_x[0] = least_sig_word;
272}
273
274void Gf448Elem::to_bytes(std::span<uint8_t, BYTES_448> out) const {
275 store_le(out, to_canonical(m_x));
276}
277
278std::array<uint8_t, BYTES_448> Gf448Elem::to_bytes() const {
279 std::array<uint8_t, BYTES_448> bytes;
280 to_bytes(bytes);
281 return bytes;
282}
283
284void Gf448Elem::ct_cond_swap(bool b, Gf448Elem& other) {
285 for(size_t i = 0; i < WORDS_448; ++i) {
286 CT::conditional_swap(b, m_x[i], other.m_x[i]);
287 }
288}
289
290void Gf448Elem::ct_cond_assign(bool b, const Gf448Elem& other) {
291 CT::conditional_assign_mem(static_cast<uint64_t>(b), m_x.data(), other.m_x.data(), WORDS_448);
292}
293
295 Gf448Elem res(0);
296 gf_add(res.m_x, m_x, other.m_x);
297 return res;
298}
299
301 Gf448Elem res(0);
302 gf_sub(res.m_x, m_x, other.m_x);
303 return res;
304}
305
307 Gf448Elem res(0);
308 gf_sub(res.m_x, res.m_x, m_x);
309 return res;
310}
311
313 Gf448Elem res(0);
314 gf_mul(res.m_x, m_x, other.m_x);
315 return res;
316}
317
319 Gf448Elem res(0);
320 gf_inv(res.m_x, other.m_x);
321 gf_mul(res.m_x, m_x, res.m_x);
322 return res;
323}
324
325bool Gf448Elem::operator==(const Gf448Elem& other) const {
326 const auto canonical_form_this = to_canonical(m_x);
327 const auto canonical_form_other = to_canonical(other.m_x);
328 return CT::is_equal(canonical_form_this.data(), canonical_form_other.data(), WORDS_448).as_bool();
329}
330
331bool Gf448Elem::is_zero() const {
332 const auto canonical_form = to_canonical(m_x);
333
334 return CT::all_zeros(canonical_form.data(), WORDS_448).as_bool();
335}
336
337bool Gf448Elem::is_odd() const {
338 const auto canonical_form = to_canonical(m_x);
339 return (canonical_form[0] & 1) == 1;
340}
341
342bool Gf448Elem::bytes_are_canonical_representation(std::span<const uint8_t, BYTES_448> x) {
343 const auto x_words = load_le<std::array<uint64_t, WORDS_448>>(x);
344 const auto x_words_canonical = to_canonical(x_words);
345 return CT::is_equal(x_words.data(), x_words_canonical.data(), WORDS_448).as_bool();
346}
347
349 Gf448Elem res(0);
350 gf_square(res.words(), elem.words());
351 return res;
352}
353
355 Gf448Elem res(1);
356
357 // (P-3)/4 is an 445 bit integer with one zero bits at 222. All others are one.
358 for(int16_t t = 445; t >= 0; --t) {
359 gf_square(res.words(), res.words());
360 if(t != 222) {
361 gf_mul(res.words(), res.words(), elem.words());
362 }
363 }
364
365 return res;
366}
367
368} // namespace Botan
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:213
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)
Definition ct_utils.h:452
constexpr Mask< T > conditional_assign_mem(T cnd, T *sink, const T *src, size_t elems)
Definition ct_utils.h:438
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:486
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:473
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])
Definition mp_core.h:984
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:948
BigInt square(const BigInt &x)
Definition numthry.cpp:157
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:698
void carry(int64_t &h0, int64_t &h1)
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:458
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:120
constexpr size_t WORDS_448
Definition curve448_gf.h:22