diff options
| -rw-r--r-- | src/pubkey/workfactor.cpp | 55 | ||||
| -rw-r--r-- | src/pubkey/workfactor.h | 2 |
2 files changed, 29 insertions, 28 deletions
diff --git a/src/pubkey/workfactor.cpp b/src/pubkey/workfactor.cpp index f3d5d164a..72ba75cf9 100644 --- a/src/pubkey/workfactor.cpp +++ b/src/pubkey/workfactor.cpp @@ -1,6 +1,6 @@ /* * Public Key Work Factor Functions -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2007,2012 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -11,39 +11,40 @@ namespace Botan { -/* -* Choose the exponent size for a DL group -*/ size_t dl_work_factor(size_t bits) { -#if 0 /* - These values were taken from RFC 3526 + Based on GNFS work factors. Constant is 1.43 times the asymptotic + value; I'm not sure but I believe that came from a paper on 'real + world' runtimes, but I don't remember where now. + + Sample return values: + |512| -> 64 + |1024| -> 86 + |1536| -> 102 + |2048| -> 116 + |3072| -> 138 + |4096| -> 155 + |8192| -> 206 + + For DL algos, we use an exponent of twice the size of the result; + the assumption is that an arbitrary discrete log on a group of size + bits would take about 2^n effort, and thus using an exponent of + size 2^(2*n) implies that all available attacks are about as easy + (as e.g Pollard's kangaroo algorithm can compute the DL in sqrt(x) + operations) while minimizing the exponent size for performance + reasons. */ - if(bits <= 1536) - return 90; - else if(bits <= 2048) - return 110; - else if(bits <= 3072) - return 130; - else if(bits <= 4096) - return 150; - else if(bits <= 6144) - return 170; - else if(bits <= 8192) - return 190; - return 256; -#else - const double MIN_ESTIMATE = 64; - - const double log_x = bits / 1.44; + + const size_t MIN_WORKFACTOR = 64; + + // approximates natural logarithm of p + const double log_p = bits / 1.4426; const double strength = - 2.76 * std::pow(log_x, 1.0/3.0) * std::pow(std::log(log_x), 2.0/3.0); + 2.76 * std::pow(log_p, 1.0/3.0) * std::pow(std::log(log_p), 2.0/3.0); - return static_cast<size_t>(std::max(strength, MIN_ESTIMATE)); -#endif + return std::max(static_cast<size_t>(strength), MIN_WORKFACTOR); } - } diff --git a/src/pubkey/workfactor.h b/src/pubkey/workfactor.h index bd1a43298..179b580e7 100644 --- a/src/pubkey/workfactor.h +++ b/src/pubkey/workfactor.h @@ -13,7 +13,7 @@ namespace Botan { /** -* Estimate work factor +* Estimate work factor for discrete logarithm * @param prime_group_size size of the group in bits * @return estimated security level for this group */ |