Botan  2.10.0
Crypto and TLS for C++11
point_mul.cpp
Go to the documentation of this file.
1 /*
2 * (C) 2015,2018 Jack Lloyd
3 *
4 * Botan is released under the Simplified BSD License (see license.txt)
5 */
6 
7 #include <botan/internal/point_mul.h>
8 #include <botan/rng.h>
9 #include <botan/reducer.h>
10 #include <botan/internal/rounding.h>
11 #include <botan/internal/ct_utils.h>
12 
13 namespace Botan {
14 
16  const PointGFp& y, const BigInt& z2)
17  {
19  return xy_mul.multi_exp(z1, z2);
20  }
21 
23  const BigInt& order,
24  size_t h) :
25  m_ws(PointGFp::WORKSPACE_SIZE),
26  m_order(order)
27  {
28  BOTAN_UNUSED(h);
29  Null_RNG null_rng;
30  m_point_mul.reset(new PointGFp_Var_Point_Precompute(base, null_rng, m_ws));
31  }
32 
34  {
35  /* for ~unique_ptr */
36  }
37 
40  {
41  return m_point_mul->mul(scalar, rng, m_order, m_ws);
42  }
43 
45  const Modular_Reducer& mod_order) :
46  m_base_point(base),
47  m_mod_order(mod_order),
48  m_p_words(base.get_curve().get_p().sig_words()),
49  m_T_size(base.get_curve().get_p().bits() + PointGFp_SCALAR_BLINDING_BITS + 1)
50  {
51  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
52 
53  const size_t p_bits = base.get_curve().get_p().bits();
54 
55  /*
56  * Some of the curves (eg secp160k1) have an order slightly larger than
57  * the size of the prime modulus. In all cases they are at most 1 bit
58  * longer. The +1 compensates for this.
59  */
60  const size_t T_bits = round_up(p_bits + PointGFp_SCALAR_BLINDING_BITS + 1, WINDOW_BITS) / WINDOW_BITS;
61 
62  std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
63 
64  PointGFp g = base;
65  PointGFp g2, g4;
66 
67  for(size_t i = 0; i != T_bits; i++)
68  {
69  g2 = g;
70  g2.mult2(ws);
71  g4 = g2;
72  g4.mult2(ws);
73 
74  T[7*i+0] = g;
75  T[7*i+1] = std::move(g2);
76  T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g
77  T[7*i+3] = g4;
78  T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g
79  T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2
80  T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g
81 
82  g.swap(g4);
83  g.mult2(ws);
84  }
85 
86  PointGFp::force_all_affine(T, ws[0].get_word_vector());
87 
88  m_W.resize(T.size() * 2 * m_p_words);
89 
90  word* p = &m_W[0];
91  for(size_t i = 0; i != T.size(); ++i)
92  {
93  T[i].get_x().encode_words(p, m_p_words);
94  p += m_p_words;
95  T[i].get_y().encode_words(p, m_p_words);
96  p += m_p_words;
97  }
98  }
99 
102  const BigInt& group_order,
103  std::vector<BigInt>& ws) const
104  {
105  if(k.is_negative())
106  throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
107 
108  // Instead of reducing k mod group order should we alter the mask size??
109  BigInt scalar = m_mod_order.reduce(k);
110 
111  if(rng.is_seeded())
112  {
113  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
114  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS);
115  scalar += group_order * mask;
116  }
117  else
118  {
119  /*
120  When we don't have an RNG we cannot do scalar blinding. Instead use the
121  same trick as OpenSSL and add one or two copies of the order to normalize
122  the length of the scalar at order.bits()+1. This at least ensures the loop
123  bound does not leak information about the high bits of the scalar.
124  */
125  scalar += group_order;
126  if(scalar.bits() == group_order.bits())
127  scalar += group_order;
128  BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
129  }
130 
131  const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
132 
133  const size_t elem_size = 2*m_p_words;
134 
135  BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
136  "Precomputed sufficient values for scalar mult");
137 
138  PointGFp R = m_base_point.zero();
139 
140  if(ws.size() < PointGFp::WORKSPACE_SIZE)
141  ws.resize(PointGFp::WORKSPACE_SIZE);
142 
143  // the precomputed multiples are not secret so use std::vector
144  std::vector<word> Wt(elem_size);
145 
146  for(size_t i = 0; i != windows; ++i)
147  {
148  const size_t window = windows - i - 1;
149  const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
150 
151  const word w = scalar.get_substring(WINDOW_BITS*window, WINDOW_BITS);
152 
153  const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
154  const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
155  const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
156  const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
157  const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
158  const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
159  const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
160 
161  for(size_t j = 0; j != elem_size; ++j)
162  {
163  const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
164  const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
165  const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
166  const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
167  const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
168  const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
169  const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
170 
171  Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
172  }
173 
174  R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
175 
176  if(i == 0 && rng.is_seeded())
177  {
178  /*
179  * Since we start with the top bit of the exponent we know the
180  * first window must have a non-zero element, and thus R is
181  * now a point other than the point at infinity.
182  */
183  BOTAN_DEBUG_ASSERT(w != 0);
184  R.randomize_repr(rng, ws[0].get_word_vector());
185  }
186  }
187 
189 
190  return R;
191  }
192 
195  std::vector<BigInt>& ws) :
196  m_curve(point.get_curve()),
197  m_p_words(m_curve.get_p().sig_words()),
198  m_window_bits(4)
199  {
200  if(ws.size() < PointGFp::WORKSPACE_SIZE)
201  ws.resize(PointGFp::WORKSPACE_SIZE);
202 
203  std::vector<PointGFp> U(static_cast<size_t>(1) << m_window_bits);
204  U[0] = point.zero();
205  U[1] = point;
206 
207  for(size_t i = 2; i < U.size(); i += 2)
208  {
209  U[i] = U[i/2].double_of(ws);
210  U[i+1] = U[i].plus(point, ws);
211  }
212 
213  // Hack to handle Blinded_Point_Multiply
214  if(rng.is_seeded())
215  {
216  BigInt& mask = ws[0];
217  BigInt& mask2 = ws[1];
218  BigInt& mask3 = ws[2];
219  BigInt& new_x = ws[3];
220  BigInt& new_y = ws[4];
221  BigInt& new_z = ws[5];
222  secure_vector<word>& tmp = ws[6].get_word_vector();
223 
224  const CurveGFp& curve = U[0].get_curve();
225 
226  const size_t p_bits = curve.get_p().bits();
227 
228  // Skipping zero point since it can't be randomized
229  for(size_t i = 1; i != U.size(); ++i)
230  {
231  mask.randomize(rng, p_bits - 1, false);
232  // Easy way of ensuring mask != 0
233  mask.set_bit(0);
234 
235  curve.sqr(mask2, mask, tmp);
236  curve.mul(mask3, mask, mask2, tmp);
237 
238  curve.mul(new_x, U[i].get_x(), mask2, tmp);
239  curve.mul(new_y, U[i].get_y(), mask3, tmp);
240  curve.mul(new_z, U[i].get_z(), mask, tmp);
241 
242  U[i].swap_coords(new_x, new_y, new_z);
243  }
244  }
245 
246  m_T.resize(U.size() * 3 * m_p_words);
247 
248  word* p = &m_T[0];
249  for(size_t i = 0; i != U.size(); ++i)
250  {
251  U[i].get_x().encode_words(p , m_p_words);
252  U[i].get_y().encode_words(p + m_p_words, m_p_words);
253  U[i].get_z().encode_words(p + 2*m_p_words, m_p_words);
254  p += 3*m_p_words;
255  }
256  }
257 
260  const BigInt& group_order,
261  std::vector<BigInt>& ws) const
262  {
263  if(k.is_negative())
264  throw Invalid_Argument("PointGFp_Var_Point_Precompute scalar must be positive");
265  if(ws.size() < PointGFp::WORKSPACE_SIZE)
266  ws.resize(PointGFp::WORKSPACE_SIZE);
267 
268  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
269  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
270  const BigInt scalar = k + group_order * mask;
271 
272  const size_t elem_size = 3*m_p_words;
273  const size_t window_elems = (1ULL << m_window_bits);
274 
275  size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;
276  PointGFp R(m_curve);
277  secure_vector<word> e(elem_size);
278 
279  if(windows > 0)
280  {
281  windows--;
282 
283  const uint32_t w = scalar.get_substring(windows*m_window_bits, m_window_bits);
284 
285  clear_mem(e.data(), e.size());
286  for(size_t i = 1; i != window_elems; ++i)
287  {
288  const auto wmask = CT::Mask<word>::is_equal(w, i);
289 
290  for(size_t j = 0; j != elem_size; ++j)
291  {
292  e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
293  }
294  }
295 
296  R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
297 
298  /*
299  Randomize after adding the first nibble as before the addition R
300  is zero, and we cannot effectively randomize the point
301  representation of the zero point.
302  */
303  R.randomize_repr(rng, ws[0].get_word_vector());
304  }
305 
306  while(windows)
307  {
308  R.mult2i(m_window_bits, ws);
309 
310  const uint32_t w = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
311 
312  clear_mem(e.data(), e.size());
313  for(size_t i = 1; i != window_elems; ++i)
314  {
315  const auto wmask = CT::Mask<word>::is_equal(w, i);
316 
317  for(size_t j = 0; j != elem_size; ++j)
318  {
319  e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
320  }
321  }
322 
323  R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
324 
325  windows--;
326  }
327 
328  BOTAN_DEBUG_ASSERT(R.on_the_curve());
329 
330  return R;
331  }
332 
333 
335  const PointGFp& y)
336  {
337  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
338 
339  PointGFp x2 = x;
340  x2.mult2(ws);
341 
342  const PointGFp x3(x2.plus(x, ws));
343 
344  PointGFp y2 = y;
345  y2.mult2(ws);
346 
347  const PointGFp y3(y2.plus(y, ws));
348 
349  m_M.reserve(15);
350 
351  m_M.push_back(x);
352  m_M.push_back(x2);
353  m_M.push_back(x3);
354 
355  m_M.push_back(y);
356  m_M.push_back(y.plus(x, ws));
357  m_M.push_back(y.plus(x2, ws));
358  m_M.push_back(y.plus(x3, ws));
359 
360  m_M.push_back(y2);
361  m_M.push_back(y2.plus(x, ws));
362  m_M.push_back(y2.plus(x2, ws));
363  m_M.push_back(y2.plus(x3, ws));
364 
365  m_M.push_back(y3);
366  m_M.push_back(y3.plus(x, ws));
367  m_M.push_back(y3.plus(x2, ws));
368  m_M.push_back(y3.plus(x3, ws));
369 
370  PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
371  }
372 
374  const BigInt& z2) const
375  {
376  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
377 
378  const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
379 
380  PointGFp H = m_M[0].zero();
381 
382  for(size_t i = 0; i != z_bits; i += 2)
383  {
384  if(i > 0)
385  {
386  H.mult2i(2, ws);
387  }
388 
389  const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
390  const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);
391 
392  const uint32_t z12 = (4*z2_b) + z1_b;
393 
394  // This function is not intended to be const time
395  if(z12)
396  {
397  H.add_affine(m_M[z12-1], ws);
398  }
399  }
400 
401  if(z1.is_negative() != z2.is_negative())
402  H.negate();
403 
404  return H;
405  }
406 
407 }
bool is_negative() const
Definition: bigint.h:530
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
Definition: point_mul.cpp:373
size_t bits() const
Definition: bigint.cpp:281
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
Definition: point_mul.cpp:334
void set_bit(size_t n)
Definition: bigint.h:429
secure_vector< word > & get_word_vector()
Definition: bigint.h:628
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:172
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:207
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
void swap(PointGFp &other)
Definition: point_gfp.cpp:573
PointGFp_Base_Point_Precompute(const PointGFp &base_point, const Modular_Reducer &mod_order)
Definition: point_mul.cpp:44
PointGFp zero() const
Definition: point_gfp.h:318
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:43
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:259
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
Definition: point_mul.cpp:38
PointGFp & negate()
Definition: point_gfp.h:136
Definition: alg_id.cpp:13
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:296
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
#define BOTAN_UNUSED(...)
Definition: assert.h:142
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:100
bool on_the_curve() const
Definition: point_gfp.cpp:538
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:308
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:253
virtual bool is_seeded() const =0
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:420
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
fe T
Definition: ge.cpp:37
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:258
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
const CurveGFp & get_curve() const
Definition: point_gfp.h:326
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
Definition: point_mul.cpp:22
const BigInt & get_p() const
Definition: curve_gfp.h:131
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_mul.cpp:15
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:183
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
Definition: point_mul.cpp:193