Botan 3.9.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
15namespace Botan {
16
17namespace {
18
19/**
20 * @brief Reduce the result of a addition modulo 2^448 - 2^224 - 1.
21 *
22 * Algorithm 1 of paper "Reduction Modulo 2^448 - 2^224 - 1", from line 27.
23 *
24 * @param h_3 Output
25 * @param h_1 Input
26 */
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; /* NOLINT(*-member-init) */
29 uint64_t carry = 0;
30
31 constexpr uint64_t zero = 0;
32
33 // Line 27+ (of the paper's algorithm 1)
34 h_2[0] = word_add(h_1[0], h_1[7], &carry);
35 h_2[1] = word_add(h_1[1], zero, &carry);
36 h_2[2] = word_add(h_1[2], zero, &carry);
37
38 // Line 30
39 h_2[3] = word_add(h_1[3], h_1[7] << 32, &carry);
40
41 // Line 31+
42 h_2[4] = word_add(h_1[4], zero, &carry);
43 h_2[5] = word_add(h_1[5], zero, &carry);
44 h_2[6] = word_add(h_1[6], zero, &carry);
45
46 h_2[7] = carry;
47
48 carry = 0;
49 h_3[0] = word_add(h_2[0], h_2[7], &carry);
50 h_3[1] = word_add(h_2[1], zero, &carry);
51 h_3[2] = word_add(h_2[2], zero, &carry);
52 // Line 37
53 h_3[3] = h_2[3] + (h_2[7] << 32) + carry;
54
55 // Line 38
56 h_3[4] = h_2[4];
57 h_3[5] = h_2[5];
58 h_3[6] = h_2[6];
59}
60
61/**
62 * @brief Reduce the result of a addition modulo 2^448 - 2^224 - 1.
63 *
64 * Algorithm 1 of paper "Reduction Modulo 2^448 - 2^224 - 1".
65 */
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; // NOLINT(*-member-init)
68 std::array<uint64_t, 8> s; // NOLINT(*-member-init)
69 std::array<uint64_t, 8> t_0; // NOLINT(*-member-init)
70 std::array<uint64_t, 8> h_1; // NOLINT(*-member-init)
71
72 uint64_t carry = 0;
73
74 // Line 4 (of the paper's algorithm 1)
75 r[0] = word_add(in[0], in[7], &carry);
76
77 // Line 5-7
78 for(size_t i = 1; i < 7; ++i) {
79 r[i] = word_add(in[i], in[i + 7], &carry);
80 }
81 r[7] = carry;
82 s[0] = r[0];
83 s[1] = r[1];
84 s[2] = r[2];
85 // Line 10
86 carry = 0;
87 s[3] = word_add(r[3], in[10] & 0xFFFFFFFF00000000, &carry);
88 // Line 11-13
89 for(size_t i = 4; i < 7; ++i) {
90 s[i] = word_add(r[i], in[i + 7], &carry);
91 }
92 s[7] = r[7] + carry;
93
94 // Line 15-17
95 for(size_t i = 0; i < 3; ++i) {
96 t_0[i] = (in[i + 11] << 32) | (in[i + 10] >> 32);
97 }
98 // Line 18
99 t_0[3] = (in[7] << 32) | (in[13] >> 32);
100 // Line 19-21
101 for(size_t i = 4; i < 7; ++i) {
102 t_0[i] = (in[i + 4] << 32) | (in[i + 3] >> 32);
103 }
104 carry = 0;
105 // Line 23-25
106 for(size_t i = 0; i < 7; ++i) {
107 h_1[i] = word_add(s[i], t_0[i], &carry);
108 }
109 h_1[7] = s[7] + carry;
110
111 reduce_after_add(out, h_1);
112}
113
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; // NOLINT(*-member-init)
118 comba_mul<7>(ws.data(), a.data(), b.data());
119 reduce_after_mul(out, ws);
120}
121
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; // NOLINT(*-member-init)
124 comba_sqr<7>(ws.data(), a.data());
125 reduce_after_mul(out, ws);
126}
127
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; // NOLINT(*-member-init)
132
133 uint64_t carry = 0;
134 for(size_t i = 0; i < WORDS_448; ++i) {
135 ws[i] = word_add(a[i], b[i], &carry);
136 }
137 ws[WORDS_448] = carry;
138
139 reduce_after_add(out, ws);
140}
141
142/**
143 * @brief Subtract two elements in GF(P). out = a - b
144 *
145 * Algorithm 2 of paper: "Reduction Modulo 2^448 - 2^224 - 1"
146 */
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; // NOLINT(*-member-init)
151 std::array<uint64_t, WORDS_448> h_1; // NOLINT(*-member-init)
152
153 uint64_t borrow = 0;
154 for(size_t i = 0; i < WORDS_448; ++i) {
155 h_0[i] = word_sub(a[i], b[i], &borrow);
156 }
157 uint64_t delta = borrow;
158 uint64_t delta_p = delta << 32;
159 borrow = 0;
160
161 constexpr uint64_t zero = 0;
162
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);
170
171 delta = borrow;
172 delta_p = delta << 32;
173 borrow = 0;
174
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);
179 out[4] = h_1[4];
180 out[5] = h_1[5];
181 out[6] = h_1[6];
182}
183
184/**
185 * @brief Inversion in GF(P) using Fermat's little theorem:
186 * x^-1 = x^(P-2) mod P
187 */
188void gf_inv(std::span<uint64_t, WORDS_448> out, std::span<const uint64_t, WORDS_448> a) {
189 clear_mem(out);
190 out[0] = 1;
191 // Square and multiply
192 for(int16_t t = 448; t >= 0; --t) {
193 gf_square(out, out);
194 // (P-2) has zero bits at indices 1, 224, 448. All others are one.
195 if(t != 448 && t != 224 && t != 1) {
196 gf_mul(out, out, a);
197 }
198 }
199}
200
201/**
202 * @brief Convert a number to its canonical representation.
203 *
204 * I.e. if the number is greater than P, subtract P. The number cannot be >= 2P
205 * since 2*P > 2^(7*64).
206 */
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,
209 0xffffffffffffffff,
210 0xffffffffffffffff,
211 0xfffffffeffffffff,
212 0xffffffffffffffff,
213 0xffffffffffffffff,
214 0xffffffffffffffff};
215
216 std::array<uint64_t, WORDS_448> in_minus_p; // NOLINT(*-member-init)
217 uint64_t borrow = 0;
218 for(size_t i = 0; i < WORDS_448; ++i) {
219 in_minus_p[i] = word_sub(in[i], p[i], &borrow);
220 }
221 std::array<uint64_t, WORDS_448> out; // NOLINT(*-member-init)
222 CT::Mask<uint64_t>::expand(borrow).select_n(out.data(), in.data(), in_minus_p.data(), WORDS_448);
223 return out;
224}
225
226} // namespace
227
228Gf448Elem::Gf448Elem(std::span<const uint8_t, BYTES_448> x) /* NOLINT(*-member-init) */ {
229 load_le(m_x, x);
230}
231
232Gf448Elem::Gf448Elem(uint64_t least_sig_word) /* NOLINT(*-member-init) */ {
233 clear_mem(m_x);
234 m_x[0] = least_sig_word;
235}
236
237void Gf448Elem::to_bytes(std::span<uint8_t, BYTES_448> out) const {
238 store_le(out, to_canonical(m_x));
239}
240
241std::array<uint8_t, BYTES_448> Gf448Elem::to_bytes() const {
242 std::array<uint8_t, BYTES_448> bytes{};
243 to_bytes(bytes);
244 return bytes;
245}
246
247void Gf448Elem::ct_cond_swap(bool b, Gf448Elem& other) {
248 for(size_t i = 0; i < WORDS_448; ++i) {
249 CT::conditional_swap(b, m_x[i], other.m_x[i]);
250 }
251}
252
253void Gf448Elem::ct_cond_assign(bool b, const Gf448Elem& other) {
254 CT::conditional_assign_mem(static_cast<uint64_t>(b), m_x.data(), other.m_x.data(), WORDS_448);
255}
256
258 Gf448Elem res(0);
259 gf_add(res.m_x, m_x, other.m_x);
260 return res;
261}
262
264 Gf448Elem res(0);
265 gf_sub(res.m_x, m_x, other.m_x);
266 return res;
267}
268
270 Gf448Elem res(0);
271 gf_sub(res.m_x, res.m_x, m_x);
272 return res;
273}
274
276 Gf448Elem res(0);
277 gf_mul(res.m_x, m_x, other.m_x);
278 return res;
279}
280
282 Gf448Elem res(0);
283 gf_inv(res.m_x, other.m_x);
284 gf_mul(res.m_x, m_x, res.m_x);
285 return res;
286}
287
288bool Gf448Elem::operator==(const Gf448Elem& other) const {
289 const auto canonical_form_this = to_canonical(m_x);
290 const auto canonical_form_other = to_canonical(other.m_x);
291 return CT::is_equal(canonical_form_this.data(), canonical_form_other.data(), WORDS_448).as_bool();
292}
293
294bool Gf448Elem::is_zero() const {
295 const auto canonical_form = to_canonical(m_x);
296
297 return CT::all_zeros(canonical_form.data(), WORDS_448).as_bool();
298}
299
300bool Gf448Elem::is_odd() const {
301 const auto canonical_form = to_canonical(m_x);
302 return (canonical_form[0] & 1) == 1;
303}
304
305bool Gf448Elem::bytes_are_canonical_representation(std::span<const uint8_t, BYTES_448> x) {
306 const auto x_words = load_le<std::array<uint64_t, WORDS_448>>(x);
307 const auto x_words_canonical = to_canonical(x_words);
308 return CT::is_equal(x_words.data(), x_words_canonical.data(), WORDS_448).as_bool();
309}
310
312 Gf448Elem res(0);
313 gf_square(res.words(), elem.words());
314 return res;
315}
316
318 Gf448Elem res(1);
319
320 // (P-3)/4 is an 445 bit integer with one zero bits at 222. All others are one.
321 for(int16_t t = 445; t >= 0; --t) {
322 gf_square(res.words(), res.words());
323 if(t != 222) {
324 gf_mul(res.words(), res.words(), elem.words());
325 }
326 }
327
328 return res;
329}
330
331} // namespace Botan
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:420
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:796
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:826
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:813
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:777
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:280
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:191
constexpr void comba_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:735
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:699
BigInt square(const BigInt &x)
Definition numthry.cpp:157
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
void carry(int64_t &h0, int64_t &h1)
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:119
constexpr size_t WORDS_448
Definition curve448_gf.h:22