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