ångstromCTF 2021 - Substitution

問題概要

Source

nc crypto.2021.chall.actf.co 21601

chall.py

#!/usr/bin/python

from functools import reduce

with open("flag", "r") as f:
    key = [ord(x) for x in f.read().strip()]



def substitute(value):
    return (reduce(lambda x, y: x*value+y, key))%691



print("Enter a number and it will be returned with our super secret synthetic substitution technique")
while True:
    try:
        value = input("> ")
        if value == 'quit':
            quit()
        value = int(value)
        enc = substitute(value)
        print(">> ", end="")
        print(enc)
    except ValueError:
        print("Invalid input. ")

入力として与えた整数$a$に対して、

$a^{n-1}k_{n-1}+a^{n-2}k_{n-2}+\cdots+a^2k_2+ak_1+k_0 (\mod 691)$

をくれるので解いてね、という問題です。

解説

$a=0,1,\cdots,690$まで全部取れるので取っちゃいましょう。その上で、それぞれの計算結果から答えを求めますが、連立すれば理論的には691文字分までは解けそうです。sageにお願いしてみましょう。

collect.py

# crypto.2021.chall.actf.co 21601
from pwn import *

r = remote("crypto.2021.chall.actf.co", 21601)

res = []

for i in range(691):
    r.recvuntil(b"> ")
    r.sendline(str(i))
    s = r.recvline().decode()
    v = int(s.split(" ")[1])
    print(v)
    res.append((i, v))

with open("solve.py", "w") as f:
    f.write("output = ")
    f.write(str(res))

solve.sage

output = [(0, 125), (1, 492), ...]

F =GF(691)
R = F['x']
res = list(R.lagrange_polynomial(output))[::-1]
print(res)

flag = ""
for a in res:
  flag += chr(a)
print(flag)