Skip to main content
Be Bitwise

RSA: The Classic Algorithm

Asymmetric Encryption · Networking & Cryptography track

7 min read

In this module

The Algorithm That Changed Everything

RSA was published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. The first practical public-key encryption system, it remains one of the most widely deployed algorithms on Earth. RSA's security rests on a simple fact: multiplying two large prime numbers is easy. Factoring their product back into the primes is extraordinarily hard.

Before RSA, encryption demanded both parties share a secret key in advance. RSA changed that. Suddenly you could communicate securely with someone you'd never met, which opened the door to secure commerce, digital signatures, and the encrypted internet we live on today.

Key Generation

RSA key generation works as follows:

  1. Choose two large random prime numbers, p and q (each typically 1024+ bits)
  2. Compute n = p * q (the modulus)
  3. Compute the totient: phi(n) = (p - 1) * (q - 1)
  4. Choose a public exponent e (commonly 65537) that is coprime to phi(n)
  5. Compute the private exponent d such that e * d = 1 mod phi(n)

That's the textbook version. Real implementations following PKCS #1 and FIPS 186 usually compute d modulo lambda(n) = lcm(p - 1, q - 1), the Carmichael function, which divides phi(n) and gives a smaller d that works just the same.

The public key is (n, e); the private key is (n, d). The primes p and q get discarded (or kept around for optimisation via the Chinese Remainder Theorem), but they're never shared. The value 65537 (2^16 + 1) is almost universally chosen as e because it has only two bits set in binary, which makes modular exponentiation with e blisteringly fast.

Encryption and Decryption

RSA encryption is modular exponentiation:

text
ciphertext = plaintext^e mod n (encrypt with public key)
plaintext = ciphertext^d mod n (decrypt with private key)

This works thanks to Euler's theorem: raising a number to the e*d power modulo n returns the original number, provided e and d are properly related through phi(n). The maths guarantees that only the holder of d (the private key) can reverse the encryption.

Key Concept

RSA encryption computes message^e mod n using the public key. Decryption computes ciphertext^d mod n using the private key. The security depends on the difficulty of factoring n to recover p and q, which would allow computing d from e. Without knowing the factorisation, computing d from the public key (n, e) is believed to be computationally infeasible.

A Small Example

For illustration (real RSA uses numbers hundreds of digits long):

text
p = 61, q = 53
n = p * q = 3233
phi(n) = 60 * 52 = 3120
e = 17 (coprime to 3120)
d = 2753 (because 17 * 2753 = 46801 = 15 * 3120 + 1)
Public key: (n=3233, e=17)
Private key: (n=3233, d=2753)
Encrypt message 65:
65^17 mod 3233 = 2790
Decrypt ciphertext 2790:
2790^2753 mod 3233 = 65 (recovered!)

Tiny numbers, picked for clarity. In practice, n is at least 2048 bits long, a beast with over 600 decimal digits. The modular exponentiation uses efficient algorithms like square-and-multiply, which computes x^e mod n without ever materialising the astronomically large intermediate value x^e.

The program below runs this exact example, then plays the attacker: it factors a series of moduli by trial division. Work out d for p = 11, q = 13, e = 7 by hand first, then swap those values in (the comment shows where) and check your answer. This is textbook RSA with tiny numbers, so treat it as a toy and never as a template.

Try itCheck your hand-computed d, then watch how the division count grows as the primes get longer.
C (GCC 9.2.0)

Every 4 bits added to each prime multiplies the work by about 16. The last modulus is only 56 bits; a 2048-bit one would need around 2^1023 trial divisions, which is why real attacks use the number field sieve instead. Even that is nowhere near fast enough at 2048 bits.

Key Sizes

RSA key sizes refer to the length of n in bits:

  • 1024-bit: Deprecated by NIST since 2011 and disallowed for new signatures after 2013. No 1024-bit key has been publicly factored yet, but the record (RSA-250, 829 bits) is close enough that nobody should rely on one.
  • 2048-bit: Current minimum standard. Expected to remain secure against classical computers through at least 2030.
  • 3072-bit: Recommended for long-term security (equivalent to 128-bit symmetric security).
  • 4096-bit: Maximum commonly used. Significantly slower but provides a wide security margin.

Larger keys buy more security at the cost of speed. A 2048-bit RSA operation runs roughly 8 times slower than a 1024-bit one. That's the pressure pushing the industry toward elliptic curve cryptography, which hits equivalent security with much smaller keys. A 256-bit ECC key matches the strength of a 3072-bit RSA key.

Why Factoring Is Hard

The fundamental assumption behind RSA is that factoring n = p * q is computationally infeasible when p and q are sufficiently large. The best known factoring algorithm (the General Number Field Sieve) has sub-exponential but super-polynomial running time.

For perspective: factoring a 2048-bit RSA key is estimated to take roughly 2^112 operations, well beyond any current or foreseeable classical computer. The largest RSA key ever publicly factored was RSA-250 at 829 bits, which burned through the equivalent of 2,700 years of single-core computation.

Quantum computers running Shor's algorithm change the picture entirely. They could factor large numbers in polynomial time. That threat is why post-quantum cryptography is an active research area, hunting for algorithms resistant to both classical and quantum attacks. Systems that need long-term security are already starting to migrate.

RSA Padding

Raw "textbook RSA" (just computing m^e mod n) is insecure for several reasons:

  • It is deterministic (same plaintext always gives same ciphertext)
  • Small messages or messages with patterns are vulnerable to mathematical attacks
  • It is malleable (an attacker can manipulate ciphertexts to produce related plaintexts)

In practice, RSA always uses padding schemes like OAEP (Optimal Asymmetric Encryption Padding) that add randomness and structure before encryption. OAEP uses a random seed and two hash function applications to mask the message, so even identical plaintexts produce different ciphertexts. Never use raw RSA.

RSA for Signatures

RSA can also create digital signatures by "encrypting" with the private key:

text
signature = hash(message)^d mod n (sign with private key)
verify: signature^e mod n == hash(message)? (verify with public key)

If the computed hash matches, the signature is valid. The message was signed by the holder of the private key and has not been tampered with. In practice, signatures also use padding (PSS, the Probabilistic Signature Scheme) for security.

RSA signatures show up in SSL/TLS certificates, code signing, and secure email (S/MIME and PGP). When your browser shows a padlock icon, it has verified an RSA or ECDSA signature on the server's certificate to confirm its identity.