RSA

RSA is named after its inventors: Ron Rivest, Adi Shamir, and Leonard Adleman. It turned public-key cryptography from a theoretical curiosity into a working technology. RSA was published in 1977. Diffie and Hellman floated the underlying idea a year earlier. RSA made it work: secure communication with no shared secret exchanged in advance. This guide covers the number theory behind RSA. It also covers the real-world attacks that shaped how it’s implemented today.

Table of Contents

1. Introduction
2. Historical Context and Development
3. Mathematical Foundations
4. How RSA Works: Complete Technical Guide
5. A Worked Example with Small Numbers
6. Python Implementation
7. Limitations
8. Padding Schemes: Why Raw RSA Isn’t Enough
9. Security Analysis and Threat Models
10. Common Vulnerabilities and Mitigation Strategies
11. Key Sizes and Performance
12. Implementation Considerations
13. Real-World Applications
14. RSA vs. Diffie-Hellman vs. ECC
15. Quantum Computing and the Future of RSA
16. Frequently Asked Questions
17. References and Further Reading

Introduction

Every time your browser shows a padlock icon, RSA likely played a role. RSA solves a problem that seems almost paradoxical. How can two parties agree on secret information using only messages anyone can see? The answer lies in a simple piece of number theory. Some operations are easy in one direction, and extraordinarily hard to reverse. Reversing them requires a specific secret.

Symmetric ciphers like AES use one key for both directions. RSA instead uses a key pair. A public key lets anyone encrypt a message or verify a signature. A private key, known only to its owner, decrypts messages or creates signatures. This single idea eliminated the need to transport a shared secret before communication could begin. That was arguably cryptography’s biggest unsolved problem before 1976.

Historical Context and Development

Whitfield Diffie and Martin Hellman laid the theoretical foundation. Their 1976 paper, “New Directions in Cryptography,” described the concept of a public-key system. It included a working key-exchange protocol. But they lacked a working implementation of full public-key encryption or signatures.

At MIT in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman searched for it. As the story goes, Rivest and Shamir proposed, and Adleman broke, dozens of schemes. They eventually landed on an approach built on factoring the product of two large primes. The algorithm was published in 1978, titled “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” RSA Data Security, Inc. formed soon after.

RSA was actually discovered earlier, in 1973, by Clifford Cocks. He was a mathematician working for the British intelligence agency GCHQ. His work stayed classified until 1997. By then, RSA was already a global standard, under Rivest, Shamir, and Adleman’s names.

RSA’s original US patent expired in September 2000, becoming fully free to use afterward. That helped cement it as the default choice for public-key cryptography for two decades.

Mathematical Foundations

RSA rests on a handful of number-theoretic ideas. You don’t need a math degree to follow them, just patience.

Prime Numbers and Factoring

A prime number has exactly two divisors: 1 and itself. Multiplying two large primes together is computationally trivial. Given only the product, working backward to find the original primes is called factoring. It gets extraordinarily hard as the numbers grow. This asymmetry, easy one way, hard the other, is the “trapdoor function” cryptography needs.

Modular Arithmetic

RSA performs all its arithmetic “mod n.” Results wrap around after reaching a modulus n, much like a clock past 12. Modular exponentiation, computing a^b mod n, stays efficient for enormous numbers, via the square-and-multiply algorithm. The reverse operation, the discrete logarithm, is hard. But RSA’s security doesn’t actually rely on the discrete logarithm problem. It relies on factoring, described below.

Euler’s Totient Function

Euler’s totient function φ(n) counts the integers between 1 and n coprime to n. That means they share no common factors with it. For a prime p, φ(p) = p − 1. Every number less than a prime is coprime to it. Critically, φ is multiplicative for coprime numbers. So for n = p × q, two distinct primes:

φ(n) = φ(p) × φ(q) = (p − 1)(q − 1)

This formula is the mathematical engine of RSA key generation.

Euler’s Theorem and Modular Inverses

Euler’s theorem states that if a and n are coprime, then a^φ(n) ≡ 1 (mod n). RSA builds directly on this. Raise a message to the power e × d, where e × d ≡ 1 (mod φ(n)). You get the original message back. Finding d, given e and φ(n), means computing a modular multiplicative inverse. That’s typically done via the Extended Euclidean Algorithm.

How RSA Works: Complete Technical Guide

Step 1: Key Generation

1. Choose two distinct large prime numbers, p and q, kept secret.
2. Compute the modulus n = p × q. This becomes part of both keys. Its bit-length, e.g. 2048 bits, is what people mean by “RSA key size.”
3. Compute Euler’s totient: φ(n) = (p − 1)(q − 1).
4. Choose a public exponent e, where 1 < e < φ(n) and gcd(e, φ(n)) = 1. Almost every implementation uses e = 65537 (2¹⁶ + 1) in practice. It’s prime, with a compact binary form for fast exponentiation. It also avoids the weaknesses of small exponents like 3.
5. Compute the private exponent d, the modular inverse of e modulo φ(n): d ≡ e⁻¹ (mod φ(n)).
6. The public key is the pair (n, e). The private key is the pair (n, d). In practice, p, q, and some CRT-derived values are also kept, to speed up decryption. Once d is computed, p, q, and φ(n) need protecting as carefully as d itself. Knowing any of them breaks the system.

Step 2: Encryption

To encrypt a message M, an integer where 0 ≤ M < n, with the public key (n, e):

C = M^e mod n

Anyone with the public key can perform this operation. Only the holder of d can reverse it.

Step 3: Decryption

To recover the message from ciphertext C, using the private key (n, d):

M = C^d mod n

This works because of the relationship established during key generation: (M^e)^d mod n = M^(ed) mod n = M^(k·φ(n)+1) mod n = M, for some integer k. It’s a direct consequence of Euler’s theorem.

Digital Signatures: RSA in Reverse

RSA’s structure is symmetric enough to produce digital signatures too, with the keys’ roles swapped. To sign a message, the sender computes S = H(M)^d mod n. It uses their own private key over a message hash. Anyone can verify it by computing H(M) =? S^e mod n, using the sender’s public key. A match proves the private key’s holder signed it. It also proves the message wasn’t altered.

Interactive Visualizer

The visualizer above runs this exact process with small demonstration numbers. One click generates a key pair, encrypts your message, and decrypts it back.

A Worked Example with Small Numbers

Real RSA keys use primes hundreds of digits long. The math is identical with small numbers. Here’s the classic textbook walkthrough:

1. Choose primes: p = 61, q = 53
2. Compute modulus: n = 61 × 53 = 3233
3. Compute totient: φ(n) = 60 × 52 = 3120
4. Choose e: e = 17 (gcd(17, 3120) = 1, so it’s valid)
5. Compute d: d = 2753, because 17 × 2753 = 46801 = 15 × 3120 + 1
6. Public key: (n = 3233, e = 17). Private key: (n = 3233, d = 2753)

Now encrypt the message M = 65:

C = 65^17 mod 3233 = 2790

And decrypt it back:

M = 2790^2753 mod 3233 = 65

The original message is recovered exactly. With numbers this small, an attacker could factor n = 3233 back into 61 × 53 instantly. That’s precisely why real RSA keys need hundreds of digits, not four.

Python Implementation

This is a genuine, complete implementation. It uses real Miller-Rabin primality testing and real prime generation. The modular inverse uses the same Extended Euclidean Algorithm from the worked example above.

import random
from math import gcd

def is_prime(n, k=20):
    """Miller-Rabin primality test."""
    if n < 2:
        return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n % p == 0:
            return n == p
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def generate_prime(bits):
    while True:
        candidate = random.getrandbits(bits) | (1 << bits - 1) | 1
        if is_prime(candidate):
            return candidate

def mod_inverse(e, phi):
    """Extended Euclidean Algorithm for modular inverse."""
    old_r, r = e, phi
    old_s, s = 1, 0
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
    return old_s % phi

def generate_keypair(bits=16):
    p = generate_prime(bits)
    q = generate_prime(bits)
    while p == q:
        q = generate_prime(bits)

    n = p * q
    phi = (p - 1) * (q - 1)

    e = 65537 if gcd(65537, phi) == 1 else 17
    d = mod_inverse(e, phi)

    return (n, e), (n, d)  # public key, private key

def encrypt(message_int, public_key):
    n, e = public_key
    return pow(message_int, e, n)

def decrypt(cipher_int, private_key):
    n, d = private_key
    return pow(cipher_int, d, n)

if __name__ == "__main__":
    # Reproduce the worked example above exactly
    n, e, d = 3233, 17, 2753
    ciphertext = encrypt(65, (n, e))
    decrypted = decrypt(ciphertext, (n, d))
    print(f"Ciphertext: {ciphertext}")
    print(f"Decrypted:  {decrypted}")
    assert ciphertext == 2790
    assert decrypted == 65

    # Now generate a fresh, real key pair
    public_key, private_key = generate_keypair(bits=16)
    message = 42
    c2 = encrypt(message, public_key)
    m2 = decrypt(c2, private_key)
    print(f"Public key:  {public_key}")
    print(f"Fresh round-trip: {message} -> {c2} -> {m2}")
    assert message == m2

Running this reproduces the worked example exactly: ciphertext 2790, decrypted back to 65. It then generates a fresh, independently random key pair and confirms a second round trip.

Limitations

This is a genuine, complete implementation of the real algorithm, not a simplified stand-in. It’s still a teaching artifact:

• No padding. As the next section explains, raw “textbook” RSA is deterministic and malleable. Production code always wraps messages in OAEP or PSS first.
• Tiny keys. The bits=16 default produces keys instantly breakable by factoring. Real keys need 2048 bits or more, as Key Sizes below covers.
• Not constant-time. pow() and this mod_inverse make no timing guarantees, the side-channel risk described in Security Analysis below.
• Never use this, or any hand-rolled RSA, in production. Real applications should use a vetted library, shown next.

Padding Schemes: Why Raw RSA Isn’t Enough

The “textbook” RSA formula above is dangerously insecure used directly, for several reasons:

• Determinism: The same plaintext always produces the same ciphertext under a given key. That leaks information; an attacker can tell when the same message is sent twice.
• Malleability: An attacker can manipulate a ciphertext predictably, without the key, changing the decrypted plaintext predictably too.
• Small message / small exponent attacks: If M^e doesn’t “wrap around” n, ordinary integer root extraction can sometimes invert it. No private key needed.

Modern implementations always wrap the message in a padding scheme before encrypting:

• PKCS#1 v1.5: The original, widely deployed scheme. Randomized padding bytes fix determinism. But it’s vulnerable to the Bleichenbacher padding oracle attack (below), unless padding errors are reported very carefully.
• OAEP (Optimal Asymmetric Encryption Padding): The modern standard for RSA encryption. It’s built on two rounds of a Feistel-like construction using hash functions. It has a security proof against chosen-ciphertext attacks. Current standards like PKCS#1 v2.2 recommend it.
• PSS (Probabilistic Signature Scheme): The modern standard for RSA signatures, with a proof PKCS#1 v1.5 lacks.

RSA isn’t “encrypt with the formula.” It’s “encrypt with the formula, wrapped in a carefully designed padding scheme.” Bad padding causes more real-world breaks than the math ever has.

Security Analysis and Threat Models

RSA’s security rests entirely on one assumption. Factoring the product of two large primes is computationally infeasible, for classical computers with sufficiently large n. No one has proven this mathematically. It’s backed by decades of failed attempts by the world’s best mathematicians. The RSA Factoring Challenge, running from 1991 to 2007, offered prize incentives too.

Beyond factoring, RSA’s practical security also depends on:

• Randomness quality: A weak generator choosing p and q lets attackers recover keys directly, skipping factoring entirely. Poorly seeded embedded devices have really shared factors between “independent” keys this way.
• Correct padding implementation: As covered above.
• Side-channel resistance: Naive implementations can leak timing, power, or cache-access patterns during decryption’s modular exponentiation. That leaks the private key, bit by bit.

Common Vulnerabilities and Mitigation Strategies

Attack	Description	Mitigation
Factoring advances / weak key sizes	Sufficiently small n (512, 768, even 1024 bits) can be factored with enough compute.	Use 2048-bit keys minimum; 3072/4096-bit for long-term security.
Low public exponent (Håstad’s broadcast attack)	If the same message is sent to enough recipients with small e (e.g., e=3) without proper padding, the plaintext can be recovered via the Chinese Remainder Theorem.	Always use proper padding (OAEP); e=65537 is standard but padding is what actually protects against this.
Common modulus attack	If two different users are mistakenly given the same modulus n with different exponents, a message encrypted to both can sometimes be recovered without either private key.	Never share a modulus between key pairs; generate each key pair independently.
Bleichenbacher padding oracle (1998)	If a server responds differently to valid vs. invalid PKCS#1 v1.5 padding, an attacker can use those responses as an oracle to decrypt ciphertexts through repeated queries. Modern variants (ROBOT, 2017) still find this in TLS servers decades later.	Use constant-time padding checks that don’t leak information via error messages or timing; prefer OAEP.
Timing attacks	Variations in how long decryption takes can leak information about the private exponent d.	Use constant-time modular exponentiation and blinding techniques.
Coppersmith’s attack	If enough bits of p, q, or d are known or if e is very small with partially known plaintext, lattice-based techniques can recover the rest.	Use full-length, properly random primes and standard padding.
Weak / predictable randomness	Poor entropy sources when generating p and q can lead to shared or guessable factors.	Use cryptographically secure random number generators (CSPRNGs) with sufficient entropy.

Key Sizes and Performance

RSA key sizes are typically discussed in bits, the bit-length of the modulus n:

• 1024-bit: Considered broken for long-term security; deprecated since the early 2010s.
• 2048-bit: The current practical minimum, recommended by NIST through at least 2030.
• 3072-bit: Roughly 128-bit symmetric security; recommended for longer-term protection.
• 4096-bit: Used where extra margin is wanted, at a real performance cost.

RSA operations slow significantly as key size grows. Decryption and signing, using the private exponent, cost far more than encryption or verification. That’s why RSA rarely encrypts bulk data directly. Instead, it encrypts a much shorter symmetric key. That key does the heavy lifting, with AES or ChaCha20. That’s the hybrid encryption approach used throughout TLS, PGP, and most RSA-based protocols.

A common optimization decrypts via the Chinese Remainder Theorem (CRT). Instead of computing C^d mod n directly, it performs two smaller exponentiations, modulo p and q, then recombines the results. That’s roughly 4x faster than the naive approach.

Implementation Considerations

• Never implement RSA padding yourself. Use audited libraries: OpenSSL, libsodium, BoringSSL, or your language’s standard crypto library.
• Prefer OAEP over PKCS#1 v1.5 for new systems requiring encryption.
• Prefer PSS over PKCS#1 v1.5 for new systems requiring signatures.
• Use e = 65537 unless you have a specific, well-understood reason not to.
• Validate all inputs, especially ciphertext length and structure, before private-key operations. This avoids padding-oracle-style leaks.
• Consider whether you need RSA at all. For new systems, ECC-based algorithms (see the ECC guide) often match RSA’s security with smaller, faster keys.

Here’s how that looks with Python’s cryptography package, which handles padding and key generation correctly:

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

ciphertext = public_key.encrypt(
    b"a secret message",
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)
assert plaintext == b"a secret message"

Real-World Applications

• TLS/HTTPS: RSA has historically handled both certificate authentication and key exchange. TLS 1.3 increasingly favors ECDHE for exchange, though RSA (or ECDSA) still commonly signs certificates.
• PGP/GPG and S/MIME: Email encryption often relies on RSA keys, as the PGP Hybrid Algorithm guide covers.
• SSH: RSA is one of several supported key types for authenticating SSH sessions.
• Code signing: Publishers sign binaries and updates with RSA keys, so systems verify authenticity before install.
• Digital certificates and PKI: Certificate Authorities use RSA, among other algorithms, to sign certificates underpinning web trust.

RSA vs. Diffie-Hellman vs. ECC

It’s easy to conflate RSA with the site’s other classic asymmetric algorithms. They solve related problems differently:

• RSA provides both encryption and signatures directly, based on integer factorization.
• Diffie-Hellman provides only key exchange, not encryption or signing. It’s based on the discrete logarithm problem in a finite field.
• ECC re-implements the same discrete-logarithm ideas on elliptic curves: ECDH for exchange, ECDSA/EdDSA for signatures. It matches RSA’s security with far smaller keys. A 256-bit ECC key roughly matches a 3072-bit RSA key.

RSA is gradually ceding ground to ECC for new deployments, mostly due to ECC’s efficiency edge. But RSA’s simplicity, maturity, and enormous deployment base keep it relevant for a long time yet.

Quantum Computing and the Future of RSA

RSA’s security assumption, that factoring is intractable, only holds for classical computers. In 1994, Peter Shor published a quantum algorithm that factors integers in polynomial time. It needs a sufficiently large, fault-tolerant quantum computer. That would break RSA, along with Diffie-Hellman and ECC, completely.

No quantum computer built to date comes anywhere near that scale. But the threat is taken seriously. NIST has already standardized post-quantum replacements: lattice-based CRYSTALS-Kyber for key encapsulation, and CRYSTALS-Dilithium for signatures. Organizations needing decades-long confidentiality are already planning migrations. An adversary could record encrypted traffic today. They’d decrypt it once a capable quantum computer exists: “harvest now, decrypt later.”

Frequently Asked Questions

Why is e usually 65537?

65537 (2¹⁶ + 1) is prime, with only two bits set in binary, making exponentiation fast. It’s also large enough to dodge the low-exponent attacks. Smaller values, like e=3, invite those under weak padding.

Can RSA encrypt arbitrarily large messages?

No. A message must be an integer smaller than the modulus n. That’s why RSA encrypts short symmetric keys, or hashes for signatures, rather than entire documents. Bulk data gets a fast symmetric cipher like AES. Only that key is RSA-encrypted.

Is RSA still safe to use today?

Yes, given a large enough key (2048 bits minimum, 3072+ long-term) and modern padding. RSA resists all known classical attacks. Quantum computing complicates the outlook, which is why standards bodies are moving toward post-quantum algorithms.

What’s the difference between RSA encryption and RSA signatures?

Encryption uses the recipient’s public key to scramble data only their private key can unscramble. Signing uses the signer’s private key instead, producing a value verifiable with their public key. That proves authenticity, not confidentiality.

Why can’t I just use “textbook” RSA without padding?

Because it’s deterministic, malleable, and vulnerable to mathematical shortcuts (see Padding Schemes). Every real-world RSA use wraps the message in OAEP or PSS padding first.

How does RSA compare in speed to AES?

RSA is orders of magnitude slower than AES for equivalent data. That’s why it protects a symmetric key rather than the data itself. That’s the standard hybrid pattern used throughout TLS and PGP.

References and Further Reading

• RSA Original Paper (1978): A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. The original publication by Rivest, Shamir, and Adleman.
• NIST SP 800-56B: Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. Official US government guidance on RSA key establishment.
• RFC 8017 (PKCS #1 v2.2): RSA Cryptography Specifications. The formal standard defining RSA encryption/signature schemes, including OAEP and PSS padding.
• Wikipedia: RSA (cryptosystem): RSA (cryptosystem). A thorough overview including the worked numerical example used in this guide.
• Bleichenbacher’s 1998 Attack Paper: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. The paper that introduced the padding oracle attack still relevant in modern TLS deployments (as ROBOT).
• NIST Post-Quantum Cryptography Project: NIST PQC Standardization. The ongoing effort to standardize algorithms resistant to quantum attacks on RSA, DH, and ECC.