☕ Buy me a coffee — $3

RSA (Rivest-Shamir-Adleman)

Overview

RSA is an asymmetric cryptographic algorithm named after its inventors: Ron Rivest, Adi Shamir, and Leonard Adleman. It's one of the first public-key cryptosystems and is widely used for secure data transmission, digital signatures, and key exchange.

RSA's security is based on the mathematical difficulty of factoring large composite numbers into their prime factors. The algorithm uses a public key for encryption and a private key for decryption, enabling secure communication without sharing secret keys.

Almost every technology built on modern cryptography has an RSA implementation somewhere in its history, and many of them still have one. TLS certificates in the browser bar, PGP-signed emails, SSH keys, code-signing certificates, JWTs, TOTP-based two-factor codes, cryptocurrency wallets in their original forms, every one of these was, at some point, built on RSA. The algorithm's role has narrowed over the past decade as elliptic-curve cryptography matured, and its role will narrow further as post-quantum standards displace it, but RSA remains the most widely-deployed asymmetric algorithm in the world and the standard example for teaching how public-key cryptography works.

The Invention of Public-Key Cryptography

RSA was the first published practical public-key cryptosystem, but it was not the first to be invented. The idea of asymmetric encryption, a mathematical scheme in which encrypting and decrypting use different keys, so that the encrypting key can be made public without revealing the decrypting key, was first described in a 1976 paper by Whitfield Diffie and Martin Hellman titled "New Directions in Cryptography." Diffie and Hellman's paper set out the concept and gave a concrete key-exchange protocol (now called Diffie–Hellman) but did not provide a full encryption scheme; they left open the question of whether such a scheme was actually possible.

Ron Rivest, Adi Shamir and Leonard Adleman, all at MIT, spent the following year searching for a mathematical trapdoor function that could provide the missing piece. Rivest and Shamir proposed candidate schemes and Adleman, the mathematician of the group, broke them; this loop continued through the spring of 1977 as they worked through dozens of ideas. The breakthrough came in April 1977, when Rivest described what would become the RSA algorithm to Shamir and Adleman over Passover dinner. Adleman's initial reaction was that it would probably not work either, but by morning he had failed to break it, and by the summer of 1977 the three had published a technical memo, and in August 1977 Martin Gardner published a description of the algorithm in his Mathematical Games column in Scientific American, including a challenge ciphertext that Gardner offered $100 for anyone who could decrypt. (The RSA-129 challenge was eventually broken in 1994 through a distributed computation involving 600 volunteers over eight months.)

The 1977 paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" was published in the Communications of the ACM in February 1978. It described RSA encryption, RSA signatures, and the entire framework of modern asymmetric cryptography in essentially the form it still uses today. Rivest, Shamir and Adleman won the Turing Award for this work in 2002.

A historical footnote: it later emerged that Clifford Cocks, working at the British intelligence agency GCHQ, had independently invented the same algorithm in 1973, three years before Diffie and Hellman's paper and four years before RSA published theirs. Cocks's work was classified as a state secret and was not publicly acknowledged until 1997. So RSA was independently invented twice; the world learned of the second invention first.

Why the Math Works

RSA's mathematical foundation is beautifully compact, and understanding it is worth the effort. The algorithm rests on a single theorem from 18th-century mathematics, Euler's theorem, published by Leonhard Euler in 1763, combined with the observation that certain computations are easy in one direction and (apparently) exponentially hard in the other.

Euler's theorem. For any integer a that is coprime to a positive integer n, aφ(n) ≡ 1 (mod n), where φ(n) is Euler's totient, the count of integers less than n that are coprime to n. When n = p·q for two distinct primes p and q, φ(n) = (p−1)(q−1).

The RSA trick. If we choose e with gcd(e, φ(n)) = 1 and set d = e−1 mod φ(n), then e·d ≡ 1 (mod φ(n)), which means e·d = k·φ(n) + 1 for some integer k. Now for any message m < n: 

(me)d = me·d = mk·φ(n) + 1
                  = (mφ(n))k · m
                  ≡ 1k · m  (mod n)     [by Euler's theorem]
                  ≡ m (mod n)

So encrypting m as me mod n and then decrypting as (me)d mod n gets us back to m. That is the entire algorithm. Everything else is engineering.

Why this is secure. Anyone with the public key (n, e) can encrypt. Decryption requires d, which requires φ(n), which requires knowing p and q, which requires factoring n. Factoring a random n = p·q where p and q are 1024-bit primes is, as far as we know, infeasible for classical computers. The fastest known algorithm, the General Number Field Sieve, takes sub-exponential time in the size of n, roughly exp(1.9 · (log n)1/3 · (log log n)2/3). For a 2048-bit n, that is around 2112 operations, which is far outside what any current or foreseeable classical computer can do.

The critical caveat. Shor's algorithm, published by Peter Shor in 1994, factors integers in polynomial time on a quantum computer. This means RSA is "quantum-vulnerable", a sufficiently large quantum computer would break every RSA key ever generated. Current quantum computers are nowhere near large enough to factor a 2048-bit RSA key, but the threat is real enough that the US and other governments have set migration deadlines to post-quantum cryptography over the coming decade. See the post-quantum cryptography section in the encryption overview.

How It Works

  1. Key Generation:
    • Choose two large prime numbers p and q
    • Calculate n = p × q
    • Calculate φ(n) = (p-1) × (q-1)
    • Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
    • Calculate d such that (d × e) mod φ(n) = 1
    • Public key: (n, e), Private key: (n, d)
  2. Encryption: c = m^e mod n
  3. Decryption: m = c^d mod n

Important: what is written above is textbook RSA, and textbook RSA is insecure. It is deterministic, so identical messages produce identical ciphertexts and an attacker can simply encrypt guesses and compare. It is also malleable: multiplying a ciphertext by se multiplies the plaintext by s, without the key. Real RSA encryption always applies a randomized padding scheme, OAEP, and real RSA signatures use PSS. Never implement the bare modular exponentiation above and ship it.

One further note on the maths: modern standards (FIPS 186-5, PKCS#1 v2.2) compute d using the Carmichael function λ(n) = lcm(p−1, q−1) rather than Euler's φ(n). Both yield a working key; λ(n) gives the smallest valid d.

RSA Algorithm


RSA_KeyGeneration():
    p, q = generate_large_primes()
    n = p * q
    φ(n) = (p - 1) * (q - 1)
    e = choose_public_exponent(φ(n))
    d = modular_inverse(e, φ(n))
    return (n, e), (n, d)

RSA_Encrypt(message, public_key):
    (n, e) = public_key
    return message^e mod n

RSA_Decrypt(ciphertext, private_key):
    (n, d) = private_key
    return ciphertext^d mod n

Implementation


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

def generate_rsa_keys(key_size=2048):
    """Generate RSA key pair"""
    private_key = rsa.generate_private_key(
        public_exponent=65537,
        key_size=key_size,
    )
    public_key = private_key.public_key()
    return private_key, public_key

def rsa_encrypt(message, public_key):
    """Encrypt message using RSA public key"""
    ciphertext = public_key.encrypt(
        message,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return ciphertext

def rsa_decrypt(ciphertext, private_key):
    """Decrypt message using RSA private key"""
    plaintext = private_key.decrypt(
        ciphertext,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return plaintext

# Example usage
private_key, public_key = generate_rsa_keys()
message = b"Hello, RSA Encryption!"
ciphertext = rsa_encrypt(message, public_key)
decrypted = rsa_decrypt(ciphertext, private_key)

Security

RSA security depends on:

  • Key Size: Larger keys provide more security but slower operations
  • Prime Generation: Primes must be truly random and large
  • Implementation: Proper padding (OAEP) is essential

Recommended key sizes:

  • 1024 bits: disallowed. Not a "minimum", NIST SP 800-131A Rev. 2 withdrew it for signature generation after 2013, and SP 800-57 Part 1 Rev. 5 sets 2048 as the floor. Treat a 1024-bit key as broken.
  • 2048 bits: today's minimum, roughly 112 bits of security. NIST IR 8547 (draft) proposes deprecating RSA-2048 after 2030 and disallowing it after 2035.
  • 3072 bits: ~128 bits of security. The right choice for anything that must stay secure past 2030.
  • 4096 bits: higher classical margin, but note that RSA operations scale badly, doubling the modulus roughly eight-folds the private-key cost.

No RSA key size is quantum-resistant. Shor's algorithm factors integers in polynomial time, so a sufficiently large quantum computer breaks RSA-4096 as readily as RSA-2048. Calling large keys "future-proof" is misleading. The migration path is post-quantum cryptography, see the post-quantum section in the encryption overview.

Applications

  • Digital signatures: the main modern use. Certificate signing, code signing, document authentication, use RSA-PSS for new designs.
  • TLS certificates: RSA still signs a large share of the web's certificates.
  • Email encryption: PGP, S/MIME.
  • Legacy key transport: older protocols encrypt a symmetric key under an RSA public key.

RSA is no longer used for key exchange in modern TLS. TLS 1.3 (RFC 8446, 2018) removed RSA key transport entirely, because it provides no forward secrecy: anyone who later obtains the server's private key can decrypt every past session they recorded. TLS 1.3 key agreement is ephemeral Diffie-Hellman, ECDHE, in practice X25519, and browsers now default to the hybrid post-quantum group X25519MLKEM768. RSA's role in a modern handshake is to sign, not to transport keys.

RSA also cannot encrypt bulk data. A 2048-bit key with OAEP-SHA256 can encrypt at most 190 bytes. Real systems use hybrid encryption: generate a random AES key, encrypt the data with AES-GCM, and encrypt only that key with RSA.

Related Algorithms

Explore other encryption algorithms: