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