4876456163

Committed 03 May 2023 09:27PM UTC coverage: 91.724% (-0.002%) from 91.726%

Build # 4876456163

Build Type

push

github

Run Details

77612 of 84615 relevant lines covered (91.72%)

11907228.65 hits per line

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

89.24

/src/lib/pubkey/dl_group/dl_group.cpp

/*
* Discrete Logarithm Parameters
* (C) 1999-2008,2015,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/dl_group.h>

#include <botan/numthry.h>
#include <botan/reducer.h>
#include <botan/internal/primality.h>
#include <botan/internal/monty.h>
#include <botan/internal/divide.h>
#include <botan/der_enc.h>
#include <botan/ber_dec.h>
#include <botan/pem.h>
#include <botan/internal/workfactor.h>
#include <botan/internal/monty_exp.h>
#include <botan/internal/fmt.h>
#include <string_view>

namespace Botan {

class DL_Group_Data final
   {
   public:
      DL_Group_Data(const BigInt& p, const BigInt& q, const BigInt& g, DL_Group_Source source) :
         m_p(p), m_q(q), m_g(g),
         m_mod_p(p),
         m_mod_q(q),
         m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
         m_monty(monty_precompute(m_monty_params, m_g, /*window bits=*/4)),
         m_p_bits(p.bits()),
         m_q_bits(q.bits()),
         m_estimated_strength(dl_work_factor(m_p_bits)),
         m_exponent_bits(dl_exponent_size(m_p_bits)),
         m_source(source)
         {
         }

      ~DL_Group_Data() = default;

      DL_Group_Data(const DL_Group_Data& other) = delete;
      DL_Group_Data(DL_Group_Data&& other) = delete;
      DL_Group_Data& operator=(const DL_Group_Data& other) = delete;
      DL_Group_Data& operator=(DL_Group_Data&& other) = delete;

      const BigInt& p() const { return m_p; }
      const BigInt& q() const { return m_q; }
      const BigInt& g() const { return m_g; }

      BigInt mod_p(const BigInt& x) const { return m_mod_p.reduce(x); }

      BigInt multiply_mod_p(const BigInt& x, const BigInt& y) const
         {
         return m_mod_p.multiply(x, y);
         }

      BigInt mod_q(const BigInt& x) const { return m_mod_q.reduce(x); }

      BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const
         {
         return m_mod_q.multiply(x, y);
         }

      BigInt square_mod_q(const BigInt& x) const
         {
         return m_mod_q.square(x);
         }

      std::shared_ptr<const Montgomery_Params> monty_params_p() const
         { return m_monty_params; }

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

      size_t estimated_strength() const { return m_estimated_strength; }

      size_t exponent_bits() const { return m_exponent_bits; }

      BigInt power_g_p(const BigInt& k, size_t max_k_bits) const
         {
         return monty_execute(*m_monty, k, max_k_bits);
         }

      BigInt power_g_p_vartime(const BigInt& k) const
         {
         return monty_execute_vartime(*m_monty, k);
         }

      BigInt power_b_p(const BigInt& b, const BigInt& k, size_t max_k_bits) const
         {
         return monty_exp(m_monty_params, b, k, max_k_bits);
         }

      BigInt power_b_p_vartime(const BigInt& b, const BigInt& k) const
         {
         return monty_exp_vartime(m_monty_params, b, k);
         }

      bool q_is_set() const { return m_q_bits > 0; }

      void assert_q_is_set(std::string_view function) const
         {
         if(q_is_set() == false)
            throw Invalid_State(fmt("DL_Group::{}: q is not set for this group", function));
         }

      DL_Group_Source source() const { return m_source; }

   private:
      BigInt m_p;
      BigInt m_q;
      BigInt m_g;
      Modular_Reducer m_mod_p;
      Modular_Reducer m_mod_q;
      std::shared_ptr<const Montgomery_Params> m_monty_params;
      std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
      size_t m_p_bits;
      size_t m_q_bits;
      size_t m_estimated_strength;
      size_t m_exponent_bits;
      DL_Group_Source m_source;
   };

//static
std::shared_ptr<DL_Group_Data> DL_Group::BER_decode_DL_group(const uint8_t data[], size_t data_len,
                                                             DL_Group_Format format,
                                                             DL_Group_Source source)
   {
   BigInt p, q, g;

   BER_Decoder decoder(data, data_len);
   BER_Decoder ber = decoder.start_sequence();

   if(format == DL_Group_Format::ANSI_X9_57)
      {
      ber.decode(p)
         .decode(q)
         .decode(g)
         .verify_end();
      }
   else if(format == DL_Group_Format::ANSI_X9_42)
      {
      ber.decode(p)
         .decode(g)
         .decode(q)
         .discard_remaining();
      }
   else if(format == DL_Group_Format::PKCS_3)
      {
      // q is left as zero
      ber.decode(p)
         .decode(g)
         .discard_remaining();
      }
   else
      throw Invalid_Argument("Unknown DL_Group encoding");

   return std::make_shared<DL_Group_Data>(p, q, g, source);
   }

//static
std::shared_ptr<DL_Group_Data>
DL_Group::load_DL_group_info(const char* p_str,
                             const char* q_str,
                             const char* g_str)
   {
   const BigInt p(p_str);
   const BigInt q(q_str);
   const BigInt g(g_str);

   return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);
   }

//static
std::shared_ptr<DL_Group_Data>
DL_Group::load_DL_group_info(const char* p_str,
                             const char* g_str)
   {
   const BigInt p(p_str);
   const BigInt q = (p - 1) / 2;
   const BigInt g(g_str);

   return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);
   }

namespace {

DL_Group_Format pem_label_to_dl_format(std::string_view label)
   {
   if(label == "DH PARAMETERS")
      return DL_Group_Format::PKCS_3;
   else if(label == "DSA PARAMETERS")
      return DL_Group_Format::ANSI_X9_57;
   else if(label == "X942 DH PARAMETERS" || label == "X9.42 DH PARAMETERS")
      return DL_Group_Format::ANSI_X9_42;
   else
      throw Decoding_Error(fmt("DL_Group: Unknown PEM label '{}'", label));
   }

}

/*
* DL_Group Constructor
*/
DL_Group::DL_Group(std::string_view str)
   {
   // Either a name or a PEM block, try name first
   m_data = DL_group_info(str);

   if(m_data == nullptr)
      {
      try
         {
         std::string label;
         const std::vector<uint8_t> ber = unlock(PEM_Code::decode(str, label));
         DL_Group_Format format = pem_label_to_dl_format(label);

         m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);
         }
      catch(...) {}
      }

   if(m_data == nullptr)
      throw Invalid_Argument(fmt("DL_Group: Unknown group '{}'", str));
   }

namespace {

/*
* Create generator of the q-sized subgroup (DSA style generator)
*/
BigInt make_dsa_generator(const BigInt& p, const BigInt& q)
   {
   BigInt e, r;
   vartime_divide(p - 1, q, e, r);

   if(e == 0 || r > 0)
      throw Invalid_Argument("make_dsa_generator q does not divide p-1");

   for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
      {
      // TODO precompute!
      BigInt g = power_mod(BigInt::from_word(PRIMES[i]), e, p);
      if(g > 1)
         return g;
      }

   throw Internal_Error("DL_Group: Couldn't create a suitable generator");
   }

}

/*
* DL_Group Constructor
*/
DL_Group::DL_Group(RandomNumberGenerator& rng,
                   PrimeType type, size_t pbits, size_t qbits)
   {
   if(pbits < 1024)
      throw Invalid_Argument(fmt("DL_Group: requested prime size {} is too small", pbits));

   if(qbits >= pbits)
      throw Invalid_Argument(fmt("DL_Group: requested q size {} is too big for p {}", qbits, pbits));

   if(type == Strong)
      {
      if(qbits != 0 && qbits != pbits - 1)
         throw Invalid_Argument("Cannot create strong-prime DL_Group with specified q bits");

      const BigInt p = random_safe_prime(rng, pbits);
      const BigInt q = (p - 1) / 2;

      /*
      Always choose a generator that is quadratic reside mod p,
      this forces g to be a generator of the subgroup of size q.
      */
      BigInt g = BigInt::from_word(2);
      if(jacobi(g, p) != 1)
         {
         // prime table does not contain 2
         for(size_t i = 0; i < PRIME_TABLE_SIZE; ++i)
            {
            g = BigInt::from_word(PRIMES[i]);
            if(jacobi(g, p) == 1)
               break;
            }
         }

      m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
      }
   else if(type == Prime_Subgroup)
      {
      if(qbits == 0)
         qbits = dl_exponent_size(pbits);

      const BigInt q = random_prime(rng, qbits);
      Modular_Reducer mod_2q(2*q);
      BigInt X;
      BigInt p;
      while(p.bits() != pbits || !is_prime(p, rng, 128, true))
         {
         X.randomize(rng, pbits);
         p = X - mod_2q.reduce(X) + 1;
         }

      const BigInt g = make_dsa_generator(p, q);
      m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
      }
   else if(type == DSA_Kosherizer)
      {
      if(qbits == 0)
         qbits = ((pbits <= 1024) ? 160 : 256);

      BigInt p, q;
      generate_dsa_primes(rng, p, q, pbits, qbits);
      const BigInt g = make_dsa_generator(p, q);
      m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
      }
   else
      {
      throw Invalid_Argument("DL_Group unknown PrimeType");
      }
   }

/*
* DL_Group Constructor
*/
DL_Group::DL_Group(RandomNumberGenerator& rng,
                   const std::vector<uint8_t>& seed,
                   size_t pbits, size_t qbits)
   {
   BigInt p, q;

   if(!generate_dsa_primes(rng, p, q, pbits, qbits, seed))
      throw Invalid_Argument("DL_Group: The seed given does not generate a DSA group");

   BigInt g = make_dsa_generator(p, q);

   m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
   }

/*
* DL_Group Constructor
*/
DL_Group::DL_Group(const BigInt& p, const BigInt& g)
   {
   m_data = std::make_shared<DL_Group_Data>(p, BigInt::zero(), g, DL_Group_Source::ExternalSource);
   }

/*
* DL_Group Constructor
*/
DL_Group::DL_Group(const BigInt& p, const BigInt& q, const BigInt& g)
   {
   m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::ExternalSource);
   }

const DL_Group_Data& DL_Group::data() const
   {
   if(m_data)
      return *m_data;

   throw Invalid_State("DL_Group uninitialized");
   }

bool DL_Group::verify_public_element(const BigInt& y) const
   {
   const BigInt& p = get_p();
   const BigInt& q = get_q();

   if(y <= 1 || y >= p)
      return false;

   if(q.is_zero() == false)
      {
      if(data().power_b_p_vartime(y, q) != 1)
         return false;
      }

   return true;
   }

bool DL_Group::verify_private_element(const BigInt& x) const
   {
   const BigInt& p = get_p();
   const BigInt& q = get_q();

   if(x <= 1 || x >= p)
      return false;

   if(q > 0 && x > q)
      return false;

   return true;
   }

bool DL_Group::verify_element_pair(const BigInt& y, const BigInt& x) const
   {
   const BigInt& p = get_p();

   if(y <= 1 || y >= p || x <= 1 || x >= p)
      return false;

   if(y != this->power_g_p(x))
      return false;

   return true;
   }

/*
* Verify the parameters
*/
bool DL_Group::verify_group(RandomNumberGenerator& rng,
                            bool strong) const
   {
   const bool from_builtin = (source() == DL_Group_Source::Builtin);

   if(!strong && from_builtin)
      return true;

   const BigInt& p = get_p();
   const BigInt& q = get_q();
   const BigInt& g = get_g();

   if(g < 2 || p < 3 || q < 0)
      return false;

   const size_t test_prob = 128;
   const bool is_randomly_generated = (source() != DL_Group_Source::ExternalSource);

   if(!is_prime(p, rng, test_prob, is_randomly_generated))
      {
      return false;
      }

   if(q != 0)
      {
      if((p - 1) % q != 0)
         {
         return false;
         }
      if(data().power_g_p_vartime(q) != 1)
         {
         return false;
         }
      if(!is_prime(q, rng, test_prob, is_randomly_generated))
         {
         return false;
         }
      }
   else
      {
      if(!from_builtin && !is_randomly_generated)
         {
         // If we got this p,g from some unknown source, try to verify
         // that the group order is not too absurdly small.

         const size_t upper_bound = strong ? 1000 : 100;

         for(size_t i = 2; i != upper_bound; ++i)
            {
            if(data().power_g_p_vartime(BigInt::from_word(i)) == 1)
               {
               return false;
               }
            }
         }
      }

   return true;
   }

/*
* Return the prime
*/
const BigInt& DL_Group::get_p() const
   {
   return data().p();
   }

/*
* Return the generator
*/
const BigInt& DL_Group::get_g() const
   {
   return data().g();
   }

/*
* Return the subgroup
*/
const BigInt& DL_Group::get_q() const
   {
   return data().q();
   }

std::shared_ptr<const Montgomery_Params> DL_Group::monty_params_p() const
   {
   return data().monty_params_p();
   }

bool DL_Group::has_q() const
   {
   return data().q_is_set();
   }

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

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

size_t DL_Group::q_bits() const
   {
   data().assert_q_is_set("q_bits");
   return data().q_bits();
   }

size_t DL_Group::q_bytes() const
   {
   data().assert_q_is_set("q_bytes");
   return data().q_bytes();
   }

size_t DL_Group::estimated_strength() const
   {
   return data().estimated_strength();
   }

size_t DL_Group::exponent_bits() const
   {
   return data().exponent_bits();
   }

BigInt DL_Group::inverse_mod_p(const BigInt& x) const
   {
   // precompute??
   return inverse_mod(x, get_p());
   }

BigInt DL_Group::mod_p(const BigInt& x) const
   {
   return data().mod_p(x);
   }

BigInt DL_Group::multiply_mod_p(const BigInt& x, const BigInt& y) const
   {
   return data().multiply_mod_p(x, y);
   }

BigInt DL_Group::inverse_mod_q(const BigInt& x) const
   {
   data().assert_q_is_set("inverse_mod_q");
   // precompute??
   return inverse_mod(x, get_q());
   }

BigInt DL_Group::mod_q(const BigInt& x) const
   {
   data().assert_q_is_set("mod_q");
   return data().mod_q(x);
   }

BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y) const
   {
   data().assert_q_is_set("multiply_mod_q");
   return data().multiply_mod_q(x, y);
   }

BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const
   {
   data().assert_q_is_set("multiply_mod_q");
   return data().multiply_mod_q(data().multiply_mod_q(x, y), z);
   }

BigInt DL_Group::square_mod_q(const BigInt& x) const
   {
   data().assert_q_is_set("square_mod_q");
   return data().square_mod_q(x);
   }

BigInt DL_Group::multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const
   {
   return monty_multi_exp(data().monty_params_p(), get_g(), x, y, z);
   }

BigInt DL_Group::power_g_p(const BigInt& x) const
   {
   return data().power_g_p(x, x.bits());
   }

BigInt DL_Group::power_g_p(const BigInt& x, size_t max_x_bits) const
   {
   return data().power_g_p(x, max_x_bits);
   }

BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x) const
   {
   return this->power_b_p(b, x, data().p_bits());
   }

BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const
   {
   return data().power_b_p(b, x, max_x_bits);
   }

DL_Group_Source DL_Group::source() const
   {
   return data().source();
   }

/*
* DER encode the parameters
*/
std::vector<uint8_t> DL_Group::DER_encode(DL_Group_Format format) const
   {
   if(get_q().is_zero() && (format != DL_Group_Format::PKCS_3))
      throw Encoding_Error("Cannot encode DL_Group in ANSI formats when q param is missing");

   std::vector<uint8_t> output;
   DER_Encoder der(output);

   if(format == DL_Group_Format::ANSI_X9_57)
      {
      der.start_sequence()
            .encode(get_p())
            .encode(get_q())
            .encode(get_g())
         .end_cons();
      }
   else if(format == DL_Group_Format::ANSI_X9_42)
      {
      der.start_sequence()
            .encode(get_p())
            .encode(get_g())
            .encode(get_q())
         .end_cons();
      }
   else if(format == DL_Group_Format::PKCS_3)
      {
      der.start_sequence()
            .encode(get_p())
            .encode(get_g())
         .end_cons();
      }
   else
      throw Invalid_Argument("Unknown DL_Group encoding");

   return output;
   }

/*
* PEM encode the parameters
*/
std::string DL_Group::PEM_encode(DL_Group_Format format) const
   {
   const std::vector<uint8_t> encoding = DER_encode(format);

   if(format == DL_Group_Format::PKCS_3)
      return PEM_Code::encode(encoding, "DH PARAMETERS");
   else if(format == DL_Group_Format::ANSI_X9_57)
      return PEM_Code::encode(encoding, "DSA PARAMETERS");
   else if(format == DL_Group_Format::ANSI_X9_42)
      return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS");
   else
      throw Invalid_Argument("Unknown DL_Group encoding");
   }

DL_Group::DL_Group(const uint8_t ber[], size_t ber_len, DL_Group_Format format)
   {
   m_data = BER_decode_DL_group(ber, ber_len, format, DL_Group_Source::ExternalSource);
   }

void DL_Group::BER_decode(const std::vector<uint8_t>& ber, DL_Group_Format format)
   {
   m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);
   }

//static
DL_Group DL_Group::DL_Group_from_PEM(std::string_view pem)
   {
   std::string label;
   const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label));
   DL_Group_Format format = pem_label_to_dl_format(label);
   return DL_Group(ber, format);
   }

}

1	/*
2	* Discrete Logarithm Parameters
3	* (C) 1999-2008,2015,2018 Jack Lloyd
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*/
7
8	#include <botan/dl_group.h>
9
10	#include <botan/numthry.h>
11	#include <botan/reducer.h>
12	#include <botan/internal/primality.h>
13	#include <botan/internal/monty.h>
14	#include <botan/internal/divide.h>
15	#include <botan/der_enc.h>
16	#include <botan/ber_dec.h>
17	#include <botan/pem.h>
18	#include <botan/internal/workfactor.h>
19	#include <botan/internal/monty_exp.h>
20	#include <botan/internal/fmt.h>
21	#include <string_view>
22
23	namespace Botan {
24
25	class DL_Group_Data final
26	{
27	public:
28	DL_Group_Data(const BigInt& p, const BigInt& q, const BigInt& g, DL_Group_Source source) :	1,318✔
29	m_p(p), m_q(q), m_g(g),	1,318✔
30	m_mod_p(p),	1,318✔
31	m_mod_q(q),	1,315✔
32	m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),	1,311✔
33	m_monty(monty_precompute(m_monty_params, m_g, /window bits=/4)),	1,097✔
34	m_p_bits(p.bits()),	1,096✔
35	m_q_bits(q.bits()),	1,096✔
36	m_estimated_strength(dl_work_factor(m_p_bits)),	1,096✔
37	m_exponent_bits(dl_exponent_size(m_p_bits)),	1,096✔
38	m_source(source)	1,096✔
39	{
40	}	2,184✔
41
42	~DL_Group_Data() = default;	5,407✔
43
44	DL_Group_Data(const DL_Group_Data& other) = delete;
45	DL_Group_Data(DL_Group_Data&& other) = delete;
46	DL_Group_Data& operator=(const DL_Group_Data& other) = delete;
47	DL_Group_Data& operator=(DL_Group_Data&& other) = delete;
48
49	const BigInt& p() const { return m_p; }	4,925✔
50	const BigInt& q() const { return m_q; }	15,566✔
51	const BigInt& g() const { return m_g; }	7,314✔
52
53	BigInt mod_p(const BigInt& x) const { return m_mod_p.reduce(x); }	148✔
54
55	BigInt multiply_mod_p(const BigInt& x, const BigInt& y) const	654✔
56	{
57	return m_mod_p.multiply(x, y);	654✔
58	}
59
60	BigInt mod_q(const BigInt& x) const { return m_mod_q.reduce(x); }	77✔
61
62	BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const	14,087✔
63	{
64	return m_mod_q.multiply(x, y);	14,087✔
65	}
66
67	BigInt square_mod_q(const BigInt& x) const	154✔
68	{
69	return m_mod_q.square(x);	154✔
70	}
71
72	std::shared_ptr<const Montgomery_Params> monty_params_p() const	6,866✔
73	{ return m_monty_params; }	13,732✔
74
75	size_t p_bits() const { return m_p_bits; }	1,335✔
76	size_t q_bits() const { return m_q_bits; }	7,492✔
77	size_t p_bytes() const { return (m_p_bits + 7) / 8; }	2,902✔
78	size_t q_bytes() const { return (m_q_bits + 7) / 8; }	465✔
79
80	size_t estimated_strength() const { return m_estimated_strength; }	52✔
81
82	size_t exponent_bits() const { return m_exponent_bits; }	87✔
83
84	BigInt power_g_p(const BigInt& k, size_t max_k_bits) const	1,132✔
85	{
86	return monty_execute(*m_monty, k, max_k_bits);	1,132✔
87	}
88
89	BigInt power_g_p_vartime(const BigInt& k) const	633✔
90	{
91	return monty_execute_vartime(*m_monty, k);	633✔
92	}
93
94	BigInt power_b_p(const BigInt& b, const BigInt& k, size_t max_k_bits) const	2,700✔
95	{
96	return monty_exp(m_monty_params, b, k, max_k_bits);	5,400✔
97	}
98
99	BigInt power_b_p_vartime(const BigInt& b, const BigInt& k) const	21✔
100	{
101	return monty_exp_vartime(m_monty_params, b, k);	42✔
102	}
103
104	bool q_is_set() const { return m_q_bits > 0; }	22,445✔
105
106	void assert_q_is_set(std::string_view function) const	22,266✔
107	{
108	if(q_is_set() == false)	22,266✔
109	throw Invalid_State(fmt("DL_Group::{}: q is not set for this group", function));	×
110	}	22,266✔
111
112	DL_Group_Source source() const { return m_source; }	142✔
113
114	private:
115	BigInt m_p;
116	BigInt m_q;
117	BigInt m_g;
118	Modular_Reducer m_mod_p;
119	Modular_Reducer m_mod_q;
120	std::shared_ptr<const Montgomery_Params> m_monty_params;
121	std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
122	size_t m_p_bits;
123	size_t m_q_bits;
124	size_t m_estimated_strength;
125	size_t m_exponent_bits;
126	DL_Group_Source m_source;
127	};
128
129	//static
130	std::shared_ptr<DL_Group_Data> DL_Group::BER_decode_DL_group(const uint8_t data[], size_t data_len,	499✔
131	DL_Group_Format format,
132	DL_Group_Source source)
133	{
134	BigInt p, q, g;	499✔
135
136	BER_Decoder decoder(data, data_len);	499✔
137	BER_Decoder ber = decoder.start_sequence();	499✔
138
139	if(format == DL_Group_Format::ANSI_X9_57)	495✔
140	{
141	ber.decode(p)	446✔
142	.decode(q)	437✔
143	.decode(g)	433✔
144	.verify_end();	433✔
145	}
146	else if(format == DL_Group_Format::ANSI_X9_42)	49✔
147	{
148	ber.decode(p)	48✔
149	.decode(g)	44✔
150	.decode(q)	41✔
151	.discard_remaining();	41✔
152	}
153	else if(format == DL_Group_Format::PKCS_3)	1✔
154	{
155	// q is left as zero
156	ber.decode(p)	1✔
157	.decode(g)	1✔
158	.discard_remaining();	1✔
159	}
160	else
161	throw Invalid_Argument("Unknown DL_Group encoding");	×
162
163	return std::make_shared<DL_Group_Data>(p, q, g, source);	473✔
164	}	1,972✔
165
166	//static
167	std::shared_ptr<DL_Group_Data>
168	DL_Group::load_DL_group_info(const char* p_str,	253✔
169	const char* q_str,
170	const char* g_str)
171	{
172	const BigInt p(p_str);	253✔
173	const BigInt q(q_str);	253✔
174	const BigInt g(g_str);	253✔
175
176	return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);	253✔
177	}	759✔
178
179	//static
180	std::shared_ptr<DL_Group_Data>
181	DL_Group::load_DL_group_info(const char* p_str,	138✔
182	const char* g_str)
183	{
184	const BigInt p(p_str);	138✔
185	const BigInt q = (p - 1) / 2;	138✔
186	const BigInt g(g_str);	138✔
187
188	return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);	138✔
189	}	414✔
190
191	namespace {
192
193	DL_Group_Format pem_label_to_dl_format(std::string_view label)	3✔
194	{
195	if(label == "DH PARAMETERS")	3✔
196	return DL_Group_Format::PKCS_3;	1✔
197	else if(label == "DSA PARAMETERS")	2✔
198	return DL_Group_Format::ANSI_X9_57;	1✔
199	else if(label == "X942 DH PARAMETERS" \|\| label == "X9.42 DH PARAMETERS")	2✔
200	return DL_Group_Format::ANSI_X9_42;	1✔
201	else
202	throw Decoding_Error(fmt("DL_Group: Unknown PEM label '{}'", label));	×
203	}
204
205	}
206
207	/*
208	* DL_Group Constructor
209	*/
210	DL_Group::DL_Group(std::string_view str)	394✔
211	{
212	// Either a name or a PEM block, try name first
213	m_data = DL_group_info(str);	394✔
214
215	if(m_data == nullptr)	394✔
216	{
217	try	3✔
218	{
219	std::string label;	3✔
220	const std::vector<uint8_t> ber = unlock(PEM_Code::decode(str, label));	6✔
221	DL_Group_Format format = pem_label_to_dl_format(label);	3✔
222
223	m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);	3✔
224	}	4✔
225	catch(...) {}	×
226	}
227
228	if(m_data == nullptr)	394✔
229	throw Invalid_Argument(fmt("DL_Group: Unknown group '{}'", str));	×
230	}	394✔
231
232	namespace {
233
234	/*
235	* Create generator of the q-sized subgroup (DSA style generator)
236	*/
237	BigInt make_dsa_generator(const BigInt& p, const BigInt& q)	8✔
238	{
239	BigInt e, r;	8✔
240	vartime_divide(p - 1, q, e, r);	8✔
241
242	if(e == 0 \|\| r > 0)	16✔
243	throw Invalid_Argument("make_dsa_generator q does not divide p-1");	×
244
245	for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)	8✔
246	{
247	// TODO precompute!
248	BigInt g = power_mod(BigInt::from_word(PRIMES[i]), e, p);	8✔
249	if(g > 1)	8✔
250	return g;	8✔
251	}	8✔
252
253	throw Internal_Error("DL_Group: Couldn't create a suitable generator");	×
254	}	16✔
255
256	}
257
258	/*
259	* DL_Group Constructor
260	*/
261	DL_Group::DL_Group(RandomNumberGenerator& rng,	9✔
262	PrimeType type, size_t pbits, size_t qbits)	9✔
263	{
264	if(pbits < 1024)	9✔
265	throw Invalid_Argument(fmt("DL_Group: requested prime size {} is too small", pbits));	×
266
267	if(qbits >= pbits)	9✔
268	throw Invalid_Argument(fmt("DL_Group: requested q size {} is too big for p {}", qbits, pbits));	×
269
270	if(type == Strong)	9✔
271	{
272	if(qbits != 0 && qbits != pbits - 1)	1✔
273	throw Invalid_Argument("Cannot create strong-prime DL_Group with specified q bits");	×
274
275	const BigInt p = random_safe_prime(rng, pbits);	1✔
276	const BigInt q = (p - 1) / 2;	1✔
277
278	/*
279	Always choose a generator that is quadratic reside mod p,
280	this forces g to be a generator of the subgroup of size q.
281	*/
282	BigInt g = BigInt::from_word(2);	1✔
283	if(jacobi(g, p) != 1)	1✔
284	{
285	// prime table does not contain 2
286	for(size_t i = 0; i < PRIME_TABLE_SIZE; ++i)	×
287	{
288	g = BigInt::from_word(PRIMES[i]);	×
289	if(jacobi(g, p) == 1)	×
290	break;
291	}
292	}
293
294	m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);	1✔
295	}	3✔
296	else if(type == Prime_Subgroup)	8✔
297	{
298	if(qbits == 0)	5✔
299	qbits = dl_exponent_size(pbits);	1✔
300
301	const BigInt q = random_prime(rng, qbits);	5✔
302	Modular_Reducer mod_2q(2*q);	5✔
303	BigInt X;	5✔
304	BigInt p;	5✔
305	while(p.bits() != pbits \|\| !is_prime(p, rng, 128, true))	2,238✔
306	{
307	X.randomize(rng, pbits);	2,233✔
308	p = X - mod_2q.reduce(X) + 1;	11,160✔
309	}
310
311	const BigInt g = make_dsa_generator(p, q);	5✔
312	m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);	5✔
313	}	20✔
314	else if(type == DSA_Kosherizer)	3✔
315	{
316	if(qbits == 0)	2✔
317	qbits = ((pbits <= 1024) ? 160 : 256);	1✔
318
319	BigInt p, q;	2✔
320	generate_dsa_primes(rng, p, q, pbits, qbits);	2✔
321	const BigInt g = make_dsa_generator(p, q);	2✔
322	m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);	2✔
323	}	6✔
324	else
325	{
326	throw Invalid_Argument("DL_Group unknown PrimeType");	1✔
327	}
328	}	9✔
329
330	/*
331	* DL_Group Constructor
332	*/
333	DL_Group::DL_Group(RandomNumberGenerator& rng,	6✔
334	const std::vector<uint8_t>& seed,
335	size_t pbits, size_t qbits)	6✔
336	{
337	BigInt p, q;	6✔
338
339	if(!generate_dsa_primes(rng, p, q, pbits, qbits, seed))	6✔
340	throw Invalid_Argument("DL_Group: The seed given does not generate a DSA group");	1✔
341
342	BigInt g = make_dsa_generator(p, q);	1✔
343
344	m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);	1✔
345	}	13✔
346
347	/*
348	* DL_Group Constructor
349	*/
350	DL_Group::DL_Group(const BigInt& p, const BigInt& g)	53✔
351	{
352	m_data = std::make_shared<DL_Group_Data>(p, BigInt::zero(), g, DL_Group_Source::ExternalSource);	53✔
353	}	53✔
354
355	/*
356	* DL_Group Constructor
357	*/
358	DL_Group::DL_Group(const BigInt& p, const BigInt& q, const BigInt& g)	392✔
359	{
360	m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::ExternalSource);	392✔
361	}	392✔
362
363	const DL_Group_Data& DL_Group::data() const	89,198✔
364	{
365	if(m_data)	89,198✔
366	return *m_data;	89,197✔
367
368	throw Invalid_State("DL_Group uninitialized");	1✔
369	}
370
371	bool DL_Group::verify_public_element(const BigInt& y) const	23✔
372	{
373	const BigInt& p = get_p();	23✔
374	const BigInt& q = get_q();	23✔
375
376	if(y <= 1 \|\| y >= p)	46✔
377	return false;	×
378
379	if(q.is_zero() == false)	23✔
380	{
381	if(data().power_b_p_vartime(y, q) != 1)	42✔
382	return false;	7✔
383	}
384
385	return true;
386	}
387
388	bool DL_Group::verify_private_element(const BigInt& x) const	659✔
389	{
390	const BigInt& p = get_p();	659✔
391	const BigInt& q = get_q();	659✔
392
393	if(x <= 1 \|\| x >= p)	1,292✔
394	return false;	27✔
395
396	if(q > 0 && x > q)	1,220✔
397	return false;	1✔
398
399	return true;
400	}
401
402	bool DL_Group::verify_element_pair(const BigInt& y, const BigInt& x) const	×
403	{
404	const BigInt& p = get_p();	×
405
406	if(y <= 1 \|\| y >= p \|\| x <= 1 \|\| x >= p)	×
407	return false;	×
408
409	if(y != this->power_g_p(x))	×
410	return false;	×
411
412	return true;
413	}
414
415	/*
416	* Verify the parameters
417	*/
418	bool DL_Group::verify_group(RandomNumberGenerator& rng,	62✔
419	bool strong) const
420	{
421	const bool from_builtin = (source() == DL_Group_Source::Builtin);	62✔
422
423	if(!strong && from_builtin)	62✔
424	return true;
425
426	const BigInt& p = get_p();	58✔
427	const BigInt& q = get_q();	58✔
428	const BigInt& g = get_g();	58✔
429
430	if(g < 2 \|\| p < 3 \|\| q < 0)	174✔
431	return false;	×
432
433	const size_t test_prob = 128;	58✔
434	const bool is_randomly_generated = (source() != DL_Group_Source::ExternalSource);	58✔
435
436	if(!is_prime(p, rng, test_prob, is_randomly_generated))	58✔
437	{
438	return false;
439	}
440
441	if(q != 0)	58✔
442	{
443	if((p - 1) % q != 0)	180✔
444	{
445	return false;
446	}
447	if(data().power_g_p_vartime(q) != 1)	90✔
448	{
449	return false;
450	}
451	if(!is_prime(q, rng, test_prob, is_randomly_generated))	45✔
452	{
453	return false;	×
454	}
455	}
456	else
457	{
458	if(!from_builtin && !is_randomly_generated)	13✔
459	{
460	// If we got this p,g from some unknown source, try to verify
461	// that the group order is not too absurdly small.
462
463	const size_t upper_bound = strong ? 1000 : 100;	6✔
464
465	for(size_t i = 2; i != upper_bound; ++i)	594✔
466	{
467	if(data().power_g_p_vartime(BigInt::from_word(i)) == 1)	1,764✔
468	{
469	return false;
470	}
471	}
472	}
473	}
474
475	return true;
476	}
477
478	/*
479	* Return the prime
480	*/
481	const BigInt& DL_Group::get_p() const	4,926✔
482	{
483	return data().p();	4,926✔
484	}
485
486	/*
487	* Return the generator
488	*/
489	const BigInt& DL_Group::get_g() const	7,314✔
490	{
491	return data().g();	7,314✔
492	}
493
494	/*
495	* Return the subgroup
496	*/
497	const BigInt& DL_Group::get_q() const	15,566✔
498	{
499	return data().q();	15,566✔
500	}
501
502	std::shared_ptr<const Montgomery_Params> DL_Group::monty_params_p() const	15✔
503	{
504	return data().monty_params_p();	15✔
505	}
506
507	bool DL_Group::has_q() const	179✔
508	{
509	return data().q_is_set();	179✔
510	}
511
512	size_t DL_Group::p_bits() const	812✔
513	{
514	return data().p_bits();	812✔
515	}
516
517	size_t DL_Group::p_bytes() const	2,902✔
518	{
519	return data().p_bytes();	2,902✔
520	}
521
522	size_t DL_Group::q_bits() const	7,492✔
523	{
524	data().assert_q_is_set("q_bits");	7,492✔
525	return data().q_bits();	7,492✔
526	}
527
528	size_t DL_Group::q_bytes() const	465✔
529	{
530	data().assert_q_is_set("q_bytes");	465✔
531	return data().q_bytes();	465✔
532	}
533
534	size_t DL_Group::estimated_strength() const	52✔
535	{
536	return data().estimated_strength();	52✔
537	}
538
539	size_t DL_Group::exponent_bits() const	87✔
540	{
541	return data().exponent_bits();	87✔
542	}
543
544	BigInt DL_Group::inverse_mod_p(const BigInt& x) const	491✔
545	{
546	// precompute??
547	return inverse_mod(x, get_p());	491✔
548	}
549
550	BigInt DL_Group::mod_p(const BigInt& x) const	148✔
551	{
552	return data().mod_p(x);	148✔
553	}
554
555	BigInt DL_Group::multiply_mod_p(const BigInt& x, const BigInt& y) const	654✔
556	{
557	return data().multiply_mod_p(x, y);	654✔
558	}
559
560	BigInt DL_Group::inverse_mod_q(const BigInt& x) const	145✔
561	{
562	data().assert_q_is_set("inverse_mod_q");	145✔
563	// precompute??
564	return inverse_mod(x, get_q());	145✔
565	}
566
567	BigInt DL_Group::mod_q(const BigInt& x) const	77✔
568	{
569	data().assert_q_is_set("mod_q");	77✔
570	return data().mod_q(x);	77✔
571	}
572
573	BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y) const	13,779✔
574	{
575	data().assert_q_is_set("multiply_mod_q");	13,779✔
576	return data().multiply_mod_q(x, y);	13,779✔
577	}
578
579	BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const	154✔
580	{
581	data().assert_q_is_set("multiply_mod_q");	154✔
582	return data().multiply_mod_q(data().multiply_mod_q(x, y), z);	308✔
583	}
584
585	BigInt DL_Group::square_mod_q(const BigInt& x) const	154✔
586	{
587	data().assert_q_is_set("square_mod_q");	154✔
588	return data().square_mod_q(x);	154✔
589	}
590
591	BigInt DL_Group::multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const	6,851✔
592	{
593	return monty_multi_exp(data().monty_params_p(), get_g(), x, y, z);	13,702✔
594	}
595
596	BigInt DL_Group::power_g_p(const BigInt& x) const	10✔
597	{
598	return data().power_g_p(x, x.bits());	10✔
599	}
600
601	BigInt DL_Group::power_g_p(const BigInt& x, size_t max_x_bits) const	1,122✔
602	{
603	return data().power_g_p(x, max_x_bits);	1,122✔
604	}
605
606	BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x) const	523✔
607	{
608	return this->power_b_p(b, x, data().p_bits());	523✔
609	}
610
611	BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const	2,700✔
612	{
613	return data().power_b_p(b, x, max_x_bits);	2,700✔
614	}
615
616	DL_Group_Source DL_Group::source() const	142✔
617	{
618	return data().source();	142✔
619	}
620
621	/*
622	* DER encode the parameters
623	*/
624	std::vector<uint8_t> DL_Group::DER_encode(DL_Group_Format format) const	159✔
625	{
626	if(get_q().is_zero() && (format != DL_Group_Format::PKCS_3))	163✔
627	throw Encoding_Error("Cannot encode DL_Group in ANSI formats when q param is missing");	×
628
629	std::vector<uint8_t> output;	159✔
630	DER_Encoder der(output);	159✔
631
632	if(format == DL_Group_Format::ANSI_X9_57)	159✔
633	{
634	der.start_sequence()	94✔
635	.encode(get_p())	94✔
636	.encode(get_q())	94✔
637	.encode(get_g())	94✔
638	.end_cons();	94✔
639	}
640	else if(format == DL_Group_Format::ANSI_X9_42)	65✔
641	{
642	der.start_sequence()	64✔
643	.encode(get_p())	64✔
644	.encode(get_g())	64✔
645	.encode(get_q())	64✔
646	.end_cons();	64✔
647	}
648	else if(format == DL_Group_Format::PKCS_3)	1✔
649	{
650	der.start_sequence()	1✔
651	.encode(get_p())	1✔
652	.encode(get_g())	1✔
653	.end_cons();	1✔
654	}
655	else
656	throw Invalid_Argument("Unknown DL_Group encoding");	×
657
658	return output;	159✔
659	}	159✔
660
661	/*
662	* PEM encode the parameters
663	*/
664	std::string DL_Group::PEM_encode(DL_Group_Format format) const	5✔
665	{
666	const std::vector<uint8_t> encoding = DER_encode(format);	5✔
667
668	if(format == DL_Group_Format::PKCS_3)	5✔
669	return PEM_Code::encode(encoding, "DH PARAMETERS");	1✔
670	else if(format == DL_Group_Format::ANSI_X9_57)	4✔
671	return PEM_Code::encode(encoding, "DSA PARAMETERS");	2✔
672	else if(format == DL_Group_Format::ANSI_X9_42)	2✔
673	return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS");	2✔
674	else
675	throw Invalid_Argument("Unknown DL_Group encoding");	×
676	}	5✔
677
678	DL_Group::DL_Group(const uint8_t ber[], size_t ber_len, DL_Group_Format format)	496✔
679	{
680	m_data = BER_decode_DL_group(ber, ber_len, format, DL_Group_Source::ExternalSource);	496✔
681	}	496✔
682
683	void DL_Group::BER_decode(const std::vector<uint8_t>& ber, DL_Group_Format format)	×
684	{
685	m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);	×
686	}	×
687
688	//static
689	DL_Group DL_Group::DL_Group_from_PEM(std::string_view pem)	×
690	{
691	std::string label;	×
692	const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label));	×
693	DL_Group_Format format = pem_label_to_dl_format(label);	×
694	return DL_Group(ber, format);	×
695	}	×
696
697	}

randombit / botan / 4876456163

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