[Preview]

I have recently started solving CTF challenges and have been looking into various categories. The category I challenged myself with this time is PPC (Professional Programming Challenges). As someone with a liberal arts background, math is a weak spot for me, so I used to get scared and avoid it. However, thanks to a certain "gut feeling" (?) that it was doable this time, I decided to take on the challenge. Just as I decided to give up and went to bed, the solution hit me, and I ended up staying up all night—a... good experience (?), haha.

[Summary]

The problem involved finding a number 'r' that is closest to a very large number n, satisfies x**y, and is smaller than n. The core of the solution is whether the code can be structured to calculate efficiently within the time limit. I was able to increase the efficiency of the code using the following methods.

1. Calculate y for 2**y closest to n

2. Decrementing the y value obtained in [1], find the x value that first satisfies 'n - (xy) < 0'**

**3. Compare if the value of 'n - ((x-1)y)' obtained from [2] is smaller than the previously found minimum value

4. Initially set a large increment step for x to satisfy the condition in [2], then adjust the step size

5. Depending on the size of the number, stop the calculation early instead of calculating x until y becomes 2

It might look a bit messy, but as someone who isn't very familiar with logarithms or limits, I was able to arrive at this solution after various trials and errors.

[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)

[Figure 1] Problem solving code (Python)

[Figure 2] Solution execution screen

댓글