Introduction to RSA Encryption

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. It was publicly described in 1977.

The Mathematics Behind RSA

RSA relies on the practical difficulty of factoring the product of two large prime numbers.

Key Generation

Choose two distinct prime numbers $p$ and $q$
Compute $n = pq$ (the modulus)
Compute $\phi(n) = (p-1)(q-1)$ (Euler's totient function)
Choose $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$
Compute $d$ such that $de \equiv 1 \pmod{\phi(n)}$

The public key is $(n, e)$ and the private key is $(n, d)$.

Encryption

To encrypt a message $M$:

$$C = M^e \mod n$$

Decryption

To decrypt ciphertext $C$:

$$M = C^d \mod n$$

Why It Works

The security of RSA relies on:

Difficulty of Factoring: Given $n = pq$, it's computationally hard to find $p$ and $q$
Euler's Theorem: $M^{\phi(n)} \equiv 1 \pmod{n}$ for $\gcd(M, n) = 1$

Proof of Correctness

We need to show that $C^d \equiv M \pmod{n}$:

$$C^d = (M^e)^d = M^{ed} = M^{k\phi(n) + 1} = M \cdot (M^{\phi(n)})^k \equiv M \cdot 1^k = M \pmod{n}$$

Example

Let's work through a simple example:

Choose primes: $p = 11$, $q = 13$
Compute: $n = 11 \times 13 = 143$
Compute: $\phi(n) = 10 \times 12 = 120$
Choose: $e = 7$ (since $\gcd(7, 120) = 1$)
Find $d$: $7d \equiv 1 \pmod{120}$, so $d = 103$

Encrypt $M = 9$: $$C = 9^7 \mod 143 = 48$$

Decrypt $C = 48$: $$M = 48^{103} \mod 143 = 9$$

Security Considerations

Key size should be at least 2048 bits for security
Proper padding schemes (like OAEP) must be used
Never reuse primes across different keys
Use cryptographically secure random number generators

Applications

HTTPS/TLS for web security
Email encryption (PGP/GPG)
Digital signatures
VPNs and secure communication

Conclusion

RSA is a beautiful application of number theory to cryptography. While quantum computers may eventually break RSA, it remains a cornerstone of modern security systems.