The RSA Algorithm

By Sudheer S

Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the RSA algorithm.

RSA is an algorithm to perform encryption and decryption of data.

The Basic Idea

RSA uses two keys to encrypt and decrypt messages:

  • Public Key: Anyone can see this key. It’s used to encrypt the message.
  • Private Key: Only you should know this key. It’s used to decrypt the message.

When someone wants to send you a secret message, they use your public key to encrypt the message. Once it’s encrypted, only your private key can decrypt it.

Here’s a simplified version of how RSA works:

  • Generate two large prime numbers:

    • Choose two large prime numbers, let’s call them p and q.
    • Multiply them together to get n (which will be part of both keys).

  • Calculate Euler’s totient:

    • Calculate a value called φ(n), which is (p - 1) * (q - 1).
    • This number helps in finding the keys.

  • Create the public Key:

    • Choose a number e that is relatively small and doesn’t share any common factors with φ(n) (except for 1).
    • The public key is made of n and e. This key is used to encrypt messages.

  • Create the private Key:

    • Find a number d such that (e * d) % φ(n) = 1. This number d is the private key.
    • The private key is made of n and d. This key is used to decrypt messages.

  • Encryption:

    • If someone wants to send you a message (let’s call the message M), they use your public key (n, e) to encrypt it.
    • The encrypted message is C, calculated by C = (M^e) % n.

  • Decryption:

    • To read the message, you use your private key (n, d) to decrypt it.
    • The original message M is recovered by M = (C^d) % n.

Why is RSA Secure?

The security of RSA relies on the fact that it’s easy to multiply two large prime numbers, but it’s very hard to do the reverse—i.e., finding the original prime numbers when you only know their product (n). This difficulty makes it extremely tough for anyone to crack the encryption without the private key.

Let’s walk through a simple example of how RSA works. We’ll use small numbers to keep things understandable, though in practice, RSA uses much larger numbers.

Step 1: Choose two prime numbers

Let’s pick two small prime numbers: p = 5 and q = 11.

Step 2: Calculate n

Multiply p and q to get n: n=p×q=5×11=55

Step 3: Calculate Euler’s totient φ(n)

Calculate φ(n) as: φ(n)=(p−1)×(q−1)=(5−1)×(11−1)=4×10=40

Step 4: Choose e (public exponent)

Choose a number e that is relatively prime to φ(n), meaning it shares no common factors with 40 other than 1. Let’s pick e = 3.

Step 5: Calculate d (private exponent)

Now, find d such that (e × d) % φ(n) = 1. This means d is the multiplicative inverse of e modulo φ(n):

We want (3 × d) % 40 = 1.

By trial, we find that d = 27 works because (3 × 27) % 40 = 81 % 40 = 1.

Step 6: Create the Keys

Public key: (n, e) = (55, 3) Private key: (n, d) = (55, 27)

Step 7: Encryption

Let’s say the message M you want to send is M = 7. To encrypt it, calculate C using the public key:

$$ C = M^{e} mod n = 7^{3} mod 55 = 343 mod 55 = 13 $$

The encrypted message is C = 13.

Step 8: Decryption

To decrypt the message, use the private key:

$$ M = (C^{d}) mod n= (13^{27}) mod 55 = 7 $$

This looks complex, but we can simplify it using modular arithmetic tricks (or a calculator):

M=7

The decrypted message is M = 7, which matches the original message.

Summary:

Public Key: (55, 3)

Private Key: (55, 27)

Original Message: 7

Encrypted Message: 13

Decrypted Message: 7

This simple example shows how RSA works. In real-life applications, the numbers would be much larger, making it extremely difficult to break the encryption without the private key.