RSA Encryption Explained: The Math Behind Your Security

What RSA Is and Why It Matters

RSA is the world's most widely deployed public-key cryptosystem. Named for its inventors — Ron Rivest, Adi Shamir, and Leonard Adleman — who published it in 1977, RSA solved a fundamental problem in cryptography that had existed since the field began: how do two parties communicate securely if they've never had the chance to exchange a secret key in advance?

Classical symmetric encryption (like AES) is fast and strong, but requires both parties to share the same key. If Alice wants to send Bob an encrypted message, she somehow needs to give Bob the decryption key — but if she could do that securely, she wouldn't need encryption to begin with. This is the key distribution problem, and for centuries it had no good solution.

RSA elegantly bypasses the problem with an asymmetric approach: two mathematically linked keys, where anything encrypted with one key can only be decrypted with the other. RSA's security rests on a mathematical problem that's easy in one direction and — as far as we currently know — computationally infeasible in the reverse direction: integer factorization.

The impact: RSA is the cryptographic foundation of HTTPS (the padlock in your browser), SSH key authentication, PGP email encryption, code signing, digital certificates, and dozens of other systems. Every time you visit a secure website, send encrypted email, or connect to a remote server via SSH, RSA (or its modern alternatives) is involved. Understanding RSA means understanding the mathematical backbone of internet security.

The Public/Private Key Concept

RSA generates a key pair: two mathematically related keys with a remarkable property — data encrypted with one key can only be decrypted with the other. They're related (generated together from the same mathematical process) but knowing one doesn't let you derive the other in any reasonable timeframe.

The public key is shared openly. Post it on your website, include it in email headers, publish it to a keyserver. Anyone can encrypt data with your public key.

The private key is kept absolutely secret. Never shared, ideally never exported from the device where it was generated. Only you have it.

The system enables two distinct operations:

Encryption: Alice wants to send Bob a secret message. She fetches Bob's public key (openly available) and encrypts the message. Now only Bob's private key can decrypt it — Alice herself can no longer read the message. Bob uses his private key to decrypt it.

Digital signing: Bob wants to prove he sent a message and that it hasn't been tampered with. He uses his private key to sign the message (producing a digital signature). Anyone with Bob's public key can verify the signature — confirm it came from someone with access to the corresponding private key (presumably Bob) and that the message hasn't changed.

These two operations — encryption and signing — are the foundation of all public key infrastructure. The elegance is that they solve both confidentiality (secret communication) and authentication (proof of identity) using the same mathematical structure.

The Math of RSA (Prime Factoring, Simplified)

RSA's security depends on the mathematical difficulty of factoring large integers — specifically, that multiplying two large prime numbers together is trivially easy, but reverting that multiplication (finding the original primes from the product) is computationally infeasible for sufficiently large numbers.

The intuition: Consider two prime numbers, 17 and 23. Their product is 391. If someone gives you 391 and asks for the two prime factors, you can work it out fairly quickly for small numbers. Now imagine that the two primes each have 1,000 digits. Their product has approximately 2,000 digits. Multiplying them takes milliseconds on a computer. Finding the original primes from the 2,000-digit product would take longer than the current age of the universe using the best known classical algorithms.

How RSA key generation works (simplified):

1. Choose two large prime numbers, p and q. (In practice, each is 1,000+ bits long for 2048-bit RSA.)
2. Calculate n = p × q. This n is the "modulus" — it's public.
3. Calculate Euler's totient: λ(n) = (p-1)(q-1). This is kept secret.
4. Choose the public exponent e (typically 65537, a prime for mathematical reasons).
5. Calculate the private exponent d, the modular multiplicative inverse of e modulo λ(n). This is the private key.
6. Publish (n, e) as the public key. Keep d secret. Destroy p, q, and λ(n).

Encryption: To encrypt a message m, compute c = m^e mod n. Anyone with the public key (n, e) can do this.

Decryption: To decrypt ciphertext c, compute m = c^d mod n. Only the holder of d (the private key) can do this.

The security relies on the fact that deriving d from the public key (n, e) requires factoring n into p and q — the hard problem. Even if you know the public exponent e and the modulus n, you cannot find d without the factors.

Key Sizes and Security Levels

The security of RSA scales with key size. The relationship between key size and effective security level (measured in "bits of security") is important to understand when choosing key lengths.

RSA-1024: Once the standard, now insecure. NIST deprecated RSA-1024 for use after 2013. Several academic factoring records have approached the range that makes 1024-bit RSA plausibly attackable by well-resourced adversaries. Do not use RSA-1024 for any security-critical purpose.

RSA-2048: The current minimum recommendation. Provides approximately 112 bits of security, adequate through approximately 2030 by most estimates. RSA-2048 is the dominant key size in TLS certificates and SSH keys today.

RSA-3072: Provides approximately 128 bits of security, roughly equivalent to AES-128. Recommended for applications requiring security beyond 2030.

RSA-4096: Provides approximately 140 bits of security. Used by security-conscious organizations and individuals who want significant safety margins. The performance overhead over RSA-2048 is real but modest for most applications.

An important context note: the "bits of security" measure for RSA is lower than the key length. RSA-2048 offers 112 bits of security — not 2048 bits. Compare this to AES-256, which offers 256 bits of security. AES-256 is vastly more computationally secure per bit of key material. RSA uses long keys to compensate for the mathematical structure that makes key recovery easier than brute force.

How RSA Is Used Today (TLS, SSH, Email)

RSA's primary modern uses are key exchange and authentication — not bulk data encryption. RSA is slow compared to symmetric ciphers, making it impractical for encrypting large amounts of data directly.

TLS (HTTPS): When your browser connects to an HTTPS website, there's a TLS handshake. Historically, RSA was used to establish the session — the browser would use the server's public key (from its certificate) to encrypt a session key. Modern TLS 1.3 uses elliptic curve Diffie-Hellman for key exchange instead (providing forward secrecy), and RSA is now used primarily to sign the certificate, not for key exchange. The server's RSA private key signs data confirming its identity.

SSH key authentication: When you use SSH keys instead of passwords to authenticate to a remote server, you're using either RSA or modern key types. The server stores your public key in ~/.ssh/authorized_keys. When you connect, you prove you hold the corresponding private key by using it to sign a challenge. The server verifies the signature with your public key. RSA-4096 or Ed25519 (elliptic curve) are current recommendations for SSH key generation.

Email encryption (PGP/GPG): PGP uses RSA (or more modern elliptic curve algorithms) for key pairs. Your PGP identity has a public key that others encrypt messages to and verify your signatures with, and a private key for decryption and signing. The email message content is typically encrypted with a symmetric cipher (AES) using a session key, and only that session key is RSA-encrypted — a hybrid approach that combines RSA's asymmetry with AES's speed.

Code signing: Software publishers sign compiled code with their private key. Operating systems and app stores verify the signature before installing. This ensures that software hasn't been tampered with after it left the publisher's hands.

RSA Limitations and Where It's Being Replaced

RSA has some meaningful limitations driving its gradual replacement in newer protocols.

Size vs security inefficiency. As described above, RSA requires very long keys for equivalent security to modern algorithms. A 256-bit elliptic curve key provides comparable security to RSA-3072. This size differential matters in practice: mobile devices, embedded systems, and high-volume services see meaningful performance improvements from switching to elliptic curve cryptography.

No forward secrecy from RSA alone. If you use a static RSA key pair for key exchange (as was done in TLS 1.2's RSA key exchange mode), a future compromise of the private key allows decryption of all past recorded traffic. Modern protocols mandate Ephemeral Diffie-Hellman (ECDHE) for key exchange, limiting historical exposure. TLS 1.3 makes ephemeral key exchange mandatory.

Padding oracle and implementation vulnerabilities. RSA's practical security depends heavily on correct implementation. PKCS#1 v1.5 padding (older standard) has well-documented vulnerabilities including ROBOT attack and Bleichenbacher's attack. OAEP padding is the correct modern choice for RSA encryption. Getting RSA right is hard; newer algorithms like X25519 (for key exchange) and Ed25519 (for signatures) are harder to misimplement.

Performance at scale. RSA operations are CPU-intensive. For high-volume servers handling millions of TLS connections per hour, ECDSA (elliptic curve digital signature algorithm) provides comparable security with substantially less computational load.

Post-Quantum Implications

RSA's security rests on the hardness of integer factorization for classical computers. A sufficiently powerful quantum computer running Shor's algorithm could factor large integers in polynomial time, breaking RSA entirely.

While general-purpose quantum computers capable of breaking RSA-2048 don't currently exist, the threat is taken seriously enough that NIST (National Institute of Standards and Technology) completed a multi-year post-quantum cryptography standardization project, selecting several quantum-resistant algorithms in 2024:

• ML-KEM (CRYSTALS-Kyber) for key encapsulation (replacing ECDHE and RSA for key exchange)
• ML-DSA (CRYSTALS-Dilithium) and SLH-DSA (SPHINCS+) for digital signatures (replacing ECDSA and RSA signatures)

Major protocol stacks are adopting these algorithms. TLS 1.3 supports hybrid key exchange combining existing algorithms (for classical security) with post-quantum algorithms (for quantum-computer resistance). Signal adopted a hybrid X3DH/PQXDH key agreement in 2023. Chrome has been conducting hybrid post-quantum TLS experiments since 2023.

The timeline for "harvest now, decrypt later" attacks is the real driver of urgency. Adversaries with the resources may already be recording encrypted internet traffic today, waiting for quantum computers capable of breaking the encryption to become available years from now. Data that needs to remain confidential for more than 10 years — classified government information, medical records, legal documents — faces a real quantum threat even though the computers don't yet exist.

For individuals, the practical implication is straightforward: use software that is actively post-quantum-aware (Signal, modern TLS-capable browsers, and operating systems) and watch for software updates that incorporate NIST post-quantum standards. RSA will remain secure for classical attackers for years to come, but its days as a long-term cryptographic foundation are numbered.