The Math behind RSA — II

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.

In part-1 of this series, we looked at some of the powerful concepts in mathematics that allowed Mr. A to send his Wi-Fi password to Mr. B securely. While doing so, we skipped through the part where Mr. A generates the private key to send it to Mr. B. In addition to this, Mr. X knows your public key. Will that be a problem? Let’s find out.

The private key has to be generated by the sender and somehow given securely to the receiver in order to make the RSA scheme work. How would Mr. A have generated the private key ‘530566616150142173292082492385' ?

In order to generate the private key first, we are going to use the Euler’s Totient Function to compute the number of integers less than n that are relatively prime to n. If you remember from the previous article, n is the product of two prime numbers. Let us assume that T(n) represents the totient function of a number n. Just to give you an intuition, T(5) is the count of the number of positive integers relatively prime to n which in this case is 4 (Since 1,2,3,4 are relatively prime to 5). From this, we can come up with a generalization that T(p) when p is prime is (p-1).

Coming back to our case, n is the product of two prime numbers. What would the totient function of such a number be?

Let us consider an example for such a case. 15 is the product of two primes namely 3 and 5. The numbers that are relatively prime to 15 are 1, 2, 4, 7, 8, 11, 13 and 14. Hence, T(15) = 8 from the above example. What is the generalized representation to this?

To understand the above generalization, let us go back to the case of 15. Out of the 15 numbers, we remove 15 from the list of relatively prime numbers which leaves us with 14 or (pq-1) numbers. Out of these (pq-1) integers, there are 4(p-1) multiples of 3(p) and 2(q-1) multiples of 5(p) between 1 and 14. Hence, we need to eliminate those numbers as well which leaves us with (pq-1)-(p-1)-(q-1) giving us the final value of the totient function on the product of two primes as (p-1)(q-1).

Now that we have this knowledge, let us proceed with finding out the value of d, the private key. d is the multiplicative inverse to e which means,

The important question now is, how do we find the multiplicative inverse of e? Well, this is where we make use of the Extended Euclidean Algorithm. Hence, the value of d that Mr. A calculated turned out to be 530566616150142173292082492385.

Let’s get back to the story now. One day, Mr. A realized that there was a lot of usage on his network that was unaccounted for. Then, he realized that he didn’t send the public key and the ciphertext through a secure channel since he thought that without the private key, nobody could get access to the credentials. But that is where he missed a trick and Mr. X acted upon it.

As we have seen earlier, in order to compute the private key, all we need is p, q and e. In this case, the value of n is relatively small and hence can be factorized into two primes easily using online tools or special factoring algorithms. Now that Mr. X has access to the values of p, q and e, he can just compute T(n) and as an extension, the value of d which would help reveal the password.

Now that Mr. A knows how Mr. X got access to his credentials, he decides to take it up as a challenge to find more secure ways to transmit his message using RSA while Mr. X was just getting started. So, what happens next? Will Mr. A manage to securely send his new password to Mr. B or will Mr. X display his hacking prowess? Stay tuned for the next part in this series to find the answer to that!