Hic Sunt Dracones — fortid2026

Description

Hic Sunt Dracones

English summary: The handout contains chall.py, patch.py, output.txt and a Dockerfile. The Dockerfile clones awnonbhowmik/Dragon-Crypto (commit 046ad8d) and applies patch.py. chall.py encodes the flag onto an elliptic curve with Koblitz encoding, pushes each point through the library's "dragon curve" turtle renderer using a random private key, and prints the end coordinates of every rendered point. The goal is to recover the flag (format FortID{...}) from output.txt.

Analysis

The pipeline (chall.py)

1. A random 256-bit prime p with p % 4 == 3 and random curve parameters a, b are chosen.
2. koblitz_encoder(flag, a, b, p) maps every plaintext character m (its ord) to an EC point (x_m, y_m) where x_m = m*k + j with k = 20 and j the first value in 1..19 that yields a point on the curve y² = x³ + a·x + b (mod p).
3. private_key = (size, iterations, angle, a, b) with:
   • size = randrange(1<<127, 1<<128) — a huge ~128-bit integer,
   • iterations = randrange(10, 15) — i.e. one of {10,11,12,13,14},
   • angle = randrange(2) * 180 — i.e. 0 or 180.
4. Each Koblitz point is passed to dragon.dragon_render(point, private_key), which drives a turtle to draw a dragon curve and returns the turtle's end coordinates (x_end, y_end).
5. Output = point_to_character(encrypted) → "X" + x-values joined by "X" followed by "Y" + y-values joined by "Y".

The patch (patch.py)

patch.py edits koblitz.py to:

• parameterize the prime p (instead of the library's hardcoded p = 751), and
• replace the original O(p) brute-force modular square root with a fast exponentiation pow(n, (p+1)//4, p), which is a valid square root when p % 4 == 3.

...