[pwnable.kr][Toddler] coin1 문제풀이

coin1

문제를 요약하면 동전이 있는데 진짜 동전은 무게가 10이고, 가짜는 9이다.

한번 실행되면 랜덤한 동전 개수(N)와 서버에게 물어볼 수 있는 카운트 수(C)가 설정되어 출력된다.

만약 '0 1' 이라고 해서 보내면 서버는 첫번째 코인과 두번째 코인의 무게를 합한 값을 대답해준다.

하나의 세트에는 1개의 가짜 동전이 존재하고, 동전을 찾으면 다시 새로운 세트가 만들어 지고 또 다시 가짜 동전 1개를 찾아야 한다.

이런식으로 총 100개의 가짜 동전을 찾으면 되는데, 문제는 주어진 시간은 60초이다.

따라서 자동화코드를 만들어서 찾는 방법 밖에없다.

 

가짜 동전을 최소한의 질의로 찾는 알고리즘부터 만들어야 한다.

예를들어 서버로부터 N=400, C=10이라는 값을 받았다고 가정했을 때,

코인을 0~200, 201~400 두 그룹으로 나누어 각 그룹의 합을 구한다.

그룹의 합이 10으로 나누어지면 가짜 코인이 존재하지 않는 그룹이므로 제외시킨다.

그리고 가짜 코인이 존재하는 그룹을 또 다시 두 그룹으로 나누어 위 방식을 반복한다.

 

from pwn import *
import time
import sys

def main():
    host = 'pwnable.kr'
    port = 9007

    r = remote(host, port)
    time.sleep(3)

    print r.recv()

    cnt = 0

    for i in range(100):
        r.recvuntil('N=')
        n = int(r.recvuntil(' '))
        r.recvuntil('C=')
        c = int(r.recv())

        print "N={}, C={}".format(n, c)

        src = 1
        des = n
        t = 0

        while(True):
            if(src > des):
                break

            message = ''

            for i in range(src, (src + des)/2 + 1):
                message += '{0} '.format(i)

            print "[-] set : {0}".format(message)

            r.sendline(message)
            result = r.recv()

            print "[*] result : {0}".format(result)

            if result.find('Correct') > -1:
                t = 1
                break
            elif result[0] == 'N':
                des = n
            elif result.find('error') > -1:
                break
            elif result.find('time') > -1:
                print "[!] time out!"
                sys.exit(1)
            elif int(result) % 10 != 0:
                des = (src + des)/2
            else:
                src = (src + des)/2 + 1

        if(t == 0):
            r.sendline(str(src))
            correctmsg = r.recv()

        cnt += 1
        print "[+] count : {0}\n".format(cnt)

    flag = r.recv()
    print "\n[*] FLAG : {0}".format(flag)

if __name__ == "__main__" :
    main()

 

 

👆알고리즘 대로 동작하는 것을 확인 할 수 있다

flag : b1NaRy_S34rch1nG_1s_3asy_p3asy

잘못 된 개념을 서술하였거나, 잘못 풀이된 내용이 있으면 댓글 달아주시면 감사합니다 :) 태클 댓글이나 메일(513.eunice@gmail.com) 환영입니다 !! 😊☺️👍