How RSA Works | A Beginner-Friendly Approach

The Basics: Two Keys, One Brilliant Idea

So if I tell you some history of RSA, then when it was discovered it was the biggest breakthrough, because at that time people were using symmetric-key cryptography which includes the same key for encryption and decryption which is less secure because anyone who has a copy of the key can able to decrypt the message or gain the secret access.

The Genius Strategy behind the RSAs

RSA was revolutionary because it introduced a trapdoor function — A function that is easy to do but hard to undo.

For example, it is easy to multiply two prime numbers to create a modulus(product) but hard to factorize back to its prime component.

This asymmetry in difficulty formed the basis for secure encryption:

• The public key (based on the modulus) is shared openly, enabling anyone to encrypt messages.
• The private key (derived from the primes) remains secret, ensuring only the intended recipient can decrypt the message.

Note: If you do not want to know the actual maths behind RSA then you can skip this upcoming section and go through the other ones.

Practical of RSA Encryption — A Sneak Peak

Let’s talk about some maths and create a simple example to understand all of the maths behind it easily.

Step — 1: Choose Prime Numbers

1. Pick two prime numbers: p = 13, q = 7.

2. Calculate their modulus(Product(n)):

This modulus defines the range of numbers of work with, if the key becomes more than that then we wrap it using the mod function and make it less than the modulus.

Step 2 — Compute Public and Private Keys

1. Calculate ϕ(n):

ϕ(n) = ( p − 1 )×( q − 1 ) = 12 × 6 = 72

2. Choose a public key(e) that is going to be used as an encryption key that is also coprime with ϕ(n).

so, Let e = 5.

3. Calculate the private key(d) using the Extended euclidian Algorithm to satisfy:

( e × d ) mod ϕ(n) = 1

which satisfies with the entries like For e = 5 and ϕ(n) = 72, d = 29.

Now, our RSA system is ready where:

• Public Key: ( e , n ) = ( 5,91 )
• Private Key: d = 29

Step 3 — Encrypt a Message

Let’s now send a top-secret message to your friend which is “HI”

As of right now, we have the public and the private keys in our hands, now we can encrypt and decrypt any message we want.

The word “HI” whose UTF-encoding is H = 72 and I = 73.

No, we need to encrypt the message using the formula:

Given the RSA parameters:

• n = 91(modulus)
• e = 5 (public key exponent)

1. Encrypt H (72):

72⁵ mod 91:

• 72 × 72 = 5184 remainder 85.
• 85 × 72 = 6120, remainder 20

….

By doing this we get so, we get the encrypted value of H (72) as 36.

2. Encrypt I (73):

73⁵ mod 91

• 73 × 73 = 5329, remainder 4.
• 4 × 73=292, remainder 20.

….

Similarly, by doing so the encrypted value of I (73) is 20.

So the Encrypted version of the message after this is going to be HI = 36,20

Step 4 — Decrypting the Message: "36, 20"

After encrypting the message, we got this value which is now encrypted as 36, and 20 need to use the private key to decrypt the original message, by using the formula.

Given the RSA parameters:

• d = 29 (private key exponent)
• n = 91

Decrypt 36, 20:

36²⁹mod 91 — — — — — →Result = 72.

20²⁹ mod 91 — — — — — →Result = 73.

Converting back to letters

( 72 , 73 ) — — — — → HI(After UTF-8 decoding)

So finally, in the end, you send your top secret message to your friend by compromising with the outer environment entities.

Why is RSA Secure?

The strength of the RSA lies in the mathematical problem which is known as factorization.

Remember the fact that two prime numbers are multiplied earlier, to calculate their modulus?

That modulus creates a trapdoor, which means it is easy to multiply the number but hard to factorize or break them into their prime components. If you are going for smaller numbers then you or any other computational power can do it but if you go deeper and increase the size of the primes then it is very difficult to factorize them, even the fastest computers take around Years, or even centuries to break the properly implemented RSA system.

Limitations of RSA

A Chain Is Only as Strong as Its Weakest Link

As we know there are various use cases of the RSA keylock system, but as we use known aspects can weaken its effectiveness if not carefully managed.

RSA key size

As we know small prime numbers can easily be broken by various techniques like brute force or something. To maintain security, RSA keys must be large (e.g., 2048 or 4096 bits).

But as the becomes larger, the computational overhead becomes excessive which decreases the overall speed of the application which we are creating. This can strain low-powered devices like IoT gadgets, smartphones, or embedded systems.

For this, we can use different algorithms like small Elliptical Diffie-Hellman curve techniques to compete.

Vulnerability due to Quantum Computing

Recently, we saw how Google’s Willow quantum chip made trillions of years of calculations in 5 minutes using qubits, and technologies like quantum entanglement.

RSA relies on the difficulty of factoring large numbers into primes. Quantum computers, using algorithms like Shor’s Algorithm, could efficiently solve this problem, which means once quantum computing came into existence most of the RSA algorithm became obsolete.

Conclusion

So after all using RSA is still a better choice, as we are on the verge of only bit technology computers. RSA remains a powerful cryptographic tool, but its limitations remind us that we must not only depend on this. Considering only this era in which we generally have access only to the normal bits then, we can also choose different techniques such as the Elliptical Diffie-Hellman curve, which reduces the computational overheads to a greater extent.

The advantages of elliptic curve cryptography over traditional RSA are widely accepted. Many experts are concerned that the mathematical algorithms behind RSA and Diffie-Hellman could be broken within 5 years, leaving ECC as the only reasonable alternative.