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!}