Botan 3.0.0
Crypto and TLS for C&
curve_gfp.cpp
Go to the documentation of this file.
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/monty.h>
15
16namespace Botan {
17
18namespace {
19
20class 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 {
28 Modular_Reducer mod_p(m_p);
29
30 m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS);
31 m_r = mod_p.reduce(m_r);
32
33 m_r2 = mod_p.square(m_r);
34 m_r3 = mod_p.multiply(m_r, m_r2);
35 m_a_r = mod_p.multiply(m_r, m_a);
36 m_b_r = mod_p.multiply(m_r, m_b);
37
38 m_a_is_zero = m_a.is_zero();
39 m_a_is_minus_3 = (m_a + 3 == m_p);
40 }
41
42 bool a_is_zero() const override { return m_a_is_zero; }
43 bool a_is_minus_3() const override { return m_a_is_minus_3; }
44
45 const BigInt& get_a() const override { return m_a; }
46
47 const BigInt& get_b() const override { return m_b; }
48
49 const BigInt& get_p() const override { return m_p; }
50
51 const BigInt& get_a_rep() const override { return m_a_r; }
52
53 const BigInt& get_b_rep() const override { return m_b_r; }
54
55 const BigInt& get_1_rep() const override { return m_r; }
56
57 bool is_one(const BigInt& x) const override { return x == m_r; }
58
59 size_t get_p_words() const override { return m_p_words; }
60
61 size_t get_ws_size() const override { return 2*m_p_words; }
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 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
94BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
95 {
96 // Should we use Montgomery inverse instead?
97 const BigInt inv = inverse_mod(x, m_p);
98 BigInt res;
99 curve_mul(res, inv, m_r3, ws);
100 return res;
101 }
102
103void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const
104 {
105 const BigInt tx = x;
106 curve_mul(x, tx, m_r2, ws);
107 }
108
109void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const
110 {
111 if(ws.size() < get_ws_size())
112 ws.resize(get_ws_size());
113
114 const size_t output_size = 2*m_p_words;
115 if(z.size() < output_size)
116 z.grow_to(output_size);
117
118 bigint_monty_redc(z.mutable_data(),
119 m_p.data(), m_p_words, m_p_dash,
120 ws.data(), ws.size());
121 }
122
123void 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 {
129 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
130
131 if(ws.size() < get_ws_size())
132 ws.resize(get_ws_size());
133
134 const size_t output_size = 2*m_p_words;
135 if(z.size() < output_size)
136 z.grow_to(output_size);
137
138 bigint_mul(z.mutable_data(), z.size(),
139 x_w, x_size, std::min(m_p_words, x_size),
140 y.data(), y.size(), std::min(m_p_words, y.size()),
141 ws.data(), ws.size());
142
143 bigint_monty_redc(z.mutable_data(),
144 m_p.data(), m_p_words, m_p_dash,
145 ws.data(), ws.size());
146 }
147
148void CurveGFp_Montgomery::curve_sqr_words(BigInt& z,
149 const word x[],
150 size_t x_size,
151 secure_vector<word>& ws) const
152 {
153 if(ws.size() < get_ws_size())
154 ws.resize(get_ws_size());
155
156 const size_t output_size = 2*m_p_words;
157 if(z.size() < output_size)
158 z.grow_to(output_size);
159
160 bigint_sqr(z.mutable_data(), z.size(),
161 x, x_size, std::min(m_p_words, x_size),
162 ws.data(), ws.size());
163
164 bigint_monty_redc(z.mutable_data(),
165 m_p.data(), m_p_words, m_p_dash,
166 ws.data(), ws.size());
167 }
168
169class 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 {
175 // All Solinas prime curves are assumed a == -3
176 }
177
178 bool a_is_zero() const override { return false; }
179 bool a_is_minus_3() const override { return true; }
180
181 const BigInt& get_a() const override { return m_a; }
182
183 const BigInt& get_b() const override { return m_b; }
184
185 const BigInt& get_1_rep() const override { return m_1; }
186
187 size_t get_p_words() const override { return m_p_words; }
188
189 size_t get_ws_size() const override { return 2*m_p_words; }
190
191 const BigInt& get_a_rep() const override { return m_a; }
192
193 const BigInt& get_b_rep() const override { return m_b; }
194
195 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 { redc_mod_p(x, ws); }
199
200 void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
201 { 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 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 {
215 curve_mul(tmp, x, y, ws);
216 x.swap(tmp);
217 }
218
219 void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const
220 {
221 curve_sqr(tmp, x, ws);
222 x.swap(tmp);
223 }
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
236BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const
237 {
238 BOTAN_UNUSED(ws);
239 return inverse_mod(x, get_p());
240 }
241
242void 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 {
248 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
249
250 if(ws.size() < get_ws_size())
251 ws.resize(get_ws_size());
252
253 const size_t output_size = 2*m_p_words;
254 if(z.size() < output_size)
255 z.grow_to(output_size);
256
257 bigint_mul(z.mutable_data(), z.size(),
258 x_w, x_size, std::min(m_p_words, x_size),
259 y.data(), y.size(), std::min(m_p_words, y.size()),
260 ws.data(), ws.size());
261
262 this->redc_mod_p(z, ws);
263 }
264
265void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size,
266 secure_vector<word>& ws) const
267 {
268 if(ws.size() < get_ws_size())
269 ws.resize(get_ws_size());
270
271 const size_t output_size = 2*m_p_words;
272 if(z.size() < output_size)
273 z.grow_to(output_size);
274
275 bigint_sqr(z.mutable_data(), output_size,
276 x, x_size, std::min(m_p_words, x_size),
277 ws.data(), ws.size());
278
279 this->redc_mod_p(z, ws);
280 }
281
282/**
283* The NIST P-192 curve
284*/
285class CurveGFp_P192 final : public CurveGFp_NIST
286 {
287 public:
288 CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}
289 const BigInt& get_p() const override { return prime_p192(); }
290 private:
291 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*/
297class CurveGFp_P224 final : public CurveGFp_NIST
298 {
299 public:
300 CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}
301 const BigInt& get_p() const override { return prime_p224(); }
302 private:
303 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*/
309class CurveGFp_P256 final : public CurveGFp_NIST
310 {
311 public:
312 CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}
313 const BigInt& get_p() const override { return prime_p256(); }
314 private:
315 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
319BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const
320 {
321 BigInt r, p2, p4, p8, p16, p32, tmp;
322
323 curve_sqr(r, x, ws);
324
325 curve_mul(p2, r, x, ws);
326 curve_sqr(r, p2, ws);
327 curve_sqr_tmp(r, tmp, ws);
328
329 curve_mul(p4, r, p2, ws);
330
331 curve_sqr(r, p4, ws);
332 for(size_t i = 0; i != 3; ++i)
333 curve_sqr_tmp(r, tmp, ws);
334 curve_mul(p8, r, p4, ws);
335
336 curve_sqr(r, p8, ws);
337 for(size_t i = 0; i != 7; ++i)
338 curve_sqr_tmp(r, tmp, ws);
339 curve_mul(p16, r, p8, ws);
340
341 curve_sqr(r, p16, ws);
342 for(size_t i = 0; i != 15; ++i)
343 curve_sqr_tmp(r, tmp, ws);
344 curve_mul(p32, r, p16, ws);
345
346 curve_sqr(r, p32, ws);
347 for(size_t i = 0; i != 31; ++i)
348 curve_sqr_tmp(r, tmp, ws);
349 curve_mul_tmp(r, x, tmp, ws);
350
351 for(size_t i = 0; i != 32*4; ++i)
352 curve_sqr_tmp(r, tmp, ws);
353 curve_mul_tmp(r, p32, tmp, ws);
354
355 for(size_t i = 0; i != 32; ++i)
356 curve_sqr_tmp(r, tmp, ws);
357 curve_mul_tmp(r, p32, tmp, ws);
358
359 for(size_t i = 0; i != 16; ++i)
360 curve_sqr_tmp(r, tmp, ws);
361 curve_mul_tmp(r, p16, tmp, ws);
362 for(size_t i = 0; i != 8; ++i)
363 curve_sqr_tmp(r, tmp, ws);
364 curve_mul_tmp(r, p8, tmp, ws);
365
366 for(size_t i = 0; i != 4; ++i)
367 curve_sqr_tmp(r, tmp, ws);
368 curve_mul_tmp(r, p4, tmp, ws);
369
370 for(size_t i = 0; i != 2; ++i)
371 curve_sqr_tmp(r, tmp, ws);
372 curve_mul_tmp(r, p2, tmp, ws);
373
374 for(size_t i = 0; i != 2; ++i)
375 curve_sqr_tmp(r, tmp, ws);
376 curve_mul_tmp(r, x, tmp, ws);
377
378 return r;
379 }
380
381/**
382* The NIST P-384 curve
383*/
384class CurveGFp_P384 final : public CurveGFp_NIST
385 {
386 public:
387 CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}
388 const BigInt& get_p() const override { return prime_p384(); }
389 private:
390 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
394BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const
395 {
396 // From https://briansmith.org/ecc-inversion-addition-chains-01
397
398 BigInt r, x2, x3, x15, x30, tmp, rl;
399
400 r = x;
401 curve_sqr_tmp(r, tmp, ws);
402 curve_mul_tmp(r, x, tmp, ws);
403 x2 = r;
404
405 curve_sqr_tmp(r, tmp, ws);
406 curve_mul_tmp(r, x, tmp, ws);
407
408 x3 = r;
409
410 for(size_t i = 0; i != 3; ++i)
411 curve_sqr_tmp(r, tmp, ws);
412 curve_mul_tmp(r, x3, tmp, ws);
413
414 rl = r;
415 for(size_t i = 0; i != 6; ++i)
416 curve_sqr_tmp(r, tmp, ws);
417 curve_mul_tmp(r, rl, tmp, ws);
418
419 for(size_t i = 0; i != 3; ++i)
420 curve_sqr_tmp(r, tmp, ws);
421 curve_mul_tmp(r, x3, tmp, ws);
422
423 x15 = r;
424 for(size_t i = 0; i != 15; ++i)
425 curve_sqr_tmp(r, tmp, ws);
426 curve_mul_tmp(r, x15, tmp, ws);
427
428 x30 = r;
429 for(size_t i = 0; i != 30; ++i)
430 curve_sqr_tmp(r, tmp, ws);
431 curve_mul_tmp(r, x30, tmp, ws);
432
433 rl = r;
434 for(size_t i = 0; i != 60; ++i)
435 curve_sqr_tmp(r, tmp, ws);
436 curve_mul_tmp(r, rl, tmp, ws);
437
438 rl = r;
439 for(size_t i = 0; i != 120; ++i)
440 curve_sqr_tmp(r, tmp, ws);
441 curve_mul_tmp(r, rl, tmp, ws);
442
443 for(size_t i = 0; i != 15; ++i)
444 curve_sqr_tmp(r, tmp, ws);
445 curve_mul_tmp(r, x15, tmp, ws);
446
447 for(size_t i = 0; i != 31; ++i)
448 curve_sqr_tmp(r, tmp, ws);
449 curve_mul_tmp(r, x30, tmp, ws);
450
451 for(size_t i = 0; i != 2; ++i)
452 curve_sqr_tmp(r, tmp, ws);
453 curve_mul_tmp(r, x2, tmp, ws);
454
455 for(size_t i = 0; i != 94; ++i)
456 curve_sqr_tmp(r, tmp, ws);
457 curve_mul_tmp(r, x30, tmp, ws);
458
459 for(size_t i = 0; i != 2; ++i)
460 curve_sqr_tmp(r, tmp, ws);
461
462 curve_mul_tmp(r, x, tmp, ws);
463
464 return r;
465 }
466
467/**
468* The NIST P-521 curve
469*/
470class CurveGFp_P521 final : public CurveGFp_NIST
471 {
472 public:
473 CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
474 const BigInt& get_p() const override { return prime_p521(); }
475 private:
476 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
480BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const
481 {
482 // Addition chain from https://eprint.iacr.org/2014/852.pdf section
483
484 BigInt r;
485 BigInt rl;
486 BigInt a7;
487 BigInt tmp;
488
489 curve_sqr(r, x, ws);
490 curve_mul_tmp(r, x, tmp, ws);
491
492 curve_sqr_tmp(r, tmp, ws);
493 curve_mul_tmp(r, x, tmp, ws);
494
495 rl = r;
496
497 for(size_t i = 0; i != 3; ++i)
498 curve_sqr_tmp(r, tmp, ws);
499 curve_mul_tmp(r, rl, tmp, ws);
500
501 curve_sqr_tmp(r, tmp, ws);
502 curve_mul_tmp(r, x, tmp, ws);
503 a7 = r; // need this value later
504
505 curve_sqr_tmp(r, tmp, ws);
506 curve_mul_tmp(r, x, tmp, ws);
507
508 rl = r;
509 for(size_t i = 0; i != 8; ++i)
510 curve_sqr_tmp(r, tmp, ws);
511 curve_mul_tmp(r, rl, tmp, ws);
512
513 rl = r;
514 for(size_t i = 0; i != 16; ++i)
515 curve_sqr_tmp(r, tmp, ws);
516 curve_mul_tmp(r, rl, tmp, ws);
517
518 rl = r;
519 for(size_t i = 0; i != 32; ++i)
520 curve_sqr_tmp(r, tmp, ws);
521 curve_mul_tmp(r, rl, tmp, ws);
522
523 rl = r;
524 for(size_t i = 0; i != 64; ++i)
525 curve_sqr_tmp(r, tmp, ws);
526 curve_mul_tmp(r, rl, tmp, ws);
527
528 rl = r;
529 for(size_t i = 0; i != 128; ++i)
530 curve_sqr_tmp(r, tmp, ws);
531 curve_mul_tmp(r, rl, tmp, ws);
532
533 rl = r;
534 for(size_t i = 0; i != 256; ++i)
535 curve_sqr_tmp(r, tmp, ws);
536 curve_mul_tmp(r, rl, tmp, ws);
537
538 for(size_t i = 0; i != 7; ++i)
539 curve_sqr_tmp(r, tmp, ws);
540 curve_mul_tmp(r, a7, tmp, ws);
541
542 for(size_t i = 0; i != 2; ++i)
543 curve_sqr_tmp(r, tmp, ws);
544 curve_mul_tmp(r, x, tmp, ws);
545
546 return r;
547 }
548
549}
550
551std::shared_ptr<CurveGFp_Repr>
552CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b)
553 {
554 if(p == prime_p192())
555 return std::make_shared<CurveGFp_P192>(a, b);
556 if(p == prime_p224())
557 return std::make_shared<CurveGFp_P224>(a, b);
558 if(p == prime_p256())
559 return std::make_shared<CurveGFp_P256>(a, b);
560 if(p == prime_p384())
561 return std::make_shared<CurveGFp_P384>(a, b);
562 if(p == prime_p521())
563 return std::make_shared<CurveGFp_P521>(a, b);
564
565 return std::make_shared<CurveGFp_Montgomery>(p, a, b);
566 }
567
568}
y
static SIMD_4x64 y
Definition: argon2_avx2.cpp:135
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
BOTAN_UNUSED
#define BOTAN_UNUSED(...)
Definition: assert.h:141
Botan::BigInt::data
const word * data() const
Definition: bigint.h:649
final
int(* final)(unsigned char *, CTX *)
Definition: commoncrypto_hash.cpp:29
BOTAN_MP_WORD_BITS
#define BOTAN_MP_WORD_BITS
Definition: build.h:50
Botan
Definition: alg_id.cpp:12
Botan::redc_p521
BOTAN_TEST_API void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:22
Botan::bigint_monty_redc
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition: mp_core.h:823
Botan::redc_p192
BOTAN_TEST_API void redc_p192(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:112
Botan::redc_p256
BOTAN_TEST_API void redc_p256(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:313
Botan::bigint_sqr
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:356
Botan::redc_p224
BOTAN_TEST_API void redc_p224(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:209
Botan::bigint_mul
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:297
Botan::prime_p384
BOTAN_TEST_API const BigInt & prime_p384()
Definition: nistp_redc.cpp:437
Botan::monty_inverse
word monty_inverse(word a)
Definition: monty.cpp:15
Botan::prime_p224
BOTAN_TEST_API const BigInt & prime_p224()
Definition: nistp_redc.cpp:203
Botan::redc_p384
BOTAN_TEST_API void redc_p384(BigInt &x, secure_vector< word > &ws)
Definition: nistp_redc.cpp:443
Botan::prime_p256
BOTAN_TEST_API const BigInt & prime_p256()
Definition: nistp_redc.cpp:307
Botan::prime_p192
BOTAN_TEST_API const BigInt & prime_p192()
Definition: nistp_redc.cpp:106
Botan::prime_p521
BOTAN_TEST_API const BigInt & prime_p521()
Definition: nistp_redc.cpp:14
Botan::inverse_mod
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:177
Generated by doxygen 1.9.6