RSA encryption explained: how it works, with an example

RSA is an asymmetric (public-key) algorithm: anyone can encrypt a message with your public key or check your signature with it, but only your private key can decrypt or sign. Its security rests on how hard it is to factor a very large number back into the two secret primes that were multiplied to make it. Today RSA is used mainly for digital signatures and certificates rather than for encrypting data, and keys should be at least 2,048 bits long.

The idea behind RSA

RSA is named after Ron Rivest, Adi Shamir and Leonard Adleman, who described it at MIT in 1977; their paper appeared in 1978. It builds on a one-way trapdoor. Multiplying two large primes is easy. Undoing it, finding the primes from their product, is so hard for large numbers that no one can do it in practice, unless they already know one of the primes.

An RSA key pair works like this:

• The public key is a pair of numbers (n, e). The modulus n is the product of two secret primes p and q, and e is a small public exponent.
  
  
• The private key is a number d, calculated from p and q so that e × d leaves a remainder of 1 when divided by (p − 1)(q − 1).
  
  
• To encrypt a message m, which must be a number smaller than n: c = m raised to the power e, modulo n.
  
  
• To decrypt: m = c raised to the power d, modulo n.
  
  

Computing d requires knowing p and q. Everyone can see n, but getting p and q from it means factoring, which is the hard problem. (Modern standards such as RFC 8017 compute d using the least common multiple of p − 1 and q − 1 instead of their product; it works the same way.)

A worked example with small numbers

Real keys use numbers hundreds of digits long, but the arithmetic is the same with small ones. You can check every step with a calculator.

1. Choose two primes: p = 17 and q = 23.
   
   
2. Multiply them: n = 17 × 23 = 391. This is the modulus.
   
   
3. Compute (p − 1)(q − 1): 16 × 22 = 352.
   
   
4. Choose the public exponent: e = 7, which shares no factor with 352.
   
   
5. Find the private exponent: d = 151, because 7 × 151 = 1,057 = 3 × 352 + 1.
   
   

The public key is (391, 7) and the private key is 151. Now encrypt the message m = 42:

• c = 42 to the power 7, modulo 391. Computers do this by repeated squaring: 42 squared is 1,764, which leaves 200 after dividing by 391; 200 squared leaves 118. Since 7 = 4 + 2 + 1, multiply 42 × 200 × 118 and take the remainder: c = 15.
  
  
• To decrypt, the private-key holder computes 15 to the power 151, modulo 391, which gives back 42.
  
  

Signing runs the same maths the other way. To sign the value 100, compute 100 to the power 151, modulo 391, which is 280. Anyone with the public key can check it: 280 to the power 7, modulo 391, gives 100 again. In practice the value signed is a hash of the document.

Why this toy version is insecure

• 391 is trivially factored into 17 × 23, which reveals everything. A 2,048-bit modulus is a number 617 digits long.
  
  
• "Textbook" RSA is deterministic. Encrypting 42 always gives 15, so an attacker can test guesses by encrypting them with the public key. Real RSA encryption adds random padding called OAEP, and real signatures use a padding scheme called PSS. The RSA standard, RFC 8017, requires both for new applications and keeps the older PKCS#1 v1.5 schemes only for compatibility (RFC 8017).
  
  

Encryption vs signing with RSA

The shift from encryption to signing is clearest in HTTPS. TLS 1.3 removed RSA key transport, where the browser encrypted a secret with the server's RSA public key; if that key ever leaked, every recorded session could be decrypted. Now both sides agree on fresh keys, usually with an elliptic-curve exchange, and the server's RSA key only signs the handshake to prove who it is. Our guide to digital signatures covers signing step by step.

Key sizes and performance

NIST's key-management guidance rates RSA key sizes by the symmetric security they are comparable to:

NIST's signature standard, FIPS 186-5, requires a modulus of at least 2,048 bits and a public exponent above 2 to the power 16, which is why most keys use e = 65,537, the usual choice just above that limit. A NIST draft transition plan proposes deprecating 2,048-bit RSA after 2030 and disallowing RSA altogether after 2035, because of quantum computers.

Classical factoring keeps improving too. In September 2026 two public records fell within about two weeks: an 862-bit RSA challenge number, then an 896-bit one, each factored with the general number field sieve running on GPUs, with AI coding agents doing much of the engineering. The researcher behind the 896-bit result wrote that it doesn't affect deployed 2,048-bit keys but shows that 1,024-bit keys are vulnerable to many organisations with data-centre GPU fleets (Stephen Weis). If you still have 1,024-bit keys anywhere, replace them.

RSA is also lopsided in speed. The public exponent is small and the private exponent is huge, so verifying and encrypting are fast while signing and decrypting are slow. On one Apple M3 Max laptop running OpenSSL 3.6 on a single core (September 2026; for comparison only), RSA-2048 managed about 2,250 signatures and about 87,000 verifications a second, and RSA-3072 about 790 signatures and about 40,000 verifications. Generating a new key pair took tens of milliseconds for 2,048 bits and over 100 milliseconds for 3,072 bits, because the software has to hunt for large primes.

RSA vs AES

They are partners, not rivals: an asymmetric method sets up or protects a key, and AES encrypts the data with it. Our guide to symmetric vs asymmetric encryption explains this hybrid design, and ECC vs RSA explains why elliptic curves are replacing RSA in many roles.

RSA and quantum computers

In 1994 Peter Shor showed that a large, error-corrected quantum computer could factor numbers efficiently, which would break RSA completely. Estimates of how large keep falling. In 2019, Craig Gidney and a co-author estimated that factoring a 2,048-bit key would take 20 million noisy qubits running for about eight hours; in May 2025, Gidney revised that to fewer than a million noisy qubits running for less than a week (arXiv). No machine anywhere near that capability has been built, but encrypted traffic recorded today could be decrypted once one exists, a threat known as "harvest now, decrypt later".

The replacements are already standardised: ML-KEM for key establishment and ML-DSA and SLH-DSA for signatures. Browsers already pair classical elliptic-curve key exchange with ML-KEM. For RSA's main remaining job, signatures, the move is slower because certificates, app stores and hardware all have to change. Our guide to post-quantum cryptography covers the timeline.

Where RSA shows up on a typical course platform

• Your website's certificate is often an RSA-2048 key, used to sign each HTTPS handshake.
  
  
• Your Android app is signed with a key the Play Store and phones verify; RSA and ECDSA are both supported.
  
  
• Signed video URLs on some CDNs use RSA or ECDSA key pairs instead of a shared secret.
  
  
• API tokens signed with RS256 let many services verify tokens that only one service can issue.
  
  

In every case the private key is the crown jewel. Whoever holds it can sign links, tokens or app updates as you, so keep it in a key-management service or hardware module, never in a repository or inside an app. See our guide to signed URLs for how the CDN case works.

Key takeaways

• RSA is asymmetric: the public key encrypts and verifies, the private key decrypts and signs.
  
  
• Its security depends on factoring being hard; the worked example shows why tiny numbers offer none.
  
  
• Use at least 2,048-bit keys with OAEP or PSS padding, and plan for 3,072 bits or elliptic curves for long-lived keys.
  
  
• RSA now mostly signs; TLS 1.3 removed RSA key transport, and AES does the bulk encryption.
  
  
• A large quantum computer would break RSA, so migration to post-quantum algorithms has begun.
  
  

Frequently asked questions

How does RSA encryption work?

RSA uses a public key made of a large number n, the product of two secret primes, and a public exponent e. To encrypt, the message is turned into a number and raised to the power e, modulo n. To decrypt, the result is raised to the private exponent d, modulo n, which gives back the message. Working out d requires the two primes, and finding them from n means factoring, which is impractical for large keys.

Is RSA symmetric or asymmetric?

RSA is asymmetric. It uses a key pair: a public key that can be shared with anyone and a private key that its owner keeps secret. Data encrypted with the public key can only be decrypted with the private key, and signatures made with the private key can be verified by anyone holding the public key. Symmetric algorithms such as AES use one shared key for both directions.

Is RSA encryption still used?

Yes, but mostly for signatures rather than encryption. RSA keys still sign many website certificates, Android apps, software updates and API tokens. Encrypting secrets directly with RSA has largely given way to elliptic-curve key exchange, which TLS 1.3 requires, and RSA key transport was removed from TLS 1.3 entirely. RSA with 2,048-bit or larger keys remains secure against classical computers, though a move to post-quantum algorithms is under way.