For me, posts (and the community comments) like this are a large part of the value of HN.
Read the title, scanned the linked page, read the insightful comments. Gained a bit of information on the current state of cryptography. On to the next item. The accumulation of all such tidbits that appear here that has been incredibly useful.
fogus: thanks for posting
all: thanks for the perspectives.
Only 2000 compute years of a single AMD 2.2GHz were reported to be used. Using the rough estimate of 9GFlops for that chip, the current top supercomputer (that we know of) is very roughly 200,000 times as powerful.
The paper estimates 1024 would be "about a thousand times harder". 1000 times harder than 2000 compute years on that chip is roughly ten compute years on that supercomputer. Closing in...
I don't pretend to understand the deep details, but the core point is that the GNSF algorithm is exponential in the bit length of the number being factored, but the exponent turns out to be distressingly small.
I'm still not understanding where your criticism is directed. GNFS (see? no typo this time. Do I get a cookie?) is quite clearly outside of PTIME, though I'm not sure to which definitions of SUBEXP and EXPTIME it belongs. Thus RSA remains an algorithm which is infeasible for tractable key sizes, even if the early guesses of 512-1024 bits turned out to be wrong.
My profuse and abject apologies for transposing those glyphs. I can't imagine how that would have happened.
Maybe you could apply your expertise a little and give us a better explanation than mine instead of criticizing my spelling? I didn't claim to understand the deep details, but frankly your sniping is helping even less.
This is a summary of cryptographic hashes being broken via cryptanalysis (breaking the algorithm), not RSA keys (big primes) being factored. I'd love to see the same chart but for prime factorization.
It's always good to see confirmatory experiments like this, but I don't see anything surprising in these results. We've known for the past few years that RSA768 was within reach of anyone who could be bothered to coordinate it; and nobody serious trusts RSA1024 against sophisticated attackers.
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?
I'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.
Factoring 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.
It must be really aggravating spending 100 days breaking a long key, only to find a short one-time-pad message dropped into the middle of a long string full of 'neenerneenerneener!'.
The way I see it, is that if someone's willing to go to these measures to compromise your data and hurt you, you're pretty much screwed no matter what you do.
As I understand it, PGP uses RSA just at the outset to generate a 128-bit (or 256-bit or whatever) key for the rest of the message. So the PGP key length is a one-time cost (per message).
Many years ago (early 1990s) I generated a 1024-bit public key which was the limit at the time. A lot of Moores have passed since then. Since key generation and usage is no more than O(bits^2), possibly only O(bits log bits), I don't see why people aren't creating >= 8192-bit keys these days.
Or maybe they are. The MIT keyserver is down at the moment, at least if I ask it for anything.
Since key generation and usage is no more than O(bits^2), possibly only O(bits log bits)...
A private key operation with N-bit RSA takes O(N^3) time using classical arithmetic, while key generation takes O(N^4) time using classical arithmetic. Your numbers are correct for public key operations, though.
