diff options
Diffstat (limited to 'comm/third_party/botan/src/lib/pubkey/dl_group/dl_group.cpp')
| -rw-r--r-- | comm/third_party/botan/src/lib/pubkey/dl_group/dl_group.cpp | 646 |
1 files changed, 646 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/pubkey/dl_group/dl_group.cpp b/comm/third_party/botan/src/lib/pubkey/dl_group/dl_group.cpp new file mode 100644 index 0000000000..05f9640e30 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/dl_group/dl_group.cpp @@ -0,0 +1,646 @@ +/* +* Discrete Logarithm Parameters +* (C) 1999-2008,2015,2018 Jack Lloyd +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include <botan/dl_group.h> +#include <botan/numthry.h> +#include <botan/reducer.h> +#include <botan/monty.h> +#include <botan/divide.h> +#include <botan/der_enc.h> +#include <botan/ber_dec.h> +#include <botan/pem.h> +#include <botan/workfactor.h> +#include <botan/internal/monty_exp.h> + +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& operator=(const 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); + } + + bool q_is_set() const { return m_q_bits > 0; } + + void assert_q_is_set(const std::string& function) const + { + if(q_is_set() == false) + throw Invalid_State("DL_Group::" + function + " q is not set for this group"); + } + + 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_cons(SEQUENCE); + + if(format == DL_Group::ANSI_X9_57) + { + ber.decode(p) + .decode(q) + .decode(g) + .verify_end(); + } + else if(format == DL_Group::ANSI_X9_42) + { + ber.decode(p) + .decode(g) + .decode(q) + .discard_remaining(); + } + else if(format == DL_Group::PKCS_3) + { + // q is left as zero + ber.decode(p) + .decode(g) + .discard_remaining(); + } + else + throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format)); + + 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(const std::string& label) + { + if(label == "DH PARAMETERS") + return DL_Group::PKCS_3; + else if(label == "DSA PARAMETERS") + return DL_Group::ANSI_X9_57; + else if(label == "X942 DH PARAMETERS" || label == "X9.42 DH PARAMETERS") + return DL_Group::ANSI_X9_42; + else + throw Decoding_Error("DL_Group: Invalid PEM label " + label); + } + +} + +/* +* DL_Group Constructor +*/ +DL_Group::DL_Group(const std::string& 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)); + 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("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(PRIMES[i], e, p); + if(g > 1) + return g; + } + + throw Internal_Error("DL_Group: Couldn't create a suitable generator"); + } + +} + +/* +* DL_Group Constructor +*/ +DL_Group::DL_Group(RandomNumberGenerator& rng, + PrimeType type, size_t pbits, size_t qbits) + { + if(pbits < 1024) + throw Invalid_Argument("DL_Group: prime size " + std::to_string(pbits) + " is too small"); + + 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 = 2; + if(jacobi(g, p) != 1) + { + // prime table does not contain 2 + for(size_t i = 0; i < PRIME_TABLE_SIZE; ++i) + { + g = 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, 0, 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(power_mod(y, q, p) != 1) + 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 != 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(q != 0) + { + if((p - 1) % q != 0) + { + return false; + } + if(this->power_g_p(q) != 1) + { + return false; + } + if(!is_prime(q, rng, test_prob, is_randomly_generated)) + { + return false; + } + } + + if(!is_prime(p, rng, test_prob, is_randomly_generated)) + { + 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(); + } + +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); + } + +DL_Group_Source DL_Group::source() const + { + return data().source(); + } + +/* +* DER encode the parameters +*/ +std::vector<uint8_t> DL_Group::DER_encode(Format format) const + { + if(get_q().is_zero() && (format == ANSI_X9_57 || format == ANSI_X9_42)) + 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 == ANSI_X9_57) + { + der.start_cons(SEQUENCE) + .encode(get_p()) + .encode(get_q()) + .encode(get_g()) + .end_cons(); + } + else if(format == ANSI_X9_42) + { + der.start_cons(SEQUENCE) + .encode(get_p()) + .encode(get_g()) + .encode(get_q()) + .end_cons(); + } + else if(format == PKCS_3) + { + der.start_cons(SEQUENCE) + .encode(get_p()) + .encode(get_g()) + .end_cons(); + } + else + throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format)); + + return output; + } + +/* +* PEM encode the parameters +*/ +std::string DL_Group::PEM_encode(Format format) const + { + const std::vector<uint8_t> encoding = DER_encode(format); + + if(format == PKCS_3) + return PEM_Code::encode(encoding, "DH PARAMETERS"); + else if(format == ANSI_X9_57) + return PEM_Code::encode(encoding, "DSA PARAMETERS"); + else if(format == ANSI_X9_42) + return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS"); + else + throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format)); + } + +DL_Group::DL_Group(const uint8_t ber[], size_t ber_len, 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, 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(const std::string& pem) + { + std::string label; + const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label)); + Format format = pem_label_to_dl_format(label); + return DL_Group(ber, format); + } + +/* +* Decode PEM encoded parameters +*/ +void DL_Group::PEM_decode(const std::string& pem) + { + std::string label; + const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label)); + Format format = pem_label_to_dl_format(label); + + m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource); + } + +//static +std::string DL_Group::PEM_for_named_group(const std::string& name) + { + DL_Group group(name); + DL_Group::Format format = group.get_q().is_zero() ? DL_Group::PKCS_3 : DL_Group::ANSI_X9_42; + return group.PEM_encode(format); + } + +} |