/src/botan/src/lib/pubkey/ec_group/curve_gfp.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Elliptic curves over GF(p) Montgomery Representation |
3 | | * (C) 2014,2015,2018 Jack Lloyd |
4 | | * 2016 Matthias Gierlings |
5 | | * |
6 | | * Botan is released under the Simplified BSD License (see license.txt) |
7 | | */ |
8 | | |
9 | | #include <botan/curve_gfp.h> |
10 | | #include <botan/internal/curve_nistp.h> |
11 | | #include <botan/numthry.h> |
12 | | #include <botan/reducer.h> |
13 | | #include <botan/internal/mp_core.h> |
14 | | #include <botan/internal/mp_asmi.h> |
15 | | #include <botan/internal/monty.h> |
16 | | |
17 | | namespace Botan { |
18 | | |
19 | | namespace { |
20 | | |
21 | | class CurveGFp_Montgomery final : public CurveGFp_Repr |
22 | | { |
23 | | public: |
24 | | CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) : |
25 | | m_p(p), m_a(a), m_b(b), |
26 | | m_p_words(m_p.sig_words()), |
27 | | m_p_dash(monty_inverse(m_p.word_at(0))) |
28 | 659 | { |
29 | 659 | Modular_Reducer mod_p(m_p); |
30 | | |
31 | 659 | m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS); |
32 | 659 | m_r = mod_p.reduce(m_r); |
33 | | |
34 | 659 | m_r2 = mod_p.square(m_r); |
35 | 659 | m_r3 = mod_p.multiply(m_r, m_r2); |
36 | 659 | m_a_r = mod_p.multiply(m_r, m_a); |
37 | 659 | m_b_r = mod_p.multiply(m_r, m_b); |
38 | | |
39 | 659 | m_a_is_zero = m_a.is_zero(); |
40 | 659 | m_a_is_minus_3 = (m_a + 3 == m_p); |
41 | 659 | } |
42 | | |
43 | 3.65M | bool a_is_zero() const override { return m_a_is_zero; } |
44 | 3.49M | bool a_is_minus_3() const override { return m_a_is_minus_3; } |
45 | | |
46 | 8.08k | const BigInt& get_a() const override { return m_a; } |
47 | | |
48 | 8.08k | const BigInt& get_b() const override { return m_b; } |
49 | | |
50 | 6.40M | const BigInt& get_p() const override { return m_p; } |
51 | | |
52 | 3.46M | const BigInt& get_a_rep() const override { return m_a_r; } |
53 | | |
54 | 20.7k | const BigInt& get_b_rep() const override { return m_b_r; } |
55 | | |
56 | 48.5k | const BigInt& get_1_rep() const override { return m_r; } |
57 | | |
58 | 46.5k | bool is_one(const BigInt& x) const override { return x == m_r; } |
59 | | |
60 | 415k | size_t get_p_words() const override { return m_p_words; } |
61 | | |
62 | 81.8M | size_t get_ws_size() const override { return 2*m_p_words + 4; } |
63 | | |
64 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
65 | | |
66 | | void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override; |
67 | | |
68 | | void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override; |
69 | | |
70 | | void curve_mul_words(BigInt& z, |
71 | | const word x_words[], |
72 | | const size_t x_size, |
73 | | const BigInt& y, |
74 | | secure_vector<word>& ws) const override; |
75 | | |
76 | | void curve_sqr_words(BigInt& z, |
77 | | const word x_words[], |
78 | | size_t x_size, |
79 | | secure_vector<word>& ws) const override; |
80 | | |
81 | | private: |
82 | | BigInt m_p; |
83 | | BigInt m_a, m_b; |
84 | | BigInt m_a_r, m_b_r; |
85 | | size_t m_p_words; // cache of m_p.sig_words() |
86 | | |
87 | | // Montgomery parameters |
88 | | BigInt m_r, m_r2, m_r3; |
89 | | word m_p_dash; |
90 | | |
91 | | bool m_a_is_zero; |
92 | | bool m_a_is_minus_3; |
93 | | }; |
94 | | |
95 | | BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const |
96 | 46.5k | { |
97 | | // Should we use Montgomery inverse instead? |
98 | 46.5k | const BigInt inv = inverse_mod(x, m_p); |
99 | 46.5k | BigInt res; |
100 | 46.5k | curve_mul(res, inv, m_r3, ws); |
101 | 46.5k | return res; |
102 | 46.5k | } |
103 | | |
104 | | void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const |
105 | 11.6k | { |
106 | 11.6k | const BigInt tx = x; |
107 | 11.6k | curve_mul(x, tx, m_r2, ws); |
108 | 11.6k | } |
109 | | |
110 | | void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const |
111 | 82.9k | { |
112 | 82.9k | if(ws.size() < get_ws_size()) |
113 | 680 | ws.resize(get_ws_size()); |
114 | | |
115 | 82.9k | const size_t output_size = 2*m_p_words + 2; |
116 | 82.9k | if(z.size() < output_size) |
117 | 20.2k | z.grow_to(output_size); |
118 | | |
119 | 82.9k | bigint_monty_redc(z.mutable_data(), |
120 | 82.9k | m_p.data(), m_p_words, m_p_dash, |
121 | 82.9k | ws.data(), ws.size()); |
122 | 82.9k | } |
123 | | |
124 | | void CurveGFp_Montgomery::curve_mul_words(BigInt& z, |
125 | | const word x_w[], |
126 | | size_t x_size, |
127 | | const BigInt& y, |
128 | | secure_vector<word>& ws) const |
129 | 43.8M | { |
130 | 43.8M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
131 | | |
132 | 43.8M | if(ws.size() < get_ws_size()) |
133 | 0 | ws.resize(get_ws_size()); |
134 | | |
135 | 43.8M | const size_t output_size = 2*m_p_words + 2; |
136 | 43.8M | if(z.size() < output_size) |
137 | 2.00M | z.grow_to(output_size); |
138 | | |
139 | 43.8M | bigint_mul(z.mutable_data(), z.size(), |
140 | 43.8M | x_w, x_size, std::min(m_p_words, x_size), |
141 | 43.8M | y.data(), y.size(), std::min(m_p_words, y.size()), |
142 | 43.8M | ws.data(), ws.size()); |
143 | | |
144 | 43.8M | bigint_monty_redc(z.mutable_data(), |
145 | 43.8M | m_p.data(), m_p_words, m_p_dash, |
146 | 43.8M | ws.data(), ws.size()); |
147 | 43.8M | } |
148 | | |
149 | | void CurveGFp_Montgomery::curve_sqr_words(BigInt& z, |
150 | | const word x[], |
151 | | size_t x_size, |
152 | | secure_vector<word>& ws) const |
153 | 31.4M | { |
154 | 31.4M | if(ws.size() < get_ws_size()) |
155 | 74.9k | ws.resize(get_ws_size()); |
156 | | |
157 | 31.4M | const size_t output_size = 2*m_p_words + 2; |
158 | 31.4M | if(z.size() < output_size) |
159 | 190k | z.grow_to(output_size); |
160 | | |
161 | 31.4M | bigint_sqr(z.mutable_data(), z.size(), |
162 | 31.4M | x, x_size, std::min(m_p_words, x_size), |
163 | 31.4M | ws.data(), ws.size()); |
164 | | |
165 | 31.4M | bigint_monty_redc(z.mutable_data(), |
166 | 31.4M | m_p.data(), m_p_words, m_p_dash, |
167 | 31.4M | ws.data(), ws.size()); |
168 | 31.4M | } |
169 | | |
170 | | class CurveGFp_NIST : public CurveGFp_Repr |
171 | | { |
172 | | public: |
173 | | CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : |
174 | | m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) |
175 | 716 | { |
176 | | // All Solinas prime curves are assumed a == -3 |
177 | 716 | } |
178 | | |
179 | 8.34M | bool a_is_zero() const override { return false; } |
180 | 8.34M | bool a_is_minus_3() const override { return true; } |
181 | | |
182 | 15.5k | const BigInt& get_a() const override { return m_a; } |
183 | | |
184 | 15.5k | const BigInt& get_b() const override { return m_b; } |
185 | | |
186 | 95.4k | const BigInt& get_1_rep() const override { return m_1; } |
187 | | |
188 | 1.14M | size_t get_p_words() const override { return m_p_words; } |
189 | | |
190 | 234M | size_t get_ws_size() const override { return 2*m_p_words + 4; } |
191 | | |
192 | 25.9k | const BigInt& get_a_rep() const override { return m_a; } |
193 | | |
194 | 34.6k | const BigInt& get_b_rep() const override { return m_b; } |
195 | | |
196 | 119k | bool is_one(const BigInt& x) const override { return x == 1; } |
197 | | |
198 | | void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override |
199 | 18.4k | { redc_mod_p(x, ws); } |
200 | | |
201 | | void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override |
202 | 179k | { redc_mod_p(x, ws); } |
203 | | |
204 | | virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0; |
205 | | |
206 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
207 | | |
208 | | void curve_mul_words(BigInt& z, |
209 | | const word x_words[], |
210 | | const size_t x_size, |
211 | | const BigInt& y, |
212 | | secure_vector<word>& ws) const override; |
213 | | |
214 | | void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector<word>& ws) const |
215 | 1.42M | { |
216 | 1.42M | curve_mul(tmp, x, y, ws); |
217 | 1.42M | x.swap(tmp); |
218 | 1.42M | } |
219 | | |
220 | | void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const |
221 | 49.2M | { |
222 | 49.2M | curve_sqr(tmp, x, ws); |
223 | 49.2M | x.swap(tmp); |
224 | 49.2M | } |
225 | | |
226 | | void curve_sqr_words(BigInt& z, |
227 | | const word x_words[], |
228 | | size_t x_size, |
229 | | secure_vector<word>& ws) const override; |
230 | | private: |
231 | | // Curve parameters |
232 | | BigInt m_1; |
233 | | BigInt m_a, m_b; |
234 | | size_t m_p_words; // cache of m_p.sig_words() |
235 | | }; |
236 | | |
237 | | BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const |
238 | 407 | { |
239 | 407 | BOTAN_UNUSED(ws); |
240 | 407 | return inverse_mod(x, get_p()); |
241 | 407 | } |
242 | | |
243 | | void CurveGFp_NIST::curve_mul_words(BigInt& z, |
244 | | const word x_w[], |
245 | | size_t x_size, |
246 | | const BigInt& y, |
247 | | secure_vector<word>& ws) const |
248 | 110M | { |
249 | 110M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
250 | | |
251 | 110M | if(ws.size() < get_ws_size()) |
252 | 0 | ws.resize(get_ws_size()); |
253 | | |
254 | 110M | const size_t output_size = 2*m_p_words + 2; |
255 | 110M | if(z.size() < output_size) |
256 | 4.32M | z.grow_to(output_size); |
257 | | |
258 | 110M | bigint_mul(z.mutable_data(), z.size(), |
259 | 110M | x_w, x_size, std::min(m_p_words, x_size), |
260 | 110M | y.data(), y.size(), std::min(m_p_words, y.size()), |
261 | 110M | ws.data(), ws.size()); |
262 | | |
263 | 110M | this->redc_mod_p(z, ws); |
264 | 110M | } |
265 | | |
266 | | void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size, |
267 | | secure_vector<word>& ws) const |
268 | 108M | { |
269 | 108M | if(ws.size() < get_ws_size()) |
270 | 170k | ws.resize(get_ws_size()); |
271 | | |
272 | 108M | const size_t output_size = 2*m_p_words + 2; |
273 | 108M | if(z.size() < output_size) |
274 | 8.80M | z.grow_to(output_size); |
275 | | |
276 | 108M | bigint_sqr(z.mutable_data(), output_size, |
277 | 108M | x, x_size, std::min(m_p_words, x_size), |
278 | 108M | ws.data(), ws.size()); |
279 | | |
280 | 108M | this->redc_mod_p(z, ws); |
281 | 108M | } |
282 | | |
283 | | /** |
284 | | * The NIST P-192 curve |
285 | | */ |
286 | | class CurveGFp_P192 final : public CurveGFp_NIST |
287 | | { |
288 | | public: |
289 | 23 | CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} |
290 | 21.4k | const BigInt& get_p() const override { return prime_p192(); } |
291 | | private: |
292 | 354k | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); } |
293 | | }; |
294 | | |
295 | | /** |
296 | | * The NIST P-224 curve |
297 | | */ |
298 | | class CurveGFp_P224 final : public CurveGFp_NIST |
299 | | { |
300 | | public: |
301 | 324 | CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} |
302 | 343k | const BigInt& get_p() const override { return prime_p224(); } |
303 | | private: |
304 | 5.99M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); } |
305 | | }; |
306 | | |
307 | | /** |
308 | | * The NIST P-256 curve |
309 | | */ |
310 | | class CurveGFp_P256 final : public CurveGFp_NIST |
311 | | { |
312 | | public: |
313 | 24 | CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} |
314 | 2.32M | const BigInt& get_p() const override { return prime_p256(); } |
315 | | private: |
316 | 32.0M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); } |
317 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
318 | | }; |
319 | | |
320 | | BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const |
321 | 30.7k | { |
322 | 30.7k | BigInt r, p2, p4, p8, p16, p32, tmp; |
323 | | |
324 | 30.7k | curve_sqr(r, x, ws); |
325 | | |
326 | 30.7k | curve_mul(p2, r, x, ws); |
327 | 30.7k | curve_sqr(r, p2, ws); |
328 | 30.7k | curve_sqr_tmp(r, tmp, ws); |
329 | | |
330 | 30.7k | curve_mul(p4, r, p2, ws); |
331 | | |
332 | 30.7k | curve_sqr(r, p4, ws); |
333 | 123k | for(size_t i = 0; i != 3; ++i) |
334 | 92.3k | curve_sqr_tmp(r, tmp, ws); |
335 | 30.7k | curve_mul(p8, r, p4, ws); |
336 | | |
337 | 30.7k | curve_sqr(r, p8, ws); |
338 | 246k | for(size_t i = 0; i != 7; ++i) |
339 | 215k | curve_sqr_tmp(r, tmp, ws); |
340 | 30.7k | curve_mul(p16, r, p8, ws); |
341 | | |
342 | 30.7k | curve_sqr(r, p16, ws); |
343 | 492k | for(size_t i = 0; i != 15; ++i) |
344 | 461k | curve_sqr_tmp(r, tmp, ws); |
345 | 30.7k | curve_mul(p32, r, p16, ws); |
346 | | |
347 | 30.7k | curve_sqr(r, p32, ws); |
348 | 985k | for(size_t i = 0; i != 31; ++i) |
349 | 954k | curve_sqr_tmp(r, tmp, ws); |
350 | 30.7k | curve_mul_tmp(r, x, tmp, ws); |
351 | | |
352 | 3.97M | for(size_t i = 0; i != 32*4; ++i) |
353 | 3.94M | curve_sqr_tmp(r, tmp, ws); |
354 | 30.7k | curve_mul_tmp(r, p32, tmp, ws); |
355 | | |
356 | 1.01M | for(size_t i = 0; i != 32; ++i) |
357 | 985k | curve_sqr_tmp(r, tmp, ws); |
358 | 30.7k | curve_mul_tmp(r, p32, tmp, ws); |
359 | | |
360 | 523k | for(size_t i = 0; i != 16; ++i) |
361 | 492k | curve_sqr_tmp(r, tmp, ws); |
362 | 30.7k | curve_mul_tmp(r, p16, tmp, ws); |
363 | 277k | for(size_t i = 0; i != 8; ++i) |
364 | 246k | curve_sqr_tmp(r, tmp, ws); |
365 | 30.7k | curve_mul_tmp(r, p8, tmp, ws); |
366 | | |
367 | 153k | for(size_t i = 0; i != 4; ++i) |
368 | 123k | curve_sqr_tmp(r, tmp, ws); |
369 | 30.7k | curve_mul_tmp(r, p4, tmp, ws); |
370 | | |
371 | 92.3k | for(size_t i = 0; i != 2; ++i) |
372 | 61.5k | curve_sqr_tmp(r, tmp, ws); |
373 | 30.7k | curve_mul_tmp(r, p2, tmp, ws); |
374 | | |
375 | 92.3k | for(size_t i = 0; i != 2; ++i) |
376 | 61.5k | curve_sqr_tmp(r, tmp, ws); |
377 | 30.7k | curve_mul_tmp(r, x, tmp, ws); |
378 | | |
379 | 30.7k | return r; |
380 | 30.7k | } |
381 | | |
382 | | /** |
383 | | * The NIST P-384 curve |
384 | | */ |
385 | | class CurveGFp_P384 final : public CurveGFp_NIST |
386 | | { |
387 | | public: |
388 | 69 | CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} |
389 | 3.84M | const BigInt& get_p() const override { return prime_p384(); } |
390 | | private: |
391 | 52.5M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); } |
392 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
393 | | }; |
394 | | |
395 | | BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const |
396 | 32.4k | { |
397 | | // From https://briansmith.org/ecc-inversion-addition-chains-01 |
398 | | |
399 | 32.4k | BigInt r, x2, x3, x15, x30, tmp, rl; |
400 | | |
401 | 32.4k | r = x; |
402 | 32.4k | curve_sqr_tmp(r, tmp, ws); |
403 | 32.4k | curve_mul_tmp(r, x, tmp, ws); |
404 | 32.4k | x2 = r; |
405 | | |
406 | 32.4k | curve_sqr_tmp(r, tmp, ws); |
407 | 32.4k | curve_mul_tmp(r, x, tmp, ws); |
408 | | |
409 | 32.4k | x3 = r; |
410 | | |
411 | 129k | for(size_t i = 0; i != 3; ++i) |
412 | 97.3k | curve_sqr_tmp(r, tmp, ws); |
413 | 32.4k | curve_mul_tmp(r, x3, tmp, ws); |
414 | | |
415 | 32.4k | rl = r; |
416 | 227k | for(size_t i = 0; i != 6; ++i) |
417 | 194k | curve_sqr_tmp(r, tmp, ws); |
418 | 32.4k | curve_mul_tmp(r, rl, tmp, ws); |
419 | | |
420 | 129k | for(size_t i = 0; i != 3; ++i) |
421 | 97.3k | curve_sqr_tmp(r, tmp, ws); |
422 | 32.4k | curve_mul_tmp(r, x3, tmp, ws); |
423 | | |
424 | 32.4k | x15 = r; |
425 | 519k | for(size_t i = 0; i != 15; ++i) |
426 | 486k | curve_sqr_tmp(r, tmp, ws); |
427 | 32.4k | curve_mul_tmp(r, x15, tmp, ws); |
428 | | |
429 | 32.4k | x30 = r; |
430 | 1.00M | for(size_t i = 0; i != 30; ++i) |
431 | 973k | curve_sqr_tmp(r, tmp, ws); |
432 | 32.4k | curve_mul_tmp(r, x30, tmp, ws); |
433 | | |
434 | 32.4k | rl = r; |
435 | 1.97M | for(size_t i = 0; i != 60; ++i) |
436 | 1.94M | curve_sqr_tmp(r, tmp, ws); |
437 | 32.4k | curve_mul_tmp(r, rl, tmp, ws); |
438 | | |
439 | 32.4k | rl = r; |
440 | 3.92M | for(size_t i = 0; i != 120; ++i) |
441 | 3.89M | curve_sqr_tmp(r, tmp, ws); |
442 | 32.4k | curve_mul_tmp(r, rl, tmp, ws); |
443 | | |
444 | 519k | for(size_t i = 0; i != 15; ++i) |
445 | 486k | curve_sqr_tmp(r, tmp, ws); |
446 | 32.4k | curve_mul_tmp(r, x15, tmp, ws); |
447 | | |
448 | 1.03M | for(size_t i = 0; i != 31; ++i) |
449 | 1.00M | curve_sqr_tmp(r, tmp, ws); |
450 | 32.4k | curve_mul_tmp(r, x30, tmp, ws); |
451 | | |
452 | 97.3k | for(size_t i = 0; i != 2; ++i) |
453 | 64.8k | curve_sqr_tmp(r, tmp, ws); |
454 | 32.4k | curve_mul_tmp(r, x2, tmp, ws); |
455 | | |
456 | 3.08M | for(size_t i = 0; i != 94; ++i) |
457 | 3.04M | curve_sqr_tmp(r, tmp, ws); |
458 | 32.4k | curve_mul_tmp(r, x30, tmp, ws); |
459 | | |
460 | 97.3k | for(size_t i = 0; i != 2; ++i) |
461 | 64.8k | curve_sqr_tmp(r, tmp, ws); |
462 | | |
463 | 32.4k | curve_mul_tmp(r, x, tmp, ws); |
464 | | |
465 | 32.4k | return r; |
466 | 32.4k | } |
467 | | |
468 | | /** |
469 | | * The NIST P-521 curve |
470 | | */ |
471 | | class CurveGFp_P521 final : public CurveGFp_NIST |
472 | | { |
473 | | public: |
474 | 276 | CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} |
475 | 9.11M | const BigInt& get_p() const override { return prime_p521(); } |
476 | | private: |
477 | 127M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); } |
478 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
479 | | }; |
480 | | |
481 | | BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const |
482 | 56.0k | { |
483 | | // Addition chain from https://eprint.iacr.org/2014/852.pdf section |
484 | | |
485 | 56.0k | BigInt r; |
486 | 56.0k | BigInt rl; |
487 | 56.0k | BigInt a7; |
488 | 56.0k | BigInt tmp; |
489 | | |
490 | 56.0k | curve_sqr(r, x, ws); |
491 | 56.0k | curve_mul_tmp(r, x, tmp, ws); |
492 | | |
493 | 56.0k | curve_sqr_tmp(r, tmp, ws); |
494 | 56.0k | curve_mul_tmp(r, x, tmp, ws); |
495 | | |
496 | 56.0k | rl = r; |
497 | | |
498 | 224k | for(size_t i = 0; i != 3; ++i) |
499 | 168k | curve_sqr_tmp(r, tmp, ws); |
500 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
501 | | |
502 | 56.0k | curve_sqr_tmp(r, tmp, ws); |
503 | 56.0k | curve_mul_tmp(r, x, tmp, ws); |
504 | 56.0k | a7 = r; // need this value later |
505 | | |
506 | 56.0k | curve_sqr_tmp(r, tmp, ws); |
507 | 56.0k | curve_mul_tmp(r, x, tmp, ws); |
508 | | |
509 | 56.0k | rl = r; |
510 | 504k | for(size_t i = 0; i != 8; ++i) |
511 | 448k | curve_sqr_tmp(r, tmp, ws); |
512 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
513 | | |
514 | 56.0k | rl = r; |
515 | 953k | for(size_t i = 0; i != 16; ++i) |
516 | 897k | curve_sqr_tmp(r, tmp, ws); |
517 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
518 | | |
519 | 56.0k | rl = r; |
520 | 1.85M | for(size_t i = 0; i != 32; ++i) |
521 | 1.79M | curve_sqr_tmp(r, tmp, ws); |
522 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
523 | | |
524 | 56.0k | rl = r; |
525 | 3.64M | for(size_t i = 0; i != 64; ++i) |
526 | 3.58M | curve_sqr_tmp(r, tmp, ws); |
527 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
528 | | |
529 | 56.0k | rl = r; |
530 | 7.23M | for(size_t i = 0; i != 128; ++i) |
531 | 7.17M | curve_sqr_tmp(r, tmp, ws); |
532 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
533 | | |
534 | 56.0k | rl = r; |
535 | 14.4M | for(size_t i = 0; i != 256; ++i) |
536 | 14.3M | curve_sqr_tmp(r, tmp, ws); |
537 | 56.0k | curve_mul_tmp(r, rl, tmp, ws); |
538 | | |
539 | 448k | for(size_t i = 0; i != 7; ++i) |
540 | 392k | curve_sqr_tmp(r, tmp, ws); |
541 | 56.0k | curve_mul_tmp(r, a7, tmp, ws); |
542 | | |
543 | 168k | for(size_t i = 0; i != 2; ++i) |
544 | 112k | curve_sqr_tmp(r, tmp, ws); |
545 | 56.0k | curve_mul_tmp(r, x, tmp, ws); |
546 | | |
547 | 56.0k | return r; |
548 | 56.0k | } |
549 | | |
550 | | } |
551 | | |
552 | | std::shared_ptr<CurveGFp_Repr> |
553 | | CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) |
554 | 1.37k | { |
555 | 1.37k | if(p == prime_p192()) |
556 | 23 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); |
557 | 1.35k | if(p == prime_p224()) |
558 | 324 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); |
559 | 1.02k | if(p == prime_p256()) |
560 | 24 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); |
561 | 1.00k | if(p == prime_p384()) |
562 | 69 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); |
563 | 935 | if(p == prime_p521()) |
564 | 276 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); |
565 | | |
566 | 659 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b)); |
567 | 659 | } |
568 | | |
569 | | } |