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>
18size_t blinding_size(
const BigInt& group_order)
20 return (group_order.bits() + 1) / 2;
51 return m_point_mul->mul(scalar, rng, m_order, m_ws);
57 m_mod_order(mod_order),
58 m_p_words(base.get_curve().get_p().sig_words())
69 const size_t T_bits =
round_up(p_bits + blinding_size(mod_order.
get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
71 std::vector<PointGFp>
T(WINDOW_SIZE*T_bits);
76 for(
size_t i = 0; i != T_bits; i++)
84 T[7*i+1] = std::move(g2);
85 T[7*i+2] =
T[7*i+1].plus(
T[7*i+0], ws);
87 T[7*i+4] =
T[7*i+3].
plus(
T[7*i+0], ws);
88 T[7*i+5] =
T[7*i+3].
plus(
T[7*i+1], ws);
89 T[7*i+6] =
T[7*i+3].
plus(
T[7*i+2], ws);
97 m_W.resize(
T.size() * 2 * m_p_words);
100 for(
size_t i = 0; i !=
T.size(); ++i)
102 T[i].get_x().encode_words(p, m_p_words);
104 T[i].get_y().encode_words(p, m_p_words);
111 const BigInt& group_order,
112 std::vector<BigInt>& ws)
const
115 throw Invalid_Argument(
"PointGFp_Base_Point_Precompute scalar must be positive");
123 const BigInt mask(rng, blinding_size(group_order));
124 scalar += group_order * mask;
134 scalar += group_order;
135 if(scalar.
bits() == group_order.
bits())
136 scalar += group_order;
140 const size_t windows =
round_up(scalar.
bits(), WINDOW_BITS) / WINDOW_BITS;
142 const size_t elem_size = 2*m_p_words;
145 "Precomputed sufficient values for scalar mult");
153 std::vector<word> Wt(elem_size);
155 for(
size_t i = 0; i != windows; ++i)
157 const size_t window = windows - i - 1;
158 const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
160 const word w = scalar.
get_substring(WINDOW_BITS*window, WINDOW_BITS);
170 for(
size_t j = 0; j != elem_size; ++j)
172 const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
173 const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
174 const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
175 const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
176 const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
177 const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
178 const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
180 Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
183 R.
add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
204 std::vector<BigInt>& ws) :
205 m_curve(point.get_curve()),
206 m_p_words(m_curve.get_p().sig_words()),
212 std::vector<PointGFp> U(
static_cast<size_t>(1) << m_window_bits);
216 for(
size_t i = 2; i < U.size(); i += 2)
219 U[i+1] = U[i].
plus(point, ws);
233 const CurveGFp& curve = U[0].get_curve();
235 const size_t p_bits = curve.
get_p().
bits();
238 for(
size_t i = 1; i != U.size(); ++i)
244 curve.
sqr(mask2, mask, tmp);
245 curve.
mul(mask3, mask, mask2, tmp);
247 curve.
mul(new_x, U[i].get_x(), mask2, tmp);
248 curve.
mul(new_y, U[i].get_y(), mask3, tmp);
249 curve.
mul(new_z, U[i].get_z(), mask, tmp);
251 U[i].swap_coords(new_x, new_y, new_z);
255 m_T.resize(U.size() * 3 * m_p_words);
258 for(
size_t i = 0; i != U.size(); ++i)
260 U[i].get_x().encode_words(p , m_p_words);
261 U[i].get_y().encode_words(p + m_p_words, m_p_words);
262 U[i].get_z().encode_words(p + 2*m_p_words, m_p_words);
269 const BigInt& group_order,
270 std::vector<BigInt>& ws)
const
273 throw Invalid_Argument(
"PointGFp_Var_Point_Precompute scalar must be positive");
278 const BigInt mask(rng, blinding_size(group_order),
false);
279 const BigInt scalar = k + group_order * mask;
281 const size_t elem_size = 3*m_p_words;
282 const size_t window_elems =
static_cast<size_t>(1) << m_window_bits;
284 size_t windows =
round_up(scalar.
bits(), m_window_bits) / m_window_bits;
292 const uint32_t w = scalar.
get_substring(windows*m_window_bits, m_window_bits);
295 for(
size_t i = 1; i != window_elems; ++i)
299 for(
size_t j = 0; j != elem_size; ++j)
301 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
305 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
317 R.
mult2i(m_window_bits, ws);
319 const uint32_t w = scalar.
get_substring((windows-1)*m_window_bits, m_window_bits);
322 for(
size_t i = 1; i != window_elems; ++i)
326 for(
size_t j = 0; j != elem_size; ++j)
328 e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
332 R.
add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
365 m_M.push_back(y.
plus(x, ws));
366 m_M.push_back(y.
plus(x2, ws));
367 m_M.push_back(y.
plus(x3, ws));
370 m_M.push_back(y2.
plus(x, ws));
371 m_M.push_back(y2.
plus(x2, ws));
372 m_M.push_back(y2.
plus(x3, ws));
375 m_M.push_back(y3.
plus(x, ws));
376 m_M.push_back(y3.
plus(x2, ws));
377 m_M.push_back(y3.
plus(x3, ws));
379 bool no_infinity =
true;
391 m_no_infinity = no_infinity;
403 for(
size_t i = 0; i != z_bits; i += 2)
413 const uint32_t z12 = (4*z2_b) + z1_b;
421 H.
add(m_M[z12-1], ws);
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_UNUSED(...)
#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
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
~Blinded_Point_Multiply()
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
const BigInt & get_modulus() const
BigInt reduce(const BigInt &x) const
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
PointGFp_Base_Point_Precompute(const PointGFp &base_point, const Modular_Reducer &mod_order)
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
void mult2(std::vector< BigInt > &workspace)
void randomize_repr(RandomNumberGenerator &rng)
PointGFp double_of(std::vector< BigInt > &workspace) const
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
void mult2i(size_t i, std::vector< BigInt > &workspace)
bool on_the_curve() const
void swap(PointGFp &other)
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
const CurveGFp & get_curve() const
void add(const PointGFp &other, std::vector< BigInt > &workspace)
virtual bool is_seeded() const =0
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
std::vector< T, secure_allocator< T > > secure_vector
void clear_mem(T *ptr, size_t n)
size_t round_up(size_t n, size_t align_to)