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