RSA Encryption

RSA encryption is one of the first and most widely used public-key cryptosystems. Invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, it relies on the computational difficulty of factoring large composite integers into their prime components. The name derives from the initials of its creators.

Unlike symmetric cryptography, where the same key encrypts and decrypts data, RSA uses a mathematically linked key pair: a public key for encryption and a private key for decryption. This breakthrough enabled secure communication over untrusted networks without prior key exchange, laying the foundation for modern digital security.

Mathematical Foundation

RSA's security rests on number theory, specifically the properties of prime numbers, modular arithmetic, and Euler's totient theorem. The system operates under the assumption that while multiplying two large primes is computationally trivial, reversing the process (integer factorization) is infeasible for sufficiently large numbers.

Modular Arithmetic & Euler's Theorem

All RSA operations occur within modular arithmetic, denoted as a ≡ b (mod n), meaning a and b leave the same remainder when divided by n. The system relies on Euler's totient function φ(n), which counts integers less than n that are coprime to n.

For two distinct primes p and q, the modulus is n = p × q, and φ(n) = (p − 1)(q − 1). Euler's theorem states that if gcd(a, n) = 1, then:

This property ensures that encryption and decryption are inverse operations.

Key Generation Process

Generating an RSA key pair involves five deterministic steps. While conceptually straightforward, modern implementations add randomness and padding to prevent side-channel attacks.

1. Generate Primes: Select two large, random prime numbers p and q (typically 1024+ bits each).
2. Compute Modulus: Calculate n = p × q. This forms the modulus for both keys.
3. Calculate Totient: Compute φ(n) = (p − 1)(q − 1).
4. Choose Public Exponent: Select e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. 65537 (0x10001) is the industry standard for efficiency and security.
5. Derive Private Exponent: Compute d ≡ e⁻¹ (mod φ(n)) using the extended Euclidean algorithm.

The public key is (n, e). The private key is (n, d). In practice, p and q are retained to optimize decryption via the Chinese Remainder Theorem (CRT).

Encryption & Decryption

RSA operates directly on numeric representations of plaintext. In modern systems, messages are first padded (e.g., OAEP) before encryption to prevent deterministic attacks.

Where m is the plaintext integer (0 ≤ m < n), c is the ciphertext, and arithmetic is performed modulo n. The correctness follows from Euler's theorem: m^(ed) ≡ m (mod n) when ed ≡ 1 (mod φ(n)).

Security & Vulnerabilities

RSA's security depends entirely on the difficulty of factoring n. No polynomial-time algorithm exists for classical computers. However, several attack vectors exist:

• Integer Factorization Advances: The General Number Field Sieve (GNFS) remains the most efficient classical factoring algorithm. Keys below 2048 bits are considered vulnerable to well-resourced adversaries.
• Side-Channel Attacks: Timing, power analysis, and fault injection can leak private key material if implementations aren't hardened.
• Quantum Computing: Shor's algorithm can factor large integers in polynomial time on a sufficiently large quantum computer. NIST is currently standardizing post-quantum alternatives.

Current best practice recommends 3072-bit keys for long-term security and 2048-bit as the absolute minimum. Key rotation and hybrid encryption (RSA + AES) are standard in production systems.

Real-World Applications

Despite the rise of elliptic-curve cryptography (ECC), RSA remains ubiquitous due to decades of integration, standardization, and compatibility:

• TLS/SSL: Key exchange and certificate signing for HTTPS, though often superseded by ECDHE in modern handshakes.
• Digital Signatures: Authenticating software updates, documents, and email (S/MIME, PGP/GPG).
• PKI Infrastructure: X.509 certificates, code signing, and hardware security modules (HSMs).
• Secure Email & Messaging: OpenPGP, S/MIME, and legacy secure communication protocols.

Historical Context

RSA was publicly described in 1977, but the underlying mathematics was discovered earlier. In 1973, James H. Ellis at GCHQ identified the theoretical framework for asymmetric cryptography. Clifford Cocks independently derived the RSA algorithm internally that same year, but the work remained classified until 1997.

Rivest, Shamir, and Adleman independently reinvented the system at MIT, filing a patent in 1977 and publishing it in 1978. The patent expired in 2000, placing RSA in the public domain. Today, it remains a cornerstone of information security and a pedagogical standard in computer science curricula.

References & Further Reading

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
• NIST FIPS PUB 186-5. (2023). Digital Signature Standard (DSS). National Institute of Standards and Technology.
• Stinson, D. R. (2006). Cryptography: Theory and Practice (2nd ed.). Chapman & Hall/CRC.
• IETF RFC 8017. (2016). Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications.

Related: Elliptic Curve Cryptography · Diffie–Hellman Key Exchange · Post-Quantum Cryptography