Back to writeups
FlagYardcryptoHardsolved

Normal El-Gamal

12 Jul 2026 · by 0xIDA

Solvers

Normal El-Gamal

Author: 0xIDA
Platform: FlagYard · Category: crypto · Difficulty: Hard

Solvers

Summary

Elliptic-curve ElGamal with encrypt/decrypt oracles. Curve parameters are secret, but many curve points leak from ciphertexts and decryption results. Recover p,a,b via GCDs of Weierstrass determinants, then use additive malleability (C1, C2+M1) ↦ M_flag+M1 to recover the flag point and decode x >> 8.

Challenge Description

This is a totally normal ElGamal implementation, nothing can go wrong :D.

Protocol (challenge.sage)

  • Curve E: y^2 = x^3 + a x + b over secret prime p, generator G, private x, public A = xG
  • Message map: try-and-increment X = (m << 8) + ctr until on curve
  • enc(m): C1 = kG, C2 = kA + M
  • dec(C): M = C2 - x C1 (returns point coords)
  • Flag encrypted once at start; decrypt blocked if:
    • exact same ciphertext, or
    • same C2.x or C2.y as flag CT, or
    • plaintext integer equals the flag

Attack

1. Collect points

Flag CT gives two points. Encrypt small integers and decrypt them to obtain more points (C1, C2, M).

2. Recover modulus p

For points on the curve, y_i^2 - x_i^3 ≡ a x_i + b (mod p). Cross differences:

(d_i - d_j)(x_k - x_l) - (d_k - d_l)(x_i - x_j) ≡ 0 (mod p)

GCD of many such integers (then strip small factors) yields p (384-bit here).

3. Recover a, b

Linear solve from two points, verify on all points.

4. Malleability

Let M1 = map(1). Submit (C1_flag, C2_flag + M1) (both C2 coords change). Oracle returns M' = M_flag + M1. Then M_flag = M' - M1, and flag = long_to_bytes(M_flag.x >> 8).

Exploit output (live)

[*] found p bits=384 a=... b=...
[*] malleable resp: m=  20107406...
[+] b'FlagY{c7ca480f5d57627fa29d030dd4636a16}'

Flag

FlagY{c7ca480f5d57627fa29d030dd4636a16}

Live-verified on tcp.flagyard.com and accepted by Flagyard submit.

Key Takeaways

  1. EC-ElGamal is additively malleable in the message point group.
  2. “Secret curve” is not secret if the oracle hands out many on-curve points — classical GCD recovery of p.
  3. Try-and-increment encoding (m << L + counter) is inverted by a right shift once the point is known.
  4. Decrypt filters on C2 coordinates are bypassed by any nontrivial point addition.

Tools

  • pwntools, sympy (optional factor assist)
  • Flagyard MCP
  • Solver: /root/flagyard/normal-el-gamal/solve.py