Sunday, February 15, 2009

How long RSA will survive?

Till now, we are mostly using RSA and ECC for securely transmitting sensitive data (like passwords, credit card numbers etc). These are based on the computational limitations of the classical computer hardware.

Most public-key cryptography based system uses RSA. In RSA, a message is encrypted with a publicly available key and decrypted with a secret key, which is mathematically related with the public key. This is proven to be an effective one and being used successfully.

But, in future, RSA (and similar) cryptography may not survive. The reason is Quantum Computing. Researchers are optimist to built practical Quantum Computer within next 10/15 years. Now, the question is, how Quantum Computer can be a threat to RSA.

Quantum Computers uses Qubits (instead of bits of classical computing) for computations. A Qubit is essentialy an atom showing quantum mechanical behavior. Like normal bit, Qubits can be used to represent 0/1 by up or down spin of the atom. But, Qubit has the advantage of quantum superposition. A classical bit has exact probability (0.5) to be in the state 0 or 1. But, Qubit in quantam mechanics has a probability distribution function of any value between them in a given time. In short, at any given time:
- n bits can be one of 2^n states
- n Qubits can be in upto 2^n states simultaneously.
This can be a great advantage for parallel computing. And, that would shorten the time needed to break a strong 1024-bit RSA code from billions of years to a matter of minutes (though not in all cases, but still this is a threat)

Using larger sized key may do sometimes. Fortunately, not all types of cryptography are vulnerable. There are four types of schemes that are immune to quantum computing:
- Hash based signature scheme
- Error correcting code scheme
- Multivariate public-key cryptosystems
- Lattice system scheme (still research ongoing)

For the time being, our systems are safe. But after 10/20 years we may need new schemes or use primenumbers consisting of thousands of digits for RSA.

Time will say, but seems in future there are good research and contribution potentials in the field of cryptography.


Ragib Hasan said...


But has Quantum computing become feasible? Are there any real systems other than theoretical models?

JustEtc Technologies said... - a great blog on recent trends in industry and research.

Short notes in programming, networking, dbms, project management, sensor network and many others