← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/lib/math/numbertheory/dsa_gen.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

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