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