算法描述
主要步骤
- 利用 seed 初始化寄存器状态
- 对寄存器状态进行旋转
- 根据寄存器状态提取伪随机数
初始化可能用的是固定的种子，也有可能是服务器时间戳，生成一个长度为624的状态数组，填充完后作为初始状态
旋转的目的是增加不确定性还有均匀性，主要是位运算实现的线性变换
提取伪随机数这一步会从状态数组中依次提取一个整数，并对其进行位运算和异或运算，生成的数即为输出的伪随机数。当所有数组全被遍历过之后，就会对状态数组再次进行一次旋转，重新生成新的状态数组。
python代码实现
这是一个简单的实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
def _int32(x):
return int(0xFFFFFFFF & x)
class MT19937:
# 初始化
def __init__(self, seed):
self.mt = [0] * 624
self.mt[0] = seed
self.mti = 0
for i in range(1, 624):
self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
# 提取伪随机数
def extract_number(self):
if self.mti == 0:
self.twist()
y = self.mt[self.mti]
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
self.mti = (self.mti + 1) % 624
return _int32(y)
# 旋转状态
def twist(self):
for i in range(0, 624):
y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df
|
为什么说是简单的生成方法呢？可能知道python的random库也是MT19937生成伪随机数，但是它对 seed 的传入经过了两步处理 init_genrand和 init_by_array，因此和上面的实现是有区别的，也就是说两者产生的状态矩阵和伪随机数是不一样的。
这里跟随xenny老师的思路走，就拿y = y ^ y << 7 & 2636928640举例
那么整个式子就是
$$
y=x \oplus ((x\ll7)\&2636928640)\\
\quad\quad\quad\quad\quad\quad =x \oplus ((x\ll7)\&10011101001011000101011010000000)
$$
注意后七位都是0，那么最后结果的后七位和最初状态的后七位就是相同的，在y已知的情况下，我们就可以步步回推了，比如倒数8~14位就是
$$
(后七位 \& 0101101) \oplus y的倒数8到14位
$$
其他的类似，用代码实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def invert(res, shift, right=True, mask=0xffffffff, bits=32):
tmp = res
if right:
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp
else:
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def inv_extract_number(y):
y = invert(y,18,True)
y = invert(y,15,False,4022730752)
y = invert(y,7,False,2636928640)
y = invert(y,11,True)
return _int32(y)
|
逆向twist
在上文中我们提到如果得到了某一轮 state 的全部信息便可以向后预测随机数，那么如果我们需要向前恢复随机数，则需要对 twist 函数进行逆向。
1
2
3
4
5
6
7
|
def twist(self):
for i in range(0, 624):
y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df
|
先关注旋转的后几步操作，能注意到由于 y>>1的最高位一定为 0，所以最终 self.mt[i]的最高位一定由 self.mt[(i + 397) % 624]或 self.mt[(i + 397) % 624] ^ 0x9908b0df控制，所以可以判断出是否经历了xor 0x9908b0df 操作。然后由于是否异或操作同时受最低位控制，那么逆向的时候即可，通过是否异或来恢复因为就右移而丢失的最低位。于是我们就得到了 y
然后分析旋转的第一步，y 是由 self.mt[i]的最高位和 self.mt[(i + 1) % 624]的除最高位部分组合得到的。所以我们只要计算 self.mt[i]和 self.mt[(i - 1) % 624]两个位置的 y 就能得到 self.mt[i]的值了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def inv_twist(state):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
def _recover(i):
y = state[i] ^ state[(i + 397) % 624]
if y & high == high:
y ^= mask
y <<= 1
y |= 1
else:
y <<= 1
return y
for i in range(len(state)-625, -1, -1):
state[i] = _recover(i) & high
state[i] |= _recover(i-1) & low
return state
|
逆向init
这玩意的主要操作是
self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] » 30) + i)
你可以发现，里面主要是乘法加法和self.mt[i - 1] ^ self.mt[i - 1] >> 30，前两者可逆运算，后面这个和前面的类似，通过invert逐位还原即可
1
2
3
4
5
6
7
|
def inv_init(last):
n = 1<<32
inv = pow(1812433253,-1,n)
for i in range(623,0,-1):
last = ((last-i)*inv)%n
last = invert(last,30)
return last
|
给出任意19937个bit
这个类型是看鸡块神的博客学到的，主要的地方还是在于构建矩阵，直接上脚本吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
Dall=list(map(int,open('data3.txt','r').readlines()))
from Crypto.Util.number import *
from random import *
from tqdm import *
n=1250
D=Dall[:n]
rng=Random()
def getRows(rng):
#这一部分根据题目实际编写，必须和题目实际比特获取顺序和方式完全一致，且确保比特数大于19937，并且请注意zfill。
row=[]
for i in range(n):
row+=list(map(int, (bin(rng.getrandbits(16))[2:].zfill(16))))
return row
M=[]
for i in tqdm_notebook(range(19968)):#这一部分为固定套路，具体原因已经写在注释中了
state = [0]*624
temp = "0"*i + "1"*1 + "0"*(19968-1-i)
for j in range(624):
state[j] = int(temp[32*j:32*j+32],2)
rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
M.append(getRows(rng))
M=Matrix(GF(2),M)
y=[]
for i in range(n):
y+=list(map(int, (bin(D[i])[2:].zfill(16))))
y=vector(GF(2),y)
s=M.solve_left(y)
#print(s)
G=[]
for i in range(624):
C=0
for j in range(32):
C<<=1
C|=int(s[32*i+j])
G.append(C)
import random
RNG1 = random.Random()
for i in range(624):
G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
print([RNG1.getrandbits(16) for _ in range(75)])
print(D[:75])
|
常用脚本
原始版本
最经典的款式，速度慢，不好用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
def construct_a_row(RNG):
row = []
for _ in range(19968//32):
tmp = RNG.getrandbits(32)
row += list(map(int, bin(tmp)[2:].zfill(32)))
return row
# 构造线性方程组的矩阵
L = []
for i in trange(19968):
state = [0]*624 # MT19937使用624个32位整数作为状态
# 构造一个只有一位为1,其他都为0的序列
temp = "0"*i + "1"*1 + "0"*(19968-1-i)
# 将这个序列分成624段,每段32位,转换为整数
for j in range(624):
state[j] = int(temp[32*j:32*j+32], 2)
RNG = Random()
RNG.setstate((3,tuple(state+[624]),None))
L.append(construct_a_row(RNG))
# 将L转换为GF(2)上的矩阵（二进制域）
L = Matrix(GF(2),L)
print(L.nrows(), L.ncols())
def MT19937_re(state):
try:
# 构造目标向量R
R = []
for i in state:
R += list(map(int, bin(i)[2:].zfill(32)))
R = vector(GF(2), R)
s = L.solve_left(R) # 这里可能会抛出异常
# 将解转换为二进制字符串
init = "".join(list(map(str,s)))
state = []
# 将解重新分割成624个32位整数
for i in range(624):
state.append(int(init[32*i:32*i+32],2))
# 创建新的RNG并设置恢复出的状态
RNG1 = Random()
RNG1.setstate((3,tuple(state+[624]),None))
return RNG1
except Exception as e:
print(f"[-]{e}")
pass
RNG = MT19937_re()
|
randcrack
一个无脑的方法？直接利用这个库进行预测，但是只能是624*32，要不然不行
1
2
3
4
5
6
7
8
|
import random
from randcrack import RandCrack
rc = RandCrack()
for i in range(624):
rc.submit(random.getrandbits(32))
print(random.getrandbits(64))
print(rc.predict_getrandbits(64))
|
github上有一个优化后的版本，但是还没有用过，可以看看链接
gf2bv
maple神写的一个库，本质是接GF(2)方程组的，MT19937刚刚好满足，所以可以拿来使用，传送门。TGCTF的那个题就可以用这个库去写，非常的好用。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *
import random
from Crypto.Util.number import *
def mt19937(bs, out):
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
#rng.getrandbits(175)
zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
print("solving...")
sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()
for i in range(2496):
out.append(pyrand.getrandbits(8))
print(pyrand.getrandbits(8))
import random
random.seed(1)
out=[]
for i in range(2496):
out.append(random.getrandbits(8))
mt19937(8, out)
|
这里，zeros.append()的时候需要注意和题目中获取randbits的方式一致。生成的pyrand其实是它的初始状态，需要预测哪个就往后递推就行了。
关于安装：
- mac直接去github下m4ri的包，然后本地编译后sudo make install
- 如果像我一样在pyenv这种虚拟环境里面跑python的，把环境注入进去
export CFLAGS="-I/usr/local/include" export LDFLAGS="-L/usr/local/lib"然后再pip install .
