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