Easy? ECDLP - TSG CTF 2024
Challenge:
from flag import flag
from Crypto.Util.number import bytes_to_long
import random
rng = random.SystemRandom()
secret = bytes_to_long(flag + rng.randbytes(1024//8-1-len(flag)))
a, b = [0x1c456bfc3fabba99a737d7fd127eaa9661f7f02e9eb2d461d7398474a93a9b87,0x8b429f4b9d14ed4307ee460e9f8764a1f276c7e5ce3581d8acd4604c2f0ee7ca]
X,Y,Z = (92512155407887452984968972936950900353410451673762367867085553821839087925110135228608997461366439417183638759117086992178461481890351767070817400228450804002809798219652013051455151430702918340448295871270728679921874136061004110590203462981486702691470087300050508138714919065755980123700315785502323688135 ,40665795291239108277438242660729881407764141249763854498178188650200250986699 , 1)
p = 0xd9d35163a870dc6dfb7f43911ff81c964dc8e1dd2481fdf6f0e653354b59c5e5
ec = EllipticCurve(Zmod(p**4),[a,b])
P = ec.point((X,Y,Z))
print((secret*P).xy())
(62273117814745802387117000953578316639782644586418639656941009579492165136792362926314161168383693280669749433205290570927417529976956408493670334719077164685977962663185902752153873035889882369556401683904738521640964604463617065151463577392262554355796294028620255379567953234291193792351243682705387292519, 518657271161893478053627976020790808461429425062738029168194264539097572374157292255844047793806213041891824369181319495179810050875252985460348040004008666418463984493701257711442508837320224308307678689718667843629104002610613765672396802249706628141469710796919824573605503050908305685208558759526126341)
Solve:
https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp
The special case of Smart’s attack
a, b = [0x1c456bfc3fabba99a737d7fd127eaa9661f7f02e9eb2d461d7398474a93a9b87,0x8b429f4b9d14ed4307ee460e9f8764a1f276c7e5ce3581d8acd4604c2f0ee7ca]
X,Y,Z = (92512155407887452984968972936950900353410451673762367867085553821839087925110135228608997461366439417183638759117086992178461481890351767070817400228450804002809798219652013051455151430702918340448295871270728679921874136061004110590203462981486702691470087300050508138714919065755980123700315785502323688135 ,40665795291239108277438242660729881407764141249763854498178188650200250986699 , 1)
p = 0xd9d35163a870dc6dfb7f43911ff81c964dc8e1dd2481fdf6f0e653354b59c5e5
ec = EllipticCurve(Zmod(p**4),[a,b])
P = ec.point((X,Y,Z))
Q = ec(62273117814745802387117000953578316639782644586418639656941009579492165136792362926314161168383693280669749433205290570927417529976956408493670334719077164685977962663185902752153873035889882369556401683904738521640964604463617065151463577392262554355796294028620255379567953234291193792351243682705387292519, 518657271161893478053627976020790808461429425062738029168194264539097572374157292255844047793806213041891824369181319495179810050875252985460348040004008666418463984493701257711442508837320224308307678689718667843629104002610613765672396802249706628141469710796919824573605503050908305685208558759526126341)
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 5), [ ZZ(t) + randint(0,p)*(p**4) for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
secret = SmartAttack(P, Q, p)
print(bytes.fromhex(f'{int(secret):x}'))