5123321399

Committed 30 May 2023 04:06PM UTC coverage: 92.213% (+0.004%) from 92.209%

Build # 5123321399

Build Type

Pull #3558

github

Committed by

web-flow

Commit Message

Merge dd72f7389 into 057bcbc35

Pull Request Pull Request #3558: Add braces around all if/else statements

Run Details

75602 of 81986 relevant lines covered (92.21%)

11859779.3 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.65

/src/lib/pubkey/ec_group/curve_gfp.cpp

/*
* Elliptic curves over GF(p) Montgomery Representation
* (C) 2014,2015,2018 Jack Lloyd
*     2016 Matthias Gierlings
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/curve_gfp.h>

#include <botan/numthry.h>
#include <botan/reducer.h>
#include <botan/internal/curve_nistp.h>
#include <botan/internal/monty.h>
#include <botan/internal/mp_core.h>

namespace Botan {

namespace {

class CurveGFp_Montgomery final : public CurveGFp_Repr {
   public:
      CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) :
            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))) {
         Modular_Reducer mod_p(m_p);

         m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS);
         m_r = mod_p.reduce(m_r);

         m_r2 = mod_p.square(m_r);
         m_r3 = mod_p.multiply(m_r, m_r2);
         m_a_r = mod_p.multiply(m_r, m_a);
         m_b_r = mod_p.multiply(m_r, m_b);

         m_a_is_zero = m_a.is_zero();
         m_a_is_minus_3 = (m_a + 3 == m_p);
      }

      bool a_is_zero() const override { return m_a_is_zero; }

      bool a_is_minus_3() const override { return m_a_is_minus_3; }

      const BigInt& get_a() const override { return m_a; }

      const BigInt& get_b() const override { return m_b; }

      const BigInt& get_p() const override { return m_p; }

      const BigInt& get_a_rep() const override { return m_a_r; }

      const BigInt& get_b_rep() const override { return m_b_r; }

      const BigInt& get_1_rep() const override { return m_r; }

      bool is_one(const BigInt& x) const override { return x == m_r; }

      size_t get_p_words() const override { return m_p_words; }

      size_t get_ws_size() const override { return 2 * m_p_words; }

      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;

      void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;

      void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override;

      void curve_mul_words(
         BigInt& z, const word x_words[], size_t x_size, const BigInt& y, secure_vector<word>& ws) const override;

      void curve_sqr_words(BigInt& z, const word x_words[], size_t x_size, secure_vector<word>& ws) const override;

   private:
      BigInt m_p;
      BigInt m_a, m_b;
      BigInt m_a_r, m_b_r;
      size_t m_p_words;  // cache of m_p.sig_words()

      // Montgomery parameters
      BigInt m_r, m_r2, m_r3;
      word m_p_dash;

      bool m_a_is_zero;
      bool m_a_is_minus_3;
};

BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const {
   // Should we use Montgomery inverse instead?
   const BigInt inv = inverse_mod(x, m_p);
   BigInt res;
   curve_mul(res, inv, m_r3, ws);
   return res;
}

void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const {
   const BigInt tx = x;
   curve_mul(x, tx, m_r2, ws);
}

void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector<word>& ws) const {
   if(ws.size() < get_ws_size()) {
      ws.resize(get_ws_size());
   }

   const size_t output_size = 2 * m_p_words;
   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

void CurveGFp_Montgomery::curve_mul_words(
   BigInt& z, const word x_w[], size_t x_size, const BigInt& y, secure_vector<word>& ws) const {
   BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);

   if(ws.size() < get_ws_size()) {
      ws.resize(get_ws_size());
   }

   const size_t output_size = 2 * m_p_words;
   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_mul(z.mutable_data(),
              z.size(),
              x_w,
              x_size,
              std::min(m_p_words, x_size),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws.data(),
              ws.size());

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

void CurveGFp_Montgomery::curve_sqr_words(BigInt& z, const word x[], size_t x_size, secure_vector<word>& ws) const {
   if(ws.size() < get_ws_size()) {
      ws.resize(get_ws_size());
   }

   const size_t output_size = 2 * m_p_words;
   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_sqr(z.mutable_data(), z.size(), x, x_size, std::min(m_p_words, x_size), ws.data(), ws.size());

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

class CurveGFp_NIST : public CurveGFp_Repr {
   public:
      CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
            m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) {
         // All Solinas prime curves are assumed a == -3
      }

      bool a_is_zero() const override { return false; }

      bool a_is_minus_3() const override { return true; }

      const BigInt& get_a() const override { return m_a; }

      const BigInt& get_b() const override { return m_b; }

      const BigInt& get_1_rep() const override { return m_1; }

      size_t get_p_words() const override { return m_p_words; }

      size_t get_ws_size() const override { return 2 * m_p_words; }

      const BigInt& get_a_rep() const override { return m_a; }

      const BigInt& get_b_rep() const override { return m_b; }

      bool is_one(const BigInt& x) const override { return x == 1; }

      void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override { redc_mod_p(x, ws); }

      void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override { redc_mod_p(x, ws); }

      virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0;

      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;

      void curve_mul_words(
         BigInt& z, const word x_words[], size_t x_size, const BigInt& y, secure_vector<word>& ws) const override;

      void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector<word>& ws) const {
         curve_mul(tmp, x, y, ws);
         x.swap(tmp);
      }

      void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector<word>& ws) const {
         curve_sqr(tmp, x, ws);
         x.swap(tmp);
      }

      void curve_sqr_words(BigInt& z, const word x_words[], size_t x_size, secure_vector<word>& ws) const override;

   private:
      // Curve parameters
      BigInt m_1;
      BigInt m_a, m_b;
      size_t m_p_words;  // cache of m_p.sig_words()
};

BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const {
   BOTAN_UNUSED(ws);
   return inverse_mod(x, get_p());
}

void CurveGFp_NIST::curve_mul_words(
   BigInt& z, const word x_w[], size_t x_size, const BigInt& y, secure_vector<word>& ws) const {
   BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);

   if(ws.size() < get_ws_size()) {
      ws.resize(get_ws_size());
   }

   const size_t output_size = 2 * m_p_words;
   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_mul(z.mutable_data(),
              z.size(),
              x_w,
              x_size,
              std::min(m_p_words, x_size),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws.data(),
              ws.size());

   this->redc_mod_p(z, ws);
}

void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size, secure_vector<word>& ws) const {
   if(ws.size() < get_ws_size()) {
      ws.resize(get_ws_size());
   }

   const size_t output_size = 2 * m_p_words;
   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_sqr(z.mutable_data(), output_size, x, x_size, std::min(m_p_words, x_size), ws.data(), ws.size());

   this->redc_mod_p(z, ws);
}

/**
* The NIST P-192 curve
*/
class CurveGFp_P192 final : public CurveGFp_NIST {
   public:
      CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}

      const BigInt& get_p() const override { return prime_p192(); }

   private:
      void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); }
};

/**
* The NIST P-224 curve
*/
class CurveGFp_P224 final : public CurveGFp_NIST {
   public:
      CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}

      const BigInt& get_p() const override { return prime_p224(); }

   private:
      void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); }
};

/**
* The NIST P-256 curve
*/
class CurveGFp_P256 final : public CurveGFp_NIST {
   public:
      CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}

      const BigInt& get_p() const override { return prime_p256(); }

   private:
      void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); }

      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
};

BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector<word>& ws) const {
   BigInt r, p2, p4, p8, p16, p32, tmp;

   curve_sqr(r, x, ws);

   curve_mul(p2, r, x, ws);
   curve_sqr(r, p2, ws);
   curve_sqr_tmp(r, tmp, ws);

   curve_mul(p4, r, p2, ws);

   curve_sqr(r, p4, ws);
   for(size_t i = 0; i != 3; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul(p8, r, p4, ws);

   curve_sqr(r, p8, ws);
   for(size_t i = 0; i != 7; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul(p16, r, p8, ws);

   curve_sqr(r, p16, ws);
   for(size_t i = 0; i != 15; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul(p32, r, p16, ws);

   curve_sqr(r, p32, ws);
   for(size_t i = 0; i != 31; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x, tmp, ws);

   for(size_t i = 0; i != 32 * 4; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, p32, tmp, ws);

   for(size_t i = 0; i != 32; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, p32, tmp, ws);

   for(size_t i = 0; i != 16; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, p16, tmp, ws);
   for(size_t i = 0; i != 8; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, p8, tmp, ws);

   for(size_t i = 0; i != 4; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, p4, tmp, ws);

   for(size_t i = 0; i != 2; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, p2, tmp, ws);

   for(size_t i = 0; i != 2; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x, tmp, ws);

   return r;
}

/**
* The NIST P-384 curve
*/
class CurveGFp_P384 final : public CurveGFp_NIST {
   public:
      CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}

      const BigInt& get_p() const override { return prime_p384(); }

   private:
      void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }

      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
};

BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const {
   // From https://briansmith.org/ecc-inversion-addition-chains-01

   BigInt r, x2, x3, x15, x30, tmp, rl;

   r = x;
   curve_sqr_tmp(r, tmp, ws);
   curve_mul_tmp(r, x, tmp, ws);
   x2 = r;

   curve_sqr_tmp(r, tmp, ws);
   curve_mul_tmp(r, x, tmp, ws);

   x3 = r;

   for(size_t i = 0; i != 3; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x3, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 6; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   for(size_t i = 0; i != 3; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x3, tmp, ws);

   x15 = r;
   for(size_t i = 0; i != 15; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x15, tmp, ws);

   x30 = r;
   for(size_t i = 0; i != 30; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x30, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 60; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 120; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   for(size_t i = 0; i != 15; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x15, tmp, ws);

   for(size_t i = 0; i != 31; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x30, tmp, ws);

   for(size_t i = 0; i != 2; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x2, tmp, ws);

   for(size_t i = 0; i != 94; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x30, tmp, ws);

   for(size_t i = 0; i != 2; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }

   curve_mul_tmp(r, x, tmp, ws);

   return r;
}

/**
* The NIST P-521 curve
*/
class CurveGFp_P521 final : public CurveGFp_NIST {
   public:
      CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}

      const BigInt& get_p() const override { return prime_p521(); }

   private:
      void redc_mod_p(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }

      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
};

BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const {
   // Addition chain from https://eprint.iacr.org/2014/852.pdf section

   BigInt r;
   BigInt rl;
   BigInt a7;
   BigInt tmp;

   curve_sqr(r, x, ws);
   curve_mul_tmp(r, x, tmp, ws);

   curve_sqr_tmp(r, tmp, ws);
   curve_mul_tmp(r, x, tmp, ws);

   rl = r;

   for(size_t i = 0; i != 3; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   curve_sqr_tmp(r, tmp, ws);
   curve_mul_tmp(r, x, tmp, ws);
   a7 = r;  // need this value later

   curve_sqr_tmp(r, tmp, ws);
   curve_mul_tmp(r, x, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 8; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 16; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 32; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 64; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 128; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   rl = r;
   for(size_t i = 0; i != 256; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, rl, tmp, ws);

   for(size_t i = 0; i != 7; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, a7, tmp, ws);

   for(size_t i = 0; i != 2; ++i) {
      curve_sqr_tmp(r, tmp, ws);
   }
   curve_mul_tmp(r, x, tmp, ws);

   return r;
}

}  // namespace

std::shared_ptr<CurveGFp_Repr> CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) {
   if(p == prime_p192()) {
      return std::make_shared<CurveGFp_P192>(a, b);
   }
   if(p == prime_p224()) {
      return std::make_shared<CurveGFp_P224>(a, b);
   }
   if(p == prime_p256()) {
      return std::make_shared<CurveGFp_P256>(a, b);
   }
   if(p == prime_p384()) {
      return std::make_shared<CurveGFp_P384>(a, b);
   }
   if(p == prime_p521()) {
      return std::make_shared<CurveGFp_P521>(a, b);
   }

   return std::make_shared<CurveGFp_Montgomery>(p, a, b);
}

}  // namespace Botan

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

randombit / botan / 5123321399

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous