ASIS CTF 2018 - Neighbour Writeup | ASIS CTF 2018

[Preview]

CTFの問題を解き始めた最近、様々な分野の問題を見ています。今回挑戦してみた分野はPPC (Professional Programming Challenges) です。文系出身の私にとって苦手な分野である数学に関する内容だったため、怖気づいて手を出さずにいましたが、今回はなぜか「いけそうな気がする」という漠然とした感覚（？）のおかげで、挑戦することになりました。諦めて寝ようと決心しベッドに横になった瞬間、解法を思いつき、そのまま徹夜してしまったという良い経験（？）ができました（笑）。

[Summary]

今回の問題は、非常に大きな数 n より小さく、x**y を満たす数の中で、n に最も近い数 'r' を見つけ出すというものでした。問題解決の核心は、制限時間内に効率的に計算できるようにコードを構成できるかどうかです。私は3つの方法を使って、コードの効率性を高めることができました。

1. n に最も近い 2y における y を求める**

2. [1]番で求めた y の値を減らしていき、'n - (xy) < 0' を初めて満たす x の値を求める**

**3. [2]番で求めた 'n - ((x-1)y)' の値が、以前に求めた最小値より小さいかどうかを比較する

4. [2]番の条件を満たすための x の増加幅を、最初は大きく設定し、その後増加幅を調整する

5. 数の大きさによっては、y が 2 になる瞬間まで x の値を求めず、途中で処理を打ち切るようにする

一見乱雑に見えるかもしれませんが、対数や極限もよく分からない私は、様々な試行錯誤の末、上記のような解法にたどり着くことができました。

[Code]

import socket
import hashlib
 
#read data - get hash_num
def read_hash():
 data=""
 data2=""
 while "[-6:] = " not in data:
 data += s.recv(1)
 data2=s.recv(6) #hash_num
 print data+data2
 return data2
 
#PoW
def do_PoW(hash_num):
 pow_result=""
 print ("[*] I'm doing PoW...")
 for i in xrange(1000000000):
 if hash_num in str(hashlib.sha256(str(i)).hexdigest())[-6:]:
 pow_result=str(i)
 break
 
 print "[!] pow result = %s" % pow_result
 
 s.send(pow_result+"\n")
 
 #read data - get big number
 data1=recvuntil("n = ")
 data2=recvuntil("To")
 data3=recvuntil(":)")
 s.recv(1)
 print data1+data2+data3
 
 return data2
 
#get y on 2**y
def get_num_x_2(a):
 for i in range(100, 1000000):
 if (a-(2**i)<0):
 print ("[*] start y - %s" % str(i-1))
 return i-1
 
#get x by decreasing y(get_num_x_2(a))
def get_num_y_2(num, num_cnt):
 x=3
 y=num
 yt=0
 tmp=a
 cnt=num_cnt
 tmp2=0
 while(1):
 if(a-(x**y)<0):
 #give-up point
 if(num>3000):
 if(y<17): 
 print ("[*] Gotya! %s" % str(tmp))
 return str(tmp)
 elif(num>2000):
 if(y<15):
 print ("[*] Gotya! %s" % str(tmp))
 return str(tmp)
 elif(num>1000):
 if(y<11):
 print ("[*] Gotya! %s" % str(tmp))
 return str(tmp)
 elif(num>700):
 if(y<8):
 print ("[*] Gotya! %s" % str(tmp))
 return str(tmp)
 else:
 if(y==2):
 print ("[*] Gotya! %s" % str(tmp))
 return str(tmp)
 
 #is smaller r?
 if(a-((x-1)**y)<tmp):
 #set increasing range of x
 if(y<=190 and cnt!=1):
 x-=cnt
 cnt = cnt/2
 continue
 tmp=a-((x-1)**y)
 y-=1
 yt=y
 cnt=num_cnt
 else:
 y-=1
 yt=y
 cnt=num_cnt
 else:
 #set increasing range of x
 if(y>190):
 x+=1
 elif(y<=190):
 x+=cnt
 
#check clear
def isNext():
 dt=""
 dt+=recvuntil("\x0a")
 if "next stage" in dt:
 data1=recvuntil("n = ")
 data2=recvuntil("To")
 data3=recvuntil(":)")
 s.recv(1)
 print data1+data2+data3
 return data2
 else:
 print dt
 while 1:
 print recvuntil("\x0a")
 
#custom recvuntil
def recvuntil(str):
 data=""
 while str not in data:
 data += s.recv(1)
 return data
 
######main######
num_y=0
num_cnt=2**250
 
s = socket.socket()
ip = '37.139.22.174'
port = 11740
s.connect((ip,port))
 
#pow
a=do_PoW(read_hash())
a=a[0:len(a)-3]
a=long(a)
 
#get r
while(1):
 num_y = get_num_x_2(a)
 result = get_num_y_2(num_y, num_cnt)
 
 print ("[!] r=\'%s\'" % str(result))
 
 s.send(result+"\n")
 
 a=isNext()
 a=a[0:len(a)-3]
 a=long(a)

[図 1] 問題解決コード (Python)

[図 2] ソリューション実行画面

コメント