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