Botan 2.19.1
Crypto and TLS for C&
dl_group.cpp
Go to the documentation of this file.
1/*
2* Discrete Logarithm Parameters
3* (C) 1999-2008,2015,2018 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/numthry.h>
10#include <botan/reducer.h>
11#include <botan/monty.h>
12#include <botan/divide.h>
13#include <botan/der_enc.h>
14#include <botan/ber_dec.h>
15#include <botan/pem.h>
16#include <botan/workfactor.h>
17#include <botan/internal/monty_exp.h>
18
19namespace Botan {
20
21class DL_Group_Data final
22 {
23 public:
24 DL_Group_Data(const BigInt& p, const BigInt& q, const BigInt& g, DL_Group_Source source) :
25 m_p(p), m_q(q), m_g(g),
26 m_mod_p(p),
27 m_mod_q(q),
28 m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
29 m_monty(monty_precompute(m_monty_params, m_g, /*window bits=*/4)),
30 m_p_bits(p.bits()),
31 m_q_bits(q.bits()),
32 m_estimated_strength(dl_work_factor(m_p_bits)),
33 m_exponent_bits(dl_exponent_size(m_p_bits)),
34 m_source(source)
35 {
36 }
37
38 ~DL_Group_Data() = default;
39
40 DL_Group_Data(const DL_Group_Data& other) = delete;
41 DL_Group_Data& operator=(const DL_Group_Data& other) = delete;
42
43 const BigInt& p() const { return m_p; }
44 const BigInt& q() const { return m_q; }
45 const BigInt& g() const { return m_g; }
46
47 BigInt mod_p(const BigInt& x) const { return m_mod_p.reduce(x); }
48
49 BigInt multiply_mod_p(const BigInt& x, const BigInt& y) const
50 {
51 return m_mod_p.multiply(x, y);
52 }
53
54 BigInt mod_q(const BigInt& x) const { return m_mod_q.reduce(x); }
55
56 BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const
57 {
58 return m_mod_q.multiply(x, y);
59 }
60
61 BigInt square_mod_q(const BigInt& x) const
62 {
63 return m_mod_q.square(x);
64 }
65
66 std::shared_ptr<const Montgomery_Params> monty_params_p() const
67 { return m_monty_params; }
68
69 size_t p_bits() const { return m_p_bits; }
70 size_t q_bits() const { return m_q_bits; }
71 size_t p_bytes() const { return (m_p_bits + 7) / 8; }
72 size_t q_bytes() const { return (m_q_bits + 7) / 8; }
73
74 size_t estimated_strength() const { return m_estimated_strength; }
75
76 size_t exponent_bits() const { return m_exponent_bits; }
77
78 BigInt power_g_p(const BigInt& k, size_t max_k_bits) const
79 {
80 return monty_execute(*m_monty, k, max_k_bits);
81 }
82
83 bool q_is_set() const { return m_q_bits > 0; }
84
85 void assert_q_is_set(const std::string& function) const
86 {
87 if(q_is_set() == false)
88 throw Invalid_State("DL_Group::" + function + " q is not set for this group");
89 }
90
91 DL_Group_Source source() const { return m_source; }
92
93 private:
94 BigInt m_p;
95 BigInt m_q;
96 BigInt m_g;
97 Modular_Reducer m_mod_p;
98 Modular_Reducer m_mod_q;
99 std::shared_ptr<const Montgomery_Params> m_monty_params;
100 std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
101 size_t m_p_bits;
102 size_t m_q_bits;
103 size_t m_estimated_strength;
104 size_t m_exponent_bits;
105 DL_Group_Source m_source;
106 };
107
108//static
109std::shared_ptr<DL_Group_Data> DL_Group::BER_decode_DL_group(const uint8_t data[], size_t data_len,
110 DL_Group::Format format,
111 DL_Group_Source source)
112 {
113 BigInt p, q, g;
114
115 BER_Decoder decoder(data, data_len);
116 BER_Decoder ber = decoder.start_cons(SEQUENCE);
117
118 if(format == DL_Group::ANSI_X9_57)
119 {
120 ber.decode(p)
121 .decode(q)
122 .decode(g)
123 .verify_end();
124 }
125 else if(format == DL_Group::ANSI_X9_42)
126 {
127 ber.decode(p)
128 .decode(g)
129 .decode(q)
130 .discard_remaining();
131 }
132 else if(format == DL_Group::PKCS_3)
133 {
134 // q is left as zero
135 ber.decode(p)
136 .decode(g)
137 .discard_remaining();
138 }
139 else
140 throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
141
142 return std::make_shared<DL_Group_Data>(p, q, g, source);
143 }
144
145//static
146std::shared_ptr<DL_Group_Data>
147DL_Group::load_DL_group_info(const char* p_str,
148 const char* q_str,
149 const char* g_str)
150 {
151 const BigInt p(p_str);
152 const BigInt q(q_str);
153 const BigInt g(g_str);
154
155 return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);
156 }
157
158//static
159std::shared_ptr<DL_Group_Data>
160DL_Group::load_DL_group_info(const char* p_str,
161 const char* g_str)
162 {
163 const BigInt p(p_str);
164 const BigInt q = (p - 1) / 2;
165 const BigInt g(g_str);
166
167 return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);
168 }
169
170namespace {
171
172DL_Group::Format pem_label_to_dl_format(const std::string& label)
173 {
174 if(label == "DH PARAMETERS")
175 return DL_Group::PKCS_3;
176 else if(label == "DSA PARAMETERS")
178 else if(label == "X942 DH PARAMETERS" || label == "X9.42 DH PARAMETERS")
180 else
181 throw Decoding_Error("DL_Group: Invalid PEM label " + label);
182 }
183
184}
185
186/*
187* DL_Group Constructor
188*/
189DL_Group::DL_Group(const std::string& str)
190 {
191 // Either a name or a PEM block, try name first
192 m_data = DL_group_info(str);
193
194 if(m_data == nullptr)
195 {
196 try
197 {
198 std::string label;
199 const std::vector<uint8_t> ber = unlock(PEM_Code::decode(str, label));
200 Format format = pem_label_to_dl_format(label);
201
202 m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);
203 }
204 catch(...) {}
205 }
206
207 if(m_data == nullptr)
208 throw Invalid_Argument("DL_Group: Unknown group " + str);
209 }
210
211namespace {
212
213/*
214* Create generator of the q-sized subgroup (DSA style generator)
215*/
216BigInt make_dsa_generator(const BigInt& p, const BigInt& q)
217 {
218 BigInt e, r;
219 vartime_divide(p - 1, q, e, r);
220
221 if(e == 0 || r > 0)
222 throw Invalid_Argument("make_dsa_generator q does not divide p-1");
223
224 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
225 {
226 // TODO precompute!
227 BigInt g = power_mod(PRIMES[i], e, p);
228 if(g > 1)
229 return g;
230 }
231
232 throw Internal_Error("DL_Group: Couldn't create a suitable generator");
233 }
234
235}
236
237/*
238* DL_Group Constructor
239*/
241 PrimeType type, size_t pbits, size_t qbits)
242 {
243 if(pbits < 1024)
244 throw Invalid_Argument("DL_Group: prime size " + std::to_string(pbits) + " is too small");
245
246 if(type == Strong)
247 {
248 if(qbits != 0 && qbits != pbits - 1)
249 throw Invalid_Argument("Cannot create strong-prime DL_Group with specified q bits");
250
251 const BigInt p = random_safe_prime(rng, pbits);
252 const BigInt q = (p - 1) / 2;
253
254 /*
255 Always choose a generator that is quadratic reside mod p,
256 this forces g to be a generator of the subgroup of size q.
257 */
258 BigInt g = 2;
259 if(jacobi(g, p) != 1)
260 {
261 // prime table does not contain 2
262 for(size_t i = 0; i < PRIME_TABLE_SIZE; ++i)
263 {
264 g = PRIMES[i];
265 if(jacobi(g, p) == 1)
266 break;
267 }
268 }
269
270 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
271 }
272 else if(type == Prime_Subgroup)
273 {
274 if(qbits == 0)
275 qbits = dl_exponent_size(pbits);
276
277 const BigInt q = random_prime(rng, qbits);
278 Modular_Reducer mod_2q(2*q);
279 BigInt X;
280 BigInt p;
281 while(p.bits() != pbits || !is_prime(p, rng, 128, true))
282 {
283 X.randomize(rng, pbits);
284 p = X - mod_2q.reduce(X) + 1;
285 }
286
287 const BigInt g = make_dsa_generator(p, q);
288 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
289 }
290 else if(type == DSA_Kosherizer)
291 {
292 if(qbits == 0)
293 qbits = ((pbits <= 1024) ? 160 : 256);
294
295 BigInt p, q;
296 generate_dsa_primes(rng, p, q, pbits, qbits);
297 const BigInt g = make_dsa_generator(p, q);
298 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
299 }
300 else
301 {
302 throw Invalid_Argument("DL_Group unknown PrimeType");
303 }
304 }
305
306/*
307* DL_Group Constructor
308*/
310 const std::vector<uint8_t>& seed,
311 size_t pbits, size_t qbits)
312 {
313 BigInt p, q;
314
315 if(!generate_dsa_primes(rng, p, q, pbits, qbits, seed))
316 throw Invalid_Argument("DL_Group: The seed given does not generate a DSA group");
317
318 BigInt g = make_dsa_generator(p, q);
319
320 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
321 }
322
323/*
324* DL_Group Constructor
325*/
327 {
328 m_data = std::make_shared<DL_Group_Data>(p, 0, g, DL_Group_Source::ExternalSource);
329 }
330
331/*
332* DL_Group Constructor
333*/
334DL_Group::DL_Group(const BigInt& p, const BigInt& q, const BigInt& g)
335 {
336 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::ExternalSource);
337 }
338
339const DL_Group_Data& DL_Group::data() const
340 {
341 if(m_data)
342 return *m_data;
343
344 throw Invalid_State("DL_Group uninitialized");
345 }
346
348 {
349 const BigInt& p = get_p();
350 const BigInt& q = get_q();
351
352 if(y <= 1 || y >= p)
353 return false;
354
355 if(q.is_zero() == false)
356 {
357 if(power_mod(y, q, p) != 1)
358 return false;
359 }
360
361 return true;
362 }
363
364bool DL_Group::verify_element_pair(const BigInt& y, const BigInt& x) const
365 {
366 const BigInt& p = get_p();
367
368 if(y <= 1 || y >= p || x <= 1 || x >= p)
369 return false;
370
371 if(y != power_g_p(x))
372 return false;
373
374 return true;
375 }
376
377/*
378* Verify the parameters
379*/
381 bool strong) const
382 {
383 const bool from_builtin = (source() == DL_Group_Source::Builtin);
384
385 if(!strong && from_builtin)
386 return true;
387
388 const BigInt& p = get_p();
389 const BigInt& q = get_q();
390 const BigInt& g = get_g();
391
392 if(g < 2 || p < 3 || q < 0)
393 return false;
394
395 const size_t test_prob = 128;
396 const bool is_randomly_generated = (source() != DL_Group_Source::ExternalSource);
397
398 if(q != 0)
399 {
400 if((p - 1) % q != 0)
401 {
402 return false;
403 }
404 if(this->power_g_p(q) != 1)
405 {
406 return false;
407 }
408 if(!is_prime(q, rng, test_prob, is_randomly_generated))
409 {
410 return false;
411 }
412 }
413
414 if(!is_prime(p, rng, test_prob, is_randomly_generated))
415 {
416 return false;
417 }
418
419 return true;
420 }
421
422/*
423* Return the prime
424*/
426 {
427 return data().p();
428 }
429
430/*
431* Return the generator
432*/
434 {
435 return data().g();
436 }
437
438/*
439* Return the subgroup
440*/
442 {
443 return data().q();
444 }
445
446std::shared_ptr<const Montgomery_Params> DL_Group::monty_params_p() const
447 {
448 return data().monty_params_p();
449 }
450
451size_t DL_Group::p_bits() const
452 {
453 return data().p_bits();
454 }
455
456size_t DL_Group::p_bytes() const
457 {
458 return data().p_bytes();
459 }
460
461size_t DL_Group::q_bits() const
462 {
463 data().assert_q_is_set("q_bits");
464 return data().q_bits();
465 }
466
467size_t DL_Group::q_bytes() const
468 {
469 data().assert_q_is_set("q_bytes");
470 return data().q_bytes();
471 }
472
474 {
475 return data().estimated_strength();
476 }
477
479 {
480 return data().exponent_bits();
481 }
482
484 {
485 // precompute??
486 return inverse_mod(x, get_p());
487 }
488
490 {
491 return data().mod_p(x);
492 }
493
495 {
496 return data().multiply_mod_p(x, y);
497 }
498
500 {
501 data().assert_q_is_set("inverse_mod_q");
502 // precompute??
503 return inverse_mod(x, get_q());
504 }
505
507 {
508 data().assert_q_is_set("mod_q");
509 return data().mod_q(x);
510 }
511
513 {
514 data().assert_q_is_set("multiply_mod_q");
515 return data().multiply_mod_q(x, y);
516 }
517
518BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const
519 {
520 data().assert_q_is_set("multiply_mod_q");
521 return data().multiply_mod_q(data().multiply_mod_q(x, y), z);
522 }
523
525 {
526 data().assert_q_is_set("square_mod_q");
527 return data().square_mod_q(x);
528 }
529
530BigInt DL_Group::multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const
531 {
532 return monty_multi_exp(data().monty_params_p(), get_g(), x, y, z);
533 }
534
536 {
537 return data().power_g_p(x, x.bits());
538 }
539
540BigInt DL_Group::power_g_p(const BigInt& x, size_t max_x_bits) const
541 {
542 return data().power_g_p(x, max_x_bits);
543 }
544
546 {
547 return data().source();
548 }
549
550/*
551* DER encode the parameters
552*/
553std::vector<uint8_t> DL_Group::DER_encode(Format format) const
554 {
555 if(get_q().is_zero() && (format == ANSI_X9_57 || format == ANSI_X9_42))
556 throw Encoding_Error("Cannot encode DL_Group in ANSI formats when q param is missing");
557
558 std::vector<uint8_t> output;
559 DER_Encoder der(output);
560
561 if(format == ANSI_X9_57)
562 {
564 .encode(get_p())
565 .encode(get_q())
566 .encode(get_g())
567 .end_cons();
568 }
569 else if(format == ANSI_X9_42)
570 {
572 .encode(get_p())
573 .encode(get_g())
574 .encode(get_q())
575 .end_cons();
576 }
577 else if(format == PKCS_3)
578 {
580 .encode(get_p())
581 .encode(get_g())
582 .end_cons();
583 }
584 else
585 throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
586
587 return output;
588 }
589
590/*
591* PEM encode the parameters
592*/
593std::string DL_Group::PEM_encode(Format format) const
594 {
595 const std::vector<uint8_t> encoding = DER_encode(format);
596
597 if(format == PKCS_3)
598 return PEM_Code::encode(encoding, "DH PARAMETERS");
599 else if(format == ANSI_X9_57)
600 return PEM_Code::encode(encoding, "DSA PARAMETERS");
601 else if(format == ANSI_X9_42)
602 return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS");
603 else
604 throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
605 }
606
607DL_Group::DL_Group(const uint8_t ber[], size_t ber_len, Format format)
608 {
609 m_data = BER_decode_DL_group(ber, ber_len, format, DL_Group_Source::ExternalSource);
610 }
611
612void DL_Group::BER_decode(const std::vector<uint8_t>& ber, Format format)
613 {
614 m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);
615 }
616
617//static
619 {
620 std::string label;
621 const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label));
622 Format format = pem_label_to_dl_format(label);
623 return DL_Group(ber, format);
624 }
625
626/*
627* Decode PEM encoded parameters
628*/
629void DL_Group::PEM_decode(const std::string& pem)
630 {
631 std::string label;
632 const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label));
633 Format format = pem_label_to_dl_format(label);
634
635 m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);
636 }
637
638//static
639std::string DL_Group::PEM_for_named_group(const std::string& name)
640 {
641 DL_Group group(name);
643 return group.PEM_encode(format);
644 }
645
646}
size_t bits() const
Definition: bigint.cpp:296
bool is_zero() const
Definition: bigint.h:421
DER_Encoder & start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: der_enc.cpp:181
DER_Encoder & end_cons()
Definition: der_enc.cpp:191
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:285
std::vector< uint8_t > DER_encode(Format format) const
Definition: dl_group.cpp:553
BigInt power_g_p(const BigInt &x) const
Definition: dl_group.cpp:535
BigInt mod_p(const BigInt &x) const
Definition: dl_group.cpp:489
static std::string PEM_for_named_group(const std::string &name)
Definition: dl_group.cpp:639
BigInt multiply_mod_p(const BigInt &x, const BigInt &y) const
Definition: dl_group.cpp:494
std::shared_ptr< const Montgomery_Params > monty_params_p() const
Definition: dl_group.cpp:446
size_t p_bits() const
Definition: dl_group.cpp:451
const BigInt & get_p() const
Definition: dl_group.cpp:425
BigInt multi_exponentiate(const BigInt &x, const BigInt &y, const BigInt &z) const
Definition: dl_group.cpp:530
bool verify_public_element(const BigInt &y) const
Definition: dl_group.cpp:347
BigInt square_mod_q(const BigInt &x) const
Definition: dl_group.cpp:524
static std::shared_ptr< DL_Group_Data > DL_group_info(const std::string &name)
Definition: dl_named.cpp:13
BigInt inverse_mod_q(const BigInt &x) const
Definition: dl_group.cpp:499
size_t p_bytes() const
Definition: dl_group.cpp:456
bool verify_element_pair(const BigInt &y, const BigInt &x) const
Definition: dl_group.cpp:364
size_t estimated_strength() const
Definition: dl_group.cpp:473
size_t q_bytes() const
Definition: dl_group.cpp:467
DL_Group_Source source() const
Definition: dl_group.cpp:545
BigInt multiply_mod_q(const BigInt &x, const BigInt &y) const
Definition: dl_group.cpp:512
BigInt inverse_mod_p(const BigInt &x) const
Definition: dl_group.cpp:483
size_t q_bits() const
Definition: dl_group.cpp:461
static DL_Group DL_Group_from_PEM(const std::string &pem)
Definition: dl_group.cpp:618
DL_Group()=default
void PEM_decode(const std::string &pem)
Definition: dl_group.cpp:629
size_t exponent_bits() const
Definition: dl_group.cpp:478
BigInt mod_q(const BigInt &x) const
Definition: dl_group.cpp:506
void BER_decode(const std::vector< uint8_t > &ber, Format format)
Definition: dl_group.cpp:612
bool verify_group(RandomNumberGenerator &rng, bool strong=true) const
Definition: dl_group.cpp:380
const BigInt & get_g() const
Definition: dl_group.cpp:433
const BigInt & get_q() const
Definition: dl_group.cpp:441
std::string PEM_encode(Format format) const
Definition: dl_group.cpp:593
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
std::string name
int(* final)(unsigned char *, CTX *)
fe X
Definition: ge.cpp:27
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:68
Definition: alg_id.cpp:13
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:151
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition: make_prm.cpp:77
size_t dl_work_factor(size_t bits)
Definition: workfactor.cpp:46
const uint16_t PRIMES[]
Definition: primes.cpp:12
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:287
DL_Group_Source
Definition: dl_group.h:18
BigInt monty_multi_exp(std::shared_ptr< const Montgomery_Params > params_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)
Definition: monty_exp.cpp:177
size_t dl_exponent_size(size_t bits)
Definition: workfactor.cpp:52
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
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:72
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(std::shared_ptr< const Montgomery_Params > params, const BigInt &g, size_t window_bits, bool const_time)
Definition: monty_exp.cpp:157
@ SEQUENCE
Definition: asn1_obj.h:42
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:159
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:268
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:250
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
Definition: monty_exp.cpp:165
Definition: bigint.h:1143
MechanismType type