Add more workfactor estimate helpers.

Specifically a named one for integer factorization (despite using same
formula as DL calc) which incorporates the k value from RFC 3766. Also
adds dl_exponent_size which returns the exponent size, this one ignores
k thus using a ~10 bit larger exponent than strictly necessary.

Adding in k downgrades 1024 bit RSA to exactly 80 bits, which is probably
about right.

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