2
$\begingroup$

I would like to know how to calculate the bit-strength of Integer Factorization Cryptography (IFC) such as RSA by using Python. I gathered it is based off the complexity of factorizing the modulus (public key). I want to be able to calculate the bit strength of arbitrary key-lengths of RSA for example, such as 4096 which is not given by NIST etc.

This is similar to this question Security strength of RSA in relation with the modulus size, where the answer is provided by using Mathematica.

The fastest publicly known algorithm for factoring is the General Number Field Sieve (GNFS). This has the complexity defined in L-notation. The formulae includes little-o 1, which I'm not sure how to fit into the calculations, in the Mathematica example it is left out (treated as being equal to 1).

Here is the relevant Mathematica code:

I generated these numbers with the following Mathematica code:

({#, N@Log2@g[#]} &) /@ {1024, 2048, 3072, 7680, 15360}

where g is defined as:

g[b_] := Exp[(64/9 * Log[2^b])^(1/3) * (Log[Log[2^b]])^(2/3)]

If I understand correctly taking log2 of the exp would cancel out, so the result it's equivalent to just:(64/9 * Log[2^b])^(1/3) * (Log[Log[2^b]])^(2/3).

I have tried the following Python code but it seems to be way off.

import fractions
import math

ln = math.log

n = pow(2, 1024)  ## change for other RSA key-sizes

a = fractions.Fraction(1,3)
c = pow(fractions.Fraction(64,9), fractions.Fraction(1,3))
# c = 1.9229994270765445

def g(a, c, n):
  return math.exp(c * pow(ln(n), a) * pow(ln(ln(n)), 1 - a))

x = g(a, c, n)
# x = 1.3158442944491604e+26
s = ln(x)
# s = 60.1416909264604

The result for 1024 is 60.14, whereas NIST says 80, and Mathematica got 86.77. The results for other key-sizes are all way off.

This is the results from Mathematica (3rd column) which are very close to NIST (1st column).

Strength  RSA modulus size   Complexity bit-length
  80        1024              86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

My results from my Python code are (10243, 60.14), (2048, 81.02), (3072, 96.16), etc.

I thought maybe this is due to rounding errors, but using WolfRamAlpha (I don't have Mathematica which is why I'm trying to use Python instead) I get the same results as Python.

This is what I put into WolfRamAlpha:

(64/9 * Log[2^1024])^(1/3) * (Log[Log[2^1024]])^(2/3)

Decimal result is 60.14169092646040456.... Pretty much same as my Python code. How did NIST and referenced answer get such different results. My code looks equivalent to me. I don't see my mistake.

What am I doing wrong?

Improve this question
$\endgroup$
3
  • $\begingroup$ log2 is log base 2. $log2(exp(x))$ is x times 1.44270 approximately, which gives the expected results. $\endgroup$
    – dave_thompson_085
    Jun 20, 2014 at 7:47
  • $\begingroup$ Can you make this an answer, since it is what I was doing wrong, I mistook log2 as log, whereas log * exp cancels, log2 * exp does not. $\endgroup$
    – sexybear
    Jun 23, 2014 at 1:57
  • $\begingroup$ Can the downvoter mention the reason for the down-vote $\endgroup$
    – sexybear
    Jun 23, 2014 at 1:58

1 Answer 1

Reset to default
5
$\begingroup$

(From comment so question can be closed properly)

log2 is log base 2. $log(exp(x))$ would cancel, but $log2(exp(x))$ is x times 1.44270 approximately, which gives the expected results

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.