6187552976

Committed 14 Sep 2023 03:21PM UTC coverage: 91.715% (-0.001%) from 91.716%

Build # 6187552976

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #3698 from randombit/rsa_bigint_todo

kem follow-up, now we do have BigInt::encode_1363 working with std::s…

Run Details

79097 of 86242 relevant lines covered (91.72%)

8661343.03 hits per line

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

88.5

/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/reducer.h>
#include <botan/internal/divide.h>
#include <botan/internal/fmt.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(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));
   }
}

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

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

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

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

randombit / botan / 6187552976

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