Botan 2.19.3
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#include <iostream>
13
14namespace Botan {
15
16namespace {
17
18size_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];
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 = static_cast<size_t>(1) << 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
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}
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:123
#define BOTAN_UNUSED(...)
Definition assert.h:142
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:55
secure_vector< word > & get_word_vector()
Definition bigint.h:625
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:430
size_t bits() const
Definition bigint.cpp:296
bool is_negative() const
Definition bigint.h:527
uint32_t get_substring(size_t offset, size_t length) const
Definition bigint.cpp:213
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
Definition point_mul.cpp:32
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
Definition point_mul.cpp:48
static Mask< T > is_equal(T x, T y)
Definition ct_utils.h:149
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
const BigInt & get_modulus() const
Definition reducer.h:21
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:37
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
PointGFp_Base_Point_Precompute(const PointGFp &base_point, const Modular_Reducer &mod_order)
Definition point_mul.cpp:54
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
void mult2(std::vector< BigInt > &workspace)
void randomize_repr(RandomNumberGenerator &rng)
Definition point_gfp.cpp:43
PointGFp zero() const
Definition point_gfp.h:319
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition point_gfp.h:309
PointGFp & negate()
Definition point_gfp.h:137
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition point_gfp.h:254
void mult2i(size_t i, std::vector< BigInt > &workspace)
bool on_the_curve() const
void swap(PointGFp &other)
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition point_gfp.h:297
const CurveGFp & get_curve() const
Definition point_gfp.h:327
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition point_gfp.h:221
virtual bool is_seeded() const =0
fe T
Definition ge.cpp:37
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition point_mul.cpp:25
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:65
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