# pure division - zer0pts ctf 2021

## challenge
It’ｓ just a division, so it is "pure". We are given the following code and outputs.
Anyway, we have to solve the ECDLP. In general, ECDLP is hard. But in this case, the curve is over quotient ring $F_p = \mathbb{Z}/p^3\mathbb{Z}$, so we can get the flag. (note: This "$F_p$" is not $\mathbb{F}_p$. It indicates the name of variable in the code.)

# task.sage
from Crypto.Util.number import *
from flag import flag

assert len(flag) == 40

p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a1 = 22457563127094032648529052905270083323161530718333104214029365341184039143821
a2 = 82792468191695528560800352263039950790995753333968972067250646020461455719312
Fp = Zmod(p^3)
E = EllipticCurve(Fp, [a1, a2])

m = bytes_to_long(flag)
S = E(201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226, 217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835)
T = m * S

with open("output.txt", "w") as f:
    f.write("T: {}".format(T))

# output.txt
T: (49376632602749543055345783411902198690599351794957124343389298933965298693663616388441379424236401744560279599744281594405742089477317921152802669021421009909184865835968088427615238677007575776072993333868804852765473010336459028 : 342987792080103175522504176026047089398654876852013925736156942540831035248585067987750805770826115548602899760190394686399806864247192767745458016875262322097116857255158318478943025083293316585095725393024663165264177646858125759 : 1)

## solution
$\mathbb{Z}/p^n\mathbb{Z}$ can be seen as a set of numbers with $n$ digits of precision in $\mathbb{Q}_p$. Since the flag is 320 bits and $p^3$ is large enough, it is no problem to solve the ECDLP over $\mathbb{Q}_p$. The main part of the solution was meant to be here. In this section, one of the solution methods which is similar to SSSA Attack is introduced.
Let $E$ be an elliptic curve over $\mathbb{Q}_p$ and let $E_f$ be the reduction curve of $E$ over $\mathbb{F}_p$. For simplicity, we assume $E_f$ is not singular.
Let $\pi : \mathbb{P}^2(\mathbb{Q}_p) \longrightarrow \mathbb{P}^2(\mathbb{F}_p)$ be a reduction map and we equate $(x,y,1) \in \mathbb{P}^2(\mathbb{Q})$ with $(x,y) \in \mathbb{A}^2$. Then let $\mathcal{E}$ be a formal group associated $E$, the isomorphism is constructed as follows
$$\ker \pi \overset{\phi}{\longrightarrow} \mathcal{E}(p\mathbb{Z}_p) \overset{\log_\mathcal{E}}\longrightarrow p\mathbb{Z}_p$$
where $\phi:\ker \pi \ni (x,y,z) \longmapsto -x/y \in \mathcal{E}(p\mathbb{Z}_p)$
Also, let $N$ be $N = \sharp E_f(\mathbb{F}_p)$. Obviously, $NP \in \ker \pi$ is holded for $P \in E(\mathbb{Q}_p)$.
Thus we can construct a isomorphism as follows
$$E(\mathbb{Q}_p) \longrightarrow \ker \pi \longrightarrow p\mathbb{Z}_p$$
Since $p\mathbb{Z}_p \simeq \mathbb{F}_p^+$, the ECDLP is solvable.

## implementation
In implementation, p-adic expansion is useful. Using the p-adic valuation $v_p$, we consider subsets $E_n(\mathbb{Q}_p) = \left\{ P \in E(\mathbb{Q}_p) \mid v_p(P_x) \leq -2n \right\} \cup \left\{O\right\}$ of $E(\mathbb{Q}_p)$. Then $E_n(\mathbb{Q}_p) \simeq \mathcal{E}(p^n\mathbb{Z}_p)$.
By using identity map, the following holds.
$$\mathcal{E}(p^n\mathbb{Z}_p)/\mathcal{E}(p^{n+1}\mathbb{Z}_p) \simeq p^n\mathbb{Z}_p / p^{n+1}\mathbb{Z}_p \simeq \mathbb{F}_p^+$$

By this result, we can sequentially find each coefficient $a_i$ of the p-adic expansion $\sum a_i p^i$ of require value.
Anyway, look at this solver.

from Crypto.Util.number import *

p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a1 = 22457563127094032648529052905270083323161530718333104214029365341184039143821
a2 = 82792468191695528560800352263039950790995753333968972067250646020461455719312
Fp = Zmod(p^3)
E = EllipticCurve(Fp, [a1, a2])

S = E(201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226, 217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835)
T = E(49376632602749543055345783411902198690599351794957124343389298933965298693663616388441379424236401744560279599744281594405742089477317921152802669021421009909184865835968088427615238677007575776072993333868804852765473010336459028, 342987792080103175522504176026047089398654876852013925736156942540831035248585067987750805770826115548602899760190394686399806864247192767745458016875262322097116857255158318478943025083293316585095725393024663165264177646858125759)

# --------------- solve -----------------
prec = 3
Qp = pAdicField(p, prec)
E = EllipticCurve(Qp, [a1, a2])

Fp = GF(p)
Ef = EllipticCurve(Fp, [a1, a2])
N = Ef.order()

S = E(S[0], S[1])
T = E(T[0], T[1])

NS = N * S
a = Fp(-NS[0] / (p * NS[1]))

n = 0
l = 1
Sp = S
Tp = T
ds = []
while Tp != 0:
    NTp = N*Tp
    w = -NTp[0] / NTp[1]
    b = w / p^l
    d = Fp(Integer(b)/a)
    ds.append(Integer(d))
    Tp = Tp - Integer(d)*Sp
    Sp = p*Sp
    n += 1
    l += 1
    if n > prec:
        break

solve = 0
for i in range(len(ds)):
    solve += ds[i] * p^i
print(long_to_bytes(solve))

Here is the flag ```zer0pts{elliptic_curve_over_p-adic!yey!}```