/src/botan/src/lib/math/numbertheory/dsa_gen.cpp

Source (jump to first uncovered line)
/*
* DSA Parameter Generation
* (C) 1999-2007 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/primality.h>

#include <botan/hash.h>
#include <botan/numthry.h>
#include <botan/reducer.h>
#include <botan/rng.h>
#include <botan/internal/fmt.h>

namespace Botan {

namespace {

/*
* Check if this size is allowed by FIPS 186-3
*/
bool fips186_3_valid_size(size_t pbits, size_t qbits) {
   if(qbits == 160) {
      return (pbits == 1024);
   }

   if(qbits == 224) {
      return (pbits == 2048);
   }

   if(qbits == 256) {
      return (pbits == 2048 || pbits == 3072);
   }

   return false;
}

// qbits assumed to be a valid size for FIPS param gen
std::string hash_function_for(size_t qbits) {
   if(qbits == 160) {
      return "SHA-1";
   }

   return "SHA-" + std::to_string(qbits);
}

}  // namespace

/*
* Attempt DSA prime generation with given seed
*/
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) {
   if(!fips186_3_valid_size(pbits, qbits)) {
      throw Invalid_Argument(fmt("FIPS 186-3 does not allow DSA domain parameters of {}/{} bits long", pbits, qbits));
   }

   if(seed_c.size() * 8 < qbits) {
      throw Invalid_Argument(
         fmt("Generating a DSA parameter set with a {} bit long q requires a seed at least as many bits long", qbits));
   }

   const std::string hash_name = hash_function_for(qbits);
   auto hash = HashFunction::create_or_throw(hash_name);

   const size_t HASH_SIZE = hash->output_length();

   class Seed final {
      public:
         explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {}

         const std::vector<uint8_t>& value() const { return m_seed; }

         Seed& operator++() {
            for(size_t j = m_seed.size(); j > 0; --j) {
               if(++m_seed[j - 1]) {
                  break;
               }
            }
            return (*this);
         }

      private:
         std::vector<uint8_t> m_seed;
   };

   Seed seed(seed_c);

   q._assign_from_bytes(hash->process(seed.value()));
   q.set_bit(qbits - 1);
   q.set_bit(0);

   if(!is_prime(q, rng, 128, true)) {
      return false;
   }

   const size_t n = (pbits - 1) / (HASH_SIZE * 8), b = (pbits - 1) % (HASH_SIZE * 8);

   BigInt X;
   std::vector<uint8_t> V(HASH_SIZE * (n + 1));

   Modular_Reducer mod_2q(2 * q);

   for(size_t j = 0; j != 4 * pbits; ++j) {
      for(size_t k = 0; k <= n; ++k) {
         ++seed;
         hash->update(seed.value());
         hash->final(&V[HASH_SIZE * (n - k)]);
      }

      if(j >= offset) {
         X._assign_from_bytes(std::span{V}.subspan(HASH_SIZE - 1 - b / 8));
         X.set_bit(pbits - 1);

         p = X - (mod_2q.reduce(X) - 1);

         if(p.bits() == pbits && is_prime(p, rng, 128, true)) {
            return true;
         }
      }
   }
   return false;
}

/*
* Generate DSA Primes
*/
std::vector<uint8_t> generate_dsa_primes(RandomNumberGenerator& rng, BigInt& p, BigInt& q, size_t pbits, size_t qbits) {
   while(true) {
      std::vector<uint8_t> seed(qbits / 8);
      rng.randomize(seed.data(), seed.size());

      if(generate_dsa_primes(rng, p, q, pbits, qbits, seed)) {
         return seed;
      }
   }
}

}  // namespace Botan

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

Coverage Report

Created: 2024-11-29 06:10