RSA-230 has been factored(lists.gforge.inria.fr)
lists.gforge.inria.fr
RSA-230 has been factored
https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2018-August/000926.html
2 comments
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.
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:
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)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.
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:
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)
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.
But you're right, it would otherwise be an appropriate simplification.
[deleted]
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!
[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.
$ 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.
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.
> 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.
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.
Congratulations to the team.
[0] http://cado-nfs.gforge.inria.fr/