-
题目分类：math
-
题目分值：350
去年信安大赛爆料的「可以心算分解任意大整数的神童」在社会上激起了激烈的讨论，就连美国的 NSA 也出来辟谣：「That's all fake! Fake news!」
Z 同学还是有点不相信，于是举办了一场「大整数分解锦标赛」，以 flag 为诱饵来寻找那些可以心算分解大整数的神童。
nc 202.38.93.241 10010 或者使用 网页终端
看似逻辑严谨没有问题的代码，其实问题出在伪随机数上。
我出这道题的原因是，我之前遇到过一些 Python 或者其他使用 MT19937 伪随机数发生器的语言的随机数预测题目。它们都是友好地给了至少 624 个完整的 32 bit 随机数。在代码中，random.getrandbits(32) 显得很突兀，一眼就看出来是在随机数发生器上做文章，而且网上很容易找到基于 624 个 32 bit 随机数的 MT19937 预测器代码。
所以，我出了这样一道题，用 sympy.randprime 来生成大素数。但其实内部还是使用了 Python 的 random 模块。
凭空预测 Python 的随机数是不太可能的，因为默认的随机数种子初始化使用了系统的 /dev/urandom。
首先，你需要多次调用程序的 Help 功能，来收集很多由随机数生成的大素数，同时也会收集到随机生成的 bits（即大素数的量级）。
然后，你需要使用收集到的信息来尽可能多的重建随机数发生器的内部状态。MT19937 算法每次生成 32 bit 的随机数，你需要搞懂 randrange 和 randprime 是如何利用多个 32 bit 随机数来生成结果的。
根据 sympy 的源代码，我们可以知道 randprime 的原理是先用 random.randint 生成一个随机整数，然后再去找它的下一个素数。因此，我们得到的素数的低位其实是丢失了一些信息的。
根据 Python 的源代码，依次找到 randint、randrange、_randbelow_with_getrandbits，关键代码为：
k = n.bit_length() # don't use (n-1) here because n can be 1
r = getrandbits(k) # 0 <= r < 2**k
while r >= n:
r = getrandbits(k)
return r我们发现，Python 会根据范围大小的 bit 数量来生成一些随机 bit，然后如果结果不在范围内就重新生成。如果出现重新生成的情况，我们就会丢失很多 bit 的信息，并且同时也会导致我们无法预测 32 bit 块的偏移量。这也是为什么题目 sympy.randprime(3, 2 ** bits) 中出现了 3 这个数字，同时 random.randrange(10, 1024) 也保证了随机的范围稍小于 2 的幂。
然后，你需要从源代码或者自己黑盒测试来搞明白 Python 的 random.getrandbits 参数不是 32 时它是如何把多个 32 bit 数拼接起来的。
当你都搞懂了之后，你就可以用反复 Help 得到的随机数来重构 MT19937 的内部状态了。当然，因为上面说的 _randbelow_with_getrandbits 不在范围就会重试的原因，你只能乐观地认为没有发生过重试。（当然，你也可以为此专门写一些代码来处理出现重试的可能。）我在出题时算过概率，如果你的脚本正确，重试几次之内就有机会得到正确的内部状态。
然后，你需要从缺失了一部分 bit 的 MT19937 内部状态来尽可能补全所有 624 个内部状态。MT19937 算法中一个块的值只与它之前第 624、623、227 个块有关，所以如果某个块的值缺失，很可能可以由上一个 624 个块的周期甚至上上个周期的数据补救，这里具体的运算不是很复杂，可以参考 MT19937 的实现，也可以参考一些其他人写的随机数预测器，例如这个。当我们补全连续的 624 个块时，就可以预测所有接下来的随机数了。
你能预测接下来的所有随机数之后就不用我讲如何获得 flag 了。
所以这道题和大整数分解本身没有任何关系。
我的解题代码在 solve.py 里面，它很复杂，因为我利用了尽可能多的 bit，包括很多范围的推导。而且我把随机数预测抽象成了一个类，你可以往里面塞入已知的随机数、已知的大素数或者未知的量，它可以维护内部状态。如果仅仅是想求解这道题，代码可以写得比我简单很多，例如说对于素数的低位，可以直接把低 32 位丢掉。
由这道题我们可见使用非密码学安全的随机数发生器用在密码学参数中会带来的不安全问题。其实对于已知 bit 更少的情况，也可能是可以解出来的，例如使用高斯消元法求解关于内部状态每个 bit 的线性方程组。
在密码学相关的程序中一定要使用密码学安全的随机数发生器（CSPRNG），不要自己随手就用个编程语言自带的 Random 函数，它们通常为了性能优化，是不安全的。