7#ifndef BOTAN_PCURVES_MUL_H_
8#define BOTAN_PCURVES_MUL_H_
10#include <botan/types.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/pcurves_algos.h>
23static constexpr size_t BasePointWindowBits = 5;
24static constexpr size_t VarPointWindowBits = 4;
25static constexpr size_t Mul2PrecompWindowBits = 3;
26static constexpr size_t Mul2WindowBits = 2;
37template <
typename C,
size_t R = 0>
65 auto result = AffinePoint::identity(m_table[0]);
68 const size_t idx1 =
static_cast<size_t>(idx - 1);
69 for(
size_t i = 0; i != m_table.size(); ++i) {
71 result.conditional_assign(found, m_table[i]);
87 auto result = AffinePoint::identity(m_table[R * iter]);
90 const size_t idx1 =
static_cast<size_t>(idx - 1);
91 for(
size_t i = 0; i != R; ++i) {
93 result.conditional_assign(found, m_table[R * iter + i]);
100 std::vector<AffinePoint> m_table;
140template <
typename C,
size_t WindowBits>
141std::vector<typename C::AffinePoint>
basemul_setup(
const typename C::AffinePoint& p,
size_t max_scalar_bits) {
142 static_assert(WindowBits >= 1 && WindowBits <= 8);
145 constexpr size_t WindowElements = (1 << WindowBits) - 1;
147 const size_t Windows = (max_scalar_bits + WindowBits - 1) / WindowBits;
149 const size_t TableSize = Windows * WindowElements;
151 std::vector<typename C::ProjectivePoint> table;
152 table.reserve(TableSize);
154 auto accum = C::ProjectivePoint::from_affine(p);
156 for(
size_t i = 0; i != TableSize; i += WindowElements) {
157 table.push_back(accum);
159 for(
size_t j = 1; j != WindowElements; ++j) {
162 table.emplace_back(table[i + j / 2].dbl());
164 table.emplace_back(table[i + j - 1] + table[i]);
168 accum = table[i + (WindowElements / 2)].dbl();
174template <
typename C,
size_t WindowBits,
typename BlindedScalar>
175typename C::ProjectivePoint
basemul_exec(std::span<const typename C::AffinePoint> table,
176 const BlindedScalar& scalar,
179 static constexpr size_t WindowElements = (1 << WindowBits) - 1;
184 const size_t w_0 = scalar.get_window(0);
185 const auto tbl_0 = table.first(WindowElements);
186 auto pt = C::ProjectivePoint::from_affine(C::AffinePoint::ct_select(tbl_0, w_0));
188 pt.randomize_rep(rng);
192 const size_t windows = (scalar.bits() + WindowBits - 1) / WindowBits;
194 for(
size_t i = 1; i != windows; ++i) {
195 const size_t w_i = scalar.get_window(WindowBits * i);
196 const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
203 accum += C::AffinePoint::ct_select(tbl_i, w_i);
207 accum.randomize_rep(rng);
218template <
typename C,
size_t TableSize>
220 static_assert(TableSize > 2);
222 std::vector<typename C::ProjectivePoint> table;
223 table.reserve(TableSize);
224 table.push_back(C::ProjectivePoint::from_affine(p));
226 for(
size_t i = 1; i != TableSize; ++i) {
229 table.push_back(table[i / 2].dbl());
231 table.push_back(table[i - 1] + p);
238template <
typename C,
size_t WindowBits,
typename BlindedScalar>
240 const BlindedScalar& scalar,
242 const size_t windows = (scalar.bits() + WindowBits - 1) / WindowBits;
245 const size_t w_0 = scalar.get_window((windows - 1) * WindowBits);
246 auto pt = C::ProjectivePoint::from_affine(table.
ct_select(w_0));
248 pt.randomize_rep(rng);
252 for(
size_t i = 1; i != windows; ++i) {
253 accum = accum.dbl_n(WindowBits);
254 auto w_i = scalar.get_window((windows - i - 1) * WindowBits);
286 accum.randomize_rep(rng);
315template <
typename C,
size_t WindowBits>
316std::vector<typename C::ProjectivePoint>
mul2_setup(
const typename C::AffinePoint& p,
317 const typename C::AffinePoint& q) {
318 static_assert(WindowBits >= 1 && WindowBits <= 4);
321 constexpr size_t TableSize = (1 << (2 * WindowBits)) - 1;
322 constexpr size_t WindowSize = (1 << WindowBits);
324 std::vector<typename C::ProjectivePoint> table;
325 table.reserve(TableSize);
327 for(
size_t i = 0; i != TableSize; ++i) {
328 const size_t t_i = (i + 1);
329 const size_t p_i = t_i % WindowSize;
330 const size_t q_i = (t_i >> WindowBits) % WindowSize;
335 auto next_tbl_e = [&]() {
336 if(p_i % 2 == 0 && q_i % 2 == 0) {
339 return table[(t_i / 2) - 1].dbl();
340 }
else if(p_i > 0 && q_i > 0) {
343 return p + table[(q_i << WindowBits) - 1];
344 }
else if(q_i == 1) {
345 return table[p_i - 1] + q;
347 return table[p_i - 1] + table[(q_i << WindowBits) - 1];
349 }
else if(p_i > 0 && q_i == 0) {
353 return C::ProjectivePoint::from_affine(p);
356 return p + table[p_i - 1 - 1];
358 }
else if(p_i == 0 && q_i > 0) {
361 return C::ProjectivePoint::from_affine(q);
364 return q + table[((q_i - 1) << WindowBits) - 1];
371 table.emplace_back(next_tbl_e());
377template <
typename C,
size_t WindowBits,
typename BlindedScalar>
379 const BlindedScalar& x,
380 const BlindedScalar& y,
382 const size_t Windows = (x.bits() + WindowBits - 1) / WindowBits;
385 const size_t w_1 = x.get_window((Windows - 1) * WindowBits);
386 const size_t w_2 = y.get_window((Windows - 1) * WindowBits);
387 const size_t window = w_1 + (w_2 << WindowBits);
388 auto pt = C::ProjectivePoint::from_affine(table.
ct_select(window));
390 pt.randomize_rep(rng);
394 for(
size_t i = 1; i != Windows; ++i) {
395 accum = accum.dbl_n(WindowBits);
397 const size_t w_1 = x.get_window((Windows - i - 1) * WindowBits);
398 const size_t w_2 = y.get_window((Windows - i - 1) * WindowBits);
399 const size_t window = w_1 + (w_2 << WindowBits);
404 accum.randomize_rep(rng);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT_UNREACHABLE()
typename C::ProjectivePoint ProjectivePoint
AffinePoint ct_select(size_t idx) const
typename C::AffinePoint AffinePoint
AffinePoint ct_select(size_t idx, size_t iter) const
static constexpr bool WholeRangeSearch
AffinePointTable(std::span< const ProjectivePoint > pts)
static constexpr Mask< T > is_equal(T x, T y)
constexpr void unpoison(const T *p, size_t n)
constexpr void poison(const T *p, size_t n)
C::ProjectivePoint varpoint_exec(const AffinePointTable< C > &table, const BlindedScalar &scalar, RandomNumberGenerator &rng)
auto to_affine_batch(std::span< const typename C::ProjectivePoint > projective)
C::ProjectivePoint mul2_exec(const AffinePointTable< C > &table, const BlindedScalar &x, const BlindedScalar &y, RandomNumberGenerator &rng)
C::ProjectivePoint basemul_exec(std::span< const typename C::AffinePoint > table, const BlindedScalar &scalar, RandomNumberGenerator &rng)
std::vector< typename C::ProjectivePoint > mul2_setup(const typename C::AffinePoint &p, const typename C::AffinePoint &q)
AffinePointTable< C > varpoint_setup(const typename C::AffinePoint &p)
std::vector< typename C::AffinePoint > basemul_setup(const typename C::AffinePoint &p, size_t max_scalar_bits)