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