Plaid CTF 2017にTeam:Harekazeの一員として参加、とったのは10ptsだし、どうでもいい問題。
ただ暗号問題を悔しくて解法を見て解き直したのでその2問。
logarithms are hard (Misc 10)
What is e^(1.000000001)?
見たときにHintがあって
- 答えが2.7182818ではない
- 過去のPlaidの ◯◯ are hardを見て
とありました。過去の◯◯ are hardを見たら何らかのバグを使っているので
logarithms bugとかで検索すると
Logarithms Bugというページが見つかり、この中に答えもありました。
Flag : 2.7191928
multicast
解けなくてすごく悔しかった問題
nbits = 1024
e = 5
flag = open("flag.txt").read().strip()
assert len(flag) <= 64
m = Integer(int(flag.encode('hex'),16))
out = open("data.txt","w")
for i in range(e):
while True:
p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
ni = p*q
phi = (p-1)*(q-1)
if gcd(phi, e) == 1:
break
while True:
ai = randint(1,ni-1)
if gcd(ai, ni) == 1:
break
bi = randint(1,ni-1)
mi = ai*m + bi
ci = pow(mi, e, ni)
out.write(str(ai)+'\n')
out.write(str(bi)+'\n')
out.write(str(ci)+'\n')
out.write(str(ni)+'\n')
Håstad’s broadcast attackの応用であることの予想がつくけれどもここからがわからなかった。
CopperSmithの定理を使う必要がある
- CopperSmithの定理
ある整数 N と次数 d のモニック多項式 f ∈ Z[x] に対し、f(x) = 0 (mod N) を満たすすべての |x| < N1/d-ε (ε ≧ 0) は効率的に求めることができる。 w = min(1/ε, log2N) としたとき、計算時間はおおむね O(w) 次元の格子に対するLLL格子次元縮小アルゴリズムの計算時間となる。
これをHåstad’s broadcast attackに応用するとf(x) = 0 (mod N)となるf(x)の式を作る。
今回はmod Nの部分はHåstad’s broadcast attackを考えて
の場合,
とすることの予想はつく、これをNのもとで0にするためには、丁度良い単位行列をかけてを全て足せばよい。
$$
T = \left(
\begin{array}{ccccc}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1
\end{array}
\right)
$$
これで式はたったので後は計算するだけ,sageを使いました
import binascii
f = open('data.txt','r')
a = []
b = []
c = []
n = []
for i in range(5):
a.append(int(f.readline().strip()))
b.append(int(f.readline().strip()))
c.append(int(f.readline().strip()))
n.append(int(f.readline().strip()))
f.close()
N = n[0]*n[1]*n[2]*n[3]*n[4]
print(N)
K = Zmod(N)
R.<x> = PolynomialRing(K)
t = []
t.append(crt([1,0,0,0,0],n))
t.append(crt([0,1,0,0,0],n))
t.append(crt([0,0,1,0,0],n))
t.append(crt([0,0,0,1,0],n))
t.append(crt([0,0,0,0,1],n))
h = [(t[i]*((a[i]*x + b[i])**5 -c[i]))for i in range(5)]
g = sum(h)
print(g)
g = g.monic()
print g
roots = g.small_roots()
print( binascii.unhexlify(hex(int(roots[0]))[2:-1]) )
flag:PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}
参考