Botan 3.14.1
Crypto and TLS for C&
bls12_381_fe.cpp
Go to the documentation of this file.
1/*
2* (C) 2024,2025,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/bls12_381_fields.h>
8
9#include <botan/internal/ct_utils.h>
10#include <botan/internal/mp_core.h>
11#include <algorithm>
12
13namespace Botan::BLS12_381 {
14
15namespace {
16
17constexpr auto FE_P = hex_to_words<word>(
18 "1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab");
19
20// R1 = 2**384 % p
21constexpr auto FE_R1 = hex_to_words<word>(
22 "15f65ec3fa80e4935c071a97a256ec6d77ce5853705257455f48985753c758baebf4000bc40c0002760900000002fffd");
23
24// R2 = (R1**2) % p
25constexpr auto FE_R2 = hex_to_words<word>(
26 "11988fe592cae3aa9a793e85b519952d67eb88a9939d83c08de5476c4c95b6d50a76e6a609d104f1f4df1f341c341746");
27
28// R3 = (R1*R2) % p
29constexpr auto FE_R3 = hex_to_words<word>(
30 "aa6346091755d4d2512d4356572472834c04e5e921e17619a53352a615e29dd315f831e03a7adf8ed48ac6bd94ca1e0");
31
32constexpr word FE_P_DASH = monty_inverse(FE_P[0]);
33
34// (p-1)/2, for the lexicographic comparison
35constexpr auto FE_P_HALF = [] {
36 auto x = FE_P;
38 return x;
39}();
40
41// (p+1)/4; since p == 3 (mod 4) this is (p >> 2) + 1, and the increment
42// cannot overflow
43constexpr auto FE_SQRT_EXP = [] {
44 auto x = FE_P;
46 x[0] += 1;
47 return x;
48}();
49
50std::array<word, FieldElement::N> fe_redc(const std::array<word, 2 * FieldElement::N>& v) {
51 std::array<word, FieldElement::N> r{};
52 std::array<word, FieldElement::N> ws{};
53 bigint_monty_redc(r.data(), v.data(), FE_P.data(), FE_P.size(), FE_P_DASH, ws.data(), ws.size());
54 return r;
55}
56
57std::array<word, FieldElement::N> fe_to_rep(std::array<word, FieldElement::N> v) {
58 std::array<word, 2 * FieldElement::N> z{};
59 comba_mul<FieldElement::N>(z.data(), v.data(), FE_R2.data());
60 return fe_redc(z);
61}
62
63/*
64The input may be as large as 2^768 - 1, which exceeds R*p, so the first
65reduction's output is not fully reduced; it is bounded by 2^384 and
66congruent to v/R. That in turn bounds the second reduction's input by
67R*p, which guarantees a fully reduced result.
68*/
69std::array<word, FieldElement::N> fe_wide_to_rep(const std::array<word, 2 * FieldElement::N>& v) {
70 auto redc_v = fe_redc(v);
71 std::array<word, 2 * FieldElement::N> z{};
72 comba_mul<FieldElement::N>(z.data(), redc_v.data(), FE_R3.data());
73 return fe_redc(z);
74}
75
76std::array<word, FieldElement::N> fe_from_rep(const std::array<word, FieldElement::N>& v) {
77 std::array<word, 2 * FieldElement::N> z{};
78 copy_mem(z.data(), v.data(), v.size());
79 return fe_redc(z);
80}
81
82} // namespace
83
84//static
85FieldElement FieldElement::from_words(std::array<word, FieldElement::N> v) {
86 return FieldElement(fe_to_rep(v));
87}
88
89//static
91 std::array<word, FieldElement::N> w{};
92 w[0] = v;
93 return FieldElement::from_words(w);
94}
95
96//static
100
101std::optional<FieldElement> FieldElement::deserialize(std::span<const uint8_t> bytes) {
102 if(bytes.size() != FieldElement::BYTES) {
103 return {};
104 }
105
106 const auto words = bytes_to_words<word, N, BYTES>(bytes.first<FieldElement::BYTES>());
107
108 if(!bigint_ct_is_lt(words.data(), N, FE_P.data(), N).as_bool()) {
109 return {};
110 }
111
112 return FieldElement::from_words(words);
113}
114
115FieldElement FieldElement::from_bytes_wide(std::span<const uint8_t, 96> bytes) {
116 return FieldElement(fe_wide_to_rep(bytes_to_words<word, 2 * N, 2 * BYTES>(bytes)));
117}
118
119void FieldElement::serialize_to(std::span<uint8_t, FieldElement::BYTES> bytes) const {
120 auto v = fe_from_rep(m_val);
121 std::reverse(v.begin(), v.end());
122 store_be(bytes, v);
123}
124
126 std::array<word, FieldElement::N> t{};
127 word carry = 0;
128 for(size_t i = 0; i != FieldElement::N; ++i) {
129 t[i] = word_add(m_val[i], other.m_val[i], &carry);
130 }
131
132 std::array<word, FieldElement::N> r{};
133 bigint_monty_maybe_sub<FieldElement::N>(r.data(), carry, t.data(), FE_P.data());
134 return FieldElement(r);
135}
136
138 std::array<word, FieldElement::N> r; // NOLINT(*-member-init)
139 word borrow = 0;
140 for(size_t i = 0; i != FieldElement::N; ++i) {
141 r[i] = word_sub(m_val[i], other.m_val[i], &borrow);
142 }
143
144 const word mask = CT::Mask<word>::expand(borrow).value();
145 word carry = 0;
146 for(size_t i = 0; i != FieldElement::N; ++i) {
147 r[i] = word_add(r[i], FE_P[i] & mask, &carry);
148 }
149
150 return FieldElement(r);
151}
152
154 std::array<word, 2 * FieldElement::N> z{};
155 comba_mul<FieldElement::N>(z.data(), data(), other.data());
156 return FieldElement(fe_redc(z));
157}
158
160 std::array<word, 2 * FieldElement::N> z{};
161 comba_sqr<FieldElement::N>(z.data(), data());
162 return FieldElement(fe_redc(z));
163}
164
165void FieldElement::square_n(size_t n) {
166 std::array<word, 2 * N> z{};
167 for(size_t i = 0; i != n; ++i) {
168 comba_sqr<N>(z.data(), this->data());
169 m_val = fe_redc(z);
170 }
171}
172
174 auto v_is_zero = CT::all_zeros(this->data(), N);
175
176 std::array<word, N> r{};
177 bigint_sub3(r.data(), FE_P.data(), N, this->data(), N);
178 v_is_zero.if_set_zero_out(r.data(), N);
179 return FieldElement(r);
180}
181
183 return CT::all_zeros(this->data(), N).as_choice();
184}
185
187 const auto v = fe_from_rep(m_val);
188 return !bigint_ct_is_lt(v.data(), N, FE_P_HALF.data(), N, true).as_choice();
189}
190
192 // The Montgomery representation of a reduced element is unique
193 return CT::is_equal(this->data(), other.data(), N).as_choice();
194}
195
197 CT::conditional_assign_mem(cnd, m_val.data(), other.m_val.data(), N);
198}
199
201 // Since p == 3 (mod 4) any square root must be x^((p+1)/4)
202 const auto r = pow_msb(*this, FE_SQRT_EXP);
203 return CT::Option<FieldElement>(r, r.square() == (*this));
204}
205
207 // Addition chain for exponentiation to p - 2
208 // Found using https://github.com/mmcloughlin/addchain
209 auto z = (*this).square();
210 auto t3 = z.square();
211 auto t10 = t3.square();
212 auto t6 = t10 * (*this);
213 auto t8 = t6 * z;
214 auto t5 = t8 * z;
215 auto t24 = t3 * t5;
216 auto t1 = t6 * t8;
217 auto t17 = t10 * t24;
218 auto t9 = t17 * (*this);
219 auto t12 = t9.square();
220 auto t4 = t12 * z;
221 auto t2 = t4 * (*this);
222 auto t22 = t12 * t17;
223 auto t14 = t22 * z;
224 auto t0 = t10 * t22;
225 auto t20 = t0 * t10;
226 auto t11 = t22 * t9;
227 auto t19 = t11 * z;
228 auto t16 = t20 * t9;
229 auto t7 = t16 * t3;
230 t12 *= t0;
231 t9 *= t7;
232 auto t15 = t9 * z;
233 z = t1 * t9;
234 auto t21 = t10 * z;
235 t4 *= t12;
236 t10 = t3 * t4;
237 t5 *= t10;
238 auto t18 = t1 * t10;
239 auto t13 = t24 * t5;
240 auto t23 = t13 * t3;
241 t3 = t1 * t18;
242 t5 = t1 * t13;
243 t1 *= t3;
244 auto t25 = t13 * t4;
245 t25.square_n(8);
246 t24 *= t25;
247 t24.square_n(11);
248 t24 *= t5;
249 t24.square_n(11);
250 t23 *= t24;
251 t23.square_n(8);
252 t23 *= t1;
253 t23.square_n(7);
254 t22 *= t23;
255 t22.square_n(9);
256 t22 *= t19;
257 t22.square_n(10);
258 t21 *= t22;
259 t21.square_n(7);
260 t20 *= t21;
261 t20.square_n(9);
262 t20 *= t7;
263 t20.square_n(6);
264 t20 *= t17;
265 t20.square_n(11);
266 t19 *= t20;
267 t19.square_n(9);
268 t19 *= t3;
269 t19.square_n(10);
270 t18 *= t19;
271 t18.square_n(6);
272 t17 *= t18;
273 t17.square_n(10);
274 t16 *= t17;
275 t16.square_n(9);
276 t15 *= t16;
277 t15.square_n(11);
278 t14 *= t15;
279 t14.square_n(10);
280 t13 *= t14;
281 t13.square_n(9);
282 t12 *= t13;
283 t12.square_n(9);
284 t12 *= t4;
285 t12.square_n(8);
286 t11 *= t12;
287 t11.square_n(10);
288 t10 *= t11;
289 t10.square_n(9);
290 t9 *= t10;
291 t9.square_n(12);
292 t9 *= t7;
293 t9.square_n(5);
294 t8 *= t9;
295 t8.square_n(11);
296 t7 *= t8;
297 t7.square_n(7);
298 t6 *= t7;
299 t6.square_n(13);
300 t5 *= t6;
301 t5.square_n(9);
302 t4 *= t5;
303 t4.square_n(8);
304 t4 *= t1;
305 t4.square_n(8);
306 t3 *= t4;
307 t3.square_n(11);
308 t3 *= z;
309 t3.square_n(8);
310 t3 *= t1;
311 t3.square_n(8);
312 t3 *= t1;
313 t3.square_n(6);
314 t2 *= t3;
315 t2.square_n(10);
316 t2 *= t1;
317 t2.square_n(9);
318 t2 *= t1;
319 t2.square_n(8);
320 t2 *= t1;
321 t2.square_n(8);
322 t2 *= t1;
323 t2.square_n(8);
324 t1 *= t2;
325 t1.square_n(7);
326 t0 *= t1;
327 t0.square_n(9);
328 z *= t0;
329 return z;
330}
331
332} // namespace Botan::BLS12_381
FieldElement add(const FieldElement &x) const
CT::Choice _is_lexicographically_largest() const
static FieldElement one()
static constexpr size_t BYTES
void conditional_assign(CT::Choice cnd, const FieldElement &other)
static std::optional< FieldElement > deserialize(std::span< const uint8_t > bytes)
CT::Choice operator==(const FieldElement &other) const
void serialize_to(std::span< uint8_t, FieldElement::BYTES > bytes) const
FieldElement mul(const FieldElement &x) const
FieldElement sub(const FieldElement &x) const
CT::Option< FieldElement > sqrt() const
static constexpr size_t N
static FieldElement from_bytes_wide(std::span< const uint8_t, 96 > bytes)
static FieldElement from_u32(uint32_t v)
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
FE pow_msb(const FE &x, const std::array< word, N > &exp)
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803
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 bytes_to_words(std::span< const uint8_t, L > bytes)
Definition mp_core.h:1255
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
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:866
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1086
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:510
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:921
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
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:904