RSA Encryption

RSA, named after Rivest, Shamir, and Adleman (1977), is a public-key cryptography system using a pair of keys: public for encryption, private for decryption. It’s foundational to secure internet communication. This article explains its mechanics, an example, security, and uses.

How RSA Works

RSA relies on modular exponentiation and prime factorization:

  1. Choose two primes, \( p \) and \( q \).
  2. Compute \( n = p \times q \) (modulus) and \( \phi(n) = (p-1)(q-1) \).
  3. Select public exponent \( e \) (coprime to \( \phi(n) \)).
  4. Find private exponent \( d \) where \( e \times d \equiv 1 \mod \phi(n) \).
  5. Encrypt: \( C = P^e \mod n \); Decrypt: \( P = C^d \mod n \).

Public key: \( (e, n) \); Private key: \( (d, n) \).

RSA Example

Small example: \( p = 3 \), \( q = 11 \):

  • \( n = 3 \times 11 = 33 \), \( \phi(33) = 2 \times 10 = 20 \).
  • \( e = 7 \) (coprime to 20), \( d = 3 \) (since \( 7 \times 3 = 21 \equiv 1 \mod 20 \)).
  • Encrypt \( P = 5 \): \( C = 5^7 \mod 33 = 78125 \mod 33 = 14 \).
  • Decrypt \( C = 14 \): \( P = 14^3 \mod 33 = 2744 \mod 33 = 5 \).

Real RSA uses much larger primes.

Security Basis

RSA’s strength lies in the difficulty of factoring \( n \) into \( p \) and \( q \). Modern keys (2048-bit) make this computationally infeasible with current technology. Quantum computers (Shor’s algorithm) pose a future threat.

Applications

RSA secures:

  • SSL/TLS: Web encryption (HTTPS).
  • Digital Signatures: Verifying authenticity.
  • Key Exchange: Safely sharing symmetric keys.

It’s critical for e-commerce and privacy.