ångstromCTF 2021 - Substitution

문제 개요

Source nc crypto.2021.chall.actf.co 21601chall.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)
답을 주셨으니 이 문제를 풀어주세요.

해설

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)