Description (번역본)

---------------------------------------------------
- 게임을 해볼까요? -
---------------------------------------------------

당신은 손에 몇 개의 금화를 쥐고 있습니다
하지만 그중 하나는 위조 동전입니다
위조 동전은 진짜 동전과 똑같이 보이지만
무게가 다릅니다
진짜 동전은 10의 무게를 가지며, 위조 동전은 9의 무게를 가집니다
저울을 사용해 위조 동전을 찾아주세요
만약 100개의 위조 동전을 찾으면 보상을 받게 됩니다 :)
참고로, 시간은 60초입니다.

- 플레이 방법 -
1. 동전의 개수(N)와 시도 횟수(C)가 주어집니다
2. 저울에 올릴 동전의 인덱스 번호를 지정합니다
3. 무게 정보를 받습니다
4. 2~3번 과정을 C번 반복한 뒤 정답을 제시합니다

- 예시 -
[서버] N=4 C=2 # 4개의 동전 중 위조 동전을 2번의 시도로 찾기
[클라이언트] 0 1 # 첫 번째와 두 번째 동전 저울에 올리기
[서버] 20 # 저울 결과: 20
[클라이언트] 3 # 네 번째 동전 저울에 올리기
[서버] 10 # 저울 결과: 10
[클라이언트] 2 # 위조 동전은 세 번째!
[서버] 정답!

- 준비되셨나요? 3초 후 시작합니다... -

solve.py

출처:

https://code-angie.tistory.com/3

시간복잡도: O(logN)
반복문과 재귀 두 가지 방법을 사용할 수 있다. (여기서는 반복문을 사용함)

자료를 오름차순으로 정렬한다.
자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.
mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.

ⓐ target이 middle 값 보다 작으면 end를 middle 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)

ⓑ target이 middle 값 보다 크면 start를 middle 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)

위 방법대로 이진탐색 알고리즘을 통해 가짜 코인이 어느 인덱스에 있는지 파악할 수 있다.

low~mid 까지 합의 무게를 10으로 나눴을 때, 나머지가 9면 가짜 코인이 포함되있는거다.

가짜코인이 포함될 경우, high를 middle로 정하고 포함되지 않을 경우, low를 middle+1 로 정하여서 계속 반복문을 통해 범위를 좁혀나가면 가짜 코인이 어느 인덱스에 있는지 알아낼 수 있었다.

from pwn import *
# context.log_level = 'debug'
context(arch='amd64', os='linux')
warnings.filterwarnings('ignore')

p = remote("0.0.0.0", 9007)

p.recvuntil(b"        - Ready? starting in 3 sec... -")
p.recvline()
p.recvline()

tryCount = 0

while True:
    result = p.recvline()

    # print(f"result: {result}, tryCount: {tryCount}")
    print(f"tryCount: {tryCount}")

    n = result.split(b"=")[1].split(b" ")[0].decode('utf-8')
    n = int(n, 10)

    c = result.split(b"=")[2].split(b"\n")[0].decode('utf-8')
    c = int(c, 10)

    print(f"n: {n}, c: {c}")

    low = 0
    high = n - 1
    for i in range(c+1):
        middle = int((low + high) / 2)
        # print(f"middle: {middle}")

        payload = ""
        for j in range(low, middle + 1):
            payload = payload + str(j) + " "
        p.sendline(payload)
        result = p.recvline()
        if b'Correct' in result:
            break
        result = int(result.split(b"\n")[0])
        # print(f"result: {result}")

        if result % 10 == 9:
            high = middle
        else:
            low = middle + 1
    tryCount += 1
    if tryCount >= 100:
        break 

p.interactive()

Result

coin1@ubuntu:/tmp/w4_coin1$ python3 solve.py
[+] Opening connection to 0.0.0.0 on port 9007: Done
tryCount: 0
n: 205, c: 8
tryCount: 1
n: 480, c: 9
tryCount: 2
n: 423, c: 9
tryCount: 3
n: 850, c: 10
tryCount: 4
n: 580, c: 10
tryCount: 5
n: 687, c: 10
tryCount: 6
n: 154, c: 8
tryCount: 7
n: 102, c: 7
tryCount: 8
n: 299, c: 9
tryCount: 9
n: 195, c: 8
tryCount: 10
n: 67, c: 7
tryCount: 11
n: 555, c: 10
tryCount: 12
n: 361, c: 9
tryCount: 13
n: 247, c: 8
tryCount: 14
n: 112, c: 7
tryCount: 15
n: 826, c: 10
tryCount: 16
n: 973, c: 10
tryCount: 17
n: 482, c: 9
tryCount: 18
n: 835, c: 10
tryCount: 19
n: 424, c: 9
tryCount: 20
n: 358, c: 9
tryCount: 21
n: 87, c: 7
tryCount: 22
n: 77, c: 7
tryCount: 23
n: 623, c: 10
tryCount: 24
n: 96, c: 7
tryCount: 25
n: 131, c: 8
tryCount: 26
n: 937, c: 10
tryCount: 27
n: 914, c: 10
tryCount: 28
n: 843, c: 10
tryCount: 29
n: 640, c: 10
tryCount: 30
n: 869, c: 10
tryCount: 31
n: 422, c: 9
tryCount: 32
n: 727, c: 10
tryCount: 33
n: 929, c: 10
tryCount: 34
n: 865, c: 10
tryCount: 35
n: 748, c: 10
tryCount: 36
n: 709, c: 10
tryCount: 37
n: 491, c: 9
tryCount: 38
n: 146, c: 8
tryCount: 39
n: 708, c: 10
tryCount: 40
n: 344, c: 9
tryCount: 41
n: 628, c: 10
tryCount: 42
n: 882, c: 10
tryCount: 43
n: 302, c: 9
tryCount: 44
n: 61, c: 6
tryCount: 45
n: 504, c: 9
tryCount: 46
n: 144, c: 8
tryCount: 47
n: 724, c: 10
tryCount: 48
n: 603, c: 10
tryCount: 49
n: 465, c: 9
tryCount: 50
n: 386, c: 9
tryCount: 51
n: 362, c: 9
tryCount: 52
n: 680, c: 10
tryCount: 53
n: 368, c: 9
tryCount: 54
n: 766, c: 10
tryCount: 55
n: 304, c: 9
tryCount: 56
n: 487, c: 9
tryCount: 57
n: 263, c: 9
tryCount: 58
n: 9, c: 4
tryCount: 59
n: 433, c: 9
tryCount: 60
n: 698, c: 10
tryCount: 61
n: 979, c: 10
tryCount: 62
n: 77, c: 7
tryCount: 63
n: 426, c: 9
tryCount: 64
n: 936, c: 10
tryCount: 65
n: 347, c: 9
tryCount: 66
n: 164, c: 8
tryCount: 67
n: 349, c: 9
tryCount: 68
n: 767, c: 10
tryCount: 69
n: 204, c: 8
tryCount: 70
n: 897, c: 10
tryCount: 71
n: 886, c: 10
tryCount: 72
n: 277, c: 9
tryCount: 73
n: 464, c: 9
tryCount: 74
n: 380, c: 9
tryCount: 75
n: 253, c: 8
tryCount: 76
n: 354, c: 9
tryCount: 77
n: 645, c: 10
tryCount: 78
n: 259, c: 9
tryCount: 79
n: 980, c: 10
tryCount: 80
n: 620, c: 10
tryCount: 81
n: 465, c: 9
tryCount: 82
n: 207, c: 8
tryCount: 83
n: 410, c: 9
tryCount: 84
n: 892, c: 10
tryCount: 85
n: 36, c: 6
tryCount: 86
n: 831, c: 10
tryCount: 87
n: 570, c: 10
tryCount: 88
n: 447, c: 9
tryCount: 89
n: 948, c: 10
tryCount: 90
n: 85, c: 7
tryCount: 91
n: 960, c: 10
tryCount: 92
n: 720, c: 10
tryCount: 93
n: 243, c: 8
tryCount: 94
n: 953, c: 10
tryCount: 95
n: 259, c: 9
tryCount: 96
n: 545, c: 10
tryCount: 97
n: 17, c: 5
tryCount: 98
n: 917, c: 10
tryCount: 99
n: 889, c: 10
[*] Switching to interactive mode
Congrats! get your flag
b1naRy_S34rch1Ng_1s_3asy_p3asy
$ 
[*] Interrupted
[*] Closed connection to 0.0.0.0 port 9007
coin1@ubuntu:/tmp/w4_coin1$