广义mt19937随机数逆向

发表于 更新于 分类于 本文字数： 4k 阅读时长 ≈ 4 分钟

题意简述

给出mt19937中的10个参数、、、、、、、、、，并给出刚刚生成的前个伪随机数，求出伪随机数对应的种子seed。

思路分析

20pts

暴力枚举seed即可，代码略。

100pts

做法的大致思路是：生成的随机数→twist后的state→twist前可能的state[-1]→求得seed

我们先考虑标准情况，也就是参数与论文完全一致的时候，这里有一篇现成的题解。

具体原理这里就不阐释了，给的链接和Mivik的题解叙述得很清楚。

然后当的首位不为1时，就不能直接通过tmp的首位判断原来的tmp是不是奇数了。

原题解中逆向twist的代码如下：

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
def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(623,-1,-1):
        tmp = state[i]^state[(i+397)%624]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        # recover highest bit
        res = tmp&high
        # recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
        tmp = state[i-1]^state[(i+396)%624]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        res |= (tmp)&low
        state[i] = res    
    return state

这里的问题就出在if tmp & high == high:这个条件判断已经失效，不能据此判定tmp的准确值。

一个简便的做法是枚举mt[N - 1]的四种可能，然后由于mt[i - 1] ^ mt[i - 1] >> 30可逆，而且因为是奇数，与2 ** 32 必定互质，因此可以通过求的逆元来倒推seed。

检验这四个seed的方式就是用seed再重新生成几个随机数，与输入比对即可。

完整代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
from gmpy2 import invert
def _int32(x):
    return int(0xFFFFFFFF & x)
class mt19937:
    def __init__(self, seed=0):# magic method (run code below automatically when an object is created) 
        self.mt = [0] * N
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, N):
            self.mt[i] = _int32(F * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
    def getstate(self,op=False):
        if self.mti == 0 and op==False:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> U
        y = y ^ y << S & B
        y = y ^ y << T & C
        y = y ^ y >> L
        self.mti = (self.mti + 1) % N
        return _int32(y)
    def twist(self):
        for i in range(0, N):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % N] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + M) % N]
            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ A
    def inverse_right(self,res, shift, mask=0xffffffff, bits=32):
        tmp = res
        for i in range(bits // shift):
            tmp = res ^ tmp >> shift & mask
        return tmp
    def inverse_left(self,res, shift, mask=0xffffffff, bits=32):
        tmp = res
        for i in range(bits // shift):
            tmp = res ^ tmp << shift & mask
        return tmp
    def extract_number(self,y): # namely "temper" in Mivik's code
        y = y ^ y >> U
        y = y ^ y << S & B
        y = y ^ y << T & C
        y = y ^ y >> L
        return y&0xffffffff
    def recover(self,y): # inverse of extract_number
        y = self.inverse_right(y,L)
        y = self.inverse_left(y,T,C)
        y = self.inverse_left(y,S,B)
        y = self.inverse_right(y,U)
        return y&0xffffffff
    def setstate(self,s): # N generated random numbers -> mt[] after twisting 
        if(len(s)!=N):
            raise ValueError("The length of prediction must be N!")
        for i in range(N):
            self.mt[i]=self.recover(s[i])
        #self.mt=s
        self.mti=0
    ''' 
    def predict(self,s): # a method to predict other pseudo random numbers after given N of them (useless in this problem)
        self.setstate(s)
        self.twist()
        return self.getstate(True)
    '''
    def invtwist(self): # mt[] after twisting -> 4 possible values of mt[-1] before twisting
        high = 0x80000000
        low = 0x7fffffff
        mask = A
        opt = [0] * 4
        for i in range(N-1,N-2,-1): # only process the last number
            for s in range(2):
                for t in range(2):
                    tmp = self.mt[i]^self.mt[(i+M)%N]
                    if s==0: # two possibilities
                        tmp ^= mask
                        tmp <<= 1
                        tmp |= 1
                    else:
                        tmp <<=1
                    res = tmp&high
                    tmp = self.mt[i-1]^self.mt[(i+M-1)%N]
                    if t==0: # another two
                        tmp ^= mask
                        tmp <<= 1
                        tmp |= 1
                    else:
                        tmp <<=1
                    res |= (tmp)&low
                    opt[s * 2 + t] = res
        return opt
    
    def recover_seed(self,last): # mt[-1] -> mt[0]
        n = 1 << 32
        inv = invert(F, n) # inverse of F mod 2 ^ 32
        for i in range(N-1, 0, -1):
            last = ((last - i) * inv) % n
            last = self.inverse_right(last, 30)
        return last

N, M, A, U, S, B, T, C, L, F = map(int, input().split())
inpt = [0] * N # align enough space
for i in range (N):
    inpt[i] = int(input())
D = mt19937() 
D.setstate(inpt) # using the input to recover state after twisting
op = D.invtwist() # generate four possibilities of D.mt[-1]
seed = [0] * 4
for i in range(4): # check the seeds one by one
    seed[i] = D.recover_seed(op[i]) 
    E = mt19937(seed[i])
    E.getstate() # another psuedo random number generator
    flag = 1
    for j in range(10): # compare first 10 numbers is totally enough 
        if E.extract_number(E.mt[j]) != inpt[j]:
            flag = 0
    if flag > 0:
        print(seed[i])
        break

时间复杂度。