/src/botan/src/lib/pubkey/workfactor.cpp
Line | Count | Source |
1 | | /* |
2 | | * Public Key Work Factor Functions |
3 | | * (C) 1999-2007,2012,2026 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/internal/workfactor.h> |
9 | | |
10 | | #include <botan/assert.h> |
11 | | #include <cmath> |
12 | | #include <numbers> |
13 | | |
14 | | namespace Botan { |
15 | | |
16 | 1.67k | size_t ecp_work_factor(size_t bits) { |
17 | 1.67k | return bits / 2; |
18 | 1.67k | } |
19 | | |
20 | | namespace { |
21 | | |
22 | 1.14k | size_t nfs_workfactor(size_t bits, double log2_k) { |
23 | | // approximates natural logarithm of an integer of given bitsize |
24 | 1.14k | const double log_p = static_cast<double>(bits) / std::numbers::log2e; |
25 | | |
26 | 1.14k | const double log_log_p = std::log(log_p); |
27 | | |
28 | | // RFC 3766: k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) |
29 | 1.14k | const double est = 1.92 * std::pow(log_p * log_log_p * log_log_p, 1.0 / 3.0); |
30 | | |
31 | | // return log2 of the workfactor |
32 | 1.14k | return static_cast<size_t>(log2_k + std::numbers::log2e * est); |
33 | 1.14k | } |
34 | | |
35 | | } // namespace |
36 | | |
37 | 1.16k | size_t if_work_factor(size_t bits) { |
38 | 1.16k | if(bits < 512) { |
39 | 22 | return 0; |
40 | 22 | } |
41 | | |
42 | | // RFC 3766 estimates k at .02 and o(1) to be effectively zero for sizes of interest |
43 | | |
44 | 1.14k | const double log2_k = -5.6438; // log2(.02) |
45 | 1.14k | return nfs_workfactor(bits, log2_k); |
46 | 1.16k | } |
47 | | |
48 | 330 | size_t dl_work_factor(size_t bits) { |
49 | | // Lacking better estimates... |
50 | 330 | return if_work_factor(bits); |
51 | 330 | } |
52 | | |
53 | 330 | size_t dl_exponent_size(size_t p_bits) { |
54 | 330 | BOTAN_ARG_CHECK(p_bits > 1, "Invalid prime length"); |
55 | | |
56 | | /* |
57 | | For relevant sizes we follow the suggestions in |
58 | | NIST SP 800-56B Rev 2 Appendix D |
59 | | "Maximum Security Strength Estimates for IFC Modulus Lengths" |
60 | | |
61 | | For sizes outside the range considered in the SP we use some sensible values |
62 | | |
63 | | Note that we return twice the value given in Table 4 since we are choosing |
64 | | the exponent size as twice the estimated security strength. |
65 | | |
66 | | See also NIST SP 800-56A Rev 3 Appendix D, Tables 25 and 26 |
67 | | */ |
68 | | |
69 | 330 | if(p_bits <= 256) { |
70 | | /* |
71 | | * For stupidly small groups we might return a value larger than the group |
72 | | * size if we fell into the conditionals below. Just use the maximum |
73 | | * possible exponent size - for all the good it will do you with a group |
74 | | * this weak. |
75 | | */ |
76 | 6 | return p_bits - 1; |
77 | 324 | } else if(p_bits <= 1024) { |
78 | | /* |
79 | | Not in the SP, but general estimates are that a 1024 bit group provides at |
80 | | most 80 bits security, so using an exponent appropriate for 96 bit security |
81 | | is more than sufficient. |
82 | | */ |
83 | 251 | return 192; |
84 | 251 | } else if(p_bits <= 2048) { |
85 | 73 | return 224; // SP 800-56B |
86 | 73 | } else if(p_bits <= 3072) { |
87 | 0 | return 256; // SP 800-56B |
88 | 0 | } else if(p_bits <= 4096) { |
89 | 0 | return 304; // SP 800-56B |
90 | 0 | } else if(p_bits <= 6144) { |
91 | 0 | return 352; // SP 800-56B |
92 | 0 | } else if(p_bits <= 8192) { |
93 | 0 | return 400; // SP 800-56B |
94 | 0 | } else { |
95 | | // For values larger than we know about, just saturate to 256 bit security |
96 | | // which is Good Enough for FFDH |
97 | | // |
98 | | // NIST puts 15360 bit groups at exactly 256 bits security |
99 | 0 | return 512; |
100 | 0 | } |
101 | 330 | } |
102 | | |
103 | | } // namespace Botan |