Cracking the Code: A Beginner's Guide to RSA Encryption

In today's digital age, data security is more important than ever. With the increasing amount of personal and sensitive information being shared online, it's crucial to ensure that this data is protected from unauthorized access.

One of the most widely used methods of data encryption is RSA (Rivest-Shamir-Adleman), named after the three MIT professors who first publicly described it in 1977.

Fun Fact: These are also the professors who created ‘Alice’ and ‘Bob’

The advent of RSA

In the early 1970s, encryption methods were based on a shared key algorithm: Alice could lock the message with a key, and Bob could unlock it with a duplicate key. This shared key could be generated by methods like the Diffie-Hellman Key Exchange:

But creating shared keys required a lot of interaction between the sender and receiver. For example, if Alice was a bank, she would need to create a separate shared key with 1000s of her customers. This method could not scale!

The solution to this scaling problem was found in the RSA algorithm:

The encryption key, also known as the public key, is used to encrypt the plaintext (original message) and the decryption key, also known as the private key, is used to decrypt the ciphertext (encrypted message).

The security of RSA lies in the fact that it is extremely difficult to find out the private key based on the public key, even if the attacker knows the encryption algorithm.

How it all works

The process of sending an encrypted message using RSA looks like this :

1. First, a user generates a pair of keys - a public key and a private key. The public key is made available to anyone who wants to send an encrypted message, while the private key is kept secret by the user.

2. When a sender wants to send an encrypted message, they use the recipient's public key to encrypt the message.

3. The encrypted message, known as the ciphertext, is then sent to the recipient.

4. The recipient uses their private key to decrypt the ciphertext, revealing the original message.

“But how is it possible to have 2 different keys for the same lock?”

Some of you might have figured that out already. The answer lies in Modular Arithmetic. Remember how that works?

Let me give you a quick recap:

Given random numbers m, E, and N, it is very easy to generate c

But, given c, E, and N, it is almost impossible to generate m

Fun Fact: These types of functions that are easy to solve in one direction, but extremely hard to reverse are called Trapdoor functions.

Now, the idea behind RSA is simply to find a private number , such that:

Since c is generated from m in the first place, the above equation is the same as:

or,

So, E = public key, and D = private key

Let's look at an example to better understand how it all comes together:

Let's say Alice wants to send a message to Bob.

1. First, Bob generates a pair of keys - a public key (N=143, E=7) and a private key (D=103). He shares his public key with Alice.

2. Alice wants to send the message "HELLO" (in ASCII, 72 69 76 76 79) to Bob. She uses Bob's public key to encrypt the message by raising each letter's ASCII value to the power of 7 mod 143. For example, for H:

• So, "H" (72) becomes 19, "E" (69) becomes 108, "L" (76) becomes 54, "L" (76) becomes 54, "O" (79) becomes 40

1. Alice receives the ciphertext 19,108,54,54,40. She then sends it to Bob over a public channel

2. Bob uses his private key (d=103) to decrypt the ciphertext by raising each ciphertext value to the power of 103 mod 143.

• 19 becomes 72, 108 becomes 69, 54 becomes 76, 54 becomes 76, 40 becomes 79

• Bob now has the original message "HELLO"

This worked because we generated the public and the private keys in such a way that:

For any outsider, finding D requires factorizing N. As long as N is a large prime, factorizing it is a TOUGH task even for supercomputers!

This is why RSA is widely used for secure data transmission and is the basis for a variety of security protocols and standards, including SSL/TLS, which is used to secure internet connections and protect online transactions even today!