MT19937（梅森旋转算法）

大家好，欢迎来到IT知识分享网。

梅森旋转算法

定义：梅森旋转算法（Mersenne twister）是一个伪随机数发生算法。由松本真和西村拓士在1997年开发，基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。

其中，最为广泛使用Mersenne Twister的一种变体是MT19937，可以产生32位整数序列。具有以下的优点：

1. 周期非常长，达到2−1。尽管如此长的周期并不必然意味着高质量的伪随机数，但短周期（比如许多旧版本软件包提供的2）确实会带来许多问题。
2. 在1 ≤k≤ 623的维度之间都可以均等分布（参见定义）。
3. 除了在统计学意义上的不正确的随机数生成器以外，在所有伪随机数生成器法中是最快的（当时

实现过程：

整个算法主要分为三个阶段：

第一阶段：获得基础的梅森旋转链；

第二阶段：对于旋转链进行旋转算法；

第三阶段：对于旋转算法所得的结果进行处理；

算法实现的过程中，参数的选取取决于梅森素数，故此得名。

MT19937

在讨论之前，引入MT19937-32的生成python代码：（此代码在 [0,2^32-1] 生成的伪随机数基本大致相同）

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( * (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 &  y = y ^ y << 15 &  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] & 0x) + (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 

接下来，我们观察上面MT19937的代码，我们可以发现代码分为四个部分：

一、_int32(x)模块

返回一个32位的二进制代码。

二、__init__(self, seed):

首先，我们必须要知道seed在代码中是种子，意思是基于已知的seed生成624个state块（伪随机数通过对不同的state块进行变换求得），我们先将state的第一个数值定为seed，代码中的623个循环便是通过state间的变换求出求出剩下的state块。

三、extract_number(self)

MT19937算法通过此模块来得到不同的伪随机数。首先，我们先进行判断，如果此时self.mti指向第一个state，我们运行__init__(self, seed):得到623个state值，如果不是，则直接进入下面的伪随机数生成过程：用通过seed求得的state值进行代码中的变换求得并返回我们所需的伪随机数。

四、twist(self):

如果只有上面的块，那么只能求得624个不同的伪随机数，但是MT19937-32却可以求出2^32-1个不同的伪随机数便是因为这个模块。旋转模块基于上一次循环中我们已经使用过的624个state值，一一对应，通过原代码中的：

y = _int32((self.mt[i] & 0x) + (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个与上一次循环中不同的state值，并进入新的循环中。

MT19937的反推导

引入反推导代码：

#python2 from Crypto.Util import number # 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 &  y = y ^ y << 15 &  y = y ^ y >> 18 return y&0xffffffff def recover(y): y = inverse_right(y,18) y = inverse_left_mask(y,15,) y = inverse_left_mask(y,7,) y = inverse_right(y,11) return y&0xffffffff def transform(message): assert len(message) % 4 == 0 new_message = '' for i in range(len(message) / 4): block = message[i * 4 : i * 4 +4] block = number.bytes_to_long(block) block = convert(block) block = number.long_to_bytes(block, 4) new_message += block return new_message transformed_flag = 'a9e3953b1aaa21f3a2' c = transformed_flag.decode('hex') flag = transform(c) print flag.encode('hex') 

反推导就是我们在知道通过Mt19937算法求得的y1，来反推出用于MT19937算法的state原始值y。而异或的反推则是再异或相同的数就可以消去这个相同的数。

那么，我们先分析生成代码中所有的不同生成方式（主要分为 “>>” “<<” “>> &” “<< &”)，所以，我们可以看到反推导代码中先将不同的生成方式写出（前四个），在其中，bits // shift是个难点，我们可以作以下分析：

 MT19937算法的基本思路大致如此。