/src/botan/src/lib/pubkey/workfactor.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Public Key Work Factor Functions |
3 | | * (C) 1999-2007,2012 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/workfactor.h> |
9 | | #include <algorithm> |
10 | | #include <cmath> |
11 | | |
12 | | namespace Botan { |
13 | | |
14 | | size_t ecp_work_factor(size_t bits) |
15 | 0 | { |
16 | 0 | return bits / 2; |
17 | 0 | } |
18 | | |
19 | | namespace { |
20 | | |
21 | | size_t nfs_workfactor(size_t bits, double log2_k) |
22 | 12.2k | { |
23 | 12.2k | // approximates natural logarithm of an integer of given bitsize |
24 | 12.2k | const double log2_e = 1.44269504088896340736; |
25 | 12.2k | const double log_p = bits / log2_e; |
26 | 12.2k | |
27 | 12.2k | const double log_log_p = std::log(log_p); |
28 | 12.2k | |
29 | 12.2k | // RFC 3766: k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) |
30 | 12.2k | const double est = 1.92 * std::pow(log_p * log_log_p * log_log_p, 1.0/3.0); |
31 | 12.2k | |
32 | 12.2k | // return log2 of the workfactor |
33 | 12.2k | return static_cast<size_t>(log2_k + log2_e * est); |
34 | 12.2k | } |
35 | | |
36 | | } |
37 | | |
38 | | size_t if_work_factor(size_t bits) |
39 | 6.13k | { |
40 | 6.13k | // RFC 3766 estimates k at .02 and o(1) to be effectively zero for sizes of interest |
41 | 6.13k | |
42 | 6.13k | const double log2_k = -5.6438; // log2(.02) |
43 | 6.13k | return nfs_workfactor(bits, log2_k); |
44 | 6.13k | } |
45 | | |
46 | | size_t dl_work_factor(size_t bits) |
47 | 6.13k | { |
48 | 6.13k | // Lacking better estimates... |
49 | 6.13k | return if_work_factor(bits); |
50 | 6.13k | } |
51 | | |
52 | | size_t dl_exponent_size(size_t bits) |
53 | 6.13k | { |
54 | 6.13k | /* |
55 | 6.13k | This uses a slightly tweaked version of the standard work factor |
56 | 6.13k | function above. It assumes k is 1 (thus overestimating the strength |
57 | 6.13k | of the prime group by 5-6 bits), and always returns at least 128 bits |
58 | 6.13k | (this only matters for very small primes). |
59 | 6.13k | */ |
60 | 6.13k | const size_t min_workfactor = 64; |
61 | 6.13k | const double log2_k = 0; |
62 | 6.13k | |
63 | 6.13k | return 2 * std::max<size_t>(min_workfactor, nfs_workfactor(bits, log2_k)); |
64 | 6.13k | } |
65 | | |
66 | | } |