Botan 3.14.1
Crypto and TLS for C&
bls12_381_point_mul.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_POINT_MUL_H_
8#define BOTAN_BLS12_381_POINT_MUL_H_
9
10#include <botan/bls12_381.h>
11#include <botan/exceptn.h>
12#include <botan/mem_ops.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/mp_core.h>
15#include <algorithm>
16#include <utility>
17#include <vector>
18
19namespace Botan::BLS12_381 {
20
21// z = -0xd201000000010000 (negative; the Miller loop and final exponentiation
22// use |z| and account for the sign by conjugation)
23constexpr uint64_t BLS_Z_ABS = 0xD201000000010000;
24
25/**
26* Window size heuristic for the Pippenger bucket method,
27* approximately ln(n) + 2
28*/
29inline size_t pippenger_window_bits(size_t n) {
30 if(n < 32) {
31 return 3;
32 }
33 size_t log2n = 5;
34 while(n >= (static_cast<size_t>(2) << log2n)) {
35 ++log2n;
36 }
37 return std::min<size_t>((log2n * 69) / 100 + 2, 16);
38}
39
40/**
41* Extract the c-bit window starting at bit offset bit (counted from the
42* least significant end) of a big-endian encoded scalar
43*/
44inline size_t scalar_window_at(std::span<const uint8_t, Scalar::BYTES> bytes, size_t bit, size_t c) {
45 size_t digit = 0;
46 for(size_t k = 0; k != c; ++k) {
47 const size_t b = bit + k;
48 if(b >= 8 * Scalar::BYTES) {
49 break;
50 }
51 const uint8_t byte = bytes[Scalar::BYTES - 1 - (b / 8)];
52 digit |= static_cast<size_t>((byte >> (b % 8)) & 1) << k;
53 }
54 return digit;
55}
56
57/**
58* Extract the Booth recoded window of a serialized scalar; constant time
59* with respect to the scalar bytes
60*/
61inline std::pair<size_t, CT::Choice> scalar_booth_window(std::span<const uint8_t, Scalar::BYTES> bytes,
62 size_t window,
63 size_t window_bits) {
64 const size_t raw = (window == 0) ? (scalar_window_at(bytes, 0, window_bits) << 1)
65 : scalar_window_at(bytes, window * window_bits - 1, window_bits + 1);
66 return booth_recode(raw, window_bits);
67}
68
69/**
70* The scalar multiplication algorithms, shared by G1 and G2; the group
71* specific formulas remain member functions of the point types.
72*/
73template <typename Pt>
74class PointMul final {
75 public:
76 /**
77 * Return pts[idx], without leaking idx
78 */
79 static Pt ct_select(std::span<const Pt> pts, size_t idx) {
80 auto result = Pt::identity();
81
82 // Selecting one coordinate at a time limits the number of live vector
83 // registers; otherwise valgrind on aarch64 crashes (in genSpill_ARM64)
84 for(size_t i = 0; i != pts.size(); ++i) {
85 const auto cnd = CT::Mask<word>::is_equal(i, idx).as_choice();
86 CT::conditional_assign_mem(cnd, result.m_x.data(), pts[i].m_x.data(), result.m_x.size());
87 }
88 for(size_t i = 0; i != pts.size(); ++i) {
89 const auto cnd = CT::Mask<word>::is_equal(i, idx).as_choice();
90 CT::conditional_assign_mem(cnd, result.m_y.data(), pts[i].m_y.data(), result.m_y.size());
91 }
92 for(size_t i = 0; i != pts.size(); ++i) {
93 const auto cnd = CT::Mask<word>::is_equal(i, idx).as_choice();
94 CT::conditional_assign_mem(cnd, result.m_z.data(), pts[i].m_z.data(), result.m_z.size());
95 }
96
97 return result;
98 }
99
100 static Pt ct_select_signed(std::span<const Pt> pts, size_t idx, CT::Choice negate) {
101 auto result = ct_select(pts, idx);
102 result.conditional_negate(negate.into_bitmask<uint32_t>() & 1);
103 return result;
104 }
105
106 /**
107 * Constant time fixed window multiplication
108 *
109 * Possible optimizations: a precomputed table (cf pcurves
110 * PrecomputedBaseMulTable) for the common fixed-base case, and a
111 * GLV/psi endomorphism split to roughly halve the doubling count
112 */
113 static Pt mul(const Pt& pt, const Scalar& scalar) {
114 constexpr size_t WINDOW_BITS = 4;
115 constexpr size_t TABLE_SIZE = (1 << (WINDOW_BITS - 1)) + 1;
116 constexpr size_t WINDOWS = (Scalar::BITS + WINDOW_BITS) / WINDOW_BITS;
117
118 std::array<Pt, TABLE_SIZE> tbl;
119 for(size_t i = 1; i != TABLE_SIZE; ++i) {
120 tbl[i] = tbl[i - 1].add(pt);
121 }
122
123 auto sbytes = scalar.serialize();
124 CT::poison(sbytes);
125
126 auto accum = Pt::identity();
127
128 for(size_t i = WINDOWS; i > 0; --i) {
129 if(i < WINDOWS) {
130 for(size_t j = 0; j != WINDOW_BITS; ++j) {
131 accum = accum.dbl();
132 }
133 }
134 const auto [digit, negate] = scalar_booth_window(sbytes, i - 1, WINDOW_BITS);
135 accum = accum.add(ct_select_signed(tbl, digit, negate));
136 }
137
138 secure_scrub_memory(sbytes);
139 CT::unpoison_all(sbytes, accum.m_x, accum.m_y, accum.m_z);
140
141 return accum;
142 }
143
144 /**
145 * Constant time a*p + b*q
146 */
147 static Pt mul2(const Pt& p, const Scalar& a, const Pt& q, const Scalar& b) {
148 constexpr size_t WINDOW_BITS = 4;
149 constexpr size_t TABLE_SIZE = (1 << (WINDOW_BITS - 1)) + 1;
150 constexpr size_t WINDOWS = (Scalar::BITS + WINDOW_BITS) / WINDOW_BITS;
151
152 // Interleaved Strauss-Shamir; both scalars share one doubling chain
153 std::array<Pt, TABLE_SIZE> ptbl;
154 std::array<Pt, TABLE_SIZE> qtbl;
155 for(size_t i = 1; i != TABLE_SIZE; ++i) {
156 ptbl[i] = ptbl[i - 1].add(p);
157 qtbl[i] = qtbl[i - 1].add(q);
158 }
159
160 auto abytes = a.serialize();
161 auto bbytes = b.serialize();
162 CT::poison_all(abytes, bbytes);
163
164 auto accum = Pt::identity();
165
166 for(size_t i = WINDOWS; i > 0; --i) {
167 if(i < WINDOWS) {
168 for(size_t j = 0; j != WINDOW_BITS; ++j) {
169 accum = accum.dbl();
170 }
171 }
172 const auto [adigit, anegate] = scalar_booth_window(abytes, i - 1, WINDOW_BITS);
173 const auto [bdigit, bnegate] = scalar_booth_window(bbytes, i - 1, WINDOW_BITS);
174 accum = accum.add(ct_select_signed(ptbl, adigit, anegate));
175 accum = accum.add(ct_select_signed(qtbl, bdigit, bnegate));
176 }
177
178 secure_scrub_memory(abytes);
179 secure_scrub_memory(bbytes);
180 CT::unpoison_all(abytes, bbytes, accum.m_x, accum.m_y, accum.m_z);
181
182 return accum;
183 }
184
185 /**
186 * Variable time single point multiplication
187 */
188 static Pt mul_vartime(const Pt& pt, const Scalar& scalar) {
189 constexpr size_t WINDOW_BITS = 4;
190 constexpr size_t TABLE_SIZE = (1 << (WINDOW_BITS - 1)) + 1;
191 constexpr size_t WINDOWS = (Scalar::BITS + WINDOW_BITS) / WINDOW_BITS;
192
193 std::array<Pt, TABLE_SIZE> tbl;
194 for(size_t i = 1; i != TABLE_SIZE; ++i) {
195 tbl[i] = tbl[i - 1].add(pt);
196 }
197
198 auto sbytes = scalar.serialize();
199
200 auto accum = Pt::identity();
201
202 for(size_t i = WINDOWS; i > 0; --i) {
203 if(i < WINDOWS) {
204 for(size_t j = 0; j != WINDOW_BITS; ++j) {
205 accum = accum.dbl();
206 }
207 }
208 const auto [digit, negate] = scalar_booth_window(sbytes, i - 1, WINDOW_BITS);
209 if(digit > 0) {
210 accum = accum.add(negate.as_bool() ? tbl[digit].negate() : tbl[digit]);
211 }
212 }
213
214 secure_scrub_memory(sbytes);
215
216 return accum;
217 }
218
219 /**
220 * Variable time a*p + b*q
221 */
222 static Pt mul2_vartime(const Pt& p, const Scalar& a, const Pt& q, const Scalar& b) {
223 constexpr size_t WINDOW_BITS = 4;
224 constexpr size_t TABLE_SIZE = (1 << (WINDOW_BITS - 1)) + 1;
225 constexpr size_t WINDOWS = (Scalar::BITS + WINDOW_BITS) / WINDOW_BITS;
226
227 std::array<Pt, TABLE_SIZE> ptbl;
228 std::array<Pt, TABLE_SIZE> qtbl;
229 for(size_t i = 1; i != TABLE_SIZE; ++i) {
230 ptbl[i] = ptbl[i - 1].add(p);
231 qtbl[i] = qtbl[i - 1].add(q);
232 }
233
234 auto abytes = a.serialize();
235 auto bbytes = b.serialize();
236
237 auto accum = Pt::identity();
238
239 for(size_t i = WINDOWS; i > 0; --i) {
240 if(i < WINDOWS) {
241 for(size_t j = 0; j != WINDOW_BITS; ++j) {
242 accum = accum.dbl();
243 }
244 }
245 const auto [adigit, anegate] = scalar_booth_window(abytes, i - 1, WINDOW_BITS);
246 const auto [bdigit, bnegate] = scalar_booth_window(bbytes, i - 1, WINDOW_BITS);
247 if(adigit > 0) {
248 accum = accum.add(anegate.as_bool() ? ptbl[adigit].negate() : ptbl[adigit]);
249 }
250 if(bdigit > 0) {
251 accum = accum.add(bnegate.as_bool() ? qtbl[bdigit].negate() : qtbl[bdigit]);
252 }
253 }
254
255 secure_scrub_memory(abytes);
256 secure_scrub_memory(bbytes);
257
258 return accum;
259 }
260
261 /**
262 * Variable time multiscalar multiplication
263 */
264 template <typename AffinePt>
265 static Pt msm_vartime(std::span<const AffinePt> points, std::span<const Scalar> scalars) {
266 if(points.size() != scalars.size()) {
267 throw Invalid_Argument("BLS12_381 msm_vartime spans must have equal length");
268 }
269
270 if(points.empty()) {
271 return Pt::identity();
272 }
273
274 // Below this size a chain of 2-ary multiplications beats the
275 // Pippenger bucket method (measured crossover; not very sensitive)
276 constexpr size_t PIPPENGER_MIN_SIZE = 16;
277
278 if(points.size() < PIPPENGER_MIN_SIZE) {
279 auto accum = Pt::identity();
280 size_t i = 0;
281 for(; i + 2 <= points.size(); i += 2) {
282 accum = accum.add(
283 mul2_vartime(Pt::from_affine(points[i]), scalars[i], Pt::from_affine(points[i + 1]), scalars[i + 1]));
284 }
285 if(i < points.size()) {
286 accum = accum.add(mul_vartime(Pt::from_affine(points[i]), scalars[i]));
287 }
288 return accum;
289 }
290
291 // The Pippenger bucket method; process the scalars in c-bit windows
292 // from the most significant down, adding each point into the bucket
293 // its window digit selects, then form the window sum with a running
294 // sum over the buckets.
295 const size_t c = pippenger_window_bits(points.size());
296 const size_t windows = (Scalar::BITS + c) / c;
297
298 std::vector<std::array<uint8_t, Scalar::BYTES>> sbytes;
299 sbytes.reserve(scalars.size());
300 for(const auto& scalar : scalars) {
301 sbytes.push_back(scalar.serialize());
302 }
303
304 std::vector<Pt> buckets(static_cast<size_t>(1) << (c - 1));
305
306 auto accum = Pt::identity();
307
308 for(size_t w = 0; w != windows; ++w) {
309 if(w > 0) {
310 for(size_t j = 0; j != c; ++j) {
311 accum = accum.dbl();
312 }
313 }
314
315 std::ranges::fill(buckets, Pt::identity());
316
317 const size_t window = windows - 1 - w;
318 for(size_t i = 0; i != points.size(); ++i) {
319 const auto [digit, negate] = scalar_booth_window(sbytes[i], window, c);
320 if(digit > 0) {
321 buckets[digit - 1] = buckets[digit - 1].add_mixed(points[i], negate.as_bool());
322 }
323 }
324
325 auto running = Pt::identity();
326 auto window_sum = Pt::identity();
327 for(size_t b = buckets.size(); b > 0; --b) {
328 running = running.add(buckets[b - 1]);
329 window_sum = window_sum.add(running);
330 }
331
332 accum = accum.add(window_sum);
333 }
334
335 secure_scrub_memory(sbytes.data(), sbytes.size() * Scalar::BYTES);
336
337 return accum;
338 }
339
340 /**
341 * Multiplication by |z|, the absolute value of the BLS parameter,
342 * used for the subgroup checks and cofactor clearing
343 */
344 static Pt mul_by_z_abs(const Pt& pt) {
345 static_assert((BLS_Z_ABS >> 63) == 1);
346 auto accum = pt;
347
348 for(size_t b = 63; b > 0; --b) {
349 accum = accum.dbl();
350 // The BLS parameter is a public constant so this branch leaks nothing
351 if(((BLS_Z_ABS >> (b - 1)) & 1) == 1) {
352 accum = accum.add(pt);
353 }
354 }
355
356 return accum;
357 }
358};
359
360} // namespace Botan::BLS12_381
361
362#endif
static Pt mul_by_z_abs(const Pt &pt)
static Pt ct_select(std::span< const Pt > pts, size_t idx)
static Pt mul_vartime(const Pt &pt, const Scalar &scalar)
static Pt mul2_vartime(const Pt &p, const Scalar &a, const Pt &q, const Scalar &b)
static Pt msm_vartime(std::span< const AffinePt > points, std::span< const Scalar > scalars)
static Pt mul2(const Pt &p, const Scalar &a, const Pt &q, const Scalar &b)
static Pt ct_select_signed(std::span< const Pt > pts, size_t idx, CT::Choice negate)
static Pt mul(const Pt &pt, const Scalar &scalar)
static constexpr size_t BITS
Definition bls12_381.h:32
static constexpr size_t BYTES
Definition bls12_381.h:35
std::array< uint8_t, Scalar::BYTES > serialize() const
Definition bls12_381.h:112
constexpr T into_bitmask() const
Definition ct_utils.h:291
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
size_t pippenger_window_bits(size_t n)
size_t scalar_window_at(std::span< const uint8_t, Scalar::BYTES > bytes, size_t bit, size_t c)
std::pair< size_t, CT::Choice > scalar_booth_window(std::span< const uint8_t, Scalar::BYTES > bytes, size_t window, size_t window_bits)
constexpr uint64_t BLS_Z_ABS
constexpr void poison_all(const Ts &... ts)
Definition ct_utils.h:201
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
constexpr std::pair< size_t, CT::Choice > booth_recode(size_t x, size_t window_bits)
Definition mp_core.h:1312
void secure_scrub_memory(void *ptr, size_t n)
Definition mem_utils.cpp:24