- Source: SECCON Beginners CTF 2024
- Author: kanon
RSAの問題。$e=17$となっており、平文$m$をごにょごにょした値が3つ与えられる。
server.py
#!/usr/local/bin/python
import os
from Crypto.Util.number import *
from random import randint
FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
e, nbit = 17, 512
m = bytes_to_long(FLAG)
p, q = getPrime(nbit), getPrime(nbit)
n = p * q
assert m < n
s = randint(0, 2**nbit)
t1, t2 = randint(0, 2**nbit), randint(0, 2**nbit)
c1 = pow(m + s, e, n)
c2 = pow(m + s * t1, e, n)
c3 = pow(m * t2 + s, e, n)
print(f"{e=}")
print(f"{n=}")
print(f"{t1=}")
print(f"{t2=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")
以降、mod nで考える。
$c_1, c_2, c_3$は以下の通りであり、$t_1, t_2$は既知、$s$はランダムな未知変数。
\displaylines{
c_1 = (m+s)^{e}
\\
c_2 = (m+st_1)^{e}
\\
c_3 = (mt_2+s)^{e}
}
これを変形するとこのような方程式が得られる。
\displaylines{
f_1 = (m+s)^{e} - c_1
\\
f_2 = (m+st_1)^{e} - c_2
\\
f_3 = (mt_2+s)^{e} - c_3
}
ここからこの方程式の関係を利用して$s$を消去したい。
多項式の変数を減らすテクニックにはCoppersmith's Short Pad Attackやグレブナー基底があるが、今回はCoppersmithの実装をバグらせてしまったので後者を用いる。
グレブナー基底に$f_1, f_2, f_3$を突っ込むと、$m^{17}+C$という形の式が得られた。
n, t1, t2, c1, c2, c3 = get_vals()
PR.<s, m> = PolynomialRing(Zmod(n))
f1 = (m + s)**e - c1
f2 = (m + s*t1)**e - c2
f3 = (m*t2 + s)**e - c3
polys = [f1, f2, f3]
basis = Ideal(polys).groebner_basis()
print(basis[0]) # m^17 + constant
この式を変形すると$m^{17}=-C$となるので、$e=17$個の$n$と$C$を得ることができればHåstad's Broadcast Attackによって$m$を復元できる。
solverを書く。
from pwn import *
from Crypto.Util.number import *
e = 17
def get_vals():
io = remote('localhost', 5000)
io.recvline() # trash e
n = int(io.recvline().decode().split('=')[1])
t1 = int(io.recvline().decode().split('=')[1])
t2 = int(io.recvline().decode().split('=')[1])
c1 = int(io.recvline().decode().split('=')[1])
c2 = int(io.recvline().decode().split('=')[1])
c3 = int(io.recvline().decode().split('=')[1])
io.close()
return ZZ(n), ZZ(t1), ZZ(t2), ZZ(c1), ZZ(c2), ZZ(c3)
def remove_s_with_groebner():
n, t1, t2, c1, c2, c3 = get_vals()
PR.<s, m> = PolynomialRing(Zmod(n))
f1 = (m + s)**e - c1
f2 = (m + s*t1)**e - c2
f3 = (m*t2 + s)**e - c3
polys = [f1, f2, f3]
basis = Ideal(polys).groebner_basis()
print(basis[0]) # m^17 + constant
return n, int(n-basis[0].coefficients()[1])
# Håstad's Broadcast Attack
ns = []
cs = []
for _ in range(e):
n, c = remove_s_with_groebner()
ns.append(n)
cs.append(c)
m = crt(cs, ns).nth_root(e)
print(long_to_bytes(m))
flagが得られた。
ctf4b{1f_y0u'r3_4n_1n73rm3d1473_b3y0nd_b361nn3r,_17'5_345y!_y4y}