Botan 3.0.0-alpha0
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 PointGFp& 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(PointGFp::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<PointGFp> T(WINDOW_SIZE*T_bits);
49
50 PointGFp g = base;
51 PointGFp 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 PointGFp::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("PointGFp_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 PointGFp R = m_base_point.zero();
125
126 if(ws.size() < PointGFp::WORKSPACE_SIZE)
127 ws.resize(PointGFp::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() < PointGFp::WORKSPACE_SIZE)
187 ws.resize(PointGFp::WORKSPACE_SIZE);
188
189 std::vector<PointGFp> 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("PointGFp_Var_Point_Precompute scalar must be positive");
251 if(ws.size() < PointGFp::WORKSPACE_SIZE)
252 ws.resize(PointGFp::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 PointGFp 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 PointGFp& 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(PointGFp::WORKSPACE_SIZE);
330
331 PointGFp x2 = x;
332 x2.mult2(ws);
333
334 const PointGFp x3(x2.plus(x, ws));
335
336 PointGFp y2 = y;
337 y2.mult2(ws);
338
339 const PointGFp 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 PointGFp::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(PointGFp::WORKSPACE_SIZE);
384
385 const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
386
387 PointGFp 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}
#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:639
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:439
size_t bits() const
Definition: bigint.cpp:309
bool is_negative() const
Definition: bigint.h:541
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:236
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
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:86
PointGFp_Base_Point_Precompute(const PointGFp &base_point, const Modular_Reducer &mod_order)
Definition: point_mul.cpp:31
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
Definition: point_mul.cpp:377
PointGFp_Multi_Point_Precompute(const PointGFp &g1, const PointGFp &g2)
Definition: point_mul.cpp:320
PointGFp mul(const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
Definition: point_mul.cpp:244
PointGFp_Var_Point_Precompute(const PointGFp &point, RandomNumberGenerator &rng, std::vector< BigInt > &ws)
Definition: point_mul.cpp:179
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:278
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:42
PointGFp zero() const
Definition: point_gfp.h:294
PointGFp double_of(std::vector< BigInt > &workspace) const
Definition: point_gfp.h:284
PointGFp & negate()
Definition: point_gfp.h:112
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:419
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:229
void mult2i(size_t i, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:258
bool on_the_curve() const
Definition: point_gfp.cpp:543
void swap(PointGFp &other)
Definition: point_gfp.cpp:578
PointGFp plus(const PointGFp &other, std::vector< BigInt > &workspace) const
Definition: point_gfp.h:272
const CurveGFp & get_curve() const
Definition: point_gfp.h:302
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:196
virtual bool is_seeded() const =0
fe T
Definition: ge.cpp:36
Definition: alg_id.cpp:13
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_mul.cpp:24
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
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