Shor’s Algorithm — how quantum computing can break cryptography
Quantum Mechanics is very interesting — due to the unique environments qubits operate in, it can make computers that are much more sophisticated than our current classical computers. In this article, we explore how quantum computing can crack our current cryptography method, focusing on RSA, using Shor’s algorithm.
Current Cryptography Methods
One of the current cryptographic methods we use is RSA (Rivest-Shamir-Adleman). The RSA algorithm involves four steps: key generation, distribution, encryption and decryption. The basic principle behind RSA is the observation that it is practical to find three very large positive integers e, d and n so that with modular exponentiation for all integers m (with 0 ≤ m < n):
and it can be extremely hard to find d without knowing the other variables. RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. The intention is that messages encrypted with the public key can only be decrypted using the private key, to be solved in a reasonable amount of time. The public keys are the integers n and e, and the private key is d. m represents the message.
The key generation for RSA works in the following way:
1.Choose two large prime numbers p and q. To make factoring harder, p and q should be chosen at random, and be similar in magnitude, but differ in length (according to the original paper written to the inventors — refer to the Sources section). Prime integers can be efficiently found using a primality test. p and q should be kept secret.
2. Calculate n = pq. n is released as part of the public key.
3. Compute λ(n), where λ is Charmichael’s totient function (more here). In this case, λ(n) = lcm (p-1, q-1). lcm is the Lowest Common Multiple, which can be calculated by :
λ(n) is kept secret.
4. Choose any integer e such that 1 < e < λ(n) and gcd(e, λ(n) = 1 — e and λ(n) are co-prime. The most commonly chosen value for e is 2¹⁶ + 1= 65537. The smallest possible value for e is 3, but this value has been shown to be less secure in some settings (Refer to this paper). e is released as part of the public key.
5. Calculate d as:
d can be seen as the modular multiplicative inverse of e modulo λ(n). d is part of the private key.
The public key consists of the modulus n and the encryption exponent e. The private key consists of the decryption exponent d. p, q and λ(n) must also be kept secret since they can be used to calculate d. They can be discarded after d has been computed.
Note: in the original RSA paper, the Euler totient function φ(n) = (p-1)(q-1) is used instead of λ(n) for calculating the private exponent d.
The encryption function for RSA can be considered
where m is the plaintext message.
The decryption function is
where c is the encrypted cyphertext.
RSA relies on factoring being impossible for large enough integers since the best-known classical algorithm requires a really long time to factor the product of two primes. Shor’s algorithm, an application of quantum mechanics, can break RSA.
Shor’s Algorithm
Shor’s algorithm is famous for factoring integers in polynomial time (just a fancy method of saying “a reasonable amount of time”). Shor’s algorithm solves the problem of period finding.
Let’s take a look at the periodic function
where a and N are positive integers, a < N and they have no common factors. the period, P, is the smallest integer so that
The goal of Shor’s algorithm is to find r. Shor’s solution was to use quantum phase estimation on the unitary operator:
To put this in practice, let’s calculate what an eigenstate of U might look like (the eigenstate is the eigenvector corresponding to eigenvalues, which shows the possible values of the observable quantity on the quantum state vector. More about it here). If we started in the state |1⟩, we can see that each successive application of U will multiply the state of our register by a (mod N), and after r applications, we will arrive at the state |1⟩ again. For example, with a = 3and N = 35:
So the superposition of the states in this cycle (|u₀⟩) would be an eigenstate of U. If we take a look at the case in which the phase of the kth state is proportional to k:
Notice the r in the eigenvalue: this is necessary to make sure the phase differences between the r computational basis states are equal. If we multiply an integer, s, by this phase difference, the eigenvalue will be:
Now, we have a unique eigenstate for each integer value of s where 0 ≤ s ≤ r — 1.
If we sum up all of the eigenstates, this conveniently cancels out all computational basis states except |1⟩.
Since the state |1⟩ is a superposition of these eigenstates, if we apply quantum phase estimation on U using the state |1⟩, we will measure a phase:
Where s is a random integer between 0 and r — 1. Finally, by using the continued fractions algorithm on ϕ.
Now, we have the period of f(x). If the period is even, if we can check :
where N is the number you are trying to factor, m, is a random positive integer that m < N, and P is the period.
If this is true, then the answer to:
where gcd is the greatest common divisor, is a non-trivial prime factor of N.
Shor’s Algorithm is very useful for breaking cryptographic methods. However, this leads to a problem — current methods won’t be as strong if quantum computers are established more commonly. Currently, researchers are looking into post-quantum cryptography — methods that can be created on a classical computer, but are difficult to be cracked on quantum computers.
Thank you so much for reading until the very end! This is my LinkedIn. Please also subscribe to my newsletter, I’m publishing my activities every month!
— Sources —
https://www.amarchenkova.com/posts/break-rsa-encryption-with-this-one-weird-trick
