RSA Encryption — How Public-Key Cryptography Works

1 2 3 4 5 6 7

difficulty levels — click green to claim

> RSA ENCRYPTION

rsa difficulty: 4–7 also known as: Rivest–Shamir–Adleman

The idea in plain English: Imagine you have an open lock box that anyone can close and lock — but only you can open. You leave the open box in a public square. Anyone who wants to send you a message drops it in, closes the lid, and the lock snaps shut. Now nobody, not even the sender, can open it — except you with your secret key. RSA is math that makes this possible: a public key everyone knows (the open box), and a private key only you have (the special key). The magic ingredient? Multiplying two huge prime numbers is easy, but trying to figure out which two primes were multiplied is astronomically hard.

Why this really exists: Before RSA (1977), sending a secret message meant both parties had to agree on a secret key in advance — like meeting in a dark alley to swap codebooks. RSA eliminated that. It made secure communication with strangers possible for the first time. Every time you visit an HTTPS website, use SSH to log into a server, or verify a PGP email signature, RSA (or its elliptic-curve successor) is working behind the scenes. It's the engine of modern internet security.

▸ Worked Example (Small Numbers)

Let's walk through a complete RSA key generation and message exchange using tiny primes so we can do the math by hand. Real RSA uses primes hundreds of digits long — but the procedure is exactly the same.

Step 1 — Choose two primes:
p = 17    q = 23

Step 2 — Compute n = p × q:
n = 17 × 23 = 391

Step 3 — Compute φ(n) = (p-1)(q-1):
φ(391) = 16 × 22 = 352

Step 4 — Choose public exponent e (coprime with φ):
e = 7    (gcd(7, 352) = 1 ✓)

Step 5 — Compute private exponent d, where e×d ≡ 1 (mod φ):
d = 151    (7 × 151 = 1057 = 3×352 + 1 ✓)

Public key: (n=391, e=7) | Private key: (d=151)

Step 6 — Encrypt a message (say "42"):
ciphertext = 42⁷ mod 391 = 73

Step 7 — Decrypt with private key:
plaintext = 73¹⁵¹ mod 391 = 42 ✓

→ The message 42 was encrypted with the public key (391, 7) and decrypted with the private key 151. An attacker who sees n=391 would need to factor it as 17×23 to compute d — easy for 391, impossible for a 2048-bit n.

▸ How to Decode (Step by Step)

Given a ciphertext integer c, the private key exponent d, and the modulus n from the puzzle:

1. Compute m = c^d mod n using fast modular exponentiation

2. Convert the resulting integer m back to text (usually ASCII bytes, sometimes hex)

3. If the conversion produces garbage, check the byte order (big-endian vs little-endian)

4. Some puzzles give you p and q directly — compute d yourself with d = pow(e, -1, (p-1)*(q-1))

# Python one-liner decryption:
m = pow(ciphertext_int, d, n)

# Convert to bytes (handles variable-length):
plain = m.to_bytes((m.bit_length() + 7) // 8, 'big')

# If you have p, q, and e but not d:
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi) # Python 3.8+
plain = pow(c, d, n)

💡 Use pow(base, exp, mod) in Python, not base ** exp % mod. The latter tries to compute the full exponent before taking the modulus, which will use astronomical memory for large exponents.

▸ Key Size — Security vs. Feasibility

RSA security relies entirely on the size of n. Here's how the factoring difficulty grows with key size. Modern standards require at least 2048 bits.

n size (bits)	n size (decimal digits)	Security Level	Factoring Time (classical)	Status
512	~155	very weak	hours on a single machine	broken
1024	~309	weak	~2 years on academic clusters	deprecated
2048	~617	strong	~300 billion years (today's tech)	secure
4096	~1,233	very strong	far beyond universe's age	secure

Note: Shor's algorithm on a sufficiently large quantum computer would break RSA instantly at any key size. That's why post-quantum cryptography (like lattice-based schemes) is being standardized right now.

▸ Important — Textbook RSA vs. Real RSA

What's shown above is "textbook RSA" — the pure math. Real RSA in the wild adds padding (OAEP or PKCS#1 v1.5) to prevent attacks:

Deterministic encryption: Without padding, the same message always produces the same ciphertext. An attacker can recognize repeated messages.
Malleability: An attacker can modify a ciphertext and predict how the decrypted plaintext changes — enabling chosen-ciphertext attacks.
Small exponent attacks: If e=3 and the message is short, the ciphertext might not "wrap around" n, making it trivial to decrypt by taking an integer root.

💡 Puzzle RSA is almost always textbook RSA (no padding) so you can solve it with raw modular exponentiation. Don't use textbook RSA for real security!

▸ Real-World Applications

HTTPS / TLS — Every time you see the padlock in your browser, RSA (or ECDHE) is being used to establish a secure connection. Your browser encrypts a session key with the server's RSA public key; only the server can decrypt it.
SSH — When you SSH into a server, your client verifies the host key (an RSA or Ed25519 key) to prove you're connecting to the right machine — preventing man-in-the-middle attacks.
PGP / GPG — Pretty Good Privacy uses RSA (or ECC) to encrypt emails and files. You publish your public key, anyone can encrypt a message for you, and only your private key can decrypt it.
Digital signatures — RSA works in reverse too: encrypt with the private key, decrypt with the public key. This is how software packages are signed. When you run apt-get install, the package signature is verified with RSA.
Smart cards / YubiKeys — Hardware security modules store RSA private keys in tamper-resistant chips. The key never leaves the device — all signing and decryption happens inside the hardware.

← Back to all ciphers