用线性代数逆向工程 Mersenne TwisterReverse engineering Mersenne Twister with Linear Algebra

Mersenne Twister（MT）是一种具有良好统计特性的随机数生成器，但加密安全性较差。用术语来说，它是一种伪随机数生成器（PRNG），但不是密码学安全的伪随机数生成器（CSPRNG）。

本文将展示如何通过线性代数从 MT 生成器的输出来恢复其内部状态。我们将使用线性代数方法来实现这一点。虽然位操作的方法更常见且更高效，但线性代数的方法在概念上更简单。

MT 的工作原理

Mersenne Twister 有多种变体。我们将重点讨论原始版本，其内部状态是一个长度为 640 的向量 x，其中填充了 32 位数字。本文中的思想同样适用于所有 MT 版本。

MT 的第一次调用返回的是 x[0] 的“ tempered”版本。下一次调用返回 x[1] 的 tempered 版本，依此类推。每经过 640 次调用后，状态会被打乱。这种打乱操作就是“Mersenne Twister”名称中“twist”的来源。（“Mersenne”部分来源于 MT 生成器的周期是一个梅森素数这一事实。）

Tempering（扰动）

以下是执行 tempering 步骤的 Python 代码。

def temper(y):
    y ^= (y >> 11) 
    y ^= (y <<  7) & 0x9d2c5680 
    y ^= (y << 15) & 0xefc60000 
    y ^= (y >> 18)  
    return y

每一步都是可逆的，因此 temper 函数本身也是可逆的。

由于 tempering 步骤是可逆的，第一个输出可用于推断内部状态的第一个元素，第二个输出用于推断第二个元素，依此类推。经过 640 次调用后，即可完全获知内部状态，并从此预测后续的所有输出。

上述所有位运算都对应于 GF(2) 域上的线性运算，该域仅包含两个元素：0 和 1。在此域中，加法是异或（XOR），乘法是与（AND）。

每一步相当于将一个 32 位的向量左乘一个 32×32 的矩阵，矩阵元素为 0 或 1；理解时需将两个比特的和视为它们的异或，乘积视为它们的与。等价地，所有算术运算都在模 2 下进行。因此，你可以像处理普通整数一样计算矩阵-向量乘积，只要在最后将每个整数对 2 取模即可。

我们将找到对应于 temper 操作的矩阵 M，并通过求其逆矩阵来证明它是可逆的。这证明了 tempering 是可逆的，理论上可以通过乘以 M⁻¹ 来计算其逆操作，尽管实际中通过位操作来撤销 tempering 会更高效。

一种恢复矩阵的方法是将它与单位向量 ei 相乘，其中 ei 的第 i 个分量为 1，其余分量为 0。于是

M ei

就是 M 的第 i 列。

因此，我们可以通过对 1 << n = 2ⁿ 进行 tempering 来得到 M 的第 n 列。

M = np.zeros((32, 32), dtype=int)
for i in range(32):
    t = temper(1 << (31-i))
    s = f"{t:032b}"
    for j in range(32):
        M[j, i] = int(s[j])

让我们生成一个随机数，并以两种方式计算其 tempered 形式：直接计算和使用矩阵乘法。

x = random.getrandbits(32)
y = temper(x)
print(f"{y:032b}")

vx = np.array([int(b) for b in f"{x:032b}"]) # vector form of x
vy = M @ vx % 2 # vector form of y
print("".join(str(b) for b in vy))

两者产生相同的比特结果：

10100101100101101100110101000110
10100101100101101100110101000110

我们可以通过求矩阵 M 的逆来找到 untemper 函数的矩阵表示。但这次我们需要在 GF(2) 域上求逆，而不是在整数或实数域上。

import galois
GF2 = galois.GF(2)
Minv = np.linalg.inv(GF2(M))

以下是使用黑色方块表示 1、白色方块表示 0 的方式可视化 M 及其逆矩阵。

M：

M⁻¹：

下一篇文章将回溯，研究构成 Mersenne Twister 各组件的线性代数原理。