Botan  2.18.2
Crypto and TLS for C++11
workfactor.cpp
Go to the documentation of this file.
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  {
16  return bits / 2;
17  }
18 
19 namespace {
20 
21 size_t nfs_workfactor(size_t bits, double log2_k)
22  {
23  // approximates natural logarithm of an integer of given bitsize
24  const double log2_e = 1.44269504088896340736;
25  const double log_p = bits / log2_e;
26 
27  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  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  return static_cast<size_t>(log2_k + log2_e * est);
34  }
35 
36 }
37 
38 size_t if_work_factor(size_t bits)
39  {
40  // RFC 3766 estimates k at .02 and o(1) to be effectively zero for sizes of interest
41 
42  const double log2_k = -5.6438; // log2(.02)
43  return nfs_workfactor(bits, log2_k);
44  }
45 
46 size_t dl_work_factor(size_t bits)
47  {
48  // Lacking better estimates...
49  return if_work_factor(bits);
50  }
51 
52 size_t dl_exponent_size(size_t bits)
53  {
54  /*
55  This uses a slightly tweaked version of the standard work factor
56  function above. It assumes k is 1 (thus overestimating the strength
57  of the prime group by 5-6 bits), and always returns at least 128 bits
58  (this only matters for very small primes).
59  */
60  const size_t min_workfactor = 64;
61  const double log2_k = 0;
62 
63  return 2 * std::max<size_t>(min_workfactor, nfs_workfactor(bits, log2_k));
64  }
65 
66 }
size_t if_work_factor(size_t bits)
Definition: workfactor.cpp:38
size_t ecp_work_factor(size_t bits)
Definition: workfactor.cpp:14
Definition: alg_id.cpp:13
size_t dl_exponent_size(size_t bits)
Definition: workfactor.cpp:52
size_t dl_work_factor(size_t bits)
Definition: workfactor.cpp:46