Crypto — Small Primes, Big Problem

Category: Crypto · Difficulty: Hard

Scenario

A fictional legacy internal tool at kashsec-labs.test still generates RSA keys with a deliberately small modulus "for speed" — a decision made in 2009 and never revisited. You've intercepted an RSA-encrypted flag along with the public key used to encrypt it.

Provided data

The public key (modulus n and public exponent e):

n = 3127
e = 3

The ciphertext (a single small integer, since the flag was encrypted as one short numeric block for this exercise):

c = 201

A reminder of how RSA encryption works: c = m^e mod n, where m is the original numeric message and decryption requires computing the private exponent d, which in turn requires knowing the two prime factors of n. The flag is built directly from the recovered number m, in the form KASHSEC{d3crypt3d_m_1s_<m>}.

Your task

Real RSA moduli are enormous (2048+ bits) specifically because factoring a product of two huge primes is computationally infeasible with current technology. This modulus is tiny — factor it, derive the private key, and decrypt the message.

Hint 1

n = 3127 is small enough to factor by hand or with a basic script — RSA's entire security rests on this being infeasible at real key sizes, which is very much not the case here. Find the two primes p and q such that p × q = 3127.

Hint 2

3127 = 53 × 59. With p and q known, compute Euler's totient: φ(n) = (p-1)(q-1). Then find d, the modular multiplicative inverse of e modulo φ(n) — the private exponent.

Show full answer

Factoring gives p = 53, q = 59, so φ(n) = 52 × 58 = 3016. Finding the modular inverse of e = 3 modulo 3016 gives d = 2011 (since 3 × 2011 mod 3016 = 1). Decrypting: m = c^d mod n = 201^2011 mod 3127 = 2222 — you can verify this the other direction too: 2222^3 mod 3127 = 201, matching the given ciphertext exactly. The recovered number gives the flag KASHSEC{d3crypt3d_m_1s_2222} — the small modulus made brute-force factoring (and from there, full private-key recovery) entirely practical, something that would be computationally impossible at real-world RSA key sizes.

The flag

KASHSEC{d3crypt3d_m_1s_2222}

Why this matters beyond the CTF

This challenge is a compressed, hand-computable version of a genuinely real historical vulnerability class: undersized RSA keys, generated for performance reasons or by outdated legacy systems, have been factored in real-world security research and real incidents. Modern guidance (referenced in Path 06's cryptography fundamentals) requires a minimum of 2048-bit RSA keys precisely because factoring becomes infeasible at that scale with any known classical algorithm — the security isn't from RSA being unbreakable in principle, it's from the specific numbers involved being chosen large enough that factoring them would take longer than the useful life of the universe with current computing power.

Bonus round — why does a small public exponent matter too?

This challenge used e = 3, a small public exponent chosen for "efficiency" — a decision independent of the key size itself.

Hint

Think about what happens if the same short message is encrypted with the same small exponent under three or more different public keys (a real scenario — e.g., the same short message broadcast to multiple recipients, each with their own RSA key but all using e=3).

Show answer

This describes Håstad's broadcast attack: if the same message is encrypted with a small public exponent (commonly e=3) under enough different, sufficiently large moduli — mathematically, at least e of them — an attacker can use the Chinese Remainder Theorem to reconstruct the original message without ever factoring any of the moduli at all, even if every individual key is otherwise perfectly secure at full 2048-bit size. This is a genuinely elegant, real cryptographic attack, and it's exactly why modern RSA implementations favor a larger public exponent like 65537 combined with proper padding schemes (OAEP) — both of which independently close off this specific attack, on top of everything a sufficiently large modulus already provides.

Real RSA keys are never this small — this challenge exists purely to make the underlying mathematics tractable to work through by hand or with a basic script, so the "why key size matters" lesson is something you can actually verify yourself rather than just being told. Path 06's cryptography fundamentals lesson covers the real-world key size guidance this challenge is illustrating.

Next up → Forensics — The EXIF Trail