PlaidCTF2017(供養)

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 = n_0 * n_1 * n_2 * n_3 * n_4

f(x) = 0 (mod n_i) の場合,

f_i(x) = (a_i * x + b_i ) - c_i ≡ 0 (mod n_i) とすることの予想はつく、これをNのもとで0にするためには、丁度良い単位行列をかけて f_i(x)を全て足せばよい。

h(x) = \sum T_i * f_i(x)

$$ 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!}

参考