Let say if Alice would like to send a secret message to Bob, she may want to first encrypt the message before sending it. Modern cryptographic techniques all use some secret keys to encrypt and decrypt a message. For example, we may generate a random sequence with a predefined seed (the key) and take the bitwise sum of the random sequence and the message as the encrypted message (also known as ciphertext). At the other end of communication, as long as Bob also has the key (the original seed), he can regenerate the random sequence and decipher the message as the bitwise sum of the random sequence and the ciphertext.
The above scenario is an example of symmetric cryptography. The problem is that Alice has to share with Bob the secret key somehow. And if some malicious Eve manages to get the secret key, she can eavesdrop the message without being caught.
Public key cryptography
To avoid the above problem, it is much better if we have an `”asymmetric” system, where the encryption and decryption keys are different. Alice will then encrypt her message with the encryption key (the public key) and Bob will decipher the ciphertext with the decryption key (the secret key). Basically, when Alice needs to send a secret message to Bob, she will first ask Bob to send her his public key. After receiving Bob’s public key, Alice will encrypt the message with his key. And only Bob can decipher the message with his secret key. Therefore, this is also called public key cryptography.
For the above to work, we need to make sure that while it is easy to compute the original message from the ciphertext with the decryption key, it is computationally infeasible (extremely expensive) to decipher the message without the key. Moreover, we need to make sure that we cannot derive the secret key from the public key, the ciphertext, or the combined information.
RSA encryption algorithm
RSA encryption algorithm considers the following math problem
where , , are the original message, encryption key, and ciphertext, respectively, and is some very large integer. In plain English, the ciphertext is the remainder of divided by .
Note that while it is easy to compute the from given and . It is very difficulty to compute the inverse for large and . Now, the question is what should the secret key be and what should we do with so that we can solve given . Actually it is not even clear from the equation alone that the inverse exists or is unique.
Euler’s theorem luckily comes to the rescue. It states that
for any integer that is coprime with . above is the Euler totient’s function and it is the number of positive integers that are both coprime and smaller than . For example, if is prime and thus does not share any factors with any numbers smaller than it, then is simply .
From Euler’s theorem, for any arbitrary positive integer , we immediately have
So if we pick , we have
. In plain English, we can decipher the message as the remainder of divided by .
Let’s borrow an numerical example from this very nice video. In particular, we will construct as the product two prime numbers and . Let’s choose and , then and . Pick and . Note that , which is an integer as desired.
So to transmit a secret message, Bob should first send the public key and to Alice. For example, Alice would like to send the message to Bob. The ciphertext should then be computed as the remainder of divided by , which gives us . And when Bob received , he should decipher the message as the remainder of divided by . This gives us back the original message of .
A really careful reader here may catch a “bug” of our argument above. Note that Euler’s theorem only hold for message which is coprime with . Since , not every integer smaller than is coprime with it. This suggests that we should limit our message only to a subset of positive integers smaller than . However, it turns out that this is not necessary. A complete proof for RSA can be shown using a combination of Chinese remainder theorem and Fermat’s little theorem (a special case of Euler’s theorem). But that would be another story.