Botan  1.10.9
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 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/internal/workfactor.h>
9 #include <algorithm>
10 #include <cmath>
11 
12 namespace Botan {
13 
14 size_t dl_work_factor(size_t bits)
15  {
16  /*
17  Based on GNFS work factors. Constant is 1.43 times the asymptotic
18  value; I'm not sure but I believe that came from a paper on 'real
19  world' runtimes, but I don't remember where now.
20 
21  Sample return values:
22  |512| -> 64
23  |1024| -> 86
24  |1536| -> 102
25  |2048| -> 116
26  |3072| -> 138
27  |4096| -> 155
28  |8192| -> 206
29 
30  For DL algos, we use an exponent of twice the size of the result;
31  the assumption is that an arbitrary discrete log on a group of size
32  bits would take about 2^n effort, and thus using an exponent of
33  size 2^(2*n) implies that all available attacks are about as easy
34  (as e.g Pollard's kangaroo algorithm can compute the DL in sqrt(x)
35  operations) while minimizing the exponent size for performance
36  reasons.
37  */
38 
39  const size_t MIN_WORKFACTOR = 64;
40 
41  // approximates natural logarithm of p
42  const double log_p = bits / 1.4426;
43 
44  const double strength =
45  2.76 * std::pow(log_p, 1.0/3.0) * std::pow(std::log(log_p), 2.0/3.0);
46 
47  return std::max(static_cast<size_t>(strength), MIN_WORKFACTOR);
48  }
49 
50 }
size_t dl_work_factor(size_t bits)
Definition: workfactor.cpp:14