Hide and seek
2 minutes to read
I have hidden my flag among the elliptic curve points. Go seek!
Challenge contributed by CryptoHack
Challenge files:
Source code analysis
We are given a SageMath script that uses Elliptic Curve Cryptography to encrypt the flag:
from Crypto.Util.number import bytes_to_long
FLAG = bytes_to_long(open("flag.txt", "rb").read().strip()[len("ECSC{"):-1])
proof.arithmetic(False)
p = 1789850433742566803999659961102071018708588095996784752439608585988988036381340404632423562593
a = 62150203092456938230366891668382702110196631396589305390157506915312399058961554609342345998
b = 1005820216843804918712728918305396768000492821656453232969553225956348680715987662653812284211
F = GF(p)
E.<G> = EllipticCurve(F, [a, b])
assert FLAG < G.order()
k = randrange(G.order())
P = k * G
Q = FLAG * P
res = []
for _ in range(42):
a = randrange(G.order())
b = randrange(G.order())
res.append((a, b, a * P + b * Q))
print(res)
We have the curve parameters ECSC{}
) as a decimal number and computes
Finally, the script gives us
Solution
First of all, we notice that the order of
$ sage -q
sage: proof.arithmetic(False)
....: p = 1789850433742566803999659961102071018708588095996784752439608585988988036381340404632423562593
....: a = 62150203092456938230366891668382702110196631396589305390157506915312399058961554609342345998
....: b = 1005820216843804918712728918305396768000492821656453232969553225956348680715987662653812284211
....: F = GF(p)
....: E.<G> = EllipticCurve(F, [a, b])
sage: factor(G.order())
12775224751 * 13026062843 * 18511195699 * 24508446437 * 25961704469 * 28450356619 * 31034521019 * 31982226581 * 32337773063
Therefore, the Discrete Logarithm Problem (ECDLP) is easy to solve using Pohlig-Hellman algorithm. As a result, if we have
In order to find
Using both equations, we can isolate
Flag
And now we just solve the ECDLP
$ python3 solve.py
ECSC{l0g_pr0perty_w0rks_d1scr3t3ly_9d03dde5}
The full script can be found in here: solve.py
.