April 16, 2019 Quantum Computers – A serious threat to encryption algorithms

To understand the impact of quantum cryptography, we have to understand how cryptography (mainly factoring) works; how it is used in computer security applications and what its impact and limitations are. The fundamental idea of factoring of prime numbers:

Suppose, we have two big prime numbers P and Q and its product PQ  (e.g. 11 * 13 = 143) where P is not equal to Q. How will you find factor P & Q if PQ i.e. 143 is given? Bruteforce!

Now, Instead of 2 digit prime numbers in P and Q, they have approximately 10,000(ten thousand) digits, resulting in 20,000 (twenty thousand) digits for PQ. Now, how will you find the original prime numbers P and Q where PQ has only one set of primes of factors?  (Hint : at least one of the factors has to be less than the square root, so the range is : [2 to square root of PQ])

Bruteforce, sure!  The only problem is it will take the lifetime of the universe to find the prime factors using this approach for such large values. In our current knowledge, there is no classical algorithm that can perform significantly better than bruteforce. In this rather small file, 20 kilobytes (assuming 1 byte per digit), we can never retrieve the original primes. Isn’t this amazing? This asymmetry of multiplication and factoring is the basis of encryption algorithms. We use different keys for encrypting and decrypting data/messages. One famous algorithm is RSA named after Ron Rivest, Adi Shamir, and Adlemen.

Factoring and  RSA
RSA encryption algorithm, for any number less than PQ and coprime to it, we can postulate this identity using Euler’s theorem. Euler’s phi function i.e. phi(PQ) is (p-1) multiplied by (q-1).

E : a random number less than PQ and co-prime to both PQ and phi(PQ) i.e (17)
D : inverse element of D, in the rink of phi(N). i.e. (1/17)

E is the part of linear representation of greatest common divisor of phi of N can be built by extended Euclidean algorithm. So now let’s look at definitions:

Public Key : number E and PQ, we share it widely during encryption. i.e.  [17,143]
Private Key : number D and PQ, we keep it secret in encryption. i.e. [1/17, 143]

M (message) :  Any random string needs to be coprime with PQ, which is likely the case. e.g. 7
Encode : encode with public key, M  to the power E, modulo (PQ). i.e  15
Decode : decode with private key (M to the power E) power D, modulo(PQ) . Since D is inverse of E, it becomes M after decoding. i.e. decoded back to 7

The same concepts are used to create an architecture of security protocols such as HTTPS which uses public key/private key to encrypt/decrypt on both both client and server to make the connection secure on transport layer.

Factoring and Period Finding  
Quantum Shor’s algorithm allows us to effectively search for a period of some period function. This period finding algorithm allows us to factor big composite numbers which is hard for classical computers. We will use QFT (quantum fourier transform) to solve period finding algorithm. QFT is quantum implementation of Fourier Transform which is used in signal processing, linear algebra. In short, Fourier Analysis is a tool to describe the internal frequencies of a function. QFT running on quantum computers is exponentially faster than FFT running on classical computers.

A : random number smaller than PQ and co-prime to it.

Fa : function maps integer number X, all such number less than N and co-prime to it in a group under modulo (N). i.e. A to power X, modulo (N).

R : is the smallest such integers in X which is also the period of function Fa. for e.g. the order of 3 modulo 5  could be these :

• 3 * 3 = 9  , 9 % 5 = 4
• 3 * 3 * 3 = 27,  27 % 5 = 2
• 3 * 3 * 3  * 3= 81, 81 % 5 = 1

The order of X is just the period of the function. Shor’s algorithms allows us to search for periods. The reasons we are so focused on periods in the problem of factors can be reduced to the problem of period finding by using modular arithmetic. We can factor whatever number is needed by computing the order of random integers.

“Then with probability ≥ 1/2, the order S of X is even, and X  to power S/2 is a nontrivial square root of 1 mod N.”

Question : Find the order of 2a (mod 63), and use it to factor 63.?

The order of 2 is 6 as 26= 64 1 (mod 63). A quantum computer can easily use a period finding algorithm to find orders so you don’t have to use bruteforce to find the order. After this step, factors can be identified using the above statement :

23=8 1, so that gcd(63, 8+1) = 9 and gcd(63,8-1) = 7 are the factors of 63.

The period finding algorithm to find order can be briefly described in these steps :

• Create the quantum state
• Measure the last m bits of the state
• Apply the Fourier transform to the first m bits
• Measure the first m bits.

This approach in quantum computing provides a way to attack security algorithm like RSA. This article is one such example. At one side, it could be a serious threat to encryption algorithms but on other side, it also shows the world of Quantum Cryptography that promises to be virtually unbreakable.  We will discuss how to actually implement Shor’s algorithm on real quantum computer in next article.