Botan 2.19.1
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 = (1ULL << 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
Definition: point_mul.cpp:109
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
Definition: point_mul.cpp:394
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
Definition: point_mul.cpp:343
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:267
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
Definition: point_mul.cpp:202
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
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)
Definition: point_gfp.cpp:420
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:254
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:259
bool on_the_curve() const
Definition: point_gfp.cpp:544
void swap(PointGFp &other)
Definition: point_gfp.cpp:579
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
Definition: alg_id.cpp:13
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