In this CTF challenge we are given the following python script:
from curve_operations import Point,Curve # Custom module
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
class Dual_EC:
def __init__(self):
p = 229054522729978652250851640754582529779
a = -75
b = -250
self.curve = Curve(p,a,b)
self.P = Point(97396093570994028423863943496522860154 , 2113909984961319354502377744504238189)
self.Q = Point(137281564215976890139225160114831726699 , 111983247632990631097104218169731744696)
self.set_initial_state()
def set_initial_state(self):
self.state = ???SECRET🤫???
def set_next_state(self):
self.state = self.curve.scalar_multiply(self.P, self.state).x
def gen_rand_num(self):
rand_point = self.curve.scalar_multiply(self.Q, self.state)
rand_num = rand_point.x
self.set_next_state()
return rand_num
def main():
prng = Dual_EC()
flag = b'flag{test}'
print("My PRNG has passed International Standards!!!")
print("Here is a Sample Random Number to prove it to you : ", prng.gen_rand_num())
key = long_to_bytes((prng.gen_rand_num() << 128) + prng.gen_rand_num())
iv = long_to_bytes(prng.gen_rand_num())
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted_bytes = cipher.encrypt(pad(flag, AES.block_size))
print('Encrypted bytes : ',encrypted_bytes)
if(__name__ == "__main__"):
main()
and the out.txt:
My PRNG has passed International Standards!!!
Here is a Sample Random Number to prove it to you : 222485190245526863452994827085862802196
Encrypted bytes : b'BI\xd5\xfd\x8e\x1e(s\xb3vUhy\x96Y\x8f\xceRr\x0c\xe6\xf0\x1a\x88x\xe2\xe9M#]\xad\x99H\x13+\x9e5\xfd\x9b \xe6\xf0\xe10w\x80q\x8d'
In the source code, an elliptic curve with the following parameters is declared:
p = 229054522729978652250851640754582529779
a = -75
b = -250
The script also declares an initial state, or an initial seed for the PRNG. However, it is secret.
For generating random numbers, the script computes the scalar multiplication of Q and the state, and uses the x value as the rand_num Then, the next state is generated as the x value of $state \cdot P$
We are given the first prng number $R.x = (Q \cdot state0).x$ which means we have to solve the discrete logarithm problem to recover state0
When we have state0, we can generate the next numbers and then get the value for the key and iv:
key = long_to_bytes((prng.gen_rand_num() << 128) + prng.gen_rand_num())
iv = long_to_bytes(prng.gen_rand_num())
It turns out the curve defined by these parameters
p = 229054522729978652250851640754582529779
a = -75
b = -250
is not an elliptic curve after all. This is because the delta is equal to 0:
delta = -16*(4*a**3 + 27*b**2) % p
print(f"delta: {delta}")
# delta: 0
This is actually good news, because we can map the points to the multiplicative group and solve the discrete logarithm a lot easier.
First, we have to define our parameters, our points, our curve and lift the point R:
p = 229054522729978652250851640754582529779
a = -75
b = -250
F = GF(p)
# Known points P and Q
P = (97396093570994028423863943496522860154 , 2113909984961319354502377744504238189)
Q = (137281564215976890139225160114831726699 , 111983247632990631097104218169731744696)
R_x = F(222485190245526863452994827085862802196)
rhs = R_x^3 + a * R_x + b
R_y = rhs.sqrt()
R = (R_x, R_y)
# define the curve / function
A.<x, y> = PolynomialRing(ZZ)
f = x^3 + a*x + b
Then, we have to find the singularity of the curve. This is the point of intersection on the nodal curve, and it is where both partial derivatives are equal to 0:
\[\large \begin{flalign} \nonumber && \frac{dy^2}{dx} &= 3x^2 + a = 0 && \text{mod } p \end{flalign}\] \[\large \begin{flalign} \nonumber && \frac{dxy}{dy} &= 2y = 0 && \text{mod } p \end{flalign}\]For $2y = 0$, it is easy. The y coordinate will be 0. However, to find x, we will have:
\[\large \begin{flalign} \nonumber && \frac{dy^2}{dx} &= 3x^2 + a = 0 && \text{mod } p \end{flalign}\] \[\large \begin{flalign} \nonumber && x^2 = - \frac{a}{3} && \text{mod } p \end{flalign}\]a_over_3 = (-a/3) % p
x_0 = -F(a_over_3).sqrt()
We now have to shift x with this large value, so that we can have the singularity located at (0, 0). This is as simple as substituting for x. We don’t have to substitute for y, because the “shift” for y is 0.
f_ = f.subs(x=x + x_0)
P_ = (P[0] - x_0, P[1])
Q_ = (Q[0] - x_0, Q[1])
R_ = (R[0] - x_0, R[1])
The shifted function f_ is equal to:
\[\large x^3 + 229054522729978652250851640754582529764 \cdot x^2\]or rather (factored_f):
\[\large x^2(229054522729978652250851640754582529764 + x)\]Which accurately describes an elliptic node:
\[\large x^2(\alpha + x)\]Since we are working with a nodal curve, we know it will map to the multiplicative group. However, we need to figure out which field it maps to. What we can do is investigate whether there exists some integer $\beta$ which, when squared and under modulus p, equals the value $\alpha$. To clarify:
\[\large \begin{flalign} \nonumber && \alpha = \beta^2 && \text{mod } p \end{flalign}\]The value $\beta$ can then be used to map to the multiplicative group $\mathbb{F}^*_p$
factored_f = f_.factor()
alpha = factored_f[0][0].constant_coefficient()
# Calculate beta such that beta^2 ≡ alpha mod p
beta = GF(p)(alpha).square_root()
And we can now perform the map to the multiplicative group. The map is:
\[\large (x, y) \large\mapsto \frac{y \;+\; \beta x}{y \;-\; \beta x}\]P_map = (P_[1] + beta*P_[0]) / (P_[1] - beta*P_[0]) % p
Q_map = (Q_[1] + beta*Q_[0]) / (Q_[1] - beta*Q_[0]) % p
R_map = (R_[1] + beta*R_[0]) / (R_[1] - beta*R_[0]) % p
We can now calculate the discrete log of R_map and Q_map to find state0! Remember, $R.x = (Q \cdot state0).x$
state_0 = discrete_log(R_map, Q_map)
print(f"State 0: {state_0}")
#State 0: 23936863590183712869017528905910138331
Now that we have the initial state, we can easily recover the iv and the key. However, we will have to implement some custom functions and classes for our curves and such (because sagemath refuses to instantiate a super-singular curve). I will omit the explanation of the classes, but you can check the solve script below for the code.
prng = Dual_EC_PRNG(state_0, curve, P, Q)
key = long_to_bytes((prng.gen_rand_num() << 128) + prng.gen_rand_num())
iv = long_to_bytes(prng.gen_rand_num())
ciphertext = b'BI\xd5\xfd\x8e\x1e(s\xb3vUhy\x96Y\x8f\xceRr\x0c\xe6\xf0\x1a\x88x\xe2\xe9M#]\xad\x99H\x13+\x9e5\xfd\x9b \xe6\xf0\xe10w\x80q\x8d'
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext_padded = cipher.decrypt(ciphertext)
plaintext = unpad(plaintext_padded, AES.block_size)
print(plaintext)
# b'ironCTF{5h0uld_h4v3_1is7en3d_t0_d4v1d_a1r34dy}'
And there is our flag!
from sage.all import *
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
# Define the finite field and parameters
p = 229054522729978652250851640754582529779
a = -75
b = -250
F = GF(p)
# Known points P and Q
P = (97396093570994028423863943496522860154 , 2113909984961319354502377744504238189)
Q = (137281564215976890139225160114831726699 , 111983247632990631097104218169731744696)
R_x = F(222485190245526863452994827085862802196)
rhs = R_x^3 + a * R_x + b
R_y = rhs.sqrt()
R = (R_x, R_y)
# Define the elliptic curve equation y^2 = x^3 + ax + b
A.<x, y> = PolynomialRing(ZZ)
f = x^3 + a*x + b
# x_0, the x-coordinate of the singularity
a_over_3 = (-a/3) % p
x_0 = -F(a_over_3).sqrt()
# Shift the curve by x_0 to move the singularity to (0, 0)
f_ = f.subs(x=x + x_0)
P_ = (P[0] - x_0, P[1])
Q_ = (Q[0] - x_0, Q[1])
R_ = (R[0] - x_0, R[1])
factored_f = f_.factor()
alpha = factored_f[0][0].constant_coefficient()
# Calculate beta such that beta^2 ≡ alpha mod p
beta = GF(p)(alpha).square_root()
# Map shifted points to the multiplicative group F*_p
P_map = (P_[1] + beta*P_[0]) / (P_[1] - beta*P_[0]) % p
Q_map = (Q_[1] + beta*Q_[0]) / (Q_[1] - beta*Q_[0]) % p
R_map = (R_[1] + beta*R_[0]) / (R_[1] - beta*R_[0]) % p
#state_0 = discrete_log(R_map, Q_map)
#print(f"State 0: {state_0}")
state_0 = 23936863590183712869017528905910138331
class Point:
def __init__(self, x, y, curve, is_infinity=False):
self.x = x
self.y = y
self.curve = curve # Reference to the curve
self.is_infinity = is_infinity
def __eq__(self, other):
if self.is_infinity and other.is_infinity:
return True
if self.is_infinity or other.is_infinity:
return False
return self.x == other.x and self.y == other.y and self.curve == other.curve
def __neg__(self):
if self.is_infinity:
return self
return Point(self.x, -self.y % self.curve.p, self.curve)
def __add__(self, Q):
P = self
if P.is_infinity:
return Q
if Q.is_infinity:
return P
if P.x == Q.x and (P.y != Q.y or P.y == 0):
return self.curve.infinity
if P.x == Q.x:
# Point doubling
lam_num = (3 * P.x * P.x + self.curve.a) % self.curve.p
lam_den = (2 * P.y) % self.curve.p
else:
# Point addition
lam_num = (Q.y - P.y) % self.curve.p
lam_den = (Q.x - P.x) % self.curve.p
# Compute the slope (lambda)
try:
lam = (lam_num * pow(lam_den, -1, self.curve.p)) % self.curve.p
except ZeroDivisionError:
return self.curve.infinity
# Compute the new point coordinates
x_r = (lam * lam - P.x - Q.x) % self.curve.p
y_r = (lam * (P.x - x_r) - P.y) % self.curve.p
return Point(x_r, y_r, self.curve)
def __rmul__(self, k):
result = self.curve.infinity
addend = self
while k:
if k & 1:
result = result + addend
addend = addend + addend
k >>= 1
return result
def __repr__(self):
if self.is_infinity:
return "Point(infinity)"
return f"Point({self.x}, {self.y})"
class Curve:
def __init__(self, p, a, b):
self.p = p # Prime modulus
self.a = a
self.b = b
self.infinity = Point(None, None, self, is_infinity=True)
def is_on_curve(self, P):
if P.is_infinity:
return True
return (P.y * P.y - (P.x * P.x * P.x + self.a * P.x + self.b)) % self.p == 0
class Dual_EC_PRNG:
def __init__(self, initial_state, curve, P, Q):
self.state = initial_state # Initial state (integer)
self.curve = curve
self.P = P
self.Q = Q
def set_next_state(self):
# Scalar multiply P by the current state and take the x-coordinate as the next state
new_point = self.state * self.P
self.state = new_point.x
def gen_rand_num(self):
# Scalar multiply Q by the current state and take the x-coordinate as the random number
rand_point = self.state * self.Q
rand_num = rand_point.x
self.set_next_state()
return rand_num
# Initialize the curve
curve = Curve(p, a, b)
# Define points P and Q
P = Point(
97396093570994028423863943496522860154,
2113909984961319354502377744504238189,
curve
)
Q = Point(
137281564215976890139225160114831726699,
111983247632990631097104218169731744696,
curve
)
# Verify that points are on the curve
assert curve.is_on_curve(P), "Point P is not on the curve"
assert curve.is_on_curve(Q), "Point Q is not on the curve"
# Initialize PRNG
prng = Dual_EC_PRNG(state_0, curve, P, Q)
print(f"leaked prng value: {prng.gen_rand_num()}")
# Generate rand1, rand2, rand3
key = long_to_bytes((prng.gen_rand_num() << 128) + prng.gen_rand_num())
iv = long_to_bytes(prng.gen_rand_num())
print(f"Derived AES Key (hex): {key.hex()}")
print(f"Derived AES IV (hex): {iv.hex()}")
# Encrypted bytes from the challenge
ciphertext = b'BI\xd5\xfd\x8e\x1e(s\xb3vUhy\x96Y\x8f\xceRr\x0c\xe6\xf0\x1a\x88x\xe2\xe9M#]\xad\x99H\x13+\x9e5\xfd\x9b \xe6\xf0\xe10w\x80q\x8d'
# Initialize AES cipher in CBC mode
cipher = AES.new(key, AES.MODE_CBC, iv)
# Decrypt and unpad the plaintext
plaintext_padded = cipher.decrypt(ciphertext)
try:
plaintext = unpad(plaintext_padded, AES.block_size)
print("Decrypted Flag:", plaintext)
except ValueError:
print("Incorrect decryption. Possible wrong key/IV.")