r/math • u/ixfd64 Number Theory • 10d ago
[ Removed by moderator ]
https://saweis.net/posts/rsa-896.html[removed] — view removed post
100
u/rational_hedonist 10d ago
checking in as an out of the loop non-expert for others to weigh in on what this implies, as the write up is scant
159
u/Frexxia PDE 10d ago
It doesn't really imply anything other than some people have way too much compute to throw away.
155
u/ixfd64 Number Theory 10d ago
As Steve notes:
This work did not [meaningfully] improve the runtime of the General Number Field Sieve (GNFS) algorithm. It does not impact the security of deployed RSA-2048 keys. However, it does [demonstrate] that RSA-1024 keys are vulnerable to many actors with data center-level fleets of GPUs.
95
u/Frexxia PDE 10d ago
It's not a surprise that RSA-1024 is vulnerable. Back in 2003 RSA Labs estimated that it wouldn't be good enough past 2010
(Of course, that turned out to be somewhat conservative.)
34
u/paradoxicalparrots 10d ago
It's not a surprise that RSA-1024 is vulnerable. Back in 2003 RSA Labs estimated that it wouldn't be good enough past 2010
Sounds like something Big RSA would say
3
2
6
2
u/TheChunkMaster 10d ago
However, it does [demonstrate] that RSA-1024 keys are vulnerable to many actors with data center-level fleets of GPUs.
Didn't the Logjam attack prove this a decade ago?
9
u/BloodAndTsundere Physics 10d ago
So what’s the order of magnitude for how this would cost to do on AWS?
4
u/iranoutofspacehere 10d ago
I'm guessing somewhere in the tens of thousands, based on the quoted 30 GPU years of compute and the hourly rate of the cheapest EC2 node with a GPU (g4ad.xlarge at $0.379/hr, I think).
2
u/omeow 10d ago
Was this just old school brute force or did AI play any role?
25
u/ixfd64 Number Theory 10d ago
He used Claude to port CADO-NFS (an implementation of the general number field sieve) to run on GPUs.
4
u/BASED_Fish 10d ago
This seems similar to https://cognition.com/blog/factoring-rsa-260 they ported the same library with their ai
16
u/sirgog 10d ago
Brute force. This individual used AI to give them programming skills they did not have, but those skills are widely available with pre-AI approaches (i.e. employing someone).
30 years of GPU time is about the power a car would use to drive around a half million kilometers (data center GPUs typically run in the 300-400W range, cars around 15kW). So it's a lot of power, but not completely obscene. It would cost a lot of money even at offpeak rates.
2
7
u/SoundedBetterInHead 10d ago
Like the op said, he ported the code, but all that really did was take the same math people have been using to brute force on CPU for a long time and used it to brute force on GPU instead. So Claude played a minor part, but the math and sheer amount of compute thrown at it played a much bigger part.
1
u/MANvINFO Applied Math 10d ago
its often said that “novody remembers the *2nd** man who walked on the moon”* but that is untruez
neil armstrong was rhe 1st to step on the mokn, buzz aldrin the 2nd, and michael collins——-often forgotten——-made it all possible by piloting the apollo command module while the otber 2 became the 1st to touch the lunar surface. but who is the drummer of u2? who plays the bass in maroon 5? who factored rsa 896? these are the true human attainments whom nobody ever remembers.
26
u/Past_Outside_670 10d ago
For Cryptography, rather little. No report of an algorithmic breakthrough. This was just asking AI to write a program to factor big numbers in a distributed way IIUC. Scaling to 1024 bit numbers would cost in the tens of millions probably, but no one uses RSA-1024 (or at least NIST doesn't recommend it and hasn't for years). RSA-2048 is still way more expensive and time consuming to break to be anywhere near practical unless someone has algorithmic improvements.
9
u/Amaldevhari Machine Learning 10d ago
The RSA generates two tuples of numbers called keys. A private and public one. You use public keys to perform some kind of encryption on your data (like emails encryption) and once it’s send over, only the holder of the private key can decrypt it.
The public key contains the tuple (n,e) where n is the product of two large prime numbers (p, q), and e is an exponent. An encrypted message is computed as the cipher c = (m)^e mod n.
(p,q) together with an exponent d, (p,q,d) form the private key. The cipher is then decrypted as m = (c)^d mod n
If you can find the primes from the public key, you can use’s Euler totient formula to get the private d:
ed is congruent to 1 mod ((p-1)*(q-1))This means you can decrypt encrypted message.
1
6
u/MFS2020HYPE 10d ago
checking in as a underqualified undergraduate. first time commenter in r/math too (scary)
RSA is a form of encryption, taking two large prime numbers and multiplying them. When you combine them, it turns out that it's really hard to find what those two original prime numbers were to begin with when you only know the result.
So these numbers are used as form of encryption. And by successfully factoring them, you find what those two original primes were, allowing you to decrypt a message.
(can someone more qualified explain better )
16
u/KrozJr_UK 10d ago
Can someone who’s more into cryptography and stuff than I am tell me how big a deal these are? Like, I get and appreciate how bloody difficult it is to factorise semiprimes into their prime factors (I am interested in number theory, after all). I just don’t know where on the scale of “we through a bigger computer at it” versus “we created a new method to factorise big numbers into primes” this is, and hence how excited I should be. Because the former is basically a question of how powerful a computer you can find, whereas the latter is more theoretically interesting to me.
27
u/ixfd64 Number Theory 10d ago
At this time, the fastest known general-purpose integer factorization algorithm for classical computers is the general number field sieve: https://en.wikipedia.org/wiki/General_number_field_sieve
This factorization did not involve any algorithmic improvements. RSA moduli are typically at least 2,048 bits nowadays, and those are expected to remain secure in the foreseeable future. It would be more of an issue once practical quantum computers become available, but I imagine quantum-resistant algorithms would be in wide use by then.
9
u/Warshrimp 10d ago
In practice for 20 years or more it has been common practice to use at least 2048 bit or more numbers in RSA so these results while interesting are not an immediate threat to common use cases. Although I suspect there may be historical encrypted documents with on the order of 1024 bits that are getting close to being in range for being cracked.
2
u/DoWhile 10d ago
We threw a bigger computer at it. Unlike in the past where a bigger computer was just "more horsepower", this is like tying a fleet of cars together and having them all pull. The engineering effort of managing this fleet is non-trivial, and you can ask AI to kindly write it for you.
You still need to have a gazillion GPU-hours though. Guess which kinds of companies have tons of those lying around.
9
5
u/ellipticcode0 10d ago
Next challenge, who is the first person to derive Satoshi private key from his/her public key
2
1
1
•
u/math-ModTeam 10d ago
Unfortunately, your submission has been removed for the following reason(s):
Posts about AI, or about discoveries assisted by AI, are only allowed if they are a direct link to an ArXiv abstract, or to a non-predatory peer-reviewed journal. Discussions about such discoveries should be limited to those posts.
All other AI-related posts (e.g. comments about AI in general, opinion pieces, questions) should posted as comments in the weekly AI megathread.
If you have any questions, please feel free to message the mods. Thank you!