angstrom CTF 2021 | substitution - crypto-writeup-public

#angstromctf2021

#!/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. ")

((k1 * value + k2) * value + k3) ... という感じで、k1, k2, ... を求める

もう少し書き直して、実はこうで、 $x$ を好きに指定できる

$a_kx^k + a_{k-1}x^{k-1} + \dots + a_0 = \sum a_ix^i \mod M$

例えば $x^2 \equiv 0 \mod M$ となるような $x$ を見つけることができれば……これは $\sqrt{M}$ ですが、今回modは素数なのでこういう値はない

雑に次のようなLLLで解けないだろうか。でもこれだとどういう $x$ を選ぶのが良いのだろう

$\begin{pmatrix} a_k & a_{k-1} & \dots & a_0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & \cdots & x^k \ 0 & 1 & \cdots & x^{k-1} \ & & \ddots & \vdots \ & & & -c + Mk \end{pmatrix}$

……とか無駄なことを考えていたが、何回でもリクエストできるのだから、フラグの長さを $k$ として $k$ 個の式を建てて連立方程式を解けば良い。実際には $k$ より長くしても余った変数が0でうまるので何でも良い。剰余連立方程式を行列で解く

from ptrlib import Socket


M = 691

for k in range(5, 50, 5):
    sock = Socket("crypto.2021.chall.actf.co", 21601)
    # sock = Socket("localhost", 19999)
    X = []
    Y = []
    for i in range(1, k+1):
        xs = [i^j % M for j in range(k)][::-1]
        X.append(xs)
        sock.sendlineafter("> ", str(i))
        y = int(sock.recvlineafter(">> "))
        Y.append(y)

    X = matrix(Zmod(M), X)
    Y = matrix(Zmod(M), Y).transpose()

    recovered = list(X.solve_right(Y).transpose())[0]
    try:
        print(repr(bytes(recovered)))
    except:
        print(recovered)

    sock.close()