Botan 3.14.1
Crypto and TLS for C&
bls12_381_fp2.cpp
Go to the documentation of this file.
1/*
2* (C) 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
12namespace Botan::BLS12_381 {
13
14namespace {
15
16// Addition chain for (p-11)/16, found using https://github.com/mmcloughlin/addchain
17FieldElement2 pow_p_minus_11_over_16(const FieldElement2& x) {
18 auto t3 = x.square();
19 auto t4 = t3.square();
20 auto z = t4 * x;
21 auto t6 = t4.square();
22 auto t7 = t6 * x;
23 auto t9 = t3 * t7;
24 auto t25 = t6 * t7;
25 auto t1 = t7 * t9;
26 auto t18 = t1 * z;
27 auto t10 = t18 * x;
28 auto t11 = t10.square();
29 auto t5 = t11 * t3;
30 auto t2 = t5 * x;
31 auto t23 = t11 * t18;
32 auto t15 = t23 * t3;
33 auto t0 = t23 * t6;
34 auto t21 = t0 * t6;
35 auto t12 = t10 * t23;
36 auto t20 = t12 * t3;
37 auto t17 = t10 * t21;
38 auto t8 = t17 * t4;
39 auto t13 = t0 * t11;
40 t10 *= t8;
41 auto t16 = t10 * t3;
42 t3 = t1 * t10;
43 auto t22 = t3 * t6;
44 t5 *= t13;
45 t11 = t4 * t5;
46 t6 = t25 * t5;
47 auto t19 = t1 * t11;
48 auto t14 = t25 * t6;
49 auto t24 = t14 * t4;
50 t4 = t1 * t19;
51 t6 = t1 * t14;
52 t1 *= t4;
53 auto t26 = t14 * t5;
54 t26.square_n(8);
55 t25 *= t26;
56 t25.square_n(11);
57 t25 *= t6;
58 t25.square_n(11);
59 t24 *= t25;
60 t24.square_n(8);
61 t24 *= t1;
62 t24.square_n(7);
63 t23 *= t24;
64 t23.square_n(9);
65 t23 *= t20;
66 t23.square_n(10);
67 t22 *= t23;
68 t22.square_n(7);
69 t21 *= t22;
70 t21.square_n(9);
71 t21 *= t8;
72 t21.square_n(6);
73 t21 *= t18;
74 t21.square_n(11);
75 t20 *= t21;
76 t20.square_n(9);
77 t20 *= t4;
78 t20.square_n(10);
79 t19 *= t20;
80 t19.square_n(6);
81 t18 *= t19;
82 t18.square_n(10);
83 t17 *= t18;
84 t17.square_n(9);
85 t16 *= t17;
86 t16.square_n(11);
87 t15 *= t16;
88 t15.square_n(10);
89 t14 *= t15;
90 t14.square_n(9);
91 t13 *= t14;
92 t13.square_n(9);
93 t13 *= t5;
94 t13.square_n(8);
95 t12 *= t13;
96 t12.square_n(10);
97 t11 *= t12;
98 t11.square_n(9);
99 t10 *= t11;
100 t10.square_n(12);
101 t10 *= t8;
102 t10.square_n(5);
103 t9 *= t10;
104 t9.square_n(11);
105 t8 *= t9;
106 t8.square_n(7);
107 t7 *= t8;
108 t7.square_n(13);
109 t6 *= t7;
110 t6.square_n(9);
111 t5 *= t6;
112 t5.square_n(8);
113 t5 *= t1;
114 t5.square_n(8);
115 t4 *= t5;
116 t4.square_n(11);
117 t3 *= t4;
118 t3.square_n(8);
119 t3 *= t1;
120 t3.square_n(8);
121 t3 *= t1;
122 t3.square_n(6);
123 t2 *= t3;
124 t2.square_n(10);
125 t2 *= t1;
126 t2.square_n(9);
127 t2 *= t1;
128 t2.square_n(8);
129 t2 *= t1;
130 t2.square_n(8);
131 t2 *= t1;
132 t2.square_n(8);
133 t1 *= t2;
134 t1.square_n(7);
135 t0 *= t1;
136 t0.square_n(4);
137 z *= t0;
138 z = z.square();
139 return z;
140}
141
142} // namespace
143
145 const auto t = pow_p_minus_11_over_16(x);
146 const auto t2 = t.square();
147 const auto t4 = t2.square();
148 const auto t8 = t4.square();
149 const auto t11 = t8 * t2 * t;
150
151 const auto x2 = x.square();
152 const auto x3 = x2 * x;
153 const auto x6 = x3.square();
154 const auto x7 = x6 * x;
155
156 // (p^2-9)/16 = q*p + 11*q + 7 for q = (p-11)/16
157 return t.conjugate() * t11 * x7;
158}
159
160//static
161std::optional<FieldElement2> FieldElement2::deserialize(std::span<const uint8_t> bytes) {
162 if(bytes.size() != FieldElement2::BYTES) {
163 return {};
164 }
165
166 // The c1 coefficient is encoded first
167 const auto c1 = FieldElement::deserialize(bytes.first(FieldElement::BYTES));
168 const auto c0 = FieldElement::deserialize(bytes.last(FieldElement::BYTES));
169
170 if(!c0 || !c1) {
171 return {};
172 }
173
174 return FieldElement2(*c0, *c1);
175}
176
177void FieldElement2::serialize_to(std::span<uint8_t, FieldElement2::BYTES> bytes) const {
178 m_c1.serialize_to(bytes.first<FieldElement::BYTES>());
179 m_c0.serialize_to(bytes.last<FieldElement::BYTES>());
180}
181
183 return m_c0.is_zero() && m_c1.is_zero();
184}
185
187 return FieldElement2(m_c0 + x.m_c0, m_c1 + x.m_c1);
188}
189
191 return FieldElement2(m_c0 - x.m_c0, m_c1 - x.m_c1);
192}
193
195 // Karatsuba multiplication using 3 base field multiplications:
196 // (a0 + a1*u)(b0 + b1*u) = (a0*b0 - a1*b1) + ((a0+a1)(b0+b1) - a0*b0 - a1*b1)*u
197 const auto v0 = m_c0 * x.m_c0;
198 const auto v1 = m_c1 * x.m_c1;
199 const auto s = (m_c0 + m_c1) * (x.m_c0 + x.m_c1);
200
201 return FieldElement2(v0 - v1, s - v0 - v1);
202}
203
205 // Complex squaring using 2 base field multiplications:
206 // (a + b*u)^2 = (a+b)(a-b) + (2ab)*u
207 const auto t0 = (m_c0 + m_c1) * (m_c0 - m_c1);
208 const auto t1 = m_c0 * m_c1;
209
210 return FieldElement2(t0, t1 + t1);
211}
212
214 for(size_t i = 0; i != n; ++i) {
215 (*this) = this->square();
216 }
217}
218
220 return FieldElement2(m_c0.negate(), m_c1.negate());
221}
222
224 return FieldElement2(m_c0, m_c1.negate());
225}
226
228 // (a + b*u)(u + 1) = (a - b) + (a + b)*u using u^2 = -1
229 return FieldElement2(m_c0 - m_c1, m_c0 + m_c1);
230}
231
233 /*
234 * We wish to compute the inverse of (a + b*u) where u^2 = -1
235 *
236 * Consider the identity (a + b*u)(a - b*u) = a^2 + b^2. Shifting
237 * the terms implies the inverse of (a + b*u) is (a - b*u)/(a^2 + b^2)
238 */
239
240 // First compute (a^2 + b^2)^-1
241 const auto ninv = (m_c0.square() + m_c1.square()).invert();
242
243 // Apply the inverse then additional negate c1
244 return FieldElement2(m_c0 * ninv, (m_c1 * ninv).negate());
245}
246
248 return (m_c0 == other.m_c0) && (m_c1 == other.m_c1);
249}
250
252 m_c0.conditional_assign(cnd, other.m_c0);
253 m_c1.conditional_assign(cnd, other.m_c1);
254}
255
257 return m_c1._is_lexicographically_largest() || (m_c1.is_zero() && m_c0._is_lexicographically_largest());
258}
259
261 // Algorithm 9 of https://eprint.iacr.org/2012/685.pdf for q == 3 (mod 4)
262
263 constexpr auto FP2_P = hex_to_words<word>(
264 "1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab");
265
266 // (p-3)/4; since p == 3 (mod 4) this is p >> 2
267 constexpr auto FP2_SQRT_EXP = [FP2_P] {
268 auto x = FP2_P;
270 return x;
271 }();
272
273 // (p-1)/2, ie p >> 1
274 constexpr auto FP2_P_HALF = [FP2_P] {
275 auto x = FP2_P;
277 return x;
278 }();
279
280 // a1 = x^((p-3)/4)
281 const auto a1 = pow_msb(*this, FP2_SQRT_EXP);
282
283 // alpha = a1^2 * x = x^((p-1)/2)
284 const auto alpha = a1.square() * (*this);
285
286 // x0 = a1 * x = x^((p+1)/4)
287 const auto x0 = a1 * (*this);
288
289 // If alpha == -1 the square root is x0 * u; otherwise it is
290 // (1 + alpha)^((p-1)/2) * x0. In the first case 1 + alpha == 0 so the
291 // generic computation yields zero and is overridden in constant time.
292 auto candidate = pow_msb(alpha + FieldElement2::one(), FP2_P_HALF) * x0;
293
294 const auto x0_u = FieldElement2(x0.c1().negate(), x0.c0());
295 const auto alpha_is_neg_one = (alpha == FieldElement2::one().negate());
296 candidate.conditional_assign(alpha_is_neg_one, x0_u);
297
298 return CT::Option<FieldElement2>(candidate, candidate.square() == (*this));
299}
300
301} // namespace Botan::BLS12_381
FieldElement2 add(const FieldElement2 &x) const
void conditional_assign(CT::Choice cnd, const FieldElement2 &other)
CT::Option< FieldElement2 > sqrt() const
FieldElement2 mul_by_nonresidue() const
constexpr FieldElement2()=default
CT::Choice _is_lexicographically_largest() const
FieldElement2 mul(const FieldElement2 &x) const
FieldElement2 conjugate() const
CT::Choice operator==(const FieldElement2 &other) const
static std::optional< FieldElement2 > deserialize(std::span< const uint8_t > bytes)
FieldElement2 sub(const FieldElement2 &x) const
static constexpr size_t BYTES
const FieldElement & c0() const
const FieldElement & c1() const
void serialize_to(std::span< uint8_t, FieldElement2::BYTES > bytes) const
static constexpr size_t BYTES
static std::optional< FieldElement > deserialize(std::span< const uint8_t > bytes)
FieldElement2 pow_p2_minus_9_over_16(const FieldElement2 &x)
FE pow_msb(const FE &x, const std::array< word, N > &exp)
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:921
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:904