Botan  2.6.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 
12 namespace Botan {
13 
15  const PointGFp& y, const BigInt& z2)
16  {
18  return xy_mul.multi_exp(z1, z2);
19  }
20 
22  const BigInt& order,
23  size_t h) :
24  m_ws(PointGFp::WORKSPACE_SIZE),
25  m_order(order)
26  {
27  BOTAN_UNUSED(h);
28  m_point_mul.reset(new PointGFp_Var_Point_Precompute(base));
29  }
30 
32  {
33  /* for ~unique_ptr */
34  }
35 
38  {
39  return m_point_mul->mul(scalar, rng, m_order, m_ws);
40  }
41 
43  const Modular_Reducer& mod_order) :
44  m_base_point(base),
45  m_mod_order(mod_order),
46  m_p_words(base.get_curve().get_p().size()),
47  m_T_size(base.get_curve().get_p().bits() + PointGFp_SCALAR_BLINDING_BITS + 1)
48  {
49  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
50 
51  const size_t p_bits = base.get_curve().get_p().bits();
52 
53  /*
54  * Some of the curves (eg secp160k1) have an order slightly larger than
55  * the size of the prime modulus. In all cases they are at most 1 bit
56  * longer. The +1 compensates for this.
57  */
58  const size_t T_bits = round_up(p_bits + PointGFp_SCALAR_BLINDING_BITS + 1, 2) / 2;
59 
60  std::vector<PointGFp> T(3*T_bits);
61  T.resize(3*T_bits);
62 
63  T[0] = base;
64  T[1] = T[0];
65  T[1].mult2(ws);
66  T[2] = T[1];
67  T[2].add(T[0], ws);
68 
69  for(size_t i = 1; i != T_bits; ++i)
70  {
71  T[3*i+0] = T[3*i - 2];
72  T[3*i+0].mult2(ws);
73  T[3*i+1] = T[3*i+0];
74  T[3*i+1].mult2(ws);
75  T[3*i+2] = T[3*i+1];
76  T[3*i+2].add(T[3*i+0], ws);
77  }
78 
79  PointGFp::force_all_affine(T, ws[0].get_word_vector());
80 
81  m_W.resize(T.size() * 2 * m_p_words);
82 
83  word* p = &m_W[0];
84  for(size_t i = 0; i != T.size(); ++i)
85  {
86  T[i].get_x().encode_words(p, m_p_words);
87  p += m_p_words;
88  T[i].get_y().encode_words(p, m_p_words);
89  p += m_p_words;
90  }
91  }
92 
95  const BigInt& group_order,
96  std::vector<BigInt>& ws) const
97  {
98  if(k.is_negative())
99  throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
100 
101  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
102  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
103 
104  // Instead of reducing k mod group order should we alter the mask size??
105  const BigInt scalar = m_mod_order.reduce(k) + group_order * mask;
106 
107  size_t windows = round_up(scalar.bits(), 2) / 2;
108 
109  BOTAN_ASSERT(windows <= m_W.size() / (3*2*m_p_words),
110  "Precomputed sufficient values for scalar mult");
111 
112  PointGFp R = m_base_point.zero();
113 
114  if(ws.size() < PointGFp::WORKSPACE_SIZE)
115  ws.resize(PointGFp::WORKSPACE_SIZE);
116 
117  for(size_t i = 0; i != windows; ++i)
118  {
119  if(i == 4)
120  {
121  R.randomize_repr(rng, ws[0].get_word_vector());
122  }
123 
124  const uint32_t w = scalar.get_substring(2*i, 2);
125 
126  if(w > 0)
127  {
128  const size_t idx = (3*i + w - 1)*2*m_p_words;
129  R.add_affine(&m_W[idx], m_p_words,
130  &m_W[idx + m_p_words], m_p_words, ws);
131  }
132  }
133 
135 
136  return R;
137  }
138 
140  {
141  m_window_bits = 4;
142 
143  m_U.resize(1U << m_window_bits);
144  m_U[0] = point.zero();
145  m_U[1] = point;
146 
147  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
148  for(size_t i = 2; i < m_U.size(); ++i)
149  {
150  m_U[i] = m_U[i-1];
151  m_U[i].add(point, ws);
152  }
153  }
154 
156  {
157  for(size_t i = 1; i != m_U.size(); ++i)
158  m_U[i].randomize_repr(rng);
159  }
160 
163  const BigInt& group_order,
164  std::vector<BigInt>& ws) const
165  {
166  if(k.is_negative())
167  throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
168  if(ws.size() < PointGFp::WORKSPACE_SIZE)
169  ws.resize(PointGFp::WORKSPACE_SIZE);
170 
171  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
172  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
173  const BigInt scalar = k + group_order * mask;
174 
175  const size_t scalar_bits = scalar.bits();
176 
177  size_t windows = round_up(scalar_bits, m_window_bits) / m_window_bits;
178 
179  PointGFp R = m_U[0];
180 
181  if(windows > 0)
182  {
183  windows--;
184  const uint32_t nibble = scalar.get_substring(windows*m_window_bits, m_window_bits);
185  R.add(m_U[nibble], ws);
186 
187  /*
188  Randomize after adding the first nibble as before the addition R
189  is zero, and we cannot effectively randomize the point
190  representation of the zero point.
191  */
192  R.randomize_repr(rng);
193 
194  while(windows)
195  {
196  for(size_t i = 0; i != m_window_bits; ++i)
197  R.mult2(ws);
198 
199  const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
200  // cache side channel here, we are relying on blinding...
201  R.add(m_U[inner_nibble], ws);
202  windows--;
203  }
204  }
205 
207 
208  return R;
209  }
210 
211 
213  const PointGFp& y)
214  {
215  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
216 
217  PointGFp x2 = x;
218  x2.mult2(ws);
219 
220  const PointGFp x3(x2.plus(x, ws));
221 
222  PointGFp y2 = y;
223  y2.mult2(ws);
224 
225  const PointGFp y3(y2.plus(y, ws));
226 
227  m_M.reserve(15);
228 
229  m_M.push_back(x);
230  m_M.push_back(x2);
231  m_M.push_back(x3);
232 
233  m_M.push_back(y);
234  m_M.push_back(y.plus(x, ws));
235  m_M.push_back(y.plus(x2, ws));
236  m_M.push_back(y.plus(x3, ws));
237 
238  m_M.push_back(y2);
239  m_M.push_back(y2.plus(x, ws));
240  m_M.push_back(y2.plus(x2, ws));
241  m_M.push_back(y2.plus(x3, ws));
242 
243  m_M.push_back(y3);
244  m_M.push_back(y3.plus(x, ws));
245  m_M.push_back(y3.plus(x2, ws));
246  m_M.push_back(y3.plus(x3, ws));
247 
248  PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
249  }
250 
252  const BigInt& z2) const
253  {
254  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
255 
256  const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
257 
258  PointGFp H = m_M[0].zero();
259 
260  for(size_t i = 0; i != z_bits; i += 2)
261  {
262  if(i > 0)
263  {
264  H.mult2(ws);
265  H.mult2(ws);
266  }
267 
268  const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2);
269  const uint8_t z2_b = z2.get_substring(z_bits - i - 2, 2);
270 
271  const uint8_t z12 = (4*z2_b) + z1_b;
272 
273  if(z12)
274  {
275  H.add_affine(m_M[z12-1], ws);
276  }
277  }
278 
279  if(z1.is_negative() != z2.is_negative())
280  H.negate();
281 
282  return H;
283  }
284 
285 }
PointGFp_Var_Point_Precompute(const PointGFp &point)
Definition: point_mul.cpp:139
bool is_negative() const
Definition: bigint.h:413
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
Definition: point_mul.cpp:251
size_t bits() const
Definition: bigint.cpp:216
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
Definition: point_mul.cpp:212
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:152
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:195
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:30
PointGFp_Base_Point_Precompute(const PointGFp &base_point, const Modular_Reducer &mod_order)
Definition: point_mul.cpp:42
PointGFp zero() const
Definition: point_gfp.h:254
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:98
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:46
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
Definition: point_mul.cpp:36
PointGFp & negate()
Definition: point_gfp.h:132
Definition: alg_id.cpp:13
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:244
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:288
#define BOTAN_UNUSED(...)
Definition: assert.h:117
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:93
bool on_the_curve() const
Definition: point_gfp.cpp:530
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:92
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:409
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:31
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:161
const CurveGFp & get_curve() const
Definition: point_gfp.h:262
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
Definition: point_mul.cpp:21
const BigInt & get_p() const
Definition: curve_gfp.h:109
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_mul.cpp:155
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:14