The Math behind RSA — I

Cryptography is a field in Cyber Security that deals with transmitting data securely through various schemes and protocols. In simple words, it makes sure that the message you send to someone is only accessible by them. Although there are many cryptographic techniques to secure data, RSA is one of the oldest and most primitive cryptographic schemes and yet is used in many places even today.

RSA (Rivest, Shamir, Adleman) is one of the best examples of how number theory goes hand in hand with security. Before diving deep into what RSA is, let us first explore a bit about the various systems in cryptography.

Cryptosystems are classified into two types broadly based on the encryption and decryption mechanism:

1. Symmetric Cryptography  — The sender and the receiver use the same key for encryption and decryption respectively.
2. Asymmetric Cryptography  — The sender and the receiver use two different keys (public and private key) for encryption and decryption.

Both of the above mentioned cryptosystems are widely in use even today and both of them have their own merits and vices. For now, let us focus on asymmetric cryptography. In asymmetric cryptosystems, we have two keys, the public key and the private key. As the name suggests, the public key is available to anyone and is used to encrypt data while, the private key is only accessible by the receiver and is necessary to decrypt the message.

The pressing question at this point would be, “How can we map a particular public key to a private key?”. Well, this is where mathematics plays a major role. Through a series of mathematical steps, we can generate the public and the private key for the message, which can then be sent to the receiver to access the message. Another interesting point to note is that, even though the two keys are related to each other in a mathematical aspect, knowing one key provides no knowledge of the other one, without additional information. So, even though a third person knows the public key, they can’t find the private key, making it very secure.

Now that we understand how asymmetric cryptography works, let’s understand the implementation of RSA.

Let’s say you Mr. A, want to send you’re Wi-Fi password — “buzz1ng@!”, to you’re friend Mr. B, securely using RSA so that others can’t get their hands on the password. This is how you would go about it:

1. Since, we need to perform mathematical operations, the text needs to be converted into numbers. Let us just convert the characters to their ascii values and use that for now (https://www.dcode.fr/ascii-code). Make sure to remove the spaces between the numbers in the output.

2. The message (m) is 98117122122491101036433.

3. The next step is to generate two prime numbers. In an ideal situation, we need to pick very large prime numbers for it to actually be secure but just for demonstration, let us pick two relatively small prime numbers p and q.

4. Let p = 1045352245208699 and

q = 792433396102379

5. The individual values of p and q should never be revealed instead, let us generate the modulus n using the formula p*q. (When the prime values are very big, it would be impossible to find p and q just from n since factoring n would be very difficult with the current computing power)

6. n = 828372029793976194824025394921

7. Then, we need to pick the value of the public exponent (e). It is generally taken to be 65537. With these values, we can generate the cipher text

c = m ^ e mod n.

8. Hence, the cipher text would be c = 103326721344696406267987036007 and the public key would be the pair (n,e) or (828372029793976194824025394921,65537)

With this we have reached the end of the encryption process. Now, Mr. B has the values of (c,n,e) and has to somehow figure out the password with just this information and the private key. But then what is the private key?

For now, let us just assume that you have already informed Mr. B of the private key (d) = 530566616150142173292082492385. All that’s left now, is to decrypt the cipher text.

1. To get the original message (m) back, we use the formula

m = c ^ d mod n.

2. This would give us the value of m = 98117122122491101036433.

3. Voila!! As you can see this is the same number we got when we converted the text to ascii.

4. To verify this, covert the number back to text (https://www.dcode.fr/ascii-code) and that reveals the password as “ buzz1ng@! ”.

Now, Mr. B is happy getting access to you’re Wi-Fi and you are relieved that nobody else got to know the password. But, as fate would have it, another friend of yours Mr. X, who knows hacking, somehow got to know the ciphertext and the public key. But you let it slide, thinking that the password is safe as long as Mr. X doesn’t know the private key. The question is, “ is your password really safe though or will Mr. X be able to access your Wi-Fi? ”. To find the answer to this question, stay tuned for the next part in this series.