题目类型：Windows CrackMe

一、题目概述：

设计一个称量方法，从 39 个球体中找到唯一一个重量异常的球体（轻、重未知），称量方法是一个矩阵，矩阵就是序列号经过转换后得到的，矩阵的每一行就是每次称量的策略，通过记录每次称量结果，即可找到对应的异常球体的编号及轻重。
数学思路：
如果可以无限次的称量，则逐个测量即可找出异常球体。如果考虑次数最少，那最少是多少了？能否考虑一种通用方法，使得每个球体检测出来的次数均相同的，但次数最少？
我们知道每次称量结果，只有三种结果：相等、左重、右重，那如果称量次数为 n 次，那么会有 $3^n$ 种结果，每一种结果可对应于一种异常的球体的编号及轻重，这样从理论上可以计算出相应的次数。 39个球体（含轻重）就有 $39*2=78$ 种结果，考虑到每次称量结果有3种，且 $3^3 = 27$，$3^4 = 81$，也就是说39个球体（含轻重）最少需要称量4次。
次数：$n=1$ ，结果：$3^n=3^1=3$
次数：$n=2$ ，结果：$3^n=3^2=9$
次数：$n=3$ ，结果：$3^n=3^3=27$
次数：$n=4$ ，结果：$3^n=3^4=81$
次数：$n=5$ ，结果：$3^n=3^5=243$
........
假定：球体的编号依次为 1 2 3 4 5 6 …... 38 39
而每次测量，如何选取球体？哪些放在左侧？哪些放在右侧？
我们把每次称量的方法作为矩阵的一行，0 表示不选取，1 表示放在右侧，-1 表示放在左侧。
比如 某一个称量矩阵。
$\left[ \begin{matrix} 0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&1&1&1&1&-1&1&-1&-1&-1&-1&-1&-1&-1&-1&-1&1&1&-1&-1&-1&1&1&1\\0&0&0&0&1&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&0&-1&-1&-1&-1&-1&-1&-1&-1&1&-1&-1&1&1&1&-1&-1&-1\\0&1&1&1&0&0&0&1&1&1&-1&-1&-1&0&0&0&1&1&1&-1&1&-1&0&0&0&-1&-1&1&1&1&0&0&0&-1&-1&-1&-1&-1&-1\\1&0&1&-1&0&1&-1&0&1&-1&0&1&-1&0&1&-1&0&1&-1&0&-1&-1&0&-1&1&0&1&0&-1&1&0&1&-1&0&-1&1&0&1&-1 \end{matrix} \right]$
第一行表示：1-13球体不参与，14-20、22、32、33、37-39，放在右侧，21、23-31、34-36 放在左侧。
称量结果：如果相等，为0；如果左侧重，为 -1 ；如果右侧重，为 1。
这样称量4次之后，会得到一个向量，
比如$\left[ \begin{matrix}0&0&1&0 \end{matrix} \right]$，其值刚好为第2个列向量，则表示第2个球体为重；
比如$\left[ \begin{matrix}0&0&-1&1 \end{matrix} \right]$，其值刚好为第4个列向量的相反值，则表示第4个球体为轻（相反值）。

二、题目逻辑：

获取序列号SN

1、读入用户输入序列号SN：SN是一个仅由[0-2]三种字符组成的字符串，长度为 156。

转换称量矩阵

2、将SN转换成称量矩阵Matrix：按照每行 39 个字符（数值），一共 4 行，且将字符串转换成数值，2 变成 -1

验证所有球体

3、验证过程：
模拟称量过程，依次读取每行的 39 个数值，0 表示不选取，1 表示放在右侧，-1 表示放在左侧。
逐个球体校验，假定球体 i 为重，则通过测量的4次结果是否与称量矩阵Matrix的第 i 列向量相等，且没有其余列向量与其相等或相反（向量乘以-1）。
如果所有球体（39个）均通过验证，则序列号正确，否则失败。

约束限制多解

4、考虑到称量矩阵（也就是序列号SN）存在很多种可能性，有如下约束：
（1）列向量升序排列：称量矩阵转换成列向量（2暂时不替换成-1），每个列向量转换成整数数值，则这个列表应该是升序排列的。
（2）剔除全1列向量：称量矩阵的列向量（正、反考虑为一种）初始选择会有 40 种（剔除0，减半，$81-1=80$，$80/2=40$），而只需要 39 个即可，另外考虑到至少有一个 0 的列向量（必须选择）有 32 个，还需要从剩余的8（$40-32=8$）个找到 7 个列向量（$39-32=7$），即有8种可能性，我们只考虑一种，比如把全 1 的列向量剔除。此时，就保证了初始的称量矩阵唯一。
（3）枚举所有可能：此时，答案还不唯一，而且很大，超过10000个，此时还需要做约束：
如果某个列向量的首位为0时，那逐步深入下去，第一个非0的数值为1，而不是2（-1）。比如 0001、0012、1000、1021、2021 满足要求，0021、0200不满足要求，经过此种方法操作，答案限定为 3781 个，耗时约 27 min，如果考虑签名验证，期望耗时约 14 min
（4）签名锁定唯一：为了更进一步限定唯一性，采用md5对SN进行签名认证。也就是第3步是一个需要穷举的过程。

本题仅考虑数学算法，不考虑其他保护措施，比如反调试、反反汇编、混淆处理。
输入字符串：156个，只能输入0/1/2，那么不分析具体算法，其解题空间非常大 ，基本排除纯暴力破解。
$3^{156} = 269721605590607563262106870407286853611938890184108047911269431464974473521$

三、题目解题思路：

具体的破解过程详见 WP，pyhon代码。
首先要从题目中意识到这是一个39个球体的称量问题。

1、获取初步的39个列向量，组成称量矩阵

（1）、找到40个“初步候选列向量”：排除[0,0,0,0]，每个列向量均有相反数，仅保留列向量（2开头、1开头、0开头且深入下去首个非0为1），排除列向量（0开头且深入下去首个非0为2）
（2）、从40个“初步候选列向量”找到32个“初步永久列向量”，即每个列向量中至少有一个0
（3）、从剩余的8个“初步可选列向量”任意选择7个，与上面的32个组成最终比较的称量矩阵，进行称量验证。

2、判断“称量矩阵”是否满足要求

（1）、升序排列
（2）、满足约束条件：每个列向量均不一样，即没有重复的；每行的0和1和2的数量均相等。
（3）、序列号的md5值满足要求

#给出的序列号：
000000000000011111111111112222222222222000011111111100001122222220000011222222011100011122200120200112220112202001122101201201201212001212020120121202010201

md5 = aac82b7ad77ab00dcef90ac079c9490d

[[ 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 1 1 -1 -1 1 -1 -1 -1 1
-1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 1]
[ 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 -1 1
-1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1]
[ 0 1 1 1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 -1 -1 -1 1 1 0 0
0 -1 -1 1 1 -1 0 0 0 1 -1 1 -1 -1 -1]
[ 1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 -1 1 0 -1 1 0 1
1 0 1 0 -1 -1 0 1 -1 0 -1 -1 0 1 -1]]

[[0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,1,1,-1,-1,1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,1,1,1,-1,1,1,1,1]
,[0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,-1,1,-1,-1,-1,-1,-1,1,1,-1,-1,-1,1,-1,-1,-1,-1]
,[0,1,1,1,0,0,0,1,1,1,-1,-1,-1,0,0,0,1,-1,-1,-1,1,1,0,0,0,-1,-1,1,1,-1,0,0,0,1,-1,1,-1,-1,-1]
,[1,0,1,-1,0,1,-1,0,1,-1,0,1,-1,0,1,-1,0,-1,1,0,-1,1,0,1,1,0,1,0,-1,-1,0,1,-1,0,-1,-1,0,1,-1]]

[[0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1,1,2,2,1,2,2,2,1,2,2,2,2,2,1,2,1,1,1,2,1,1,1,1]
,[0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,2,1,2,2,2,2,2,1,1,2,2,2,1,2,2,2,2]
,[0,1,1,1,0,0,0,1,1,1,2,2,2,0,0,0,1,2,2,2,1,1,0,0,0,2,2,1,1,2,0,0,0,1,2,1,2,2,2]
,[1,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,2,1,0,2,1,0,1,1,0,1,0,2,2,0,1,2,0,2,2,0,1,2]]

a=[
[0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1,1,2,2,1,2,2,2,1,2,2,2,2,2,1,2,1,1,1,2,1,1,1,1],
[0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,2,1,2,2,2,2,2,1,1,2,2,2,1,2,2,2,2],
[0,1,1,1,0,0,0,1,1,1,2,2,2,0,0,0,1,2,2,2,1,1,0,0,0,2,2,1,1,2,0,0,0,1,2,1,2,2,2],
[1,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,2,1,0,2,1,0,1,1,0,1,0,2,2,0,1,2,0,2,2,0,1,2]]

后续：

考虑序列号压缩，能够缩减字符数量。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课