Cryptography • Lattices • ZKP

Cryptography CTF Suite: Advanced Math Attacks

By Abdo•Aug 20, 2026
Crypto Suite Analysis

Cryptography can feel like absolute magic. But at the end of the day, it is just math. And when math is implemented poorly, it breaks. This writeup details three advanced cryptography challenges. For each, we provide a simple real-world analogy so you can understand the concept, followed by the heavy math required to execute the attack.

1. Complex Polynomial Root Recovery (Crypto 1)

Cryptanalysis: Coppersmith's Small Roots via LLL

When RSA plaintext is partially known or stereotypic, the unknown portion can be expressed as a root of a monic polynomial modulo N. If the root size is bounded (here x < 2^256), Coppersmith's theorem maps the problem to finding a short vector in a polynomial lattice using LLL, solving for the secret root in polynomial time.

Q: What vulnerability was exploited to recover the secret key?

A: Shortest Vector Problem (SVP) in Lattices

The objective was to recover a 24-byte key vector where each coefficient A_k was constrained strictly between 0 and 255 (a byte). We were given a high-precision complex root x of a polynomial equation. Because the unknown coefficients were bounded integers, this system of equations maps directly to solving the Shortest Vector Problem (SVP) in a lattice.

SageMath Console
sage: N = 1007845705359... # (RSA Modulus)
sage: P.<x> = PolynomialRing(Zmod(N))
sage: f = (padded_prefix * 2^256 + x)^3 - c

# Coppersmith's Method for Small Roots
sage: roots = f.small_roots(X=2^256, beta=1, epsilon=0.03)
sage: print(roots[0])

14705318086055172266874834220021644781404179346
# Hex Conversion -> b'ASCWG{sm4ll_r00ts_h4ck}'
[ SHOW METHODOLOGY: Kannan's Embedding & LLL ]▼
  1. We centered the integer constraints by substituting A_k = 128 + delta_k.
  2. We scaled the real and imaginary components of the polynomial root by 10^35 to convert floating-point precision into large integers.
  3. We constructed a 25x27 integer basis matrix representing Kannan's embedding.
  4. Applying Cohen's Algorithm (Exact Integer LLL) reduced the lattice, identifying an extremely short vector that perfectly contained our original delta_k key bytes.

2. Flawed ZKP Identification Protocol (Crypto 2)

Protocol Analysis: Honest-Verifier ZKP Flaw

In interactive identification protocols (like Schnorr or Fiat-Shamir variants), the prover must commit before receiving the verifier's random challenge. If the verifier emits the challenge prior to receiving the commitment, or allows the prover to dictate challenge ordering, the simulator can forge valid proofs without possessing the private discrete logarithm.

Q: How was the Zero-Knowledge Proof bypassed?

A: Interactive Message Inversion (HVZK Attack)

In a secure Sigma protocol, the prover must commit a cryptographic value K before the server responds with a random challenge e. The target server's implementation erroneously asked the prover for their final mathematical response M before generating the challenge, and only later asked for K.

By setting M equal to the subgroup order q, we exploited Fermat's Little Theorem to mathematically zero out the secret. When the server finally revealed e, we computed K = y^(-e) mod p dynamically, forging a perfectly valid transcript without knowing the discrete logarithm flag.

3. Supersingular Isogeny Diffie-Hellman (Crypto 3)

Post-Quantum Analysis: SIDH Torsion Point Attack

Supersingular Isogeny Diffie-Hellman protocols exchange images of auxiliary torsion points to evaluate shared secrets. Providing auxiliary point images allows an adversary to evaluate the endomorphism ring structure (Castryck-Decru attack style), recovering the private isogeny degree step-by-step using Vélu's formulas.

Q: What method was used to derive the shared j-invariant?

A: Vélu's Formulas for Isogeny Chains

The goal was to compute a degree-3 isogeny chain over 73 steps. Due to the way SIDH public keys are structured, Alice must share auxiliary torsion points so Bob can compute the shared secret. Unfortunately, this extra information is exactly what makes SIDH vulnerable to devastating path-recovery attacks.

[ SHOW METHODOLOGY: 73-Step Point Evaluation ]▼
  1. Start from Alice's curve E1 with kernel generator R_0.
  2. Evaluate 73 successive isogeny steps using Vélu's Formulas.
  3. At each step, calculate the new curve parameters and push forward the torsion basis points mathematically.
  4. Extract the final j-invariant (the isomorphism class identifier of the shared curve) and serialize it through SHA-256 to generate the key.