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

Source (jump to first uncovered line)
/*
* 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

Coverage Report

Created: 2024-11-29 06:10

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