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