Impressive. I wonder the methodology. Algorithmic improvements? More probably just an implementational optimisation. Last RSA record was due to special q sieving methods if I recall well, some 3k core hours.
I hope there’s a theoretical improvement behind the result.
So RSA 260 is about 2-3 times harder than RSA 250, which was solved in 2700 core hours in 2020, so it’s probably no algorithmic improvements, just a tweak here and there plus faster hardware.
It's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques.
Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough?
And actual history ended up being the boring version: it was absolutely enough, factorization is seemingly settled math at this point, no new techniques have been discovered.
At the end of the day RSA was just fine and no one really needed to bother with ECC and all of its confusing tutorials.
And the ~23 year old 1024 bit key holding my GnuPG box closed is still just fine, cryptographically. (Though the chances of getting hit with a keylogger or other side channel attack over that period are nontrivially high and I suppose I really should rotate it or something).
RSA might be fine mathematically but as a production cryptosystem it’s an unmitigated disaster by modern standards.
Compared to elliptic curves, it is comically easy to build an RSA implementation which is catastrophically broken. Both the number of and subtlety of footguns in RSA are extreme.
Even ignoring that, ECC is far more efficient (in part thanks to smaller key sizes and being able to be done with fixed-width arithmetic rather than needing bignums) and far better suited for embedded devices. Migration has been an enormous win even if you think the security of RSA is fine.
Assuming a given fixed key size, where does RSA need non-fixed-width arithmatic? AFAIK you can do all RSA maths with registers just double as wide as the key, no variable width anything required there. And I don't think that this is much different from ECC maths, apart from ECC's keys just being way less wide for an approximately equivalent security level.
the researchers from the RSA-250 record have publicly claimed that factoring 1024-bit RSA keys is within reach of nation states. Your 1024 bit key is only "fine" because you are a small fry, not because cryptographers think it cannot be attacked. This would be true if you used a (non-standard) RSA-768 parameterization as well, which is easier than what we are talking about on this post.
It's also worth mentioning the main concern for RSA is not GNFS, but something stronger. SOTA RSA attacks (such as GNFS) use "index calculus". You can also use index calculus to attack finite field diffie hellman. In the 2010's, there was remarkable progress in index calculus attacks against finite field DH in the small characteristic case. For example, the current record for binary characteristic finite field DH is ~30k bits (and this is by an academic --- a nation state could definitely do more).
It is not known that similar progress is possible in other cases (such as for RSA). But it's very much possible that factoring is much easier than expected. Simultaneously I wouldn't personally bet money on it, and if that breakthrough happened, there were sufficient warning signs that I would feel justified in saying "told you so" to people trusting RSA.
> Your 1024 bit key is only "fine" because you are a small fry, not because cryptographers think it cannot be attacked.
This is falling for an xkcd 538 fallacy, btw. Nation states obviously have vast higher capability to subvert individual data than brute forcing its crypto. I stand by what I said: 1024-bit RSA keys are "fine" and will remain so. RSA-309 will not fall within our lifetime.
> it's very much possible that factoring is much easier than expected
And this is sort of toothless? I mean, that's true for ECC too. It's true for all cryptography. It's true for all software. For all engineering. For all math. We'll never know what we don't know. New discoveries tomorrow may upend everything any given property ("safety" is just one) we think our existing machines hold.
But they probably won't. And the moments where that happens are extremely rare. And to be blunt RSA already got hit with that particular lightning bolt.
That's a weirdly confident prediction. Why do you think 309 isn't going to fall in our lifetimes?
"SHA2 will never be broken in our lifetimes" is something I've heard JP Aumasson say many times, but that's based on the fact that there's no line of sight anywhere to techniques that could break it. But you can't say that about 1024 bit RSA.
Background: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough?
And actual history ended up being the boring version: it was absolutely enough, factorization is seemingly settled math at this point, no new techniques have been discovered.
At the end of the day RSA was just fine and no one really needed to bother with ECC and all of its confusing tutorials.
And the ~23 year old 1024 bit key holding my GnuPG box closed is still just fine, cryptographically. (Though the chances of getting hit with a keylogger or other side channel attack over that period are nontrivially high and I suppose I really should rotate it or something).
Compared to elliptic curves, it is comically easy to build an RSA implementation which is catastrophically broken. Both the number of and subtlety of footguns in RSA are extreme.
Even ignoring that, ECC is far more efficient (in part thanks to smaller key sizes and being able to be done with fixed-width arithmetic rather than needing bignums) and far better suited for embedded devices. Migration has been an enormous win even if you think the security of RSA is fine.
It's also worth mentioning the main concern for RSA is not GNFS, but something stronger. SOTA RSA attacks (such as GNFS) use "index calculus". You can also use index calculus to attack finite field diffie hellman. In the 2010's, there was remarkable progress in index calculus attacks against finite field DH in the small characteristic case. For example, the current record for binary characteristic finite field DH is ~30k bits (and this is by an academic --- a nation state could definitely do more).
It is not known that similar progress is possible in other cases (such as for RSA). But it's very much possible that factoring is much easier than expected. Simultaneously I wouldn't personally bet money on it, and if that breakthrough happened, there were sufficient warning signs that I would feel justified in saying "told you so" to people trusting RSA.
This is falling for an xkcd 538 fallacy, btw. Nation states obviously have vast higher capability to subvert individual data than brute forcing its crypto. I stand by what I said: 1024-bit RSA keys are "fine" and will remain so. RSA-309 will not fall within our lifetime.
> it's very much possible that factoring is much easier than expected
And this is sort of toothless? I mean, that's true for ECC too. It's true for all cryptography. It's true for all software. For all engineering. For all math. We'll never know what we don't know. New discoveries tomorrow may upend everything any given property ("safety" is just one) we think our existing machines hold.
But they probably won't. And the moments where that happens are extremely rare. And to be blunt RSA already got hit with that particular lightning bolt.
"SHA2 will never be broken in our lifetimes" is something I've heard JP Aumasson say many times, but that's based on the fact that there's no line of sight anywhere to techniques that could break it. But you can't say that about 1024 bit RSA.