Step 237. 10 Real CTF Crypto Problems — The Day You Deploy Your Arsenal in the Field

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★★☆ | Estimated time: 8+ hours (spread over several days)

Prerequisites: the entire Crypto track from Steps 227~236 — modular arithmetic, RSA attacks, block modes, hash attacks, DH/ECC.

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime. CTF archives like Dreamhack and picoCTF are legal learning platforms officially opened by their operators.

• What you need: a CTF archive account (Dreamhack or picoCTF), Python, a notes document.
• Caution: starting today, you build "the eye that classifies a problem’s type on sight." Classification accuracy matters more than solve count.

Half of solving Crypto problems isn’t computation — it’s classification. The moment you look at a problem that hands you nothing but an output.txt and sense "this is a small-e problem," 80% of the solve is done. Today we select 10 real problems and apply the classification routine — but first, we warm up by solving 3 mini problems built in this chapter with measured solutions, to prime the "classify → attack" instinct.

1. Learning Objectives

By the end of this chapter, you will be able to:

• Narrow a Crypto problem’s type candidates down to two by looking at the given numbers (parameter sizes and shapes)
• Apply the standard checklist (factordb → small e → Fermat → Wiener → common modulus) to RSA problems in order
• Solve single-byte XOR, small-e RSA, and small-n RSA with attack code
• Record "classification clue → attack used" in one line per solve, building your own classification table
• Respect the boundary of researching only as far as technique documentation when you meet an unknown type

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

2-1. A Map of Crypto Problem Types

At the Dreamhack~picoCTF level, the recurring types fall into six broad branches.

2-2. The Classification Routine — The Numbers Are All the Hints

In an output.txt-style problem, the sizes and shapes of the given numbers are the entire hint. Fix a routine:

Step 1: what's given? (n, e, c? a hex string? p, g, A?)
Step 2: observe sizes — is n short? is e 3? is e as big as n? is p small?
Step 3: write down 2 type candidates
Step 4: run a 1-minute verification experiment for each (factordb lookup, cube-root attempt, etc.)

2-3. The RSA Standard Checklist

When you meet an RSA problem, eliminate in this order (the weapons from Steps 229~230):

1. factordb: look up n — a surprising number of n’s are already factored and posted
2. Small e: with e = 3 and a short plaintext, m^3 doesn’t exceed n or barely does — integer cube root
3. Fermat factorization: if p and q are close (similar bit lengths), factor quickly near √n
4. Wiener’s attack: if d is small (below n’s fourth root), recover d via continued fractions
5. Common modulus: the same plaintext encrypted with the same n but different e’s — recover via extended Euclid

2-4. The Boundary of Research

When you meet an unknown type, reading as far as technique documentation is allowed — learning "what’s the RSA small-d attack?" fills your toolbox. Forbidden is that problem’s write-up. The boundary is the same as Step 202: "learning a general technique" is allowed; "obtaining this problem’s answer" is forbidden.

3. Follow Along

The three mini problems below were built for this chapter, and their solutions were actually measured on Python 3.12.14, 2026-09-09. A warm-up before the 10 real problems.

3-1. Mini Problem 1 — Single-Byte XOR

[Problem] ciphertext (hex): 242e2325393a72301d73311d27383f
          hint: the plaintext is in flag{...} format, the key is 1 byte

Classification: hex string + 1-byte key → single-byte XOR (row 1 of the type table). Solution:

ct = bytes.fromhex("242e2325393a72301d73311d27383f")
for k in range(256):
    pt = bytes(c ^ k for c in ct)
    if pt.startswith(b"flag{"):
        print(f"key k={k:#04x} -> {pt}")
        break

key k=0x42 -> b'flag{x0r_1s_ez}'

How to read it: 256 exhaustive tries + a distinguisher (the flag{ prefix) is the canonical skeleton of the XOR type. Without a distinguisher, substitute "is the output all printable English characters?"

3-2. Mini Problem 2 — Small-e RSA

[Problem] n = 1000036000099, e = 3, c = 95567816608
          hint: the plaintext is 2 short ASCII characters

Classification: three values n, e, c + e = 3 → small-e attack candidate. Without skipping factordb, look at e first. Compute m³:

n, e, c = 1000036000099, 3, 95567816608
m_true = int.from_bytes(b"hi", "big")
print(m_true**3, m_true**3 // n)   # 19096251818489, about 19 — 19x larger than n, so it wrapped

19096251818489 19

Don’t give up even if it wrapped — since m³ = c + k·n, raise k and test integer cube roots:

def iroot3(x):
    r = round(x ** (1/3))
    for cand in range(max(0, r-2), r+3):
        if cand**3 == x:
            return cand
for k in range(30):
    r = iroot3(c + k * n)
    if r is not None:
        print(f"k={k}: m={r} -> {r.to_bytes(2, 'big')}")
        break

k=19: m=26729 -> b'hi'

How to read it: with e = 3, if m^e < n take the cube root directly; if it slightly exceeds, test while adding k·n — in the measurement it recovered at k = 19. "It wrapped" means exactly "there are finitely many candidates."

3-3. Mini Problem 3 — Small-n RSA

[Problem] n = 3233, e = 17, c = 2557

Classification: n is 4 digits → factorization (in the field, this corresponds to a factordb lookup). Solution:

def factor(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return i, n // i
p, q = factor(3233)
phi = (p - 1) * (q - 1)
d = pow(17, -1, phi)
m = pow(2557, d, 3233)
print(f"n = {p} x {q}, phi = {phi}, d = {d}, m = {m}")

n = 53 x 61, phi = 3120, d = 2753, m = 42

How to read it: exactly Step 228’s RSA decryption procedure — compute φ(n), then d = e⁻¹ (mod φ), then c^d mod n. One fact — n is small — turns "public-key cryptography" into a toy. In the field, feeding this n to factordb is the first move.

3-4. The Main Event — Selecting and Recording 10 Real Problems

Now to the archives. Selection criteria:

1. 10 unsolved problems from the Crypto category, without type bias (roughly: 1 encoding, 2 XOR, 3 RSA, 1 block mode, 1 hash, 2 DH/math)
2. Apply 2-2’s classification routine to each, recording the 2 candidates before solving
3. After each solve, always leave a one-line record

[Screen example — classification record table]
problem    | given            | 2 candidates      | actual type  | attack used
mini-xor   | 16 hex bytes     | XOR / substitution| single XOR   | 256 exhaustive
small-e    | n, e=3, c        | small e / factor  | small e      | cube root + k·n
dreamhack-A| n 256-bit,e=65537| factordb / Fermat | factordb hit | recover d, decrypt
...

The completion bar is 7+ of 10 solved + classification table v1. How often the table’s "2 candidates" overlap the "actual type" is your skill metric.

4. Missions & Exercises

Mission — 10 Real Problems and Classification Table v1

1. Select 10 Crypto problems from Dreamhack or picoCTF and leave a selection record
2. Apply the classification routine (observe numbers → 2 candidates → verification experiment) to each
3. For RSA problems, apply 2-3’s checklist in order and record at which stage it solved
4. Collect the one-line "classification clue → attack used" per solve into classification table v1
5. If fewer than 7 are solved, add the remaining problems’ types to the table as "unsolved — retraining address"

Exercises

Exercise 1. An output.txt contains only n (1024-bit), e = 3, and c. List the two things to do in the first minute, in order.

Exercise 2. Design an experiment that distinguishes "single-byte XOR" from a "substitution cipher" when a problem gives only a hex string.

Exercise 3. e is neither 65537 nor 3 — it’s oddly large (about the same digit count as n). Which attack candidate comes to mind? Along with the condition under which that attack works.

Exercise 4. Explain from a measurement perspective why you must not solve with the "2 candidates" column left blank.

[classification table v1]
problem  | clue                  | 2 candidates       | actual type| attack             | result
mini-xor | hex, flag{ format hint| singleXOR/substit. | single XOR | 256 exhaustive     | solved
small-e  | e=3, short plaintext  | small e/factordb   | small e    | cube root (k=19)   | solved
small-n  | n is 4 digits         | factorization/…    | small n    | trial division→d   | solved
real 1~10| (record each clue)    |                    |            |                    |

6. Common Pitfalls & Fixes

Wall 1. Your hands freeze at the sight of output.txt

Symptom: just a list of numbers, and you don’t know where to start.
Cause: you skipped the classification routine and jumped straight to hunting for an attack.
Fix: go back to step 1 — write "what’s given" on paper. Three values n, e, c mean RSA, and next comes size observation. The numbers’ digit counts are the entire hint.

Wall 2. The cube root doesn’t come out exact

Symptom: round(c ** (1/3)) cubed differs from c.
Cause: one of two — m³ exceeded n and wrapped, or floating-point error.
Fix: for the wrapped case, test while adding k·n (k = 19 in the 3-2 measurement). Floating point loses precision on big numbers, so in the field use an integer-only approximate root (binary search or sympy’s integer_nthroot).

Wall 3. You stall when n isn’t on factordb

Symptom: after the lookup fails, you don’t know the next move.
Cause: you only remembered checklist stage 1.
Fix: go through stages 2~5 in order — check e’s size (small e/Wiener), check p·q proximity (Fermat), check for another ciphertext with the same n (common modulus). If none applies, re-examine the problem’s other materials (a service connection, the hint text).

Wall 4. The temptation to search for the write-up

Symptom: after 30 stuck minutes, you want to search the problem number.
Cause: you set the goal as "solve count." Today’s goal is the classification eye.
Fix: note the time the search urge arose, and instead look up a technique document (e.g., "RSA attacks list"). Reading the weapons list, not the problem’s solution, is allowed.

Wall 5. The classification table becomes just "solved/unsolved"

Symptom: the record is results only, useless as review material later.
Cause: you didn’t write the clues and candidates before solving.
Fix: enforce the order — when opening a row, fill the "clue" and "2 candidates" columns first. The harder the problem, the more valuable the clue record.

7. Summary

Today’s Concepts

Today’s Commands & Code

An Instinct More Important Than Commands

Crypto problems are closer to a reading-comprehension exam than a cryptography exam — the sizes and shapes of the given numbers are the author’s message. e being 3, n being short, e being oddly large — all of them are signposts saying "come this way." Once reading these signposts becomes second nature over these 10 problems, Step 238’s independent-solving check is merely a validation of the classification routine.

Once every box is checked, Step 237 is complete.