14925550168

Committed 09 May 2025 09:10AM UTC coverage: 91.309% (+0.2%) from 91.13%

Build # 14925550168

Build Type

Pull #4861

github

Committed by

web-flow

Commit Message

Merge 1c9f082b7 into c06967092

Pull Request Pull Request #4861: FIX: Ambiguous c'tor overloads in X509_DN with initializer list

Run Details

96201 of 105358 relevant lines covered (91.31%)

13003445.07 hits per line

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

88.56

/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/ber_dec.h>
#include <botan/der_enc.h>
#include <botan/numthry.h>
#include <botan/pem.h>
#include <botan/internal/barrett.h>
#include <botan/internal/divide.h>
#include <botan/internal/fmt.h>
#include <botan/internal/mod_inv.h>
#include <botan/internal/monty.h>
#include <botan/internal/monty_exp.h>
#include <botan/internal/primality.h>
#include <botan/internal/workfactor.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(Barrett_Reduction::for_public_modulus(p)),
            m_mod_q(Barrett_Reduction::for_public_modulus(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(const BigInt& p, const BigInt& g, DL_Group_Source source) :
            m_p(p),
            m_g(g),
            m_mod_p(Barrett_Reduction::for_public_modulus(p)),
            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(0),
            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; }

      const Barrett_Reduction& reducer_mod_p() const { return m_mod_p; }

      const Barrett_Reduction& reducer_mod_q() const {
         BOTAN_STATE_CHECK(m_mod_q);
         return *m_mod_q;
      }

      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).value();
      }

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

      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).value();
      }

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

      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;  // zero if no q set
      BigInt m_g;
      Barrett_Reduction m_mod_p;
      std::optional<Barrett_Reduction> 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) {
   BER_Decoder decoder(data, data_len);
   BER_Decoder ber = decoder.start_sequence();

   if(format == DL_Group_Format::ANSI_X9_57) {
      BigInt p, q, g;
      ber.decode(p).decode(q).decode(g).verify_end();
      return std::make_shared<DL_Group_Data>(p, q, g, source);
   } else if(format == DL_Group_Format::ANSI_X9_42) {
      BigInt p, g, q;
      ber.decode(p).decode(g).decode(q).discard_remaining();
      return std::make_shared<DL_Group_Data>(p, q, g, source);
   } else if(format == DL_Group_Format::PKCS_3) {
      BigInt p, g;
      ber.decode(p).decode(g).discard_remaining();
      return std::make_shared<DL_Group_Data>(p, g, source);
   } else {
      throw Invalid_Argument("Unknown DL_Group encoding");
   }
}

//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);

   if(q.is_zero()) {
      return std::make_shared<DL_Group_Data>(p, g, DL_Group_Source::Builtin);
   } else {
      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));
   }
}

}  // namespace

/*
* 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));
   }
}

DL_Group DL_Group::from_name(std::string_view name) {
   auto data = DL_group_info(name);

   if(!data) {
      throw Invalid_Argument(fmt("DL_Group: Unknown group '{}'", name));
   }

   return DL_Group(data);
}

//static
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);
}

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");
   }

   // TODO we compute these, then throw them away and recompute in DL_Group_Data
   auto reduce_mod = Barrett_Reduction::for_public_modulus(p);
   auto monty_params = std::make_shared<Montgomery_Params>(p, reduce_mod);

   for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) {
      BigInt g = monty_exp_vartime(monty_params, BigInt::from_word(PRIMES[i]), e).value();
      if(g > 1) {
         return g;
      }
   }

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

}  // namespace

/*
* 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.

      We use 2 by default, but if 2 is not a quadratic reside then use 4 which
      is always a quadratic reside, being the square of 2 (or p - 2)
      */
      BigInt g = BigInt::from_word(2);
      if(jacobi(g, p) != 1) {
         g = BigInt::from_word(4);
      }

      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);
      const BigInt q2 = q * 2;
      BigInt X;
      BigInt p;
      while(p.bits() != pbits || !is_prime(p, rng, 128, true)) {
         X.randomize(rng, pbits);
         // Variable time division is OK here since DH groups are public anyway
         p = X - (X % q2) + 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, g, DL_Group_Source::ExternalSource);
}

/*
* DL_Group Constructor
*/
DL_Group::DL_Group(const BigInt& p, const BigInt& q, const BigInt& g) {
   if(q.is_zero()) {
      m_data = std::make_shared<DL_Group_Data>(p, g, DL_Group_Source::ExternalSource);
   } else {
      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, x.bits())) {
      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_public_prime(x, get_p());
}

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

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

const Barrett_Reduction& DL_Group::_reducer_mod_p() const {
   return data().reducer_mod_p();
}

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

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

BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y) const {
   data().assert_q_is_set("multiply_mod_q");
   return data().reducer_mod_q().multiply(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 this->multiply_mod_q(this->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().reducer_mod_q().square(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).value();
}

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);
}

}  // namespace Botan

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

randombit / botan / 14925550168

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