*ctf Magic_number

Posted on | Edited on

介绍

一道 crypto 的题目

因为涉及到递归，写了半天也没写出来，下面为参考大佬的思路。

题目描述

1.Given n(1<=n<=14) integers a1,a2,…,an in interval [0,1024), you should determine them by sending several queries.

2.For each query, you can ask “how many integers are in interval [l,r)?” through stdout in format “? l r” where 0<=l<r<=1024, and you will recieve an integer through stdin as the answer.

3.Finally, if all the integers are determined, you should output them in arbitrary order and in format “! a1 a2 … an”.

4.Please notice that some of the integers can be the same and that you can send no more than 99 queries in each level.

分析

每个level会告诉你有多少个数，如下Level 0 : n = 1

可以使用形如? n m查询[n,m)之间有多少个数，每个level最多查询99次

最后可以用形如! a1 a2 ... an来提交答案

方法很明显，类似二分法，每次查一半。
具体描述如下，每次level调用search函数，search函数递归的调用find函数。

find函数：
​ 首先判断所以查找的区间是否正好差1，如果是代表此时的first为其中一个结果，当因为可能有重复，所以乘上所需找的个数，其实就是重复的次数。
​ 然后去查找所需查找区间的前一半有多少个数，而后一半的数则为，总数减去前一半的。
​ 最后，如果前后都大于零则，递归调用find查找前后两部分，然后想家。如果其中一个大于零，则调用find查找大于零的那一部分。

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from pwn import *
import re

def search(con):
    def find(left, right, nums):
        if left == right - 1:
            return [left] * nums

        mid = (left + right) / 2
        con.sendline('? %d %d' % (left, mid))
    
        left_num = int(con.recvline()[:-1])
        right_num = nums - left_num
    
        if left_num &gt; 0 and right_num &gt; 0:
            return find(left,mid,left_num) + find(mid,right,right_num)
        elif left_num &gt; 0:
            return find(left,mid,left_num)
        elif right_num &gt; 0:
            return find(mid,right,right_num)
    
    con.recvuntil('------------------------\n')
    info = con.recvline()[:-1]
    con.info(info)
    level, n = re.match(r'^Level (\d+) : n = (\d+)$',info).groups()
    ret_list = find(0,1024,int(n))
    ret = ' '.join(map(str,ret_list))
    con.info('Result %s'%ret)
    con.sendline('! %s'%ret)

con = remote('47.89.18.224', 10011)

for _ in range(10):
    search(con)

con.interactive()