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