PDA

View Full Version : Quantum Computers and RSA Encryption



publius
2013-Jun-10, 07:06 AM
From stuff I've been reading, it is said that a quantum computer of enough power would be able to easily break RSA public key encryption. If anyone is knowledgable on this business, would you care to give me the Cliff Notes version of this works? The stuff I read is either too dumbed down or not dumbed down enough for me :)

I know it has to do with factoring of large prime numbers, and the quantum computer can do the required numerical drudgery very fast (sort of doing it all at once) via some very clever tricks. Supposedly this cuts the time required from exponential (or near exponential) to polynomial time, ie O(N^3) rather than O(e^N).

If someone would just sort of run through the process of how we would "crack" something doing this, I'd appreciate it. And, and I'm assuming this has to be true, is there a process/method where the O time would be still be ridiculously large for a quantum computer and not ridiculously large for the encrypting system that one could be safe?

Jens
2013-Jun-10, 07:37 AM
I think I can only give you a very dumbed down version, but from the perspective of someone who has studied it a little bit. Yes, a quantum computer would be able to do it very fast, by using the property of qubits of being to have more than one value at once, like the position of an electron within an atom. So it would theoretically make the calculations very fast. Unfortunately, quantum computers prove very difficult to make, and I seriously doubt that the NSA has a powerful one (they probably have experimental ones, but none that could outperform even a simple normal computer). As for the last question, I think a quantum computer would just be more powerful at breaking codes, so you would just need to have longer encryptions.

HenrikOlsen
2013-Jun-10, 08:23 AM
As for the last question, I think a quantum computer would just be more powerful at breaking codes, so you would just need to have longer encryptions.
The "just" is a very large "just" though.

Ivan Viehoff
2013-Jun-10, 02:24 PM
I think the quantum computer recently in the news was one that exploits quantum tunnelling effects rather than Qubits.

There seem to be useful developments in quantum encryption that even quantum computers can't get around.