text: /*
   * Discrete Logarithm Parameters
   * (C) 1999-2008,2015,2018 Jack Lloyd
   *
   * Botan is released under the Simplified BSD License (see license.txt)
   */
  
  #include <botan/ber_dec.h>
  #include <botan/der_enc.h>
  #include <botan/dl_group.h>
  #include <botan/internal/divide.h>
  #include <botan/internal/monty.h>
  #include <botan/internal/monty_exp.h>
  #include <botan/internal/primality.h>
  #include <botan/internal/workfactor.h>
  #include <botan/numthry.h>
  #include <botan/pem.h>
  #include <botan/reducer.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);
  }
  
  } // namespace
  
  /*
   * 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");
  }
  
  } // namespace
  
  /*
   * 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);
  }
  
  } // namespace Botan
  