Algorithms Explained: RSA Encryption
RSA (Rivest-Shamir-Adleman) algorithm is one of the many algorithms that allow you to transmit data securely over a potentially insecure medium. The basic working principle of the algorithm is illustrated below.
First, the receiver generates a public key and a private key, and sends the public key to the sender. Then, the sender encrypts the message with the received public key, and sends it back to the receiver. The receiver then decrypts the message using the private key, and the original message is retrieved.
As we can see from the diagram above, the raw message never gets transmitted over the public domain, which is where attackers will be eavesdropping. The private key must be kept securely at all times, so that the message cannot be decrpyted by a third party.
The idea behind this algorithm is that the message is computationally expensive to decode without the private key, and even if the public key is compromised, it is also computationally expensive to derive the private key from the public key. At this point, you might be wondering what the relationship between the public and private key is, and how the private key is able to decrypt messages encrypted with the public key. The bottom line idea is that such operation is possible as both keys are derived from a common set of numbers, but let’s dig into detail what this actually means.
The math behind the RSA algorithm:
We first select two prime numbers, p and q. These two numbers will be the common building blocks for both the public and private keys. Using these two numbers, we derive four variables. Firstly, we have n, the product of the two numbers.
We then calculate the totient of n, φ(n). In our case, this can be calculated from a simple function:
We then select a new variable, e, which fulfills the following conditions:
Finally, we select a value for a new variable d, which has the following property:
Now, our public key will consist of (n,e) and our private key (d,e). Encrypting the message with our key is fairly simple. Let’s say our message is m and the encrypted message is c. Then, m and c have the following relationship:
Encryption:
Decryption:
Example:
Let’s say we choose p=3, q=5. Then, we would have our n variable to be:
Then, we calculate the totient, φ(n):
We can then pick a value for e that meets the criteria mentioned above. Let’s pick 17, as it meets the criteria:
Then we can pick a value for d, that satisfies the above criterion. we can pick 53, as:
Now we have the public key consisted of (n, e) to be (77,17), and the public key consisted of (n,d) to be (77,53). Let’s say we want to send a payload message of the number 6.
We then encrypt the message:
And decrypting gives us:
