1. Reconnaissance

We are provided with three files: script.sage, output.txt, and the flag source.

Analyzing the source code script.sage, I immediately noticed a critical anomaly in how the Elliptic Curve is defined.

Instead of a standard Prime Field GF(p), the challenge defines the curve over a Ring:

1# script.sage (Snippet)
2p = getPrime(256)
3Fp = Zmod(p**3)  # <--- CRITICAL VULNERABILITY
4E = EllipticCurve(Fp, [a1, a2])

Standard ECC attacks (like Pollard’s Rho) are designed for groups of prime order. The use of Zmod(p**3) introduces a “smooth” group structure that is mathematically unsound for cryptography.

2. Vulnerability Analysis

This specific setup creates an Anomalous Elliptic Curve over a Ring.

The security of this system collapses because we can lift the Discrete Logarithm Problem (DLP) from the ring $\mathbb{Z}_{p^3}$ to the field of $p$-adic numbers $\mathbb{Q}_p$.

By mapping the points to the kernel of reduction, the group operation becomes isomorphic to the additive group $\mathbb{Z}_p^+$. This allows us to solve the DLP using simple linear division (Smart-Satoh-Araki Attack).

💡 Deep Dive: For the full mathematical proof, complexity analysis ($O(\log^k p)$), and the theory behind $p$-adic lifting, please refer to my technical whitepaper:

📄 Research Paper: Anomalous ECC over Ring $Z_p^k$

3. Exploitation

I developed a solver script based on the research paper above. The script utilizes SageMath to perform Hensel Lifting and Formal Group Logarithms.

The Solver (solve.sage)

Full exploit script below. It parses the parameters from output.txt and recovers the private key.

 1#!/usr/bin/env sage
 2from Crypto.Util.number import long_to_bytes
 3
 4# --- Challenge Data (Extracted from output.txt) ---
 5p = 77850376203167082774832332184672896189931422848651278014948748677228456332131
 6a1 = 54218396295747723814424256150888176111221178301395281945102353539212737911035
 7a2 = 61218013219285849474796901019700888900813809664160179992304043263572452193336
 8Sx = 241180723497442482330367812582158547743446031776411113595405872566221794395256582184317280589879202035747732151779161499088366825422670793341162618889792751454990293203892248035092010213533424623465860626349538834411761549474342149
 9Sy = 168462652779133703946945260758649348241725210242169399013006152879583714553723743677100213164655979332546294444972092078974924892370533483883586638331254934669888229119561379369430441788648163141949755262983975554131442146136973484
10Tx = 424851916228714462365085257292763894061382284875782003631369845562693655809234282909562260797914837320564563093335974827930050357413049537501422911381381898645035029588295205598189406116072282929695864693916579869541203622715096376
11Ty = 105754228565087023376118142239483499795342624795650260177891063513111144610927604886831720337269741987729635922298201611139539479287046924868964291424924768695000710410719796294206815492445391996206582430136842447279551532585811588
12
13def solve():
14    print("[*] Initializing Smart-Satoh p-adic Attack...")
15
16    # 1. Setup p-adic Field (Precision 10 covers p^2)
17    K = Qp(p, prec=10)
18    E = EllipticCurve(K, [a1, a2])
19
20    # 2. Hensel Lifting & Sign Correction
21    try:
22        S = E.lift_x(Sx)
23        T = E.lift_x(Tx)
24    except ValueError: return
25
26    if GF(p)(S[1]) != GF(p)(Sy): S = -S
27    if GF(p)(T[1]) != GF(p)(Ty): T = -T
28
29    # 3. Move to Kernel (Linearization)
30    N = EllipticCurve(GF(p), [a1, a2]).order()
31    S_prime, T_prime = N * S, N * T
32
33    # 4. Formal Logarithm: log(P) = -x/y (Linear Approx)
34    p_adic_log = lambda P: 0 if P[0] == 0 else -P[0]/P[1]
35    
36    # 5. Recover Scalar
37    m = Integer(p_adic_log(T_prime) / p_adic_log(S_prime)) % (p**2)
38
39    print(f"[+] Recovered m: {m}")
40    print(f"[+] Flag: {long_to_bytes(m).decode()}")
41
42if __name__ == "__main__":
43    solve()

4. Execution & Flag

Running the solver against the challenge data:

1❯ sage solve.sage
2[*] Initializing Smart-Satoh p-adic Attack...
3[+] Recovered m: 586544301890030643045629705953467823417282289901496547749896088376204034328161137295864930333821
4[+] Flag: FLAG{SM@RT_@TT@K_1s_@SM@RT_M0V3_1snt_1t}

Final Flag:

FLAG{SM@RT_@TT@K_1s_@SM@RT_M0V3_1snt_1t}