mt19937的随机数生成器结构由一个32位的种子，然后生成一个具有624个32位数的状态数组。这些整数按顺序输出，全部输出后对该状态应用算法以获取下一组 624 个整数。
生成时分三个过程：
32位的MT19937的python代码```pythondef _int32(x):return int(0xFFFFFFFF & x)class MT19937:def __init__(self, seed):self.mt = [0] * 624self.mt[0] = seedself.mti = 0for 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 >> 11y = y ^ y << 7 & 2636928640y = y ^ y << 15 & 4022730752y = y ^ y >> 18self.mti = (self.mti + 1) % 624return _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```
这种情况只需要将已知的624组填入状态矩阵，即可进行预测和回溯。
有许多可以进行这类攻击的py库，如**randcrack**，**mt19937predictor**等，使用方法大同小异。
```pythonfrom randcrack import RandCrack#已知连续随机数data=[...]RC = RandCrack()for i in data:RC.submit(i)#给出足够多的随机数后，使用predict_getrandbits()即可预测随机数flag = RC.predict_getrandbits(32)```
任意19968个bit
在使用**getrandbits()**时如果是输出32的倍数时，会将前生成的32比特放在低位，新生成的拼接在高位。
而getrandbits(16) 中，只返回高16比特，其余比特位被丢弃。getrandbits(33) 中，低 32 比特取自第一组，而高1位取自第二组的最高位比特，第二组低31比特被丢弃。
如果给出了不连续的19968比特，这时候我们可以使用已知的部分构建矩阵求解：
对于每一个比特位b~i~，可以和状态矩阵state用一个线性关系表示出来
s*t=b_i
当我们有足够多的b之后就可以构成下面的矩阵方程
s*T=b
其中s和b为长19968的向量，T为19968*19968的矩阵。
如果T是满秩的，求解这个矩阵方程就可以得到s的唯一解，成功复原state，便可以进行溯源和预测。
所以接下来我们只要想办法获得b和T即可。
寻找T的过程类似于一个黑盒调用。具体来说，如果我们取s为：(1,0,0,...,0)
按照这个s设置state，然后调用getrandbits(),生成我们已知位置的比特，得到 b' ，此时得到的 b' 既是T的第一行。
同理，我们接下来取s：(0,1,0,...,0)
得到T的第二行。全部进行完即可得到完整的T。
```pythonDall=list(map(int,open('data3.txt','r').readlines()))from Crypto.Util.number import *from random import *from tqdm import *n=1250D=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 rowM=[]for i in tqdm_notebook(range(19968)):#这一部分为固定套路，具体原因已经写在注释中了"""referennce:糖醋小鸡块 2025/1/21 20:26:51这部分代码相当于取了一组线性基糖醋小鸡块 2025/1/21 20:26:56因为mt19937是线性的"""state = [0]*624temp = "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=0for j in range(32):C<<=1C|=int(s[32*i+j])G.append(C)import randomRNG1 = 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])```
原文始发于微信公众号（SKSEC）：【表哥有话说 第114期】MT19937
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论