Botan  1.10.9
dl_group.cpp
Go to the documentation of this file.
1 /*
2 * Discrete Logarithm Parameters
3 * (C) 1999-2008 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/dl_group.h>
9 #include <botan/libstate.h>
10 #include <botan/parsing.h>
11 #include <botan/numthry.h>
12 #include <botan/der_enc.h>
13 #include <botan/ber_dec.h>
14 #include <botan/pipe.h>
15 #include <botan/pem.h>
16 #include <botan/internal/workfactor.h>
17 #include <botan/internal/assert.h>
18 
19 namespace Botan {
20 
21 /*
22 * DL_Group Constructor
23 */
25  {
26  initialized = false;
27  }
28 
29 /*
30 * DL_Group Constructor
31 */
32 DL_Group::DL_Group(const std::string& type)
33  {
34  std::string grp_contents = global_state().get("dl", type);
35 
36  if(grp_contents == "")
37  throw Invalid_Argument("DL_Group: Unknown group " + type);
38 
39  DataSource_Memory pem(grp_contents);
40  PEM_decode(pem);
41  }
42 
43 /*
44 * DL_Group Constructor
45 */
47  PrimeType type, size_t pbits, size_t qbits)
48  {
49  if(pbits < 512)
50  throw Invalid_Argument("DL_Group: prime size " + to_string(pbits) +
51  " is too small");
52 
53  if(type == Strong)
54  {
55  p = random_safe_prime(rng, pbits);
56  q = (p - 1) / 2;
57  g = 2;
58  }
59  else if(type == Prime_Subgroup)
60  {
61  if(!qbits)
62  qbits = 2 * dl_work_factor(pbits);
63 
64  q = random_prime(rng, qbits);
65  BigInt X;
66  while(p.bits() != pbits || !check_prime(p, rng))
67  {
68  X.randomize(rng, pbits);
69  p = X - (X % (2*q) - 1);
70  }
71 
72  g = make_dsa_generator(p, q);
73  }
74  else if(type == DSA_Kosherizer)
75  {
76  qbits = qbits ? qbits : ((pbits <= 1024) ? 160 : 256);
77 
79  global_state().algorithm_factory(),
80  p, q,
81  pbits, qbits);
82 
83  g = make_dsa_generator(p, q);
84  }
85 
86  initialized = true;
87  }
88 
89 /*
90 * DL_Group Constructor
91 */
93  const MemoryRegion<byte>& seed, size_t pbits, size_t qbits)
94  {
95  if(!generate_dsa_primes(rng,
96  global_state().algorithm_factory(),
97  p, q, pbits, qbits, seed))
98  throw Invalid_Argument("DL_Group: The seed given does not "
99  "generate a DSA group");
100 
101  g = make_dsa_generator(p, q);
102 
103  initialized = true;
104  }
105 
106 /*
107 * DL_Group Constructor
108 */
109 DL_Group::DL_Group(const BigInt& p1, const BigInt& g1)
110  {
111  initialize(p1, 0, g1);
112  }
113 
114 /*
115 * DL_Group Constructor
116 */
117 DL_Group::DL_Group(const BigInt& p1, const BigInt& q1, const BigInt& g1)
118  {
119  initialize(p1, q1, g1);
120  }
121 
122 /*
123 * DL_Group Initializer
124 */
125 void DL_Group::initialize(const BigInt& p1, const BigInt& q1, const BigInt& g1)
126  {
127  if(p1 < 3)
128  throw Invalid_Argument("DL_Group: Prime invalid");
129  if(g1 < 2 || g1 >= p1)
130  throw Invalid_Argument("DL_Group: Generator invalid");
131  if(q1 < 0 || q1 >= p1)
132  throw Invalid_Argument("DL_Group: Subgroup invalid");
133 
134  p = p1;
135  g = g1;
136  q = q1;
137 
138  initialized = true;
139  }
140 
141 /*
142 * Verify that the group has been set
143 */
144 void DL_Group::init_check() const
145  {
146  if(!initialized)
147  throw Invalid_State("DLP group cannot be used uninitialized");
148  }
149 
150 /*
151 * Verify the parameters
152 */
154  bool strong) const
155  {
156  init_check();
157 
158  if(g < 2 || p < 3 || q < 0)
159  return false;
160  if((q != 0) && ((p - 1) % q != 0))
161  return false;
162 
163  if(!strong)
164  return true;
165 
166  if(!check_prime(p, rng))
167  return false;
168  if((q > 0) && !check_prime(q, rng))
169  return false;
170  return true;
171  }
172 
173 /*
174 * Return the prime
175 */
176 const BigInt& DL_Group::get_p() const
177  {
178  init_check();
179  return p;
180  }
181 
182 /*
183 * Return the generator
184 */
185 const BigInt& DL_Group::get_g() const
186  {
187  init_check();
188  return g;
189  }
190 
191 /*
192 * Return the subgroup
193 */
194 const BigInt& DL_Group::get_q() const
195  {
196  init_check();
197  if(q == 0)
198  throw Invalid_State("DLP group has no q prime specified");
199  return q;
200  }
201 
202 /*
203 * DER encode the parameters
204 */
206  {
207  init_check();
208 
209  if((q == 0) && (format != PKCS_3))
210  throw Encoding_Error("The ANSI DL parameter formats require a subgroup");
211 
212  if(format == ANSI_X9_57)
213  {
214  return DER_Encoder()
216  .encode(p)
217  .encode(q)
218  .encode(g)
219  .end_cons()
220  .get_contents();
221  }
222  else if(format == ANSI_X9_42)
223  {
224  return DER_Encoder()
226  .encode(p)
227  .encode(g)
228  .encode(q)
229  .end_cons()
230  .get_contents();
231  }
232  else if(format == PKCS_3)
233  {
234  return DER_Encoder()
236  .encode(p)
237  .encode(g)
238  .end_cons()
239  .get_contents();
240  }
241 
242  throw Invalid_Argument("Unknown DL_Group encoding " + to_string(format));
243  }
244 
245 /*
246 * PEM encode the parameters
247 */
248 std::string DL_Group::PEM_encode(Format format) const
249  {
250  SecureVector<byte> encoding = DER_encode(format);
251  if(format == PKCS_3)
252  return PEM_Code::encode(encoding, "DH PARAMETERS");
253  else if(format == ANSI_X9_57)
254  return PEM_Code::encode(encoding, "DSA PARAMETERS");
255  else if(format == ANSI_X9_42)
256  return PEM_Code::encode(encoding, "X942 DH PARAMETERS");
257  else
258  throw Invalid_Argument("Unknown DL_Group encoding " + to_string(format));
259  }
260 
261 /*
262 * Decode BER encoded parameters
263 */
265  {
266  BigInt new_p, new_q, new_g;
267 
268  BER_Decoder decoder(source);
269  BER_Decoder ber = decoder.start_cons(SEQUENCE);
270 
271  if(format == ANSI_X9_57)
272  {
273  ber.decode(new_p)
274  .decode(new_q)
275  .decode(new_g)
276  .verify_end();
277  }
278  else if(format == ANSI_X9_42)
279  {
280  ber.decode(new_p)
281  .decode(new_g)
282  .decode(new_q)
284  }
285  else if(format == PKCS_3)
286  {
287  ber.decode(new_p)
288  .decode(new_g)
290  }
291  else
292  throw Invalid_Argument("Unknown DL_Group encoding " + to_string(format));
293 
294  initialize(new_p, new_q, new_g);
295  }
296 
297 /*
298 * Decode PEM encoded parameters
299 */
301  {
302  std::string label;
303  DataSource_Memory ber(PEM_Code::decode(source, label));
304 
305  if(label == "DH PARAMETERS")
306  BER_decode(ber, PKCS_3);
307  else if(label == "DSA PARAMETERS")
308  BER_decode(ber, ANSI_X9_57);
309  else if(label == "X942 DH PARAMETERS")
310  BER_decode(ber, ANSI_X9_42);
311  else
312  throw Decoding_Error("DL_Group: Invalid PEM label " + label);
313  }
314 
315 /*
316 * Create generator of the q-sized subgroup (DSA style generator)
317 */
318 BigInt DL_Group::make_dsa_generator(const BigInt& p, const BigInt& q)
319  {
320  BigInt g, e = (p - 1) / q;
321 
322  BOTAN_ASSERT(e > 0, "q does not divide p, invalid group");
323 
324  for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
325  {
326  g = power_mod(PRIMES[i], e, p);
327  if(g > 1)
328  return g;
329  }
330 
331  throw Internal_Error("DL_Group: Couldn't create a suitable generator");
332  }
333 
334 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:220
SecureVector< byte > get_contents()
Definition: der_enc.cpp:122
std::string PEM_encode(Format format) const
Definition: dl_group.cpp:248
BER_Decoder & decode(bool &)
Definition: ber_dec.cpp:338
void PEM_decode(DataSource &src)
Definition: dl_group.cpp:300
bool verify_group(RandomNumberGenerator &rng, bool strong) const
Definition: dl_group.cpp:153
const BigInt & get_q() const
Definition: dl_group.cpp:194
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
const BigInt & get_p() const
Definition: dl_group.cpp:176
void BER_decode(DataSource &src, Format format)
Definition: dl_group.cpp:264
DER_Encoder & end_cons()
Definition: der_enc.cpp:145
BER_Decoder start_cons(ASN1_Tag, ASN1_Tag=UNIVERSAL)
Definition: ber_dec.cpp:232
#define BOTAN_ASSERT(expr, msg)
Definition: assert.h:19
SecureVector< byte > decode(DataSource &source, std::string &label)
Definition: pem.cpp:56
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:209
size_t bits() const
Definition: bigint.cpp:253
RandomNumberGenerator * rng
Definition: global_rng.cpp:165
void randomize(RandomNumberGenerator &rng, size_t bitsize=0)
Definition: big_rand.cpp:29
const BigInt & get_g() const
Definition: dl_group.cpp:185
Library_State & global_state()
SecureVector< byte > DER_encode(Format format) const
Definition: dl_group.cpp:205
BER_Decoder & discard_remaining()
Definition: ber_dec.cpp:182
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:87
std::string encode(const byte der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:19
BER_Decoder & verify_end()
Definition: ber_dec.cpp:160
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:251
DER_Encoder & start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: der_enc.cpp:135
std::string to_string(u64bit n, size_t min_len)
Definition: parsing.cpp:42
size_t dl_work_factor(size_t bits)
Definition: workfactor.cpp:14
const u16bit BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
bool generate_dsa_primes(RandomNumberGenerator &rng, Algorithm_Factory &af, BigInt &p, BigInt &q, size_t pbits, size_t qbits, const MemoryRegion< byte > &seed_c)
Definition: dsa_gen.cpp:41
std::string get(const std::string &section, const std::string &key) const
Definition: libstate.cpp:114
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
bool check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:143