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)⟶{\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 \stackrel{\varphi }{⟶}\mathcal{E}(p{\mathbb{Z}}_p)\stackrel{{\log }_{\mathcal{E}}}{⟶}p{\mathbb{Z}}_p$$
where

$\varphi :\ker \pi \ni (x,y,z)⟼-x/y\in \mathcal{E}(p{\mathbb{Z}}_p)$
Also, let

$N$ be

$N=\mathrm{♯}{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)⟶\ker \pi ⟶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)=\{P\in E({\mathbb{Q}}_p)\mid v_p(P_x)\le -2n\}\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!}