Botan 3.0.0
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/internal/primality.h>
9#include <botan/internal/fmt.h>
10#include <botan/numthry.h>
11#include <botan/hash.h>
12#include <botan/reducer.h>
13#include <botan/rng.h>
14
15namespace Botan {
16
17namespace {
18
19/*
20* Check if this size is allowed by FIPS 186-3
21*/
22bool fips186_3_valid_size(size_t pbits, size_t qbits)
23 {
24 if(qbits == 160)
25 return (pbits == 1024);
26
27 if(qbits == 224)
28 return (pbits == 2048);
29
30 if(qbits == 256)
31 return (pbits == 2048 || pbits == 3072);
32
33 return false;
34 }
35
36// qbits assumed to be a valid size for FIPS param gen
37std::string hash_function_for(size_t qbits)
38 {
39 if(qbits == 160)
40 return "SHA-1";
41
42 return "SHA-" + std::to_string(qbits);
43 }
44
45}
46
47/*
48* Attempt DSA prime generation with given seed
49*/
51 BigInt& p, BigInt& q,
52 size_t pbits, size_t qbits,
53 const std::vector<uint8_t>& seed_c,
54 size_t offset)
55 {
56 if(!fips186_3_valid_size(pbits, qbits))
57 {
58 throw Invalid_Argument(
59 fmt("FIPS 186-3 does not allow DSA domain parameters of {}/{} bits long",
60 pbits, qbits));
61 }
62
63 if(seed_c.size() * 8 < qbits)
64 {
65 throw Invalid_Argument(
66 fmt("Generating a DSA parameter set with a {} bit long q requires a seed at least as many bits long", qbits));
67 }
68
69 const std::string hash_name = hash_function_for(qbits);
70 auto hash = HashFunction::create_or_throw(hash_name);
71
72 const size_t HASH_SIZE = hash->output_length();
73
74 class Seed final
75 {
76 public:
77 explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {}
78
79 const std::vector<uint8_t>& value() const { return m_seed; }
80
81 Seed& operator++()
82 {
83 for(size_t j = m_seed.size(); j > 0; --j)
84 if(++m_seed[j-1])
85 break;
86 return (*this);
87 }
88 private:
89 std::vector<uint8_t> m_seed;
90 };
91
92 Seed seed(seed_c);
93
94 q.binary_decode(hash->process(seed.value()));
95 q.set_bit(qbits-1);
96 q.set_bit(0);
97
98 if(!is_prime(q, rng, 128, true))
99 return false;
100
101 const size_t n = (pbits-1) / (HASH_SIZE * 8),
102 b = (pbits-1) % (HASH_SIZE * 8);
103
104 BigInt X;
105 std::vector<uint8_t> V(HASH_SIZE * (n+1));
106
107 Modular_Reducer mod_2q(2*q);
108
109 for(size_t j = 0; j != 4*pbits; ++j)
110 {
111 for(size_t k = 0; k <= n; ++k)
112 {
113 ++seed;
114 hash->update(seed.value());
115 hash->final(&V[HASH_SIZE * (n-k)]);
116 }
117
118 if(j >= offset)
119 {
120 X.binary_decode(&V[HASH_SIZE - 1 - b/8],
121 V.size() - (HASH_SIZE - 1 - b/8));
122 X.set_bit(pbits-1);
123
124 p = X - (mod_2q.reduce(X) - 1);
125
126 if(p.bits() == pbits && is_prime(p, rng, 128, true))
127 return true;
128 }
129 }
130 return false;
131 }
132
133/*
134* Generate DSA Primes
135*/
137 BigInt& p, BigInt& q,
138 size_t pbits, size_t qbits)
139 {
140 while(true)
141 {
142 std::vector<uint8_t> seed(qbits / 8);
143 rng.randomize(seed.data(), seed.size());
144
145 if(generate_dsa_primes(rng, p, q, pbits, qbits, seed))
146 return seed;
147 }
148 }
149
150}
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:431
void set_bit(size_t n)
Definition: bigint.h:443
size_t bits() const
Definition: bigint.cpp:312
static std::unique_ptr< HashFunction > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Definition: hash.cpp:320
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
void randomize(std::span< uint8_t > output)
Definition: rng.h:53
int(* final)(unsigned char *, CTX *)
FE_25519 X
Definition: ge.cpp:26
Definition: alg_id.cpp:12
std::string fmt(std::string_view format, const T &... args)
Definition: fmt.h:60
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:370
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:50