Simplifying Shor’s Method
Simplifying Shor’s Method
Our existing methods of key exchange and public key encryption are not secure within an era of quantum computers. Why? Because the hard problems they are based on, do not become hard problems anymore with quantum computers. For RSA, we create a public modulus (N) and which is the multiplication of two prime numbers (P and Q). If N is large enough (such as with 2,048 bits) and if random prime numbers are used, it is not computationally feasible to factor it (as it would take the energy to boil all the oceans on the planet, and still take billions and billions of years to crack a single key).
Shor imagined two sine waves, one of length P and the other of length Q. Assuming that P and Q are co-prime (that they do not share a common factor), he proposed a question of finding the point at which the harmony of P overlaps with Q, and then repeats itself. For this, we can project to a point N, and then find the point at which the phase of P and Q will be 0. In a quantum computer, this phase checking is a fairly easy task, and we can thus factorize N in terms of P and Q. All we need to do is to change the length of P and Q and find the point at which we determine they are in phase at point N.
So let’s say I pick P=2 and Q=3 (which are two prime numbers), and where I generate two sine waves with a length of 2 and a length of 3. When I plot the two together, you can see that the point at which they are in-phase is at 6 [link]:
And here are two waves of lengths 11 and 13 [here] and we see they are in-phase at 143 (which is 11x13):
In this way, we crack RSA, but generating two waves of different lengths, and then looking at the point at which they synchronize. The hard problem that we had before, has just become a relatively easy one within a quantum computer.
Conclusions
We must depreciate our existing key exchange and digital signature methods, and more toward a post-quantum cryptography era. Luckily NIST has defined a number of methods for standardization for key exchange/public key encryption and digital signatures. The key main methods going forward is Kyber (for key exchange/public key encryption) and Dilithium (for digital signatures). You can learn more here: