Slashdot Mirror
Time Running Out for Public Key Encryption
holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"
It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys.
What this does mean is that there's going to be a lot of money to be made replacing public-key cryptograhy in custom code ala Y2K.
My blog
Yeah, the Chinese government is the only government that would like to do that.
I don't care why you're posting AC
The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15. While it is true that factoring numbers of the magnitude used in cryptography is now a "matter of engineering", there are profound difficulties involved in scaling quantum computing. The fundamental problem is called "decoherence" and describes the tendency of quantum systems to become entangled with their environment, and the consequent loss of pure quantum states. The issues involved in quantum computation connect to deep issues of thermodynamics and entropy, and research on quantum computation has potentially great significance for fundamental physics. Cryptography may have to develop and implement new, extended standards as computational techniques evolve, but the encryption sky is not yet falling.
That might be theoretically true, but in practice public keys are in use for YEARS (if not decades).
Example, vising gmail and checking out the certificate Google (which is pretty security conscious) has a key valid from 05/03/2007 through 05/14/2008 (over a year).
In order to trivially look at EVERY session encrypted over gmail an attack would need to crack that key ONCE. Google is pretty good by the way, there are certs in existence for far longer than 1 year out on the intraweb.
It is true that every session uses a symmetric cypher with a different session key... but how do you think the keys are exchanged? Once the PKI encryption is broken, the attacker will be able to read the session key in plaintext and decrypt the entire session. And this is for every single person using Google's certificate. That is why cracking PKI is so profitable, the long-term nature of the keys means once it is cracked, you have free reign for a long time.
AntiFA: An abbreviation for Anti First Amendment.
Generating the assymmetric keys takes time, that's why you use symmetric keys for real time encryption. So changing the assymmetric keys too often is unfeasible right now. You want them to be valid for a longer time than just a few seconds.