Coverage Report

Created: 2020-05-23 13:54

/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.5k
   {
23
12.5k
   // approximates natural logarithm of an integer of given bitsize
24
12.5k
   const double log2_e = 1.44269504088896340736;
25
12.5k
   const double log_p = bits / log2_e;
26
12.5k
27
12.5k
   const double log_log_p = std::log(log_p);
28
12.5k
29
12.5k
   // RFC 3766: k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2))
30
12.5k
   const double est = 1.92 * std::pow(log_p * log_log_p * log_log_p, 1.0/3.0);
31
12.5k
32
12.5k
   // return log2 of the workfactor
33
12.5k
   return static_cast<size_t>(log2_k + log2_e * est);
34
12.5k
   }
35
36
}
37
38
size_t if_work_factor(size_t bits)
39
6.27k
   {
40
6.27k
   // RFC 3766 estimates k at .02 and o(1) to be effectively zero for sizes of interest
41
6.27k
42
6.27k
   const double log2_k = -5.6438; // log2(.02)
43
6.27k
   return nfs_workfactor(bits, log2_k);
44
6.27k
   }
45
46
size_t dl_work_factor(size_t bits)
47
6.27k
   {
48
6.27k
   // Lacking better estimates...
49
6.27k
   return if_work_factor(bits);
50
6.27k
   }
51
52
size_t dl_exponent_size(size_t bits)
53
6.27k
   {
54
6.27k
   /*
55
6.27k
   This uses a slightly tweaked version of the standard work factor
56
6.27k
   function above. It assumes k is 1 (thus overestimating the strength
57
6.27k
   of the prime group by 5-6 bits), and always returns at least 128 bits
58
6.27k
   (this only matters for very small primes).
59
6.27k
   */
60
6.27k
   const size_t min_workfactor = 64;
61
6.27k
   const double log2_k = 0;
62
6.27k
63
6.27k
   return 2 * std::max<size_t>(min_workfactor, nfs_workfactor(bits, log2_k));
64
6.27k
   }
65
66
}