How RSA Works: Public Keys, Trapdoors, and Factoring

Before public-key cryptography, two people who wanted to talk in private had a chicken-and-egg problem: they needed a shared secret key to encrypt, but sharing that key safely required a secure channel they did not yet have. RSA, published in 1977 by Rivest, Shamir, and Adleman, was the first practical answer. It lets you publish a key to the whole world and still keep a secret. That idea underpins HTTPS, code signing, and encrypted email.

RSA is a public-key (asymmetric) system. You generate a pair of mathematically linked keys. One is public and you can hand it to anyone. One is private and you guard it. What one key does, only the other can undo. That asymmetry is the whole trick.

The two things a keypair does

A keypair supports two complementary operations, and it helps to keep them separate in your head.

Encryption to you. Anyone encrypts a message with your public key. Only your private key can decrypt it. This delivers confidentiality without a pre-shared secret.
Signing by you. You sign a message with your private key. Anyone verifies the signature with your public key. This proves the message came from you and was not altered.

The same keypair, run in two directions. Encryption uses the public key to lock and the private key to unlock. Signing uses the private key to lock and the public key to unlock.

The trapdoor: easy one way, hard the other

Public-key crypto needs a mathematical operation that is easy to compute but hard to reverse, unless you hold a secret. Cryptographers call this a trapdoor. RSA's trapdoor is integer factorisation.

Here is the intuition without the algebra:

Pick two large prime numbers, call them p and q. Each might be 1024 bits or more.
Multiply them to get a modulus n. Multiplication is fast, even for huge numbers.
Your public key is built from n. Your private key depends on knowing p and q.

The security bet is that going backwards, taking n and recovering the original primes p and q, is computationally infeasible when the primes are large enough. Multiplying two thousand-bit primes takes microseconds. Factoring their two-thousand-bit product would take the best known algorithms far longer than the age of the universe on current hardware. That gap between easy-forward and hard-backward is what protects the private key.

Anyone with your public key can multiply and encrypt. Only someone who knows the factors can efficiently decrypt. The factors are the trapdoor.

Why RSA does not encrypt your files directly

RSA can only encrypt data smaller than its modulus, and it is orders of magnitude slower than a symmetric cipher like AES. So RSA is used to encrypt a short random symmetric key, and that symmetric key encrypts the actual data. This hybrid pattern is how TLS and encrypted email work in practice.

Key sizes and what they buy

RSA key size is the length of the modulus n in bits. Bigger keys are harder to factor and slower to use. The tradeoff is real, so pick deliberately.

Key size	Status	Use it for
1024-bit	Deprecated, considered breakable	Legacy only, migrate away
2048-bit	Current minimum	General use, most TLS certificates
3072-bit	Stronger margin	Longer-lived keys, higher assurance
4096-bit	Conservative	Long-term secrets, root and CA keys

NIST guidance treats 2048 bits as the floor for new keys and points to 3072 bits for security that should last well into the future. Doubling the key size more than doubles the cost of operations, so servers under load feel the difference. This performance cost is one reason elliptic curve cryptography has become popular: it reaches comparable strength with far smaller keys. See How Elliptic Curve Cryptography Works.

Padding is not optional

Plain "textbook" RSA, where you feed the raw message straight into the math, is insecure. It is deterministic (the same message always encrypts to the same ciphertext), it leaks structure, and it falls to several classic attacks. Real RSA always wraps the message in a padding scheme that adds randomness and structure.

For encryption, use OAEP (Optimal Asymmetric Encryption Padding). It randomises the ciphertext and blocks chosen-ciphertext attacks.
For signatures, use PSS (Probabilistic Signature Scheme). The older PKCS#1 v1.5 signature padding is still seen in the wild but PSS is the modern recommendation.

If a library or config asks you to choose and you are not sure, OAEP for encryption and PSS for signatures are the safe defaults. Raw RSA is a footgun.

How to use RSA safely

You will almost never implement RSA yourself. The job is to configure it correctly and hold the private key tightly.

Generate at least 2048-bit keys, prefer 3072 for anything long-lived. Do not create new 1024-bit keys.
Always use OAEP for encryption and PSS for signatures. Reject any tooling that only offers unpadded RSA.
Protect the private key like the crown jewels. Store it in a hardware security module or a secrets manager, restrict file permissions, and never commit it to a repo.
Use RSA to move a symmetric key, then let AES do the bulk work. This is faster and is the standard hybrid design. See Symmetric vs Asymmetric Encryption.
Rotate keys and set sensible certificate lifetimes. A stolen private key with a ten-year validity is a decade-long problem.

Weak key sizes, missing padding, and leaked private keys all surface as tracked vulnerabilities. You can see how public-key weaknesses turn into real CVEs on our Exploit Intelligence dashboard, which underlines how often the failure is a configuration choice rather than a flaw in the math.

The quantum question, kept honest

RSA's security depends on factoring being hard. A large, fault-tolerant quantum computer running Shor's algorithm could factor the modulus efficiently, which would break RSA. That machine does not exist today, and credible estimates for when it might arrive vary widely, so treat confident timelines with suspicion. The practical response is to inventory where you rely on RSA and plan a migration to post-quantum algorithms as NIST standards mature. The concern is real and worth preparing for, without panic. See Post-Quantum Cryptography Explained.

RSA has served for nearly fifty years because its core bet, that factoring large numbers is hard, has held against classical attack. Deploy it with modern key sizes and padding, guard the private key, and use it for what it is good at: establishing keys and proving identity. Let a symmetric cipher carry the data.

A worked example with small numbers

The real algorithm uses numbers hundreds of digits long, which are impossible to follow by hand. The mechanics are identical at any size, so it helps to watch them run on tiny primes. These numbers are a standard teaching example and they are far too small to be secure, but they show every step.

Start with key generation:

Pick two primes. Say p is 61 and q is 53.
Multiply them to get the modulus. Here n is 61 times 53, which is 3233.
Compute the totient, the count of numbers below n that share no factor with it. For two primes it is (p minus 1) times (q minus 1), so (60 times 52) equals 3120.
Choose a public exponent e that shares no common factor with the totient. A common choice is 65537, but for this small example take e as 17.
Compute the private exponent d as the modular inverse of e with respect to the totient. That means the d for which e times d leaves a remainder of 1 when divided by 3120. For e equal to 17 that d is 2753, because 17 times 2753 is 46801, and 46801 divided by 3120 leaves a remainder of 1.

The public key is now the pair (n equals 3233, e equals 17). The private key is d equals 2753, held alongside n. The primes p and q have done their job and should be discarded or protected, because anyone who recovers them can recompute d.

Now encrypt. Represent the message as a number m smaller than n. Take m equal to 65. The ciphertext c is m raised to the power e, reduced modulo n:

c = 65^17 mod 3233 = 2790

To decrypt, raise the ciphertext to the private exponent d, again modulo n:

m = 2790^2753 mod 3233 = 65

The original 65 comes back. Signing runs the same machinery in reverse. The holder of the private key raises a value to d to produce a signature, and anyone raises that signature to the public e to recover the value and check it. Notice that no step other than finding d ever needs the primes. The security of the whole scheme is the difficulty of getting from n back to p and q, which for 3233 is trivial and for a 2048-bit modulus is the wall that has held for decades.

Why the math actually reverses

The reason encryption and decryption undo each other is a result from number theory. Raising a number to the power e and then to the power d, all modulo n, returns the original number whenever e times d is congruent to 1 modulo the totient of n. That congruence is exactly the relationship key generation set up when it computed d as the inverse of e. Euler's theorem guarantees that a number raised to the totient is congruent to 1 modulo n, so the extra full multiples of the totient hidden inside the exponent e times d fall away and leave the input unchanged. You do not need to work the proof to use RSA, but the shape of it explains why the two exponents are locked together and why knowing the totient, which requires knowing p and q, is enough to derive the private key.

Modular exponentiation, the operation at the center of both directions, is fast even on enormous numbers because it can be done by repeated squaring rather than by multiplying the base out in full. That efficiency is what makes RSA practical to compute while factoring the modulus stays infeasible. The forward direction and the trapdoor direction sit on opposite sides of that computational gap.

How RSA breaks when it is misused

The factoring problem has held, so almost every real RSA failure comes from a mistake in how the algorithm is deployed rather than a break in the core math. The recurring classes are worth knowing because they explain why the safe-usage rules exist.

No padding. Textbook RSA is deterministic and malleable. Because the same plaintext always yields the same ciphertext, an attacker can recognise repeated messages and, for a small message space, simply encrypt every candidate and compare. OAEP exists to close this.
Padding oracles. Older PKCS#1 v1.5 encryption padding gives an attacker who can submit ciphertexts and observe whether the padding was valid a way to recover plaintext one query at a time. This is the Bleichenbacher class of attack. Constant-time handling and modern padding are the response.
Small or shared exponents. A very small public exponent combined with no padding can let an attacker recover a message sent to several recipients, or one that is short relative to the modulus, by taking an ordinary integer root. Padding and a sensible exponent close the gap.
Weak randomness in key generation. If two keys are generated with a faulty random source and happen to share one prime factor, the shared factor can be found by taking the greatest common divisor of the two moduli, which instantly factors both. Good entropy at generation time is not optional.
Side channels. The time or power a device spends on a private-key operation can leak bits of the key if the implementation is not constant-time. This is an implementation flaw rather than a flaw in RSA, which is one more reason to use a vetted library.

The algorithm is rarely the weak point

When RSA fails in the field, the cause is almost always a deployment choice: missing padding, a leaked or reused private key, weak entropy at key generation, or a timing leak in a hand-rolled implementation. The factoring problem itself has resisted classical attack for decades. Treat any advice to implement RSA yourself, or to skip padding for speed, as a red flag.

RSA compared with elliptic curve cryptography

RSA is one of two public-key families in wide use. The other, elliptic curve cryptography, rests on a different hard problem and reaches comparable strength with much smaller keys. The comparison clarifies when each fits.

Property	RSA	Elliptic curve (ECC)
Hard problem	Integer factorisation	Elliptic curve discrete logarithm
Key size for similar strength	3072-bit	256-bit
Key generation speed	Slower	Faster
Signing speed	Slower	Faster
Verification speed	Fast	Moderate
Ciphertext and signature size	Larger	Smaller
Maturity and ubiquity	Very high, decades of deployment	High and growing
Quantum exposure	Broken by Shor's algorithm	Also broken by Shor's algorithm

The practical takeaway is that ECC delivers the same security level with less data on the wire and less computation, which is why newer systems and constrained devices lean on it. RSA remains everywhere because the installed base is enormous and its behaviour is well understood. Both fall to a sufficiently large quantum computer, so neither is a long-term answer to that specific threat. See How Elliptic Curve Cryptography Works for the other side of this table.

How RSA fits into TLS and signatures

In a TLS handshake, RSA historically played one of two roles. In older key-transport handshakes the client generated a symmetric secret, encrypted it with the server's RSA public key, and sent it over, so only the server could decrypt it. Modern TLS prefers ephemeral key exchange for forward secrecy and uses RSA mainly to sign the handshake, proving the server holds the private key that matches its certificate. Either way the pattern from earlier holds: RSA establishes trust and moves a small secret, and a symmetric cipher such as AES then carries the actual data.

Digital signatures follow a similar division of labour. You never sign a large document directly with RSA. You hash the document to a fixed-size digest with a function such as SHA-256, then sign the digest with PSS padding. A verifier hashes the document the same way and checks the signature against that hash. This is why a signature stays small no matter how large the signed file is, and why the strength of a signature depends on both the RSA key and the hash function behind it. See How Digital Signatures Work for the full flow.

Common misconceptions

A few beliefs about RSA cause real mistakes.

"A longer key is always better." Beyond a point, larger keys buy little extra security while costing meaningful performance. A 4096-bit key is sensible for long-lived roots, but pushing every TLS server to 8192 bits mostly adds latency.
"RSA encrypts my files." RSA encrypts a short symmetric key, and that key encrypts the files. The size limit and the speed cost make direct bulk encryption impractical.
"If I have MFA I do not need to worry about key theft." The private key is the identity. A stolen private key lets an attacker impersonate the server or user until the key is revoked, regardless of other controls.
"Textbook RSA is fine for a quick internal tool." Unpadded RSA is broken in ways that do not depend on the attacker being sophisticated. There is no context where raw RSA is the right choice.
"Quantum computers already break RSA." No machine today can run Shor's algorithm at the scale needed to factor a 2048-bit modulus. The threat is real and worth planning for, and it is not present-day.

How RSA has aged

RSA arrived in 1977 and reached broad deployment as the internet commercialised in the 1990s, when it secured early web transactions and email. Over the decades the safe-usage rules tightened as attacks appeared: padding moved from the original schemes to PKCS#1 v1.5 and then to OAEP and PSS, minimum key sizes climbed from 512 to 1024 to 2048 bits as factoring records fell, and implementers learned to make private-key operations constant-time. The core trapdoor never broke. What changed was the accumulated understanding of how to wrap it safely. That trajectory is the reason to treat modern guidance, current key sizes, current padding, vetted libraries, as the accumulated scar tissue of real attacks rather than as bureaucratic caution.

Frequently asked questions

Is RSA still safe to use in 2026? Yes, with modern parameters. A 2048-bit or larger key with OAEP for encryption and PSS for signatures, generated with good randomness and protected properly, has no known practical break on classical computers. The forward-looking concern is quantum, and that is a migration question rather than a reason to abandon RSA now.

Why is 65537 such a common public exponent? It is a prime, which simplifies the coprime requirement, and its binary form has very few set bits, which makes encryption and verification fast. It is also large enough to avoid the small-exponent attacks that plague values like 3 when padding is weak.

Can I use the same keypair for both encryption and signing? It is discouraged. Separating keys by purpose limits the damage if one is misused and avoids subtle interactions between the two operations. Many standards and compliance regimes require distinct keys for encryption and signing.

What happens if my private key leaks? Anyone with the private key can decrypt anything encrypted to the matching public key and can forge signatures as you. The response is to revoke the certificate immediately, reissue with a fresh keypair, and rotate anything that depended on the compromised key. This is why long certificate lifetimes on a leakable key are dangerous.

How is RSA different from AES? AES is a symmetric cipher: the same secret key encrypts and decrypts, and it is fast enough for bulk data. RSA is asymmetric: a public key and a private key that undo each other, slower, and used to establish keys and prove identity. They are used together, with RSA moving an AES key that then does the heavy lifting. See Symmetric vs Asymmetric Encryption.

Does a bigger modulus protect against quantum attacks? Not meaningfully. Shor's algorithm scales well enough that doubling the key size does not restore security against a capable quantum computer. The answer to quantum is a different family of algorithms, not a larger RSA key. See Post-Quantum Cryptography Explained.

Why must I hash a message before signing it? RSA can only operate on values smaller than the modulus, and signing a raw large document is both impossible and insecure. Hashing reduces any input to a fixed-size digest, and the signature covers that digest. This keeps signatures small and ties their strength to a vetted hash function.

An operational checklist

Configuring RSA correctly comes down to a short set of decisions that recur across TLS servers, code-signing pipelines, and internal services.

Generate on a system with strong entropy. Weak randomness at generation time is the one failure that cannot be fixed later, because it may leak a shared prime. Use the platform's vetted key generation, not a script you wrote.
Pick the size for the key's lifetime. A 2048-bit key is fine for a certificate that rotates yearly. A root or code-signing key that lives for a decade earns 3072 or 4096 bits.
Lock the padding. OAEP for encryption, PSS for signatures. Reject any configuration that offers only unpadded operations or defaults to the older v1.5 encryption padding.
Store the private key in hardware where you can. A hardware security module or a platform key store keeps the key from ever appearing in a file that can be copied. Restrict access and audit it.
Plan revocation before you need it. Know how you would revoke and reissue if the key leaked, and keep certificate lifetimes short enough that a missed revocation is not a multi-year exposure.
Track where RSA lives. Maintaining an inventory of every place you depend on RSA makes both routine rotation and an eventual post-quantum migration a manageable project rather than an archaeology dig.

Each item maps back to a failure class from the sections above, which is why the checklist is short and why every line earns its place.