/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/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 | | |
16 | | namespace Botan { |
17 | | |
18 | | namespace { |
19 | | |
20 | | class CurveGFp_Montgomery final : public CurveGFp_Repr |
21 | | { |
22 | | public: |
23 | | CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) : |
24 | | m_p(p), m_a(a), m_b(b), |
25 | | m_p_words(m_p.sig_words()), |
26 | | m_p_dash(monty_inverse(m_p.word_at(0))) |
27 | 636 | { |
28 | 636 | Modular_Reducer mod_p(m_p); |
29 | 636 | |
30 | 636 | m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS); |
31 | 636 | m_r = mod_p.reduce(m_r); |
32 | 636 | |
33 | 636 | m_r2 = mod_p.square(m_r); |
34 | 636 | m_r3 = mod_p.multiply(m_r, m_r2); |
35 | 636 | m_a_r = mod_p.multiply(m_r, m_a); |
36 | 636 | m_b_r = mod_p.multiply(m_r, m_b); |
37 | 636 | |
38 | 636 | m_a_is_zero = m_a.is_zero(); |
39 | 636 | m_a_is_minus_3 = (m_a + 3 == m_p); |
40 | 636 | } |
41 | | |
42 | 2.79M | bool a_is_zero() const override { return m_a_is_zero; } |
43 | 2.64M | bool a_is_minus_3() const override { return m_a_is_minus_3; } |
44 | | |
45 | 5.80k | const BigInt& get_a() const override { return m_a; } |
46 | | |
47 | 5.80k | const BigInt& get_b() const override { return m_b; } |
48 | | |
49 | 4.66M | const BigInt& get_p() const override { return m_p; } |
50 | | |
51 | 2.58M | const BigInt& get_a_rep() const override { return m_a_r; } |
52 | | |
53 | 12.5k | const BigInt& get_b_rep() const override { return m_b_r; } |
54 | | |
55 | 49.0k | const BigInt& get_1_rep() const override { return m_r; } |
56 | | |
57 | 34.6k | bool is_one(const BigInt& x) const override { return x == m_r; } |
58 | | |
59 | 427k | size_t get_p_words() const override { return m_p_words; } |
60 | | |
61 | 60.5M | size_t get_ws_size() const override { return 2*m_p_words + 4; } |
62 | | |
63 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
64 | | |
65 | | void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override; |
66 | | |
67 | | void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override; |
68 | | |
69 | | void curve_mul_words(BigInt& z, |
70 | | const word x_words[], |
71 | | const size_t x_size, |
72 | | const BigInt& y, |
73 | | secure_vector<word>& ws) const override; |
74 | | |
75 | | void curve_sqr_words(BigInt& z, |
76 | | const word x_words[], |
77 | | size_t x_size, |
78 | | secure_vector<word>& ws) const override; |
79 | | |
80 | | private: |
81 | | BigInt m_p; |
82 | | BigInt m_a, m_b; |
83 | | BigInt m_a_r, m_b_r; |
84 | | size_t m_p_words; // cache of m_p.sig_words() |
85 | | |
86 | | // Montgomery parameters |
87 | | BigInt m_r, m_r2, m_r3; |
88 | | word m_p_dash; |
89 | | |
90 | | bool m_a_is_zero; |
91 | | bool m_a_is_minus_3; |
92 | | }; |
93 | | |
94 | | BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const |
95 | 34.9k | { |
96 | | // Should we use Montgomery inverse instead? |
97 | 34.9k | const BigInt inv = inverse_mod(x, m_p); |
98 | 34.9k | BigInt res; |
99 | 34.9k | curve_mul(res, inv, m_r3, ws); |
100 | 34.9k | return res; |
101 | 34.9k | } |
102 | | |
103 | | void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const |
104 | 8.79k | { |
105 | 8.79k | const BigInt tx = x; |
106 | 8.79k | curve_mul(x, tx, m_r2, ws); |
107 | 8.79k | } |
108 | | |
109 | | void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const |
110 | 56.3k | { |
111 | 56.3k | if(ws.size() < get_ws_size()) |
112 | 510 | ws.resize(get_ws_size()); |
113 | 56.3k | |
114 | 56.3k | const size_t output_size = 2*m_p_words + 2; |
115 | 56.3k | if(z.size() < output_size) |
116 | 12.1k | z.grow_to(output_size); |
117 | 56.3k | |
118 | 56.3k | bigint_monty_redc(z.mutable_data(), |
119 | 56.3k | m_p.data(), m_p_words, m_p_dash, |
120 | 56.3k | ws.data(), ws.size()); |
121 | 56.3k | } |
122 | | |
123 | | void CurveGFp_Montgomery::curve_mul_words(BigInt& z, |
124 | | const word x_w[], |
125 | | size_t x_size, |
126 | | const BigInt& y, |
127 | | secure_vector<word>& ws) const |
128 | 32.5M | { |
129 | 32.5M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
130 | 32.5M | |
131 | 32.5M | if(ws.size() < get_ws_size()) |
132 | 0 | ws.resize(get_ws_size()); |
133 | 32.5M | |
134 | 32.5M | const size_t output_size = 2*m_p_words + 2; |
135 | 32.5M | if(z.size() < output_size) |
136 | 1.92M | z.grow_to(output_size); |
137 | 32.5M | |
138 | 32.5M | bigint_mul(z.mutable_data(), z.size(), |
139 | 32.5M | x_w, x_size, std::min(m_p_words, x_size), |
140 | 32.5M | y.data(), y.size(), std::min(m_p_words, y.size()), |
141 | 32.5M | ws.data(), ws.size()); |
142 | 32.5M | |
143 | 32.5M | bigint_monty_redc(z.mutable_data(), |
144 | 32.5M | m_p.data(), m_p_words, m_p_dash, |
145 | 32.5M | ws.data(), ws.size()); |
146 | 32.5M | } |
147 | | |
148 | | void CurveGFp_Montgomery::curve_sqr_words(BigInt& z, |
149 | | const word x[], |
150 | | size_t x_size, |
151 | | secure_vector<word>& ws) const |
152 | 23.3M | { |
153 | 23.3M | if(ws.size() < get_ws_size()) |
154 | 52.3k | ws.resize(get_ws_size()); |
155 | 23.3M | |
156 | 23.3M | const size_t output_size = 2*m_p_words + 2; |
157 | 23.3M | if(z.size() < output_size) |
158 | 165k | z.grow_to(output_size); |
159 | 23.3M | |
160 | 23.3M | bigint_sqr(z.mutable_data(), z.size(), |
161 | 23.3M | x, x_size, std::min(m_p_words, x_size), |
162 | 23.3M | ws.data(), ws.size()); |
163 | 23.3M | |
164 | 23.3M | bigint_monty_redc(z.mutable_data(), |
165 | 23.3M | m_p.data(), m_p_words, m_p_dash, |
166 | 23.3M | ws.data(), ws.size()); |
167 | 23.3M | } |
168 | | |
169 | | class CurveGFp_NIST : public CurveGFp_Repr |
170 | | { |
171 | | public: |
172 | | CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : |
173 | | m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) |
174 | 698 | { |
175 | | // All Solinas prime curves are assumed a == -3 |
176 | 698 | } |
177 | | |
178 | 11.3M | bool a_is_zero() const override { return false; } |
179 | 11.3M | bool a_is_minus_3() const override { return true; } |
180 | | |
181 | 18.9k | const BigInt& get_a() const override { return m_a; } |
182 | | |
183 | 18.9k | const BigInt& get_b() const override { return m_b; } |
184 | | |
185 | 118k | const BigInt& get_1_rep() const override { return m_1; } |
186 | | |
187 | 1.13M | size_t get_p_words() const override { return m_p_words; } |
188 | | |
189 | 272M | size_t get_ws_size() const override { return 2*m_p_words + 4; } |
190 | | |
191 | 35.7k | const BigInt& get_a_rep() const override { return m_a; } |
192 | | |
193 | 47.6k | const BigInt& get_b_rep() const override { return m_b; } |
194 | | |
195 | 116k | bool is_one(const BigInt& x) const override { return x == 1; } |
196 | | |
197 | | void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override |
198 | 28.3k | { redc_mod_p(x, ws); } |
199 | | |
200 | | void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override |
201 | 199k | { redc_mod_p(x, ws); } |
202 | | |
203 | | virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0; |
204 | | |
205 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
206 | | |
207 | | void curve_mul_words(BigInt& z, |
208 | | const word x_words[], |
209 | | const size_t x_size, |
210 | | const BigInt& y, |
211 | | secure_vector<word>& ws) const override; |
212 | | |
213 | | void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector<word>& ws) const |
214 | 1.39M | { |
215 | 1.39M | curve_mul(tmp, x, y, ws); |
216 | 1.39M | x.swap(tmp); |
217 | 1.39M | } |
218 | | |
219 | | void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const |
220 | 48.3M | { |
221 | 48.3M | curve_sqr(tmp, x, ws); |
222 | 48.3M | x.swap(tmp); |
223 | 48.3M | } |
224 | | |
225 | | void curve_sqr_words(BigInt& z, |
226 | | const word x_words[], |
227 | | size_t x_size, |
228 | | secure_vector<word>& ws) const override; |
229 | | private: |
230 | | // Curve parameters |
231 | | BigInt m_1; |
232 | | BigInt m_a, m_b; |
233 | | size_t m_p_words; // cache of m_p.sig_words() |
234 | | }; |
235 | | |
236 | | BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const |
237 | 434 | { |
238 | 434 | BOTAN_UNUSED(ws); |
239 | 434 | return inverse_mod(x, get_p()); |
240 | 434 | } |
241 | | |
242 | | void CurveGFp_NIST::curve_mul_words(BigInt& z, |
243 | | const word x_w[], |
244 | | size_t x_size, |
245 | | const BigInt& y, |
246 | | secure_vector<word>& ws) const |
247 | 130M | { |
248 | 130M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
249 | 130M | |
250 | 130M | if(ws.size() < get_ws_size()) |
251 | 0 | ws.resize(get_ws_size()); |
252 | 130M | |
253 | 130M | const size_t output_size = 2*m_p_words + 2; |
254 | 130M | if(z.size() < output_size) |
255 | 4.40M | z.grow_to(output_size); |
256 | 130M | |
257 | 130M | bigint_mul(z.mutable_data(), z.size(), |
258 | 130M | x_w, x_size, std::min(m_p_words, x_size), |
259 | 130M | y.data(), y.size(), std::min(m_p_words, y.size()), |
260 | 130M | ws.data(), ws.size()); |
261 | 130M | |
262 | 130M | this->redc_mod_p(z, ws); |
263 | 130M | } |
264 | | |
265 | | void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size, |
266 | | secure_vector<word>& ws) const |
267 | 122M | { |
268 | 122M | if(ws.size() < get_ws_size()) |
269 | 185k | ws.resize(get_ws_size()); |
270 | 122M | |
271 | 122M | const size_t output_size = 2*m_p_words + 2; |
272 | 122M | if(z.size() < output_size) |
273 | 11.8M | z.grow_to(output_size); |
274 | 122M | |
275 | 122M | bigint_sqr(z.mutable_data(), output_size, |
276 | 122M | x, x_size, std::min(m_p_words, x_size), |
277 | 122M | ws.data(), ws.size()); |
278 | 122M | |
279 | 122M | this->redc_mod_p(z, ws); |
280 | 122M | } |
281 | | |
282 | | /** |
283 | | * The NIST P-192 curve |
284 | | */ |
285 | | class CurveGFp_P192 final : public CurveGFp_NIST |
286 | | { |
287 | | public: |
288 | 23 | CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} |
289 | 20.3k | const BigInt& get_p() const override { return prime_p192(); } |
290 | | private: |
291 | 344k | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); } |
292 | | }; |
293 | | |
294 | | /** |
295 | | * The NIST P-224 curve |
296 | | */ |
297 | | class CurveGFp_P224 final : public CurveGFp_NIST |
298 | | { |
299 | | public: |
300 | 303 | CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} |
301 | 333k | const BigInt& get_p() const override { return prime_p224(); } |
302 | | private: |
303 | 5.75M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); } |
304 | | }; |
305 | | |
306 | | /** |
307 | | * The NIST P-256 curve |
308 | | */ |
309 | | class CurveGFp_P256 final : public CurveGFp_NIST |
310 | | { |
311 | | public: |
312 | 20 | CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} |
313 | 2.92M | const BigInt& get_p() const override { return prime_p256(); } |
314 | | private: |
315 | 37.9M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); } |
316 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
317 | | }; |
318 | | |
319 | | BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const |
320 | 30.9k | { |
321 | 30.9k | BigInt r, p2, p4, p8, p16, p32, tmp; |
322 | 30.9k | |
323 | 30.9k | curve_sqr(r, x, ws); |
324 | 30.9k | |
325 | 30.9k | curve_mul(p2, r, x, ws); |
326 | 30.9k | curve_sqr(r, p2, ws); |
327 | 30.9k | curve_sqr_tmp(r, tmp, ws); |
328 | 30.9k | |
329 | 30.9k | curve_mul(p4, r, p2, ws); |
330 | 30.9k | |
331 | 30.9k | curve_sqr(r, p4, ws); |
332 | 123k | for(size_t i = 0; i != 3; ++i) |
333 | 92.7k | curve_sqr_tmp(r, tmp, ws); |
334 | 30.9k | curve_mul(p8, r, p4, ws); |
335 | 30.9k | |
336 | 30.9k | curve_sqr(r, p8, ws); |
337 | 247k | for(size_t i = 0; i != 7; ++i) |
338 | 216k | curve_sqr_tmp(r, tmp, ws); |
339 | 30.9k | curve_mul(p16, r, p8, ws); |
340 | 30.9k | |
341 | 30.9k | curve_sqr(r, p16, ws); |
342 | 494k | for(size_t i = 0; i != 15; ++i) |
343 | 463k | curve_sqr_tmp(r, tmp, ws); |
344 | 30.9k | curve_mul(p32, r, p16, ws); |
345 | 30.9k | |
346 | 30.9k | curve_sqr(r, p32, ws); |
347 | 989k | for(size_t i = 0; i != 31; ++i) |
348 | 958k | curve_sqr_tmp(r, tmp, ws); |
349 | 30.9k | curve_mul_tmp(r, x, tmp, ws); |
350 | 30.9k | |
351 | 3.98M | for(size_t i = 0; i != 32*4; ++i) |
352 | 3.95M | curve_sqr_tmp(r, tmp, ws); |
353 | 30.9k | curve_mul_tmp(r, p32, tmp, ws); |
354 | 30.9k | |
355 | 1.02M | for(size_t i = 0; i != 32; ++i) |
356 | 989k | curve_sqr_tmp(r, tmp, ws); |
357 | 30.9k | curve_mul_tmp(r, p32, tmp, ws); |
358 | 30.9k | |
359 | 525k | for(size_t i = 0; i != 16; ++i) |
360 | 494k | curve_sqr_tmp(r, tmp, ws); |
361 | 30.9k | curve_mul_tmp(r, p16, tmp, ws); |
362 | 278k | for(size_t i = 0; i != 8; ++i) |
363 | 247k | curve_sqr_tmp(r, tmp, ws); |
364 | 30.9k | curve_mul_tmp(r, p8, tmp, ws); |
365 | 30.9k | |
366 | 154k | for(size_t i = 0; i != 4; ++i) |
367 | 123k | curve_sqr_tmp(r, tmp, ws); |
368 | 30.9k | curve_mul_tmp(r, p4, tmp, ws); |
369 | 30.9k | |
370 | 92.7k | for(size_t i = 0; i != 2; ++i) |
371 | 61.8k | curve_sqr_tmp(r, tmp, ws); |
372 | 30.9k | curve_mul_tmp(r, p2, tmp, ws); |
373 | 30.9k | |
374 | 92.7k | for(size_t i = 0; i != 2; ++i) |
375 | 61.8k | curve_sqr_tmp(r, tmp, ws); |
376 | 30.9k | curve_mul_tmp(r, x, tmp, ws); |
377 | 30.9k | |
378 | 30.9k | return r; |
379 | 30.9k | } |
380 | | |
381 | | /** |
382 | | * The NIST P-384 curve |
383 | | */ |
384 | | class CurveGFp_P384 final : public CurveGFp_NIST |
385 | | { |
386 | | public: |
387 | 66 | CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} |
388 | 4.10M | const BigInt& get_p() const override { return prime_p384(); } |
389 | | private: |
390 | 53.7M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); } |
391 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
392 | | }; |
393 | | |
394 | | BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const |
395 | 29.6k | { |
396 | | // From https://briansmith.org/ecc-inversion-addition-chains-01 |
397 | 29.6k | |
398 | 29.6k | BigInt r, x2, x3, x15, x30, tmp, rl; |
399 | 29.6k | |
400 | 29.6k | r = x; |
401 | 29.6k | curve_sqr_tmp(r, tmp, ws); |
402 | 29.6k | curve_mul_tmp(r, x, tmp, ws); |
403 | 29.6k | x2 = r; |
404 | 29.6k | |
405 | 29.6k | curve_sqr_tmp(r, tmp, ws); |
406 | 29.6k | curve_mul_tmp(r, x, tmp, ws); |
407 | 29.6k | |
408 | 29.6k | x3 = r; |
409 | 29.6k | |
410 | 118k | for(size_t i = 0; i != 3; ++i) |
411 | 89.0k | curve_sqr_tmp(r, tmp, ws); |
412 | 29.6k | curve_mul_tmp(r, x3, tmp, ws); |
413 | 29.6k | |
414 | 29.6k | rl = r; |
415 | 207k | for(size_t i = 0; i != 6; ++i) |
416 | 178k | curve_sqr_tmp(r, tmp, ws); |
417 | 29.6k | curve_mul_tmp(r, rl, tmp, ws); |
418 | 29.6k | |
419 | 118k | for(size_t i = 0; i != 3; ++i) |
420 | 89.0k | curve_sqr_tmp(r, tmp, ws); |
421 | 29.6k | curve_mul_tmp(r, x3, tmp, ws); |
422 | 29.6k | |
423 | 29.6k | x15 = r; |
424 | 474k | for(size_t i = 0; i != 15; ++i) |
425 | 445k | curve_sqr_tmp(r, tmp, ws); |
426 | 29.6k | curve_mul_tmp(r, x15, tmp, ws); |
427 | 29.6k | |
428 | 29.6k | x30 = r; |
429 | 919k | for(size_t i = 0; i != 30; ++i) |
430 | 890k | curve_sqr_tmp(r, tmp, ws); |
431 | 29.6k | curve_mul_tmp(r, x30, tmp, ws); |
432 | 29.6k | |
433 | 29.6k | rl = r; |
434 | 1.81M | for(size_t i = 0; i != 60; ++i) |
435 | 1.78M | curve_sqr_tmp(r, tmp, ws); |
436 | 29.6k | curve_mul_tmp(r, rl, tmp, ws); |
437 | 29.6k | |
438 | 29.6k | rl = r; |
439 | 3.59M | for(size_t i = 0; i != 120; ++i) |
440 | 3.56M | curve_sqr_tmp(r, tmp, ws); |
441 | 29.6k | curve_mul_tmp(r, rl, tmp, ws); |
442 | 29.6k | |
443 | 474k | for(size_t i = 0; i != 15; ++i) |
444 | 445k | curve_sqr_tmp(r, tmp, ws); |
445 | 29.6k | curve_mul_tmp(r, x15, tmp, ws); |
446 | 29.6k | |
447 | 949k | for(size_t i = 0; i != 31; ++i) |
448 | 919k | curve_sqr_tmp(r, tmp, ws); |
449 | 29.6k | curve_mul_tmp(r, x30, tmp, ws); |
450 | 29.6k | |
451 | 89.0k | for(size_t i = 0; i != 2; ++i) |
452 | 59.3k | curve_sqr_tmp(r, tmp, ws); |
453 | 29.6k | curve_mul_tmp(r, x2, tmp, ws); |
454 | 29.6k | |
455 | 2.81M | for(size_t i = 0; i != 94; ++i) |
456 | 2.78M | curve_sqr_tmp(r, tmp, ws); |
457 | 29.6k | curve_mul_tmp(r, x30, tmp, ws); |
458 | 29.6k | |
459 | 89.0k | for(size_t i = 0; i != 2; ++i) |
460 | 59.3k | curve_sqr_tmp(r, tmp, ws); |
461 | 29.6k | |
462 | 29.6k | curve_mul_tmp(r, x, tmp, ws); |
463 | 29.6k | |
464 | 29.6k | return r; |
465 | 29.6k | } |
466 | | |
467 | | /** |
468 | | * The NIST P-521 curve |
469 | | */ |
470 | | class CurveGFp_P521 final : public CurveGFp_NIST |
471 | | { |
472 | | public: |
473 | 286 | CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} |
474 | 11.9M | const BigInt& get_p() const override { return prime_p521(); } |
475 | | private: |
476 | 155M | void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); } |
477 | | BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override; |
478 | | }; |
479 | | |
480 | | BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const |
481 | 56.5k | { |
482 | | // Addition chain from https://eprint.iacr.org/2014/852.pdf section |
483 | 56.5k | |
484 | 56.5k | BigInt r; |
485 | 56.5k | BigInt rl; |
486 | 56.5k | BigInt a7; |
487 | 56.5k | BigInt tmp; |
488 | 56.5k | |
489 | 56.5k | curve_sqr(r, x, ws); |
490 | 56.5k | curve_mul_tmp(r, x, tmp, ws); |
491 | 56.5k | |
492 | 56.5k | curve_sqr_tmp(r, tmp, ws); |
493 | 56.5k | curve_mul_tmp(r, x, tmp, ws); |
494 | 56.5k | |
495 | 56.5k | rl = r; |
496 | 56.5k | |
497 | 226k | for(size_t i = 0; i != 3; ++i) |
498 | 169k | curve_sqr_tmp(r, tmp, ws); |
499 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
500 | 56.5k | |
501 | 56.5k | curve_sqr_tmp(r, tmp, ws); |
502 | 56.5k | curve_mul_tmp(r, x, tmp, ws); |
503 | 56.5k | a7 = r; // need this value later |
504 | 56.5k | |
505 | 56.5k | curve_sqr_tmp(r, tmp, ws); |
506 | 56.5k | curve_mul_tmp(r, x, tmp, ws); |
507 | 56.5k | |
508 | 56.5k | rl = r; |
509 | 508k | for(size_t i = 0; i != 8; ++i) |
510 | 452k | curve_sqr_tmp(r, tmp, ws); |
511 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
512 | 56.5k | |
513 | 56.5k | rl = r; |
514 | 960k | for(size_t i = 0; i != 16; ++i) |
515 | 904k | curve_sqr_tmp(r, tmp, ws); |
516 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
517 | 56.5k | |
518 | 56.5k | rl = r; |
519 | 1.86M | for(size_t i = 0; i != 32; ++i) |
520 | 1.80M | curve_sqr_tmp(r, tmp, ws); |
521 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
522 | 56.5k | |
523 | 56.5k | rl = r; |
524 | 3.67M | for(size_t i = 0; i != 64; ++i) |
525 | 3.61M | curve_sqr_tmp(r, tmp, ws); |
526 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
527 | 56.5k | |
528 | 56.5k | rl = r; |
529 | 7.28M | for(size_t i = 0; i != 128; ++i) |
530 | 7.23M | curve_sqr_tmp(r, tmp, ws); |
531 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
532 | 56.5k | |
533 | 56.5k | rl = r; |
534 | 14.5M | for(size_t i = 0; i != 256; ++i) |
535 | 14.4M | curve_sqr_tmp(r, tmp, ws); |
536 | 56.5k | curve_mul_tmp(r, rl, tmp, ws); |
537 | 56.5k | |
538 | 452k | for(size_t i = 0; i != 7; ++i) |
539 | 395k | curve_sqr_tmp(r, tmp, ws); |
540 | 56.5k | curve_mul_tmp(r, a7, tmp, ws); |
541 | 56.5k | |
542 | 169k | for(size_t i = 0; i != 2; ++i) |
543 | 113k | curve_sqr_tmp(r, tmp, ws); |
544 | 56.5k | curve_mul_tmp(r, x, tmp, ws); |
545 | 56.5k | |
546 | 56.5k | return r; |
547 | 56.5k | } |
548 | | |
549 | | } |
550 | | |
551 | | std::shared_ptr<CurveGFp_Repr> |
552 | | CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) |
553 | 1.33k | { |
554 | 1.33k | if(p == prime_p192()) |
555 | 23 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); |
556 | 1.31k | if(p == prime_p224()) |
557 | 303 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); |
558 | 1.00k | if(p == prime_p256()) |
559 | 20 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); |
560 | 988 | if(p == prime_p384()) |
561 | 66 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); |
562 | 922 | if(p == prime_p521()) |
563 | 286 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); |
564 | 636 | |
565 | 636 | return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b)); |
566 | 636 | } |
567 | | |
568 | | } |