Botan  2.4.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 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/der_enc.h>
11 #include <botan/ber_dec.h>
12 #include <botan/pem.h>
13 #include <botan/workfactor.h>
14 
15 namespace Botan {
16 
17 /*
18 * DL_Group Constructor
19 */
21  {
22  m_initialized = false;
23  }
24 
25 /*
26 * DL_Group Constructor
27 */
28 DL_Group::DL_Group(const std::string& name)
29  {
30  const std::string pem = PEM_for_named_group(name);
31 
32  if(pem == "")
33  throw Invalid_Argument("DL_Group: Unknown group " + name);
34 
35  PEM_decode(pem);
36  }
37 
38 /*
39 * DL_Group Constructor
40 */
42  PrimeType type, size_t pbits, size_t qbits)
43  {
44  if(pbits < 1024)
45  throw Invalid_Argument("DL_Group: prime size " + std::to_string(pbits) +
46  " is too small");
47 
48  if(type == Strong)
49  {
50  m_p = random_safe_prime(rng, pbits);
51  m_q = (m_p - 1) / 2;
52  m_g = 2;
53 
54  /*
55  Always choose a generator that is quadratic reside mod p,
56  this forces g to be a generator of the subgroup of size q.
57  */
58  if(jacobi(m_g, m_p) != 1)
59  {
60  // prime table does not contain 2
61  for(size_t i = 0; i < PRIME_TABLE_SIZE; ++i)
62  {
63  m_g = PRIMES[i];
64  if(jacobi(m_g, m_p) == 1)
65  break;
66  }
67  }
68  }
69  else if(type == Prime_Subgroup)
70  {
71  if(!qbits)
72  qbits = dl_exponent_size(pbits);
73 
74  m_q = random_prime(rng, qbits);
75  BigInt X;
76  while(m_p.bits() != pbits || !is_prime(m_p, rng))
77  {
78  X.randomize(rng, pbits);
79  m_p = X - (X % (2*m_q) - 1);
80  }
81 
82  m_g = make_dsa_generator(m_p, m_q);
83  }
84  else if(type == DSA_Kosherizer)
85  {
86  qbits = qbits ? qbits : ((pbits <= 1024) ? 160 : 256);
87 
88  generate_dsa_primes(rng, m_p, m_q, pbits, qbits);
89 
90  m_g = make_dsa_generator(m_p, m_q);
91  }
92 
93  m_initialized = true;
94  }
95 
96 /*
97 * DL_Group Constructor
98 */
100  const std::vector<uint8_t>& seed,
101  size_t pbits, size_t qbits)
102  {
103  if(!generate_dsa_primes(rng, m_p, m_q, pbits, qbits, seed))
104  throw Invalid_Argument("DL_Group: The seed given does not "
105  "generate a DSA group");
106 
107  m_g = make_dsa_generator(m_p, m_q);
108 
109  m_initialized = true;
110  }
111 
112 /*
113 * DL_Group Constructor
114 */
115 DL_Group::DL_Group(const BigInt& p1, const BigInt& g1)
116  {
117  initialize(p1, 0, g1);
118  }
119 
120 /*
121 * DL_Group Constructor
122 */
123 DL_Group::DL_Group(const BigInt& p1, const BigInt& q1, const BigInt& g1)
124  {
125  initialize(p1, q1, g1);
126  }
127 
128 /*
129 * DL_Group Initializer
130 */
131 void DL_Group::initialize(const BigInt& p1, const BigInt& q1, const BigInt& g1)
132  {
133  if(p1 < 3)
134  throw Invalid_Argument("DL_Group: Prime invalid");
135  if(g1 < 2 || g1 >= p1)
136  throw Invalid_Argument("DL_Group: Generator invalid");
137  if(q1 < 0 || q1 >= p1)
138  throw Invalid_Argument("DL_Group: Subgroup invalid");
139 
140  m_p = p1;
141  m_g = g1;
142  m_q = q1;
143 
144  m_initialized = true;
145  }
146 
147 /*
148 * Verify that the group has been set
149 */
150 void DL_Group::init_check() const
151  {
152  if(!m_initialized)
153  throw Invalid_State("DLP group cannot be used uninitialized");
154  }
155 
156 /*
157 * Verify the parameters
158 */
160  bool strong) const
161  {
162  init_check();
163 
164  if(m_g < 2 || m_p < 3 || m_q < 0)
165  return false;
166 
167  const size_t prob = (strong) ? 128 : 10;
168 
169  if(m_q != 0)
170  {
171  if((m_p - 1) % m_q != 0)
172  {
173  return false;
174  }
175  if(power_mod(m_g, m_q, m_p) != 1)
176  {
177  return false;
178  }
179  if(!is_prime(m_q, rng, prob))
180  {
181  return false;
182  }
183  }
184  if(!is_prime(m_p, rng, prob))
185  {
186  return false;
187  }
188  return true;
189  }
190 
191 /*
192 * Return the prime
193 */
194 const BigInt& DL_Group::get_p() const
195  {
196  init_check();
197  return m_p;
198  }
199 
200 /*
201 * Return the generator
202 */
203 const BigInt& DL_Group::get_g() const
204  {
205  init_check();
206  return m_g;
207  }
208 
209 /*
210 * Return the subgroup
211 */
212 const BigInt& DL_Group::get_q() const
213  {
214  init_check();
215  if(m_q == 0)
216  throw Invalid_State("DLP group has no q prime specified");
217  return m_q;
218  }
219 
220 /*
221 * DER encode the parameters
222 */
223 std::vector<uint8_t> DL_Group::DER_encode(Format format) const
224  {
225  init_check();
226 
227  if((m_q == 0) && (format != PKCS_3))
228  throw Encoding_Error("The ANSI DL parameter formats require a subgroup");
229 
230  if(format == ANSI_X9_57)
231  {
232  return DER_Encoder()
234  .encode(m_p)
235  .encode(m_q)
236  .encode(m_g)
237  .end_cons()
239  }
240  else if(format == ANSI_X9_42)
241  {
242  return DER_Encoder()
244  .encode(m_p)
245  .encode(m_g)
246  .encode(m_q)
247  .end_cons()
249  }
250  else if(format == PKCS_3)
251  {
252  return DER_Encoder()
254  .encode(m_p)
255  .encode(m_g)
256  .end_cons()
258  }
259 
260  throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
261  }
262 
263 /*
264 * PEM encode the parameters
265 */
266 std::string DL_Group::PEM_encode(Format format) const
267  {
268  const std::vector<uint8_t> encoding = DER_encode(format);
269 
270  if(format == PKCS_3)
271  return PEM_Code::encode(encoding, "DH PARAMETERS");
272  else if(format == ANSI_X9_57)
273  return PEM_Code::encode(encoding, "DSA PARAMETERS");
274  else if(format == ANSI_X9_42)
275  return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS");
276  else
277  throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
278  }
279 
280 /*
281 * Decode BER encoded parameters
282 */
283 void DL_Group::BER_decode(const std::vector<uint8_t>& data,
284  Format format)
285  {
286  BigInt new_p, new_q, new_g;
287 
288  BER_Decoder decoder(data);
289  BER_Decoder ber = decoder.start_cons(SEQUENCE);
290 
291  if(format == ANSI_X9_57)
292  {
293  ber.decode(new_p)
294  .decode(new_q)
295  .decode(new_g)
296  .verify_end();
297  }
298  else if(format == ANSI_X9_42)
299  {
300  ber.decode(new_p)
301  .decode(new_g)
302  .decode(new_q)
304  }
305  else if(format == PKCS_3)
306  {
307  ber.decode(new_p)
308  .decode(new_g)
310  }
311  else
312  throw Invalid_Argument("Unknown DL_Group encoding " + std::to_string(format));
313 
314  initialize(new_p, new_q, new_g);
315  }
316 
317 /*
318 * Decode PEM encoded parameters
319 */
320 void DL_Group::PEM_decode(const std::string& pem)
321  {
322  std::string label;
323 
324  auto ber = unlock(PEM_Code::decode(pem, label));
325 
326  if(label == "DH PARAMETERS")
327  BER_decode(ber, PKCS_3);
328  else if(label == "DSA PARAMETERS")
329  BER_decode(ber, ANSI_X9_57);
330  else if(label == "X942 DH PARAMETERS" || label == "X9.42 DH PARAMETERS")
331  BER_decode(ber, ANSI_X9_42);
332  else
333  throw Decoding_Error("DL_Group: Invalid PEM label " + label);
334  }
335 
336 /*
337 * Create generator of the q-sized subgroup (DSA style generator)
338 */
339 BigInt DL_Group::make_dsa_generator(const BigInt& p, const BigInt& q)
340  {
341  const BigInt e = (p - 1) / q;
342 
343  if(e == 0 || (p - 1) % q > 0)
344  throw Invalid_Argument("make_dsa_generator q does not divide p-1");
345 
346  for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
347  {
348  BigInt g = power_mod(PRIMES[i], e, p);
349  if(g > 1)
350  return g;
351  }
352 
353  throw Internal_Error("DL_Group: Couldn't create a suitable generator");
354  }
355 
356 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
fe X
Definition: ge.cpp:27
const uint16_t PRIMES[]
Definition: primes.cpp:12
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:374
size_t bits() const
Definition: bigint.cpp:183
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
const BigInt & get_g() const
Definition: dl_group.cpp:203
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:455
BER_Decoder & decode(bool &v)
Definition: ber_dec.cpp:355
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:108
MechanismType type
DER_Encoder & end_cons()
Definition: der_enc.cpp:146
void PEM_decode(const std::string &pem)
Definition: dl_group.cpp:320
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
bool verify_group(RandomNumberGenerator &rng, bool strong) const
Definition: dl_group.cpp:159
const BigInt & get_p() const
Definition: dl_group.cpp:194
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:114
std::vector< uint8_t > DER_encode(Format format) const
Definition: dl_group.cpp:223
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:68
BER_Decoder start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: ber_dec.cpp:251
BER_Decoder & discard_remaining()
Definition: ber_dec.cpp:186
Definition: alg_id.cpp:13
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:95
BER_Decoder & verify_end()
Definition: ber_dec.cpp:176
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:40
void BER_decode(const std::vector< uint8_t > &ber, Format format)
Definition: dl_group.cpp:283
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_named.cpp:12
std::string PEM_encode(Format format) const
Definition: dl_group.cpp:266
const BigInt & get_q() const
Definition: dl_group.cpp:212