Botan 3.14.1
Crypto and TLS for C&
Botan::BLS12_381::PointMul< Pt > Class Template Referencefinal

#include <bls12_381_point_mul.h>

Static Public Member Functions

static Pt ct_select (std::span< const Pt > pts, size_t idx)
static Pt ct_select_signed (std::span< const Pt > pts, size_t idx, CT::Choice negate)
template<typename AffinePt>
static Pt msm_vartime (std::span< const AffinePt > points, std::span< const Scalar > scalars)
static Pt mul (const Pt &pt, const Scalar &scalar)
static Pt mul2 (const Pt &p, const Scalar &a, const Pt &q, const Scalar &b)
static Pt mul2_vartime (const Pt &p, const Scalar &a, const Pt &q, const Scalar &b)
static Pt mul_by_z_abs (const Pt &pt)
static Pt mul_vartime (const Pt &pt, const Scalar &scalar)

Detailed Description

template<typename Pt>
class Botan::BLS12_381::PointMul< Pt >

The scalar multiplication algorithms, shared by G1 and G2; the group specific formulas remain member functions of the point types.

Definition at line 74 of file bls12_381_point_mul.h.

Member Function Documentation

◆ ct_select()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::ct_select ( std::span< const Pt > pts,
size_t idx )
inlinestatic

Return pts[idx], without leaking idx

Definition at line 79 of file bls12_381_point_mul.h.

79 {
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 }
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754

References Botan::CT::conditional_assign_mem(), and Botan::CT::Mask< T >::is_equal().

Referenced by ct_select_signed().

◆ ct_select_signed()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::ct_select_signed ( std::span< const Pt > pts,
size_t idx,
CT::Choice negate )
inlinestatic

Definition at line 100 of file bls12_381_point_mul.h.

100 {
101 auto result = ct_select(pts, idx);
102 result.conditional_negate(negate.into_bitmask<uint32_t>() & 1);
103 return result;
104 }
static Pt ct_select(std::span< const Pt > pts, size_t idx)

References ct_select(), and Botan::CT::Choice::into_bitmask().

Referenced by mul(), and mul2().

◆ msm_vartime()

template<typename Pt>
template<typename AffinePt>
Pt Botan::BLS12_381::PointMul< Pt >::msm_vartime ( std::span< const AffinePt > points,
std::span< const Scalar > scalars )
inlinestatic

Variable time multiscalar multiplication

Definition at line 265 of file bls12_381_point_mul.h.

265 {
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(
284 }
285 if(i < points.size()) {
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
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
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]);
330 }
331
332 accum = accum.add(window_sum);
333 }
334
336
337 return accum;
338 }
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)
size_t pippenger_window_bits(size_t n)
std::pair< size_t, CT::Choice > scalar_booth_window(std::span< const uint8_t, Scalar::BYTES > bytes, size_t window, size_t window_bits)
void secure_scrub_memory(void *ptr, size_t n)
Definition mem_utils.cpp:24

References Botan::BLS12_381::Scalar::BITS, Botan::BLS12_381::Scalar::BYTES, mul2_vartime(), mul_vartime(), Botan::BLS12_381::pippenger_window_bits(), Botan::BLS12_381::scalar_booth_window(), and Botan::secure_scrub_memory().

Referenced by Botan::BLS12_381::G1Projective::msm_vartime(), and Botan::BLS12_381::G2Projective::msm_vartime().

◆ mul()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::mul ( const Pt & pt,
const Scalar & scalar )
inlinestatic

Constant time fixed window multiplication

Possible optimizations: a precomputed table (cf pcurves PrecomputedBaseMulTable) for the common fixed-base case, and a GLV/psi endomorphism split to roughly halve the doubling count

Definition at line 113 of file bls12_381_point_mul.h.

113 {
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
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();
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);
136 }
137
139 CT::unpoison_all(sbytes, accum.m_x, accum.m_y, accum.m_z);
140
141 return accum;
142 }
static Pt ct_select_signed(std::span< const Pt > pts, size_t idx, CT::Choice negate)
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56

References Botan::BLS12_381::Scalar::BITS, ct_select_signed(), Botan::CT::poison(), Botan::BLS12_381::scalar_booth_window(), Botan::secure_scrub_memory(), Botan::BLS12_381::Scalar::serialize(), and Botan::CT::unpoison_all().

Referenced by Botan::BLS12_381::G1Projective::mul(), and Botan::BLS12_381::G2Projective::mul().

◆ mul2()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::mul2 ( const Pt & p,
const Scalar & a,
const Pt & q,
const Scalar & b )
inlinestatic

Constant time a*p + b*q

Definition at line 147 of file bls12_381_point_mul.h.

147 {
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
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();
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);
176 }
177
181
182 return accum;
183 }
constexpr void poison_all(const Ts &... ts)
Definition ct_utils.h:201

References Botan::BLS12_381::Scalar::BITS, ct_select_signed(), Botan::CT::poison_all(), Botan::BLS12_381::scalar_booth_window(), Botan::secure_scrub_memory(), Botan::BLS12_381::Scalar::serialize(), and Botan::CT::unpoison_all().

Referenced by Botan::BLS12_381::G1Projective::mul2(), and Botan::BLS12_381::G2Projective::mul2().

◆ mul2_vartime()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::mul2_vartime ( const Pt & p,
const Scalar & a,
const Pt & q,
const Scalar & b )
inlinestatic

Variable time a*p + b*q

Definition at line 222 of file bls12_381_point_mul.h.

222 {
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
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
257
258 return accum;
259 }

References Botan::BLS12_381::Scalar::BITS, Botan::BLS12_381::scalar_booth_window(), Botan::secure_scrub_memory(), and Botan::BLS12_381::Scalar::serialize().

Referenced by msm_vartime(), Botan::BLS12_381::G1Projective::mul2_vartime(), and Botan::BLS12_381::G2Projective::mul2_vartime().

◆ mul_by_z_abs()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::mul_by_z_abs ( const Pt & pt)
inlinestatic

Multiplication by |z|, the absolute value of the BLS parameter, used for the subgroup checks and cofactor clearing

Definition at line 344 of file bls12_381_point_mul.h.

344 {
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 }

References Botan::BLS12_381::BLS_Z_ABS.

Referenced by Botan::BLS12_381::G2Affine::deserialize().

◆ mul_vartime()

template<typename Pt>
Pt Botan::BLS12_381::PointMul< Pt >::mul_vartime ( const Pt & pt,
const Scalar & scalar )
inlinestatic

Variable time single point multiplication

Definition at line 188 of file bls12_381_point_mul.h.

188 {
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
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
215
216 return accum;
217 }

References Botan::BLS12_381::Scalar::BITS, Botan::BLS12_381::scalar_booth_window(), Botan::secure_scrub_memory(), and Botan::BLS12_381::Scalar::serialize().

Referenced by msm_vartime().


The documentation for this class was generated from the following file: