Unveiling the Story and Significance of the RSA Algorithm

Let’s talk about one of the most famous algorithms in cybersecurity, the RSA algorithm. As simple as it is, it has yet to be broken. It was created by three MIT scholars, Ron Rivest, Adi Shamir, and Leonard Adleman, and published in 1977.

Although a similar approach had already been discovered by an English mathematician, Clifford Cocks. While working for Britain’s GCHQ, he proposed this algorithm, but due to the secretive nature of the organisation, his work was classified. In 1997, his work was declassified, and he got the recognition of being the first person to propose this algorithm. The British GCHQ did not implement the algorithm, as Clifford tells us in one of his interviews, “They thought very seriously about how to do it, but came to the conclusion, quite correctly at the time, that it was too expensive.”.

Asymmetric Encryption

Diffie-Helman released a study regarding digital signatures and public-private key cryptography, which gave the idea of creating an asymmetric public-private key cryptosystem. Ron Rivest and Adi Shamir were computer scientists and used to propose potential functions to Leonard Adleman, a mathematician who then broke those functions. In April 1977, Ron Rivest created this algorithm after getting the idea late at night and having the paper ready by morning with Adleman’s approval (proving that the best work is done when we don’t sleep). It was first published in the public eye with a mention by Martin Gardner in Scientific American in August 1977.

The central idea of the RSA algorithm is to create a one-way function that can be used to derive a solution in one direction but not in the other. In order to do so, RSA makes use of modular arithmetic, also known as clock arithmetic.

An example of modular arithmetic can be 46 mod 12, which will be equal to 10, and can be understood as a clock with 12 divisions from 1 to 12, and on that clock, if 46 is counted, then we will reach 10 after 3 complete rotations.

Now, to make it work we find a prime modulus such as 17 and it’s primitive root such as 3 which gives only uniform distribution around the clock.

Let's calculate the powers of 3 modulo 17:

3^1 mod 17 = 3
3^2 mod 17 = 9
3^3 mod 17 = 10
3^4 mod 17 = 13
3^5 mod 17 = 5
3^6 mod 17 = 15
3^7 mod 17 = 11
3^8 mod 17 = 16
3^9 mod 17 = 14
3^10 mod 17 = 8
3^11 mod 17 = 7
3^12 mod 17 = 4
3^13 mod 17 = 12
3^14 mod 17 = 6
3^15 mod 17 = 2
3^16 mod 17 = 1

The powers of 3 generate all the residues from 1 to 16 modulo 17. Therefore, 3 is indeed a primitive root of 17.

So let me break down the RSA algorithm as simple as possible

1. Choose two prime numbers(p1, p2)
2. Calculate n = p1 * p2
3. Calculating Euler’s Totient Function Φ = (p1-1) * (p2-1)
4. Choose a coprime to Φ , call it e
5. Calculate the private key d = (k * Φ(n) + 1) / e

Now, after key generation, we can use n and e as the public key to encrypt messages. And use d and n as private key to decrypt messages.

Let’s take an example

p1 = 53, p2 = 59

n = p1 * p2 = 53 * 59 = 3127

Φ(n) = (p1-1) * (p2-1) = 52 * 58 = 3016

e = 3

d = (k * Φ(n) + 1) / e = (2 * 3016 + 1) / 3 = 2011

Let’s take a message “HI” which can be written as 89 if we take A = 1, B = 2.

To encrypt the message we send the public key n and e to the other party which then encrypts the message.

c = mᵉ mod n = 89³ mod 3127 = 1394

The encrypted message is then sent back to user which the uses private key d to decrypt the message and get the original message.

m = cᵈ mod n = 1394²⁰¹¹ mod 3127 = 89

Thereby, recovering the encrypted message.

Rivest, Shamir and Adleman received the Association for Computing Machinery’s 2002 Alan Turing Award for their contributions, among other awards.

And for everyone wondering why is it so safe that it still cannot be broken the answer would be that it can be broken… BUT… it requires us to find factors of n which are 2 primes numbers. Now, yes if we take low numbers then it can be broken but if we take a larger numbers as factors it becomes virtually impossible to factorize them and get back the original prime factors. Since 2015, NIST recommends a minimum of 2048-bit keys for RSA which was previously 1024-bit.

Obviously this article contains only the most basics of RSA cryptosystem so I will cover this topic in depth but if you want me to do it faster, let me know.

Until then play around with this RSA encryption tool that I built !!