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