Botan 3.8.1
Crypto and TLS for C&
dl_group.h
Go to the documentation of this file.
1/*
2* Discrete Logarithm Group
3* (C) 1999-2008,2018 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#ifndef BOTAN_DL_PARAM_H_
9#define BOTAN_DL_PARAM_H_
10
11#include <botan/bigint.h>
12#include <memory>
13#include <string_view>
14
15namespace Botan {
16
19class DL_Group_Data;
20
26
27/**
28* The DL group encoding format variants.
29*/
40
41/**
42* This class represents discrete logarithm groups. It holds a prime
43* modulus p, a generator g, and (optionally) a prime q which is a
44* factor of (p-1). In most cases g generates the order-q subgroup.
45*/
46class BOTAN_PUBLIC_API(2, 0) DL_Group final {
47 public:
48 /**
49 * Determine the prime creation for DL groups.
50 */
52
54
55 /**
56 * Construct a DL group with uninitialized internal value.
57 */
58 BOTAN_DEPRECATED("Deprecated no replacement") DL_Group() = default;
59
60 /**
61 * Construct a DL group that is registered in the configuration.
62 * @param name the name of the group, for example "modp/ietf/3072"
63 *
64 * @warning This constructor also accepts PEM inputs. This behavior is
65 * deprecated and will be removed in a future major release. Instead
66 * use DL_Group::from_PEM or DL_Group::from_name
67 */
68 BOTAN_DEPRECATED("Use DL_Group::from_name or DL_Group::from_PEM") explicit DL_Group(std::string_view name);
69
70 /**
71 * Construct a DL group that is registered in the configuration.
72 * @param name the name of the group, for example "modp/ietf/3072"
73 * @throws Invalid_Argument if the named group is unknown
74 */
75 static DL_Group from_name(std::string_view name);
76
77 /*
78 * Read a PEM representation
79 */
80 static DL_Group from_PEM(std::string_view pem);
81
82 /*
83 * Read a PEM representation
84 */
85 BOTAN_DEPRECATED("Use from_PEM") static DL_Group DL_Group_from_PEM(std::string_view pem) {
86 return DL_Group::from_PEM(pem);
87 }
88
89 /**
90 * Create a new group randomly.
91 * @param rng the random number generator to use
92 * @param type specifies how the creation of primes p and q shall
93 * be performed. If type=Strong, then p will be determined as a
94 * safe prime, and q will be chosen as (p-1)/2. If
95 * type=Prime_Subgroup and qbits = 0, then the size of q will be
96 * determined according to the estimated difficulty of the DL
97 * problem. If type=DSA_Kosherizer, DSA primes will be created.
98 * @param pbits the number of bits of p
99 * @param qbits the number of bits of q. Leave it as 0 to have
100 * the value determined according to pbits.
101 */
102 DL_Group(RandomNumberGenerator& rng, PrimeType type, size_t pbits, size_t qbits = 0);
103
104 /**
105 * Create a DSA group with a given seed.
106 * @param rng the random number generator to use
107 * @param seed the seed to use to create the random primes
108 * @param pbits the desired bit size of the prime p
109 * @param qbits the desired bit size of the prime q.
110 */
111 DL_Group(RandomNumberGenerator& rng, const std::vector<uint8_t>& seed, size_t pbits = 1024, size_t qbits = 0);
112
113 /**
114 * Create a DL group.
115 * @param p the prime p
116 * @param g the base g
117 */
118 DL_Group(const BigInt& p, const BigInt& g);
119
120 /**
121 * Create a DL group.
122 * @param p the prime p
123 * @param q the prime q
124 * @param g the base g
125 */
126 DL_Group(const BigInt& p, const BigInt& q, const BigInt& g);
127
128 /**
129 * Decode a BER-encoded DL group param
130 */
131 DL_Group(const uint8_t ber[], size_t ber_len, DL_Group_Format format);
132
133 /**
134 * Decode a BER-encoded DL group param
135 */
136 template <typename Alloc>
137 DL_Group(const std::vector<uint8_t, Alloc>& ber, DL_Group_Format format) :
138 DL_Group(ber.data(), ber.size(), format) {}
139
140 /**
141 * Get the prime p.
142 * @return prime p
143 */
144 const BigInt& get_p() const;
145
146 /**
147 * Get the prime q, returns zero if q is not used
148 * @return prime q
149 */
150 const BigInt& get_q() const;
151
152 /**
153 * Get the base g.
154 * @return base g
155 */
156 const BigInt& get_g() const;
157
158 /**
159 * Perform validity checks on the group.
160 * @param rng the rng to use
161 * @param strong whether to perform stronger by lengthier tests
162 * @return true if the object is consistent, false otherwise
163 */
164 bool verify_group(RandomNumberGenerator& rng, bool strong = true) const;
165
166 /**
167 * Verify a public element, ie check if y = g^x for some x.
168 *
169 * This is not a perfect test. It verifies that 1 < y < p and (if q is set)
170 * that y is in the subgroup of size q.
171 */
172 bool verify_public_element(const BigInt& y) const;
173
174 /**
175 * Verify a private element
176 *
177 * Specifically this checks that x is > 1 and < p, and additionally if
178 * q is set then x must be < q
179 */
180 bool verify_private_element(const BigInt& x) const;
181
182 /**
183 * Verify a pair of elements y = g^x
184 *
185 * This verifies that 1 < x,y < p and that y=g^x mod p
186 */
187 BOTAN_DEPRECATED("Deprecated no replacement") bool verify_element_pair(const BigInt& y, const BigInt& x) const;
188
189 /**
190 * Encode this group into a string using PEM encoding.
191 * @param format the encoding format
192 * @return string holding the PEM encoded group
193 */
194 std::string PEM_encode(DL_Group_Format format) const;
195
196 /**
197 * Encode this group into a string using DER encoding.
198 * @param format the encoding format
199 * @return string holding the DER encoded group
200 */
201 std::vector<uint8_t> DER_encode(DL_Group_Format format) const;
202
203 /**
204 * Reduce an integer modulo p
205 * @return x % p
206 */
207 BigInt mod_p(const BigInt& x) const;
208
209 /**
210 * Multiply and reduce an integer modulo p
211 * @return (x*y) % p
212 */
213 BigInt multiply_mod_p(const BigInt& x, const BigInt& y) const;
214
215 /**
216 * Return the inverse of x mod p
217 */
218 BigInt inverse_mod_p(const BigInt& x) const;
219
220 /**
221 * Reduce an integer modulo q
222 * Throws if q is unset on this DL_Group
223 * @return x % q
224 */
225 BigInt mod_q(const BigInt& x) const;
226
227 /**
228 * Multiply and reduce an integer modulo q
229 * Throws if q is unset on this DL_Group
230 * @return (x*y) % q
231 */
232 BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const;
233
234 /**
235 * Multiply and reduce an integer modulo q
236 * Throws if q is unset on this DL_Group
237 * @return (x*y*z) % q
238 */
239 BigInt multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const;
240
241 /**
242 * Square and reduce an integer modulo q
243 * Throws if q is unset on this DL_Group
244 * @return (x*x) % q
245 */
246 BigInt square_mod_q(const BigInt& x) const;
247
248 /**
249 * Return the inverse of x mod q
250 * Throws if q is unset on this DL_Group
251 */
252 BigInt inverse_mod_q(const BigInt& x) const;
253
254 /**
255 * Modular exponentiation
256 *
257 * @warning this function leaks the size of x via the number of
258 * loop iterations. Use the version taking the maximum size to
259 * avoid this.
260 *
261 * @return (g^x) % p
262 */
263 BOTAN_DEPRECATED("Use version taking bitlength upper bound") inline BigInt power_g_p(const BigInt& x) const {
264 return power_g_p(x, x.bits());
265 }
266
267 /**
268 * Modular exponentiation
269 * @param x the exponent
270 * @param max_x_bits x is assumed to be at most this many bits long.
271 *
272 * @return (g^x) % p
273 */
274 BigInt power_g_p(const BigInt& x, size_t max_x_bits) const;
275
276 /**
277 * Modular exponentiation
278 * @param b the base
279 * @param x the exponent
280 * @param max_x_bits x is assumed to be at most this many bits long.
281 *
282 * @return (b^x) % p
283 */
284 BigInt power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const;
285
286 /**
287 * Modular exponentiation
288 * @param b the base
289 * @param x the exponent
290 *
291 * @return (b^x) % p
292 */
293 BigInt power_b_p(const BigInt& b, const BigInt& x) const;
294
295 /**
296 * Multi-exponentiate
297 * Return (g^x * y^z) % p
298 */
299 BigInt multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const;
300
301 /**
302 * Return parameters for Montgomery reduction/exponentiation mod p
303 */
304 std::shared_ptr<const Montgomery_Params> monty_params_p() const;
305
306 /**
307 * Return the size of p in bits
308 * Same as get_p().bits()
309 */
310 size_t p_bits() const;
311
312 /**
313 * Return the size of p in bytes
314 * Same as get_p().bytes()
315 */
316 size_t p_bytes() const;
317
318 /**
319 * Return the size of q in bits
320 * Same as get_q().bits()
321 * Throws if q is unset
322 */
323 size_t q_bits() const;
324
325 /**
326 * Return the size of q in bytes
327 * Same as get_q().bytes()
328 * Throws if q is unset
329 */
330 size_t q_bytes() const;
331
332 /**
333 * Return if the q value is set
334 */
335 bool has_q() const;
336
337 /**
338 * Return size in bits of a secret exponent
339 *
340 * This attempts to balance between the attack costs of NFS
341 * (which depends on the size of the modulus) and Pollard's rho
342 * (which depends on the size of the exponent).
343 *
344 * It may vary over time for a particular group, if the attack
345 * costs change.
346 */
347 size_t exponent_bits() const;
348
349 /**
350 * Return an estimate of the strength of this group against
351 * discrete logarithm attacks (eg NFS). Warning: since this only
352 * takes into account known attacks it is by necessity an
353 * overestimate of the actual strength.
354 */
355 size_t estimated_strength() const;
356
357 /**
358 * Decode a DER/BER encoded group into this instance.
359 * @param ber a vector containing the DER/BER encoded group
360 * @param format the format of the encoded group
361 *
362 * @warning avoid this. Instead use the DL_Group constructor
363 */
364 BOTAN_DEPRECATED("Use DL_Group constructor taking BER encoding")
365 void BER_decode(const std::vector<uint8_t>& ber, DL_Group_Format format) {
366 *this = DL_Group(ber, format);
367 }
368
369 DL_Group_Source source() const;
370
371 /*
372 * For internal use only
373 * TODO(Botan4) Underscore prefix this
374 */
375 static std::shared_ptr<DL_Group_Data> DL_group_info(std::string_view name);
376
377 /*
378 * For internal use only
379 */
380 const Barrett_Reduction& _reducer_mod_p() const;
381
382 private:
383 DL_Group(std::shared_ptr<DL_Group_Data> data) : m_data(std::move(data)) {}
384
385 static std::shared_ptr<DL_Group_Data> load_DL_group_info(const char* p_str, const char* q_str, const char* g_str);
386
387 static std::shared_ptr<DL_Group_Data> load_DL_group_info(const char* p_str, const char* g_str);
388
389 static std::shared_ptr<DL_Group_Data> BER_decode_DL_group(const uint8_t data[],
390 size_t data_len,
391 DL_Group_Format format,
392 DL_Group_Source source);
393
394 const DL_Group_Data& data() const;
395 std::shared_ptr<DL_Group_Data> m_data;
396};
397
398} // namespace Botan
399
400#endif
#define BOTAN_PUBLIC_API(maj, min)
Definition api.h:19
#define BOTAN_DEPRECATED(msg)
Definition api.h:59
BigInt power_g_p(const BigInt &x) const
Definition dl_group.h:263
static DL_Group from_PEM(std::string_view pem)
Definition dl_group.cpp:223
DL_Group(const std::vector< uint8_t, Alloc > &ber, DL_Group_Format format)
Definition dl_group.h:137
static DL_Group DL_Group_from_PEM(std::string_view pem)
Definition dl_group.h:85
static DL_Group from_name(std::string_view name)
Definition dl_group.cpp:212
DL_Group_Format Format
Definition dl_group.h:53
void BER_decode(const std::vector< uint8_t > &ber, DL_Group_Format format)
Definition dl_group.h:365
DL_Group()=default
DL_Group_Format
Definition dl_group.h:30
DL_Group_Source
Definition dl_group.h:21
EC_Point multi_exponentiate(const EC_Point &p1, const BigInt &z1, const EC_Point &p2, const BigInt &z2)
Definition point_mul.cpp:35