Botan 2.19.5 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
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
25 PointGFp multi_exponentiate(const PointGFp& x, const BigInt& z1,
26 const PointGFp& y, const BigInt& z2)
27 {
28 PointGFp_Multi_Point_Precompute xy_mul(x, y);
29 return xy_mul.multi_exp(z1, z2);
30 }
31
32 Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base,
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
43 Blinded_Point_Multiply::~Blinded_Point_Multiply()
44 {
45 /* for ~unique_ptr */
46 }
47
48 PointGFp Blinded_Point_Multiply::blinded_multiply(const BigInt& scalar,
49 RandomNumberGenerator& rng)
50 {
51 return m_point_mul->mul(scalar, rng, m_order, m_ws);
52 }
53
54 PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base,
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
109 PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
110 RandomNumberGenerator& rng,
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
197 BOTAN_DEBUG_ASSERT(R.on_the_curve());
198
199 return R;
200 }
201
202 PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& point,
203 RandomNumberGenerator& rng,
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
267 PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
268 RandomNumberGenerator& rng,
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
337 BOTAN_DEBUG_ASSERT(R.on_the_curve());
338
339 return R;
340 }
341
342
343 PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute(const PointGFp& x,
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
394 PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
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}
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BOTAN_UNUSED
#define BOTAN_UNUSED(...)
Definition: assert.h:142
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
Botan::BigInt
Definition: bigint.h:25
Botan::BigInt::get_word_vector
secure_vector< word > & get_word_vector()
Definition: bigint.h:631
Botan::BigInt::randomize
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
Botan::BigInt::set_bit
void set_bit(size_t n)
Definition: bigint.h:436
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:304
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:533
Botan::BigInt::get_substring
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:221
Botan::Blinded_Point_Multiply::Blinded_Point_Multiply
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
Definition: point_mul.cpp:32
Botan::Blinded_Point_Multiply::blinded_multiply
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
Definition: point_mul.cpp:48
Botan::Blinded_Point_Multiply::~Blinded_Point_Multiply
~Blinded_Point_Multiply()
Definition: point_mul.cpp:43
Botan::CT::Mask::is_equal
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
Botan::CurveGFp
Definition: curve_gfp.h:97
Botan::CurveGFp::mul
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:175
Botan::CurveGFp::sqr
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:186
Botan::CurveGFp::get_p
const BigInt & get_p() const
Definition: curve_gfp.h:134
Botan::Invalid_Argument
Definition: exceptn.h:137
Botan::Modular_Reducer
Definition: reducer.h:19
Botan::Modular_Reducer::get_modulus
const BigInt & get_modulus() const
Definition: reducer.h:21
Botan::Modular_Reducer::reduce
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
Botan::Null_RNG
Definition: rng.h:207
Botan::PointGFp_Base_Point_Precompute::mul
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:109
Botan::PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute
PointGFp_Base_Point_Precompute(const PointGFp &base_point, const Modular_Reducer &mod_order)
Definition: point_mul.cpp:54
Botan::PointGFp_Multi_Point_Precompute
Definition: point_mul.h:67
Botan::PointGFp_Multi_Point_Precompute::multi_exp
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
Definition: point_mul.cpp:394
Botan::PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
Definition: point_mul.cpp:343
Botan::PointGFp_Var_Point_Precompute
Definition: point_mul.h:42
Botan::PointGFp_Var_Point_Precompute::mul
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:267
Botan::PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
Definition: point_mul.cpp:202
Botan::PointGFp
Definition: point_gfp.h:48
Botan::PointGFp::mult2
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
Botan::PointGFp::randomize_repr
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:43
Botan::PointGFp::zero
PointGFp zero() const
Definition: point_gfp.h:319
Botan::PointGFp::double_of
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:309
Botan::PointGFp::WORKSPACE_SIZE
@ WORKSPACE_SIZE
Definition: point_gfp.h:56
Botan::PointGFp::negate
PointGFp & negate()
Definition: point_gfp.h:137
Botan::PointGFp::force_all_affine
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:420
Botan::PointGFp::add_affine
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:254
Botan::PointGFp::mult2i
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:259
Botan::PointGFp::on_the_curve
bool on_the_curve() const
Definition: point_gfp.cpp:544
Botan::PointGFp::swap
void swap(PointGFp &other)
Definition: point_gfp.cpp:579
Botan::PointGFp::plus
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:297
Botan::PointGFp::get_curve
const CurveGFp & get_curve() const
Definition: point_gfp.h:327
Botan::PointGFp::add
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:221
Botan::RandomNumberGenerator
Definition: rng.h:26
Botan::RandomNumberGenerator::is_seeded
virtual bool is_seeded() const =0
T
fe T
Definition: ge.cpp:37
Botan
Definition: alg_id.cpp:13
Botan::multi_exponentiate
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_mul.cpp:25
Botan::secure_vector
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
Botan::round_up
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21