Writeup 4 GFCTF 2021 onceTheGame面向小白的超详细题解从背包到整除性质从源码分析到脚本逐行讲解。一、题目信息项目内容题目名onceTheGame来源GFCTF 2021分类伪装成密码学的算法交互题靶机node4.anna.nssctf.cn:23792NSSCTF 复现环境提示“It is not a crypto, but a simple game. Analyze the source code and get the flag!” / “There may be a backpack”FlagNSSCTF{cf2d7899-2d3d-4b60-94b2-74eace67027f}二、这道题到底在玩什么2.1 面子一个游戏连接靶机会看到一段 ASCII 大标题然后是[OK] Lets play 24 games! [*] The 1st game start! [*] The Public Key is 10 [*] Please give me the number I want!翻译成人话服务器要和你玩N 局游戏N 每次随机可能是 21、24、27…。每局给你一个Public Key n比如 10。让你交出一个它想要的数字序列。交对了 → 给你2 字节 flag进入下一局。交错了 → 回[ERROR] Sorry, youre not the person Im looking for!然后继续下一局不会断线。24 局全过就能拼出完整 flag。2.2 里子一个性质匹配问题题目提示 “There may be a backpack”诱导你去做背包密码子集和问题。但官方 WP 说得很直白核心代码是check1函数主要是检验输入数组的长度分析移位和a数组的累加操作后能够发现整体是一个状压背包的思路我们只需要关注性质判断的点即发现数组需要满足这样一个性质每个数k和下标i一定要满足k % (i1) 0或者(i1) % k 0。翻译check1里确实有一堆移位 数组累加看起来像背包校验。但那些是干扰项真正卡你的只有一条输入数组必须满足整除性质。所以这道题不用解背包只需要搜索一个满足整除性质的排列。❌找了半天也没找到check1函数。2.3 什么是整除性质设你交出的数组是arr长度为n等于 Public Key那么对每个位置i从 1 开始arr[i] % i 0 或者 i % arr[i] 0举例n4 时数组[1,2,3,4]位置 i值 kk % ii % k满足?1100✅2200✅3300✅4400✅再举例[1,4,3,2]位置 i值 kk % ii % k满足?1100✅2402%4≠0✅k%i03300✅422%4≠00✅i%k0两个条件满足任意一个就行所以很多排列都合法。2.4 还有一个隐藏要求数组是 1…n 的排列虽然 WP 没明说但从长度检验和每个数用一次的搜索逻辑看数组长度必须等于n。数组里的数必须是1..n各出现一次即一个排列。所以问题最终定义为给定 n找一个 1…n 的排列使第 i 位的数 k 满足k % i 0或i % k 0。三、为什么看着像背包其实不是3.1 背包问题的样子子集和/背包给一组权重a [a1, a2, ..., an]和一个目标S找x_i ∈ {0,1}使Σ x_i * a_i SMerkle-Hellman 背包密码公钥是一组数密文是一个和解密就是解子集和。3.2 本题为什么不是特征真背包本题公钥形式一组数单个数 n目标一个和 S“give me the number I want” 要的是数组解法贪心 / LLL 格约减DFS 搜索排列提示“backpack”“backpack” 是指“回溯”关键点The Public Key is 10只有一个数而真背包的公钥应该是一组数。这个10其实是数组长度 n不是目标值。3.3 出题人的障眼法check1里有移位操作可能形如(1 i)看起来像二进制背包的权重。数组a的累加看起来像Σ arr[i] * a[i]。这些让人误以为要解背包。但实际上移位和累加是干扰代码真正 return False 的地方是整除性质判断。官方 WP 的原话我们只需要关注性质判断的点就是在说别管那些移位累加只看整除约束。四、解题思路4.1 核心把问题转成带约束的排列搜索已知长度 n Public Key。第 i 位填 k要求k % i 0 || i % k 0。每个数 1…n 用且只用一次。用回溯 DFS从位置 1 开始。对每个位置 i尝试所有满足整除关系且还没用过的数。填到位置 n1 就找到一个解。回溯时撤销选择。4.2 预处理match[i]表为了快速知道位置 i 能填哪些数先建一张表match[i][所有与 i 满足整除关系的数 j]构建方式foriinrange(1,n1):forjinrange(1,n1):ifi%j0orj%i0:match[i].append(j)这样 DFS 时位置 i 只需遍历match[i]不用每次重新判断。4.3 DFS 搜索defback(index,arr):ifindexn1:# 填满了保存这个解returnfornuminmatch[index]:ifnumnotinvisited:# 没用过visited.add(num)arr.append(num)back(index1,arr)arr.pop()visited.discard(num)# 回溯4.4 为什么第一个解总是1,2,3,...,n因为match[1]包含 11 整除所有数。match[2]包含 2。…DFS 从位置 1 开始第一个尝试的就是 1然后位置 2 第一个尝试 2依此类推。所以第一个找到的解就是平凡解1,2,3,...,n。它满足i % i 0合法。靶机接受这个平凡解所以每次只发第一个解就行。五、payload 格式一个容易踩的坑5.1 官方脚本的拼接方式ss[]# 存所有解, 每个元素形如 ,1,2,3,4defback(index,s):...ss.append(s)# s ,1,2,3,4resforiinss:resi[1:]# 去掉开头的逗号 - 1,2,3,4res-# 解之间用横杠returnres[:-1]最终格式1,2,3,4-2,1,4,3-1,4,3,2-...即同一个解内部用逗号分隔。不同解之间用横杠分隔。5.2 为什么不能全用横杠如果你发1-2-3-4内部也是横杠靶机解析时会把整串当成一个解里面的数是 1、2、3、4但格式不对直接判错。5.3 实操建议既然靶机接受第一个解payload 可以只发第一个解payload1,2,3,4,...,n# 只发平凡解另也可以发整串。注意 payload 长度n14 时所有解拼起来有 35 万字符虽然靶机能收但没必要。六、交互脚本逐行讲解6.1 完整脚本#!/usr/bin/env python3# -*- coding: utf-8 -*- [GFCTF 2021] onceTheGame 每轮读 Public Key n, 发送 n 的合法排列 成功回显: fl is XX - 收两字节 失败回显: [ERROR] - 继续下一轮 frompwnimport*fromcollectionsimportdefaultdict HOSTnode4.anna.nssctf.cnPORT23792premote(HOST,PORT,timeout15)flagcache{}defgetOnePayload(n):生成 n 的所有合法排列, 内部逗号, 解间横杠matchdefaultdict(list)foriinrange(1,n1):forjinrange(1,n1):ifi%j0orj%i0:match[i].append(j)ss[]visitedset()defback(index,s):ifindexn1:ss.append(s)returnfornuminmatch[index]:ifnumnotinvisited:visited.add(num)back(index1,s,str(num))visited.discard(num)back(1,)resforiinss:resi[1:]# 去掉开头逗号res-# 解间横杠returnres[:-1]defgenerateCache():预生成 n4..14 的 payloadprint([-] Generating cache for n4..14 ...)foriinrange(4,15):cache[i]getOnePayload(i)print(f[OK] cache[{i}] len{len(cache[i])})print([OK] Cache ready)defone_game(index):玩一局: 读 n - 发包 - 判定成功/失败globalflagprint(f[*] Round{index})p.recvuntil(The Public Key is )nint(str(p.recvline()).split(\n)[0][2:-3])print(f[*] Public Key {n})p.recv()ifnnotincache:cache[n]getOnePayload(n)payloadcache[n]p.sendline(payload)# 循环收数据, 匹配 fl is 或 ERRORdatabwhileTrue:try:chunkp.recv(timeout5)exceptEOFError:print([!] Connection closed)returnFalseifnotchunk:print([!] recv timeout)returnFalsedatachunkifbfl isindata:taildata.split(bfl is )[-1]stail[:2].decode(errorsignore)flagsprint(f[OK] Got 2 bytes:{s}| flag:{flag})returnTrueifbERRORindata:print([!] This round failed)returnFalseif__name____main__:p.recvuntil(Lets play )nint(str(p.recvline()).split( )[0][2:])print(f[OK] Rounds:{n})generateCache()success0foriinrange(n):ifone_game(i1):success1print(f\n[*] Success:{success}/{n})# 收尾, 可能有额外的 flag 片段try:p.recvuntil([OK],timeout5)remainstr(p.recvline())ifflag isinremain:flagremain.split( )[-1][:-3]exceptException:passprint(f[OK] Final flag:{flag})6.2 关键行讲解p remote(HOST, PORT, timeout15)连接靶机。注意这是裸 TCP 服务不是 HTTP所以不能用浏览器访问必须用 pwntools。p.recvuntil(Lets play )先读到 banner 里的Lets play。n int(str(p.recvline()).split( )[0][2:])读下一行比如24 games!提取出 24动作分解p.recvline()→b24 games!\nstr(...)→b24 games!\\n.split( )[0]→b24[2:]→24int(...)→24p.recvuntil(The Public Key is )每轮开头等这行。n int(str(p.recvline()).split(\n)[0][2:-3])读下一行10\n提取 np.recvline()→b10\nstr(...)→b10\\n.split(\n)[0]→b10[2:]→10这里用[2:-3]是为了兼容更长的字符串官方写法实际[2:]就够。p.recv()吃掉Please give me the number I want!后面的换行。p.sendline(payload)发送 payload。循环recvwhileTrue:chunkp.recv(timeout5)datachunkifbfl isindata:...ifbERRORindata:...为什么不用recvuntil(fl is)因为失败时靶机返回[ERROR]不会出现fl isrecvuntil会一直等到超时然后 pwntools 抛 EOFError看起来像断线其实是超时。改成循环recv同时匹配两种字符串就不会误判。tail data.split(bfl is )[-1]成功回显形如fl is NS\n切出NS\n取前 2 字节NS。flag s拼接到总 flag。失败也继续one_game返回 False 后主循环继续下一轮。靶机失败不断线所以不会卡住。收尾p.recvuntil([OK],timeout5)remainstr(p.recvline())ifflag isinremain:flagremain.split( )[-1][:-3]24 轮跑完后靶机还会发一段[OK] Final flagNSSCTF{ ...拼上尾部。七、运行结果rootRambo:/GFCTF_2021_onceTheGame# python3 exp.py [] Opening connection to node4.anna.nssctf.cn on port 23792: Done /GFCTF_2021_onceTheGame/exp.py:99: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes p.recvuntil(Lets play ) [OK] Rounds: 24 [-] Generating cache for n4..14 ... [OK] cache[4] len63 [OK] cache[5] len99 [OK] cache[6] len431 [OK] cache[7] len573 [OK] cache[8] len2111 [OK] cache[9] len4499 [OK] cache[10] len14699 [OK] cache[11] len17999 [OK] cache[12] len108269 [OK] cache[13] len127109 [OK] cache[14] len352439 [OK] Cache ready [*] Round 1 /GFCTF_2021_onceTheGame/exp.py:61: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes p.recvuntil(The Public Key is ) [*] Public Key 10 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10-1,2,3,4,10,6,7,8,9,5-1,2,3,8,5,6,7,4,9,... /GFCTF_2021_onceTheGame/exp.py:71: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes p.sendline(payload) [OK] Got 2 bytes: NS | flag: NS [*] Round 2 [*] Public Key 8 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8-1,2,3,8,5,6,7,4-1,2,6,4,5,3,7,8-1,2,6,8,5,3,... [OK] Got 2 bytes: SC | flag: NSSC [*] Round 3 [*] Public Key 10 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10-1,2,3,4,10,6,7,8,9,5-1,2,3,8,5,6,7,4,9,... [OK] Got 2 bytes: TF | flag: NSSCTF [*] Round 4 [*] Public Key 9 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9-1,2,3,8,5,6,7,4,9-1,2,6,4,5,3,7,8,9-1,2,6,... [OK] Got 2 bytes: {c | flag: NSSCTF{c [*] Round 5 [*] Public Key 8 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8-1,2,3,8,5,6,7,4-1,2,6,4,5,3,7,8-1,2,6,8,5,3,... [OK] Got 2 bytes: f2 | flag: NSSCTF{cf2 [*] Round 6 [*] Public Key 12 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11,12-1,2,3,4,5,12,7,8,9,10,11,6-1,2,3,... [OK] Got 2 bytes: d7 | flag: NSSCTF{cf2d7 [*] Round 7 [*] Public Key 10 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10-1,2,3,4,10,6,7,8,9,5-1,2,3,8,5,6,7,4,9,... [OK] Got 2 bytes: 89 | flag: NSSCTF{cf2d789 [*] Round 8 [*] Public Key 13 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11,12,13-1,2,3,4,5,12,7,8,9,10,11,6,13-... [OK] Got 2 bytes: 9- | flag: NSSCTF{cf2d7899- [*] Round 9 [*] Public Key 10 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10-1,2,3,4,10,6,7,8,9,5-1,2,3,8,5,6,7,4,9,... [OK] Got 2 bytes: 2d | flag: NSSCTF{cf2d7899-2d [*] Round 10 [*] Public Key 11 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11-1,2,3,4,10,6,7,8,9,5,11-1,2,3,8,5,6,... [OK] Got 2 bytes: 3d | flag: NSSCTF{cf2d7899-2d3d [*] Round 11 [*] Public Key 11 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11-1,2,3,4,10,6,7,8,9,5,11-1,2,3,8,5,6,... [OK] Got 2 bytes: -4 | flag: NSSCTF{cf2d7899-2d3d-4 [*] Round 12 [*] Public Key 11 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11-1,2,3,4,10,6,7,8,9,5,11-1,2,3,8,5,6,... [OK] Got 2 bytes: b6 | flag: NSSCTF{cf2d7899-2d3d-4b6 [*] Round 13 [*] Public Key 12 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11,12-1,2,3,4,5,12,7,8,9,10,11,6-1,2,3,... [OK] Got 2 bytes: 0- | flag: NSSCTF{cf2d7899-2d3d-4b60- [*] Round 14 [*] Public Key 4 [*] Sending payload (first 60 chars): 1,2,3,4-1,4,3,2-2,1,3,4-2,4,3,1-3,2,1,4-3,4,1,2-4,1,3,2-4,2,... [OK] Got 2 bytes: 94 | flag: NSSCTF{cf2d7899-2d3d-4b60-94 [*] Round 15 [*] Public Key 4 [*] Sending payload (first 60 chars): 1,2,3,4-1,4,3,2-2,1,3,4-2,4,3,1-3,2,1,4-3,4,1,2-4,1,3,2-4,2,... [OK] Got 2 bytes: b2 | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2 [*] Round 16 [*] Public Key 13 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11,12,13-1,2,3,4,5,12,7,8,9,10,11,6,13-... [OK] Got 2 bytes: -7 | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-7 [*] Round 17 [*] Public Key 9 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9-1,2,3,8,5,6,7,4,9-1,2,6,4,5,3,7,8,9-1,2,6,... [OK] Got 2 bytes: 4e | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74e [*] Round 18 [*] Public Key 4 [*] Sending payload (first 60 chars): 1,2,3,4-1,4,3,2-2,1,3,4-2,4,3,1-3,2,1,4-3,4,1,2-4,1,3,2-4,2,... [OK] Got 2 bytes: ac | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eac [*] Round 19 [*] Public Key 5 [*] Sending payload (first 60 chars): 1,2,3,4,5-1,4,3,2,5-2,1,3,4,5-2,4,3,1,5-3,2,1,4,5-3,4,1,2,5-... [OK] Got 2 bytes: e6 | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace6 [*] Round 20 [*] Public Key 6 [*] Sending payload (first 60 chars): 1,2,3,4,5,6-1,2,6,4,5,3-1,4,3,2,5,6-1,4,6,2,5,3-1,6,3,4,5,2-... [OK] Got 2 bytes: 70 | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace670 [*] Round 21 [*] Public Key 9 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9-1,2,3,8,5,6,7,4,9-1,2,6,4,5,3,7,8,9-1,2,6,... [OK] Got 2 bytes: 27 | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace67027 [*] Round 22 [*] Public Key 5 [*] Sending payload (first 60 chars): 1,2,3,4,5-1,4,3,2,5-2,1,3,4,5-2,4,3,1,5-3,2,1,4,5-3,4,1,2,5-... [OK] Got 2 bytes: f} | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace67027f} [*] Round 23 [*] Public Key 9 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9-1,2,3,8,5,6,7,4,9-1,2,6,4,5,3,7,8,9-1,2,6,... [OK] Got 2 bytes: | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace67027f} [*] Round 24 [*] Public Key 14 [*] Sending payload (first 60 chars): 1,2,3,4,5,6,7,8,9,10,11,12,13,14-1,2,3,4,5,6,14,8,9,10,11,12... [OK] Got 2 bytes: | flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace67027f} [*] Success: 24/24 /GFCTF_2021_onceTheGame/exp.py:114: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes p.recvuntil([OK], timeout5) [OK] Final flag: NSSCTF{cf2d7899-2d3d-4b60-94b2-74eace67027f} [*] Closed connection to node4.anna.nssctf.cn port 23792 rootRambo:/GFCTF_2021_onceTheGame#八、踩坑总结坑现象原因解决以为是背包提示 “backpack”干扰项读源码找性质判断点payload 格式错全横杠被拒内部应该用逗号内部用逗号、解间用横杠误以为断线EOFErrorrecvuntil(fl is)超时改循环recv匹配 ERROR失败就退出只过一轮脚本逻辑失败后继续下一轮回合数写死27 变了随机动态读Lets play N games!缓存 KeyErrorn 不在 4…14缓存范围加if n not in cache兜底九、知识点延伸9.1 状压背包是什么状压指用二进制位表示选择状态。比如 n3101表示选第 1、3 个不选第 2 个。状压背包就是枚举2^n种选择每种算一次和。本题check1里可能真有这种代码但不是必须解的那一关。9.2 回溯搜索模板defback(状态):if到达终点:保存解returnfor每个可能的选择:if选择合法:做选择 back(新状态)撤销选择本题就是在这个模板上把合法定义为整除 未使用。9.3 pwntools 的recvvsrecvuntil函数行为适用recvuntil(s)一直读到出现 ss 一定会出现recv(timeout)读一次最多等 timeouts 可能不出现当成功/失败回显不同时用recv循环更安全。十、一句话总结这道题是伪装成密码学的搜索题。提示 “backpack” 是指回溯搜索真正的突破口是check1里的整除性质。把它转成1…n 排列 整除约束的 DFS每轮发第一个解平凡解1,2,3,...,n24 轮拼出 flag。难点不在算法在 payload 格式和 pwntools 交互逻辑。Rambo2026年10月06日