The Mathematical Beauty Behind RSA

Cryptography is truly a fascinating thing. How data is encrypted and how secret keys are shared… but the most fascinating thing about cryptography is the algorithms behind them. How did people even come up with those?!? Truly amazing!

So… a brief introduction to cryptography before we get our hands dirty with the fascinating mathematics. Cryptography is basically the ART of writing and solving codes. (Okay that was copied straight from google but I couldn’t have said it any better). And then comes the two types; symmetric key cryptography where both parties share the same key for encrypting and decrypting; asymmetric key cryptography where everyone has a pair of keys, public key(which is known by everyone) and the private key(which is… well… private). And one of these keys is used to encrypt and the other is used to decrypt. If you’re new to cryptography… then let’s take the classic Bob and Alice example. If Bob wants to send something secret to Alice, then Bob encrypts the message using Alice’s public key, and Alice can then decrypt is using her own private key. So that’s basically the basics of cryptography.

Today’s guest of honor, RSA (named after it’s founders, of course, Rivest–Shamir–Adleman), is an asymmetric key algorithm. Before getting deep into RSA, what is the mathematical basis of asymmetric key cryptography? Trapdoor functions.

Now, what’s a trapdoor function? Well… it’s a function where it is super easy to go from x to y, but very very hard to go back from y to x. But… there is a “trapdoor” which is like a secret passageway to easily get from y to x. So how does this help asymmetric key cryptography? Basically, if x is your private key, it’s really really easy for you to generate your public key y using the trapdoor function, but anyone who knows your public key shouldn’t be able to know your private key. And it works out that way by using a trapdoor function (and keeping the trap door sealed of course!).

Now let’s really get into RSA. RSA uses modular exponentiation for encryption and decryption. Using this method for cryptography was actually an idea of British mathematician and cryptographer Clifford Cocks. Now how does that work with RSA? Basically, we have a pair of values e and n which will be our public key and another pair d and n as the private key. (The n in both pairs is the same number).

For encryption, first, we convert the message into an integer m, then raise to the power e and take modulus n. So basically if the result of encryption is c, then c = me (mod n).

For decrypting take c, raise to the power d, and take modulus n. So basically m = cd (mod n). Here, d will be the trapdoor that helps to decrypt the message.

What happens here is, raising to the power d reverses the process of raising to the power e, which looks like this m = (me)d (mod n). Further simplified, m = med (mod n). And we have to find e and d which satisfies this. Now that we have established the method, we need to get the values for e,d, and n.

The basis of finding the value n is prime factorization. Prime factorization is writing a non-prime whole number as products of primes. And the prime factorization of any number is unique. For example, 10 = 2 * 5 and 12 = 2 * 2 * 5. And it turns out prime factorization is very hard to do. It seems quite easy by looking at the examples that I have, but actually, when the numbers become larger and larger, it becomes harder to find its prime factors. So… if we have two large prime numbers p and q, it is easy to calculate n=pq, but hard to factorize n into p and q.

So as step one of the RSA algorithm, take two large prime numbers p and q (of approximately 150 digits… yes very large indeed). Calculate n = p*q which will result in a value n with more than 300 digits! (it would take years and years for a computer to factorize this into p and q.) The calculated n will be part of both the public AND private key. And the initial primes p and q should be kept secret.

Step 2 is where Swiss mathematician Leonhard Euler comes in. Euler defined the 𝜱 function (Or the Euler’s totient) where 𝜱(n) gives the number of positive integers less than or equal to n that are relatively prime to n (numbers that do not share any common factors with n). Now calculating the 𝜱 function for a number is quite hard, EXCEPT in one special case. When n is prime! Then, any number less than or equal to n except 1, does not have any common factors with n (remember, n is a prime now). Therefore 𝜱(n) = n — 1. Another nice feature of the 𝜱 function is that it is multiplicative which basically means 𝜱(p*q) = 𝜱(p) * 𝜱(q).

So now you’re probably seeing where I am going with this. If we have any number n with prime products p and q, we can easily compute 𝜱(n).

𝜱(n) = 𝜱(p*q) = 𝜱(p) * 𝜱(q) = (p-1)*(q-1)

How cool is that?!

So now step 3. How do we use this awesome Euler’s totient to generate our keys? For this, we use Euler’s theorem, which gives the relationship between the 𝜱 function and modular exponentiation. So what does the Euler’s theorem state? Simply the following: m𝜱(n) = 1 (mod n) where m and n are relatively prime. To use Euler’s theorem for RSA, let’s do some modifications to the equation.

First, let’s multiply 𝜱(n) by some integer k. Then mk*𝜱(n) = 1k (mod n). We know 1 raised to any power is always 1. So the above result further simplified gives mk*𝜱(n) = 1 (mod n).

Then, let’s multiply both sides by m, which will give m*mk*𝜱(n) = m*1 (mod n). This can be further simplified as mk*𝜱(n)+1 = m (mod n).

Now doesn’t this equation look familiar? No? What if I substitute k = e and 𝜱(n)+1 = d? Then we have med = m (mod n). Aha! Now isn’t this the equation we wanted in the first place? Yes, it IS the equation I mentioned a few paragraphs ago!

So it seems like we have found our e and d! For e, take any number between 1 and 𝜱(n), AND relatively prime to 𝜱(n). Now, this e with the n we found earlier is the public key.

Take d, such that e*d = k*𝜱(n) + 1 (this is the result of what we discovered from Euler’s theorem, in case you’re wondering where this came from). We can also write the same equation as e*d = 1 mod (𝜱(n)) (because what we need is e*d to have a remainder of 1 when divided by 𝜱(n)). Now this d, with the n is the private key.

And the value of d should be kept SECRET along with p and q. As we figured out along the way, d depends on 𝜱(n) which in turn depends on the prime factorization of n (which is, p*q). And since n is very very VERY large it is almost impossible to find it’s prime factors even by a computer for many MANY years. Therefore, we can be sure no one else can decrypt a message meant for you if you keep your d,p, and q well hidden.

So let’s see all that we found out in an example.

Let’s take p = 3 and q = 11 (I know I said p and q should have like 150 digits but forget that for this example)

Then n = 3*11 = 33

𝜱(33) = (3–1)*(11–1) = 2*10 = 20

Now take e between 1 and 𝜱(33) and relatively prime to 𝜱(33). So let’s take e = 7.

Now find d such that e*d = 1 mod (𝜱(33)). So we’ll take d = 3 (because 1 = 3*7 (mod 20) ).

Now we have our public and private keys.

Public key -> 7,33

Private key -> 3,33

Now let’s see encryption and decryption in action using these keys.

Imagine that your message is mapped to integer 2. So m = 2

Now let’s encrypt m using e and n : c = me (mod n) = 27 (mod 33) = 29

Now let’s decrypt c using d and n : m = cd (mod n) = 293 (mod 33) = 2

Viola! So it works! And now we know HOW it works as well.

On a final note, I mentioned at the beginning that RSA was named after its founders Rivest, Shamir, and Adleman. But… throughout the mathematical explanation, you may have noticed that I mentioned some other names. If you’re wondering what that’s all about… it turns out that when this method was first published, it had been CLASSIFIED! (yup, locked away in some secret place like all those private keys). But Rivest, Shamir, and Adleman have RE-DISCOVERED this method later in 1977 (re-discovered independently, not stolen!) and named it after themselves.

So that’s the mathematical beauty behind RSA! I hope you got an idea about the mathematics of RSA without being too confused.

image courtesy: google images