HN Explorer

12 comments

[ 2.9 ms ] story [ 34.3 ms ] thread
ggm
For the less numerate of us, rsa230 to rsa1024 is a linear or exponential increase in complexity? (Or some other nonlinear function)

Bitlength increase in crypto can be complex.

ColinWright
RSA-230 has 230 decimal digits, or 762 bits.[0]

RSA-1024 has 309 decimal digits, or 1024 bits.[1]

So the relative increase in size in bits is 1024/762, roughly a 34% increase, a factor of about 1.34.

Currently the complexity of the NFS is thought to be:

exp( c (ln n)^(1/3) (ln ln n)^(2/3) ) [2]

where c is about 2. That means that RSA-1024 (1024 bits) will take about 18% to 19% longer than RSA-230 (762 bits).[3]

[0] https://en.wikipedia.org/wiki/RSA_numbers#RSA-230

[1] https://en.wikipedia.org/wiki/RSA_numbers#RSA-1024

[2] https://en.wikipedia.org/wiki/General_number_field_sieve

[3] Program:

    #!/usr/bin/python

    from math import *

    ln = log

    def complexity( n ):

        return exp( \
            (64./9)**(1./3) * \
            (ln(n)**(1./3)) * \
            (ln(ln(n))**(2./3)) \
            )

    print complexity(762)
    print complexity(1024)
    print complexity(1024)/complexity(762)
ggm
Oh dear. That's very close. RSA2048 and RSA4096 make for very long outcomes in certs and dnssec and the like and I suspect HSM upgrades are coming too if we don't walk to the ECC stuff for shorter representations of the signings at equivalent complexity in solving (so I am told)

[Edit] thanks for simple python too!

ggm
I modified to code to print in a loop. The complexity() function from your second code is unaltered:

$ python3 /tmp/t.py complexity of 762, 89775939935689957703680.000000 relative complexity of 762 to 762 , 1.00

complexity of 1024, 131584429444916036885282816.000000 relative complexity of 1024 to 762 , 1465.70

complexity of 2048, 153297054278133875964680175492268032.000000 relative complexity of 2048 to 762 , 1707551649004.70

complexity of 4096, 128907209987952013910454741738429736597460090880.000000 relative complexity of 4096 to 762 , 1435877029862269597515776.00

$

Feels like the rise by bitlength is non-linear. So, moving to RSA2048 has significant benefit against 1024, to the extent 1024 is tractably weak against 762, but I am still feeling this does not point to an immediate, apparent threat to 1024.

Forseeable, but not immediate.

rurban
> Forseeable, but not immediate

This was the open source outspin of the NSA with French SW. You have to assume that internally with their own HW and SW they are at least 100x better, not counting Shor with their Quantum Computer, which should have around 2000 qbits.

malft
It's very rare for something to scale sublinearly in the number of bits :-)

complexity(2∗∗1024)/complexity(2∗∗762) comes out to about 1500x more work.

[deleted]
(comment deleted)
ColinWright
You are absolutely right - I was misled by the page I referred to using "n" as the number being factored, and not the size of the problem, which is log_2(n).

So to correct myself, the difficulty factor is 1400 to 1500, and here's the modified Python program, using the simplest change I could:

    #!/usr/bin/python
    
    from math import *
    
    ln = log
    
    def complexity( n ):
    
        lnn = ln(2**n)
    
        return exp( \
            (64./9)**(1./3) * \
            (lnn**(1./3)) * \
            (ln(lnn)**(2./3)) \
            )
    
    print complexity(762)
    print complexity(1024)
    print complexity(1024)/complexity(762)
That's not the fastest or best way to compute this, but it's the smallest and cleanest change I could get away with that reflects how I think about this, which is number of bits. A reasonable alternative is in the parent comment to this one.
jwilk
This should be slightly more efficient:

  lnn = n * ln(2)
ColinWright
It is, but not everyone is comfortable with why that is true, hence leaving it the way I did.

But you're right, it would otherwise be an appropriate simplification.

ColinWright
That's a substantial achievement, I look forward to reading the details. A little searching around suggests that it was a run of CADO-NFS[0] and it's likely that they simply ran it for long enough on a large enough cluster, but we'll wait for the details.

Congratulations to the team.

[0] http://cado-nfs.gforge.inria.fr/