/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 | 649 | { |
29 | 649 | Modular_Reducer mod_p(m_p); |
30 | | |
31 | 649 | m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS); |
32 | 649 | m_r = mod_p.reduce(m_r); |
33 | | |
34 | 649 | m_r2 = mod_p.square(m_r); |
35 | 649 | m_r3 = mod_p.multiply(m_r, m_r2); |
36 | 649 | m_a_r = mod_p.multiply(m_r, m_a); |
37 | 649 | m_b_r = mod_p.multiply(m_r, m_b); |
38 | | |
39 | 649 | m_a_is_zero = m_a.is_zero(); |
40 | 649 | m_a_is_minus_3 = (m_a + 3 == m_p); |
41 | 649 | } |
42 | | |
43 | 2.80M | bool a_is_zero() const override { return m_a_is_zero; } |
44 | 2.67M | bool a_is_minus_3() const override { return m_a_is_minus_3; } |
45 | | |
46 | 6.26k | const BigInt& get_a() const override { return m_a; } |
47 | | |
48 | 6.26k | const BigInt& get_b() const override { return m_b; } |
49 | | |
50 | 4.69M | const BigInt& get_p() const override { return m_p; } |
51 | | |
52 | 2.62M | const BigInt& get_a_rep() const override { return m_a_r; } |
53 | | |
54 | 12.8k | const BigInt& get_b_rep() const override { return m_b_r; } |
55 | | |
56 | 37.5k | const BigInt& get_1_rep() const override { return m_r; } |
57 | | |
58 | 36.8k | bool is_one(const BigInt& x) const override { return x == m_r; } |
59 | | |
60 | 406k | size_t get_p_words() const override { return m_p_words; } |
61 | | |
62 | 61.0M | 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 | 37.1k | { |
97 | | // Should we use Montgomery inverse instead? |
98 | 37.1k | const BigInt inv = inverse_mod(x, m_p); |
99 | 37.1k | BigInt res; |
100 | 37.1k | curve_mul(res, inv, m_r3, ws); |
101 | 37.1k | return res; |
102 | 37.1k | } |
103 | | |
104 | | void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const |
105 | 9.13k | { |
106 | 9.13k | const BigInt tx = x; |
107 | 9.13k | curve_mul(x, tx, m_r2, ws); |
108 | 9.13k | } |
109 | | |
110 | | void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const |
111 | 59.0k | { |
112 | 59.0k | if(ws.size() < get_ws_size()) |
113 | 496 | ws.resize(get_ws_size()); |
114 | | |
115 | 59.0k | const size_t output_size = 2*m_p_words + 2; |
116 | 59.0k | if(z.size() < output_size) |
117 | 12.3k | z.grow_to(output_size); |
118 | | |
119 | 59.0k | bigint_monty_redc(z.mutable_data(), |
120 | 59.0k | m_p.data(), m_p_words, m_p_dash, |
121 | 59.0k | ws.data(), ws.size()); |
122 | 59.0k | } |
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 | 32.7M | { |
130 | 32.7M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
131 | | |
132 | 32.7M | if(ws.size() < get_ws_size()) |
133 | 0 | ws.resize(get_ws_size()); |
134 | | |
135 | 32.7M | const size_t output_size = 2*m_p_words + 2; |
136 | 32.7M | if(z.size() < output_size) |
137 | 1.89M | z.grow_to(output_size); |
138 | | |
139 | 32.7M | bigint_mul(z.mutable_data(), z.size(), |
140 | 32.7M | x_w, x_size, std::min(m_p_words, x_size), |
141 | 32.7M | y.data(), y.size(), std::min(m_p_words, y.size()), |
142 | 32.7M | ws.data(), ws.size()); |
143 | | |
144 | 32.7M | bigint_monty_redc(z.mutable_data(), |
145 | 32.7M | m_p.data(), m_p_words, m_p_dash, |
146 | 32.7M | ws.data(), ws.size()); |
147 | 32.7M | } |
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 | 23.5M | { |
154 | 23.5M | if(ws.size() < get_ws_size()) |
155 | 54.9k | ws.resize(get_ws_size()); |
156 | | |
157 | 23.5M | const size_t output_size = 2*m_p_words + 2; |
158 | 23.5M | if(z.size() < output_size) |
159 | 159k | z.grow_to(output_size); |
160 | | |
161 | 23.5M | bigint_sqr(z.mutable_data(), z.size(), |
162 | 23.5M | x, x_size, std::min(m_p_words, x_size), |
163 | 23.5M | ws.data(), ws.size()); |
164 | | |
165 | 23.5M | bigint_monty_redc(z.mutable_data(), |
166 | 23.5M | m_p.data(), m_p_words, m_p_dash, |
167 | 23.5M | ws.data(), ws.size()); |
168 | 23.5M | } |
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 | 765 | { |
176 | | // All Solinas prime curves are assumed a == -3 |
177 | 765 | } |
178 | | |
179 | 11.7M | bool a_is_zero() const override { return false; } |
180 | 11.7M | bool a_is_minus_3() const override { return true; } |
181 | | |
182 | 19.6k | const BigInt& get_a() const override { return m_a; } |
183 | | |
184 | 19.6k | const BigInt& get_b() const override { return m_b; } |
185 | | |
186 | 119k | const BigInt& get_1_rep() const override { return m_1; } |
187 | | |
188 | 1.23M | size_t get_p_words() const override { return m_p_words; } |
189 | | |
190 | 283M | size_t get_ws_size() const override { return 2*m_p_words + 4; } |
191 | | |
192 | 35.2k | const BigInt& get_a_rep() const override { return m_a; } |
193 | | |
194 | 47.1k | const BigInt& get_b_rep() const override { return m_b; } |
195 | | |
196 | 122k | 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 | 28.6k | { redc_mod_p(x, ws); } |
200 | | |
201 | | void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override |
202 | 204k | { 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.46M | { |
216 | 1.46M | curve_mul(tmp, x, y, ws); |
217 | 1.46M | x.swap(tmp); |
218 | 1.46M | } |
219 | | |
220 | | void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const |
221 | 50.6M | { |
222 | 50.6M | curve_sqr(tmp, x, ws); |
223 | 50.6M | x.swap(tmp); |
224 | 50.6M | } |
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 | 430 | { |
239 | 430 | BOTAN_UNUSED(ws); |
240 | 430 | return inverse_mod(x, get_p()); |
241 | 430 | } |
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 | 135M | { |
249 | 135M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
250 | | |
251 | 135M | if(ws.size() < get_ws_size()) |
252 | 0 | ws.resize(get_ws_size()); |
253 | | |
254 | 135M | const size_t output_size = 2*m_p_words + 2; |
255 | 135M | if(z.size() < output_size) |
256 | 4.69M | z.grow_to(output_size); |
257 | | |
258 | 135M | bigint_mul(z.mutable_data(), z.size(), |
259 | 135M | x_w, x_size, std::min(m_p_words, x_size), |
260 | 135M | y.data(), y.size(), std::min(m_p_words, y.size()), |
261 | 135M | ws.data(), ws.size()); |
262 | | |
263 | 135M | this->redc_mod_p(z, ws); |
264 | 135M | } |
265 | | |
266 | | void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size, |
267 | | secure_vector<word>& ws) const |
268 | 127M | { |
269 | 127M | if(ws.size() < get_ws_size()) |
270 | 190k | ws.resize(get_ws_size()); |
271 | | |
272 | 127M | const size_t output_size = 2*m_p_words + 2; |
273 | 127M | if(z.size() < output_size) |
274 | 12.2M | z.grow_to(output_size); |
275 | | |
276 | 127M | bigint_sqr(z.mutable_data(), output_size, |
277 | 127M | x, x_size, std::min(m_p_words, x_size), |
278 | 127M | ws.data(), ws.size()); |
279 | | |
280 | 127M | this->redc_mod_p(z, ws); |
281 | 127M | } |
282 | | |
283 | | /** |
284 | | * The NIST P-192 curve |
285 | | */ |
286 | | class CurveGFp_P192 final : public CurveGFp_NIST |
287 | | { |
288 | | public: |
289 | 22 | CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} |
290 | 20.4k | const BigInt& get_p() const override { return prime_p192(); } |
291 | | private: |
292 | 336k | 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 | 339 | CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} |
302 | 387k | const BigInt& get_p() const override { return prime_p224(); } |
303 | | private: |
304 | 6.61M | 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 | 23 | CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} |
314 | 2.74M | const BigInt& get_p() const override { return prime_p256(); } |
315 | | private: |
316 | 36.4M | 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 | 31.8k | { |
322 | 31.8k | BigInt r, p2, p4, p8, p16, p32, tmp; |
323 | | |
324 | 31.8k | curve_sqr(r, x, ws); |
325 | | |
326 | 31.8k | curve_mul(p2, r, x, ws); |
327 | 31.8k | curve_sqr(r, p2, ws); |
328 | 31.8k | curve_sqr_tmp(r, tmp, ws); |
329 | | |
330 | 31.8k | curve_mul(p4, r, p2, ws); |
331 | | |
332 | 31.8k | curve_sqr(r, p4, ws); |
333 | 127k | for(size_t i = 0; i != 3; ++i) |
334 | 95.6k | curve_sqr_tmp(r, tmp, ws); |
335 | 31.8k | curve_mul(p8, r, p4, ws); |
336 | | |
337 | 31.8k | curve_sqr(r, p8, ws); |
338 | 255k | for(size_t i = 0; i != 7; ++i) |
339 | 223k | curve_sqr_tmp(r, tmp, ws); |
340 | 31.8k | curve_mul(p16, r, p8, ws); |
341 | | |
342 | 31.8k | curve_sqr(r, p16, ws); |
343 | 510k | for(size_t i = 0; i != 15; ++i) |
344 | 478k | curve_sqr_tmp(r, tmp, ws); |
345 | 31.8k | curve_mul(p32, r, p16, ws); |
346 | | |
347 | 31.8k | curve_sqr(r, p32, ws); |
348 | 1.02M | for(size_t i = 0; i != 31; ++i) |
349 | 988k | curve_sqr_tmp(r, tmp, ws); |
350 | 31.8k | curve_mul_tmp(r, x, tmp, ws); |
351 | | |
352 | 4.11M | for(size_t i = 0; i != 32*4; ++i) |
353 | 4.08M | curve_sqr_tmp(r, tmp, ws); |
354 | 31.8k | curve_mul_tmp(r, p32, tmp, ws); |
355 | | |
356 | 1.05M | for(size_t i = 0; i != 32; ++i) |
357 | 1.02M | curve_sqr_tmp(r, tmp, ws); |
358 | 31.8k | curve_mul_tmp(r, p32, tmp, ws); |
359 | | |
360 | 542k | for(size_t i = 0; i != 16; ++i) |
361 | 510k | curve_sqr_tmp(r, tmp, ws); |
362 | 31.8k | curve_mul_tmp(r, p16, tmp, ws); |
363 | 286k | for(size_t i = 0; i != 8; ++i) |
364 | 255k | curve_sqr_tmp(r, tmp, ws); |
365 | 31.8k | curve_mul_tmp(r, p8, tmp, ws); |
366 | | |
367 | 159k | for(size_t i = 0; i != 4; ++i) |
368 | 127k | curve_sqr_tmp(r, tmp, ws); |
369 | 31.8k | curve_mul_tmp(r, p4, tmp, ws); |
370 | | |
371 | 95.6k | for(size_t i = 0; i != 2; ++i) |
372 | 63.7k | curve_sqr_tmp(r, tmp, ws); |
373 | 31.8k | curve_mul_tmp(r, p2, tmp, ws); |
374 | | |
375 | 95.6k | for(size_t i = 0; i != 2; ++i) |
376 | 63.7k | curve_sqr_tmp(r, tmp, ws); |
377 | 31.8k | curve_mul_tmp(r, x, tmp, ws); |
378 | | |
379 | 31.8k | return r; |
380 | 31.8k | } |
381 | | |
382 | | /** |
383 | | * The NIST P-384 curve |
384 | | */ |
385 | | class CurveGFp_P384 final : public CurveGFp_NIST |
386 | | { |
387 | | public: |
388 | 91 | CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} |
389 | 4.22M | const BigInt& get_p() const override { return prime_p384(); } |
390 | | private: |
391 | 55.8M | 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 | 31.1k | { |
397 | | // From https://briansmith.org/ecc-inversion-addition-chains-01 |
398 | | |
399 | 31.1k | BigInt r, x2, x3, x15, x30, tmp, rl; |
400 | | |
401 | 31.1k | r = x; |
402 | 31.1k | curve_sqr_tmp(r, tmp, ws); |
403 | 31.1k | curve_mul_tmp(r, x, tmp, ws); |
404 | 31.1k | x2 = r; |
405 | | |
406 | 31.1k | curve_sqr_tmp(r, tmp, ws); |
407 | 31.1k | curve_mul_tmp(r, x, tmp, ws); |
408 | | |
409 | 31.1k | x3 = r; |
410 | | |
411 | 124k | for(size_t i = 0; i != 3; ++i) |
412 | 93.3k | curve_sqr_tmp(r, tmp, ws); |
413 | 31.1k | curve_mul_tmp(r, x3, tmp, ws); |
414 | | |
415 | 31.1k | rl = r; |
416 | 217k | for(size_t i = 0; i != 6; ++i) |
417 | 186k | curve_sqr_tmp(r, tmp, ws); |
418 | 31.1k | curve_mul_tmp(r, rl, tmp, ws); |
419 | | |
420 | 124k | for(size_t i = 0; i != 3; ++i) |
421 | 93.3k | curve_sqr_tmp(r, tmp, ws); |
422 | 31.1k | curve_mul_tmp(r, x3, tmp, ws); |
423 | | |
424 | 31.1k | x15 = r; |
425 | 497k | for(size_t i = 0; i != 15; ++i) |
426 | 466k | curve_sqr_tmp(r, tmp, ws); |
427 | 31.1k | curve_mul_tmp(r, x15, tmp, ws); |
428 | | |
429 | 31.1k | x30 = r; |
430 | 964k | for(size_t i = 0; i != 30; ++i) |
431 | 933k | curve_sqr_tmp(r, tmp, ws); |
432 | 31.1k | curve_mul_tmp(r, x30, tmp, ws); |
433 | | |
434 | 31.1k | rl = r; |
435 | 1.89M | for(size_t i = 0; i != 60; ++i) |
436 | 1.86M | curve_sqr_tmp(r, tmp, ws); |
437 | 31.1k | curve_mul_tmp(r, rl, tmp, ws); |
438 | | |
439 | 31.1k | rl = r; |
440 | 3.76M | for(size_t i = 0; i != 120; ++i) |
441 | 3.73M | curve_sqr_tmp(r, tmp, ws); |
442 | 31.1k | curve_mul_tmp(r, rl, tmp, ws); |
443 | | |
444 | 497k | for(size_t i = 0; i != 15; ++i) |
445 | 466k | curve_sqr_tmp(r, tmp, ws); |
446 | 31.1k | curve_mul_tmp(r, x15, tmp, ws); |
447 | | |
448 | 995k | for(size_t i = 0; i != 31; ++i) |
449 | 964k | curve_sqr_tmp(r, tmp, ws); |
450 | 31.1k | curve_mul_tmp(r, x30, tmp, ws); |
451 | | |
452 | 93.3k | for(size_t i = 0; i != 2; ++i) |
453 | 62.2k | curve_sqr_tmp(r, tmp, ws); |
454 | 31.1k | curve_mul_tmp(r, x2, tmp, ws); |
455 | | |
456 | 2.95M | for(size_t i = 0; i != 94; ++i) |
457 | 2.92M | curve_sqr_tmp(r, tmp, ws); |
458 | 31.1k | curve_mul_tmp(r, x30, tmp, ws); |
459 | | |
460 | 93.3k | for(size_t i = 0; i != 2; ++i) |
461 | 62.2k | curve_sqr_tmp(r, tmp, ws); |
462 | | |
463 | 31.1k | curve_mul_tmp(r, x, tmp, ws); |
464 | | |
465 | 31.1k | return r; |
466 | 31.1k | } |
467 | | |
468 | | /** |
469 | | * The NIST P-521 curve |
470 | | */ |
471 | | class CurveGFp_P521 final : public CurveGFp_NIST |
472 | | { |
473 | | public: |
474 | 290 | CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} |
475 | 12.6M | const BigInt& get_p() const override { return prime_p521(); } |
476 | | private: |
477 | 164M | 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 | 59.4k | { |
483 | | // Addition chain from https://eprint.iacr.org/2014/852.pdf section |
484 | | |
485 | 59.4k | BigInt r; |
486 | 59.4k | BigInt rl; |
487 | 59.4k | BigInt a7; |
488 | 59.4k | BigInt tmp; |
489 | | |
490 | 59.4k | curve_sqr(r, x, ws); |
491 | 59.4k | curve_mul_tmp(r, x, tmp, ws); |
492 | | |
493 | 59.4k | curve_sqr_tmp(r, tmp, ws); |
494 | 59.4k | curve_mul_tmp(r, x, tmp, ws); |
495 | | |
496 | 59.4k | rl = r; |
497 | | |
498 | 237k | for(size_t i = 0; i != 3; ++i) |
499 | 178k | curve_sqr_tmp(r, tmp, ws); |
500 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
501 | | |
502 | 59.4k | curve_sqr_tmp(r, tmp, ws); |
503 | 59.4k | curve_mul_tmp(r, x, tmp, ws); |
504 | 59.4k | a7 = r; // need this value later |
505 | | |
506 | 59.4k | curve_sqr_tmp(r, tmp, ws); |
507 | 59.4k | curve_mul_tmp(r, x, tmp, ws); |
508 | | |
509 | 59.4k | rl = r; |
510 | 534k | for(size_t i = 0; i != 8; ++i) |
511 | 475k | curve_sqr_tmp(r, tmp, ws); |
512 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
513 | | |
514 | 59.4k | rl = r; |
515 | 1.01M | for(size_t i = 0; i != 16; ++i) |
516 | 950k | curve_sqr_tmp(r, tmp, ws); |
517 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
518 | | |
519 | 59.4k | rl = r; |
520 | 1.96M | for(size_t i = 0; i != 32; ++i) |
521 | 1.90M | curve_sqr_tmp(r, tmp, ws); |
522 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
523 | | |
524 | 59.4k | rl = r; |
525 | 3.86M | for(size_t i = 0; i != 64; ++i) |
526 | 3.80M | curve_sqr_tmp(r, tmp, ws); |
527 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
528 | | |
529 | 59.4k | rl = r; |
530 | 7.66M | for(size_t i = 0; i != 128; ++i) |
531 | 7.60M | curve_sqr_tmp(r, tmp, ws); |
532 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
533 | | |
534 | 59.4k | rl = r; |
535 | 15.2M | for(size_t i = 0; i != 256; ++i) |
536 | 15.2M | curve_sqr_tmp(r, tmp, ws); |
537 | 59.4k | curve_mul_tmp(r, rl, tmp, ws); |
538 | | |
539 | 475k | for(size_t i = 0; i != 7; ++i) |
540 | 415k | curve_sqr_tmp(r, tmp, ws); |
541 | 59.4k | curve_mul_tmp(r, a7, tmp, ws); |
542 | | |
543 | 178k | for(size_t i = 0; i != 2; ++i) |
544 | 118k | curve_sqr_tmp(r, tmp, ws); |
545 | 59.4k | curve_mul_tmp(r, x, tmp, ws); |
546 | | |
547 | 59.4k | return r; |
548 | 59.4k | } |
549 | | |
550 | | } |
551 | | |
552 | | std::shared_ptr<CurveGFp_Repr> |
553 | | CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) |
554 | 1.41k | { |
555 | 1.41k | if(p == prime_p192()) |
556 | 22 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); |
557 | 1.39k | if(p == prime_p224()) |
558 | 339 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); |
559 | 1.05k | if(p == prime_p256()) |
560 | 23 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); |
561 | 1.03k | if(p == prime_p384()) |
562 | 91 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); |
563 | 939 | if(p == prime_p521()) |
564 | 290 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); |
565 | | |
566 | 649 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b)); |
567 | 649 | } |
568 | | |
569 | | } |