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