/src/botan/src/lib/pubkey/ec_group/ec_group.cpp

Source (jump to first uncovered line)
/*
* ECC Domain Parameters
*
* (C) 2007 Falko Strenzke, FlexSecure GmbH
* (C) 2008,2018 Jack Lloyd
* (C) 2018 Tobias Niemann
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/ec_group.h>
#include <botan/internal/point_mul.h>
#include <botan/internal/primality.h>
#include <botan/ber_dec.h>
#include <botan/der_enc.h>
#include <botan/pem.h>
#include <botan/reducer.h>
#include <botan/mutex.h>
#include <botan/rng.h>
#include <vector>

namespace Botan {

class EC_Group_Data final
   {
   public:

      EC_Group_Data(const BigInt& p,
                    const BigInt& a,
                    const BigInt& b,
                    const BigInt& g_x,
                    const BigInt& g_y,
                    const BigInt& order,
                    const BigInt& cofactor,
                    const OID& oid) :
         m_curve(p, a, b),
         m_base_point(m_curve, g_x, g_y),
         m_g_x(g_x),
         m_g_y(g_y),
         m_order(order),
         m_cofactor(cofactor),
         m_mod_order(order),
         m_base_mult(m_base_point, m_mod_order),
         m_oid(oid),
         m_p_bits(p.bits()),
         m_order_bits(order.bits()),
         m_a_is_minus_3(a == p - 3),
         m_a_is_zero(a.is_zero())
         {
         }

      bool match(const BigInt& p, const BigInt& a, const BigInt& b,
                 const BigInt& g_x, const BigInt& g_y,
                 const BigInt& order, const BigInt& cofactor) const
         {
         return (this->p() == p &&
                 this->a() == a &&
                 this->b() == b &&
                 this->order() == order &&
                 this->cofactor() == cofactor &&
                 this->g_x() == g_x &&
                 this->g_y() == g_y);
         }

      void set_oid(const OID& oid)
         {
         BOTAN_STATE_CHECK(m_oid.empty());
         m_oid = oid;
         }

      const OID& oid() const { return m_oid; }
      const BigInt& p() const { return m_curve.get_p(); }
      const BigInt& a() const { return m_curve.get_a(); }
      const BigInt& b() const { return m_curve.get_b(); }
      const BigInt& order() const { return m_order; }
      const BigInt& cofactor() const { return m_cofactor; }
      const BigInt& g_x() const { return m_g_x; }
      const BigInt& g_y() const { return m_g_y; }

      size_t p_bits() const { return m_p_bits; }
      size_t p_bytes() const { return (m_p_bits + 7) / 8; }

      size_t order_bits() const { return m_order_bits; }
      size_t order_bytes() const { return (m_order_bits + 7) / 8; }

      const CurveGFp& curve() const { return m_curve; }
      const PointGFp& base_point() const { return m_base_point; }

      bool a_is_minus_3() const { return m_a_is_minus_3; }
      bool a_is_zero() const { return m_a_is_zero; }

      BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); }

      BigInt square_mod_order(const BigInt& x) const
         {
         return m_mod_order.square(x);
         }

      BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const
         {
         return m_mod_order.multiply(x, y);
         }

      BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const
         {
         return m_mod_order.multiply(m_mod_order.multiply(x, y), z);
         }

      BigInt inverse_mod_order(const BigInt& x) const
         {
         return inverse_mod(x, m_order);
         }

      PointGFp blinded_base_point_multiply(const BigInt& k,
                                           RandomNumberGenerator& rng,
                                           std::vector<BigInt>& ws) const
         {
         return m_base_mult.mul(k, rng, m_order, ws);
         }

   private:
      CurveGFp m_curve;
      PointGFp m_base_point;

      BigInt m_g_x;
      BigInt m_g_y;
      BigInt m_order;
      BigInt m_cofactor;
      Modular_Reducer m_mod_order;
      PointGFp_Base_Point_Precompute m_base_mult;
      OID m_oid;
      size_t m_p_bits;
      size_t m_order_bits;
      bool m_a_is_minus_3;
      bool m_a_is_zero;
   };

class EC_Group_Data_Map final
   {
   public:
      EC_Group_Data_Map() {}

      size_t clear()
         {
         lock_guard_type<mutex_type> lock(m_mutex);
         size_t count = m_registered_curves.size();
         m_registered_curves.clear();
         return count;
         }

      std::shared_ptr<EC_Group_Data> lookup(const OID& oid)
         {
         lock_guard_type<mutex_type> lock(m_mutex);

         for(auto i : m_registered_curves)
            {
            if(i->oid() == oid)
               return i;
            }

         // Not found, check hardcoded data
         std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);

         if(data)
            {
            m_registered_curves.push_back(data);
            return data;
            }

         // Nope, unknown curve
         return std::shared_ptr<EC_Group_Data>();
         }

      std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p,
                                                      const BigInt& a,
                                                      const BigInt& b,
                                                      const BigInt& g_x,
                                                      const BigInt& g_y,
                                                      const BigInt& order,
                                                      const BigInt& cofactor,
                                                      const OID& oid)
         {
         lock_guard_type<mutex_type> lock(m_mutex);

         for(auto i : m_registered_curves)
            {
            if(!oid.empty())
               {
               if(i->oid() == oid)
                  {
                  if(!i->match(p, a, b, g_x, g_y, order, cofactor))
                     throw Invalid_Argument("Attempting to register a curve using OID " + oid.to_string() +
                                            " but another curve is already registered using that OID");
                  return i;
                  }
               else if(i->oid().has_value())
                  continue; // distinct OIDs so not a match
               }

            if(i->match(p, a, b, g_x, g_y, order, cofactor))
               {
               /*
               * If the same curve was previously created without an OID
               * but has been registered again using an OID, save that OID.
               */
               if(oid.empty() == false)
                  {
                  if(i->oid().empty() == true)
                     {
                     i->set_oid(oid);
                     }
                  else
                     {
                     throw Invalid_Argument("Cannot register ECC group with OID " + oid.to_string() +
                                            " already registered using " + i->oid().to_string());
                     }
                  }
               return i;
               }
            }

         // Not found - if OID is set try looking up that way

         if(oid.has_value())
            {
            // Not located in existing store - try hardcoded data set
            std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);

            if(data)
               {
               m_registered_curves.push_back(data);
               return data;
               }
            }

         // Not found or no OID, add data and return
         std::shared_ptr<EC_Group_Data> d =
            std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid);

         m_registered_curves.push_back(d);
         return d;
         }

   private:
      mutex_type m_mutex;
      std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
   };

//static
EC_Group_Data_Map& EC_Group::ec_group_data()
   {
   /*
   * This exists purely to ensure the allocator is constructed before g_ec_data,
   * which ensures that its destructor runs after ~g_ec_data is complete.
   */

   static Allocator_Initializer g_init_allocator;
   static EC_Group_Data_Map g_ec_data;
   return g_ec_data;
   }

//static
size_t EC_Group::clear_registered_curve_data()
   {
   return ec_group_data().clear();
   }

//static
std::shared_ptr<EC_Group_Data>
EC_Group::load_EC_group_info(const char* p_str,
                             const char* a_str,
                             const char* b_str,
                             const char* g_x_str,
                             const char* g_y_str,
                             const char* order_str,
                             const OID& oid)
   {
   const BigInt p(p_str);
   const BigInt a(a_str);
   const BigInt b(b_str);
   const BigInt g_x(g_x_str);
   const BigInt g_y(g_y_str);
   const BigInt order(order_str);
   const BigInt cofactor(1); // implicit

   return std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid);
   }

//static
std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[], size_t len)
   {
   BER_Decoder ber(bits, len);
   BER_Object obj = ber.get_next_object();

   if(obj.type() == NULL_TAG)
      {
      throw Decoding_Error("Cannot handle ImplicitCA ECC parameters");
      }
   else if(obj.type() == OBJECT_ID)
      {
      OID dom_par_oid;
      BER_Decoder(bits, len).decode(dom_par_oid);
      return ec_group_data().lookup(dom_par_oid);
      }
   else if(obj.type() == SEQUENCE)
      {
      BigInt p, a, b, order, cofactor;
      std::vector<uint8_t> base_pt;
      std::vector<uint8_t> seed;

      BER_Decoder(bits, len)
         .start_cons(SEQUENCE)
           .decode_and_check<size_t>(1, "Unknown ECC param version code")
           .start_cons(SEQUENCE)
            .decode_and_check(OID("1.2.840.10045.1.1"),
                              "Only prime ECC fields supported")
             .decode(p)
           .end_cons()
           .start_cons(SEQUENCE)
             .decode_octet_string_bigint(a)
             .decode_octet_string_bigint(b)
             .decode_optional_string(seed, BIT_STRING, BIT_STRING)
           .end_cons()
           .decode(base_pt, OCTET_STRING)
           .decode(order)
           .decode(cofactor)
         .end_cons()
         .verify_end();

      if(p.bits() < 64 || p.is_negative() || !is_bailie_psw_probable_prime(p))
         throw Decoding_Error("Invalid ECC p parameter");

      if(a.is_negative() || a >= p)
         throw Decoding_Error("Invalid ECC a parameter");

      if(b <= 0 || b >= p)
         throw Decoding_Error("Invalid ECC b parameter");

      if(order <= 0 || !is_bailie_psw_probable_prime(order))
         throw Decoding_Error("Invalid ECC order parameter");

      if(cofactor <= 0 || cofactor >= 16)
         throw Decoding_Error("Invalid ECC cofactor parameter");

      std::pair<BigInt, BigInt> base_xy = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b);

      return ec_group_data().lookup_or_create(p, a, b, base_xy.first, base_xy.second, order, cofactor, OID());
      }
   else
      {
      throw Decoding_Error("Unexpected tag while decoding ECC domain params");
      }
   }

EC_Group::EC_Group()
   {
   }

EC_Group::~EC_Group()
   {
   // shared_ptr possibly freed here
   }

EC_Group::EC_Group(const OID& domain_oid)
   {
   this->m_data = ec_group_data().lookup(domain_oid);
   if(!this->m_data)
      throw Invalid_Argument("Unknown EC_Group " + domain_oid.to_string());
   }

EC_Group::EC_Group(const std::string& str)
   {
   if(str == "")
      return; // no initialization / uninitialized

   try
      {
      const OID oid = OID::from_string(str);
      if(oid.has_value())
         m_data = ec_group_data().lookup(oid);
      }
   catch(...)
      {
      }

   if(m_data == nullptr)
      {
      if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----")
         {
         // OK try it as PEM ...
         secure_vector<uint8_t> ber = PEM_Code::decode_check_label(str, "EC PARAMETERS");
         this->m_data = BER_decode_EC_group(ber.data(), ber.size());
         }
      }

   if(m_data == nullptr)
      throw Invalid_Argument("Unknown ECC group '" + str + "'");
   }

//static
std::string EC_Group::PEM_for_named_group(const std::string& name)
   {
   try
      {
      EC_Group group(name);
      return group.PEM_encode();
      }
   catch(...)
      {
      return "";
      }
   }

EC_Group::EC_Group(const BigInt& p,
                   const BigInt& a,
                   const BigInt& b,
                   const BigInt& base_x,
                   const BigInt& base_y,
                   const BigInt& order,
                   const BigInt& cofactor,
                   const OID& oid)
   {
   m_data = ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid);
   }

EC_Group::EC_Group(const std::vector<uint8_t>& ber)
   {
   m_data = BER_decode_EC_group(ber.data(), ber.size());
   }

const EC_Group_Data& EC_Group::data() const
   {
   if(m_data == nullptr)
      throw Invalid_State("EC_Group uninitialized");
   return *m_data;
   }

const CurveGFp& EC_Group::get_curve() const
   {
   return data().curve();
   }

bool EC_Group::a_is_minus_3() const
   {
   return data().a_is_minus_3();
   }

bool EC_Group::a_is_zero() const
   {
   return data().a_is_zero();
   }

size_t EC_Group::get_p_bits() const
   {
   return data().p_bits();
   }

size_t EC_Group::get_p_bytes() const
   {
   return data().p_bytes();
   }

size_t EC_Group::get_order_bits() const
   {
   return data().order_bits();
   }

size_t EC_Group::get_order_bytes() const
   {
   return data().order_bytes();
   }

const BigInt& EC_Group::get_p() const
   {
   return data().p();
   }

const BigInt& EC_Group::get_a() const
   {
   return data().a();
   }

const BigInt& EC_Group::get_b() const
   {
   return data().b();
   }

const PointGFp& EC_Group::get_base_point() const
   {
   return data().base_point();
   }

const BigInt& EC_Group::get_order() const
   {
   return data().order();
   }

const BigInt& EC_Group::get_g_x() const
   {
   return data().g_x();
   }

const BigInt& EC_Group::get_g_y() const
   {
   return data().g_y();
   }

const BigInt& EC_Group::get_cofactor() const
   {
   return data().cofactor();
   }

BigInt EC_Group::mod_order(const BigInt& k) const
   {
   return data().mod_order(k);
   }

BigInt EC_Group::square_mod_order(const BigInt& x) const
   {
   return data().square_mod_order(x);
   }

BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const
   {
   return data().multiply_mod_order(x, y);
   }

BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const
   {
   return data().multiply_mod_order(x, y, z);
   }

BigInt EC_Group::inverse_mod_order(const BigInt& x) const
   {
   return data().inverse_mod_order(x);
   }

const OID& EC_Group::get_curve_oid() const
   {
   return data().oid();
   }

size_t EC_Group::point_size(PointGFp::Compression_Type format) const
   {
   // Hybrid and standard format are (x,y), compressed is y, +1 format byte
   if(format == PointGFp::COMPRESSED)
      return (1 + get_p_bytes());
   else
      return (1 + 2*get_p_bytes());
   }

PointGFp EC_Group::OS2ECP(const uint8_t bits[], size_t len) const
   {
   return Botan::OS2ECP(bits, len, data().curve());
   }

PointGFp EC_Group::point(const BigInt& x, const BigInt& y) const
   {
   // TODO: randomize the representation?
   return PointGFp(data().curve(), x, y);
   }

PointGFp EC_Group::point_multiply(const BigInt& x, const PointGFp& pt, const BigInt& y) const
   {
   PointGFp_Multi_Point_Precompute xy_mul(get_base_point(), pt);
   return xy_mul.multi_exp(x, y);
   }

PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k,
                                               RandomNumberGenerator& rng,
                                               std::vector<BigInt>& ws) const
   {
   return data().blinded_base_point_multiply(k, rng, ws);
   }

BigInt EC_Group::blinded_base_point_multiply_x(const BigInt& k,
                                               RandomNumberGenerator& rng,
                                               std::vector<BigInt>& ws) const
   {
   const PointGFp pt = data().blinded_base_point_multiply(k, rng, ws);

   if(pt.is_zero())
      return 0;
   return pt.get_affine_x();
   }

BigInt EC_Group::random_scalar(RandomNumberGenerator& rng) const
   {
   return BigInt::random_integer(rng, 1, get_order());
   }

PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point,
                                              const BigInt& k,
                                              RandomNumberGenerator& rng,
                                              std::vector<BigInt>& ws) const
   {
   PointGFp_Var_Point_Precompute mul(point, rng, ws);
   return mul.mul(k, rng, get_order(), ws);
   }

PointGFp EC_Group::zero_point() const
   {
   return PointGFp(data().curve());
   }

std::vector<uint8_t>
EC_Group::DER_encode(EC_Group_Encoding form) const
   {
   std::vector<uint8_t> output;

   DER_Encoder der(output);

   if(form == EC_DOMPAR_ENC_EXPLICIT)
      {
      const size_t ecpVers1 = 1;
      const OID curve_type("1.2.840.10045.1.1"); // prime field

      const size_t p_bytes = get_p_bytes();

      der.start_cons(SEQUENCE)
            .encode(ecpVers1)
            .start_cons(SEQUENCE)
               .encode(curve_type)
               .encode(get_p())
            .end_cons()
            .start_cons(SEQUENCE)
               .encode(BigInt::encode_1363(get_a(), p_bytes),
                       OCTET_STRING)
               .encode(BigInt::encode_1363(get_b(), p_bytes),
                       OCTET_STRING)
            .end_cons()
              .encode(get_base_point().encode(PointGFp::UNCOMPRESSED), OCTET_STRING)
            .encode(get_order())
            .encode(get_cofactor())
         .end_cons();
      }
   else if(form == EC_DOMPAR_ENC_OID)
      {
      const OID oid = get_curve_oid();
      if(oid.empty())
         {
         throw Encoding_Error("Cannot encode EC_Group as OID because OID not set");
         }
      der.encode(oid);
      }
   else if(form == EC_DOMPAR_ENC_IMPLICITCA)
      {
      der.encode_null();
      }
   else
      {
      throw Internal_Error("EC_Group::DER_encode: Unknown encoding");
      }

   return output;
   }

std::string EC_Group::PEM_encode() const
   {
   const std::vector<uint8_t> der = DER_encode(EC_DOMPAR_ENC_EXPLICIT);
   return PEM_Code::encode(der, "EC PARAMETERS");
   }

bool EC_Group::operator==(const EC_Group& other) const
   {
   if(m_data == other.m_data)
      return true; // same shared rep

   /*
   * No point comparing order/cofactor as they are uniquely determined
   * by the curve equation (p,a,b) and the base point.
   */
   return (get_p() == other.get_p() &&
           get_a() == other.get_a() &&
           get_b() == other.get_b() &&
           get_g_x() == other.get_g_x() &&
           get_g_y() == other.get_g_y());
   }

bool EC_Group::verify_public_element(const PointGFp& point) const
   {
   //check that public point is not at infinity
   if(point.is_zero())
      return false;

   //check that public point is on the curve
   if(point.on_the_curve() == false)
      return false;

   //check that public point has order q
   if((point * get_order()).is_zero() == false)
      return false;

   if(get_cofactor() > 1)
      {
      if((point * get_cofactor()).is_zero())
         return false;
      }

   return true;
   }

bool EC_Group::verify_group(RandomNumberGenerator& rng,
                            bool) const
   {
   const BigInt& p = get_p();
   const BigInt& a = get_a();
   const BigInt& b = get_b();
   const BigInt& order = get_order();
   const PointGFp& base_point = get_base_point();

   if(a < 0 || a >= p)
      return false;
   if(b <= 0 || b >= p)
      return false;
   if(order <= 0)
      return false;

   //check if field modulus is prime
   if(!is_prime(p, rng, 128))
      {
      return false;
      }

   //check if order is prime
   if(!is_prime(order, rng, 128))
      {
      return false;
      }

   //compute the discriminant: 4*a^3 + 27*b^2 which must be nonzero
   const Modular_Reducer mod_p(p);

   const BigInt discriminant = mod_p.reduce(
      mod_p.multiply(4, mod_p.cube(a)) +
      mod_p.multiply(27, mod_p.square(b)));

   if(discriminant == 0)
      {
      return false;
      }

   //check for valid cofactor
   if(get_cofactor() < 1)
      {
      return false;
      }

   //check if the base point is on the curve
   if(!base_point.on_the_curve())
      {
      return false;
      }
   if((base_point * get_cofactor()).is_zero())
      {
      return false;
      }
   //check if order of the base point is correct
   if(!(base_point * order).is_zero())
      {
      return false;
      }

   return true;
   }

}

Coverage Report

Created: 2020-05-23 13:54

Line	Count	Source (jump to first uncovered line)
1		/*
2		* ECC Domain Parameters
3		*
4		* (C) 2007 Falko Strenzke, FlexSecure GmbH
5		* (C) 2008,2018 Jack Lloyd
6		* (C) 2018 Tobias Niemann
7		*
8		* Botan is released under the Simplified BSD License (see license.txt)
9		*/
10
11		#include <botan/ec_group.h>
12		#include <botan/internal/point_mul.h>
13		#include <botan/internal/primality.h>
14		#include <botan/ber_dec.h>
15		#include <botan/der_enc.h>
16		#include <botan/pem.h>
17		#include <botan/reducer.h>
18		#include <botan/mutex.h>
19		#include <botan/rng.h>
20		#include <vector>
21
22		namespace Botan {
23
24		class EC_Group_Data final
25		{
26		public:
27
28		EC_Group_Data(const BigInt& p,
29		const BigInt& a,
30		const BigInt& b,
31		const BigInt& g_x,
32		const BigInt& g_y,
33		const BigInt& order,
34		const BigInt& cofactor,
35		const OID& oid) :
36		m_curve(p, a, b),
37		m_base_point(m_curve, g_x, g_y),
38		m_g_x(g_x),
39		m_g_y(g_y),
40		m_order(order),
41		m_cofactor(cofactor),
42		m_mod_order(order),
43		m_base_mult(m_base_point, m_mod_order),
44		m_oid(oid),
45		m_p_bits(p.bits()),
46		m_order_bits(order.bits()),
47		m_a_is_minus_3(a == p - 3),
48		m_a_is_zero(a.is_zero())
49	1.21k	{
50	1.21k	}
51
52		bool match(const BigInt& p, const BigInt& a, const BigInt& b,
53		const BigInt& g_x, const BigInt& g_y,
54		const BigInt& order, const BigInt& cofactor) const
55	0	{
56	0	return (this->p() == p &&
57	0	this->a() == a &&
58	0	this->b() == b &&
59	0	this->order() == order &&
60	0	this->cofactor() == cofactor &&
61	0	this->g_x() == g_x &&
62	0	this->g_y() == g_y);
63	0	}
64
65		void set_oid(const OID& oid)
66	0	{
67	0	BOTAN_STATE_CHECK(m_oid.empty());
68	0	m_oid = oid;
69	0	}
70
71	68.8k	const OID& oid() const { return m_oid; }
72	2.59k	const BigInt& p() const { return m_curve.get_p(); }
73	2.59k	const BigInt& a() const { return m_curve.get_a(); }
74	2.59k	const BigInt& b() const { return m_curve.get_b(); }
75	37.2k	const BigInt& order() const { return m_order; }
76	21.0k	const BigInt& cofactor() const { return m_cofactor; }
77	0	const BigInt& g_x() const { return m_g_x; }
78	0	const BigInt& g_y() const { return m_g_y; }
79
80	332	size_t p_bits() const { return m_p_bits; }
81	8.95k	size_t p_bytes() const { return (m_p_bits + 7) / 8; }
82
83	746	size_t order_bits() const { return m_order_bits; }
84	373	size_t order_bytes() const { return (m_order_bits + 7) / 8; }
85
86	22.8k	const CurveGFp& curve() const { return m_curve; }
87	1.41k	const PointGFp& base_point() const { return m_base_point; }
88
89	0	bool a_is_minus_3() const { return m_a_is_minus_3; }
90	0	bool a_is_zero() const { return m_a_is_zero; }
91
92	708	BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); }
93
94		BigInt square_mod_order(const BigInt& x) const
95	0	{
96	0	return m_mod_order.square(x);
97	0	}
98
99		BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const
100	726	{
101	726	return m_mod_order.multiply(x, y);
102	726	}
103
104		BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const
105	0	{
106	0	return m_mod_order.multiply(m_mod_order.multiply(x, y), z);
107	0	}
108
109		BigInt inverse_mod_order(const BigInt& x) const
110	10.9k	{
111	10.9k	return inverse_mod(x, m_order);
112	10.9k	}
113
114		PointGFp blinded_base_point_multiply(const BigInt& k,
115		RandomNumberGenerator& rng,
116		std::vector<BigInt>& ws) const
117	23.7k	{
118	23.7k	return m_base_mult.mul(k, rng, m_order, ws);
119	23.7k	}
120
121		private:
122		CurveGFp m_curve;
123		PointGFp m_base_point;
124
125		BigInt m_g_x;
126		BigInt m_g_y;
127		BigInt m_order;
128		BigInt m_cofactor;
129		Modular_Reducer m_mod_order;
130		PointGFp_Base_Point_Precompute m_base_mult;
131		OID m_oid;
132		size_t m_p_bits;
133		size_t m_order_bits;
134		bool m_a_is_minus_3;
135		bool m_a_is_zero;
136		};
137
138		class EC_Group_Data_Map final
139		{
140		public:
141	9	EC_Group_Data_Map() {}
142
143		size_t clear()
144	2.95k	{
145	2.95k	lock_guard_type<mutex_type> lock(m_mutex);
146	2.95k	size_t count = m_registered_curves.size();
147	2.95k	m_registered_curves.clear();
148	2.95k	return count;
149	2.95k	}
150
151		std::shared_ptr<EC_Group_Data> lookup(const OID& oid)
152	19.1k	{
153	19.1k	lock_guard_type<mutex_type> lock(m_mutex);
154	19.1k
155	19.1k	for(auto i : m_registered_curves)
156	50.1k	{
157	50.1k	if(i->oid() == oid)
158	18.0k	return i;
159	50.1k	}
160	19.1k
161	19.1k	// Not found, check hardcoded data
162	19.1k	std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);
163	1.13k
164	1.13k	if(data)
165	1.03k	{
166	1.03k	m_registered_curves.push_back(data);
167	1.03k	return data;
168	1.03k	}
169	100
170	100	// Nope, unknown curve
171	100	return std::shared_ptr<EC_Group_Data>();
172	100	}
173
174		std::shared_ptr<EC_Group_Data> lookup_or_create(const BigInt& p,
175		const BigInt& a,
176		const BigInt& b,
177		const BigInt& g_x,
178		const BigInt& g_y,
179		const BigInt& order,
180		const BigInt& cofactor,
181		const OID& oid)
182	178	{
183	178	lock_guard_type<mutex_type> lock(m_mutex);
184	178
185	178	for(auto i : m_registered_curves)
186	0	{
187	0	if(!oid.empty())
188	0	{
189	0	if(i->oid() == oid)
190	0	{
191	0	if(!i->match(p, a, b, g_x, g_y, order, cofactor))
192	0	throw Invalid_Argument("Attempting to register a curve using OID " + oid.to_string() +
193	0	" but another curve is already registered using that OID");
194	0	return i;
195	0	}
196	0	else if(i->oid().has_value())
197	0	continue; // distinct OIDs so not a match
198	0	}
199	0
200	0	if(i->match(p, a, b, g_x, g_y, order, cofactor))
201	0	{
202	0	/*
203	0	* If the same curve was previously created without an OID
204	0	* but has been registered again using an OID, save that OID.
205	0	*/
206	0	if(oid.empty() == false)
207	0	{
208	0	if(i->oid().empty() == true)
209	0	{
210	0	i->set_oid(oid);
211	0	}
212	0	else
213	0	{
214	0	throw Invalid_Argument("Cannot register ECC group with OID " + oid.to_string() +
215	0	" already registered using " + i->oid().to_string());
216	0	}
217	0	}
218	0	return i;
219	0	}
220	0	}
221	178
222	178	// Not found - if OID is set try looking up that way
223	178
224	178	if(oid.has_value())
225	0	{
226	0	// Not located in existing store - try hardcoded data set
227	0	std::shared_ptr<EC_Group_Data> data = EC_Group::EC_group_info(oid);
228	0
229	0	if(data)
230	0	{
231	0	m_registered_curves.push_back(data);
232	0	return data;
233	0	}
234	178	}
235	178
236	178	// Not found or no OID, add data and return
237	178	std::shared_ptr<EC_Group_Data> d =
238	178	std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid);
239	178
240	178	m_registered_curves.push_back(d);
241	178	return d;
242	178	}
243
244		private:
245		mutex_type m_mutex;
246		std::vector<std::shared_ptr<EC_Group_Data>> m_registered_curves;
247		};
248
249		//static
250		EC_Group_Data_Map& EC_Group::ec_group_data()
251	22.3k	{
252	22.3k	/*
253	22.3k	* This exists purely to ensure the allocator is constructed before g_ec_data,
254	22.3k	* which ensures that its destructor runs after ~g_ec_data is complete.
255	22.3k	*/
256	22.3k
257	22.3k	static Allocator_Initializer g_init_allocator;
258	22.3k	static EC_Group_Data_Map g_ec_data;
259	22.3k	return g_ec_data;
260	22.3k	}
261
262		//static
263		size_t EC_Group::clear_registered_curve_data()
264	2.95k	{
265	2.95k	return ec_group_data().clear();
266	2.95k	}
267
268		//static
269		std::shared_ptr<EC_Group_Data>
270		EC_Group::load_EC_group_info(const char* p_str,
271		const char* a_str,
272		const char* b_str,
273		const char* g_x_str,
274		const char* g_y_str,
275		const char* order_str,
276		const OID& oid)
277	1.03k	{
278	1.03k	const BigInt p(p_str);
279	1.03k	const BigInt a(a_str);
280	1.03k	const BigInt b(b_str);
281	1.03k	const BigInt g_x(g_x_str);
282	1.03k	const BigInt g_y(g_y_str);
283	1.03k	const BigInt order(order_str);
284	1.03k	const BigInt cofactor(1); // implicit
285	1.03k
286	1.03k	return std::make_shared<EC_Group_Data>(p, a, b, g_x, g_y, order, cofactor, oid);
287	1.03k	}
288
289		//static
290		std::shared_ptr<EC_Group_Data> EC_Group::BER_decode_EC_group(const uint8_t bits[], size_t len)
291	3.86k	{
292	3.86k	BER_Decoder ber(bits, len);
293	3.86k	BER_Object obj = ber.get_next_object();
294	3.86k
295	3.86k	if(obj.type() == NULL_TAG)
296	8	{
297	8	throw Decoding_Error("Cannot handle ImplicitCA ECC parameters");
298	8	}
299	3.85k	else if(obj.type() == OBJECT_ID)
300	3.26k	{
301	3.26k	OID dom_par_oid;
302	3.26k	BER_Decoder(bits, len).decode(dom_par_oid);
303	3.26k	return ec_group_data().lookup(dom_par_oid);
304	3.26k	}
305	592	else if(obj.type() == SEQUENCE)
306	440	{
307	440	BigInt p, a, b, order, cofactor;
308	440	std::vector<uint8_t> base_pt;
309	440	std::vector<uint8_t> seed;
310	440
311	440	BER_Decoder(bits, len)
312	440	.start_cons(SEQUENCE)
313	440	.decode_and_check<size_t>(1, "Unknown ECC param version code")
314	440	.start_cons(SEQUENCE)
315	440	.decode_and_check(OID("1.2.840.10045.1.1"),
316	440	"Only prime ECC fields supported")
317	440	.decode(p)
318	440	.end_cons()
319	440	.start_cons(SEQUENCE)
320	440	.decode_octet_string_bigint(a)
321	440	.decode_octet_string_bigint(b)
322	440	.decode_optional_string(seed, BIT_STRING, BIT_STRING)
323	440	.end_cons()
324	440	.decode(base_pt, OCTET_STRING)
325	440	.decode(order)
326	440	.decode(cofactor)
327	440	.end_cons()
328	440	.verify_end();
329	440
330	440	if(p.bits() < 64 \|\| p.is_negative() \|\| !is_bailie_psw_probable_prime(p))
331	18	throw Decoding_Error("Invalid ECC p parameter");
332	422
333	422	if(a.is_negative() \|\| a >= p)
334	19	throw Decoding_Error("Invalid ECC a parameter");
335	403
336	403	if(b <= 0 \|\| b >= p)
337	4	throw Decoding_Error("Invalid ECC b parameter");
338	399
339	399	if(order <= 0 \|\| !is_bailie_psw_probable_prime(order))
340	24	throw Decoding_Error("Invalid ECC order parameter");
341	375
342	375	if(cofactor <= 0 \|\| cofactor >= 16)
343	14	throw Decoding_Error("Invalid ECC cofactor parameter");
344	361
345	361	std::pair<BigInt, BigInt> base_xy = Botan::OS2ECP(base_pt.data(), base_pt.size(), p, a, b);
346	361
347	361	return ec_group_data().lookup_or_create(p, a, b, base_xy.first, base_xy.second, order, cofactor, OID());
348	361	}
349	152	else
350	152	{
351	152	throw Decoding_Error("Unexpected tag while decoding ECC domain params");
352	152	}
353	3.86k	}
354
355		EC_Group::EC_Group()
356	17.3k	{
357	17.3k	}
358
359		EC_Group::~EC_Group()
360	48.4k	{
361	48.4k	// shared_ptr possibly freed here
362	48.4k	}
363
364		EC_Group::EC_Group(const OID& domain_oid)
365	113	{
366	113	this->m_data = ec_group_data().lookup(domain_oid);
367	113	if(!this->m_data)
368	0	throw Invalid_Argument("Unknown EC_Group " + domain_oid.to_string());
369	113	}
370
371		EC_Group::EC_Group(const std::string& str)
372	15.8k	{
373	15.8k	if(str == "")
374	0	return; // no initialization / uninitialized
375	15.8k
376	15.8k	try
377	15.8k	{
378	15.8k	const OID oid = OID::from_string(str);
379	15.8k	if(oid.has_value())
380	15.8k	m_data = ec_group_data().lookup(oid);
381	15.8k	}
382	15.8k	catch(...)
383	15.8k	{
384	0	}
385	15.8k
386	15.8k	if(m_data == nullptr)
387	0	{
388	0	if(str.size() > 30 && str.substr(0, 29) == "-----BEGIN EC PARAMETERS-----")
389	0	{
390	0	// OK try it as PEM ...
391	0	secure_vector<uint8_t> ber = PEM_Code::decode_check_label(str, "EC PARAMETERS");
392	0	this->m_data = BER_decode_EC_group(ber.data(), ber.size());
393	0	}
394	0	}
395	15.8k
396	15.8k	if(m_data == nullptr)
397	0	throw Invalid_Argument("Unknown ECC group '" + str + "'");
398	15.8k	}
399
400		//static
401		std::string EC_Group::PEM_for_named_group(const std::string& name)
402	0	{
403	0	try
404	0	{
405	0	EC_Group group(name);
406	0	return group.PEM_encode();
407	0	}
408	0	catch(...)
409	0	{
410	0	return "";
411	0	}
412	0	}
413
414		EC_Group::EC_Group(const BigInt& p,
415		const BigInt& a,
416		const BigInt& b,
417		const BigInt& base_x,
418		const BigInt& base_y,
419		const BigInt& order,
420		const BigInt& cofactor,
421		const OID& oid)
422	0	{
423	0	m_data = ec_group_data().lookup_or_create(p, a, b, base_x, base_y, order, cofactor, oid);
424	0	}
425
426		EC_Group::EC_Group(const std::vector<uint8_t>& ber)
427	3.86k	{
428	3.86k	m_data = BER_decode_EC_group(ber.data(), ber.size());
429	3.86k	}
430
431		const EC_Group_Data& EC_Group::data() const
432	155k	{
433	155k	if(m_data == nullptr)
434	100	throw Invalid_State("EC_Group uninitialized");
435	155k	return *m_data;
436	155k	}
437
438		const CurveGFp& EC_Group::get_curve() const
439	0	{
440	0	return data().curve();
441	0	}
442
443		bool EC_Group::a_is_minus_3() const
444	0	{
445	0	return data().a_is_minus_3();
446	0	}
447
448		bool EC_Group::a_is_zero() const
449	0	{
450	0	return data().a_is_zero();
451	0	}
452
453		size_t EC_Group::get_p_bits() const
454	332	{
455	332	return data().p_bits();
456	332	}
457
458		size_t EC_Group::get_p_bytes() const
459	8.95k	{
460	8.95k	return data().p_bytes();
461	8.95k	}
462
463		size_t EC_Group::get_order_bits() const
464	746	{
465	746	return data().order_bits();
466	746	}
467
468		size_t EC_Group::get_order_bytes() const
469	373	{
470	373	return data().order_bytes();
471	373	}
472
473		const BigInt& EC_Group::get_p() const
474	2.59k	{
475	2.59k	return data().p();
476	2.59k	}
477
478		const BigInt& EC_Group::get_a() const
479	2.59k	{
480	2.59k	return data().a();
481	2.59k	}
482
483		const BigInt& EC_Group::get_b() const
484	2.59k	{
485	2.59k	return data().b();
486	2.59k	}
487
488		const PointGFp& EC_Group::get_base_point() const
489	1.41k	{
490	1.41k	return data().base_point();
491	1.41k	}
492
493		const BigInt& EC_Group::get_order() const
494	37.2k	{
495	37.2k	return data().order();
496	37.2k	}
497
498		const BigInt& EC_Group::get_g_x() const
499	0	{
500	0	return data().g_x();
501	0	}
502
503		const BigInt& EC_Group::get_g_y() const
504	0	{
505	0	return data().g_y();
506	0	}
507
508		const BigInt& EC_Group::get_cofactor() const
509	21.0k	{
510	21.0k	return data().cofactor();
511	21.0k	}
512
513		BigInt EC_Group::mod_order(const BigInt& k) const
514	708	{
515	708	return data().mod_order(k);
516	708	}
517
518		BigInt EC_Group::square_mod_order(const BigInt& x) const
519	0	{
520	0	return data().square_mod_order(x);
521	0	}
522
523		BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const
524	726	{
525	726	return data().multiply_mod_order(x, y);
526	726	}
527
528		BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const
529	0	{
530	0	return data().multiply_mod_order(x, y, z);
531	0	}
532
533		BigInt EC_Group::inverse_mod_order(const BigInt& x) const
534	10.9k	{
535	10.9k	return data().inverse_mod_order(x);
536	10.9k	}
537
538		const OID& EC_Group::get_curve_oid() const
539	18.7k	{
540	18.7k	return data().oid();
541	18.7k	}
542
543		size_t EC_Group::point_size(PointGFp::Compression_Type format) const
544	0	{
545	0	// Hybrid and standard format are (x,y), compressed is y, +1 format byte
546	0	if(format == PointGFp::COMPRESSED)
547	0	return (1 + get_p_bytes());
548	0	else
549	0	return (1 + 2*get_p_bytes());
550	0	}
551
552		PointGFp EC_Group::OS2ECP(const uint8_t bits[], size_t len) const
553	20.0k	{
554	20.0k	return Botan::OS2ECP(bits, len, data().curve());
555	20.0k	}
556
557		PointGFp EC_Group::point(const BigInt& x, const BigInt& y) const
558	2.83k	{
559	2.83k	// TODO: randomize the representation?
560	2.83k	return PointGFp(data().curve(), x, y);
561	2.83k	}
562
563		PointGFp EC_Group::point_multiply(const BigInt& x, const PointGFp& pt, const BigInt& y) const
564	0	{
565	0	PointGFp_Multi_Point_Precompute xy_mul(get_base_point(), pt);
566	0	return xy_mul.multi_exp(x, y);
567	0	}
568
569		PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k,
570		RandomNumberGenerator& rng,
571		std::vector<BigInt>& ws) const
572	23.7k	{
573	23.7k	return data().blinded_base_point_multiply(k, rng, ws);
574	23.7k	}
575
576		BigInt EC_Group::blinded_base_point_multiply_x(const BigInt& k,
577		RandomNumberGenerator& rng,
578		std::vector<BigInt>& ws) const
579	0	{
580	0	const PointGFp pt = data().blinded_base_point_multiply(k, rng, ws);
581	0
582	0	if(pt.is_zero())
583	0	return 0;
584	0	return pt.get_affine_x();
585	0	}
586
587		BigInt EC_Group::random_scalar(RandomNumberGenerator& rng) const
588	15.9k	{
589	15.9k	return BigInt::random_integer(rng, 1, get_order());
590	15.9k	}
591
592		PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point,
593		const BigInt& k,
594		RandomNumberGenerator& rng,
595		std::vector<BigInt>& ws) const
596	19.4k	{
597	19.4k	PointGFp_Var_Point_Precompute mul(point, rng, ws);
598	19.4k	return mul.mul(k, rng, get_order(), ws);
599	19.4k	}
600
601		PointGFp EC_Group::zero_point() const
602	0	{
603	0	return PointGFp(data().curve());
604	0	}
605
606		std::vector<uint8_t>
607		EC_Group::DER_encode(EC_Group_Encoding form) const
608	0	{
609	0	std::vector<uint8_t> output;
610	0
611	0	DER_Encoder der(output);
612	0
613	0	if(form == EC_DOMPAR_ENC_EXPLICIT)
614	0	{
615	0	const size_t ecpVers1 = 1;
616	0	const OID curve_type("1.2.840.10045.1.1"); // prime field
617	0
618	0	const size_t p_bytes = get_p_bytes();
619	0
620	0	der.start_cons(SEQUENCE)
621	0	.encode(ecpVers1)
622	0	.start_cons(SEQUENCE)
623	0	.encode(curve_type)
624	0	.encode(get_p())
625	0	.end_cons()
626	0	.start_cons(SEQUENCE)
627	0	.encode(BigInt::encode_1363(get_a(), p_bytes),
628	0	OCTET_STRING)
629	0	.encode(BigInt::encode_1363(get_b(), p_bytes),
630	0	OCTET_STRING)
631	0	.end_cons()
632	0	.encode(get_base_point().encode(PointGFp::UNCOMPRESSED), OCTET_STRING)
633	0	.encode(get_order())
634	0	.encode(get_cofactor())
635	0	.end_cons();
636	0	}
637	0	else if(form == EC_DOMPAR_ENC_OID)
638	0	{
639	0	const OID oid = get_curve_oid();
640	0	if(oid.empty())
641	0	{
642	0	throw Encoding_Error("Cannot encode EC_Group as OID because OID not set");
643	0	}
644	0	der.encode(oid);
645	0	}
646	0	else if(form == EC_DOMPAR_ENC_IMPLICITCA)
647	0	{
648	0	der.encode_null();
649	0	}
650	0	else
651	0	{
652	0	throw Internal_Error("EC_Group::DER_encode: Unknown encoding");
653	0	}
654	0
655	0	return output;
656	0	}
657
658		std::string EC_Group::PEM_encode() const
659	0	{
660	0	const std::vector<uint8_t> der = DER_encode(EC_DOMPAR_ENC_EXPLICIT);
661	0	return PEM_Code::encode(der, "EC PARAMETERS");
662	0	}
663
664		bool EC_Group::operator==(const EC_Group& other) const
665	0	{
666	0	if(m_data == other.m_data)
667	0	return true; // same shared rep
668	0
669	0	/*
670	0	* No point comparing order/cofactor as they are uniquely determined
671	0	* by the curve equation (p,a,b) and the base point.
672	0	*/
673	0	return (get_p() == other.get_p() &&
674	0	get_a() == other.get_a() &&
675	0	get_b() == other.get_b() &&
676	0	get_g_x() == other.get_g_x() &&
677	0	get_g_y() == other.get_g_y());
678	0	}
679
680		bool EC_Group::verify_public_element(const PointGFp& point) const
681	0	{
682	0	//check that public point is not at infinity
683	0	if(point.is_zero())
684	0	return false;
685	0
686	0	//check that public point is on the curve
687	0	if(point.on_the_curve() == false)
688	0	return false;
689	0
690	0	//check that public point has order q
691	0	if((point * get_order()).is_zero() == false)
692	0	return false;
693	0
694	0	if(get_cofactor() > 1)
695	0	{
696	0	if((point * get_cofactor()).is_zero())
697	0	return false;
698	0	}
699	0
700	0	return true;
701	0	}
702
703		bool EC_Group::verify_group(RandomNumberGenerator& rng,
704		bool) const
705	0	{
706	0	const BigInt& p = get_p();
707	0	const BigInt& a = get_a();
708	0	const BigInt& b = get_b();
709	0	const BigInt& order = get_order();
710	0	const PointGFp& base_point = get_base_point();
711	0
712	0	if(a < 0 \|\| a >= p)
713	0	return false;
714	0	if(b <= 0 \|\| b >= p)
715	0	return false;
716	0	if(order <= 0)
717	0	return false;
718	0
719	0	//check if field modulus is prime
720	0	if(!is_prime(p, rng, 128))
721	0	{
722	0	return false;
723	0	}
724	0
725	0	//check if order is prime
726	0	if(!is_prime(order, rng, 128))
727	0	{
728	0	return false;
729	0	}
730	0
731	0	//compute the discriminant: 4a^3 + 27b^2 which must be nonzero
732	0	const Modular_Reducer mod_p(p);
733	0
734	0	const BigInt discriminant = mod_p.reduce(
735	0	mod_p.multiply(4, mod_p.cube(a)) +
736	0	mod_p.multiply(27, mod_p.square(b)));
737	0
738	0	if(discriminant == 0)
739	0	{
740	0	return false;
741	0	}
742	0
743	0	//check for valid cofactor
744	0	if(get_cofactor() < 1)
745	0	{
746	0	return false;
747	0	}
748	0
749	0	//check if the base point is on the curve
750	0	if(!base_point.on_the_curve())
751	0	{
752	0	return false;
753	0	}
754	0	if((base_point * get_cofactor()).is_zero())
755	0	{
756	0	return false;
757	0	}
758	0	//check if order of the base point is correct
759	0	if(!(base_point * order).is_zero())
760	0	{
761	0	return false;
762	0	}
763	0
764	0	return true;
765	0	}
766
767		}