Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

dl_group.cpp
Go to the documentation of this file.
1 /*
2 * Discrete Logarithm Parameters
3 * (C) 1999-2008,2015 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7
8 #include <botan/dl_group.h>
9 #include <botan/parsing.h>
10 #include <botan/numthry.h>
11 #include <botan/der_enc.h>
12 #include <botan/ber_dec.h>
13 #include <botan/pem.h>
14 #include <botan/workfactor.h>
15 #include <botan/pow_mod.h>
16
17 namespace Botan {
18
19 /*
20 * DL_Group Constructor
21 */
22 DL_Group::DL_Group()
23 {
24 m_initialized = false;
25 }
26
27 /*
28 * DL_Group Constructor
29 */
30 DL_Group::DL_Group(const std::string& name)
31 {
32 const std::string pem = PEM_for_named_group(name);
33
34 if(pem == "")
35 throw Invalid_Argument("DL_Group: Unknown group " + name);
36
37 PEM_decode(pem);
38 }
39
40 /*
41 * DL_Group Constructor
42 */
43 DL_Group::DL_Group(RandomNumberGenerator& rng,
44 PrimeType type, size_t pbits, size_t qbits)
45 {
46 if(pbits < 1024)
47 throw Invalid_Argument("DL_Group: prime size " + std::to_string(pbits) +
48 " is too small");
49
50 if(type == Strong)
51 {
52 m_p = random_safe_prime(rng, pbits);
53 m_q = (m_p - 1) / 2;
54 m_g = 2;
55
56 /*
57 Always choose a generator that is quadratic reside mod p,
58 this forces g to be a generator of the subgroup of size q.
59 */
60 if(jacobi(m_g, m_p) != 1)
61 {
62 // prime table does not contain 2
63 for(size_t i = 0; i < PRIME_TABLE_SIZE; ++i)
64 {
65 m_g = PRIMES[i];
66 if(jacobi(m_g, m_p) == 1)
67 break;
68 }
69 }
70 }
71 else if(type == Prime_Subgroup)
72 {
73 if(!qbits)
74 qbits = dl_exponent_size(pbits);
75
76 m_q = random_prime(rng, qbits);
77 BigInt X;
78 while(m_p.bits() != pbits || !is_prime(m_p, rng))
79 {
80 X.randomize(rng, pbits);
81 m_p = X - (X % (2*m_q) - 1);
82 }
83
84 m_g = make_dsa_generator(m_p, m_q);
85 }
86 else if(type == DSA_Kosherizer)
87 {
88 qbits = qbits ? qbits : ((pbits <= 1024) ? 160 : 256);
89
90 generate_dsa_primes(rng, m_p, m_q, pbits, qbits);
91
92 m_g = make_dsa_generator(m_p, m_q);
93 }
94
95 m_initialized = true;
96 }
97
98 /*
99 * DL_Group Constructor
100 */
101 DL_Group::DL_Group(RandomNumberGenerator& rng,
102 const std::vector<uint8_t>& seed,
103 size_t pbits, size_t qbits)
104 {
105 if(!generate_dsa_primes(rng, m_p, m_q, pbits, qbits, seed))
106 throw Invalid_Argument("DL_Group: The seed given does not "
107 "generate a DSA group");
108
109 m_g = make_dsa_generator(m_p, m_q);
110
111 m_initialized = true;
112 }
113
114 /*
115 * DL_Group Constructor
116 */
117 DL_Group::DL_Group(const BigInt& p1, const BigInt& g1)
118 {
119 initialize(p1, 0, g1);
120 }
121
122 /*
123 * DL_Group Constructor
124 */
125 DL_Group::DL_Group(const BigInt& p1, const BigInt& q1, const BigInt& g1)
126 {
127 initialize(p1, q1, g1);
128 }
129
130 /*
131 * DL_Group Initializer
132 */
133 void DL_Group::initialize(const BigInt& p1, const BigInt& q1, const BigInt& g1)
134 {
135 if(p1 < 3)
136 throw Invalid_Argument("DL_Group: Prime invalid");
137 if(g1 < 2 || g1 >= p1)
138 throw Invalid_Argument("DL_Group: Generator invalid");
139 if(q1 < 0 || q1 >= p1)
140 throw Invalid_Argument("DL_Group: Subgroup invalid");
141
142 m_p = p1;
143 m_g = g1;
144 m_q = q1;
145
146 m_initialized = true;
147 }
148
149 /*
150 * Verify that the group has been set
151 */
152 void DL_Group::init_check() const
153 {
154 if(!m_initialized)
155 throw Invalid_State("DLP group cannot be used uninitialized");
156 }
157
158 /*
159 * Verify the parameters
160 */
161 bool DL_Group::verify_group(RandomNumberGenerator& rng,
162 bool strong) const
163 {
164 init_check();
165
166 if(m_g < 2 || m_p < 3 || m_q < 0)
167 return false;
168
169 const size_t prob = (strong) ? 128 : 10;
170
171 if(m_q != 0)
172 {
173 if((m_p - 1) % m_q != 0)
174 {
175 return false;
176 }
177 if(power_mod(m_g, m_q, m_p) != 1)
178 {
179 return false;
180 }
181 if(!is_prime(m_q, rng, prob))
182 {
183 return false;
184 }
185 }
186 if(!is_prime(m_p, rng, prob))
187 {
188 return false;
189 }
190 return true;
191 }
192
193 /*
194 * Return the prime
195 */
196 const BigInt& DL_Group::get_p() const
197 {
198 init_check();
199 return m_p;
200 }
201
202 /*
203 * Return the generator
204 */
205 const BigInt& DL_Group::get_g() const
206 {
207 init_check();
208 return m_g;
209 }
210
211 /*
212 * Return the subgroup
213 */
214 const BigInt& DL_Group::get_q() const
215 {
216 init_check();
217 if(m_q == 0)
218 throw Invalid_State("DLP group has no q prime specified");
219 return m_q;
220 }
221
222 /*
223 * DER encode the parameters
224 */
225 std::vector<uint8_t> DL_Group::DER_encode(Format format) const
226 {
227 init_check();
228
229 if((m_q == 0) && (format != PKCS_3))
230 throw Encoding_Error("The ANSI DL parameter formats require a subgroup");
231
232 if(format == ANSI_X9_57)
233 {
234 return DER_Encoder()
235 .start_cons(SEQUENCE)
236 .encode(m_p)
237 .encode(m_q)
238 .encode(m_g)
239 .end_cons()
240 .get_contents_unlocked();
241 }
242 else if(format == ANSI_X9_42)
243 {
244 return DER_Encoder()
245 .start_cons(SEQUENCE)
246 .encode(m_p)
247 .encode(m_g)
248 .encode(m_q)
249 .end_cons()
250 .get_contents_unlocked();
251 }
252 else if(format == PKCS_3)
253 {
254 return DER_Encoder()
255 .start_cons(SEQUENCE)
256 .encode(m_p)
257 .encode(m_g)
258 .end_cons()
259 .get_contents_unlocked();
260 }
261
262 throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
263 }
264
265 /*
266 * PEM encode the parameters
267 */
268 std::string DL_Group::PEM_encode(Format format) const
269 {
270 const std::vector<uint8_t> encoding = DER_encode(format);
271
272 if(format == PKCS_3)
273 return PEM_Code::encode(encoding, "DH PARAMETERS");
274 else if(format == ANSI_X9_57)
275 return PEM_Code::encode(encoding, "DSA PARAMETERS");
276 else if(format == ANSI_X9_42)
277 return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS");
278 else
279 throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
280 }
281
282 /*
283 * Decode BER encoded parameters
284 */
285 void DL_Group::BER_decode(const std::vector<uint8_t>& data,
286 Format format)
287 {
288 BigInt new_p, new_q, new_g;
289
290 BER_Decoder decoder(data);
291 BER_Decoder ber = decoder.start_cons(SEQUENCE);
292
293 if(format == ANSI_X9_57)
294 {
295 ber.decode(new_p)
296 .decode(new_q)
297 .decode(new_g)
298 .verify_end();
299 }
300 else if(format == ANSI_X9_42)
301 {
302 ber.decode(new_p)
303 .decode(new_g)
304 .decode(new_q)
305 .discard_remaining();
306 }
307 else if(format == PKCS_3)
308 {
309 ber.decode(new_p)
310 .decode(new_g)
311 .discard_remaining();
312 }
313 else
314 throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
315
316 initialize(new_p, new_q, new_g);
317 }
318
319 /*
320 * Decode PEM encoded parameters
321 */
322 void DL_Group::PEM_decode(const std::string& pem)
323 {
324 std::string label;
325
326 auto ber = unlock(PEM_Code::decode(pem, label));
327
328 if(label == "DH PARAMETERS")
329 BER_decode(ber, PKCS_3);
330 else if(label == "DSA PARAMETERS")
331 BER_decode(ber, ANSI_X9_57);
332 else if(label == "X942 DH PARAMETERS" || label == "X9.42 DH PARAMETERS")
333 BER_decode(ber, ANSI_X9_42);
334 else
335 throw Decoding_Error("DL_Group: Invalid PEM label " + label);
336 }
337
338 /*
339 * Create generator of the q-sized subgroup (DSA style generator)
340 */
341 BigInt DL_Group::make_dsa_generator(const BigInt& p, const BigInt& q)
342 {
343 const BigInt e = (p - 1) / q;
344
345 if(e == 0 || (p - 1) % q > 0)
346 throw Invalid_Argument("make_dsa_generator q does not divide p-1");
347
348 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
349 {
350 BigInt g = power_mod(PRIMES[i], e, p);
351 if(g > 1)
352 return g;
353 }
354
355 throw Internal_Error("DL_Group: Couldn't create a suitable generator");
356 }
357
358 }
Botan::PRIME_TABLE_SIZE
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
Botan::DL_Group::Prime_Subgroup
Definition: dl_group.h:59
Botan::Invalid_Argument
Definition: exceptn.h:34
Botan::DL_Group::PKCS_3
Definition: dl_group.h:48
Botan::PEM_Code::decode
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:68
Botan::DL_Group::DL_Group
DL_Group()
Definition: dl_group.cpp:22
Botan::PRIMES
const uint16_t BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
Botan::BigInt
Definition: bigint.h:23
Botan::DL_Group::PEM_encode
std::string PEM_encode(Format format) const
Definition: dl_group.cpp:268
Botan::dl_exponent_size
size_t dl_exponent_size(size_t bits)
Definition: workfactor.cpp:40
Botan::DER_Encoder::get_contents_unlocked
std::vector< uint8_t > get_contents_unlocked()
Definition: der_enc.h:27
Botan::RandomNumberGenerator
Definition: rng.h:25
Botan::DL_Group::ANSI_X9_57
Definition: dl_group.h:47
Botan::BigInt::randomize
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
Botan::PEM_Code::encode
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
Botan::is_prime
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:441
Botan::DL_Group::verify_group
bool verify_group(RandomNumberGenerator &rng, bool strong) const
Definition: dl_group.cpp:161
Botan::Invalid_State
Definition: exceptn.h:61
Botan::DL_Group::get_q
const BigInt & get_q() const
Definition: dl_group.cpp:214
Botan::DL_Group::Strong
Definition: dl_group.h:59
Botan::BER_Decoder::decode
BER_Decoder & decode(bool &v)
Definition: ber_dec.cpp:376
Botan::DL_Group::get_p
const BigInt & get_p() const
Definition: dl_group.cpp:196
Botan::ASN1::to_string
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:47
type
MechanismType type
Definition: p11_mechanism.cpp:43
Botan::DER_Encoder::end_cons
DER_Encoder & end_cons()
Definition: der_enc.cpp:147
Botan::DL_Group::PEM_decode
void PEM_decode(const std::string &pem)
Definition: dl_group.cpp:322
Botan::DL_Group::DER_encode
std::vector< uint8_t > DER_encode(Format format) const
Definition: dl_group.cpp:225
Botan::generate_dsa_primes
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
Botan::DER_Encoder::encode
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:216
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:184
Botan::DER_Encoder
Definition: der_enc.h:22
Botan::DL_Group::get_g
const BigInt & get_g() const
Definition: dl_group.cpp:205
Botan::DL_Group::Format
Format
Definition: dl_group.h:45
Botan::DL_Group::PrimeType
PrimeType
Definition: dl_group.h:59
Botan::Decoding_Error
Definition: exceptn.h:189
Botan::SEQUENCE
Definition: asn1_obj.h:39
Botan::BER_Decoder::start_cons
BER_Decoder start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: ber_dec.cpp:258
Botan::BER_Decoder::discard_remaining
BER_Decoder & discard_remaining()
Definition: ber_dec.cpp:199
Botan
Definition: alg_id.cpp:13
Botan::DL_Group::ANSI_X9_42
Definition: dl_group.h:46
Botan::random_safe_prime
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:114
Botan::unlock
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:125
Botan::BER_Decoder::verify_end
BER_Decoder & verify_end()
Definition: ber_dec.cpp:168
Botan::power_mod
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:373
Botan::DER_Encoder::start_cons
DER_Encoder & start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: der_enc.cpp:137
Botan::DL_Group::DSA_Kosherizer
Definition: dl_group.h:59
Botan::DL_Group::BER_decode
void BER_decode(const std::vector< uint8_t > &ber, Format format)
Definition: dl_group.cpp:285
Botan::jacobi
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
Botan::BER_Decoder
Definition: ber_dec.h:19
Botan::DL_Group::PEM_for_named_group
static std::string PEM_for_named_group(const std::string &name)
Definition: dl_named.cpp:12
Botan::Encoding_Error
Definition: exceptn.h:180
Botan::random_prime
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17