Private Curve - 0xl4ugh CTF 2024
Challenge:
from Crypto.Util.number import getPrime,bytes_to_long
from secret import flag, p,a,b
flag=bytes_to_long(flag)
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]
P=G*flag
print('here is my 7 xs can u get my private key ?')
#print(P[0])
for i in range(7):
PP=P+i*G
print(PP[0])
'''
here is my 7 xs can u get my private key ?
127222731808447286384197097524849730324280912084690383123034174156693907296321941583008138816149304043198829099586978152639
540150767459876746741544981524050320567261340627105743010550795668800394677819357272612801849680099119164471834128771848184
378426912752589864658307848293724051252472266429208255456184007500868515338668653822829851730193370970777687937350186024739
114528622155057967694026934367142168000739167063266001591280862125480038107282641048998814104241182719055831758176542012114
322400405850331256663554456242498354334347017862265389196757152850674454034744292814021471167045908645361119988919752367867
496047308313146975448000924265615728665813401349451895964344399497579232646901690982051726266819379622021083585061713111901
339613985780778130822549050414603776860269549419836797423421156347303558845214120048926926114443864057942273222884788713615
'''
Solve:
I thought it was an amazing challenge.
This paper is very helpful to recover the curve parameters.
After that, the curve order is smooth enough to solve the discrete log just by excluding the biggest factor.
from Crypto.Util.number import *
x1 = 127222731808447286384197097524849730324280912084690383123034174156693907296321941583008138816149304043198829099586978152639
x2 = 540150767459876746741544981524050320567261340627105743010550795668800394677819357272612801849680099119164471834128771848184
x3 = 378426912752589864658307848293724051252472266429208255456184007500868515338668653822829851730193370970777687937350186024739
x4 = 114528622155057967694026934367142168000739167063266001591280862125480038107282641048998814104241182719055831758176542012114
x5 = 322400405850331256663554456242498354334347017862265389196757152850674454034744292814021471167045908645361119988919752367867
x6 = 496047308313146975448000924265615728665813401349451895964344399497579232646901690982051726266819379622021083585061713111901
x7 = 339613985780778130822549050414603776860269549419836797423421156347303558845214120048926926114443864057942273222884788713615
C = Matrix([
[2*x2**2 + 2*x2*(x1+x3), 2*x2 - (x1+x3), 2*x2, 2],
[2*x3**2 + 2*x3*(x2+x4), 2*x3 - (x2+x4), 2*x3, 2],
[2*x4**2 + 2*x4*(x3+x5), 2*x4 - (x3+x5), 2*x4, 2],
[2*x5**2 + 2*x5*(x4+x6), 2*x5 - (x4+x6), 2*x5, 2],
[2*x6**2 + 2*x6*(x5+x7), 2*x6 - (x5+x7), 2*x6, 2],
])
u = Matrix([
[(x1+x3) * x2**2],
[(x2+x4) * x3**2],
[(x3+x5) * x4**2],
[(x4+x6) * x5**2],
[(x5+x7) * x6**2],
])
m = C.augment(u).det()
for _ in range(100):
C = C.change_ring(Zmod(m))
for uu in range(1, 100):
try:
l1, l2, l3, l4 = C.solve_right(uu*u).T[0]
break
except:
pass
m //= gcd(m, uu)
l1, l2, l3, l4 = C.solve_right(u).T[0]
m = gcd(m, l1**2-l2)
p = max(factor(int(m)))[0]
A = l3 % p
B = (l4 - l1*l3) * pow(2, -1, p) % p
E = EllipticCurve(GF(p), [A, B])
possible_G = []
for P1 in E.lift_x(ZZ(x1), all=True):
for P2 in E.lift_x(ZZ(x2), all=True):
for P3 in E.lift_x(ZZ(x3), all=True):
G1 = P2 - P1
G2 = P3 - P2
if G1 == G2:
possible_G.append(G1)
# G.order()
order = 556965490678630938378478504080786693800314491282937950160435260930503737423792557485852859174204084888400324899682328099393
#print(factor(order))
primes = [72227181939217 , 108661850383939 , 109941210688553 , 117077820297817 , 118416071094367 , 139218006249863]
for G in possible_G:
for P in E.lift_x(ZZ(x1), all=True):
dlogs = []
"""
for fac in primes:
t = int(order) // int(fac)
dlog = (t*P).log(t*G)
dlogs += [dlog]
print(dlogs)
"""
dlogs = [51088168138150, 20841038223433, 99422819666350, 84141054836054, 92245366899078, 44522182731635]
flag = crt(dlogs, primes)
print(long_to_bytes(int(flag)))
# 0xL4ugh{PREDICTING_GENERATOR_Paper}