Botan 3.14.1
Crypto and TLS for C&
bls12_381_group.h
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#ifndef BOTAN_BLS12_381_GROUP_H_
8#define BOTAN_BLS12_381_GROUP_H_
9
10#include <botan/bls12_381.h>
11#include <botan/mem_ops.h>
12#include <botan/internal/bls12_381_fields.h>
13#include <botan/internal/ct_utils.h>
14#include <algorithm>
15#include <optional>
16#include <span>
17#include <vector>
18
19namespace Botan::BLS12_381 {
20
21/**
22* The group law, point codec, and affine conversion logic, shared by G1
23* and G2. The Group traits provide the point and field element types,
24* the coordinate load/store, and the curve constants.
25*/
26template <typename Group>
27class GroupOps final {
28 public:
29 using Affine = typename Group::Affine;
30 using Projective = typename Group::Projective;
31 using FE = typename Group::FE;
32
33 static_assert(Affine::BYTES == FE::BYTES);
34
35 static Projective from_affine(const Affine& affine) {
36 // z == 0 if the identity element or 1 otherwise
37 auto z = FE::one();
38 z.conditional_assign(CT::Choice::from_int(affine.m_infinity), FE::zero());
39 return Projective(Group::load(affine.m_x), Group::load(affine.m_y), z);
40 }
41
42 static Affine to_affine(const Projective& pt) {
43 const auto z = Group::load(pt.m_z);
44 const auto zinv = z.invert();
45 const auto inf = z.is_zero();
46
47 // Canonicalize the identity to (0, 1); otherwise a round trip
48 // through from_affine would produce the invalid triple (0, 0, 0),
49 // which acts as an absorbing element of the addition formulas
50 auto y = Group::load(pt.m_y) * zinv;
51 y.conditional_assign(inf, FE::one());
52
53 return Affine(Group::load(pt.m_x) * zinv, y, inf.template into_bitmask<uint32_t>() & 1);
54 }
55
56 static std::vector<Affine> to_affine_batch(std::span<const Projective> points) {
57 const size_t n = points.size();
58
59 std::vector<Affine> affine;
60 affine.reserve(n);
61
62 if(n == 0) {
63 return affine;
64 }
65
66 /*
67 Batch inversion of the z coordinates using Montgomery's trick, with a
68 single field inversion plus 3*(n-1) multiplications.
69
70 See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
71 (Hankerson, Menezes, Vanstone)
72
73 An identity element (z == 0) would zero the running product, so
74 identity z's are replaced by one, and the affine identity is instead
75 assigned at the end; this handles identities in constant time, rather
76 than leaking their presence by falling back to serial conversion.
77 */
78
79 const auto masked_z = [](const Projective& pt) {
80 auto z = Group::load(pt.m_z);
81 z.conditional_assign(z.is_zero(), FE::one());
82 return z;
83 };
84
85 const auto affine_from = [](const Projective& pt, const FE& z_inv) {
86 const auto inf = Group::load(pt.m_z).is_zero();
87
88 auto x = Group::load(pt.m_x) * z_inv;
89 auto y = Group::load(pt.m_y) * z_inv;
90
91 // Canonicalize the identity to (0, 1), as in to_affine
92 x.conditional_assign(inf, FE::zero());
93 y.conditional_assign(inf, FE::one());
94
95 return Affine(x, y, inf.template into_bitmask<uint32_t>() & 1);
96 };
97
98 std::vector<FE> prefix;
99 prefix.reserve(n);
100
101 prefix.push_back(masked_z(points[0]));
102 for(size_t i = 1; i != n; ++i) {
103 prefix.push_back(prefix[i - 1] * masked_z(points[i]));
104 }
105
106 auto inv = prefix[n - 1].invert();
107
108 for(size_t i = n; i > 1; --i) {
109 const auto& pt = points[i - 1];
110 affine.push_back(affine_from(pt, inv * prefix[i - 2]));
111 inv = inv * masked_z(pt);
112 }
113 affine.push_back(affine_from(points[0], inv));
114
115 std::reverse(affine.begin(), affine.end());
116
117 return affine;
118 }
119
120 static Projective negate(const Projective& pt) {
121 return Projective(Group::load(pt.m_x), Group::load(pt.m_y).negate(), Group::load(pt.m_z));
122 }
123
124 static void conditional_negate(Projective& pt, uint32_t negate) {
125 auto y = Group::load(pt.m_y);
126 y.conditional_assign(CT::Choice::from_int(negate), y.negate());
127 pt.m_y = Group::store(y);
128 }
129
130 static Projective dbl(const Projective& pt) {
131 // Algorithm 9, https://eprint.iacr.org/2015/1060.pdf
132
133 const auto x = Group::load(pt.m_x);
134 const auto y = Group::load(pt.m_y);
135 const auto z = Group::load(pt.m_z);
136
137 auto t0 = y.square();
138 auto z3 = t0 + t0;
139 z3 = z3 + z3;
140 z3 = z3 + z3;
141 auto t1 = y * z;
142 auto t2 = z.square();
143 t2 = Group::mul_by_3b(t2);
144 auto x3 = t2 * z3;
145 auto y3 = t0 + t2;
146 z3 = t1 * z3;
147 t1 = t2 + t2;
148 t2 = t1 + t2;
149 t0 = t0 - t2;
150 y3 = t0 * y3;
151 y3 = x3 + y3;
152 t1 = x * y;
153 x3 = t0 * t1;
154 x3 = x3 + x3;
155
156 return Projective(x3, y3, z3);
157 }
158
159 static Projective add(const Projective& a, const Projective& b) {
160 // Algorithm 7, https://eprint.iacr.org/2015/1060.pdf
161
162 const auto x1 = Group::load(a.m_x);
163 const auto y1 = Group::load(a.m_y);
164 const auto z1 = Group::load(a.m_z);
165 const auto x2 = Group::load(b.m_x);
166 const auto y2 = Group::load(b.m_y);
167 const auto z2 = Group::load(b.m_z);
168
169 auto t0 = x1 * x2;
170 auto t1 = y1 * y2;
171 auto t2 = z1 * z2;
172 auto t3 = x1 + y1;
173 auto t4 = x2 + y2;
174 t3 = t3 * t4;
175 t4 = t0 + t1;
176 t3 = t3 - t4;
177 t4 = y1 + z1;
178 auto x3 = y2 + z2;
179 t4 = t4 * x3;
180 x3 = t1 + t2;
181 t4 = t4 - x3;
182 x3 = x1 + z1;
183 auto y3 = x2 + z2;
184 x3 = x3 * y3;
185 y3 = t0 + t2;
186 y3 = x3 - y3;
187 x3 = t0 + t0;
188 t0 = x3 + t0;
189 t2 = Group::mul_by_3b(t2);
190 auto z3 = t1 + t2;
191 t1 = t1 - t2;
192 y3 = Group::mul_by_3b(y3);
193 x3 = t4 * y3;
194 t2 = t3 * t1;
195 x3 = t2 - x3;
196 y3 = y3 * t0;
197 t1 = t1 * z3;
198 y3 = t1 + y3;
199 t0 = t0 * t3;
200 z3 = z3 * t4;
201 z3 = z3 + t0;
202
203 return Projective(x3, y3, z3);
204 }
205
206 static Projective add_mixed(const Projective& a, const Affine& other, bool negate_other) {
207 // Algorithm 8, https://eprint.iacr.org/2015/1060.pdf
208 //
209 // The formula assumes other is not the identity; that case is
210 // handled by conditional assignment at the end
211
212 const auto x1 = Group::load(a.m_x);
213 const auto y1 = Group::load(a.m_y);
214 const auto z1 = Group::load(a.m_z);
215 const auto x2 = Group::load(other.m_x);
216 auto y2 = Group::load(other.m_y);
217 if(negate_other) {
218 y2 = y2.negate();
219 }
220
221 auto t0 = x1 * x2;
222 auto t1 = y1 * y2;
223 auto t3 = x2 + y2;
224 auto t4 = x1 + y1;
225 t3 = t3 * t4;
226 t4 = t0 + t1;
227 t3 = t3 - t4;
228 t4 = y2 * z1;
229 t4 = t4 + y1;
230 auto y3 = x2 * z1;
231 y3 = y3 + x1;
232 auto x3 = t0 + t0;
233 t0 = x3 + t0;
234 auto t2 = Group::mul_by_3b(z1);
235 auto z3 = t1 + t2;
236 t1 = t1 - t2;
237 y3 = Group::mul_by_3b(y3);
238 x3 = t4 * y3;
239 t2 = t3 * t1;
240 x3 = t2 - x3;
241 y3 = y3 * t0;
242 t1 = t1 * z3;
243 y3 = t1 + y3;
244 t0 = t0 * t3;
245 z3 = z3 * t4;
246 z3 = z3 + t0;
247
248 auto result = Projective(x3, y3, z3);
249
250 const auto other_is_identity = CT::Choice::from_int(other.m_infinity);
251 CT::conditional_assign_mem(other_is_identity, result.m_x.data(), a.m_x.data(), result.m_x.size());
252 CT::conditional_assign_mem(other_is_identity, result.m_y.data(), a.m_y.data(), result.m_y.size());
253 CT::conditional_assign_mem(other_is_identity, result.m_z.data(), a.m_z.data(), result.m_z.size());
254
255 return result;
256 }
257
258 /**
259 * Deserialization without the subgroup check, which is group
260 * specific and remains the caller's responsibility for any point
261 * other than the identity
262 */
263 static std::optional<Affine> deserialize_unchecked(std::span<const uint8_t> bytes) {
264 if(bytes.size() != Affine::BYTES) {
265 return {};
266 }
267
268 const uint8_t flags = bytes[0];
269
270 // Only the compressed encoding is supported
271 if((flags & 0x80) != 0x80) {
272 return {};
273 }
274
275 const bool is_infinity = (flags & 0x40) == 0x40;
276 const bool y_is_largest = (flags & 0x20) == 0x20;
277
278 std::array<uint8_t, Affine::BYTES> x_bytes{};
279 copy_mem(x_bytes.data(), bytes.data(), bytes.size());
280 x_bytes[0] &= 0x1F;
281
282 if(is_infinity) {
283 // The identity is encoded as the infinity flag with all other bits zero
284 if(y_is_largest || !CT::all_zeros(x_bytes.data(), x_bytes.size()).as_bool()) {
285 return {};
286 }
287 return Affine::identity();
288 }
289
290 const auto x = FE::deserialize(x_bytes);
291 if(!x) {
292 return {};
293 }
294
295 const auto y2 = x->square() * (*x) + Group::curve_b();
296 auto y = y2.sqrt().as_optional_vartime();
297 if(!y) {
298 return {};
299 }
300
301 // Choose either y or -y depending on the sign flag
302 const auto flip =
303 (y->_is_lexicographically_largest() != CT::Choice::from_int(static_cast<word>(flags & 0x20)));
304 y->conditional_assign(flip, y->negate());
305
306 return Affine(*x, *y, 0);
307 }
308
309 static std::array<uint8_t, Affine::BYTES> serialize(const Affine& pt) {
310 auto bytes = Group::load(pt.m_x).serialize();
311
312 // Set the compressed point indicator bit
313 bytes[0] |= 0x80;
314
315 const auto identity = CT::Choice::from_int(pt.m_infinity);
316
317 // If the identity element, set the identity bit
318 bytes[0] |= (identity.template into_bitmask<uint8_t>() & 0x40);
319
320 // If y is the larger choice *and* not the point at identity, set the large-y bit
321 const auto large_y = Group::load(pt.m_y)._is_lexicographically_largest();
322 bytes[0] |= ((!identity && large_y).template into_bitmask<uint8_t>() & 0x20);
323
324 return bytes;
325 }
326};
327
328} // namespace Botan::BLS12_381
329
330#endif
typename Group::Projective Projective
static Projective from_affine(const Affine &affine)
static Projective add(const Projective &a, const Projective &b)
static Projective add_mixed(const Projective &a, const Affine &other, bool negate_other)
static std::optional< Affine > deserialize_unchecked(std::span< const uint8_t > bytes)
static Affine to_affine(const Projective &pt)
static std::vector< Affine > to_affine_batch(std::span< const Projective > points)
static Projective dbl(const Projective &pt)
static Projective negate(const Projective &pt)
static std::array< uint8_t, Affine::BYTES > serialize(const Affine &pt)
typename Group::Affine Affine
static void conditional_negate(Projective &pt, uint32_t negate)
static constexpr Choice from_int(T v)
Definition ct_utils.h:268
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 void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
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