Hide and seek

2 minutos de lectura

I have hidden my flag among the elliptic curve points. Go seek!
Challenge contributed by CryptoHack
Challenge files:
output.txt
hide_and_seek.sage

Análisis del código fuente

Se nos proporciona un script de SageMath que usa criptografía de curva elíptica para cifrar la 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)

Tenemos los parámetros de la curva $a, b, p$, por lo que podemos obtener el punto generador $G$. Luego, para cifrar la flag, el script toma un número aleatorio $k$ y calcula $P = k \cdot G$. Después de eso, el script toma la flag (sin ECSC{}) como número decimal y calcula $Q = \mathrm{FLAG} \cdot P$.

Finalmente, el script nos da $42$ resultados de: $(a, b, a \cdot P + b \cdot Q)$ con $a$ y $b$ aleatorios.

Solución

En primer lugar, notamos que el orden de $G$ es smooth (todos los factores son pequeños):

$ 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

Por lo tanto, el problema de logaritmo discreto (ECDLP) es fácil de resolver usando el algoritmo de Pohlig-Hellman. Como resultado, si tenemos $P$ y $Q = \mathrm{FLAG} \cdot P$, podemos encontrar $\mathrm{FLAG}$.

Para encontrar $P$ y $Q$, podemos tomar $2$ de las salidas:

$$ \begin{cases} R_1 = a_1 \cdot P + b_1 \cdot Q \\ R_2 = a_2 \cdot P + b_2 \cdot Q \end{cases} $$

Usando ambas ecuaciones, podemos despejar $P$ y $Q$:

$$ \begin{cases} P = (a_1 b_1^{-1} - a_2 b_2^{-1})^{-1} \cdot (b_1^{-1} \cdot R_1 - b_2^{-1} \cdot R_2) \\ Q = (a_1^{-1} b_1 - a_2^{-1} b_2)^{-1} \cdot (a_1^{-1} \cdot R_1 - a_2^{-1} \cdot R_2) \end{cases} $$

Flag

Y ahora solo resolvemos el ECDLP $Q = \mathrm{FLAG} \cdot P$ para obtener la flag:

$ python3 solve.py
ECSC{l0g_pr0perty_w0rks_d1scr3t3ly_9d03dde5}

El script completo se puede encontrar aquí: solve.py.