/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/internal/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 | 136 | { |
23 | | // approximates natural logarithm of an integer of given bitsize |
24 | 136 | const double log2_e = 1.44269504088896340736; |
25 | 136 | const double log_p = bits / log2_e; |
26 | | |
27 | 136 | const double log_log_p = std::log(log_p); |
28 | | |
29 | | // RFC 3766: k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) |
30 | 136 | const double est = 1.92 * std::pow(log_p * log_log_p * log_log_p, 1.0/3.0); |
31 | | |
32 | | // return log2 of the workfactor |
33 | 136 | return static_cast<size_t>(log2_k + log2_e * est); |
34 | 136 | } |
35 | | |
36 | | } |
37 | | |
38 | | size_t if_work_factor(size_t bits) |
39 | 539 | { |
40 | 539 | if(bits < 512) |
41 | 403 | return 0; |
42 | | |
43 | | // RFC 3766 estimates k at .02 and o(1) to be effectively zero for sizes of interest |
44 | | |
45 | 136 | const double log2_k = -5.6438; // log2(.02) |
46 | 136 | return nfs_workfactor(bits, log2_k); |
47 | 539 | } |
48 | | |
49 | | size_t dl_work_factor(size_t bits) |
50 | 539 | { |
51 | | // Lacking better estimates... |
52 | 539 | return if_work_factor(bits); |
53 | 539 | } |
54 | | |
55 | | size_t dl_exponent_size(size_t bits) |
56 | 539 | { |
57 | 539 | if(bits == 0) |
58 | 0 | return 0; |
59 | 539 | if(bits <= 256) |
60 | 381 | return bits - 1; |
61 | 158 | if(bits <= 1024) |
62 | 48 | return 192; |
63 | 110 | if(bits <= 1536) |
64 | 63 | return 224; |
65 | 47 | if(bits <= 2048) |
66 | 47 | return 256; |
67 | 0 | if(bits <= 4096) |
68 | 0 | return 384; |
69 | 0 | return 512; |
70 | 0 | } |
71 | | |
72 | | } |