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

nbits = 1024
e = 5
flag = open("flag.txt").read().strip()
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 , this has a root . We could try to find this root using Coppersmith, but it turns out it not possible since the size of is larger than . However, due to a publication by Håstad, we can construct the following:

where

It is easy to construct as

using the Chinese Remainder Theorem. Clearly, also has a root (this is easy to check!). Since is strictly smaller than , the polynomial roots of can be found using Coppersmith!

p = data['n'][0] * data['n'][1] * data['n'][2] * data['n'][3] * data['n'][4]
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[5], p)
print f.small_roots(X=2^512, beta=1)[0]

The code outputs the long integer representation of

PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}

### Like this:

Like Loading...