/src/botan/src/lib/pubkey/ec_group/point_mul.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | size_t blinding_size(const BigInt& group_order) |
18 | 53.8k | { |
19 | 53.8k | return (group_order.bits() + 1) / 2; |
20 | 53.8k | } |
21 | | |
22 | | } |
23 | | |
24 | | PointGFp multi_exponentiate(const PointGFp& x, const BigInt& z1, |
25 | | const PointGFp& y, const BigInt& z2) |
26 | 0 | { |
27 | 0 | PointGFp_Multi_Point_Precompute xy_mul(x, y); |
28 | 0 | return xy_mul.multi_exp(z1, z2); |
29 | 0 | } |
30 | | |
31 | | PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base, |
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 | 1.47k | { |
37 | 1.47k | std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); |
38 | | |
39 | 1.47k | 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 | 1.47k | const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS; |
47 | | |
48 | 1.47k | std::vector<PointGFp> T(WINDOW_SIZE*T_bits); |
49 | | |
50 | 1.47k | PointGFp g = base; |
51 | 1.47k | PointGFp g2, g4; |
52 | | |
53 | 204k | for(size_t i = 0; i != T_bits; i++) |
54 | 203k | { |
55 | 203k | g2 = g; |
56 | 203k | g2.mult2(ws); |
57 | 203k | g4 = g2; |
58 | 203k | g4.mult2(ws); |
59 | | |
60 | 203k | T[7*i+0] = g; |
61 | 203k | T[7*i+1] = std::move(g2); |
62 | 203k | T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g |
63 | 203k | T[7*i+3] = g4; |
64 | 203k | T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g |
65 | 203k | T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2 |
66 | 203k | T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g |
67 | | |
68 | 203k | g.swap(g4); |
69 | 203k | g.mult2(ws); |
70 | 203k | } |
71 | | |
72 | 1.47k | PointGFp::force_all_affine(T, ws[0].get_word_vector()); |
73 | | |
74 | 1.47k | m_W.resize(T.size() * 2 * m_p_words); |
75 | | |
76 | 1.47k | word* p = &m_W[0]; |
77 | 1.40M | for(size_t i = 0; i != T.size(); ++i) |
78 | 1.40M | { |
79 | 1.40M | T[i].get_x().encode_words(p, m_p_words); |
80 | 1.40M | p += m_p_words; |
81 | 1.40M | T[i].get_y().encode_words(p, m_p_words); |
82 | 1.40M | p += m_p_words; |
83 | 1.40M | } |
84 | 1.47k | } |
85 | | |
86 | | PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k, |
87 | | RandomNumberGenerator& rng, |
88 | | const BigInt& group_order, |
89 | | std::vector<BigInt>& ws) const |
90 | 32.5k | { |
91 | 32.5k | if(k.is_negative()) |
92 | 0 | 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 | 32.5k | BigInt scalar = m_mod_order.reduce(k); |
96 | | |
97 | 32.5k | if(rng.is_seeded()) |
98 | 32.5k | { |
99 | | // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure) |
100 | 32.5k | const BigInt mask(rng, blinding_size(group_order)); |
101 | 32.5k | scalar += group_order * mask; |
102 | 32.5k | } |
103 | 0 | else |
104 | 0 | { |
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 | 0 | scalar += group_order; |
112 | 0 | if(scalar.bits() == group_order.bits()) |
113 | 0 | scalar += group_order; |
114 | 0 | BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1); |
115 | 0 | } |
116 | | |
117 | 32.5k | const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS; |
118 | | |
119 | 32.5k | const size_t elem_size = 2*m_p_words; |
120 | | |
121 | 32.5k | BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size), |
122 | 32.5k | "Precomputed sufficient values for scalar mult"); |
123 | | |
124 | 32.5k | PointGFp R = m_base_point.zero(); |
125 | | |
126 | 32.5k | if(ws.size() < PointGFp::WORKSPACE_SIZE) |
127 | 21.9k | ws.resize(PointGFp::WORKSPACE_SIZE); |
128 | | |
129 | | // the precomputed multiples are not secret so use std::vector |
130 | 32.5k | std::vector<word> Wt(elem_size); |
131 | | |
132 | 6.98M | for(size_t i = 0; i != windows; ++i) |
133 | 6.95M | { |
134 | 6.95M | const size_t window = windows - i - 1; |
135 | 6.95M | const size_t base_addr = (WINDOW_SIZE*window)*elem_size; |
136 | | |
137 | 6.95M | const word w = scalar.get_substring(WINDOW_BITS*window, WINDOW_BITS); |
138 | | |
139 | 6.95M | const auto w_is_1 = CT::Mask<word>::is_equal(w, 1); |
140 | 6.95M | const auto w_is_2 = CT::Mask<word>::is_equal(w, 2); |
141 | 6.95M | const auto w_is_3 = CT::Mask<word>::is_equal(w, 3); |
142 | 6.95M | const auto w_is_4 = CT::Mask<word>::is_equal(w, 4); |
143 | 6.95M | const auto w_is_5 = CT::Mask<word>::is_equal(w, 5); |
144 | 6.95M | const auto w_is_6 = CT::Mask<word>::is_equal(w, 6); |
145 | 6.95M | const auto w_is_7 = CT::Mask<word>::is_equal(w, 7); |
146 | | |
147 | 112M | for(size_t j = 0; j != elem_size; ++j) |
148 | 105M | { |
149 | 105M | const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]); |
150 | 105M | const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]); |
151 | 105M | const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]); |
152 | 105M | const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]); |
153 | 105M | const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]); |
154 | 105M | const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]); |
155 | 105M | const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]); |
156 | | |
157 | 105M | Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7; |
158 | 105M | } |
159 | | |
160 | 6.95M | R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws); |
161 | | |
162 | 6.95M | if(i == 0 && rng.is_seeded()) |
163 | 32.5k | { |
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 | 32.5k | BOTAN_DEBUG_ASSERT(w != 0); |
170 | 32.5k | R.randomize_repr(rng, ws[0].get_word_vector()); |
171 | 32.5k | } |
172 | 6.95M | } |
173 | | |
174 | 32.5k | BOTAN_DEBUG_ASSERT(R.on_the_curve()); |
175 | | |
176 | 32.5k | return R; |
177 | 32.5k | } |
178 | | |
179 | | PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& point, |
180 | | RandomNumberGenerator& rng, |
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 | 19.9k | { |
186 | 19.9k | if(ws.size() < PointGFp::WORKSPACE_SIZE) |
187 | 7.43k | ws.resize(PointGFp::WORKSPACE_SIZE); |
188 | | |
189 | 19.9k | std::vector<PointGFp> U(static_cast<size_t>(1) << m_window_bits); |
190 | 19.9k | U[0] = point.zero(); |
191 | 19.9k | U[1] = point; |
192 | | |
193 | 159k | for(size_t i = 2; i < U.size(); i += 2) |
194 | 139k | { |
195 | 139k | U[i] = U[i/2].double_of(ws); |
196 | 139k | U[i+1] = U[i].plus(point, ws); |
197 | 139k | } |
198 | | |
199 | | // Hack to handle Blinded_Point_Multiply |
200 | 19.9k | if(rng.is_seeded()) |
201 | 19.9k | { |
202 | 19.9k | BigInt& mask = ws[0]; |
203 | 19.9k | BigInt& mask2 = ws[1]; |
204 | 19.9k | BigInt& mask3 = ws[2]; |
205 | 19.9k | BigInt& new_x = ws[3]; |
206 | 19.9k | BigInt& new_y = ws[4]; |
207 | 19.9k | BigInt& new_z = ws[5]; |
208 | 19.9k | secure_vector<word>& tmp = ws[6].get_word_vector(); |
209 | | |
210 | 19.9k | const CurveGFp& curve = U[0].get_curve(); |
211 | | |
212 | 19.9k | const size_t p_bits = curve.get_p().bits(); |
213 | | |
214 | | // Skipping zero point since it can't be randomized |
215 | 318k | for(size_t i = 1; i != U.size(); ++i) |
216 | 298k | { |
217 | 298k | mask.randomize(rng, p_bits - 1, false); |
218 | | // Easy way of ensuring mask != 0 |
219 | 298k | mask.set_bit(0); |
220 | | |
221 | 298k | curve.sqr(mask2, mask, tmp); |
222 | 298k | curve.mul(mask3, mask, mask2, tmp); |
223 | | |
224 | 298k | curve.mul(new_x, U[i].get_x(), mask2, tmp); |
225 | 298k | curve.mul(new_y, U[i].get_y(), mask3, tmp); |
226 | 298k | curve.mul(new_z, U[i].get_z(), mask, tmp); |
227 | | |
228 | 298k | U[i].swap_coords(new_x, new_y, new_z); |
229 | 298k | } |
230 | 19.9k | } |
231 | | |
232 | 19.9k | m_T.resize(U.size() * 3 * m_p_words); |
233 | | |
234 | 19.9k | word* p = &m_T[0]; |
235 | 338k | for(size_t i = 0; i != U.size(); ++i) |
236 | 318k | { |
237 | 318k | U[i].get_x().encode_words(p , m_p_words); |
238 | 318k | U[i].get_y().encode_words(p + m_p_words, m_p_words); |
239 | 318k | U[i].get_z().encode_words(p + 2*m_p_words, m_p_words); |
240 | 318k | p += 3*m_p_words; |
241 | 318k | } |
242 | 19.9k | } |
243 | | |
244 | | PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k, |
245 | | RandomNumberGenerator& rng, |
246 | | const BigInt& group_order, |
247 | | std::vector<BigInt>& ws) const |
248 | 19.9k | { |
249 | 19.9k | if(k.is_negative()) |
250 | 0 | throw Invalid_Argument("PointGFp_Var_Point_Precompute scalar must be positive"); |
251 | 19.9k | if(ws.size() < PointGFp::WORKSPACE_SIZE) |
252 | 0 | ws.resize(PointGFp::WORKSPACE_SIZE); |
253 | | |
254 | | // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure) |
255 | 19.9k | const BigInt mask(rng, blinding_size(group_order), false); |
256 | 19.9k | const BigInt scalar = k + group_order * mask; |
257 | | |
258 | 19.9k | const size_t elem_size = 3*m_p_words; |
259 | 19.9k | const size_t window_elems = static_cast<size_t>(1) << m_window_bits; |
260 | | |
261 | 19.9k | size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits; |
262 | 19.9k | PointGFp R(m_curve); |
263 | 19.9k | secure_vector<word> e(elem_size); |
264 | | |
265 | 19.9k | if(windows > 0) |
266 | 19.9k | { |
267 | 19.9k | windows--; |
268 | | |
269 | 19.9k | const uint32_t w = scalar.get_substring(windows*m_window_bits, m_window_bits); |
270 | | |
271 | 19.9k | clear_mem(e.data(), e.size()); |
272 | 318k | for(size_t i = 1; i != window_elems; ++i) |
273 | 298k | { |
274 | 298k | const auto wmask = CT::Mask<word>::is_equal(w, i); |
275 | | |
276 | 6.20M | for(size_t j = 0; j != elem_size; ++j) |
277 | 5.90M | { |
278 | 5.90M | e[j] |= wmask.if_set_return(m_T[i * elem_size + j]); |
279 | 5.90M | } |
280 | 298k | } |
281 | | |
282 | 19.9k | 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 | 19.9k | R.randomize_repr(rng, ws[0].get_word_vector()); |
290 | 19.9k | } |
291 | | |
292 | 3.00M | while(windows) |
293 | 2.98M | { |
294 | 2.98M | R.mult2i(m_window_bits, ws); |
295 | | |
296 | 2.98M | const uint32_t w = scalar.get_substring((windows-1)*m_window_bits, m_window_bits); |
297 | | |
298 | 2.98M | clear_mem(e.data(), e.size()); |
299 | 47.7M | for(size_t i = 1; i != window_elems; ++i) |
300 | 44.7M | { |
301 | 44.7M | const auto wmask = CT::Mask<word>::is_equal(w, i); |
302 | | |
303 | 1.01G | for(size_t j = 0; j != elem_size; ++j) |
304 | 968M | { |
305 | 968M | e[j] |= wmask.if_set_return(m_T[i * elem_size + j]); |
306 | 968M | } |
307 | 44.7M | } |
308 | | |
309 | 2.98M | 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 | 2.98M | windows--; |
312 | 2.98M | } |
313 | | |
314 | 19.9k | BOTAN_DEBUG_ASSERT(R.on_the_curve()); |
315 | | |
316 | 19.9k | return R; |
317 | 19.9k | } |
318 | | |
319 | | |
320 | | PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute(const PointGFp& x, |
321 | | const PointGFp& y) |
322 | 274 | { |
323 | 274 | if(x.on_the_curve() == false || y.on_the_curve() == false) |
324 | 0 | { |
325 | 0 | m_M.push_back(x.zero()); |
326 | 0 | return; |
327 | 0 | } |
328 | | |
329 | 274 | std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); |
330 | | |
331 | 274 | PointGFp x2 = x; |
332 | 274 | x2.mult2(ws); |
333 | | |
334 | 274 | const PointGFp x3(x2.plus(x, ws)); |
335 | | |
336 | 274 | PointGFp y2 = y; |
337 | 274 | y2.mult2(ws); |
338 | | |
339 | 274 | const PointGFp y3(y2.plus(y, ws)); |
340 | | |
341 | 274 | m_M.reserve(15); |
342 | | |
343 | 274 | m_M.push_back(x); |
344 | 274 | m_M.push_back(x2); |
345 | 274 | m_M.push_back(x3); |
346 | | |
347 | 274 | m_M.push_back(y); |
348 | 274 | m_M.push_back(y.plus(x, ws)); |
349 | 274 | m_M.push_back(y.plus(x2, ws)); |
350 | 274 | m_M.push_back(y.plus(x3, ws)); |
351 | | |
352 | 274 | m_M.push_back(y2); |
353 | 274 | m_M.push_back(y2.plus(x, ws)); |
354 | 274 | m_M.push_back(y2.plus(x2, ws)); |
355 | 274 | m_M.push_back(y2.plus(x3, ws)); |
356 | | |
357 | 274 | m_M.push_back(y3); |
358 | 274 | m_M.push_back(y3.plus(x, ws)); |
359 | 274 | m_M.push_back(y3.plus(x2, ws)); |
360 | 274 | m_M.push_back(y3.plus(x3, ws)); |
361 | | |
362 | 274 | bool no_infinity = true; |
363 | 274 | for(auto& pt : m_M) |
364 | 4.11k | { |
365 | 4.11k | if(pt.is_zero()) |
366 | 285 | no_infinity = false; |
367 | 4.11k | } |
368 | | |
369 | 274 | if(no_infinity) |
370 | 179 | { |
371 | 179 | PointGFp::force_all_affine(m_M, ws[0].get_word_vector()); |
372 | 179 | } |
373 | | |
374 | 274 | m_no_infinity = no_infinity; |
375 | 274 | } |
376 | | |
377 | | PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1, |
378 | | const BigInt& z2) const |
379 | 196 | { |
380 | 196 | if(m_M.size() == 1) |
381 | 0 | return m_M[0]; |
382 | | |
383 | 196 | std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE); |
384 | | |
385 | 196 | const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2); |
386 | | |
387 | 196 | PointGFp H = m_M[0].zero(); |
388 | | |
389 | 34.4k | for(size_t i = 0; i != z_bits; i += 2) |
390 | 34.2k | { |
391 | 34.2k | if(i > 0) |
392 | 34.0k | { |
393 | 34.0k | H.mult2i(2, ws); |
394 | 34.0k | } |
395 | | |
396 | 34.2k | const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2); |
397 | 34.2k | const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2); |
398 | | |
399 | 34.2k | const uint32_t z12 = (4*z2_b) + z1_b; |
400 | | |
401 | | // This function is not intended to be const time |
402 | 34.2k | if(z12) |
403 | 28.1k | { |
404 | 28.1k | if(m_no_infinity) |
405 | 15.8k | H.add_affine(m_M[z12-1], ws); |
406 | 12.3k | else |
407 | 12.3k | H.add(m_M[z12-1], ws); |
408 | 28.1k | } |
409 | 34.2k | } |
410 | | |
411 | 196 | if(z1.is_negative() != z2.is_negative()) |
412 | 0 | H.negate(); |
413 | | |
414 | 196 | return H; |
415 | 196 | } |
416 | | |
417 | | } |