RSA — named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman — is the algorithm that turned public-key cryptography from a theoretical curiosity into a working, deployable technology. Published in 1977, it was the first practical implementation of the idea that Whitfield Diffie and Martin Hellman had proposed just a year earlier: that two people could communicate securely without ever having exchanged a secret key in advance. This guide covers everything from the number theory that makes RSA possible to the real-world attacks that have 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. Padding Schemes: Why Raw RSA Isn’t Enough
7. Security Analysis and Threat Models
8. Common Vulnerabilities and Mitigation Strategies
9. Key Sizes and Performance
10. Implementation Considerations
11. Real-World Applications
12. RSA vs. Diffie-Hellman vs. ECC
13. Quantum Computing and the Future of RSA
14. Practical Code Implementation
15. Frequently Asked Questions
16. Conclusion
17. References and Further Reading

Introduction

Every time your browser shows a padlock icon, there’s a good chance RSA (or one of its close relatives) played a role in getting you there. RSA solves a problem that seems almost paradoxical: how can two parties agree on secret information using only messages that anyone can see? The answer lies in a beautifully simple piece of number theory — some mathematical operations are easy to perform in one direction and extraordinarily hard to reverse, unless you hold a specific piece of secret information.

Unlike symmetric ciphers such as AES, where the same key encrypts and decrypts, RSA uses a key pair: a public key that anyone can use to encrypt a message or verify a signature, and a private key, known only to its owner, that decrypts messages or creates signatures. This single idea eliminated the need to securely transport a shared secret before communication could begin — arguably the most significant unsolved problem in cryptography before 1976.

Historical Context and Development

The theoretical foundation for public-key cryptography was laid by Whitfield Diffie and Martin Hellman in their 1976 paper “New Directions in Cryptography.” They described the concept of a public-key system and delivered a working key-exchange protocol, but they did not have a working implementation of full public-key encryption or digital signatures.

In 1977, three researchers at MIT — Ron Rivest, Adi Shamir, and Leonard Adleman — set out to find a mathematical function that could serve as the missing piece. After many failed attempts (the story goes that Rivest and Shamir proposed and Adleman broke dozens of candidate schemes), they landed on an approach built on the difficulty of factoring the product of two large prime numbers. The algorithm was published in 1978 as “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” and RSA Data Security, Inc. was founded to commercialize it.

Interestingly, RSA was independently discovered a few years earlier (1973) by Clifford Cocks, a mathematician working for the British intelligence agency GCHQ — but his work was classified and not revealed until 1997, by which point RSA was already a global standard under Rivest, Shamir, and Adleman’s names.

RSA’s original US patent expired in September 2000, after which it became fully free to use without licensing — a factor that helped cement it as the default choice for public-key cryptography for the following 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, however, working backward to find the original primes — factoring — becomes extraordinarily difficult as the numbers grow. This asymmetry (easy one way, hard the other) is exactly the kind of “trapdoor function” public-key cryptography needs.

Modular Arithmetic

RSA performs all of its arithmetic “mod n” — meaning results wrap around after reaching some modulus n, much like a clock wraps around after 12. Modular exponentiation (computing a^b mod n) can be done efficiently even for enormous numbers using the square-and-multiply algorithm, while 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

For a number n, Euler’s totient function φ(n) counts how many integers between 1 and n are coprime to n (share no common factors other than 1). For a prime p, φ(p) = p − 1, since 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 is built directly on top of this: if you 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, typically 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 the public and private key. Its bit-length (e.g., 2048 bits) is what people mean when they refer to “RSA key size.”
3. Compute Euler’s totient: φ(n) = (p − 1)(q − 1).
4. Choose a public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (e and φ(n) share no common factors). In practice, almost every implementation uses e = 65537 (2¹⁶ + 1), because it’s prime, has a compact binary representation (fast exponentiation), and avoids known weaknesses associated with very small exponents like 3.
5. Compute the private exponent d as the modular multiplicative 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 — more on that later). Once d is computed, p, q, and φ(n) must be discarded or protected as carefully as d itself, since knowing any of them breaks the system.

Step 2: Encryption

To encrypt a message M (represented as an integer 0 ≤ M < n) using the recipient’s public key (n, e):

C = M^e mod n

Anyone with the public key can perform this operation, but 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, a direct consequence of Euler’s theorem.

Digital Signatures: RSA in Reverse

RSA’s structure is symmetric enough that the same math produces digital signatures, just with the roles of the keys swapped. To sign a message, the sender computes S = H(M)^d mod n using their own private key over a hash of the message. Anyone can verify the signature by computing H(M) =? S^e mod n using the sender’s public key. If it matches, the signature proves the message was signed by the holder of the private key and hasn’t been altered.

A Worked Example with Small Numbers

Real RSA keys use primes hundreds of digits long, but the math is identical with small numbers — which is exactly what the interactive visualizer above lets you experiment with. 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, i.e., 17 × 2753 ≡ 1 (mod 3120)
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 in a fraction of a second — which is precisely why real RSA keys need to be hundreds of digits long, not four.

Padding Schemes: Why Raw RSA Isn’t Enough

The “textbook” RSA described above — encrypt with M^e mod n, decrypt with C^d mod n — is dangerously insecure to use directly, for several reasons:

• Determinism: The same plaintext always produces the same ciphertext under a given key, leaking information (e.g., an attacker can tell when the same message is sent twice).
• Malleability: An attacker can manipulate a ciphertext in predictable ways and produce a predictable change to the decrypted plaintext, without knowing the key.
• Small message / small exponent attacks: If M is small enough that M^e doesn’t “wrap around” the modulus n, the ciphertext can potentially be inverted with ordinary integer root extraction rather than needing the private key at all.

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

• PKCS#1 v1.5: The original, widely deployed padding scheme. It adds randomized padding bytes before encryption, which fixes determinism, but it’s vulnerable to the Bleichenbacher padding oracle attack (see below) if implementations aren’t extremely careful about how they report padding errors.
• OAEP (Optimal Asymmetric Encryption Padding): The modern standard for RSA encryption, built on top of two rounds of a Feistel-like construction using hash functions. It provides provable security against chosen-ciphertext attacks and is what current standards (like PKCS#1 v2.2) recommend.
• PSS (Probabilistic Signature Scheme): The modern standard for RSA signatures, offering a security proof that PKCS#1 v1.5 signatures lack.

The takeaway: RSA is not “encrypt with the formula” — it’s “encrypt with the formula, wrapped in a carefully designed padding scheme,” and getting the padding wrong has been the source of more real-world RSA vulnerabilities than the underlying math ever has.

Security Analysis and Threat Models

RSA’s security rests entirely on the assumption that factoring the product of two large primes is computationally infeasible with classical computers, for sufficiently large n. No one has proven this mathematically — it’s an assumption backed by decades of failed attempts by the world’s best mathematicians and the massive prize incentives (the RSA Factoring Challenge) that ran from 1991 to 2007.

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

• Randomness quality: If the random number generator used to choose p and q is weak or predictable, keys can be recovered directly, bypassing factoring entirely. Several real-world incidents (e.g., poorly seeded embedded devices generating shared factors between “independent” keys) have exploited exactly this.
• Correct padding implementation: As covered above.
• Side-channel resistance: Naive implementations that leak timing, power consumption, or cache-access patterns during the modular exponentiation in decryption can leak 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 any use requiring long-term security; deprecated since the early 2010s.
• 2048-bit: The current practical minimum, recommended by NIST through at least 2030.
• 3072-bit: Roughly equivalent to 128-bit symmetric security; recommended for longer-term protection.
• 4096-bit: Used where extra margin is wanted, at a real performance cost.

RSA operations get significantly slower as key size grows — decryption/signing (using the private exponent) is much more expensive than encryption/verification (using the small public exponent, especially with e=65537). This is why RSA is almost never used to encrypt bulk data directly; instead, it’s used to encrypt (or exchange) a much shorter symmetric key, which then does the heavy lifting with AES or ChaCha20 — the hybrid encryption approach used throughout TLS, PGP, and virtually every other RSA-based protocol.

A common optimization is decrypting via the Chinese Remainder Theorem (CRT): instead of computing C^d mod n directly, the implementation performs two smaller exponentiations modulo p and q separately and recombines the results, which is roughly 4x faster than the naive approach.

Implementation Considerations

• Never implement RSA padding yourself. Use audited cryptographic libraries (OpenSSL, libsodium, BoringSSL, or your language’s standard crypto library) rather than hand-rolling the math.
• 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 performing private-key operations, to avoid padding-oracle-style leaks.
• Consider whether you need RSA at all. For new systems without legacy compatibility constraints, ECC-based algorithms (see the Elliptic Curve Cryptography guide) generally offer equivalent security with dramatically smaller keys and faster operations.

Real-World Applications

• TLS/HTTPS: RSA has historically been used both for authentication (the certificate’s signature) and for key exchange, though modern TLS 1.3 deployments increasingly favor ECDHE for key exchange while RSA (or ECDSA) still commonly signs certificates.
• PGP/GPG and S/MIME: Email encryption and signing frequently rely on RSA key pairs, as covered in the PGP Hybrid Algorithm guide.
• SSH: RSA is one of several supported key types for authenticating SSH sessions.
• Code signing: Software publishers sign binaries and updates with RSA private keys so users’ systems can verify authenticity before installation.
• Digital certificates and PKI: Certificate Authorities use RSA (among other algorithms) to sign the certificates that underpin the web’s trust infrastructure.

RSA vs. Diffie-Hellman vs. ECC

It’s easy to conflate RSA with the other classic asymmetric algorithms on this site, but they solve related problems in different ways:

• RSA provides both encryption and signatures directly, based on the difficulty of integer factorization.
• Diffie-Hellman provides only key exchange (not general encryption or signing on its own), based on the difficulty of the discrete logarithm problem in a finite field.
• ECC re-implements the same discrete-logarithm-based ideas (key exchange via ECDH, signatures via ECDSA/EdDSA) on elliptic curves, achieving equivalent security to RSA with far smaller keys — a 256-bit ECC key offers roughly the same security as a 3072-bit RSA key.

In modern practice, RSA is gradually ceding ground to ECC for new deployments, largely due to ECC’s efficiency advantage, but RSA’s simplicity, maturity, and enormous existing deployment base mean it will remain relevant for a long time.

Quantum Computing and the Future of RSA

RSA’s security assumption — that factoring large numbers is intractable — only holds for classical computers. In 1994, mathematician Peter Shor published a quantum algorithm that can factor integers in polynomial time on a sufficiently large, fault-tolerant quantum computer, which would break RSA (along with Diffie-Hellman and ECC) completely.

No quantum computer built to date has anywhere near the scale or error-correction needed to run Shor’s algorithm against real-world RSA key sizes, but the threat is taken seriously enough that NIST has already standardized post-quantum replacements — lattice-based schemes like CRYSTALS-Kyber (for key encapsulation) and CRYSTALS-Dilithium (for signatures) — designed to resist quantum attacks. Organizations handling data that needs to stay confidential for decades are already planning migrations, since an adversary could record encrypted traffic today and decrypt it once a capable quantum computer exists (“harvest now, decrypt later”).

Practical Code Implementation

The following Python example implements RSA from scratch using small numbers purely for educational purposes — never use this code for real security, since it lacks padding, uses tiny insecure primes, and isn’t written to resist side-channel leaks.

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__":
    public_key, private_key = generate_keypair(bits=16)
    print(f"Public key:  {public_key}")
    print(f"Private key: {private_key}")

    message = 42
    ciphertext = encrypt(message, public_key)
    decrypted = decrypt(ciphertext, private_key)

    print(f"Original message:  {message}")
    print(f"Ciphertext:        {ciphertext}")
    print(f"Decrypted message: {decrypted}")
    assert message == decrypted

For production use, rely on established libraries instead — for example, Python’s cryptography package, which correctly handles padding, key generation, and side-channel protections:

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
    )
)

Frequently Asked Questions

Why is e usually 65537?

65537 (2¹⁶ + 1) is prime, has only two bits set in binary (making exponentiation fast via square-and-multiply), and is large enough to avoid the low-exponent attacks that smaller values like e=3 are vulnerable to when padding is weak or absent.

Can RSA encrypt arbitrarily large messages?

No — a message must be represented as an integer smaller than the modulus n. This is exactly why RSA is used to encrypt short symmetric keys (or hashes, for signatures) rather than entire documents; bulk data is encrypted with a fast symmetric cipher like AES, and only that symmetric key is RSA-encrypted.

Is RSA still safe to use today?

Yes, with a sufficiently large key size (2048 bits minimum, 3072+ recommended for longer-term security) and modern padding (OAEP/PSS), RSA remains secure against all known classical attacks. Its long-term outlook is complicated by quantum computing, which is why standards bodies are actively transitioning toward post-quantum algorithms for new systems.

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

Encryption uses the recipient’s public key to scramble data that only their private key can unscramble. Signing uses the signer’s private key to produce a value that anyone can verify with the signer’s public key — proving authenticity and integrity rather than providing confidentiality.

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

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

How does RSA compare in speed to AES?

RSA is orders of magnitude slower than AES for equivalent amounts of data, which is why it’s used to protect a symmetric key rather than the data itself — the standard hybrid encryption pattern used throughout TLS, PGP, and similar systems.

Conclusion

RSA’s genius lies in turning a simple, almost playful observation about prime numbers — multiplication is easy, factoring is hard — into a system that underpins global digital trust. Nearly fifty years after its invention, it remains one of the most widely deployed cryptographic algorithms in the world, even as elliptic-curve alternatives and, eventually, post-quantum schemes gradually take over new deployments. Understanding RSA — its elegant math, its very real implementation pitfalls, and its looming quantum-era expiration date — is essential groundwork for understanding almost everything else in modern cryptography.

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.