ASIS CTF 2018 - Neighbour 题解 | ASIS CTF 2018

[Preview]

最近刚开始刷 CTF，接触了各个领域的题目。这次挑战的是 PPC (Professional Programming Challenges) 领域。作为一个文科生，数学本来是我的弱项，平时看到都会被吓退，但这次不知为何有一种“能行”的直觉，于是便挑战了一把。本来打算放弃去睡觉，结果躺在床上的瞬间突然想到了解题思路，于是干脆熬了个通宵，也算是一次难忘的经历吧，哈哈……

[Summary]

这道题的目标是找出小于巨型数字 n 且满足 x**y 形式的、最接近 n 的数值 'r'。解题的核心在于如何编写代码以在规定时间内进行高效计算。我使用了以下 3 种方法来提高效率：

1. 求出使 2y 最接近 n 的 y 值**

2. 递减 [1] 中求得的 y 值，找出首次满足 n - (x**y) < 0 的 x 值

3. 将 [2] 中算出的 n - ((x-1)**y) 与之前求得的最小值进行比较

4. 为了满足 [2] 的条件，最初将 x 的增量设得较大，随后动态调整增量

5. 根据数值大小，若计算过于耗时，则不强制计算到 y=2 的情况，直接中途放弃

虽然代码看起来可能有些杂乱，但对于不熟悉对数和极限的我来说，这是经过多次试错后才得出的解决方案。

[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] 解法运行截图

评论