-
题目分类：general
-
题目分值：250
时间可以正向流动，也可以逆向流动，熵可以增加，也能够降低。
NETET 组织最近收到线报，地球上有一伙人找到了 shuffle 的逆函数，我们把这伙人称为 SHUFFLE 组织。技术团队分析了 SHUFFLE 组织的部分网络流量，其中的部分数据被经过了特殊处理，使其变成了人类无法阅读的顺序，但是 SHUFFLE 组织的人却似乎可以还原。
类似处理方法通常被人们称之为加密，但恐怖的是，SHUFFLE 仅仅使用了现有编程语言中自带的 shuffle 函数，如 Python 中的 random.shuffle(x)，这既不需要共享知识，也没有密钥交换，数据的位置被随机打乱，并且因为其随机性，每次处理后的结果都不相同。
“等等……”，敏锐并且数理基础扎实的你打断了正在报告的同事，“shuffle 的输出是对称群 Sn 中某个置换作用在输入上的结果，这个置换可以是 Sn 中的任意元素，而且每个元素的概率相等，所以 shuffle 之后理论上就无法还原了”。
确实。这就是诡异的地方，比如 hello 可能被 shuffle 之后变成 lehol，原来的信息被随机打乱了。
“等等……”，敏锐并且数理基础扎实的你再次打断了正在报告的同事，“我起码知道原来的字符串的统计特征”。
正是。我们知道 「研表究明，汉字的序顺并不定一能影阅响读」，说不定 SHUFFLE 这一伙人正是掌握了这种技术————他们能在 shuffle 空间和正常空间随意翻转穿梭。但这对于我们来说简直是不可能实现的任务，比如字符串 「00001111」，shuffle 之后变成了 「01101001」，我们又怎么可能知道 shuffle 前的数据是什么呢？幸运的是……
“等等……”，敏锐并且数理基础扎实的你，刚准备打断正在报告的同事……
好好好，你啥都懂。我们找到了一个 SHUFFLE 的密码库，但重要情报被 shuffle 化了，破译小组还没有任何进展，我们逆向得到的生成验证码的代码也放在下边了，你行你上好吧。
首先我们来分析题目的设置：
- 正常提交验证码，提示信息是 shuffle 过后的，如果验证码正确，可以得到被 shuffle 之后的 flag；
- shuffle 模式提交验证码，验证码是 shuffle 过后的，随意提交，提示信息是正常顺序；
- 因为是选择字符数量，提交验证码的时候不需要字符顺序正确；
- 从题目附件脚本来看，产生验证码的全部信息都已知，包括字体、字符集、长度等；
- 验证码有 16 个字符，10 条彩色随机噪音；
- 附件使用的随机产生器都是 SystemRandom；
根据题意和以上设置可以推测：
- shuffle 模式下如果验证码正确，可以得到正常模式的 flag；
- 只需要还原有哪些字符，不用还原字符顺序（应该也没法还原）；
- 不用考虑随机数预测；
所以我们的任务就是：通过 shuffle 后的验证码图片还原其中的字符个数。
观察渲染生成的验证码中的文字，发现这些文字的像素值是均匀分布在黑色到白色间的，共有 256 种可能的取值，边缘处逐渐由黑变白，并不是只有纯黑和纯白，我们忽略纯白的那种取值，还剩下 255 种。
记 pix(x) 为字符 x 生成图片中像素值的统计向量（忽略白色，维度：255），我们可以得到以下恒等关系：
forall x, y, pix(x . y) = pix(x) + pix(y),
其中 . 为字符串连接，所以对于验证码来说，
pix(captcha) = sum(pix(c) for c in captcha) = sum(n(captcha, x) * pix(x) for x in alphabet),
其中 captcha 是验证码，alphabet 是字符集（共 62 个），n(captcha, x) 是某个字符在验证码中出现的次数。
如果我们把字符集中所有字符的 pix() 计算出，就可以排列成维度为 (62, 255) 的字体像素矩阵 A，其中 aij 代表第 i 个字符的图像有多少个像素值为 j 的像素。同时将 shuffle 后验证码整体统计得到的 pix() 计算出，记为维度为 255 的向量 b，那么我们想要求解的就是字符数量就是维度为 62 的向量 x = (n(captcha, 'a'), n(captcha, 'b'), ...)，并且有以下方程：
A^T.x = b,
啊这。这不是线性方程吗，还是个超定线性方程组，解就完事儿了。
噪音使得上式不完全相等，不能应用一些精确求解办法。首先我们在统计 pix(captcha) 时忽略所有彩色的像素，由于彩色的噪声遮盖了部分字符，我们的 b 会比真实的 b_true 略小一点，这样得到的方程是：
A^T.x = b_true - noise,
其中 noise 为非负的噪音。
由于噪音未知（是随机生成的）但是很小，对上式变形，用优化方法最小化噪音，求解 x* = argmin_x(noise . noise^T) = argmin_x((Ax - b_true) . (Ax - b_true)^T) 即可。
有很多方法可以求解此式，下面给出一种使用最小二乘的参考方法。
# char-pix matrix, shape: (62, 255)
A = np.array([count_pix(img_generate(c)) for c in alphabet])
# pix sum vector, shape: (255, )
b = count_pix(img)
# Solve A^T.x = b using least-squares method
xf, *_ = np.linalg.lstsq(A.T, b, rcond=None)
# number matrix, shape: (62, )
x = xf.round().astype(np.int).tolist()本题也可以用线性回归、神经网络等，直接拟合 pix(captcha) -> x 的映射关系，准确率足以通过本题。
如果使用上述优化思路，带 L1 正则的优化方法（如：Lasso）抵抗噪音的能力更强。
见 payload.py。