Coverage Report

Created: 2022-06-23 06:44

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