Botan  2.7.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, 2) / 2;
61 
62  std::vector<PointGFp> T(3*T_bits);
63  T.resize(3*T_bits);
64 
65  T[0] = base;
66  T[1] = T[0];
67  T[1].mult2(ws);
68  T[2] = T[1];
69  T[2].add(T[0], ws);
70 
71  for(size_t i = 1; i != T_bits; ++i)
72  {
73  T[3*i+0] = T[3*i - 2];
74  T[3*i+0].mult2(ws);
75  T[3*i+1] = T[3*i+0];
76  T[3*i+1].mult2(ws);
77  T[3*i+2] = T[3*i+1];
78  T[3*i+2].add(T[3*i+0], ws);
79  }
80 
81  PointGFp::force_all_affine(T, ws[0].get_word_vector());
82 
83  m_W.resize(T.size() * 2 * m_p_words);
84 
85  word* p = &m_W[0];
86  for(size_t i = 0; i != T.size(); ++i)
87  {
88  T[i].get_x().encode_words(p, m_p_words);
89  p += m_p_words;
90  T[i].get_y().encode_words(p, m_p_words);
91  p += m_p_words;
92  }
93  }
94 
97  const BigInt& group_order,
98  std::vector<BigInt>& ws) const
99  {
100  if(k.is_negative())
101  throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
102 
103  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
104  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS);
105 
106  // Instead of reducing k mod group order should we alter the mask size??
107  const BigInt scalar = m_mod_order.reduce(k) + group_order * mask;
108 
109  const size_t windows = round_up(scalar.bits(), 2) / 2;
110 
111  const size_t elem_size = 2*m_p_words;
112 
113  BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
114  "Precomputed sufficient values for scalar mult");
115 
116  PointGFp R = m_base_point.zero();
117 
118  if(ws.size() < PointGFp::WORKSPACE_SIZE)
119  ws.resize(PointGFp::WORKSPACE_SIZE);
120 
121  // the precomputed multiples are not secret so use std::vector
122  std::vector<word> Wt(elem_size);
123 
124  for(size_t i = 0; i != windows; ++i)
125  {
126  const size_t window = windows - i - 1;
127  const size_t base_addr = (3*window)*elem_size;
128 
129  const word w = scalar.get_substring(2*window, 2);
130 
131  const word w_is_1 = CT::is_equal<word>(w, 1);
132  const word w_is_2 = CT::is_equal<word>(w, 2);
133  const word w_is_3 = CT::is_equal<word>(w, 3);
134 
135  for(size_t j = 0; j != elem_size; ++j)
136  {
137  const word w1 = m_W[base_addr + 0*elem_size + j];
138  const word w2 = m_W[base_addr + 1*elem_size + j];
139  const word w3 = m_W[base_addr + 2*elem_size + j];
140 
141  Wt[j] = CT::select3<word>(w_is_1, w1, w_is_2, w2, w_is_3, w3, 0);
142  }
143 
144  R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
145 
146  if(i == 0)
147  {
148  /*
149  * Since we start with the top bit of the exponent we know the
150  * first window must have a non-zero element, and thus R is
151  * now a point other than the point at infinity.
152  */
153  BOTAN_DEBUG_ASSERT(w != 0);
154  R.randomize_repr(rng, ws[0].get_word_vector());
155  }
156  }
157 
159 
160  return R;
161  }
162 
165  std::vector<BigInt>& ws) :
166  m_curve(point.get_curve()),
167  m_p_words(m_curve.get_p().sig_words()),
168  m_window_bits(4)
169  {
170  if(ws.size() < PointGFp::WORKSPACE_SIZE)
171  ws.resize(PointGFp::WORKSPACE_SIZE);
172 
173  std::vector<PointGFp> U(1U << m_window_bits);
174  U[0] = point.zero();
175  U[1] = point;
176 
177  for(size_t i = 2; i < U.size(); i += 2)
178  {
179  U[i] = U[i/2].double_of(ws);
180  U[i+1] = U[i].plus(point, ws);
181  }
182 
183  // Hack to handle Blinded_Point_Multiply
184  if(rng.is_seeded())
185  {
186  BigInt& mask = ws[0];
187  BigInt& mask2 = ws[1];
188  BigInt& mask3 = ws[2];
189  BigInt& new_x = ws[3];
190  BigInt& new_y = ws[4];
191  BigInt& new_z = ws[5];
192  secure_vector<word>& tmp = ws[6].get_word_vector();
193 
194  const CurveGFp& curve = U[0].get_curve();
195 
196  const size_t p_bits = curve.get_p().bits();
197 
198  // Skipping zero point since it can't be randomized
199  for(size_t i = 1; i != U.size(); ++i)
200  {
201  mask.randomize(rng, p_bits - 1, false);
202  // Easy way of ensuring mask != 0
203  mask.set_bit(0);
204 
205  curve.sqr(mask2, mask, tmp);
206  curve.mul(mask3, mask, mask2, tmp);
207 
208  curve.mul(new_x, U[i].get_x(), mask2, tmp);
209  curve.mul(new_y, U[i].get_y(), mask3, tmp);
210  curve.mul(new_z, U[i].get_z(), mask, tmp);
211 
212  U[i].swap_coords(new_x, new_y, new_z);
213  }
214  }
215 
216  m_T.resize(U.size() * 3 * m_p_words);
217 
218  word* p = &m_T[0];
219  for(size_t i = 0; i != U.size(); ++i)
220  {
221  U[i].get_x().encode_words(p , m_p_words);
222  U[i].get_y().encode_words(p + m_p_words, m_p_words);
223  U[i].get_z().encode_words(p + 2*m_p_words, m_p_words);
224  p += 3*m_p_words;
225  }
226  }
227 
230  const BigInt& group_order,
231  std::vector<BigInt>& ws) const
232  {
233  if(k.is_negative())
234  throw Invalid_Argument("PointGFp_Var_Point_Precompute scalar must be positive");
235  if(ws.size() < PointGFp::WORKSPACE_SIZE)
236  ws.resize(PointGFp::WORKSPACE_SIZE);
237 
238  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
239  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
240  const BigInt scalar = k + group_order * mask;
241 
242  const size_t elem_size = 3*m_p_words;
243  const size_t window_elems = (1ULL << m_window_bits);
244 
245  size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;
246  PointGFp R(m_curve);
247  secure_vector<word> e(elem_size);
248 
249  if(windows > 0)
250  {
251  windows--;
252 
253  const uint32_t w = scalar.get_substring(windows*m_window_bits, m_window_bits);
254 
255  clear_mem(e.data(), e.size());
256  for(size_t i = 1; i != window_elems; ++i)
257  {
258  const word wmask = CT::is_equal<word>(w, i);
259 
260  for(size_t j = 0; j != elem_size; ++j)
261  {
262  e[j] |= wmask & m_T[i * elem_size + j];
263  }
264  }
265 
266  R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
267 
268  /*
269  Randomize after adding the first nibble as before the addition R
270  is zero, and we cannot effectively randomize the point
271  representation of the zero point.
272  */
273  R.randomize_repr(rng, ws[0].get_word_vector());
274  }
275 
276  while(windows)
277  {
278  R.mult2i(m_window_bits, ws);
279 
280  const uint32_t w = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
281 
282  clear_mem(e.data(), e.size());
283  for(size_t i = 1; i != window_elems; ++i)
284  {
285  const word wmask = CT::is_equal<word>(w, i);
286 
287  for(size_t j = 0; j != elem_size; ++j)
288  e[j] |= wmask & m_T[i * elem_size + j];
289  }
290 
291  R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
292 
293  windows--;
294  }
295 
296  BOTAN_DEBUG_ASSERT(R.on_the_curve());
297 
298  return R;
299  }
300 
301 
303  const PointGFp& y)
304  {
305  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
306 
307  PointGFp x2 = x;
308  x2.mult2(ws);
309 
310  const PointGFp x3(x2.plus(x, ws));
311 
312  PointGFp y2 = y;
313  y2.mult2(ws);
314 
315  const PointGFp y3(y2.plus(y, ws));
316 
317  m_M.reserve(15);
318 
319  m_M.push_back(x);
320  m_M.push_back(x2);
321  m_M.push_back(x3);
322 
323  m_M.push_back(y);
324  m_M.push_back(y.plus(x, ws));
325  m_M.push_back(y.plus(x2, ws));
326  m_M.push_back(y.plus(x3, ws));
327 
328  m_M.push_back(y2);
329  m_M.push_back(y2.plus(x, ws));
330  m_M.push_back(y2.plus(x2, ws));
331  m_M.push_back(y2.plus(x3, ws));
332 
333  m_M.push_back(y3);
334  m_M.push_back(y3.plus(x, ws));
335  m_M.push_back(y3.plus(x2, ws));
336  m_M.push_back(y3.plus(x3, ws));
337 
338  PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
339  }
340 
342  const BigInt& z2) const
343  {
344  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
345 
346  const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
347 
348  PointGFp H = m_M[0].zero();
349 
350  for(size_t i = 0; i != z_bits; i += 2)
351  {
352  if(i > 0)
353  {
354  H.mult2i(2, ws);
355  }
356 
357  const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2);
358  const uint8_t z2_b = z2.get_substring(z_bits - i - 2, 2);
359 
360  const uint8_t z12 = (4*z2_b) + z1_b;
361 
362  // This function is not intended to be const time
363  if(z12)
364  {
365  H.add_affine(m_M[z12-1], ws);
366  }
367  }
368 
369  if(z1.is_negative() != z2.is_negative())
370  H.negate();
371 
372  return H;
373  }
374 
375 }
bool is_negative() const
Definition: bigint.h:460
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
Definition: point_mul.cpp:341
size_t bits() const
Definition: bigint.cpp:228
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:97
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
Definition: point_mul.cpp:302
void set_bit(size_t n)
Definition: bigint.cpp:201
secure_vector< word > & get_word_vector()
Definition: bigint.h:553
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:179
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:164
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:43
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:316
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:111
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:42
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:256
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
Definition: point_mul.cpp:38
PointGFp & negate()
Definition: point_gfp.h:133
Definition: alg_id.cpp:13
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:294
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:276
#define BOTAN_UNUSED(...)
Definition: assert.h:130
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:95
bool on_the_curve() const
Definition: point_gfp.cpp:540
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:306
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:251
virtual bool is_seeded() const =0
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:422
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:38
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:228
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
const CurveGFp & get_curve() const
Definition: point_gfp.h:324
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:133
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
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:190
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
Definition: point_mul.cpp:163