Written By: Alex Liao
A classical computer uses a binary, 1s and 0s, for computational work; whereas a quantum computer uses qubits, which could be any subatomic particle such as a proton, neutron, electron etc. Subatomic particles have a property called “spin”, which is an intrinsic property that is purely quantum mechanical. Spin behaves like angular momentum, which is essentially magnetic moment whereby fermions, subatomic particles with spin, form alignment in the presence of a magnetic field. It is important to note that fermions do not physically spin, it is simply a quantum property that behaves like angular momentum. Most importantly, spin is quantized, meaning it only has discrete values +½ and -½, which indicate spin up and spin down respectively. Spin up and down mimic the binary system used in classical computers, representing 1s and 0s respectively,
A qubit has the ability to exist in a state of superposition, whereby subatomic particles exist in both states, spin up and down, simultaneously. This is what allows the immense computational power of a quantum computer. Essentially, one classical bit could only contain one unit of data, either a 1 or 0; in contrast, one qubit could contain the data of a 1 and 0 at the same time. If you increase the number of qubits to 2, it could represent 2^2 units of data, whereas 2 bits could still only contain 1 unit of data. As the number of qubits increase, the amount of equivalent classical information contained in N qubits increases exponentially equivalent to 2^N classical bits. In a fully entangled state, roughly 300 perfect qubits, we would theoretically have 2^300 classical bits, which is as many particles as there are in the universe.
The problem with quantum computers lies in the property that makes it unparalleled to current technology. Even though quantum superposition allows us to compute every known feasible possibility, this state “collapses” immediately after observation, meaning it falls into a deterministic reality of one singular probability; essentially, we could not measure a superposition, we could only measure one basis state, which means all information about the other states is lost. This is the problem that researchers have been trying to solve for the past decade, to develop an algorithm that accurately pinpoints the desired state.
It is important to understand that quantum computers are not a complete replacement of classical computers. Quantum computers are not universally faster, but rather they are only faster in specific calculations that involve a large number of operations such as trial and error or decryption; they are not practical in simple logic computations such as video streaming, simple numerical calculations, or in general, browsing the internet.
What is RSA Encryption?
RSA (Rivest-Shamir-Adleman) encryption is an asymmetric encryption algorithm that is used in most digital services we use. RSA encryption uses two keys, a public key that is accessible to all users and is used to encrypt data, and a private key that is mathematically linked to the public key but instead is only known to the creator and is used to decrypt data.
A public key is generated by first selecting two extremely large prime numbers, “p” and “q”, hundreds of digits long. The two prime numbers are then multiplied to get another number, “N”, that becomes the modulus in both the public and private key. We then use Euler’s Totient Function to find the co prime numbers of N, “ɸ(N)”. The second integer, “e”, needed for the public key is generated based on ɸ(N) whereby it has to be within 1 and ɸ(N), as well as be a co prime of both N and ɸ(N). The second integer, “d”, needed for the private key is such that d multiplied by e modulus ɸ(N) is equal to 1. Thus the public and private key is represented by [e, N] and [d, N] respectively. Example:
p = 2
q = 7
N = 2 * 7 = 14
ɸ(N) = (p - 1)(q - 1) = (2 - 1)(7 - 1) = 1 * 6 = 6
∴ e = 5
∴ de (mod ɸ(N)) = 1
=> 5d (mod 6) = 1
∴ d = 11
Public key: [5, 14]
Private key: [11, 14]
How a Quantum Computer breaks RSA Encryption
A quantum computer’s immense computational capacity enables it to factor the product of two primes much faster than any supercomputer we have currently. RSA encryption could be broken as such:
Say for this example the modulus of the public and private key were computed such that:
p = 7
q = 11
N = 77
The quantum computer has no information N’s two prime factors; however, it could compute it through this algorithm,
where “g” is a random integer. If g was raised to a power of “r”, it would eventually equal a multiple of N + 1. For this example, we set g as 8. If we compute this we would find that r is equal to 10.
Once we have r, we could rearrange the equation as such:
In our example, mN would equal to 32769 multiplied by 32767. We could then use Euclid’s algorithm to find the greatest common factor of N and either (g^r/2+ 1) or (g^r/2- 1). In our case, 77 and 32769.
32769/77 = 425 R 44
77/44 = 1 R 33
44/33 = 1 R 11
33/11 = 3 R 0
When the remainder is 0, the divisor would be the greatest common factor of N, 11. We could then find N’s other prime factor by simply dividing N by 11, giving us 7.
A quantum computer doesn’t compute all these steps, in fact it only computes step 2, finding the exponent r. If we continued to compute all the remainders from the previous table, we would notice that the remainders cycle.
This is because any number to the power of 0 gives a remainder of 1, 8^0/77 = 1. It is also because the remainders cycle that r could be obtained simply by finding the number of terms between any two like remainders.
To find r using a quantum computer, we would need two sets of qubits, one empty and the other storing numbers up to 10^1234 . We would then raise g to the power of the first set of qubits and divide them by N, storing the remainders in the empty set. Through this process, we have entangled the two sets and thus we now could measure the remainders to find terms with like remainders. The final step would be to exclude the remainder superposition, leaving us with a periodic superposition of states differing by r that we would apply a quantum fourier transform on to obtain states containing 1/r where r is simply the inverse.
Comments