RSA-230 has been factored | Hacker News Reader

RSA-230 has been factored

lists.gforge.inria.fr

60 pointsbane11 comments

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/

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.

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)

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!

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.

> 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.

Hi, On the topic of the relative difficulty/complexity of factoring RSA1024, one should be interested in the analysis contained in https://eprint.iacr.org/2010/006.pdf, where sieving for RSA1024 is benchmarked as 1000x that of RSA768, and later, due to improvements in polynomial selection http://www.ams.org/journals/mcom/2016-85-298/S0025-5718-2015... , 490x compared to the RSA768 result.

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.

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.

This should be slightly more efficient:

  lnn = n * ln(2)

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.

Reply on news.ycombinator.com