7#include <botan/internal/point_mul.h>
9#include <botan/reducer.h>
10#include <botan/internal/rounding.h>
11#include <botan/internal/ct_utils.h>
17size_t blinding_size(
const BigInt& group_order)
19 return (group_order.bits() + 1) / 2;
34 m_mod_order(mod_order),
35 m_p_words(base.get_curve().get_p().sig_words())
46 const size_t T_bits =
round_up(p_bits + blinding_size(mod_order.
get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
48 std::vector<EC_Point>
T(WINDOW_SIZE*T_bits);
53 for(
size_t i = 0; i != T_bits; i++)
61 T[7*i+1] = std::move(g2);
62 T[7*i+2] =
T[7*i+1].plus(
T[7*i+0], ws);
64 T[7*i+4] =
T[7*i+3].plus(
T[7*i+0], ws);
65 T[7*i+5] =
T[7*i+3].plus(
T[7*i+1], ws);
66 T[7*i+6] =
T[7*i+3].plus(
T[7*i+2], ws);
74 m_W.resize(
T.size() * 2 * m_p_words);
77 for(
size_t i = 0; i !=
T.size(); ++i)
79 T[i].get_x().encode_words(p, m_p_words);
81 T[i].get_y().encode_words(p, m_p_words);
89 std::vector<BigInt>& ws)
const
92 throw Invalid_Argument(
"EC_Point_Base_Point_Precompute scalar must be positive");
100 const BigInt mask(rng, blinding_size(group_order));
101 scalar += group_order * mask;
111 scalar += group_order;
112 if(scalar.
bits() == group_order.
bits())
113 scalar += group_order;
117 const size_t windows =
round_up(scalar.
bits(), WINDOW_BITS) / WINDOW_BITS;
119 const size_t elem_size = 2*m_p_words;
122 "Precomputed sufficient values for scalar mult");
130 std::vector<word> Wt(elem_size);
132 for(
size_t i = 0; i != windows; ++i)
134 const size_t window = windows - i - 1;
135 const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
137 const word w = scalar.
get_substring(WINDOW_BITS*window, WINDOW_BITS);
147 for(
size_t j = 0; j != elem_size; ++j)
149 const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
150 const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
151 const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
152 const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
153 const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
154 const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
155 const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
157 Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
160 R.
add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
181 std::vector<BigInt>& ws) :
182 m_curve(point.get_curve()),
183 m_p_words(m_curve.get_p().sig_words()),
189 std::vector<EC_Point> U(
static_cast<size_t>(1) << m_window_bits);
193 for(
size_t i = 2; i < U.size(); i += 2)
196 U[i+1] = U[i].
plus(point, ws);
210 const CurveGFp& curve = U[0].get_curve();
212 const size_t p_bits = curve.
get_p().
bits();
215 for(
size_t i = 1; i != U.size(); ++i)
221 curve.
sqr(mask2, mask, tmp);
222 curve.
mul(mask3, mask, mask2, tmp);
224 curve.
mul(new_x, U[i].get_x(), mask2, tmp);
225 curve.
mul(new_y, U[i].get_y(), mask3, tmp);
226 curve.
mul(new_z, U[i].get_z(), mask, tmp);
228 U[i].swap_coords(new_x, new_y, new_z);
232 m_T.resize(U.size() * 3 * m_p_words);
235 for(
size_t i = 0; i != U.size(); ++i)
237 U[i].get_x().encode_words(p , m_p_words);
238 U[i].get_y().encode_words(p + m_p_words, m_p_words);
239 U[i].get_z().encode_words(p + 2*m_p_words, m_p_words);
246 const BigInt& group_order,
247 std::vector<BigInt>& ws)
const
250 throw Invalid_Argument(
"EC_Point_Var_Point_Precompute scalar must be positive");
255 const BigInt mask(rng, blinding_size(group_order),
false);
256 const BigInt scalar = k + group_order * mask;
258 const size_t elem_size = 3*m_p_words;
259 const size_t window_elems =
static_cast<size_t>(1) << m_window_bits;
261 size_t windows =
round_up(scalar.
bits(), m_window_bits) / m_window_bits;
269 const uint32_t w = scalar.
get_substring(windows*m_window_bits, m_window_bits);
272 for(
size_t i = 1; i != window_elems; ++i)
276 for(
size_t j = 0; j != elem_size; ++j)
278 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
282 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
294 R.
mult2i(m_window_bits, ws);
296 const uint32_t w = scalar.
get_substring((windows-1)*m_window_bits, m_window_bits);
299 for(
size_t i = 1; i != window_elems; ++i)
303 for(
size_t j = 0; j != elem_size; ++j)
305 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
309 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
325 m_M.push_back(x.
zero());
348 m_M.push_back(
y.plus(x, ws));
349 m_M.push_back(
y.plus(x2, ws));
350 m_M.push_back(
y.plus(x3, ws));
353 m_M.push_back(y2.
plus(x, ws));
354 m_M.push_back(y2.
plus(x2, ws));
355 m_M.push_back(y2.
plus(x3, ws));
358 m_M.push_back(y3.
plus(x, ws));
359 m_M.push_back(y3.
plus(x2, ws));
360 m_M.push_back(y3.
plus(x3, ws));
362 bool no_infinity =
true;
374 m_no_infinity = no_infinity;
389 for(
size_t i = 0; i != z_bits; i += 2)
399 const uint32_t z12 = (4*z2_b) + z1_b;
407 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)