How does RSA encryption work?
Since we have been discussing quantum computers, one of the main application of them is to break the RSA encryption. But what is this scheme and how does it work? Let's start with how encryption evolved during the history of mankind. In the ancient times one method was to peel in a spiral fashion the bark out of a tree branch and hold onto the stick. With the bark still attached you write the message vertically and after you peel it the message appears garbled up. To decode it you wrap the bark back on the branch and the letters neatly align if you have a branch of the right diameter. This is a rather poor method of hiding the message and better methods were required.
A big improvement in antiquity was the Caesar's cypher in which each letter is substituted by another letter. This method provides a large number of possibilities for encryption, but it has a simple weakness: in any language some words and some letter combinations are very common. For example in the English language the word "the" is the most common, and from it you can easily guess the substitution for the letters T, H, and E. Working in reversed word frequency order you can break this method of encryption relatively easily. The counter method for this was to daily change the substitution method by some sort of algorithm available to both the sender and receiver. One classical example of this was the Enigma machine used by Germany in the second world war.
Now if you do need to change the way the encryption is run after each encrypted message, is there a method which is unbreakable? Indeed it is, and it is based on XOR. In ASCII, each letter is represented by a number and each number has a binary representation of 0 and 1. If you have a one-time use of a cipher key: a sequence of random letters the same length as the message to be sent, you extract the binary representation of the cypher and you do a bit-wise XOR operation between the bits of the text and the bits of the cypher. The operation is reversible and as long as you do not reuse the key to allow the possibility of of the frequency attack explained above, the encryption is unbreakable. So why not use this method all the time and call it a day? Because the management of the keys is horrendous in practice.
The next improvement came from using asymmetric keys. The key idea is that of factorizing a number intro primes. It is trivial to multiply numbers, but there is no good known algorithm to do the factorization. The factorization time of a number made out of the product of two primes is proportional to the square root of the number. Say that we have a 400 digit number. The square root is a 200 digit number. The lifetime of the universe in seconds is an 18 digit number. A computer which factorizes a million tries per second, can only check \(10^{24}\) possibilities. This means that the computer has to run for \(10^{176}\) times the lifetime of the universe to factor a 400 digit number!
So what is the RSA algorithm?
Step 1: pick two large prime numbers p and q and multiply them.
Step 2: multiply (p-1) with (q-1) and find out a small number e relative prime with (p-1) * (q-1). pq and e form the public key you broadcast to the world.
Recall that each letter has a corresponding ASCII code and can be represented as a number.
Step3: the sender wants to encode a number M. Using the public key he computes the encryption of M as: \(M^e\ (mod~pq) = C\) and he sends C to you.
Step 4: you first compute a number d such that \( ed=1 (mod~(p-1)(q-1))\)
Step 5: Finally you compute \(C^d (mod~pq) = M\)
The computations are in general time consuming and the method is used in practice only to encrypt the unbreakable (one-time used) XOR keys.
To break the RSA encryption one needs to be able to factorize the pq product. One way to do it is by Shor's algoritm. In this approach all steps are fast except the key part which is a quantum Fourier transform. In one of the prior posts I discussed a classical embedding of a quantum computer in what amounts to be an analog computer. The speedup in this setting is due to the ability to represent analog signals which are able to fast compute a Fourier transform.
The key question to ask is whether the computational speedup of the computation in a quantum computer is due to quantum mechanics, or is due to the nature of the analog structured being utilized in Shor's algorithm. Supporters of the Many Worlds Interpretation like David Deutsch contend it is quantum mechanics, but my take on it that this assertion is proven false by several concrete realization of analog computational devices. Besides the emulation device created by Brian R La Cour and Granville E Ott, there are other prototype analog devices using optical waves capable of fast performing the key step in Shor's algorithm. The fathers of this line of research are David Ferry and Harris Akis from Arizona State University who published the first paper on this in 2001: Quantum wave processing in Superlattices and Microstructures - a journal unknown to the quantum foundation community.
Now if you do need to change the way the encryption is run after each encrypted message, is there a method which is unbreakable? Indeed it is, and it is based on XOR. In ASCII, each letter is represented by a number and each number has a binary representation of 0 and 1. If you have a one-time use of a cipher key: a sequence of random letters the same length as the message to be sent, you extract the binary representation of the cypher and you do a bit-wise XOR operation between the bits of the text and the bits of the cypher. The operation is reversible and as long as you do not reuse the key to allow the possibility of of the frequency attack explained above, the encryption is unbreakable. So why not use this method all the time and call it a day? Because the management of the keys is horrendous in practice.
The next improvement came from using asymmetric keys. The key idea is that of factorizing a number intro primes. It is trivial to multiply numbers, but there is no good known algorithm to do the factorization. The factorization time of a number made out of the product of two primes is proportional to the square root of the number. Say that we have a 400 digit number. The square root is a 200 digit number. The lifetime of the universe in seconds is an 18 digit number. A computer which factorizes a million tries per second, can only check \(10^{24}\) possibilities. This means that the computer has to run for \(10^{176}\) times the lifetime of the universe to factor a 400 digit number!
So what is the RSA algorithm?
 |
| Adi Shamir, Ron Rivest and Len Adleman |
Step 1: pick two large prime numbers p and q and multiply them.
Step 2: multiply (p-1) with (q-1) and find out a small number e relative prime with (p-1) * (q-1). pq and e form the public key you broadcast to the world.
Recall that each letter has a corresponding ASCII code and can be represented as a number.
Step3: the sender wants to encode a number M. Using the public key he computes the encryption of M as: \(M^e\ (mod~pq) = C\) and he sends C to you.
Step 4: you first compute a number d such that \( ed=1 (mod~(p-1)(q-1))\)
Step 5: Finally you compute \(C^d (mod~pq) = M\)
The computations are in general time consuming and the method is used in practice only to encrypt the unbreakable (one-time used) XOR keys.
To break the RSA encryption one needs to be able to factorize the pq product. One way to do it is by Shor's algoritm. In this approach all steps are fast except the key part which is a quantum Fourier transform. In one of the prior posts I discussed a classical embedding of a quantum computer in what amounts to be an analog computer. The speedup in this setting is due to the ability to represent analog signals which are able to fast compute a Fourier transform.
The key question to ask is whether the computational speedup of the computation in a quantum computer is due to quantum mechanics, or is due to the nature of the analog structured being utilized in Shor's algorithm. Supporters of the Many Worlds Interpretation like David Deutsch contend it is quantum mechanics, but my take on it that this assertion is proven false by several concrete realization of analog computational devices. Besides the emulation device created by Brian R La Cour and Granville E Ott, there are other prototype analog devices using optical waves capable of fast performing the key step in Shor's algorithm. The fathers of this line of research are David Ferry and Harris Akis from Arizona State University who published the first paper on this in 2001: Quantum wave processing in Superlattices and Microstructures - a journal unknown to the quantum foundation community.
Hi Florin,
ReplyDelete"Supporters of the Many Worlds Interpretation like David Deutsch contend it is quantum mechanics"
This would be a strange claim. You can use QM all your life without believing in any interpretation.Quantum calculation procedures do not require any interpretation.So I am surprised that one has to use any interpretation to decide whether the speedup is due to QM or not.
Hi Kashyap,
DeleteI tried to look up the exact quote from Deutsch but I could not find it. But basically the gist was as follows: quantum computers are faster than classical computers and the question is why? Where does the computation speedup takes place? In the many parallel worlds is the answer. Think of a quantum computer as many classical computers working in parallel in each if the many worlds of MWI, and then combining the computation results.
But as it was demonstrated experimentally, quantum computers are nothing but analog computers (vs. digital) and you get massive parallelism from the continuous analog structure regardless if it is a qbit or a pure classical wave and not from hypothetical many worlds.
Breaking RSA comes down on how fast you can do a Fourier transform. I am not sure if it was actually done using classical waves, but if someone succeeded it will be a well guarded secret: all modern commercial transactions are based on RSA.