Context
We are given the code used to crypt the flag and some other informations.
Code
Here is the code given:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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())
The flag is crypted using AES. The key used in the encryption is key = str(a) + str(b).
So, in order to find the key, we need to find a et b.
Resolution
a and b are the coefficients of an elliptic curve defined over a finite field. They determine the shape and properties of the curve.
The code asserts that the determinant of the curve, calculated using determinant = 4 * a**3 + 27 * b**2, is not zero. This check ensures that the curve is non-singular and can be used for cryptographic operations.
After defining the elliptic curve E using the coefficients a and b, the code generates two random points G and H on the curve.
In the code p is the prime modulus of the finite field over which the curve is defined.
We know that sage uses the Weierstrass equation for the elliptic curve.
So, we have:
1
2
G_y ** 2 = G_x ** 3 + a * G_x + b
H_y ** 2 = H_x ** 3 + a * H_x + b
By isolating b,
1
G_y ** 2 - G_x ** 3 - a * G_x = H_y ** 2 - H_x ** 3 - a * H_x
1
a * G_x - a * H_x = G_y ** 2 - G_x ** 3 - H_y ** 2 + H_x ** 3
1
a * (G_x - H_x) = (G_y ** 2 - G_x ** 3) - (H_y ** 2 - H_x ** 3)
So, we have
1
2
3
a = (G_y ** 2 - G_x ** 3) - (H_y ** 2 - H_x ** 3) / (G_x - H_x)
b = G_y ** 2 - G_x ** 3 - a * G_x
Implementation
I defined a function to ensure the results of each operations are modulo p:
1
2
def moins(x, y, p):
return (x % p - y % p + p) % p
We calculate a and b:
1
2
3
4
5
6
# Solve for a
a = moins(moins(G_y ** 2, H_y ** 2, p), moins(G_x ** 3, H_x ** 3, p), p) * pow(moins(G_x, H_x, p), -1, p) % p
# Solve for b using one of the expressions for b
b = moins(G_y ** 2, G_x ** 3, p)
b = moins(b, a * G_x % p, p)
We can now decrypt the flag:
1
2
3
4
5
key = str(a) + str(b)
aes = AES.new(hashlib.sha1(key.encode()).digest()[:16], AES.MODE_CBC, iv=iv)
flag = aes.decrypt(secret_message)
print(flag.decode())
Output:
