7#ifndef BOTAN_BLS12_381_POINT_MUL_H_
8#define BOTAN_BLS12_381_POINT_MUL_H_
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>
34 while(n >= (
static_cast<size_t>(2) << log2n)) {
37 return std::min<size_t>((log2n * 69) / 100 + 2, 16);
44inline size_t scalar_window_at(std::span<const uint8_t, Scalar::BYTES> bytes,
size_t bit,
size_t c) {
46 for(
size_t k = 0; k != c; ++k) {
47 const size_t b = bit + k;
52 digit |=
static_cast<size_t>((
byte >> (b % 8)) & 1) << k;
61inline std::pair<size_t, CT::Choice>
scalar_booth_window(std::span<const uint8_t, Scalar::BYTES> bytes,
64 const size_t raw = (window == 0) ? (
scalar_window_at(bytes, 0, window_bits) << 1)
79 static Pt
ct_select(std::span<const Pt> pts,
size_t idx) {
80 auto result = Pt::identity();
84 for(
size_t i = 0; i != pts.size(); ++i) {
88 for(
size_t i = 0; i != pts.size(); ++i) {
92 for(
size_t i = 0; i != pts.size(); ++i) {
102 result.conditional_negate(negate.
into_bitmask<uint32_t>() & 1);
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;
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);
126 auto accum = Pt::identity();
128 for(
size_t i = WINDOWS; i > 0; --i) {
130 for(
size_t j = 0; j != WINDOW_BITS; ++j) {
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;
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);
164 auto accum = Pt::identity();
166 for(
size_t i = WINDOWS; i > 0; --i) {
168 for(
size_t j = 0; j != WINDOW_BITS; ++j) {
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;
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);
200 auto accum = Pt::identity();
202 for(
size_t i = WINDOWS; i > 0; --i) {
204 for(
size_t j = 0; j != WINDOW_BITS; ++j) {
210 accum = accum.add(negate.as_bool() ? tbl[digit].negate() : tbl[digit]);
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;
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);
237 auto accum = Pt::identity();
239 for(
size_t i = WINDOWS; i > 0; --i) {
241 for(
size_t j = 0; j != WINDOW_BITS; ++j) {
248 accum = accum.add(anegate.as_bool() ? ptbl[adigit].negate() : ptbl[adigit]);
251 accum = accum.add(bnegate.as_bool() ? qtbl[bdigit].negate() : qtbl[bdigit]);
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");
271 return Pt::identity();
276 constexpr size_t PIPPENGER_MIN_SIZE = 16;
278 if(points.size() < PIPPENGER_MIN_SIZE) {
279 auto accum = Pt::identity();
281 for(; i + 2 <= points.size(); i += 2) {
283 mul2_vartime(Pt::from_affine(points[i]), scalars[i], Pt::from_affine(points[i + 1]), scalars[i + 1]));
285 if(i < points.size()) {
286 accum = accum.add(
mul_vartime(Pt::from_affine(points[i]), scalars[i]));
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());
304 std::vector<Pt> buckets(
static_cast<size_t>(1) << (c - 1));
306 auto accum = Pt::identity();
308 for(
size_t w = 0; w != windows; ++w) {
310 for(
size_t j = 0; j != c; ++j) {
315 std::ranges::fill(buckets, Pt::identity());
317 const size_t window = windows - 1 - w;
318 for(
size_t i = 0; i != points.size(); ++i) {
321 buckets[digit - 1] = buckets[digit - 1].add_mixed(points[i], negate.as_bool());
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);
332 accum = accum.add(window_sum);
348 for(
size_t b = 63; b > 0; --b) {
352 accum = accum.add(pt);
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
static constexpr size_t BYTES
std::array< uint8_t, Scalar::BYTES > serialize() const
constexpr T into_bitmask() const
static constexpr Mask< T > is_equal(T x, T y)
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)
constexpr void unpoison_all(const Ts &... ts)
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
constexpr void poison(const T *p, size_t n)
constexpr std::pair< size_t, CT::Choice > booth_recode(size_t x, size_t window_bits)
void secure_scrub_memory(void *ptr, size_t n)