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