Crypto基础篇-MT19937

简介

梅森旋转（Mersenne Twister）是一个PRNG（伪随机数发生器），基于有限二进制字段上的矩阵线性递归，可快速产生高质量的伪随机数，周期为$2^{19937}-1$，也就是19937bits。
python中的random库使用的便是这种算法。

实现步骤：

1. 获得基础的梅森旋转链
2. 对于旋转链进行旋转算法
3. 对旋转算法所得结果进行处理

涉及变量：

• $w:$ 加密长度，以bit为单位，$w$位整数
• $n:$ 递归长度
• $m:$ 周期参数，用于第三阶段的偏移量
• $a:$ 旋转矩阵的参数
• $r:$ 低位掩码，即低位要提取的位数
• $f:$ 初始化旋转链所需参数
• $b,c:$ TGFSR的掩码
• $s,t:$ TGFSR的位移量
• $u,d,l:$ 额外的梅森旋转所需要的掩码和位移量

加密方法

1.初始化

将传入的seed赋值给$MT_0$作为初始值，并且递推得到旋转链
递推式： $MT_I=f\times [(MT_{i-1})\oplus((MT_{i-1})>>(w-2))]+i$

2.旋转算法

连接$MT_i$的高$w-r$位和$MT_{i+1}$的低$r$位，若这个组合后的二进制数末位为0，将其除以2。否则将这个数除以2后再与$a$进行异或。假设我们最终得到的数字为$P$
我们得到递推式为$MT_i=MT_{i+m}\oplus P$

3.结果处理

设$x$是该序列的下一个值，$y$是一个中间变量，$z$是算法的返回值。
处理过程如下：

y = x ^ ((x>>u) & d)
y = y ^ ((y<<s) & b)
y = y ^ ((y<<t) & c)
z = y ^ (y>>l)

代码如下：

def _int32(x):
    return int(0xFFFFFFFF & x)
 
class MT19937:
    # 根据seed初始化624的state
    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

解密方法

关键： 求出一个周期内的全部内容，然后便可以推出前面的所有情况

1.逆向第四步

$z = y \oplus (y>>l)$，求$y$

• 高$l$位： 可以看出$y$的高$l$位便是$z$的高$l$位
• 高$l\sim 2l$位： 由$z$的高$(l\sim 2l)\oplus y的高l位$得到$y的高l\sim 2l位$
• 高$il\sim (i+1)l$位： 同上由$z$的高$(il\sim (i+1)l)\oplus y$的高$[(i-1)l]\sim il$位得到

2.逆向第三步

$y_1 = y \oplus ((y<<t) \land c)$，求$y$

• 低$t$位： 可以看出$y_1$的低$t$位便是$y$的低$t$位异或$c$的低$t$位
• 低$it\sim (i+1)t$位： 由$y_1$的低$it\sim (i+1)t$位与$y的(i-1)\sim it$位与$c$的$it\sim (i+1)t$的并的异或

3.逆向第二、一步

与上同理，总代码如下：

# right shift inverse  
def inverse_right(res, shift, bits=32):  
tmp = res  
for i in range(bits // shift):  
tmp = res ^ tmp >> shift  
return tmp  
# right shift with mask inverse  
def inverse_right_mask(res, shift, mask, bits=32):  
tmp = res  
for i in range(bits // shift):  
tmp = res ^ tmp >> shift & mask  
return tmp  
# left shift inverse  
def inverse_left(res, shift, bits=32):  
tmp = res  
for i in range(bits // shift):  
tmp = res ^ tmp << shift  
return tmp  
# left shift with mask inverse  
def inverse_left_mask(res, shift, mask, bits=32):  
tmp = res  
for i in range(bits // shift):  
tmp = res ^ tmp << shift & mask  
return tmp  
def extract_number(y):  
y = y ^ y >> 11  
y = y ^ y << 7 & 2636928640  
y = y ^ y << 15 & 4022730752  
y = y ^ y >> 18  
return y&0xffffffff  
def recover(y):  
y = inverse_right(y,18)  
y = inverse_left_mask(y,15,4022730752)  
y = inverse_left_mask(y,7,2636928640)  
y = inverse_right(y,11)  
return y&0xffffffff  
print(recover(0xf1c680f8))  
'''  
for i in s:  
print(recover(i))  
  
y = extract_number(o)  
print('y=',y,'o=',o)  
print(recover(y) == o)  
'''

对于MT32的一些参数：
$(w,n,m,r)=(32,624,397,31)$
$(a,f)=(9908B0DF_h,1812433253)$
$(u,d,s,b,t,c)=(11,FFFFFFFF_h),7,9D2C5680_h,15,EFC60000_h$
$l=18$

常见题型

1.逆向随机数产生器内部的state中的内容

2.预测后面的随机数

3.求出之前的随机数

参考：Explore MT19937 - huangx607087’s Blog