8#include <botan/dl_group.h>
10#include <botan/ber_dec.h>
11#include <botan/der_enc.h>
12#include <botan/numthry.h>
14#include <botan/reducer.h>
15#include <botan/internal/divide.h>
16#include <botan/internal/fmt.h>
17#include <botan/internal/mod_inv.h>
18#include <botan/internal/monty.h>
19#include <botan/internal/monty_exp.h>
20#include <botan/internal/primality.h>
21#include <botan/internal/workfactor.h>
26class DL_Group_Data
final {
28 DL_Group_Data(
const BigInt& p,
const BigInt& q,
const BigInt& g,
DL_Group_Source source) :
32 m_mod_p(Modular_Reducer::for_public_modulus(p)),
33 m_mod_q(Modular_Reducer::for_public_modulus(q)),
34 m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
42 DL_Group_Data(
const BigInt& p,
const BigInt& g,
DL_Group_Source source) :
45 m_mod_p(Modular_Reducer::for_public_modulus(p)),
46 m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
54 ~DL_Group_Data() =
default;
56 DL_Group_Data(
const DL_Group_Data& other) =
delete;
57 DL_Group_Data(DL_Group_Data&& other) =
delete;
58 DL_Group_Data& operator=(
const DL_Group_Data& other) =
delete;
59 DL_Group_Data& operator=(DL_Group_Data&& other) =
delete;
61 const BigInt& p()
const {
return m_p; }
63 const BigInt& q()
const {
return m_q; }
65 const BigInt& g()
const {
return m_g; }
67 const Modular_Reducer& reducer_mod_p()
const {
return m_mod_p; }
69 const Modular_Reducer& reducer_mod_q()
const {
74 std::shared_ptr<const Montgomery_Params> monty_params_p()
const {
return m_monty_params; }
76 size_t p_bits()
const {
return m_p_bits; }
78 size_t q_bits()
const {
return m_q_bits; }
80 size_t p_bytes()
const {
return (m_p_bits + 7) / 8; }
82 size_t q_bytes()
const {
return (m_q_bits + 7) / 8; }
84 size_t estimated_strength()
const {
return m_estimated_strength; }
86 size_t exponent_bits()
const {
return m_exponent_bits; }
88 BigInt power_g_p(
const BigInt& k,
size_t max_k_bits)
const {
94 BigInt power_b_p(
const BigInt&
b,
const BigInt& k,
size_t max_k_bits)
const {
98 BigInt power_b_p_vartime(
const BigInt&
b,
const BigInt& k)
const {
102 bool q_is_set()
const {
return m_q_bits > 0; }
104 void assert_q_is_set(std::string_view function)
const {
105 if(q_is_set() ==
false) {
106 throw Invalid_State(
fmt(
"DL_Group::{}: q is not set for this group", function));
116 Modular_Reducer m_mod_p;
117 std::optional<Modular_Reducer> m_mod_q;
118 std::shared_ptr<const Montgomery_Params> m_monty_params;
119 std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
122 size_t m_estimated_strength;
123 size_t m_exponent_bits;
128std::shared_ptr<DL_Group_Data> DL_Group::BER_decode_DL_group(
const uint8_t data[],
132 BER_Decoder decoder(data, data_len);
133 BER_Decoder ber = decoder.start_sequence();
137 ber.decode(p).decode(q).decode(g).verify_end();
138 return std::make_shared<DL_Group_Data>(p, q, g,
source);
141 ber.decode(p).decode(g).decode(q).discard_remaining();
142 return std::make_shared<DL_Group_Data>(p, q, g,
source);
145 ber.decode(p).decode(g).discard_remaining();
146 return std::make_shared<DL_Group_Data>(p, g,
source);
148 throw Invalid_Argument(
"Unknown DL_Group encoding");
153std::shared_ptr<DL_Group_Data> DL_Group::load_DL_group_info(
const char* p_str,
const char* q_str,
const char* g_str) {
154 const BigInt p(p_str);
155 const BigInt q(q_str);
156 const BigInt g(g_str);
166std::shared_ptr<DL_Group_Data> DL_Group::load_DL_group_info(
const char* p_str,
const char* g_str) {
167 const BigInt p(p_str);
168 const BigInt q = (p - 1) / 2;
169 const BigInt g(g_str);
177 if(label ==
"DH PARAMETERS") {
179 }
else if(label ==
"DSA PARAMETERS") {
181 }
else if(label ==
"X942 DH PARAMETERS" || label ==
"X9.42 DH PARAMETERS") {
184 throw Decoding_Error(
fmt(
"DL_Group: Unknown PEM label '{}'", label));
197 if(m_data ==
nullptr) {
207 if(m_data ==
nullptr) {
239 if(e == 0 || r > 0) {
251 throw Internal_Error(
"DL_Group: Couldn't create a suitable generator");
265 throw Invalid_Argument(
fmt(
"DL_Group: requested q size {} is too big for p {}", qbits, pbits));
269 if(qbits != 0 && qbits != pbits - 1) {
270 throw Invalid_Argument(
"Cannot create strong-prime DL_Group with specified q bits");
274 const BigInt q = (p - 1) / 2;
301 while(p.
bits() != pbits || !
is_prime(p, rng, 128,
true)) {
302 X.randomize(rng, pbits);
303 p =
X - mod_2q.reduce(
X) + 1;
306 const BigInt g = make_dsa_generator(p, q);
310 qbits = ((pbits <= 1024) ? 160 : 256);
315 const BigInt g = make_dsa_generator(p, q);
329 throw Invalid_Argument(
"DL_Group: The seed given does not generate a DSA group");
332 BigInt g = make_dsa_generator(p, q);
355const DL_Group_Data& DL_Group::data()
const {
360 throw Invalid_State(
"DL_Group uninitialized");
367 if(y <= 1 || y >= p) {
372 if(data().power_b_p_vartime(y, q) != 1) {
384 if(x <= 1 || x >= p) {
398 if(y <= 1 || y >= p || x <= 1 || x >= p) {
415 if(!strong && from_builtin) {
423 if(g < 2 || p < 3 || q < 0) {
427 const size_t test_prob = 128;
430 if(!
is_prime(p, rng, test_prob, is_randomly_generated)) {
435 if((p - 1) % q != 0) {
438 if(data().power_g_p_vartime(q) != 1) {
441 if(!
is_prime(q, rng, test_prob, is_randomly_generated)) {
445 if(!from_builtin && !is_randomly_generated) {
449 const size_t upper_bound = strong ? 1000 : 100;
451 for(
size_t i = 2; i != upper_bound; ++i) {
484 return data().monty_params_p();
488 return data().q_is_set();
492 return data().p_bits();
496 return data().p_bytes();
500 data().assert_q_is_set(
"q_bits");
501 return data().q_bits();
505 data().assert_q_is_set(
"q_bytes");
506 return data().q_bytes();
510 return data().estimated_strength();
514 return data().exponent_bits();
523 return data().reducer_mod_p().reduce(x);
527 return data().reducer_mod_p().multiply(x, y);
531 return data().reducer_mod_p();
535 data().assert_q_is_set(
"inverse_mod_q");
541 data().assert_q_is_set(
"mod_q");
542 return data().reducer_mod_q().reduce(x);
546 data().assert_q_is_set(
"multiply_mod_q");
547 return data().reducer_mod_q().multiply(x, y);
551 data().assert_q_is_set(
"multiply_mod_q");
556 data().assert_q_is_set(
"square_mod_q");
557 return data().reducer_mod_q().square(x);
565 return data().power_g_p(x, max_x_bits);
573 return data().power_b_p(
b, x, max_x_bits);
577 return data().source();
585 throw Encoding_Error(
"Cannot encode DL_Group in ANSI formats when q param is missing");
588 std::vector<uint8_t> output;
608 const std::vector<uint8_t> encoding =
DER_encode(format);
#define BOTAN_STATE_CHECK(expr)
static BigInt from_word(word n)
DER_Encoder & start_sequence()
DER_Encoder & encode(bool b)
bool verify_private_element(const BigInt &x) const
std::vector< uint8_t > DER_encode(DL_Group_Format format) const
BigInt power_g_p(const BigInt &x) const
static DL_Group from_PEM(std::string_view pem)
BigInt mod_p(const BigInt &x) const
BigInt multiply_mod_p(const BigInt &x, const BigInt &y) const
std::shared_ptr< const Montgomery_Params > monty_params_p() const
std::string PEM_encode(DL_Group_Format format) const
const BigInt & get_p() const
static DL_Group from_name(std::string_view name)
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
const Modular_Reducer & _reducer_mod_p() const
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
BigInt power_b_p(const BigInt &b, const BigInt &x, size_t max_x_bits) const
size_t exponent_bits() const
BigInt mod_q(const BigInt &x) const
bool verify_group(RandomNumberGenerator &rng, bool strong=true) const
const BigInt & get_g() const
static std::shared_ptr< DL_Group_Data > DL_group_info(std::string_view name)
const BigInt & get_q() const
static Modular_Reducer for_public_modulus(const BigInt &m)
int(* final)(unsigned char *, CTX *)
std::string encode(const uint8_t der[], size_t length, std::string_view 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)
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
std::string fmt(std::string_view format, const T &... args)
const size_t PRIME_TABLE_SIZE
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
size_t dl_work_factor(size_t bits)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
BigInt inverse_mod_public_prime(const BigInt &x, const BigInt &p)
std::vector< T > unlock(const secure_vector< T > &in)
Montgomery_Int monty_exp(const std::shared_ptr< const Montgomery_Params > ¶ms_p, const BigInt &g, const BigInt &k, size_t max_k_bits)
Montgomery_Int monty_exp_vartime(const std::shared_ptr< const Montgomery_Params > ¶ms_p, const BigInt &g, const BigInt &k)
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)
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
size_t dl_exponent_size(size_t bits)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
int32_t jacobi(const BigInt &a, const BigInt &n)
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Montgomery_Int monty_multi_exp(const std::shared_ptr< const Montgomery_Params > ¶ms_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)