Botan 3.9.0
Crypto and TLS for C&
dl_group.cpp
Go to the documentation of this file.
1/*
2* Discrete Logarithm Parameters
3* (C) 1999-2008,2015,2018 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/dl_group.h>
9
10#include <botan/ber_dec.h>
11#include <botan/der_enc.h>
12#include <botan/numthry.h>
13#include <botan/pem.h>
14#include <botan/internal/barrett.h>
15#include <botan/internal/divide.h>
16#include <botan/internal/fmt.h>
17#include <botan/internal/mod_inv.h>
18#include <botan/internal/monty.h>
19#include <botan/internal/monty_exp.h>
20#include <botan/internal/primality.h>
21#include <botan/internal/workfactor.h>
22#include <string_view>
23
24namespace Botan {
25
26class DL_Group_Data final {
27 public:
28 DL_Group_Data(const BigInt& p, const BigInt& q, const BigInt& g, DL_Group_Source source) :
29 m_p(p),
30 m_q(q),
31 m_g(g),
32 m_mod_p(Barrett_Reduction::for_public_modulus(p)),
33 m_mod_q(Barrett_Reduction::for_public_modulus(q)),
34 m_monty_params(m_p, m_mod_p),
35 m_monty(monty_precompute(m_monty_params, m_g, /*window bits=*/4)),
36 m_p_bits(p.bits()),
37 m_q_bits(q.bits()),
38 m_estimated_strength(dl_work_factor(m_p_bits)),
39 m_exponent_bits(dl_exponent_size(m_p_bits)),
40 m_source(source) {}
41
42 DL_Group_Data(const BigInt& p, const BigInt& g, DL_Group_Source source) :
43 m_p(p),
44 m_g(g),
45 m_mod_p(Barrett_Reduction::for_public_modulus(p)),
46 m_monty_params(m_p, m_mod_p),
47 m_monty(monty_precompute(m_monty_params, m_g, /*window bits=*/4)),
48 m_p_bits(p.bits()),
49 m_q_bits(0),
50 m_estimated_strength(dl_work_factor(m_p_bits)),
51 m_exponent_bits(dl_exponent_size(m_p_bits)),
52 m_source(source) {}
53
54 ~DL_Group_Data() = default;
55
56 DL_Group_Data(const DL_Group_Data& other) = delete;
57 DL_Group_Data(DL_Group_Data&& other) = delete;
58 DL_Group_Data& operator=(const DL_Group_Data& other) = delete;
59 DL_Group_Data& operator=(DL_Group_Data&& other) = delete;
60
61 const BigInt& p() const { return m_p; }
62
63 const BigInt& q() const { return m_q; }
64
65 const BigInt& g() const { return m_g; }
66
67 const Barrett_Reduction& reducer_mod_p() const { return m_mod_p; }
68
69 const Barrett_Reduction& reducer_mod_q() const {
70 BOTAN_STATE_CHECK(m_mod_q);
71 return *m_mod_q;
72 }
73
74 const Montgomery_Params& monty_params_p() const { return m_monty_params; }
75
76 size_t p_bits() const { return m_p_bits; }
77
78 size_t q_bits() const { return m_q_bits; }
79
80 size_t p_bytes() const { return (m_p_bits + 7) / 8; }
81
82 size_t q_bytes() const { return (m_q_bits + 7) / 8; }
83
84 size_t estimated_strength() const { return m_estimated_strength; }
85
86 size_t exponent_bits() const { return m_exponent_bits; }
87
88 BigInt power_g_p(const BigInt& k, size_t max_k_bits) const {
89 return monty_execute(*m_monty, k, max_k_bits).value();
90 }
91
92 BigInt power_g_p_vartime(const BigInt& k) const { return monty_execute_vartime(*m_monty, k).value(); }
93
94 BigInt power_b_p(const BigInt& b, const BigInt& k, size_t max_k_bits) const {
95 return monty_exp(m_monty_params, b, k, max_k_bits).value();
96 }
97
98 BigInt power_b_p_vartime(const BigInt& b, const BigInt& k) const {
99 return monty_exp_vartime(m_monty_params, b, k).value();
100 }
101
102 bool q_is_set() const { return m_q_bits > 0; }
103
104 void assert_q_is_set(std::string_view function) const {
105 if(!q_is_set()) {
106 throw Invalid_State(fmt("DL_Group::{}: q is not set for this group", function));
107 }
108 }
109
110 DL_Group_Source source() const { return m_source; }
111
112 private:
113 BigInt m_p;
114 BigInt m_q; // zero if no q set
115 BigInt m_g;
116 Barrett_Reduction m_mod_p;
117 std::optional<Barrett_Reduction> m_mod_q;
118 Montgomery_Params m_monty_params;
119 std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
120 size_t m_p_bits;
121 size_t m_q_bits;
122 size_t m_estimated_strength;
123 size_t m_exponent_bits;
124 DL_Group_Source m_source;
125};
126
127//static
128std::shared_ptr<DL_Group_Data> DL_Group::BER_decode_DL_group(const uint8_t data[],
129 size_t data_len,
130 DL_Group_Format format,
131 DL_Group_Source source) {
132 BER_Decoder decoder(data, data_len);
133 BER_Decoder ber = decoder.start_sequence();
134
135 if(format == DL_Group_Format::ANSI_X9_57) {
136 BigInt p;
137 BigInt q;
138 BigInt g;
139 ber.decode(p).decode(q).decode(g).verify_end();
140 return std::make_shared<DL_Group_Data>(p, q, g, source);
141 } else if(format == DL_Group_Format::ANSI_X9_42) {
142 BigInt p;
143 BigInt g;
144 BigInt q;
145 ber.decode(p).decode(g).decode(q).discard_remaining();
146 return std::make_shared<DL_Group_Data>(p, q, g, source);
147 } else if(format == DL_Group_Format::PKCS_3) {
148 BigInt p;
149 BigInt g;
150 ber.decode(p).decode(g).discard_remaining();
151 return std::make_shared<DL_Group_Data>(p, g, source);
152 } else {
153 throw Invalid_Argument("Unknown DL_Group encoding");
154 }
155}
156
157//static
158std::shared_ptr<DL_Group_Data> DL_Group::load_DL_group_info(const char* p_str, const char* q_str, const char* g_str) {
159 const BigInt p(p_str);
160 const BigInt q(q_str);
161 const BigInt g(g_str);
162
163 if(q.is_zero()) {
164 return std::make_shared<DL_Group_Data>(p, g, DL_Group_Source::Builtin);
165 } else {
166 return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);
167 }
168}
169
170//static
171std::shared_ptr<DL_Group_Data> DL_Group::load_DL_group_info(const char* p_str, const char* g_str) {
172 const BigInt p(p_str);
173 const BigInt q = (p - 1) / 2;
174 const BigInt g(g_str);
175
176 return std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::Builtin);
177}
178
179namespace {
180
181DL_Group_Format pem_label_to_dl_format(std::string_view label) {
182 if(label == "DH PARAMETERS") {
184 } else if(label == "DSA PARAMETERS") {
186 } else if(label == "X942 DH PARAMETERS" || label == "X9.42 DH PARAMETERS") {
188 } else {
189 throw Decoding_Error(fmt("DL_Group: Unknown PEM label '{}'", label));
190 }
191}
192
193} // namespace
194
195/*
196* DL_Group Constructor
197*/
198DL_Group::DL_Group(std::string_view str) {
199 // Either a name or a PEM block, try name first
200 m_data = DL_group_info(str);
201
202 if(m_data == nullptr) {
203 try {
204 std::string label;
205 const std::vector<uint8_t> ber = unlock(PEM_Code::decode(str, label));
206 DL_Group_Format format = pem_label_to_dl_format(label);
207
208 m_data = BER_decode_DL_group(ber.data(), ber.size(), format, DL_Group_Source::ExternalSource);
209 } catch(...) {}
210 }
211
212 if(m_data == nullptr) {
213 throw Invalid_Argument(fmt("DL_Group: Unknown group '{}'", str));
214 }
215}
216
217DL_Group DL_Group::from_name(std::string_view name) {
218 auto data = DL_group_info(name);
219
220 if(!data) {
221 throw Invalid_Argument(fmt("DL_Group: Unknown group '{}'", name));
222 }
223
224 return DL_Group(data);
225}
226
227//static
228DL_Group DL_Group::from_PEM(std::string_view pem) {
229 std::string label;
230 const std::vector<uint8_t> ber = unlock(PEM_Code::decode(pem, label));
231 DL_Group_Format format = pem_label_to_dl_format(label);
232 return DL_Group(ber, format);
233}
234
235namespace {
236
237/*
238* Create generator of the q-sized subgroup (DSA style generator)
239*/
240BigInt make_dsa_generator(const BigInt& p, const BigInt& q) {
241 BigInt e;
242 BigInt r;
243 vartime_divide(p - 1, q, e, r);
244
245 if(e == 0 || r > 0) {
246 throw Invalid_Argument("make_dsa_generator q does not divide p-1");
247 }
248
249 // TODO we compute these, then throw them away and recompute in DL_Group_Data
251 Montgomery_Params params(p, mod_p);
252
253 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) {
254 BigInt g = monty_exp_vartime(params, BigInt::from_word(PRIMES[i]), e).value();
255 if(g > 1) {
256 return g;
257 }
258 }
259
260 throw Internal_Error("DL_Group: Couldn't create a suitable generator");
261}
262
263} // namespace
264
265/*
266* DL_Group Constructor
267*/
268DL_Group::DL_Group(RandomNumberGenerator& rng, PrimeType type, size_t pbits, size_t qbits) {
269 if(pbits < 1024) {
270 throw Invalid_Argument(fmt("DL_Group: requested prime size {} is too small", pbits));
271 }
272
273 if(qbits >= pbits) {
274 throw Invalid_Argument(fmt("DL_Group: requested q size {} is too big for p {}", qbits, pbits));
275 }
276
277 if(type == Strong) {
278 if(qbits != 0 && qbits != pbits - 1) {
279 throw Invalid_Argument("Cannot create strong-prime DL_Group with specified q bits");
280 }
281
282 const BigInt p = random_safe_prime(rng, pbits);
283 const BigInt q = (p - 1) / 2;
284
285 /*
286 Always choose a generator that is quadratic reside mod p, this forces g to
287 be a generator of the subgroup of size q.
288
289 We use 2 by default, but if 2 is not a quadratic reside then use 4 which
290 is always a quadratic reside, being the square of 2 (or p - 2)
291 */
293 if(jacobi(g, p) != 1) {
294 g = BigInt::from_word(4);
295 }
296
297 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
298 } else if(type == Prime_Subgroup) {
299 if(qbits == 0) {
300 qbits = dl_exponent_size(pbits);
301 }
302
303 const BigInt q = random_prime(rng, qbits);
304 const BigInt q2 = q * 2;
305 BigInt X;
306 BigInt p;
307 while(p.bits() != pbits || !is_prime(p, rng, 128, true)) {
308 X.randomize(rng, pbits);
309 // Variable time division is OK here since DH groups are public anyway
310 p = X - (X % q2) + 1;
311 }
312
313 const BigInt g = make_dsa_generator(p, q);
314 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
315 } else if(type == DSA_Kosherizer) {
316 if(qbits == 0) {
317 qbits = ((pbits <= 1024) ? 160 : 256);
318 }
319
320 BigInt p;
321 BigInt q;
322 generate_dsa_primes(rng, p, q, pbits, qbits);
323 const BigInt g = make_dsa_generator(p, q);
324 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
325 } else {
326 throw Invalid_Argument("DL_Group unknown PrimeType");
327 }
328}
329
330/*
331* DL_Group Constructor
332*/
333DL_Group::DL_Group(RandomNumberGenerator& rng, const std::vector<uint8_t>& seed, size_t pbits, size_t qbits) {
334 BigInt p;
335 BigInt q;
336
337 if(!generate_dsa_primes(rng, p, q, pbits, qbits, seed)) {
338 throw Invalid_Argument("DL_Group: The seed given does not generate a DSA group");
339 }
340
341 BigInt g = make_dsa_generator(p, q);
342
343 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::RandomlyGenerated);
344}
345
346/*
347* DL_Group Constructor
348*/
349DL_Group::DL_Group(const BigInt& p, const BigInt& g) {
350 m_data = std::make_shared<DL_Group_Data>(p, g, DL_Group_Source::ExternalSource);
351}
352
353/*
354* DL_Group Constructor
355*/
356DL_Group::DL_Group(const BigInt& p, const BigInt& q, const BigInt& g) {
357 if(q.is_zero()) {
358 m_data = std::make_shared<DL_Group_Data>(p, g, DL_Group_Source::ExternalSource);
359 } else {
360 m_data = std::make_shared<DL_Group_Data>(p, q, g, DL_Group_Source::ExternalSource);
361 }
362}
363
364const DL_Group_Data& DL_Group::data() const {
365 if(m_data) {
366 return *m_data;
367 }
368
369 throw Invalid_State("DL_Group uninitialized");
370}
371
373 const BigInt& p = get_p();
374 const BigInt& q = get_q();
375
376 if(y <= 1 || y >= p) {
377 return false;
378 }
379
380 if(!q.is_zero()) {
381 if(data().power_b_p_vartime(y, q) != 1) {
382 return false;
383 }
384 }
385
386 return true;
387}
388
390 const BigInt& p = get_p();
391 const BigInt& q = get_q();
392
393 if(x <= 1 || x >= p) {
394 return false;
395 }
396
397 if(q > 0 && x > q) {
398 return false;
399 }
400
401 return true;
402}
403
404bool DL_Group::verify_element_pair(const BigInt& y, const BigInt& x) const {
405 const BigInt& p = get_p();
406
407 if(y <= 1 || y >= p || x <= 1 || x >= p) {
408 return false;
409 }
410
411 if(y != this->power_g_p(x, x.bits())) {
412 return false;
413 }
414
415 return true;
416}
417
418/*
419* Verify the parameters
420*/
421bool DL_Group::verify_group(RandomNumberGenerator& rng, bool strong) const {
422 const bool from_builtin = (source() == DL_Group_Source::Builtin);
423
424 if(!strong && from_builtin) {
425 return true;
426 }
427
428 const BigInt& p = get_p();
429 const BigInt& q = get_q();
430 const BigInt& g = get_g();
431
432 if(g < 2 || p < 3 || q < 0) {
433 return false;
434 }
435
436 const size_t test_prob = 128;
437 const bool is_randomly_generated = (source() != DL_Group_Source::ExternalSource);
438
439 if(!is_prime(p, rng, test_prob, is_randomly_generated)) {
440 return false;
441 }
442
443 if(q != 0) {
444 if((p - 1) % q != 0) {
445 return false;
446 }
447 if(data().power_g_p_vartime(q) != 1) {
448 return false;
449 }
450 if(!is_prime(q, rng, test_prob, is_randomly_generated)) {
451 return false;
452 }
453 } else {
454 if(!from_builtin && !is_randomly_generated) {
455 // If we got this p,g from some unknown source, try to verify
456 // that the group order is not too absurdly small.
457
458 const size_t upper_bound = strong ? 1000 : 100;
459
460 for(size_t i = 2; i != upper_bound; ++i) {
461 if(data().power_g_p_vartime(BigInt::from_word(i)) == 1) {
462 return false;
463 }
464 }
465 }
466 }
467
468 return true;
469}
470
471/*
472* Return the prime
473*/
474const BigInt& DL_Group::get_p() const {
475 return data().p();
476}
477
478/*
479* Return the generator
480*/
481const BigInt& DL_Group::get_g() const {
482 return data().g();
483}
484
485/*
486* Return the subgroup
487*/
488const BigInt& DL_Group::get_q() const {
489 return data().q();
490}
491
493 return data().monty_params_p();
494}
495
496bool DL_Group::has_q() const {
497 return data().q_is_set();
498}
499
500size_t DL_Group::p_bits() const {
501 return data().p_bits();
502}
503
504size_t DL_Group::p_bytes() const {
505 return data().p_bytes();
506}
507
508size_t DL_Group::q_bits() const {
509 data().assert_q_is_set("q_bits");
510 return data().q_bits();
511}
512
513size_t DL_Group::q_bytes() const {
514 data().assert_q_is_set("q_bytes");
515 return data().q_bytes();
516}
517
519 return data().estimated_strength();
520}
521
523 return data().exponent_bits();
524}
525
527 // precompute??
528 return inverse_mod_public_prime(x, get_p());
529}
530
532 return data().reducer_mod_p().reduce(x);
533}
534
535BigInt DL_Group::multiply_mod_p(const BigInt& x, const BigInt& y) const {
536 return data().reducer_mod_p().multiply(x, y);
537}
538
540 return data().reducer_mod_p();
541}
542
544 data().assert_q_is_set("inverse_mod_q");
545 // precompute??
546 return inverse_mod_public_prime(x, get_q());
547}
548
550 data().assert_q_is_set("mod_q");
551 return data().reducer_mod_q().reduce(x);
552}
553
554BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y) const {
555 data().assert_q_is_set("multiply_mod_q");
556 return data().reducer_mod_q().multiply(x, y);
557}
558
559BigInt DL_Group::multiply_mod_q(const BigInt& x, const BigInt& y, const BigInt& z) const {
560 data().assert_q_is_set("multiply_mod_q");
561 return this->multiply_mod_q(this->multiply_mod_q(x, y), z);
562}
563
565 data().assert_q_is_set("square_mod_q");
566 return data().reducer_mod_q().square(x);
567}
568
569BigInt DL_Group::multi_exponentiate(const BigInt& x, const BigInt& y, const BigInt& z) const {
570 return monty_multi_exp(data().monty_params_p(), get_g(), x, y, z).value();
571}
572
573BigInt DL_Group::power_g_p(const BigInt& x, size_t max_x_bits) const {
574 return data().power_g_p(x, max_x_bits);
575}
576
577BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x) const {
578 return this->power_b_p(b, x, data().p_bits());
579}
580
581BigInt DL_Group::power_b_p(const BigInt& b, const BigInt& x, size_t max_x_bits) const {
582 return data().power_b_p(b, x, max_x_bits);
583}
584
586 return data().source();
587}
588
589/*
590* DER encode the parameters
591*/
592std::vector<uint8_t> DL_Group::DER_encode(DL_Group_Format format) const {
593 if(get_q().is_zero() && (format != DL_Group_Format::PKCS_3)) {
594 throw Encoding_Error("Cannot encode DL_Group in ANSI formats when q param is missing");
595 }
596
597 std::vector<uint8_t> output;
598 DER_Encoder der(output);
599
600 if(format == DL_Group_Format::ANSI_X9_57) {
602 } else if(format == DL_Group_Format::ANSI_X9_42) {
604 } else if(format == DL_Group_Format::PKCS_3) {
606 } else {
607 throw Invalid_Argument("Unknown DL_Group encoding");
608 }
609
610 return output;
611}
612
613/*
614* PEM encode the parameters
615*/
616std::string DL_Group::PEM_encode(DL_Group_Format format) const {
617 const std::vector<uint8_t> encoding = DER_encode(format);
618
619 if(format == DL_Group_Format::PKCS_3) {
620 return PEM_Code::encode(encoding, "DH PARAMETERS");
621 } else if(format == DL_Group_Format::ANSI_X9_57) {
622 return PEM_Code::encode(encoding, "DSA PARAMETERS");
623 } else if(format == DL_Group_Format::ANSI_X9_42) {
624 return PEM_Code::encode(encoding, "X9.42 DH PARAMETERS");
625 } else {
626 throw Invalid_Argument("Unknown DL_Group encoding");
627 }
628}
629
630DL_Group::DL_Group(const uint8_t ber[], size_t ber_len, DL_Group_Format format) {
631 m_data = BER_decode_DL_group(ber, ber_len, format, DL_Group_Source::ExternalSource);
632}
633
634} // namespace Botan
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
static Barrett_Reduction for_public_modulus(const BigInt &m)
Definition barrett.cpp:33
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition big_rand.cpp:18
size_t bits() const
Definition bigint.cpp:311
static BigInt from_word(word n)
Definition bigint.cpp:34
bool is_zero() const
Definition bigint.h:457
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:175
DER_Encoder & start_sequence()
Definition der_enc.h:65
DER_Encoder & end_cons()
Definition der_enc.cpp:173
DER_Encoder & encode(bool b)
Definition der_enc.cpp:252
const Barrett_Reduction & _reducer_mod_p() const
Definition dl_group.cpp:539
bool verify_private_element(const BigInt &x) const
Definition dl_group.cpp:389
std::vector< uint8_t > DER_encode(DL_Group_Format format) const
Definition dl_group.cpp:592
BigInt power_g_p(const BigInt &x) const
Definition dl_group.h:263
static DL_Group from_PEM(std::string_view pem)
Definition dl_group.cpp:228
BigInt mod_p(const BigInt &x) const
Definition dl_group.cpp:531
BigInt multiply_mod_p(const BigInt &x, const BigInt &y) const
Definition dl_group.cpp:535
size_t p_bits() const
Definition dl_group.cpp:500
std::string PEM_encode(DL_Group_Format format) const
Definition dl_group.cpp:616
const BigInt & get_p() const
Definition dl_group.cpp:474
static DL_Group from_name(std::string_view name)
Definition dl_group.cpp:217
BigInt multi_exponentiate(const BigInt &x, const BigInt &y, const BigInt &z) const
Definition dl_group.cpp:569
bool verify_public_element(const BigInt &y) const
Definition dl_group.cpp:372
BigInt square_mod_q(const BigInt &x) const
Definition dl_group.cpp:564
BigInt inverse_mod_q(const BigInt &x) const
Definition dl_group.cpp:543
size_t p_bytes() const
Definition dl_group.cpp:504
bool verify_element_pair(const BigInt &y, const BigInt &x) const
Definition dl_group.cpp:404
size_t estimated_strength() const
Definition dl_group.cpp:518
size_t q_bytes() const
Definition dl_group.cpp:513
bool has_q() const
Definition dl_group.cpp:496
DL_Group_Source source() const
Definition dl_group.cpp:585
BigInt multiply_mod_q(const BigInt &x, const BigInt &y) const
Definition dl_group.cpp:554
BigInt inverse_mod_p(const BigInt &x) const
Definition dl_group.cpp:526
size_t q_bits() const
Definition dl_group.cpp:508
DL_Group()=default
const Montgomery_Params & _monty_params_p() const
Definition dl_group.cpp:492
BigInt power_b_p(const BigInt &b, const BigInt &x, size_t max_x_bits) const
Definition dl_group.cpp:581
size_t exponent_bits() const
Definition dl_group.cpp:522
BigInt mod_q(const BigInt &x) const
Definition dl_group.cpp:549
bool verify_group(RandomNumberGenerator &rng, bool strong=true) const
Definition dl_group.cpp:421
const BigInt & get_g() const
Definition dl_group.cpp:481
static std::shared_ptr< DL_Group_Data > DL_group_info(std::string_view name)
Definition dl_named.cpp:13
const BigInt & get_q() const
Definition dl_group.cpp:488
BigInt value() const
Definition monty.cpp:245
std::string encode(const uint8_t der[], size_t length, std::string_view label, size_t width)
Definition pem.cpp:39
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition pem.cpp:62
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:230
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition make_prm.cpp:97
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
Montgomery_Int monty_exp_vartime(const Montgomery_Params &params_p, const BigInt &g, const BigInt &k)
Definition monty_exp.h:55
const uint16_t PRIMES[]
Definition primes.cpp:12
const size_t PRIME_TABLE_SIZE
Definition numthry.h:174
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
size_t dl_work_factor(size_t bits)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:354
BigInt inverse_mod_public_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:291
Montgomery_Int monty_multi_exp(const Montgomery_Params &params_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)
std::vector< T > unlock(const secure_vector< T > &in)
Definition secmem.h:86
bool generate_dsa_primes(RandomNumberGenerator &rng, BigInt &p, BigInt &q, size_t pbits, size_t qbits, const std::vector< uint8_t > &seed_c, size_t offset)
Definition dsa_gen.cpp:54
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
size_t dl_exponent_size(size_t bits)
DL_Group_Format
Definition dl_group.h:30
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition numthry.cpp:116
DL_Group_Source
Definition dl_group.h:21
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition make_prm.cpp:294
Montgomery_Int monty_exp(const Montgomery_Params &params_p, const BigInt &g, const BigInt &k, size_t max_k_bits)
Definition monty_exp.h:47