# PlaidCTF’17 – Multicast

We are given a challenge which contains a Sage script, which holds the following lines of code

nbits = 1024
e = 5
assert len(flag) <= 64
m = Integer(int(flag.encode('hex'),16))
out = open("data.txt","w")

for i in range(e):
while True:
p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
ni = p*q
phi = (p-1)*(q-1)
if gcd(phi, e) == 1:
break

while True:
ai = randint(1,ni-1)
if gcd(ai, ni) == 1:
break

bi = randint(1,ni-1)
mi = ai*m + bi
ci = pow(mi, e, ni)
out.write(str(ai)+'\n')
out.write(str(bi)+'\n')
out.write(str(ci)+'\n')
out.write(str(ni)+'\n')


…along with a text file containing the encrypted flag. Let us first parse the file and put in a JSON structure

data = {'n' : [n0, n1, ...], 'a' : [a0, a1, ...], ...}

We see that the flag is encrypted several times, up to affine transformation. If we define a polynomial $g_i(x) = (a_ix + b_i)^5 - c_i \mod N_i$, this has a root $g_i(m) = 0 \mod N_i$. We could try to find this root using Coppersmith, but it turns out it not possible since the size of $(am + b)^5$ is larger than $N_i$. However, due to a publication by Håstad, we can construct the following: $g(x) = \sum \phi_i(N_i) g_i(x)$

where $\phi_i \mod N_j = \begin{cases}0 & \quad \text{if } i \neq j\\1 & \quad \text{when } i = j\\\end{cases}$

It is easy to construct $\phi_i$ as $\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}$

using the Chinese Remainder Theorem. Clearly, $g(x)$ also has a root $g(m) = 0 \mod (\prod N_i)$ (this is easy to check!). Since $m^5$ is strictly smaller than $\prod_k N_k$, the polynomial roots of $g(x)$ can be found using Coppersmith!

p = data['n'] * data['n'] * data['n'] * data['n'] * data['n']
PR. = PolynomialRing(Zmod(p))
f = 0

# compute the target polynomial
for i in range(0, 5):
q = p / data['n'][i]
qinv = inverse_mod(q, data['n'][i])
f = f + q * qinv * ((data['a'][i]*x + data['b'][i])^5 - data['c'][i])

# make f monic
f = f * inverse_mod(f, p)

print f.small_roots(X=2^512, beta=1)


The code outputs the long integer representation of

PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}