Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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