Botan 2.19.3
Crypto and TLS for C&
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
13namespace Botan {
14
15namespace {
16
17/*
18* Check if this size is allowed by FIPS 186-3
19*/
20bool 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*/
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}
void binary_decode(const uint8_t buf[], size_t length)
Definition bigint.cpp:432
void set_bit(size_t n)
Definition bigint.h:430
size_t bits() const
Definition bigint.cpp:296
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition hash.cpp:329
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:37
virtual void randomize(uint8_t output[], size_t length)=0
int(* final)(unsigned char *, CTX *)
fe X
Definition ge.cpp:27
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:228
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
MechanismType hash