点击蓝字 关注我们
日期: 2022-04-26 作者: Mr-hello 介绍: nAnB一款算法工程师喜爱的小游戏。
0x00 前言
为什么想要研究这个小游戏,当然是CTF
比赛中遇到,它夹在一道简单的 pwn
题目中,该题目出现在2022
年虎符杯线上赛中,被算法大佬吊打,本场比赛是清华大佬们出的赛题,里面涉及的算法较多,作为一名小菜鸡,我只好赛后分析一下。
0x01 游戏原理
说一下这个小游戏的逻辑,本场比赛里面涉及的是猜 4
位数,从 1000 - 9999
如果不限制次数,让谁都可以爆破出来,但是这次比赛是要求在 7
次之内猜解出来,首先程序会生成一个随机 4
位数(真随机数),所以不用考虑伪随机数的情况了,也不可能给你钻空子的。
然后,你每次提交一个随机数,程序都会给你一个 nAnB
的反馈,这个反馈中 nA
代表你猜解的 4
位数其中的 n
位的数值被你猜中,并且位置也同样猜中,nB
代表你猜中了 n
位的数值,但是这 n
位你没有猜中位置。这两个 n
相互独立,什么意思呢,例如:随机数为 4595
,你如果提交 3553
那么程序的反馈是 1A1B
,如果你提交 5555
,程序的反馈是 2A0B
,如果随机数为 6666
,你提交 6723
,程序的反馈是 1A0B
。
0x02 游戏实现
我当然选择使用 Python
语言来设计啦
别问为啥不用 CC++
因为 Python
是世界上最好的语言!!
然后我就栽坑了...
这个坑后面再说...
设计思路应该是比较清晰的,首先我们应该生成一个 4
位数字,然后记录下来,然后与使用者提交的数字进行比较。但是考虑到比较时需要按位比较,我将生成的随机数的每一位变成了 list
存储,同样使用者提交的 4
位数字相同的办法存储。
后续工作就是如何进行比较,首先判断 nA
的情况,这个点很好解决,因为 nA
代表的是数值和位置同时满足,直接遍历判断是否相等即可找出 n
的数值。
最后确定 nB
,因为刚开始的时候想的比较简单,以为只需要判断数值相同,但是下标不同即可满足条件,但是在测试过程中发现,这样在生成的随机数存在相同数字时会出错,而且如果某位先满足了 nA
的条件,即可不参与 nB
的计数。
这里我使用了标记的方法,一旦满足 nA
的条件,我将该位置上的数字进行了替换,后续不进行再次计数,但是这种方法涉及到对存储的 list
中的数据进行更改,而且机会共有 7
次每次开始计算 nAnB
时需要将 list
数据还原成最初的随机数状态,可能大家理所应当的想到,那每次循环的时候设计一个 tmp_list
变量,每次循环开始的时候还原成最原始的数据,每次计算的时候更改 tmp_list
中的数据就行,作者也是这样想的,但是发生了一件出现在我知识盲区里的知识。
看一下如下代码:
a = [1,2,3,4]
b = a
b[0] = 100
print(b)
print(a)
上述代码输出的 a
内容应该是什么呢,输出内容发现是 [100,2,3,4]
,竟然是传地址!原来 Python
在进行 list
类型数据传递时,默认使用浅拷贝模式,浅拷贝会创建新对象,其内容是原对象的引用。当然还有一个深拷贝,就是和浅拷贝相反的一个情况。(作者这里只遇到了 list
类型传递时会出现这种情况,因为深拷贝会额外消耗内存空间, python
语言特性问题)所以想实现只传值的情况,可以使用深拷贝操作。
代码如下:
import
copy
a = [
1
,
2
,
3
,
4
]
b =
copy
.deepcopy(a)
b[
0
] =
100
(b)
(a)
好了,经过调试,外加从坑里爬出来之后,最终设计出来的简短小游戏代码如下:
# -*- coding: UTF-8 -*-
# author: Mr_hello
import
random
import
copy
def
ansInit
()
:
random.seed()
return
list(str(random.randint(
1000
,
9999
)))
while
True
:
final_ans = ansInit()
#print(final_ans)
print(
'this is a guess number game'
)
print(
'you have seven times to guess it'
)
for
i
in
range(
7
):
indexA =
0
indexB =
0
temp_ans = copy.deepcopy(final_ans)
# 深拷贝
num = list(input(
"It's %d time: "
%(i +
1
)))
while
len(num) <
4
:
print(
'please input 1000 <= number <= 9999'
)
num = list(input(
"It's %d time: "
%(i +
1
)))
for
j
in
range(len(temp_ans)):
# 计算nA
if
num[j] == temp_ans[j]:
indexA +=
1
num[j] = temp_ans[j] =
'-'
# 满足nA之后将数据置为'-',不参与后续nB计数。
for
k
in
range(len(temp_ans)):
# 计算nB
for
o
in
range(len(num)):
if
temp_ans[k] !=
'-'
and
num[o] !=
'-'
:
if
k != o
and
temp_ans[k] == num[o]:
indexB +=
1
break
print(
"%dA%dB"
%(indexA,indexB))
if
indexA ==
4
and
indexB ==
0
:
print(
'you win'
)
exit()
print(
'you loss try againn'
)
0x03 破解算法
这个游戏,被称之为珠玑妙算游戏,看了看网上的大部分解题算法大致分为两步:
第一步:首先尝试 1234
,根据该数字得到的反馈,对所有 1000 ~ 9999
的数字进行 nAnB
的判断,取出所有满足与得到的反馈相同的数字集合,将不符合的反馈进行踢除。
第二步:从第一步得到的数字集合中取一个数字,进行尝试得到反馈,然后再次进入针对于第一步数字集合的 nAnB
判断,再次踢除不符合的数字,并且一直重复第二步。
PS: 为什么首先尝试 1234
呢,因为在不知道任何反馈的情况下,选取 0 ~ 9
中不重复的 4
位数字组合,这样可以最大化得到数字信息。如果你问为什么不选 5678
那你就是在抬杠!
破解代码部分实现如下:
def
compare
(num,temp)
:
A =
0
B =
0
for
j
in
range(len(temp)):
if
num[j] == temp[j]:
A +=
1
num[j] = temp[j] =
'-'
for
k
in
range(len(temp)):
for
o
in
range(len(num)):
if
temp[k] !=
'-'
and
num[o] !=
'-'
:
if
k != o
and
temp[k] == num[o]:
B +=
1
break
return
A, B
def
delnum
(num,indexA,indexB)
:
global
maps
number =
0
for
temp
in
maps:
if
temp !=
0
:
A,B = compare(copy.deepcopy(num),copy.deepcopy(list(str(temp))))
if
A == indexA
and
B == indexB:
pass
else
:
maps[maps.index(temp)] =
0
def
suggestnum
(num,i,indexA,indexB)
:
global
maps
delnum(num,indexA,indexB)
for
i
in
maps:
if
i !=
0
:
return
list(str(i))
这种算法实现的时候提取的数字,是从剩余数字集合中取第一个,利用该种算法经过大量尝试,发现可以实现的平均猜解次数为 6 ~ 7
次。尝试 400
次破解平均次数为 6.6325
,下图是我尝试 200
次算出的平均次数。
由此可见,上述算法已经可以做到平均 7
次之内将数字猜解出,但是这种算法情况有相当一部分概率会出现大于 7
次的现象,所以我又进行了一次改进。
既然在第二步中,我们是按照数字集合的第一位进行取,那么我们在第一步拿到数字集合之后,选取数字集合里面的每一位进行对比,记录每一位被排除的数字个数,优先选取排除个数最多的那个数字作为下一次尝试的数,这样是不是可以实现平均更少次数猜解出来呢。
实现代码如下:
def
compare
(num,temp)
:
A =
0
B =
0
for
j
in
range(len(temp)):
if
num[j] == temp[j]:
A +=
1
num[j] = temp[j] =
'-'
for
k
in
range(len(temp)):
for
o
in
range(len(num)):
if
temp[k] !=
'-'
and
num[o] !=
'-'
:
if
k != o
and
temp[k] == num[o]:
B +=
1
break
return
A, B
def
delnum
(num,indexA,indexB)
:
global
maps
number =
0
value =
0
for
temp
in
maps:
if
temp !=
0
:
A,B = compare(copy.deepcopy(num),copy.deepcopy(list(str(temp))))
if
A == indexA
and
B == indexB:
pass
else
:
number +=
1
return
number
def
maps_move
(num,indexA,indexB)
:
global
maps
temp_maps = copy.deepcopy(maps)
for
temp
in
temp_maps:
A, B = compare(copy.deepcopy(num),copy.deepcopy(list(str(temp))))
if
A == indexA
and
B == indexB:
pass
else
:
maps.remove(temp)
def
suggestnum
(num,indexA,indexB)
:
global
maps
renum =
0
delnumMax =
0
del_num =
0
print(
'Del num '
+ str(delnum(num,indexA,indexB)))
maps_move(num,indexA,indexB)
for
i
in
maps:
count = delnum(list(str(i)),indexA,indexB)
if
delnumMax ==
0
or
delnumMax < count:
delnumMax = count
del_num = i
return
list(str(del_num))
这里因为涉及到两个 for
循环效率变慢,但是我将第一次猜测更改为 1234
第二次尝试更改为 5678
之后效率相对变快,而且测试 500
次后统计出来的平均次数变为 5.896
次。但是在 500
次中仍然存在 16
次大于 7
次才成功猜解出来。也就是说失败率大约为 3.2%
。
0x04 结语
我毕竟不是玩算法的大佬,我也不懂什么是信息摘要算法,或许上文我用到了该算法,但是我也不知道,咱也不懂啊,我只是知道网上有说可以实现稳定 6
次之内得到所有正确答案,但是我目前实现不了。而且我最后设计出来的解题算法,失败率仍然在 3.2%
左右,惭愧,学习去了。
免责声明:本文仅供安全研究与讨论之用,严禁用于非法用途,违者后果自负。
宸极实验室隶属山东九州信泰信息科技股份有限公司,致力于网络安全对抗技术研究,是山东省发改委认定的“网络安全对抗关键技术山东省工程实验室”。团队成员专注于 Web 安全、移动安全、红蓝对抗等领域,善于利用黑客视角发现和解决网络安全问题。
团队自成立以来,圆满完成了多次国家级、省部级重要网络安全保障和攻防演习活动,并积极参加各类网络安全竞赛,屡获殊荣。
对信息安全感兴趣的小伙伴欢迎加入宸极实验室,关注公众号,回复『招聘』,获取联系方式。
原文始发于微信公众号(宸极实验室):『CTF』聊聊一个数字游戏
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论