Shor’s Algorithm — a threat to RSA encryption?!
RSA Encryption was once considered as unbreakable but now we are questioning it’s security, so what exactly has changed?
Let’s discuss!
RSA is one of the oldest, public-key cryptosystem that is widely used for secure data transmission. It is mainly built on the principles of public key exchange and the computationally difficult problem of prime factorization.
RSA public keys are the result of two large, randomly generated prime factors. For a classical computer, there is no particular algorithm to find out the prime factor and using the brute force it requires exponential time. So, in other words, it’s operating under the assumption that it is quite impossible to determine two randomly-generated prime numbers within a reasonable amount of time.
Does this mean that we can relay on RSA encryption algorithm?
Yes! but as long as Quantum Computing is not in loop.
In 1994, Peter Shor developed an algorithm which can solve the prime factorization problem within polynomial time on a theoretical quantum computer. The algorithm makes use of two useful quantum properties- superposition and destructive interference.
So how Shor’s algorithm exactly works?
It can be divided into two major parts, firstly the problem of prime factorization is converted into comparatively solvable problem i.e. finding the period of a modular operation. This conversion can be achieved with the help of classical computer.
But similar to the prime factorization, it’s impossible to determine the period on classical computer in less than exponential time. That’s where the second and most important part begins. According P. Shor, with the help of Quantum Fourier Series it is theoretically possible to find a quantum period in polynomial time. And once we know the period, prime factors can be easily determined on a classical computer with some additional calculations.
There are many difficulties while building the large-scale quantum-computer. That’s why the biggest challenge while implementing Shor’s algorithm is availability of a large enough quantum computer.
So for now, we can consider quantum encryption breaking as a possibility, not a actual threat.
Sources
- P. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. 1996.
- Ian Tillman Shor’s Algorithm on 9th December, 2002
- Evgeny Milanov The RSA Algorithm on 3 June 2009
