diff options
| -rw-r--r-- | src/lib/pubkey/dh/dh.cpp | 2 | ||||
| -rw-r--r-- | src/lib/pubkey/dl_group/dl_group.cpp | 2 | ||||
| -rw-r--r-- | src/lib/pubkey/elgamal/elgamal.cpp | 4 | ||||
| -rw-r--r-- | src/lib/pubkey/if_algo/if_algo.cpp | 2 | ||||
| -rw-r--r-- | src/lib/pubkey/workfactor.cpp | 56 | ||||
| -rw-r--r-- | src/lib/pubkey/workfactor.h | 19 |
6 files changed, 53 insertions, 32 deletions
diff --git a/src/lib/pubkey/dh/dh.cpp b/src/lib/pubkey/dh/dh.cpp index f182a7792..3888166bb 100644 --- a/src/lib/pubkey/dh/dh.cpp +++ b/src/lib/pubkey/dh/dh.cpp @@ -43,7 +43,7 @@ DH_PrivateKey::DH_PrivateKey(RandomNumberGenerator& rng, if(x == 0) { const BigInt& p = group_p(); - x.randomize(rng, 2 * dl_work_factor(p.bits())); + x.randomize(rng, dl_exponent_size(p.bits())); } if(y == 0) diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp index fbaa67eaa..8e9c35f2a 100644 --- a/src/lib/pubkey/dl_group/dl_group.cpp +++ b/src/lib/pubkey/dl_group/dl_group.cpp @@ -55,7 +55,7 @@ DL_Group::DL_Group(RandomNumberGenerator& rng, else if(type == Prime_Subgroup) { if(!qbits) - qbits = 2 * dl_work_factor(pbits); + qbits = dl_exponent_size(pbits); q = random_prime(rng, qbits); BigInt X; diff --git a/src/lib/pubkey/elgamal/elgamal.cpp b/src/lib/pubkey/elgamal/elgamal.cpp index 5bcdd5689..4ff3cc47a 100644 --- a/src/lib/pubkey/elgamal/elgamal.cpp +++ b/src/lib/pubkey/elgamal/elgamal.cpp @@ -34,7 +34,7 @@ ElGamal_PrivateKey::ElGamal_PrivateKey(RandomNumberGenerator& rng, x = x_arg; if(x == 0) - x.randomize(rng, 2 * dl_work_factor(group_p().bits())); + x.randomize(rng, dl_exponent_size(group_p().bits())); y = power_mod(group_g(), x, group_p()); @@ -112,7 +112,7 @@ ElGamal_Encryption_Operation::raw_encrypt(const byte msg[], size_t msg_len, if(m >= p) throw Invalid_Argument("ElGamal encryption: Input is too large"); - BigInt k(rng, 2 * dl_work_factor(p.bits())); + BigInt k(rng, dl_exponent_size(p.bits())); BigInt a = powermod_g_p(k); BigInt b = mod_p.multiply(m, powermod_y_p(k)); diff --git a/src/lib/pubkey/if_algo/if_algo.cpp b/src/lib/pubkey/if_algo/if_algo.cpp index d8430b40c..9c49b8dd4 100644 --- a/src/lib/pubkey/if_algo/if_algo.cpp +++ b/src/lib/pubkey/if_algo/if_algo.cpp @@ -15,7 +15,7 @@ namespace Botan { size_t IF_Scheme_PublicKey::estimated_strength() const { - return dl_work_factor(n.bits()); + return if_work_factor(n.bits()); } AlgorithmIdentifier IF_Scheme_PublicKey::algorithm_identifier() const diff --git a/src/lib/pubkey/workfactor.cpp b/src/lib/pubkey/workfactor.cpp index 46a7be507..5cbd17f09 100644 --- a/src/lib/pubkey/workfactor.cpp +++ b/src/lib/pubkey/workfactor.cpp @@ -16,40 +16,42 @@ size_t ecp_work_factor(size_t bits) return bits / 2; } +size_t if_work_factor(size_t bits) + { + // RFC 3766: k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) + // It estimates k at .02 and o(1) to be effectively zero for sizes of interest + const double k = .02; + + // approximates natural logarithm of p + const double log2_e = std::log2(std::exp(1)); + const double log_p = bits / log2_e; + + const double est = 1.92 * std::pow(log_p * std::log(log_p) * std::log(log_p), 1.0/3.0); + + return static_cast<size_t>(std::log2(k) + log2_e * est); + } + size_t dl_work_factor(size_t bits) { + // Lacking better estimates... + return if_work_factor(bits); + } + +size_t dl_exponent_size(size_t bits) + { /* - 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. + 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; + const double log2_e = std::log2(std::exp(1)); + const double log_p = bits / log2_e; - // approximates natural logarithm of p - const double log_p = bits / 1.4426; - - const double strength = - 2.76 * std::pow(log_p, 1.0/3.0) * std::pow(std::log(log_p), 2.0/3.0); + const double strength = 1.92 * std::pow(log_p, 1.0/3.0) * std::pow(std::log(log_p), 2.0/3.0); - return std::max(static_cast<size_t>(strength), MIN_WORKFACTOR); + return 2 * std::max<size_t>(MIN_WORKFACTOR, log2_e * strength); } } diff --git a/src/lib/pubkey/workfactor.h b/src/lib/pubkey/workfactor.h index ab7f6b051..eb86b6d88 100644 --- a/src/lib/pubkey/workfactor.h +++ b/src/lib/pubkey/workfactor.h @@ -20,6 +20,25 @@ namespace Botan { size_t dl_work_factor(size_t prime_group_size); /** +* Return the appropriate exponent size to use for a particular prime +* group. This is twice the size of the estimated cost of breaking the +* key using an index calculus attack; the assumption is that if 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. +*/ +size_t dl_exponent_size(size_t prime_group_size); + +/** +* Estimate work factor for integer factorization +* @param n_bits size of modulus in bits +* @return estimated security level for this modulus +*/ +size_t if_work_factor(size_t n_bits); + +/** * Estimate work factor for EC discrete logarithm * @param prime_group_size size of the group in bits * @return estimated security level for this group |