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().sig_words()) {
40 const size_t T_bits =
round_up(p_bits + blinding_size(mod_order.
get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
42 std::vector<EC_Point>
T(WINDOW_SIZE * T_bits);
47 for(
size_t i = 0; i != T_bits; i++) {
54 T[7 * i + 1] = std::move(g2);
55 T[7 * i + 2] =
T[7 * i + 1].plus(
T[7 * i + 0], ws);
57 T[7 * i + 4] =
T[7 * i + 3].
plus(
T[7 * i + 0], ws);
58 T[7 * i + 5] =
T[7 * i + 3].
plus(
T[7 * i + 1], ws);
59 T[7 * i + 6] =
T[7 * i + 3].
plus(
T[7 * i + 2], ws);
67 m_W.resize(
T.size() * 2 * m_p_words);
70 for(
size_t i = 0; i !=
T.size(); ++i) {
71 T[i].get_x().encode_words(p, m_p_words);
73 T[i].get_y().encode_words(p, m_p_words);
81 std::vector<BigInt>& ws)
const {
83 throw Invalid_Argument(
"EC_Point_Base_Point_Precompute scalar must be positive");
91 const BigInt mask(rng, blinding_size(group_order));
92 scalar += group_order * mask;
100 scalar += group_order;
101 if(scalar.
bits() == group_order.
bits()) {
102 scalar += group_order;
107 const size_t windows =
round_up(scalar.
bits(), WINDOW_BITS) / WINDOW_BITS;
109 const size_t elem_size = 2 * m_p_words;
111 BOTAN_ASSERT(windows <= m_W.size() / (3 * elem_size),
"Precomputed sufficient values for scalar mult");
120 std::vector<word> Wt(elem_size);
122 for(
size_t i = 0; i != windows; ++i) {
123 const size_t window = windows - i - 1;
124 const size_t base_addr = (WINDOW_SIZE * window) * elem_size;
126 const word w = scalar.
get_substring(WINDOW_BITS * window, WINDOW_BITS);
136 for(
size_t j = 0; j != elem_size; ++j) {
137 const word w1 = w_is_1.if_set_return(m_W[base_addr + 0 * elem_size + j]);
138 const word w2 = w_is_2.if_set_return(m_W[base_addr + 1 * elem_size + j]);
139 const word w3 = w_is_3.if_set_return(m_W[base_addr + 2 * elem_size + j]);
140 const word w4 = w_is_4.if_set_return(m_W[base_addr + 3 * elem_size + j]);
141 const word w5 = w_is_5.if_set_return(m_W[base_addr + 4 * elem_size + j]);
142 const word w6 = w_is_6.if_set_return(m_W[base_addr + 5 * elem_size + j]);
143 const word w7 = w_is_7.if_set_return(m_W[base_addr + 6 * elem_size + j]);
145 Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
148 R.
add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
168 std::vector<BigInt>& ws) :
169 m_curve(point.get_curve()), m_p_words(m_curve.get_p().sig_words()), m_window_bits(4) {
174 std::vector<EC_Point> U(
static_cast<size_t>(1) << m_window_bits);
178 for(
size_t i = 2; i < U.size(); i += 2) {
180 U[i + 1] = U[i].
plus(point, ws);
193 const CurveGFp& curve = U[0].get_curve();
195 const size_t p_bits = curve.
get_p().
bits();
198 for(
size_t i = 1; i != U.size(); ++i) {
203 curve.
sqr(mask2, mask, tmp);
204 curve.
mul(mask3, mask, mask2, tmp);
206 curve.
mul(new_x, U[i].get_x(), mask2, tmp);
207 curve.
mul(new_y, U[i].get_y(), mask3, tmp);
208 curve.
mul(new_z, U[i].get_z(), mask, tmp);
210 U[i].swap_coords(new_x, new_y, new_z);
214 m_T.resize(U.size() * 3 * m_p_words);
217 for(
size_t i = 0; i != U.size(); ++i) {
218 U[i].get_x().encode_words(p, m_p_words);
219 U[i].get_y().encode_words(p + m_p_words, m_p_words);
220 U[i].get_z().encode_words(p + 2 * m_p_words, m_p_words);
227 const BigInt& group_order,
228 std::vector<BigInt>& ws)
const {
230 throw Invalid_Argument(
"EC_Point_Var_Point_Precompute scalar must be positive");
237 const BigInt mask(rng, blinding_size(group_order),
false);
238 const BigInt scalar = k + group_order * mask;
240 const size_t elem_size = 3 * m_p_words;
241 const size_t window_elems =
static_cast<size_t>(1) << m_window_bits;
243 size_t windows =
round_up(scalar.
bits(), m_window_bits) / m_window_bits;
250 const uint32_t w = scalar.
get_substring(windows * m_window_bits, m_window_bits);
253 for(
size_t i = 1; i != window_elems; ++i) {
256 for(
size_t j = 0; j != elem_size; ++j) {
257 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
261 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);
272 R.
mult2i(m_window_bits, ws);
274 const uint32_t w = scalar.
get_substring((windows - 1) * m_window_bits, m_window_bits);
277 for(
size_t i = 1; i != window_elems; ++i) {
280 for(
size_t j = 0; j != elem_size; ++j) {
281 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
285 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);
297 m_M.push_back(x.
zero());
320 m_M.push_back(y.
plus(x, ws));
321 m_M.push_back(y.
plus(x2, ws));
322 m_M.push_back(y.
plus(x3, ws));
325 m_M.push_back(y2.
plus(x, ws));
326 m_M.push_back(y2.
plus(x2, ws));
327 m_M.push_back(y2.
plus(x3, ws));
330 m_M.push_back(y3.
plus(x, ws));
331 m_M.push_back(y3.
plus(x2, ws));
332 m_M.push_back(y3.
plus(x3, ws));
334 bool no_infinity =
true;
335 for(
auto& pt : m_M) {
345 m_no_infinity = no_infinity;
349 if(m_M.size() == 1) {
359 for(
size_t i = 0; i != z_bits; i += 2) {
367 const uint32_t z12 = (4 * z2_b) + z1_b;
374 H.
add(m_M[z12 - 1], ws);
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT(expr, assertion_made)
secure_vector< word > & get_word_vector()
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
uint32_t get_substring(size_t offset, size_t length) const
static Mask< T > is_equal(T x, T y)
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
const BigInt & get_p() const
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
EC_Point plus(const EC_Point &other, std::vector< BigInt > &workspace) const
void swap(EC_Point &other)
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
const CurveGFp & get_curve() const
static void force_all_affine(std::vector< 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)