8#include <botan/dl_group.h>
9#include <botan/numthry.h>
10#include <botan/reducer.h>
11#include <botan/monty.h>
12#include <botan/divide.h>
13#include <botan/der_enc.h>
14#include <botan/ber_dec.h>
16#include <botan/workfactor.h>
17#include <botan/internal/monty_exp.h>
21class DL_Group_Data
final
24 DL_Group_Data(
const BigInt& p,
const BigInt& q,
const BigInt& g,
DL_Group_Source source) :
25 m_p(p), m_q(q), m_g(g),
28 m_monty_params(
std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
38 ~DL_Group_Data() =
default;
40 DL_Group_Data(
const DL_Group_Data& other) =
delete;
41 DL_Group_Data& operator=(
const DL_Group_Data& other) =
delete;
43 const BigInt& p()
const {
return m_p; }
44 const BigInt& q()
const {
return m_q; }
45 const BigInt& g()
const {
return m_g; }
47 BigInt mod_p(
const BigInt& x)
const {
return m_mod_p.reduce(x); }
49 BigInt multiply_mod_p(
const BigInt& x,
const BigInt& y)
const
51 return m_mod_p.multiply(x, y);
54 BigInt mod_q(
const BigInt& x)
const {
return m_mod_q.reduce(x); }
56 BigInt multiply_mod_q(
const BigInt& x,
const BigInt& y)
const
58 return m_mod_q.multiply(x, y);
61 BigInt square_mod_q(
const BigInt& x)
const
63 return m_mod_q.square(x);
66 std::shared_ptr<const Montgomery_Params> monty_params_p()
const
67 {
return m_monty_params; }
69 size_t p_bits()
const {
return m_p_bits; }
70 size_t q_bits()
const {
return m_q_bits; }
71 size_t p_bytes()
const {
return (m_p_bits + 7) / 8; }
72 size_t q_bytes()
const {
return (m_q_bits + 7) / 8; }
74 size_t estimated_strength()
const {
return m_estimated_strength; }
76 size_t exponent_bits()
const {
return m_exponent_bits; }
78 BigInt power_g_p(
const BigInt& k,
size_t max_k_bits)
const
83 bool q_is_set()
const {
return m_q_bits > 0; }
85 void assert_q_is_set(
const std::string& function)
const
87 if(q_is_set() ==
false)
88 throw Invalid_State(
"DL_Group::" + function +
" q is not set for this group");
97 Modular_Reducer m_mod_p;
98 Modular_Reducer m_mod_q;
99 std::shared_ptr<const Montgomery_Params> m_monty_params;
100 std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
103 size_t m_estimated_strength;
104 size_t m_exponent_bits;
109std::shared_ptr<DL_Group_Data> DL_Group::BER_decode_DL_group(
const uint8_t data[],
size_t data_len,
115 BER_Decoder decoder(data, data_len);
116 BER_Decoder ber = decoder.start_cons(
SEQUENCE);
130 .discard_remaining();
137 .discard_remaining();
140 throw Invalid_Argument(
"Unknown DL_Group encoding " + std::to_string(format));
142 return std::make_shared<DL_Group_Data>(p, q, g,
source);
146std::shared_ptr<DL_Group_Data>
147DL_Group::load_DL_group_info(
const char* p_str,
151 const BigInt p(p_str);
152 const BigInt q(q_str);
153 const BigInt g(g_str);
159std::shared_ptr<DL_Group_Data>
160DL_Group::load_DL_group_info(
const char* p_str,
163 const BigInt p(p_str);
164 const BigInt q = (p - 1) / 2;
165 const BigInt g(g_str);
174 if(label ==
"DH PARAMETERS")
176 else if(label ==
"DSA PARAMETERS")
178 else if(label ==
"X942 DH PARAMETERS" || label ==
"X9.42 DH PARAMETERS")
181 throw Decoding_Error(
"DL_Group: Invalid PEM label " + label);
194 if(m_data ==
nullptr)
200 Format format = pem_label_to_dl_format(label);
207 if(m_data ==
nullptr)
232 throw Internal_Error(
"DL_Group: Couldn't create a suitable generator");
244 throw Invalid_Argument(
"DL_Group: prime size " + std::to_string(pbits) +
" is too small");
248 if(qbits != 0 && qbits != pbits - 1)
249 throw Invalid_Argument(
"Cannot create strong-prime DL_Group with specified q bits");
252 const BigInt q = (p - 1) / 2;
281 while(p.
bits() != pbits || !
is_prime(p, rng, 128,
true))
287 const BigInt g = make_dsa_generator(p, q);
293 qbits = ((pbits <= 1024) ? 160 : 256);
297 const BigInt g = make_dsa_generator(p, q);
310 const std::vector<uint8_t>& seed,
311 size_t pbits,
size_t qbits)
316 throw Invalid_Argument(
"DL_Group: The seed given does not generate a DSA group");
318 BigInt g = make_dsa_generator(p, q);
339const DL_Group_Data& DL_Group::data()
const
368 if(y <= 1 || y >= p || x <= 1 || x >= p)
385 if(!strong && from_builtin)
392 if(g < 2 || p < 3 || q < 0)
395 const size_t test_prob = 128;
408 if(!
is_prime(q, rng, test_prob, is_randomly_generated))
414 if(!
is_prime(p, rng, test_prob, is_randomly_generated))
448 return data().monty_params_p();
453 return data().p_bits();
458 return data().p_bytes();
463 data().assert_q_is_set(
"q_bits");
464 return data().q_bits();
469 data().assert_q_is_set(
"q_bytes");
470 return data().q_bytes();
475 return data().estimated_strength();
480 return data().exponent_bits();
491 return data().mod_p(x);
496 return data().multiply_mod_p(x, y);
501 data().assert_q_is_set(
"inverse_mod_q");
508 data().assert_q_is_set(
"mod_q");
509 return data().mod_q(x);
514 data().assert_q_is_set(
"multiply_mod_q");
515 return data().multiply_mod_q(x, y);
520 data().assert_q_is_set(
"multiply_mod_q");
526 data().assert_q_is_set(
"square_mod_q");
527 return data().square_mod_q(x);
537 return data().power_g_p(x, x.
bits());
542 return data().power_g_p(x, max_x_bits);
547 return data().source();
556 throw Encoding_Error(
"Cannot encode DL_Group in ANSI formats when q param is missing");
558 std::vector<uint8_t> output;
585 throw Invalid_Argument(
"Unknown DL_Group encoding " + std::to_string(format));
595 const std::vector<uint8_t> encoding =
DER_encode(format);
604 throw Invalid_Argument(
"Unknown DL_Group encoding " + std::to_string(format));
622 Format format = pem_label_to_dl_format(label);
633 Format format = pem_label_to_dl_format(label);
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
DER_Encoder & start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
DER_Encoder & encode(bool b)
std::vector< uint8_t > DER_encode(Format format) const
BigInt power_g_p(const BigInt &x) const
BigInt mod_p(const BigInt &x) const
static std::string PEM_for_named_group(const std::string &name)
BigInt multiply_mod_p(const BigInt &x, const BigInt &y) const
std::shared_ptr< const Montgomery_Params > monty_params_p() const
const BigInt & get_p() const
BigInt multi_exponentiate(const BigInt &x, const BigInt &y, const BigInt &z) const
bool verify_public_element(const BigInt &y) const
BigInt square_mod_q(const BigInt &x) const
static std::shared_ptr< DL_Group_Data > DL_group_info(const std::string &name)
BigInt inverse_mod_q(const BigInt &x) const
bool verify_element_pair(const BigInt &y, const BigInt &x) const
size_t estimated_strength() const
DL_Group_Source source() const
BigInt multiply_mod_q(const BigInt &x, const BigInt &y) const
BigInt inverse_mod_p(const BigInt &x) const
static DL_Group DL_Group_from_PEM(const std::string &pem)
void PEM_decode(const std::string &pem)
size_t exponent_bits() const
BigInt mod_q(const BigInt &x) const
void BER_decode(const std::vector< uint8_t > &ber, Format format)
bool verify_group(RandomNumberGenerator &rng, bool strong=true) const
const BigInt & get_g() const
const BigInt & get_q() const
std::string PEM_encode(Format format) const
BigInt reduce(const BigInt &x) const
int(* final)(unsigned char *, CTX *)
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
size_t dl_work_factor(size_t bits)
const size_t PRIME_TABLE_SIZE
BigInt monty_multi_exp(std::shared_ptr< const Montgomery_Params > params_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)
size_t dl_exponent_size(size_t bits)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
bool generate_dsa_primes(RandomNumberGenerator &rng, BigInt &p, BigInt &q, size_t pbits, size_t qbits, const std::vector< uint8_t > &seed_c, size_t offset)
std::vector< T > unlock(const secure_vector< T > &in)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(std::shared_ptr< const Montgomery_Params > params, const BigInt &g, size_t window_bits, bool const_time)
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
int32_t jacobi(const BigInt &a, const BigInt &n)
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)