How RSA works, without the number theory

Before RSA, exchanging encrypted messages meant already sharing a secret. That is symmetric cryptography: one key, held at both ends, that scrambles and unscrambles.

The cipher was never the hard part. Getting the key to the other end was. Any channel you could send it over is a channel somebody could be reading.

RSA is asymmetric: two linked keys. You publish one, the public key, keep the other, the private key, and what one does only the other can undo.

Hand out open padlocks and keep the only key. Anyone can snap one shut on a box and post it to you; nobody, the sender included, can open it again.

Run that backwards and you get the half people forget. Use the private key first and anyone with the public key can undo it.

Nothing stays secret, since everyone holds the public key, but only the private key could have produced it. That is a digital signature, and it is where almost all of RSA's remaining work happens.

RSA is named for Rivest, Shamir and Adleman, who described it in 1977 and published in February 1978.

Clifford Cocks had written down an equivalent scheme in 1973 at GCHQ, the UK's signals intelligence agency, where it stayed classified until 1997.

The trapdoor and the two exponents

Multiplying two large primes is easy. Taking the product back apart into those primes is not. That gap is the whole thing.

Key generation picks two large distinct random primes, p and q, and multiplies them into the modulus n. The length of n is what "a 2048-bit RSA key" measures.

The public key is the pair (e, n), where e is the public exponent. The private key is (d, n), where d is the private one.

Encrypting a message m is m^e mod n, and mod is clock arithmetic: 17 mod 12 = 5.

Raising a number to a power and keeping only the remainder is modular exponentiation, a trapdoor one-way function: easy forwards, hard backwards, easy backwards if you hold a secret.

The secret is the primes: knowing p and q gives you d, and without them you would have to factor n. Factoring is not the one-way function itself. It is the hard problem that makes modular exponentiation impractical to reverse.

Those are not abstractions. Inspect a generated 3072-bit private key and OpenSSL prints those same numbers: the modulus, the public exponent, the private exponent and both primes.

The commands for generating a key and reading it back are in OpenSSL commands worth remembering.

The public exponent is 65537 almost everywhere, and the reason is written down: FIPS 186-5, the US federal digital signature standard, requires 2^16 < e < 2^256, so 65537 is the smallest value the standard permits, and the popular e = 3 is out.

Key length buys difficulty, and it is running out

The 1978 paper recommended a modulus of about 664 bits and estimated 3.8 × 10^9 years to factor one.

RSA-250, an 829-bit number from RSA's old public factoring challenge, fell in February 2020 to CADO-NFS, an open-source factoring program, at roughly 2700 core-years: one CPU core running for 2700 years, or a large academic cluster for a few months, which is what happened.

The record is now RSA-260, 862 bits, announced by Eric Lu on 3 September 2026 with no method published. The inventors' own recommended size is broken.

Security strength in bits is the yardstick for comparing unlike algorithms. NIST, the US standards body whose cryptography publications the rest of the industry follows, maps modulus length onto it.

SP 800-57 Part 1 Revision 5 gives the numbers: 1024 gives 80 bits or less, 2048 gives 112, and 3072 gives 128, the same as AES-128.

AES is the Advanced Encryption Standard, the symmetric cipher that does the bulk encryption once the keys are agreed. 4096 is not on that list at all, so it buys no standardised tier over 3072.

Use 3072 for a new key, not the 4096 everybody reaches for.

1024 bits is disallowed, which is a NIST term of art. Deprecated means you may use it if you accept the risk; disallowed means you may not.

SP 800-131A Rev 2 puts RSA between 1024 and 2048 bits in that second bucket, where all it may do is verify old signatures.

Nor is 3072 a long-term answer. NIST IR 8547, an initial public draft from November 2024, deprecates 112-bit strength after 2030 and disallows it after 2035.

Everything at 128 bits or above, 3072 and 4096 included, is disallowed after 2035 too.

Raw RSA is broken

Handing data straight to that arithmetic gives you textbook RSA, which is deterministic: an attacker who can guess your plaintext confirms the guess by encrypting it.

The fix is a padding scheme, which turns your data into a formatted, randomised block before the maths runs.

For encryption that means OAEP, Optimal Asymmetric Encryption Padding, required for new applications by RFC 8017, one of the numbered specification documents that define how the internet works.

The older padding in that same standard, PKCS #1 v1.5, survives only for compatibility: Bleichenbacher-style attacks recover plaintext from it without the private key, and NIST disallowed it for key transport after 31 December 2023.

For signatures, prefer PSS, the Probabilistic Signature Scheme. It is randomised, so signing a file twice gives two different signatures, and what gets exponentiated is an encoded block holding the hash: a fixed-length fingerprint of the message, and the thing you sign instead of the file.

But v1.5 signatures are not a vulnerability the way v1.5 encryption is, and TLS 1.3 still permits them in certificates. TLS is Transport Layer Security, the protocol that encrypts web traffic.

RSA also cannot encrypt much.

RFC 8017 caps OAEP at the modulus size minus twice the hash length minus two bytes, so a 2048-bit key with SHA-256 tops out at 190 bytes; feed it 191 and OpenSSL fails with data too large for key size. That limit is why hybrid encryption exists: generate a random symmetric key, encrypt the data with AES-GCM, the mode that also detects tampering, and use RSA on the key alone.

What RSA actually does in HTTPS

RSA does not carry the session key for your HTTPS connection, though nearly every explanation of RSA says it does.

SSL is TLS's obsolete predecessor whose name stuck; HTTPS is HTTP inside TLS. A certificate binds a public key to a domain name, signed by a Certificate Authority whose own key ships in your browser's trust store.

A session key is the temporary symmetric key encrypting a connection's bytes, and key exchange is how two parties end up with the same one without sending it.

RSA used to do that last job: the browser encrypted a secret with the server's public key. RFC 8446 removed those static RSA cipher suites from TLS 1.3 outright in 2018.

What replaced them is ephemeral Diffie-Hellman, where the two sides derive a shared secret from fresh values neither of them sends, plus pre-shared keys.

RFC 10015 finished the job for TLS 1.2 in July 2026: clients must not offer static RSA, servers must not select it.

The reason is forward secrecy: stealing a server's private key tomorrow must not decrypt traffic recorded last year, and RSA key transport cannot promise it.

What is left for RSA is signing, in two places: the CA's signature on the certificate, and the server's CertificateVerify signature proving it holds that certificate's private key.

RFC 9325 requires at least a 2048-bit modulus there, so RSA is still accepted everywhere certificates are, just not as an encryptor. Read the exchange below and watch which arrows are signatures and which produce the session key.

X25519 is the elliptic-curve version of the Diffie-Hellman agreement above.

SSH, commits and packages all sign, often not with RSA

SSH, the Secure Shell protocol for logging into remote machines, uses only the signature direction: the server sends a challenge, the client signs it, and the server checks it against the public keys in ~/.ssh/authorized_keys.

The key type has moved. Older tutorials say your private key is ~/.ssh/id_rsa; it is not, unless you asked for that. OpenSSH 8.8 turned off RSA signatures that use SHA-1 and retired the ssh-rsa name.

Since OpenSSH 9.5, released 4 October 2023, ssh-keygen has generated Ed25519 keys by default. Ed25519 is elliptic-curve cryptography: much smaller keys for the same strength. It signs; X25519, from the same family, agrees on a key.

"RSA/GPG key", the phrase that floats around git commit signing, is a category error. OpenPGP is a standard for keys and signatures, GPG the usual implementation, and an OpenPGP key can be RSA or elliptic-curve.

Git's gpg.format takes openpgp by default plus x509 and ssh, and that third value lets you sign with the Ed25519 key you already have.

Two prerequisites nobody mentions: git verify-commit fails on your own valid signature until gpg.ssh.allowedSignersFile lists the keys you trust, and GitHub shows Unverified until you upload that key.

The package managers APT, on Debian and Ubuntu, and RPM, on Fedora and Red Hat Enterprise Linux, run the same mechanism at scale: one signature on repository metadata covers a whole tree of packages pulled from mirrors nobody has reason to trust. That is OpenPGP again rather than RSA by design, though Debian's archive keys happen to be RSA-4096.

The signature proves two things: the metadata came from the repository whose key you trust, and it reached you unaltered. It proves nothing about whether the software is benign.

The same caveat applies when you sign a container image.

What a signature proves, and what replaces RSA

NIST defines non-repudiation as assurance of the integrity and origin of data, verifiable as having come from an entity in possession of the private key.

In possession of the private key, not authored by a particular person. Stolen laptops, forwarded SSH agents and continuous integration runners all break the inference to a human.

Keep the key where it cannot be copied: an HSM, a hardware security module that signs without the key entering ordinary memory. Failing that, chmod 600 and a passphrase raise the cost of a copy without preventing one.

RSA remains the right answer wherever something else already requires it: an enterprise CA that issues nothing else, hardware too old to know about elliptic curves, an established Public Key Infrastructure.

A PKI is the set of CAs, certificates and policies that decide which public keys get believed.

For anything greenfield, a new system with no legacy compatibility to preserve, prefer Ed25519 for signatures and X25519 for key agreement: smaller keys, faster handshakes.

Shor's algorithm, published by Peter Shor in 1997, factors integers quickly on a quantum computer large enough to run it, which would end RSA rather than weaken it.

The post-quantum replacements, algorithms believed safe against one, already exist: NIST published FIPS 203 (ML-KEM, for key establishment), FIPS 204 (ML-DSA, for signatures) and FIPS 205 (SLH-DSA, hash-based) as final standards on 13 August 2024.

The padlock still works, and RSA signatures are still in daily use.

But the RFCs legislated the encryption half out of TLS, OpenSSH moved its default off RSA, and the draft timetable disallows every RSA key length after 2035.

Signing is what is left, and that draft puts a date on it.