Botan  1.11.15
src/lib/pubkey/workfactor.cpp
Go to the documentation of this file.
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 }