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