Coverage Report

Created: 2020-06-30 13:58

/src/botan/src/lib/math/numbertheory/dsa_gen.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
* DSA Parameter Generation
3
* (C) 1999-2007 Jack Lloyd
4
*
5
* Botan is released under the Simplified BSD License (see license.txt)
6
*/
7
8
#include <botan/numthry.h>
9
#include <botan/hash.h>
10
#include <botan/reducer.h>
11
#include <botan/rng.h>
12
13
namespace Botan {
14
15
namespace {
16
17
/*
18
* Check if this size is allowed by FIPS 186-3
19
*/
20
bool fips186_3_valid_size(size_t pbits, size_t qbits)
21
0
   {
22
0
   if(qbits == 160)
23
0
      return (pbits == 1024);
24
0
25
0
   if(qbits == 224)
26
0
      return (pbits == 2048);
27
0
28
0
   if(qbits == 256)
29
0
      return (pbits == 2048 || pbits == 3072);
30
0
31
0
   return false;
32
0
   }
33
34
}
35
36
/*
37
* Attempt DSA prime generation with given seed
38
*/
39
bool generate_dsa_primes(RandomNumberGenerator& rng,
40
                         BigInt& p, BigInt& q,
41
                         size_t pbits, size_t qbits,
42
                         const std::vector<uint8_t>& seed_c,
43
                         size_t offset)
44
0
   {
45
0
   if(!fips186_3_valid_size(pbits, qbits))
46
0
      throw Invalid_Argument(
47
0
         "FIPS 186-3 does not allow DSA domain parameters of " +
48
0
         std::to_string(pbits) + "/" + std::to_string(qbits) + " bits long");
49
0
50
0
   if(seed_c.size() * 8 < qbits)
51
0
      throw Invalid_Argument(
52
0
         "Generating a DSA parameter set with a " + std::to_string(qbits) +
53
0
         " bit long q requires a seed at least as many bits long");
54
0
55
0
   const std::string hash_name = "SHA-" + std::to_string(qbits);
56
0
   std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw(hash_name));
57
0
58
0
   const size_t HASH_SIZE = hash->output_length();
59
0
60
0
   class Seed final
61
0
      {
62
0
      public:
63
0
         explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {}
64
0
65
0
         const std::vector<uint8_t>& value() const { return m_seed; }
66
0
67
0
         Seed& operator++()
68
0
            {
69
0
            for(size_t j = m_seed.size(); j > 0; --j)
70
0
               if(++m_seed[j-1])
71
0
                  break;
72
0
            return (*this);
73
0
            }
74
0
      private:
75
0
         std::vector<uint8_t> m_seed;
76
0
      };
77
0
78
0
   Seed seed(seed_c);
79
0
80
0
   q.binary_decode(hash->process(seed.value()));
81
0
   q.set_bit(qbits-1);
82
0
   q.set_bit(0);
83
0
84
0
   if(!is_prime(q, rng, 128, true))
85
0
      return false;
86
0
87
0
   const size_t n = (pbits-1) / (HASH_SIZE * 8),
88
0
                b = (pbits-1) % (HASH_SIZE * 8);
89
0
90
0
   BigInt X;
91
0
   std::vector<uint8_t> V(HASH_SIZE * (n+1));
92
0
93
0
   Modular_Reducer mod_2q(2*q);
94
0
95
0
   for(size_t j = 0; j != 4*pbits; ++j)
96
0
      {
97
0
      for(size_t k = 0; k <= n; ++k)
98
0
         {
99
0
         ++seed;
100
0
         hash->update(seed.value());
101
0
         hash->final(&V[HASH_SIZE * (n-k)]);
102
0
         }
103
0
104
0
      if(j >= offset)
105
0
         {
106
0
         X.binary_decode(&V[HASH_SIZE - 1 - b/8],
107
0
                         V.size() - (HASH_SIZE - 1 - b/8));
108
0
         X.set_bit(pbits-1);
109
0
110
0
         p = X - (mod_2q.reduce(X) - 1);
111
0
112
0
         if(p.bits() == pbits && is_prime(p, rng, 128, true))
113
0
            return true;
114
0
         }
115
0
      }
116
0
   return false;
117
0
   }
118
119
/*
120
* Generate DSA Primes
121
*/
122
std::vector<uint8_t> generate_dsa_primes(RandomNumberGenerator& rng,
123
                                      BigInt& p, BigInt& q,
124
                                      size_t pbits, size_t qbits)
125
0
   {
126
0
   while(true)
127
0
      {
128
0
      std::vector<uint8_t> seed(qbits / 8);
129
0
      rng.randomize(seed.data(), seed.size());
130
0
131
0
      if(generate_dsa_primes(rng, p, q, pbits, qbits, seed))
132
0
         return seed;
133
0
      }
134
0
   }
135
136
}