Difficulté: facile

Points: 796

Challenge

Énoncé

Ce challenge nous donne deux fichiers. Le premier data.txt:

93808707311515764328749048019429156823177018815962831703088729905542530725 144188081159786866301184058966215079553216226588404139826447829786378964579
139273587750511132949199077353388298279458715287916158719683257616077625421 30737261732951428402751520492138972590770609126561688808936331585804316784
231933770389389338159753408142515592951889415487365399671635245679612352781
8233d04a29befd2efb932b4dbac8d41869e13ecba7e5f13d48128ddd74ea0c7085b4ff402326870313e2f1dfbc9de3f96225ffbe58a87e687665b7d45a41ac22
00b7822a196b00795078b69fcd91280d

Ainsi que le code source challenge.py :

from sage.all import EllipticCurve, GF
import hashlib
from Crypto.Cipher import AES
from secret import FLAG
from os import urandom

p = 231933770389389338159753408142515592951889415487365399671635245679612352781
a = ?
b = ?

determinant = 4 * a**3 + 27 * b**2
assert determinant != 0

E = EllipticCurve(GF(p), [a,b])
G = E.random_point()
H = E.random_point()

print(G.xy()[0], G.xy()[1])
print(H.xy()[0], H.xy()[1])
print(p)

iv = urandom(16)
key = str(a) + str(b)
aes = AES.new(hashlib.sha1(key.encode()).digest()[:16], AES.MODE_CBC, iv=iv)
cipher = aes.encrypt(FLAG)
print(cipher.hex())
print(iv.hex())

Solution

On comprend rapidement que le flag a été chiffré en utilisant l’algorithme AES. Heureusement on nous donne des informations sur la clé de chiffrement, il s’agit de la concaténation des coefficients a et b d’une courbe éliptique dont l’on connait les coordonnées de 2 points. Utilisons ces coordonnées pour retrouver la clé et déchiffrer le flag.

L’équation d’une courbe elliptique est $y^2 = x^3 + ax + b \mod{p}$

Il s’agit d’un système de deux équations à deux inconnus dont la solution est :

$a \equiv ((y_G^2 - y_H^2) - (x_G^3 - x_H^3)) (x_G - x_H)^{-1}\mod{p} $

$ b \equiv (y_G^2 - x_G^3 - ax_G) \mod{p} $

Le script suivant utilise ces formules pour retrouver la clé et déchiffrer le flag :

from Crypto.Cipher import AES
import hashlib

cipher = bytes.fromhex("8233d04a29befd2efb932b4dbac8d41869e13ecba7e5f13d48128ddd74ea0c7085b4ff402326870313e2f1dfbc9de3f96225ffbe58a87e687665b7d45a41ac22")

p = 231933770389389338159753408142515592951889415487365399671635245679612352781
iv = bytes.fromhex("00b7822a196b00795078b69fcd91280d")

x1 = 93808707311515764328749048019429156823177018815962831703088729905542530725
y1 = 144188081159786866301184058966215079553216226588404139826447829786378964579
x2 = 139273587750511132949199077353388298279458715287916158719683257616077625421
y2 = 30737261732951428402751520492138972590770609126561688808936331585804316784

a = (((y1**2 - y2**2) - (x1**3 - x2**3)) * pow(x1 - x2, -1, p)) % p
b = (y1**2 - x1**3 - a*x1) % p

key = str(a) + str(b)

aes = AES.new(hashlib.sha1(key.encode()).digest()[:16], AES.MODE_CBC, iv=iv)

flag = aes.decrypt(cipher).decode('ascii')
print(f"{flag}")

404CTF{70u735_l35_gr4nd35_p3r50nn3s_0nt_d_@b0rd_373_d35_3nf4n7s}