Botan 3.0.0-alpha0
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* The DL group encoding format variants.
26*/
27enum class DL_Group_Format {
30 PKCS_3,
31
36};
37
38/**
39* This class represents discrete logarithm groups. It holds a prime
40* modulus p, a generator g, and (optionally) a prime q which is a
41* factor of (p-1). In most cases g generates the order-q subgroup.
42*/
44 {
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(const std::string& name);
69
70 /*
71 * Read a PEM representation
72 */
73 static DL_Group DL_Group_from_PEM(const std::string& 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 */
89 size_t pbits, size_t qbits = 0);
90
91 /**
92 * Create a DSA group with a given seed.
93 * @param rng the random number generator to use
94 * @param seed the seed to use to create the random primes
95 * @param pbits the desired bit size of the prime p
96 * @param qbits the desired bit size of the prime q.
97 */
99 const std::vector<uint8_t>& seed,
100 size_t pbits = 1024, size_t qbits = 0);
101
102 /**
103 * Create a DL group.
104 * @param p the prime p
105 * @param g the base g
106 */
107 DL_Group(const BigInt& p, const BigInt& g);
108
109 /**
110 * Create a DL group.
111 * @param p the prime p
112 * @param q the prime q
113 * @param g the base g
114 */
115 DL_Group(const BigInt& p, const BigInt& q, const BigInt& g);
116
117 /**
118 * Decode a BER-encoded DL group param
119 */
120 DL_Group(const uint8_t ber[], size_t ber_len, DL_Group_Format format);
121
122 /**
123 * Decode a BER-encoded DL group param
124 */
125 template<typename Alloc>
126 DL_Group(const std::vector<uint8_t, Alloc>& ber, DL_Group_Format format) :
127 DL_Group(ber.data(), ber.size(), format) {}
128
129 /**
130 * Get the prime p.
131 * @return prime p
132 */
133 const BigInt& get_p() const;
134
135 /**
136 * Get the prime q, returns zero if q is not used
137 * @return prime q
138 */
139 const BigInt& get_q() const;
140
141 /**
142 * Get the base g.
143 * @return base g
144 */
145 const BigInt& get_g() const;
146
147 /**
148 * Perform validity checks on the group.
149 * @param rng the rng to use
150 * @param strong whether to perform stronger by lengthier tests
151 * @return true if the object is consistent, false otherwise
152 */
153 bool verify_group(RandomNumberGenerator& rng, bool strong = true) const;
154
155 /**
156 * Verify a public element, ie check if y = g^x for some x.
157 *
158 * This is not a perfect test. It verifies that 1 < y < p and (if q is set)
159 * that y is in the subgroup of size q.
160 */
161 bool verify_public_element(const BigInt& y) const;
162
163 /**
164 * Verify a pair of elements y = g^x
165 *
166 * This verifies that 1 < x,y < p and that y=g^x mod p
167 */
168 bool verify_element_pair(const BigInt& y, const BigInt& x) const;
169
170 /**
171 * Encode this group into a string using PEM encoding.
172 * @param format the encoding format
173 * @return string holding the PEM encoded group
174 */
175 std::string PEM_encode(DL_Group_Format format) const;
176
177 /**
178 * Encode this group into a string using DER encoding.
179 * @param format the encoding format
180 * @return string holding the DER encoded group
181 */
182 std::vector<uint8_t> DER_encode(DL_Group_Format format) const;
183
184 /**
185 * Reduce an integer modulo p
186 * @return x % p
187 */
188 BigInt mod_p(const BigInt& x) const;
189
190 /**
191 * Multiply and reduce an integer modulo p
192 * @return (x*y) % p
193 */
194 BigInt multiply_mod_p(const BigInt& x, const BigInt& y) const;
195
196 /**
197 * Return the inverse of x mod p
198 */
199 BigInt inverse_mod_p(const BigInt& x) const;
200
201 /**
202 * Reduce an integer modulo q
203 * Throws if q is unset on this DL_Group
204 * @return x % q
205 */
206 BigInt mod_q(const BigInt& x) const;
207
208 /**
209 * Multiply and reduce an integer modulo q
210 * Throws if q is unset on this DL_Group
211 * @return (x*y) % q
212 */
213 BigInt multiply_mod_q(const BigInt& x, const BigInt& y) const;
214
215 /**
216 * Multiply and reduce an integer modulo q
217 * Throws if q is unset on this DL_Group
218 * @return (x*y*z) % q
219 */
220 BigInt multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const;
221
222 /**
223 * Square and reduce an integer modulo q
224 * Throws if q is unset on this DL_Group
225 * @return (x*x) % q
226 */
227 BigInt square_mod_q(const BigInt& x) const;
228
229 /**
230 * Return the inverse of x mod q
231 * Throws if q is unset on this DL_Group
232 */
233 BigInt inverse_mod_q(const BigInt& x) const;
234
235 /**
236 * Modular exponentiation
237 *
238 * @warning this function leaks the size of x via the number of
239 * loop iterations. Use the version taking the maximum size to
240 * avoid this.
241 *
242 * @return (g^x) % p
243 */
244 BigInt power_g_p(const BigInt& x) const;
245
246 /**
247 * Modular exponentiation
248 * @param x the exponent
249 * @param max_x_bits x is assumed to be at most this many bits long.
250 *
251 * @return (g^x) % p
252 */
253 BigInt power_g_p(const BigInt& x, size_t max_x_bits) const;
254
255 /**
256 * Modular exponentiation
257 * @param b the base
258 * @param x the exponent
259 * @param max_x_bits x is assumed to be at most this many bits long.
260 *
261 * @return (b^x) % p
262 */
263 BigInt power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const;
264
265 /**
266 * Multi-exponentiate
267 * Return (g^x * y^z) % p
268 */
269 BigInt multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const;
270
271 /**
272 * Return parameters for Montgomery reduction/exponentiation mod p
273 */
274 std::shared_ptr<const Montgomery_Params> monty_params_p() const;
275
276 /**
277 * Return the size of p in bits
278 * Same as get_p().bits()
279 */
280 size_t p_bits() const;
281
282 /**
283 * Return the size of p in bytes
284 * Same as get_p().bytes()
285 */
286 size_t p_bytes() const;
287
288 /**
289 * Return the size of q in bits
290 * Same as get_q().bits()
291 * Throws if q is unset
292 */
293 size_t q_bits() const;
294
295 /**
296 * Return the size of q in bytes
297 * Same as get_q().bytes()
298 * Throws if q is unset
299 */
300 size_t q_bytes() const;
301
302 /**
303 * Return size in bits of a secret exponent
304 *
305 * This attempts to balance between the attack costs of NFS
306 * (which depends on the size of the modulus) and Pollard's rho
307 * (which depends on the size of the exponent).
308 *
309 * It may vary over time for a particular group, if the attack
310 * costs change.
311 */
312 size_t exponent_bits() const;
313
314 /**
315 * Return an estimate of the strength of this group against
316 * discrete logarithm attacks (eg NFS). Warning: since this only
317 * takes into account known attacks it is by necessity an
318 * overestimate of the actual strength.
319 */
320 size_t estimated_strength() const;
321
322 /**
323 * Decode a DER/BER encoded group into this instance.
324 * @param ber a vector containing the DER/BER encoded group
325 * @param format the format of the encoded group
326 *
327 * @warning avoid this. Instead use the DL_Group constructor
328 */
329 void BER_decode(const std::vector<uint8_t>& ber, DL_Group_Format format);
330
331 DL_Group_Source source() const;
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, DL_Group_Format format)
Definition: dl_group.h:126
DL_Group()=default
std::string name
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
PolynomialVector b
Definition: kyber.cpp:821
std::string PEM_encode(const Private_Key &key)
Definition: pkcs8.cpp:137
Definition: alg_id.cpp:13
DL_Group_Format
Definition: dl_group.h:27
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:24
MechanismType type