RSA Encryption

RSA, developed by Rivest, Shamir, and Adleman in 1977, is a cornerstone of public-key cryptography. At MathMultiverse, we break down its mathematical foundation, provide clear examples, and visualize its mechanics to secure digital communication.

How RSA Works

RSA uses modular arithmetic and prime factorization:

  1. Choose primes \( p \) and \( q \).
  2. Compute \( n = p \times q \), \( \phi(n) = (p-1)(q-1) \).
  3. Select \( e \), coprime to \( \phi(n) \).
  4. Find \( d \) where \( e \times d \equiv 1 \mod \phi(n) \).
  5. Encrypt: \( C = P^e \mod n \); Decrypt: \( P = C^d \mod n \).
\[ \text{Public key: } (e, n), \quad \text{Private key: } (d, n) \]

Examples

Basic RSA

Using \( p = 3 \), \( q = 11 \):

\[ n = 33, \quad \phi(33) = 20 \] \[ e = 7, \quad d = 3 \] \[ C = 5^7 \mod 33 = 14 \] \[ P = 14^3 \mod 33 = 5 \]

Larger Primes

Using \( p = 17 \), \( q = 23 \):

\[ n = 391, \quad \phi(391) = 336 \] \[ e = 5, \quad d = 269 \] \[ C = 10^5 \mod 391 = 100 \] \[ P = 100^{269} \mod 391 = 10 \]

Visualizations

Modular Exponentiation

Security Basis

RSA’s security relies on the difficulty of factoring large \( n \). With 2048-bit keys, factorization is infeasible today, though quantum computers may challenge this in the future.

Applications

  • HTTPS: Secures web communication, e.g., \( C = 10^5 \mod 391 \).
  • Digital Signatures: Verifies authenticity using \( P = C^d \mod n \).
  • Key Exchange: Enables secure symmetric key sharing.