9#include <botan/curve_gfp.h>
11#include <botan/numthry.h>
12#include <botan/reducer.h>
13#include <botan/internal/curve_nistp.h>
14#include <botan/internal/monty.h>
15#include <botan/internal/mp_core.h>
21class CurveGFp_Montgomery
final :
public CurveGFp_Repr {
23 CurveGFp_Montgomery(
const BigInt& p,
const BigInt& a,
const BigInt& b) :
24 m_p(p), m_a(a), m_b(b), m_p_words(m_p.sig_words()), m_p_dash(
monty_inverse(m_p.word_at(0))) {
25 Modular_Reducer mod_p(m_p);
28 m_r = mod_p.reduce(m_r);
30 m_r2 = mod_p.square(m_r);
31 m_r3 = mod_p.multiply(m_r, m_r2);
32 m_a_r = mod_p.multiply(m_r, m_a);
33 m_b_r = mod_p.multiply(m_r, m_b);
35 m_a_is_zero = m_a.is_zero();
36 m_a_is_minus_3 = (m_a + 3 == m_p);
39 bool a_is_zero()
const override {
return m_a_is_zero; }
41 bool a_is_minus_3()
const override {
return m_a_is_minus_3; }
43 const BigInt& get_a()
const override {
return m_a; }
45 const BigInt& get_b()
const override {
return m_b; }
47 const BigInt& get_p()
const override {
return m_p; }
49 const BigInt& get_a_rep()
const override {
return m_a_r; }
51 const BigInt& get_b_rep()
const override {
return m_b_r; }
53 const BigInt& get_1_rep()
const override {
return m_r; }
55 bool is_one(
const BigInt& x)
const override {
return x == m_r; }
57 size_t get_p_words()
const override {
return m_p_words; }
59 size_t get_ws_size()
const override {
return 2 * m_p_words; }
61 BigInt invert_element(
const BigInt& x, secure_vector<word>& ws)
const override;
63 void to_curve_rep(BigInt& x, secure_vector<word>& ws)
const override;
65 void from_curve_rep(BigInt& x, secure_vector<word>& ws)
const override;
68 BigInt& z,
const word x_words[],
size_t x_size,
const BigInt& y, secure_vector<word>& ws)
const override;
70 void curve_sqr_words(BigInt& z,
const word x_words[],
size_t x_size, secure_vector<word>& ws)
const override;
79 BigInt m_r, m_r2, m_r3;
86BigInt CurveGFp_Montgomery::invert_element(
const BigInt& x, secure_vector<word>& ws)
const {
90 curve_mul(res, inv, m_r3, ws);
94void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws)
const {
96 curve_mul(x, tx, m_r2, ws);
99void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws)
const {
100 if(ws.size() < get_ws_size()) {
101 ws.resize(get_ws_size());
104 const size_t output_size = 2 * m_p_words;
105 if(z.size() < output_size) {
106 z.grow_to(output_size);
112void CurveGFp_Montgomery::curve_mul_words(
113 BigInt& z,
const word x_w[],
size_t x_size,
const BigInt& y, secure_vector<word>& ws)
const {
116 if(ws.size() < get_ws_size()) {
117 ws.resize(get_ws_size());
120 const size_t output_size = 2 * m_p_words;
121 if(z.size() < output_size) {
122 z.grow_to(output_size);
129 std::min(m_p_words, x_size),
132 std::min(m_p_words, y.size()),
139void CurveGFp_Montgomery::curve_sqr_words(BigInt& z,
const word x[],
size_t x_size, secure_vector<word>& ws)
const {
140 if(ws.size() < get_ws_size()) {
141 ws.resize(get_ws_size());
144 const size_t output_size = 2 * m_p_words;
145 if(z.size() < output_size) {
146 z.grow_to(output_size);
149 bigint_sqr(z.mutable_data(), z.size(), x, x_size, std::min(m_p_words, x_size), ws.data(), ws.size());
154class CurveGFp_NIST :
public CurveGFp_Repr {
156 CurveGFp_NIST(
size_t p_bits,
const BigInt& a,
const BigInt& b) :
161 bool a_is_zero()
const override {
return false; }
163 bool a_is_minus_3()
const override {
return true; }
165 const BigInt& get_a()
const override {
return m_a; }
167 const BigInt& get_b()
const override {
return m_b; }
169 const BigInt& get_1_rep()
const override {
return m_1; }
171 size_t get_p_words()
const override {
return m_p_words; }
173 size_t get_ws_size()
const override {
return 2 * m_p_words; }
175 const BigInt& get_a_rep()
const override {
return m_a; }
177 const BigInt& get_b_rep()
const override {
return m_b; }
179 bool is_one(
const BigInt& x)
const override {
return x == 1; }
181 void to_curve_rep(BigInt& x, secure_vector<word>& ws)
const override { redc_mod_p(x, ws); }
183 void from_curve_rep(BigInt& x, secure_vector<word>& ws)
const override { redc_mod_p(x, ws); }
185 virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws)
const = 0;
187 BigInt invert_element(
const BigInt& x, secure_vector<word>& ws)
const override;
189 void curve_mul_words(
190 BigInt& z,
const word x_words[],
size_t x_size,
const BigInt& y, secure_vector<word>& ws)
const override;
192 void curve_mul_tmp(BigInt& x,
const BigInt& y, BigInt& tmp, secure_vector<word>& ws)
const {
193 curve_mul(tmp, x, y, ws);
197 void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws)
const {
198 curve_sqr(tmp, x, ws);
202 void curve_sqr_words(BigInt& z,
const word x_words[],
size_t x_size, secure_vector<word>& ws)
const override;
211BigInt CurveGFp_NIST::invert_element(
const BigInt& x, secure_vector<word>& ws)
const {
216void CurveGFp_NIST::curve_mul_words(
217 BigInt& z,
const word x_w[],
size_t x_size,
const BigInt& y, secure_vector<word>& ws)
const {
220 if(ws.size() < get_ws_size()) {
221 ws.resize(get_ws_size());
224 const size_t output_size = 2 * m_p_words;
225 if(z.size() < output_size) {
226 z.grow_to(output_size);
233 std::min(m_p_words, x_size),
236 std::min(m_p_words, y.size()),
240 this->redc_mod_p(z, ws);
243void CurveGFp_NIST::curve_sqr_words(BigInt& z,
const word x[],
size_t x_size, secure_vector<word>& ws)
const {
244 if(ws.size() < get_ws_size()) {
245 ws.resize(get_ws_size());
248 const size_t output_size = 2 * m_p_words;
249 if(z.size() < output_size) {
250 z.grow_to(output_size);
253 bigint_sqr(z.mutable_data(), output_size, x, x_size, std::min(m_p_words, x_size), ws.data(), ws.size());
255 this->redc_mod_p(z, ws);
261class CurveGFp_P192
final :
public CurveGFp_NIST {
263 CurveGFp_P192(
const BigInt& a,
const BigInt& b) : CurveGFp_NIST(192, a, b) {}
265 const BigInt& get_p()
const override {
return prime_p192(); }
268 void redc_mod_p(BigInt& x, secure_vector<word>& ws)
const override {
redc_p192(x, ws); }
274class CurveGFp_P224
final :
public CurveGFp_NIST {
276 CurveGFp_P224(
const BigInt& a,
const BigInt& b) : CurveGFp_NIST(224, a, b) {}
278 const BigInt& get_p()
const override {
return prime_p224(); }
281 void redc_mod_p(BigInt& x, secure_vector<word>& ws)
const override {
redc_p224(x, ws); }
287class CurveGFp_P256
final :
public CurveGFp_NIST {
289 CurveGFp_P256(
const BigInt& a,
const BigInt& b) : CurveGFp_NIST(256, a, b) {}
291 const BigInt& get_p()
const override {
return prime_p256(); }
294 void redc_mod_p(BigInt& x, secure_vector<word>& ws)
const override {
redc_p256(x, ws); }
296 BigInt invert_element(
const BigInt& x, secure_vector<word>& ws)
const override;
299BigInt CurveGFp_P256::invert_element(
const BigInt& x, secure_vector<word>& ws)
const {
300 BigInt r, p2, p4, p8, p16, p32, tmp;
304 curve_mul(p2, r, x, ws);
305 curve_sqr(r, p2, ws);
306 curve_sqr_tmp(r, tmp, ws);
308 curve_mul(p4, r, p2, ws);
310 curve_sqr(r, p4, ws);
311 for(
size_t i = 0; i != 3; ++i) {
312 curve_sqr_tmp(r, tmp, ws);
314 curve_mul(p8, r, p4, ws);
316 curve_sqr(r, p8, ws);
317 for(
size_t i = 0; i != 7; ++i) {
318 curve_sqr_tmp(r, tmp, ws);
320 curve_mul(p16, r, p8, ws);
322 curve_sqr(r, p16, ws);
323 for(
size_t i = 0; i != 15; ++i) {
324 curve_sqr_tmp(r, tmp, ws);
326 curve_mul(p32, r, p16, ws);
328 curve_sqr(r, p32, ws);
329 for(
size_t i = 0; i != 31; ++i) {
330 curve_sqr_tmp(r, tmp, ws);
332 curve_mul_tmp(r, x, tmp, ws);
334 for(
size_t i = 0; i != 32 * 4; ++i) {
335 curve_sqr_tmp(r, tmp, ws);
337 curve_mul_tmp(r, p32, tmp, ws);
339 for(
size_t i = 0; i != 32; ++i) {
340 curve_sqr_tmp(r, tmp, ws);
342 curve_mul_tmp(r, p32, tmp, ws);
344 for(
size_t i = 0; i != 16; ++i) {
345 curve_sqr_tmp(r, tmp, ws);
347 curve_mul_tmp(r, p16, tmp, ws);
348 for(
size_t i = 0; i != 8; ++i) {
349 curve_sqr_tmp(r, tmp, ws);
351 curve_mul_tmp(r, p8, tmp, ws);
353 for(
size_t i = 0; i != 4; ++i) {
354 curve_sqr_tmp(r, tmp, ws);
356 curve_mul_tmp(r, p4, tmp, ws);
358 for(
size_t i = 0; i != 2; ++i) {
359 curve_sqr_tmp(r, tmp, ws);
361 curve_mul_tmp(r, p2, tmp, ws);
363 for(
size_t i = 0; i != 2; ++i) {
364 curve_sqr_tmp(r, tmp, ws);
366 curve_mul_tmp(r, x, tmp, ws);
374class CurveGFp_P384
final :
public CurveGFp_NIST {
376 CurveGFp_P384(
const BigInt& a,
const BigInt& b) : CurveGFp_NIST(384, a, b) {}
378 const BigInt& get_p()
const override {
return prime_p384(); }
381 void redc_mod_p(BigInt& x, secure_vector<word>& ws)
const override {
redc_p384(x, ws); }
383 BigInt invert_element(
const BigInt& x, secure_vector<word>& ws)
const override;
386BigInt CurveGFp_P384::invert_element(
const BigInt& x, secure_vector<word>& ws)
const {
389 BigInt r, x2, x3, x15, x30, tmp, rl;
392 curve_sqr_tmp(r, tmp, ws);
393 curve_mul_tmp(r, x, tmp, ws);
396 curve_sqr_tmp(r, tmp, ws);
397 curve_mul_tmp(r, x, tmp, ws);
401 for(
size_t i = 0; i != 3; ++i) {
402 curve_sqr_tmp(r, tmp, ws);
404 curve_mul_tmp(r, x3, tmp, ws);
407 for(
size_t i = 0; i != 6; ++i) {
408 curve_sqr_tmp(r, tmp, ws);
410 curve_mul_tmp(r, rl, tmp, ws);
412 for(
size_t i = 0; i != 3; ++i) {
413 curve_sqr_tmp(r, tmp, ws);
415 curve_mul_tmp(r, x3, tmp, ws);
418 for(
size_t i = 0; i != 15; ++i) {
419 curve_sqr_tmp(r, tmp, ws);
421 curve_mul_tmp(r, x15, tmp, ws);
424 for(
size_t i = 0; i != 30; ++i) {
425 curve_sqr_tmp(r, tmp, ws);
427 curve_mul_tmp(r, x30, tmp, ws);
430 for(
size_t i = 0; i != 60; ++i) {
431 curve_sqr_tmp(r, tmp, ws);
433 curve_mul_tmp(r, rl, tmp, ws);
436 for(
size_t i = 0; i != 120; ++i) {
437 curve_sqr_tmp(r, tmp, ws);
439 curve_mul_tmp(r, rl, tmp, ws);
441 for(
size_t i = 0; i != 15; ++i) {
442 curve_sqr_tmp(r, tmp, ws);
444 curve_mul_tmp(r, x15, tmp, ws);
446 for(
size_t i = 0; i != 31; ++i) {
447 curve_sqr_tmp(r, tmp, ws);
449 curve_mul_tmp(r, x30, tmp, ws);
451 for(
size_t i = 0; i != 2; ++i) {
452 curve_sqr_tmp(r, tmp, ws);
454 curve_mul_tmp(r, x2, tmp, ws);
456 for(
size_t i = 0; i != 94; ++i) {
457 curve_sqr_tmp(r, tmp, ws);
459 curve_mul_tmp(r, x30, tmp, ws);
461 for(
size_t i = 0; i != 2; ++i) {
462 curve_sqr_tmp(r, tmp, ws);
465 curve_mul_tmp(r, x, tmp, ws);
473class CurveGFp_P521
final :
public CurveGFp_NIST {
475 CurveGFp_P521(
const BigInt& a,
const BigInt& b) : CurveGFp_NIST(521, a, b) {}
477 const BigInt& get_p()
const override {
return prime_p521(); }
480 void redc_mod_p(BigInt& x, secure_vector<word>& ws)
const override {
redc_p521(x, ws); }
482 BigInt invert_element(
const BigInt& x, secure_vector<word>& ws)
const override;
485BigInt CurveGFp_P521::invert_element(
const BigInt& x, secure_vector<word>& ws)
const {
494 curve_mul_tmp(r, x, tmp, ws);
496 curve_sqr_tmp(r, tmp, ws);
497 curve_mul_tmp(r, x, tmp, ws);
501 for(
size_t i = 0; i != 3; ++i) {
502 curve_sqr_tmp(r, tmp, ws);
504 curve_mul_tmp(r, rl, tmp, ws);
506 curve_sqr_tmp(r, tmp, ws);
507 curve_mul_tmp(r, x, tmp, ws);
510 curve_sqr_tmp(r, tmp, ws);
511 curve_mul_tmp(r, x, tmp, ws);
514 for(
size_t i = 0; i != 8; ++i) {
515 curve_sqr_tmp(r, tmp, ws);
517 curve_mul_tmp(r, rl, tmp, ws);
520 for(
size_t i = 0; i != 16; ++i) {
521 curve_sqr_tmp(r, tmp, ws);
523 curve_mul_tmp(r, rl, tmp, ws);
526 for(
size_t i = 0; i != 32; ++i) {
527 curve_sqr_tmp(r, tmp, ws);
529 curve_mul_tmp(r, rl, tmp, ws);
532 for(
size_t i = 0; i != 64; ++i) {
533 curve_sqr_tmp(r, tmp, ws);
535 curve_mul_tmp(r, rl, tmp, ws);
538 for(
size_t i = 0; i != 128; ++i) {
539 curve_sqr_tmp(r, tmp, ws);
541 curve_mul_tmp(r, rl, tmp, ws);
544 for(
size_t i = 0; i != 256; ++i) {
545 curve_sqr_tmp(r, tmp, ws);
547 curve_mul_tmp(r, rl, tmp, ws);
549 for(
size_t i = 0; i != 7; ++i) {
550 curve_sqr_tmp(r, tmp, ws);
552 curve_mul_tmp(r, a7, tmp, ws);
554 for(
size_t i = 0; i != 2; ++i) {
555 curve_sqr_tmp(r, tmp, ws);
557 curve_mul_tmp(r, x, tmp, ws);
564std::shared_ptr<CurveGFp_Repr> CurveGFp::choose_repr(
const BigInt& p,
const BigInt& a,
const BigInt& b) {
566 return std::make_shared<CurveGFp_P192>(a, b);
569 return std::make_shared<CurveGFp_P224>(a, b);
572 return std::make_shared<CurveGFp_P256>(a, b);
575 return std::make_shared<CurveGFp_P384>(a, b);
578 return std::make_shared<CurveGFp_P521>(a, b);
581 return std::make_shared<CurveGFp_Montgomery>(p, a, b);
#define BOTAN_DEBUG_ASSERT(expr)
const word * data() const
int(* final)(unsigned char *, CTX *)
#define BOTAN_MP_WORD_BITS
BOTAN_TEST_API void redc_p521(BigInt &x, secure_vector< word > &ws)
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
BOTAN_TEST_API void redc_p192(BigInt &x, secure_vector< word > &ws)
BOTAN_TEST_API void redc_p256(BigInt &x, secure_vector< word > &ws)
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)
constexpr auto monty_inverse(W a) -> W
BOTAN_TEST_API void redc_p224(BigInt &x, secure_vector< word > &ws)
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)
BOTAN_TEST_API const BigInt & prime_p384()
BOTAN_TEST_API const BigInt & prime_p224()
BOTAN_TEST_API void redc_p384(BigInt &x, secure_vector< word > &ws)
BOTAN_TEST_API const BigInt & prime_p256()
BOTAN_TEST_API const BigInt & prime_p192()
BOTAN_TEST_API const BigInt & prime_p521()
BigInt inverse_mod(const BigInt &n, const BigInt &mod)