This post is a sequel to the previous post on this topic: Behind HTTPS: RSA Encryption – The Basics. I hope you remember the basics mentioned in that post. You may want to revisit it, if you like. In this post, however, we will discuss the algorithm used by RSA in a bit detail. So lets get started.
Here is the illustration of RSA from the previous post:
Receiver Generates two keys: PuK = Public Key PrK = Private Key Sender asks for receiver's public key. At Sender: C = E(M, PuK) Send C to Receiver. At Receiver: M = D(C, PrK)
We will discuss the RSA algorithm in three different parts:
Generating the Key Pair:
Generate two big prime numbers, p and q, pseudo randomly. These numbers are of the order of magnitude of 2^1024 in practice but we’ll choose p = 23 and q = 43, just to be able to demonstrate here otherwise this post would be filled with big numbers only 😛 .
n = p * q = 23 * 43 = 989. m = (p - 1) * (q - 1) = 22 * 42 = 924.
Now, find a number e that is coprime with m and less than m, i. e.:
find e such that gcd(e, m) = 1
Generally, in practice we pick e = 65537, which is a prime by itself, if it’s coprime with m. But, here we’ll pick e = 5(You can see that gcd(5, 924) = 1).
Now, we are going to pick one final number 🙂 and it’s called d and we pick d such that:
de = 1(mod m)
i.e. we pick d such that d multiplied by e gives remainder 1 when divided by m. This is a simple problem of modular arithmetic(for those interested).
So, we pick d = 185:
185 * 5 = 925 925 % 924 = 1
So, we have got 4 numbers:
e = 5 n = 989 m = 924 d = 185
So, the keys are:
Public Key = PuK = (e, n) = (5, 989) Private Key = PrK = (d, n) = (185, 989)
So, our prime numbers don’t appear anywhere and it is very difficult and expensive for the computer to try and find out p and q and thus find d and m, in practice(Remember p and q are very large in practice and so is n – so factoring them will take ages 😛 ).
During Encryption,the receiver generates the key pair and the sender asks for it and sends the encrypted message. The sender breaks the message into chunks and then encrypts it. So, lets try and encrypt “KTREAT”, we’ll use ASCII values as the values of the characters:
For each character m, the cipher C = power(m, e) mod n K = 75, C1 = 75 ^ 5(mod 989) = 715 T = 84, C2 = 84 ^ 5(mod 989) = 398 R = 82, C3 = 82 ^ 5(mod 989) = 395 E = 69, C4 = 69 ^ 5(mod 989) = 46 A = 65, C5 = 65 ^ 5(mod 989) = 770 T = 84, C6 = 84 ^ 5(mod 989) = 398
These ciphers C1 through C6 are what is sent to the receiver.
So, having received the ciphers sent from the sender, the receiver decrypts them using the private key(which was not made public) as follows(the calculations below were performed using a C program, by the way, so don’t ask me what calculator I used 😛 . You can also calculate these using a very good tool called Microsoft Math, really awesome.):
For each cipher C, message m = power(c, d) mod n C1 = 715, m1 = 715 ^ 185(mod n) = 75 = K C2 = 398, m2 = 398 ^ 185(mod n) = 84 = T C3 = 395, m3 = 395 ^ 185(mod n) = 82 = R C4 = 46, m4 = 46 ^ 185(mod n) = 69 = E C5 = 770, m1 = 770 ^ 185(mod n) = 65 = A C6 = 398, m1 = 398 ^ 185(mod n) = 84 = T
So, there you go, we’ve got our original message – KTREAT back. And that’s all for today and RSA algorithm. Thanks for reading, hope you liked it. Comment if you have any.