Botan
1.11.15
|
00001 /* 00002 * Public Key Work Factor Functions 00003 * (C) 1999-2007,2012 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/workfactor.h> 00009 #include <algorithm> 00010 #include <cmath> 00011 00012 namespace Botan { 00013 00014 size_t ecp_work_factor(size_t bits) 00015 { 00016 return bits / 2; 00017 } 00018 00019 size_t dl_work_factor(size_t bits) 00020 { 00021 /* 00022 Based on GNFS work factors. Constant is 1.43 times the asymptotic 00023 value; I'm not sure but I believe that came from a paper on 'real 00024 world' runtimes, but I don't remember where now. 00025 00026 Sample return values: 00027 |512| -> 64 00028 |1024| -> 86 00029 |1536| -> 102 00030 |2048| -> 116 00031 |3072| -> 138 00032 |4096| -> 155 00033 |8192| -> 206 00034 00035 For DL algos, we use an exponent of twice the size of the result; 00036 the assumption is that an arbitrary discrete log on a group of size 00037 bits would take about 2^n effort, and thus using an exponent of 00038 size 2^(2*n) implies that all available attacks are about as easy 00039 (as e.g Pollard's kangaroo algorithm can compute the DL in sqrt(x) 00040 operations) while minimizing the exponent size for performance 00041 reasons. 00042 */ 00043 00044 const size_t MIN_WORKFACTOR = 64; 00045 00046 // approximates natural logarithm of p 00047 const double log_p = bits / 1.4426; 00048 00049 const double strength = 00050 2.76 * std::pow(log_p, 1.0/3.0) * std::pow(std::log(log_p), 2.0/3.0); 00051 00052 return std::max(static_cast<size_t>(strength), MIN_WORKFACTOR); 00053 } 00054 00055 }