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