Botan  2.7.0
Crypto and TLS for C++11
dsa_gen.cpp
Go to the documentation of this file.
1 /*
2 * DSA Parameter Generation
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/numthry.h>
9 #include <botan/hash.h>
10 #include <botan/reducer.h>
11 #include <botan/rng.h>
12 
13 namespace Botan {
14 
15 namespace {
16 
17 /*
18 * Check if this size is allowed by FIPS 186-3
19 */
20 bool fips186_3_valid_size(size_t pbits, size_t qbits)
21  {
22  if(qbits == 160)
23  return (pbits == 1024);
24 
25  if(qbits == 224)
26  return (pbits == 2048);
27 
28  if(qbits == 256)
29  return (pbits == 2048 || pbits == 3072);
30 
31  return false;
32  }
33 
34 }
35 
36 /*
37 * Attempt DSA prime generation with given seed
38 */
40  BigInt& p, BigInt& q,
41  size_t pbits, size_t qbits,
42  const std::vector<uint8_t>& seed_c,
43  size_t offset)
44  {
45  if(!fips186_3_valid_size(pbits, qbits))
46  throw Invalid_Argument(
47  "FIPS 186-3 does not allow DSA domain parameters of " +
48  std::to_string(pbits) + "/" + std::to_string(qbits) + " bits long");
49 
50  if(seed_c.size() * 8 < qbits)
51  throw Invalid_Argument(
52  "Generating a DSA parameter set with a " + std::to_string(qbits) +
53  " bit long q requires a seed at least as many bits long");
54 
55  const std::string hash_name = "SHA-" + std::to_string(qbits);
56  std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw(hash_name));
57 
58  const size_t HASH_SIZE = hash->output_length();
59 
60  class Seed final
61  {
62  public:
63  explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {}
64 
65  const std::vector<uint8_t>& value() const { return m_seed; }
66 
67  Seed& operator++()
68  {
69  for(size_t j = m_seed.size(); j > 0; --j)
70  if(++m_seed[j-1])
71  break;
72  return (*this);
73  }
74  private:
75  std::vector<uint8_t> m_seed;
76  };
77 
78  Seed seed(seed_c);
79 
80  q.binary_decode(hash->process(seed.value()));
81  q.set_bit(qbits-1);
82  q.set_bit(0);
83 
84  if(!is_prime(q, rng, 128, true))
85  return false;
86 
87  const size_t n = (pbits-1) / (HASH_SIZE * 8),
88  b = (pbits-1) % (HASH_SIZE * 8);
89 
90  BigInt X;
91  std::vector<uint8_t> V(HASH_SIZE * (n+1));
92 
93  Modular_Reducer mod_2q(2*q);
94 
95  for(size_t j = 0; j != 4*pbits; ++j)
96  {
97  for(size_t k = 0; k <= n; ++k)
98  {
99  ++seed;
100  hash->update(seed.value());
101  hash->final(&V[HASH_SIZE * (n-k)]);
102  }
103 
104  if(j >= offset)
105  {
106  X.binary_decode(&V[HASH_SIZE - 1 - b/8],
107  V.size() - (HASH_SIZE - 1 - b/8));
108  X.set_bit(pbits-1);
109 
110  p = X - (mod_2q.reduce(X) - 1);
111 
112  if(p.bits() == pbits && is_prime(p, rng, 128, true))
113  return true;
114  }
115  }
116  return false;
117  }
118 
119 /*
120 * Generate DSA Primes
121 */
122 std::vector<uint8_t> generate_dsa_primes(RandomNumberGenerator& rng,
123  BigInt& p, BigInt& q,
124  size_t pbits, size_t qbits)
125  {
126  while(true)
127  {
128  std::vector<uint8_t> seed(qbits / 8);
129  rng.randomize(seed.data(), seed.size());
130 
131  if(generate_dsa_primes(rng, p, q, pbits, qbits, seed))
132  return seed;
133  }
134  }
135 
136 }
fe X
Definition: ge.cpp:27
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: hash.cpp:345
virtual void randomize(uint8_t output[], size_t length)=0
size_t bits() const
Definition: bigint.cpp:228
void set_bit(size_t n)
Definition: bigint.cpp:201
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:507
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:210
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)
Definition: dsa_gen.cpp:39
Definition: alg_id.cpp:13
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:38
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:326
MechanismType hash