Botan  2.19.1
Crypto and TLS for C++11
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 
13 namespace Botan {
14 
15 class Montgomery_Params;
16 class DL_Group_Data;
17 
18 enum 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  */
86  DL_Group(RandomNumberGenerator& rng, PrimeType type,
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
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
Definition: bigint.h:1143
MechanismType type
DL_Group_Source
Definition: dl_group.h:18
std::string name
std::string PEM_encode(const Private_Key &key)
Definition: pkcs8.cpp:148
Definition: alg_id.cpp:13
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_mul.cpp:25