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