easy pseudo random - zer0pts ctf 2021

challenge

The following code and the outputs was given. It seems that the flag is encrypted with random numbers. We can get the upper k bits of two consecutive values, named w0 and w1. We can get the flag when the prediction of pseudo random numbers can be achieved using these.

# task.sage
from Crypto.Util.number import*
from flag import flag

nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)

b = randrange(p)
d = 2
F = v^2 + b

v0 = randrange(p)
v1 = F(v0)

k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))

# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)

print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")

solution

Let \(F(v) = v^2 + b\) over \(\mathbb{F}_p\) and \(n\) be the nbits. Then \(v_0\) and \(v_1\) are given by the following equations.
\[\begin{eqnarray} v_0 &=& 2^{n-k} w_0 + x \\ v_1 &=& 2^{n-k} w_1 + y \end{eqnarray}\]
Here \(x\) and \(y\) are unknown quantities. If they are found, we can expect the pseudo random sequences. Expanding \(v_1\), we get further
\[\begin{eqnarray} v_1 &=& F(v_0) \\ &=& (2^{n-k}w_0 + x)^2 + b　\end{eqnarray}\]
Thus, we get the following equation
\[\begin{eqnarray} f(x, y) &=& 2^{n-k}w_1 + y - ((2^{n-k}w_0 + x)^2 + b) \\ &=& y + c_2x^2 + c_1x + c_0 \\ &=& 0\end{eqnarray}\]
where \(c_i \ (i=0,...,2)\) are suitable constants (They are explicitly depend on know parameters).
For easy understanding, the equation is written \(y + c_2x^2 + c_1x + c_0 \equiv 0 \mod p\) as a congruence in integers.

Now, \(k = \lceil \frac{nd}{d + 1} \rceil \ where\ d = \deg f\), and therefore we can believe that required roots are found by Coppersmith's method.

# solve.sage
from Crypto.Util.number import *
from small_roots import small_roots

nbits = 256
with open("output.txt") as f:
	while True:
		buf = f.readline()
		if not buf:
			break
		exec(buf)

Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
F = v^2 + b
Pf.<x, y> = PolynomialRing(Fp)

d = 2
k = ceil(nbits * (d / (d + 1)))
delta = float(1 / (d + 1))

bounds = (floor(p^delta), floor(p^delta))
f = (y + w1 * pow(2, nbits - k)) - ((x + w0 * pow(2, nbits - k))^2 + b)

# multivariate coppersmith
res = small_roots(f, bounds)
print(res[0])

x0 = res[0][0]
x1 = res[0][1]
v0 = x0 + w0 * pow(2, nbits - k)
v1 = x1 + w1 * pow(2, nbits - k)
print(v0, v1)

v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)
print(long_to_bytes(m))

Here is the flag zer0pts{is_blum_blum_shub_safe?}