はじめに
2025年8月16日 10:00(JST) から 8月18日 10:00(JST) に開催された、sekaiCTF 2025 crypto / SSSS の writeup です。1日目のみの参加だったので、追加問題はノータッチです。
会社のチームで参加したので、成績は残しません。
昨年、ズタボロにされた思い出のある CTF でしたが、今年は1問解けたことで、去年の雪辱を晴らせたと思ってます。ただ、2問目の Alter Ego をチラ見して、これが medium か、、、？と天を仰ぎ、先の長さを実感しました。来年も参加する動機ができました。
writeup
SSSS
chall.py
import random, os
p = 2 ** 256 - 189
FLAG = os.getenv("FLAG", "SEKAI{}")
def challenge(secret):
t = int(input())
assert 20 <= t <= 50, "Number of parties not in range"
f = gen(t, secret)
for i in range(t):
x = int(input())
assert 0 < x < p, "Bad input"
print(poly_eval(f, x))
if int(input()) == secret:
print(FLAG)
exit(0)
else:
print(":<")
def gen(degree, secret):
poly = [random.randrange(0, p) for _ in range(degree + 1)]
index = random.randint(0, degree)
poly[index] = secret
return poly
def poly_eval(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
if __name__ == "__main__":
secret = random.randrange(0, p)
for _ in range(2):
challenge(secret)ncat しても、プロンプトはなく、標準入力を待ち受けてる状態です。
solve
20 ~ 50 の範囲の整数 t を標準入力で待ち受けてます。この t をもとに、t+1 個の係数をもつ、有限体上の多項式を定義します。
y \equiv \sum_{i=0}^{t} c_i\,x^i \pmod{p}なお係数は、gen関数によって、ランダムな位置で secret に置換されてます。
t 回多項式を出力したのち、再度標準入力を求められます。ここで入力した値が secret であれば、FLAG が出力されます。この一連の操作を2回まで行います。secret の値は初めに乱数として定義されてるので、係数を求める操作を2回行い、それらの内同じ値が secret となります。
というわけで係数を求めていきます。 y \equiv 3 + 5x + 7x^2 \mod{p} のような簡単な例を考えます。 x = 1, 2, 3 における値を y_1 = f(1), \quad y_2 = f(2), \quad y_3 = f(3) と書くと、各係数 [c_0, c_1, c_2 ]^T に対して次の連立一次方程式となります。
\underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix}}_{\displaystyle V} \begin{bmatrix} c_0 \ c_1 \ c_2 \end{bmatrix}^T \equiv \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} \equiv \begin{bmatrix} 15 \\ 7 \\ 13 \end{bmatrix} \pmod{p}このとき、掃き出し法で V を単位行列にしてくと、
\left[ \begin{array}{ccc|c} 1 & 1 & 1 & y_1 \\ 1 & 2 & 4 & y_2 \\ 1 & 3 & 9 & y_3 \end{array} \right] \ \xrightarrow{\ R_2 \leftarrow R_2 - R_1,\ \ R_3 \leftarrow R_3 - R_1\ } \left[ \begin{array}{ccc|c} 1 & 1 & 1 & y_1 \\ 0 & 1 & 3 & y_2 - y_1 \\ 0 & 2 & 8 & y_3 - y_1 \end{array} \right] \ \xrightarrow{\ R_3 \leftarrow R_3 - 2R_2\ } \left[ \begin{array}{ccc|c} 1 & 1 & 1 & y_1 \\ 0 & 1 & 3 & y_2 - y_1 \\ 0 & 0 & 2 & y_3 - 2y_2 + y_1 \end{array} \right]よって
\left\{ \begin{array}{l} c_2 \equiv (2)^{-1} \left(y_3 - 2y_2 + y_1\right) \pmod{p},\\ c_1 \equiv \left(y_2 - y_1\right) - 3c_2 \pmod{p},\\ c_0 \equiv y_1 - c_1 - c_2 \pmod{p} \end{array} \right.ここで、有限体上での p=17 における 2 の逆元は 9 であることに注意すると、各係数が、 c_0 = 3, c_1= 5, c_2 = 7 と計算できます。
つまり、求めたい係数の数だけ、線形独立な方程式が必要になるということがわかります。係数が t+1 個あるなら、方程式も t+1 個必要とういことです。
しかし、chall.py を見てみると、求めたい係数が t+1 個なのに対して、方程式は t 個しか用意できず、係数ベクトルを一意に復元することができません。
for i in range(t): # t回、xに代入できる⇒t個方程式が用意できる
x = int(input())
assert 0 < x < p, "Bad input"
print(poly_eval(f, x))
# 係数t+1, xの次数t
def poly_eval(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p そこで、掃き出し法の過程で係数項を減らせるような、いい感じの x を選んで代入することを考えます。± のペアを代入すれば係数項が減らせるのでは？という気持ちで実験してみます。solve_right の実装がどうなってるのかはわからないが、± で代入すればよしなに掃き出し法で消えるような w を求めてくれるだろう
p = 17
F = GF(p)
t = 4 # 方程式の数, xのべき乗数
xs = [2, -2, 4, -4] # 方程式に代入する値
V = Matrix(F, [[x**j for j in range(t+1)] for x in xs])
VT = V.transpose()
print(V)
"""
[ 1 2 4 8 16]
[ 1 15 4 9 16]
[ 1 4 16 13 1]
[ 1 13 16 4 1]
"""
c = vector(F, [5, 7, 9, 11, 13]) # なんでもいい 今回はc_1=7 がsecretとする
y = V * c # 方程式の値
print(y)
"""
(11, 11, 10, 8)
"""
k = 1 # c1を取り出す
e1 = vector(F, [1 if i==k else 0 for i in range(t+1)])
w = VT.solve_right(e1) # Ax=b の x を返す 今回は V^Tw=e1
c1 = w * y
print(c1) # c_1=7が得られる4本の方程式の x 対して、xs = [2, -2, 4, -4] をそれぞれ代入することで、行列 V は上記のようにになります。抜き出したい係数の位置 k に対して、基底ベクトル e_k を用意し、 V^T w = e_k を掃き出し法で解いて w を得ます。このとき、代入値 xs がそれぞれ ± のペアの対称性から、得られた w は w^T y の計算で偶数番目の係数項が消え、奇数番目の係数項だけが取り出せるような値となりました。あとは w^T y を計算することで、secret を取り出すことができます。
あとは問題に合わせて solve を書いてくだけです。
p = (2**256) - 189
F = GF(p)
t = 50
# 方程式への代入値で±1~±25
xs_rows = []
for A in range(1, t//2 + 1):
xs_rows.append(A)
xs_rows.append(-A)
xs_send = [int(F(xs)) for xs in xs_rows]
V = Matrix(F, [[x**j for j in range(t+1)] for x in xs_send])
VT = V.transpose()
r = remote("ssss.chals.sekai.team", 1337, ssl=True)
r.sendline(str(t))
y1 = []
for x in xs_send:
r.sendline(str(x))
y1.append(int(r.recvline())) # x を代入してpoly_evalで出力される y を得てる
print(y1) # t=50個
r.sendline(b"0") # 一回目の標準入力スキップ
r.recvline()
y1F = vector(F, y1)
S1 = set()
for k in range(1, t+1, 2):
e = vector(F, [1 if i==k else 0 for i in range(t+1)]) # 奇数番目が1の基底ベクトル
w = VT.solve_right(e) # 掃き出し法
S1.add(int(w*y1F)) # 係数集合獲得
print(S1)
# 一回目と同じことをやって、係数集合獲得
r.sendline(str(t))
y2 = []
for x in xs_send:
r.sendline(str(x))
y2 .append(int(r.recvline()))
print(F"y2:{len(y2)}")
y2F = vector(F, y2)
S2 = set()
for k in range(1, t+1, 2):
e = vector(F, [1 if i==k else 0 for i in range(t+1)])
w = VT.solve_right(e)
S2.add(int(w*y2F))
print(S2)
if S1 & S2: # 係数集合同士の積集合をとって、存在すればそれがsecret
print("OK")
secret = (S1 & S2).pop()
r.sendline(str(secret))
while True:
print(r.recvline())
else:
print("miss")限界の t=50 を指定して、±1 ~ ±25 を xs として方程式に代入して、行列 V を求めてます。前述の議論から奇数番目の項から係数が 25 個得られるはずですが、このうちどれが secret かはわかりません。そのため、一回目はわざとミスして係数集合 S1 だけを得ます。二回目も同様に 25 個の係数集合 S2 が得られ、この二つの S1 と S2 の積集合が secret となります。
なお、これはたまたまgen関数によって secret の配置される位置が奇数番目だった事象が二回連続で起きた場合にのみ解けます。大体25%です。
問題文の Shamir についてですが、Shamir の秘密分散という手法があり、秘密情報が一定数以上集まることで元の情報が復元できるとのことです。今回は二つの秘密情報が含まれてるセットを突合させることで、秘密情報を特定することで FLAG 獲得につながりました。
Alter Ego
全くわからない、、、楕円曲線の基礎もおろそかなので upsolve も厳しいかな、、、
コメント