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