4 ms·
Correct my ignorance, please, but people are talking like cryptosystems using 768-bit keys have been cracked. These folks showed that you can factor a single 7
by nathanb 17y ago
Correct my ignorance, please, but people are talking like cryptosystems using 768-bit keys have been cracked.
These folks showed that you can factor a single 768-bit number in under four years, if you have the computing power of a moderate-size cluster at your disposal and approximately one terabyte of memory. Interesting, certainly, but this exposes no vulnerabilities we weren't already aware of.
Brute forcing a 768-bit key would require multiple, potentially billions, of such factorizations, correct? Proving that you can factor an n-bit number in time t simply demonstrates that the time required to crack a cryptosystem with an n-bit key on the same hardware is an integer multiple of t.
Am I misunderstanding this, or are the people claiming "768 bits are not enough" just the usual paranoid element?
- tel 17y agoI'm not a security person, but my understanding is that all security systems are known to fail and thus come with a lifetime. Real safes aren't uncrackable, but uncrackable under 15 minutes of duress. Crypto seems a little different since exponential complexity pushes those lifetimes out to what people often assume is infnite. A demonstration of a 4 year lifetime of a 768-bit under moderately powerful attack makes it clear that it isn't different and that its lifetime is now scarily short. It's a lot like what I assume the introduction of power tools might have done to safe cracking. What previously was a 30 minute safe becomes a 30 second safe once the people you want to keep out can drill.
- Retric 17y agoFactoring a single 768-bit key let's you read every message sent to a single person using 768-bit RSA. Of forge a message signed by someone using a related system to sign documents. PS: Don't forget, a large bot net could use 1 million CPU cluster to crack the same number.
- jrockway 17y agoBrute forcing a 768-bit key would require multiple, potentially billions, of such factorizations, correct? No. There is only one possible factorization of an RSA public key. RSA public keys are, by definition, the product of exactly two primes. Once you have factored the public key, it is trivial to derive the private key from the two factors. RSA is only secure because it is hard to factor numbers. This work shows that it's just hard, not impossible.
- nathanb 17y agoI see...thank you for correcting my false assumption.