DownUnderCTF 2021 | Subsutitution Cipher 2

#joseph

#downunderctf2021

from string import ascii_lowercase, digits
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET)

def encrypt(msg, f):
    ct = ''
    for c in msg:
        ct += CHARSET[f.substitute(CHARSET.index(c))]
    return ct

P.<x> = PolynomialRing(GF(n))
f = P.random_element(6)

FLAG = open('./flag.txt', 'r').read().strip()

enc = encrypt(FLAG, f)
print(enc)

単一換字暗号

今度は6次の多項式が使われている。DUCTF{から始まり}で終わることが推測できるので、多項式補間でを推測すれば良い

from string import ascii_lowercase, digits
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET)

P.<x> = PolynomialRing(GF(n))

with open("output.txt") as f:
    z = f.read().strip()

xs = []
ys = []

for i, c in enumerate("DUCTF{"):
    xs.append(CHARSET.index(c))
    y = CHARSET.index(z[i])
    ys.append(y)

xs.append(CHARSET.index('}'))
ys.append(CHARSET.index(z[-1]))

f = P.lagrange_polynomial(list(zip(xs, ys)))
print(f)

flag = []
for i in range(len(z)):
    y = CHARSET.index(z[i])
    roots = ((f - y).roots())
    for r in roots:
        print(CHARSET[r[0]], end="")
    print()