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
not really. they can still use the same algorithm, it'll just take longer. it might work for a while, but it's not a long term solution.
plus, cryptography is very resource-intensive, growing exponentially with key size. there comes a point when it's just not practical to use a key that large, as it will take too long to encrypt/decrypt/generate the key.
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.
RSA uses primes. This leaves the ones that don't: HFE, NTRU, ECC, XTR, Paillier, ElGamal, ....
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
The general handshaking mechanism itself is not in danger. It is the prime factor-based RSA algorithm. There might be other key algorithms in danger as well, but this doesn't reflect on the PK framework.
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.
Superpositional computation works very nicely against ECC and the discrete logarithm problem.
SC doesn't work against things in class NP-COMPLETE, but it's quite effective against many problems that are in NP but less than NP-COMPLETE. In fact, I'm scratching my head trying to find one that SC doesn't work against.
Also, the total number of qubits required is twice the number of bits in the key. While nontrivial, it is not as ridiculous as you're making it out to be. It's possible we'll have this in twenty years. Less, if engineering breakthroughs go our way; more, if they don't.