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