Toy RSA Cracker

RSA is the algorithm behind every HTTPS certificate, every SSH key, and every PGP-signed email you've ever sent. It works because one direction of the computation is trivial, and the other direction is (for large keys) practically impossible. This level makes you take the impossible direction — on a key so small that it's actually easy.

Analogy

Picture a padlock hanging open on a public bulletin board — anyone can grab it and snap it shut on anything they like, but only the shopkeeper who made it owns the unique key that opens it back up. Mailing someone a secret parcel? Take one of their padlocks off the board, clamp it over your box, and drop it in the post: even the thief who intercepts the box can't pry the lock open, and neither can you once it's closed. The genius is that closing locks is easy and making duplicate keys is astronomically hard — unless the padlock is a tiny toy one, in which case a bored teenager with tweezers (this lesson's playground) can pick it in seconds.

The one-way function

Pick two large primes, p and q. Multiply them: n = p × q.

Given n, recovering p and q is called the integer factorization problem. There is no known polynomial-time algorithm for it. The best classical algorithms (the General Number Field Sieve) run in sub-exponential time — still brutally slow for large inputs.

That asymmetry is the foundation of RSA:

• Multiplying p × q — microseconds, even for 2048-bit primes.
• Factoring n back into p and q — infeasible for a 2048-bit n (estimated 300 trillion CPU-years on current hardware).

The trapdoor

RSA adds a mathematical structure on top of the factoring problem. Encrypting requires only the public key (n, e). Decrypting requires a private exponent d, which can only be computed by someone who knows φ(n) = (p-1)(q-1). And computing φ(n) requires knowing p and q.

So the trapdoor is: factor n, and you own the private key.

The full recipe:

Key generation:
  1. Pick two large primes p, q
  2. n = p × q
  3. φ(n) = (p-1)(q-1)
  4. Pick e coprime to φ(n) — typically 65537
  5. d = e⁻¹ mod φ(n)   ← private exponent
  Public key:  (n, e)
  Private key: (n, d)

Encryption:  ct = m^e mod n
Decryption:  m  = ct^d mod n

Why 2048 bits

A 24-bit n (what you're attacking here) has at most 8 million candidate divisors. A modern laptop can trial-divide to the square root — about 4096 candidates — in microseconds.

At 2048 bits, n has roughly 6 × 10^616 possible values. The square root alone is a 617-digit number. Trial division is hopeless. Even the best sieve algorithms require computational resources orders of magnitude beyond what exists today.

Key size	Factoring difficulty
24-bit	Microseconds (trial division)
40-bit	Milliseconds (trial division to √n ~ 500k)
512-bit	Days to weeks (special-purpose hardware, 1999)
768-bit	Two years, cluster of hundreds of CPUs (2009)
1024-bit	Estimated nation-state level effort
2048-bit	No known feasible attack

NIST recommends a minimum of 2048-bit RSA keys through 2030 and 3072-bit beyond that.

What happens with a small n

Your job in this level:

1. Factor n using trial division — iterate candidate divisors from 2 up to √n, stop at the first one that divides evenly. That's p. Then q = n / p.
2. Compute φ(n) = (p − 1) × (q − 1).
3. Recover d = e⁻¹ mod φ(n) using the extended Euclidean algorithm.
4. Decrypt m = ct^d mod n.
5. Decode m from a BigInt back to ASCII bytes.

The playground walks you through this step by step. The visualizer shows the trial-division process frame by frame so you can see exactly when the prime factor is found.

Why real RSA is safe

Two things protect modern RSA:

1. Key size: 2048+ bits makes factoring infeasible with any known algorithm.
2. Padding: Textbook RSA (what we use here) is vulnerable to several algebraic attacks even without factoring. Production RSA uses OAEP padding, which randomises each encryption and prevents structural attacks.

This level uses raw, unpadded RSA. That is intentional — it's simpler to analyse — but it is not what you ship.

Important disclaimer

The RSA operations in this playground are implemented for education only. They use tiny keys, no padding, and no side-channel protections. Do not use this code in any production context. For real asymmetric encryption, use a vetted library: node:crypto, OpenSSL, or cryptography (Python).