What I’m going to cover in this article
- History of RSA
- What is RSA?
- Mathematical theorems that are needed (Euler’s Phi function, Modular Arithmetic, Modular Multiplicative Inverse, Fermat’s Little Theorem/Euler’s Theorem)
- How does RSA work?
- Encrypting and Decrypting with RSA
- Why does RSA work?
- Breaking of RSA (Very Brief)
- Problems with RSA
- Extra Resources
Pre-requisites
You should understand what cryptography means specifically what asymmetric cryptography means.
History of RSA
RSA actually stands for Rivest, Shamir, Adleman the three developers of RSA. It was developed in 1977 just an year after Diffie-Hellman cryptographic algorithm. Though people say Rivest, Shamir & Adleman weren’t the first to develop RSA & that it was actually the Britishers during WW2 but they kept it a secret. Whatever the case maybe they did give us an awesome cryptographic algorithm.
What is RSA?
RSA is an asymmetric cryptographic algorithm.
Yes but what does that mean?
If you know a bit about asymmetric cryptography you know to converse securely, someone will encrypt a message using your public key and you’ll decrypt it using your private key. RSA is just an algorithm used to generate those private and public keys.
There are many cryptographic algorithms these days and RSA is just one of them. ECC (Elliptic Curve Cryptography) is another algo which is more popular these days but nonetheless RSA is still used. I’m not going to dive into what actually cryptography is and what are the various types of cryptography, that’s a topic for another day.
Mathematical theorems that are needed to understand RSA
If you want to understand how RSA works it’s essential to understand some basic mathematical theorems (they are easy af).
Euler’s Phi Function / Euler’s totient Function
Euler’s Phi Function gives you the number of numbers from 1 to n that are relatively prime to n. It’s usually denoted with Φ(n) or φ(n).
I’m not going to dive deep into this because it’s not necessary, what we need is to how to calculate Euler’s Phi for a prime number.
If n is a prime number then the formula for calculating φ(n) is simple —
φ(n) = (n-1)
Also one important property of Euler’s Phi is that —
φ(x₁ * x₂ * x₃,…,xₙ) = (x₁-1)(x₂-1)(x₃–1)…(xₙ-1)
given that x₁, x₂, x₃,…,xₙ are all prime numbers
Modular Arithmetic
If you’ve ever been introduced to arithmetic operations in programming you must’ve used the symbol (%) what’s called a modulo, it returns the remainder of the two operands. For eg —
10 % 3 = 1
But this isn’t how we write this in mathematics, we write it as
10 ≡ 1 mod 3
43 ≡ 7 mod 12
Modular Multiplicative Inverse
So basically imagine an equation 2 * y ≡ 1 mod 11, “y” here is the modular multiplicative inverse of 2 under 11 or 2 mod 11 as when 2 * y is divided by 11 it yields a remainder of 1.
The best way to solve this problem is EEA (Euclid’s Extended Algorithm)
So let’s solve the problem -
There’ll be total of 7 variables A, B, Q, R, T₁, T₂ & T
A = Dividend, B = Divisor, R = Remainder, Q = Quotient, T₁ = 0 (initially),
T₂ = 1 (initially) & T will be calculated by a formula given as T = T₁ - T₂ x Q
Do it once and then substitute the value of B to A, R to B, T₂ to T₁ & T to T₂ and do it again until you encounter a situation where you won’t be able to move ahead with the Algo and at that point of time whatever is the value of T₁ will be your modular multiplicative inverse.
You’ll understand it much better after an example so let’s see one —
Q. What’s the multiplicative inverse of 2 mod 11?
Let’s put in the values -
A = 11, B = 2, after calculating Q & R the values will be 5 & 1 respectively
T = T₁ - T₂ x Q ⇒ T = 0 – 1x5 = -5 (initially T₁ = 0 & T₂ = 1)
Now substituting the value A = B = 2, B = R = 1, T₁ = T₂ = 1, T₂ = T = -5
after calculating the new Q = 2, R = 0 & T = 1 - (-5)x2 = 10
Now substituting the values again A = 1, B = 0, T₁ = -5 & T₂ = 10
Now we can’t move ahead with the process because we can’t divide with 0.
So, the value of T₁ should be the answer i.e. -5 which is fine but we need a positive value. To convert this to a positive value all we need to do is to add T₁ to the modulo in this case we need to add 11 and -5 i.e. 11 + (-5) = 6
and 6 is our modular multiplicative inverse.
If this was too complex for you or you didn’t understand it for any reason, I’ll recommend watching 4 really short videos of Neso Academy on this topic. You can look it up after reading this blog.
Part 1, Part 2, Part 3, Part 4
you can also use a calculator if you want the one I use is
Euler’s Theorem
if n and a are co-prime positive integers, and φ(n) is Euler’s Phi Function then —
a raised to the power φ(n) is congruent to 1 modulo n —
“^” this symbol represents exponential power (eg: 3 ^ 2 = 9)
a^φ(n) ≡ 1 mod n
Now we basically have everything we need to actually get started with how RSA works.
How does RSA work?
When you’ll learn how RSA actually works you’ll see that they didn’t invent anything new they just put together mathematical theorems that have already existed for 100s of years. So let’s get into it —
Step 1
You take 2 random prime numbers p & q like really huge prime numbers the standard these days are 1024 or 2048 bits in length each so you understand what size of numbers we talking about here.
Random here doesn’t mean Math.random() in JS, that won’t suffice we use specific algorithms that give us prime numbers that full-fill some criteria so that we know they are good to use. We generally would be using some Hardware Security Module (HSM)
But for this example we are not going to take those big numbers ofc, we’ll just take any two small prime numbers. Let’s go with 31 and 37.
p = 31, q = 37
Now just multiply these so n = p x q ⇒ n = 31 x 37 ⇒ n = 1147
Step 2
Now you use Euler’s Phi Function to take out φ(n)
Note :- You can use Carmichael function too i.e. λ(n)
n isn’t prime so how do we take out the φ(n)? well good thing is n is a product of two prime numbers.
So we just apply the property we learned above —
φ(n) = φ(p*q) = (p-1)(q-1) = 1080 ⇒ φ(n) = 1080
Step 3
Now to take out your encryption key (public key) e.
It can be any number as long as it full fills two conditions
1 < e < φ(n) & e is coprime with φ(n) i.e. HCF(e, φ(n)) = 1
HCF is the same as GCD
So you can calculate e or I can just cheat and tell you that 17 will work lol. You can choose any value that fits that criteria but the bigger it is the safer it will be.
The most used value of e is 65537. But we can’t use that because it’s larger than φ(n) in this case.
So, now we have p = 31, q = 37, n = 1147, φ(n) = 1080 & e = 17
Step 4
Now to calculate your decryption key (private key) d.
It’s the modular multiplicative inverse of e under φ(n) so basically
e*d ≡ 1 (mod φ(n)) ⇒ 17*d ≡ 1 (mod 1080)
Using the methods we discussed earlier we can calculate d but I’m just going to use the calculator lol
So, d = 953
Now we are all setup all the tough parts are over. Now comes the fun part.
Encryption & Decryption with RSA
Our encryption key will be (e, n) and decryption key will be (d, n).
Now, how do we share top secret information with our friends?
It’s easy, take whatever message you have let’s suppose the message is “ok”, convert it to a number you can use ASCII representation or any online converter. There are a tonn of ways to do this.
So after converting “ok” to numbers using ASCII we get = 111, 107 = M
Encrypting this message (I’m ofc using a calculator lol)—
To encrypt a message we raise the message to the power of e and the modulo of that number with n becomes the cipher text.
So, as we have e = 17 & n = 1147
y₁ = 111¹⁷ ≡ 851 mod 1147
y₂ = 107¹⁷ ≡ 971 mod 1147
So the cipher text = c = 851, 971
Now how to decipher it?
It’s simple again as we know d = 953. So, we basically do the same thing
x₁ ≡ 851⁹⁵³ (mod 1147) ≡ 111 mod 1147
x₂ ≡ 971⁹⁵³ (mod 1147) ≡ 107 mod 1147
So, the decrypted message is = 111, 107
Now we’ve finally Encrypted and Decrypted the messages successfully.
In reality we’ll not actually directly encrypt the message itself but pad it with some extra “random” numbers or hash it or do both to increase security.
Remind you again these aren’t the values we deal with while actually encrypting with RSA also there are many security calculations done before encrypting. So, don’t try to encrypt something important using this lol.
Why does it work?
Ok so you wanna know why RSA works? It’s actually very simple.
According to our calculations we can say that
cᵈ ≡ Mᵉᵈ (mod n)
here c is the cipher text d is the decryption key M is the original message, e is the encryption key and n is the product of the original two primes p & q.
If you don’t see how cᵈ ≡ Mᵉᵈ (mod n) is true then remember that c ≡ Mᵉ (mod n).
Now moving forward
As we know e & d are modular multiplicative inverse of each other. So,
This symbol | denotes divisibility for eg:- if x|y then x is divisible by y
ed ≡ 1(mod φ(n)) ⇒ φ(n)|(ed − 1)
⇒ (ed − 1) = φ(n)k, for some integer K
⇒ ed = 1 + φ(n)k, for some integer K
Now,
Medium isn’t letting me write all the weird expression so I’m gonna put pictures instead.
Since, n & M are co-primes, using Euler’s Theorem
Hence,
Therefore, we have concluded that
Breaking of RSA (Very Brief)
Could you break RSA?
Only if there are some problems in the process of encrypting the values itself.
For once, if you make p, q or d public you are done. Anyone can calculate d if they have the two initial prime numbers.
Another way might be if the numbers p & q are too close to each other or if it’s too close to the square root of n. Essentially you don’t want the numbers to be anywhere near close to each other or to the square root of n. There are theorems like Fermat’s Factorization Theorem that can be used against RSA if you were sloppy while generating the prime numbers.
I’m not going to cover it in length here because it’ll get too lengthy. If you want to learn more about breaking RSA I’ll attach a YouTube video in the end of the Blog you can refer there.
Problems with RSA
The major problem with RSA is the length of the keys. The keys are usually very very long and that’s one of the reasons why ECC is becoming more and more popular.
For reference:-
Using 7680 bit key in RSA will provide the same level of security if you use 384 bit key in ECC.
Also RSA is greatly vulnerable to quantum attacks. But so are most of the conventional cryptographic algorithms.
Extra resources
A whole video series on Cryptography (Make sure to refer to other sources if this confuses you)
Book on Cryptography (Or you can download the PDF)
And that’s about it. To be honest, you can write a whole book on just RSA but these are the very basics of it. I hope I brought some level of clarity on the topic of RSA through this blog.
Until next time.
