7#include <botan/internal/point_mul.h>
9#include <botan/reducer.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/rounding.h>
18size_t blinding_size(
const BigInt& group_order) {
19 return (group_order.bits() + 1) / 2;
30 m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p_words()) {
35 const size_t T_bits =
round_up(order_bits + blinding_size(mod_order.
get_modulus()), WINDOW_BITS) / WINDOW_BITS;
37 std::vector<EC_Point>
T(WINDOW_SIZE * T_bits);
42 for(
size_t i = 0; i != T_bits; i++) {
49 T[7 * i + 1] = std::move(g2);
50 T[7 * i + 2] =
T[7 * i + 1].plus(
T[7 * i + 0], ws);
52 T[7 * i + 4] =
T[7 * i + 3].
plus(
T[7 * i + 0], ws);
53 T[7 * i + 5] =
T[7 * i + 3].
plus(
T[7 * i + 1], ws);
54 T[7 * i + 6] =
T[7 * i + 3].
plus(
T[7 * i + 2], ws);
62 m_W.resize(
T.size() * 2 * m_p_words);
65 for(
size_t i = 0; i !=
T.size(); ++i) {
66 T[i].get_x().encode_words(p, m_p_words);
68 T[i].get_y().encode_words(p, m_p_words);
76 std::vector<BigInt>& ws)
const {
78 throw Invalid_Argument(
"EC_Point_Base_Point_Precompute scalar must be positive");
86 const BigInt mask(rng, blinding_size(group_order));
87 scalar += group_order * mask;
95 scalar += group_order;
96 if(scalar.
bits() == group_order.
bits()) {
97 scalar += group_order;
102 const size_t windows =
round_up(scalar.
bits(), WINDOW_BITS) / WINDOW_BITS;
104 const size_t elem_size = 2 * m_p_words;
106 BOTAN_ASSERT(windows <= m_W.size() / (3 * elem_size),
"Precomputed sufficient values for scalar mult");
115 std::vector<word> Wt(elem_size);
117 for(
size_t i = 0; i != windows; ++i) {
118 const size_t window = windows - i - 1;
119 const size_t base_addr = (WINDOW_SIZE * window) * elem_size;
121 const word w = scalar.
get_substring(WINDOW_BITS * window, WINDOW_BITS);
131 for(
size_t j = 0; j != elem_size; ++j) {
132 const word w1 = w_is_1.if_set_return(m_W[base_addr + 0 * elem_size + j]);
133 const word w2 = w_is_2.if_set_return(m_W[base_addr + 1 * elem_size + j]);
134 const word w3 = w_is_3.if_set_return(m_W[base_addr + 2 * elem_size + j]);
135 const word w4 = w_is_4.if_set_return(m_W[base_addr + 3 * elem_size + j]);
136 const word w5 = w_is_5.if_set_return(m_W[base_addr + 4 * elem_size + j]);
137 const word w6 = w_is_6.if_set_return(m_W[base_addr + 5 * elem_size + j]);
138 const word w7 = w_is_7.if_set_return(m_W[base_addr + 6 * elem_size + j]);
140 Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
143 R.
add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
163 std::vector<BigInt>& ws) :
164 m_curve(point.get_curve()), m_p_words(m_curve.get_p_words()), m_window_bits(4) {
169 std::vector<EC_Point> U(
static_cast<size_t>(1) << m_window_bits);
173 for(
size_t i = 2; i < U.size(); i += 2) {
175 U[i + 1] = U[i].
plus(point, ws);
181 for(
size_t i = 1; i != U.size(); ++i) {
186 m_T.resize(U.size() * 3 * m_p_words);
189 for(
size_t i = 0; i != U.size(); ++i) {
190 U[i].get_x().encode_words(p, m_p_words);
191 U[i].get_y().encode_words(p + m_p_words, m_p_words);
192 U[i].get_z().encode_words(p + 2 * m_p_words, m_p_words);
199 const BigInt& group_order,
200 std::vector<BigInt>& ws)
const {
202 throw Invalid_Argument(
"EC_Point_Var_Point_Precompute scalar must be positive");
209 const BigInt mask(rng, blinding_size(group_order),
false);
210 const BigInt scalar = k + group_order * mask;
212 const size_t elem_size = 3 * m_p_words;
213 const size_t window_elems =
static_cast<size_t>(1) << m_window_bits;
215 size_t windows =
round_up(scalar.
bits(), m_window_bits) / m_window_bits;
222 const uint32_t w = scalar.
get_substring(windows * m_window_bits, m_window_bits);
225 for(
size_t i = 1; i != window_elems; ++i) {
228 for(
size_t j = 0; j != elem_size; ++j) {
229 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
233 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);
244 R.
mult2i(m_window_bits, ws);
246 const uint32_t w = scalar.
get_substring((windows - 1) * m_window_bits, m_window_bits);
249 for(
size_t i = 1; i != window_elems; ++i) {
252 for(
size_t j = 0; j != elem_size; ++j) {
253 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
257 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);
269 m_M.push_back(x.
zero());
292 m_M.push_back(y.
plus(x, ws));
293 m_M.push_back(y.
plus(x2, ws));
294 m_M.push_back(y.
plus(x3, ws));
297 m_M.push_back(y2.
plus(x, ws));
298 m_M.push_back(y2.
plus(x2, ws));
299 m_M.push_back(y2.
plus(x3, ws));
302 m_M.push_back(y3.
plus(x, ws));
303 m_M.push_back(y3.
plus(x2, ws));
304 m_M.push_back(y3.
plus(x3, ws));
306 bool no_infinity =
true;
307 for(
auto& pt : m_M) {
317 m_no_infinity = no_infinity;
321 if(m_M.size() == 1) {
331 for(
size_t i = 0; i != z_bits; i += 2) {
339 const uint32_t z12 = (4 * z2_b) + z1_b;
346 H.
add(m_M[z12 - 1], ws);
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT(expr, assertion_made)
uint32_t get_substring(size_t offset, size_t length) const
static constexpr Mask< T > is_equal(T x, T y)
EC_Point_Base_Point_Precompute(const EC_Point &base_point, const Modular_Reducer &mod_order)
EC_Point mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
EC_Point_Multi_Point_Precompute(const EC_Point &g1, const EC_Point &g2)
EC_Point multi_exp(const BigInt &k1, const BigInt &k2) const
EC_Point_Var_Point_Precompute(const EC_Point &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
EC_Point mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
void swap(EC_Point &other) noexcept
EC_Point plus(const EC_Point &other, std::vector< BigInt > &workspace) const
void randomize_repr(RandomNumberGenerator &rng)
void add(const EC_Point &other, std::vector< BigInt > &workspace)
void add_affine(const EC_Point &other, std::vector< BigInt > &workspace)
void mult2(std::vector< BigInt > &workspace)
EC_Point double_of(std::vector< BigInt > &workspace) const
void mult2i(size_t i, std::vector< BigInt > &workspace)
bool on_the_curve() const
static void force_all_affine(std::span< EC_Point > points, secure_vector< word > &ws)
const BigInt & get_modulus() const
BigInt reduce(const BigInt &x) const
virtual bool is_seeded() const =0
EC_Point multi_exponentiate(const EC_Point &p1, const BigInt &z1, const EC_Point &p2, const BigInt &z2)
std::vector< T, secure_allocator< T > > secure_vector
constexpr void clear_mem(T *ptr, size_t n)
size_t round_up(size_t n, size_t align_to)