MT19937

发表于 阅读次数： Waline： 本文字数： 9.3k 阅读时长 ≈ 34 分钟

记录MT19937学习过程

MT19937

MT19937 即梅森旋转算法（Mersenne twister）由松本眞（日语：松本真）和西村拓士在 1997 年开发，基于二进制有限域 $\mathbb{F}_2$上的矩阵线性递归，可以快速产生高质量的伪随机数。

该算法的周期为 $2^{19937}-1$，故名为MT19937。该算法具有以下优点：

  1. 周期非常长，为 $2^{19937}-1$
  2. 在 $1 \le k \le 623$ 都满足 $k$ - 分布
  3. 能比硬件实现的方法更快产生随机数
  • $k$ - 分布：一个周期为 $P$ 的 $w$ 位整数的伪随机序列 $x_i$ ，如果下列成立则称其 $v$ - 比特精度的 $k$ - 分布成立。

​ 令 $\mathrm{trunc_v(x)}$ 表示由 $x$ 的前 $v$ 位形成的数，并考虑 $P$ 中 $k$ 个 $v$ 位向量。
$$
(\mathrm{trunc_v(x_i)},\mathrm{trunc_v(x_{i+1})},…,\mathrm{trunc_v(x_{v+k-1})})(0 \le i < P)
$$
​ 然后，$2^{kv}$ 个组合中每一个都在一个周期内出现次数相同（全 0 组合出现次数较少除外）。

代码实现

MT19937 算法可以分为3部分

  1. 初始化：通过种子（就是常称为的seed）产生一个长度为624的状态数组（这里记为state），而种子可以由用户给定，也可以将时间戳之类的东西作为种子。
  2. 旋转状态：将状态数组中的每个元素进行线性变换，生成新的状态数组。这个过程是通过对当前状态数组中的每个元素进行位运算和异或运算来实现的。旋转的目的是为了增加随机数的均匀性和不可预测性。
  3. 提取伪随机数 ：这一步会从状态数组中依次提取一个整数，并对其进行位运算和异或运算，生成的数即为输出的伪随机数。当所有数组全被遍历过之后，就会对状态数组再次进行一次旋转，重新生成新的状态数组。（将提取出的整数记为output）

其中 32 位的 MT19937 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

举个例子：

1
114514 对应的状态序列(前四个)为: [114514, 3276889435, 1198910394, 2731152330]

可以发现状态序列的第一个值就是seed，当我们调用extract_number()的时候，状态序列会先做一次twist，以seed = 114514为例，twist之后的状态序列为

1
[1300186559, 2421719561, 1949913479, 4078121321]

再根据这个状态序列提取出伪随机数

1
114514 产生的输出序列(前四个)为: [2953888979, 3549084027, 2904140651, 3722666743]

安全分析

逆向 extract_number 函数

分析可见文末xenny师傅的博客，代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def recover(y):
    y = inverse_right_mask(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right_mask(y,11)
    return y&0xffffffff

验证一下recover(output) == state

1
2
3
4
print(recover(2953888979))
print(recover(3549084027))
print(recover(2904140651))
print(recover(3722666743))

运行结果

1
2
3
4
1300186559
2421719561
1949913479
4078121321

与twist之后的状态对上了

预测随机数

当我们能够逆向 extract_number 中的数据时，这也意味着我们能够提取得到 state 中的原始数据，同时可以发现后续的随机数完全依赖于上一轮的 state，所以如果我们能够得到某一轮的全部 state 数据，便可以向后调用 twist 来预测随机数。

逆向 twist 函数

分析可见文末xenny师傅的博客，代码实现（用的是badmonkey师傅的）：

我们拿3个状态序列进行验证

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
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

state1 = [114514, 3276889435, 1198910394, 2731152330, 1221055980, 2110667654, 2498345801, 2558461854, 712277140, 4004272749, 1197902704, 2284551328, 3209223670, 2016617809, 2421524638, 1142841755, 3312315346, 1447551622, 2823265877, 3227453286, 2419455981, 1652734048, 3370493787, 3700497871, 2395401620, 2428174919, 1507971667, 2816728181, 1763879439, 2517669283, 402993571, 1628557422, 1536926443, 2600239219, 1970415031, 1009862385, 3137271353, 3623467116, 3091344113, 3418094854, 45449249, 2685679150, 69921670, 2510529033, 2912145795, 3170283794, 696609662, 3768309477, 3955678958, 2268973234, 680943010, 1658626845, 1511675456, 1817432282, 2983434653, 2903159538, 596314344, 2348198849, 814882601, 2188524648, 4165767182, 1537657438, 129216185, 91484220, 334619628, 484194397, 60228083, 3426996258, 2114569801, 3236938413, 680062188, 1329841507, 1208766962, 3327942696, 1997927489, 1763679627, 3951952318, 3055539422, 2239543066, 2312639687, 2998968073, 2556994216, 1257973604, 2901317676, 2060757114, 3278719964, 3201451601, 3235719702, 1968822177, 3325473401, 3530404988, 1046031734, 1488786922, 4039207188, 288146801, 3463077620, 696952531, 717208736, 569838466, 3291356333, 1145859850, 2262938300, 182793052, 745373619, 577711367, 1143374636, 295687723, 2094629474, 4249644155, 1820001221, 1810391234, 3620440158, 97620513, 1573474422, 599617125, 445881164, 3379294576, 1509019092, 1616917119, 174807597, 47687993, 892617974, 2705382280, 2363062253, 243546311, 4261275136, 2740476589, 153906826, 2742384370, 3666763057, 241731388, 2722133807, 3245414981, 412668963, 247950677, 1736679440, 3557703741, 867337983, 883341861, 2993176100, 3882670986, 1546514074, 3708622517, 2655738973, 1656965387, 2959616899, 4108858231, 995189079, 1368651495, 650870611, 3031541589, 2751829226, 2772166688, 4039821315, 4245219482, 2167186936, 3712370238, 2415614894, 1676556154, 1359591206, 2716475907, 2274948102, 3054135862, 1012775719, 2352199175, 317881758, 1446452732, 280377976, 1450658304, 1706146830, 3039574421, 1818593342, 1739683975, 3056485259, 1193539259, 2270159377, 1426414895, 1581081047, 4235010080, 2721409410, 1997021236, 2363757214, 4130657346, 2721417052, 2209486, 4290993663, 1464070438, 3589080094, 2525046061, 1445122888, 835612043, 3252525974, 834936713, 1073726158, 1523194376, 2078938960, 4178349241, 1247350823, 2010232260, 2489721984, 224655890, 935545827, 1524526169, 4163098499, 4176971340, 2964407544, 4004512112, 3931905582, 2444819857, 1890891472, 1490614855, 2339648625, 672087347, 640184564, 3105039642, 1729067855, 960128158, 1010057519, 1405673317, 3649611599, 2542120408, 180175327, 1711559897, 50663959, 441414387, 2390844864, 416282732, 1894961023, 1430801306, 3409496076, 1558181329, 4153953271, 862424108, 387045957, 3149728547, 1987120624, 1218935297, 2690458349, 3841568825, 1063752145, 2577162597, 1755549076, 2321455547, 2007345136, 517094409, 458326402, 3355749184, 1548971366, 2219264411, 3853642582, 561337987, 2687253930, 1846230084, 798143798, 72705356, 1039836155, 4118873607, 3258680469, 1669961264, 2919201624, 3057964422, 1174921753, 667094142, 2434096317, 3376992099, 2354328041, 3982194113, 2808629397, 2334028703, 2486018814, 2803772026, 3706255975, 3735441028, 4048829268, 2640181605, 2791081398, 3187283224, 1420508759, 138780420, 2393694635, 1184332229, 3997757293, 4276770176, 2496387274, 417828868, 1602877105, 2235729038, 3691067483, 503993304, 3420040537, 2686226340, 1773044641, 799706948, 2949769977, 91162925, 3438458088, 3573556447, 4006365173, 1221921592, 429780904, 237532788, 1787220209, 596697054, 1460150725, 1285764996, 901649834, 1027376964, 4028678919, 1248204232, 1617832578, 1842078181, 3398378539, 1642769664, 1597164446, 1666936309, 311817855, 3884791895, 3894947425, 3042623464, 350745233, 776555893, 4153552234, 1893211311, 1566470121, 1333612492, 381694502, 1001660484, 2234589211, 1128139813, 1089867645, 197228854, 1168947609, 530551364, 2400655905, 1276054557, 875480155, 1610951735, 2754435231, 2996501571, 3119206392, 4017707254, 908998398, 3298533772, 2579842498, 627590680, 2588836049, 1840168857, 664924243, 3804577051, 3509253077, 1967766220, 1386834240, 2465288453, 1220720676, 2388751611, 2463852704, 2415721294, 543085153, 816179883, 2327321054, 3313299764, 2481101596, 2201764416, 2919855989, 854315615, 523753448, 4209727478, 3030307352, 4157525938, 3415518022, 2888990891, 3345364256, 2511844163, 3006169882, 1261015534, 3087563714, 2278724664, 3439167067, 1498618418, 4063470234, 781322457, 1346936858, 1326620453, 3011448499, 3805578837, 773261167, 2316916557, 3269573294, 3333438661, 3849843107, 3556832678, 2069444768, 3790111245, 79089423, 2924984693, 18734206, 2604232002, 4125055949, 4091705300, 1700550754, 2540755871, 1649978242, 895076161, 4141115192, 3282587355, 2340467917, 808656449, 2669853244, 2651892238, 4259808341, 4169350536, 2592320626, 1682635212, 31343742, 3066721620, 4093989517, 1227461030, 2347358084, 3292708736, 2808589138, 4123289652, 532909656, 867975774, 2707193533, 881539587, 386826200, 2047543778, 400188218, 1993945486, 3458143768, 4090834261, 3451382429, 2825920518, 91932485, 1828162795, 175756293, 1017795757, 1665072886, 185452585, 2175593188, 657966198, 2019404359, 3439175000, 2265772450, 1355412956, 3914090222, 3381121599, 1102843755, 3075985554, 3358743185, 5496668, 4012072207, 3776127872, 1193484148, 350488559, 1371474450, 3343394375, 4157439645, 3676800032, 4249018010, 1454421289, 2562843285, 3974248033, 1493690489, 1456402728, 3805485054, 3641302435, 2011107827, 1094359118, 2513002496, 1424094368, 91663964, 1067845668, 1608023053, 522149526, 4011366665, 3856710862, 2622436286, 3356690186, 461674860, 2472498556, 2815371927, 412650411, 1285201754, 3083178955, 327737650, 904043680, 1352232199, 1795832646, 1202938860, 29049707, 3789741602, 2252885489, 1373818316, 3409504463, 261949035, 2186267943, 1447542410, 1226019273, 2855570907, 3012827537, 3525493748, 307724649, 3869655396, 912846491, 2303989792, 805681508, 1144302191, 687742306, 1336478631, 1048014972, 4088774379, 2184608648, 543267187, 3083147105, 1643853586, 2652563331, 2265473258, 1216505230, 2125765234, 1628273767, 4037979207, 3572915422, 2733632060, 1018468994, 2877196631, 4257066391, 3435508083, 2953048896, 227233051, 1677058233, 3393987243, 1630377564, 352262598, 165290804, 2253568411, 3810860149, 152658599, 1398820093, 3642047879, 1642654512, 1629029746, 1559147389, 2694721035, 323615917, 421807970, 2704383436, 1588101737, 4145880364, 3009653936, 4003227232, 1731486262, 2746953947, 2817353926, 3675732862, 996892540, 3554282008, 4012601812, 1827732225, 3462793519, 3646827660, 3018399132, 858013576, 2953108187, 2465692369, 3424871028, 1592298025, 2328226815, 3679158793, 3014109739, 2387940711, 3787948052, 199416399, 1669163624, 2471243435, 1957026796, 3348929473, 2859616203, 704636303, 515381934, 3349915370, 2137689394, 2868839013, 1941312490, 3337330943, 1258381749, 4039172686, 3780083628, 3246066007, 3738477681, 1292100936, 2302445852, 4061473062, 2439056106, 1987540954, 1464041146, 3884979483, 717892813, 3378013239, 1793810139, 3029669978, 3544298769, 240194676, 2300258335, 4109982413, 2073760675, 2736681800, 96213137, 3293727893, 3750657935, 38682782, 902172345, 2819871329, 1881013876, 2587165583, 3400261128, 2783936447, 3708062970, 2299257255, 888427908, 2898617216, 1554962103, 3369868860, 1925228618]
state2 = [1300186559, 2421719561, 1949913479, 4078121321, 1556067905, 2787486266, 3136021751, 2526179473, 635316516, 1400921081, 2604074092, 3249849589, 418817570, 4037671367, 1636052064, 1190923301, 1795011901, 1004604065, 2485834046, 2554059407, 4205349812, 2033769714, 1344771434, 2997296894, 3465985956, 3326352296, 732242008, 3641892827, 2232321494, 2936087020, 659720973, 3256635428, 1516889854, 275025745, 1252522298, 738716613, 1854282611, 2849909068, 1873029766, 3841467490, 1932846561, 1226358250, 309693247, 3908476008, 640086734, 2554269927, 776579599, 623549099, 2865930935, 2647457006, 3923439162, 2589653938, 4263228156, 2175968077, 3114665078, 2966857716, 3687905867, 3584407716, 1350964262, 3144576576, 2585664434, 1106699171, 4294649476, 1598571743, 262622820, 1948321351, 2133196904, 2965545683, 1538016887, 2370677717, 3379970973, 1698476215, 3068612628, 3059990111, 2834419782, 174131451, 81237602, 1570833691, 855385013, 629687189, 3497747178, 2909705400, 234083706, 3996451137, 2256113529, 3740866652, 754190929, 1415694532, 2845509841, 1557415582, 263584700, 1196732851, 2144589670, 3492122892, 3336040792, 1267052103, 1153242012, 3687017742, 3028465890, 3765041826, 1429694420, 207685735, 621445853, 1001078733, 4029776482, 2207308451, 3637149781, 2445699193, 1717643549, 99715333, 1875996224, 4078855341, 1632478108, 3064035217, 4277957453, 2793636656, 1285128089, 519945857, 4257622747, 108626880, 2643608209, 1478625354, 2714800475, 3209154779, 3461373767, 475185495, 3866746233, 755900923, 1597052688, 3129601545, 1156397627, 1236520637, 3637483477, 4255049420, 4186829475, 3525445277, 3559844454, 2323762937, 2674304649, 2425582000, 1729074666, 3840833400, 255337334, 2306998122, 3760562284, 3214023193, 1681796735, 2726868737, 2471053332, 576847545, 212486172, 2776688956, 1376680046, 2417496621, 664940746, 3440907204, 3759195409, 2866815171, 334464239, 1512549318, 2900822999, 938855962, 155214947, 1179600720, 4203750227, 406827382, 3093284839, 3117211601, 4277910643, 3715507772, 4244058080, 1906019989, 834157361, 1959550693, 2070462915, 4167615495, 3580586588, 2910502587, 633302829, 3155725275, 2885701252, 1390776238, 1336072448, 2277211533, 3649278738, 3244227318, 1497403877, 346260150, 537921553, 1898931284, 3248599655, 9549388, 3240838422, 1617356876, 3033105076, 1469833125, 1833251366, 1302310200, 1567649018, 2703353874, 2820880867, 2101338820, 3488744901, 3371096956, 2333677421, 2030638284, 4231341832, 623744218, 62998731, 377142964, 2567877238, 157115091, 3432663029, 516411923, 3746104257, 3029262382, 4144983612, 718920930, 2137472368, 3995969875, 22191306, 587299604, 2893966416, 954886694, 1542349911, 2226905610, 3551625002, 1742430322, 3049580047, 2203982768, 1373086797, 84701271, 883292103, 1044238777, 3987404393, 2558862587, 3668343376, 1883466927, 118471874, 2368742991, 2230861581, 4255371362, 1026482141, 4238089190, 910805600, 2955445406, 4128402492, 1636016038, 199240025, 2576715508, 2729508907, 3113427334, 3515695411, 697275134, 1592213241, 650556938, 1460949881, 1452687381, 3571707272, 21728317, 3933195906, 1497792261, 3179672900, 2469055517, 1996259687, 2147557561, 776253687, 2947771633, 51276949, 1106943490, 529158532, 1232459148, 3767864653, 4193248866, 1980029040, 4096763963, 1855050522, 3992461752, 67386296, 72924865, 798909476, 3335728822, 4206054289, 2544054857, 1667887907, 1378309729, 1281770162, 3575329374, 4245849552, 2952094038, 2996286928, 410126790, 4206969828, 2761503777, 2528901287, 2820990151, 1663252720, 2904344065, 1777485667, 2985519918, 438855416, 3107569577, 3102582982, 579210656, 1199443918, 744644631, 2224067273, 3041421326, 2639888889, 2719913303, 1383736203, 4136425977, 4049632659, 2219904116, 3290661668, 55911461, 2982732145, 1427678280, 2486171684, 4060070147, 3958147001, 666062800, 4230097260, 1661187194, 3500373021, 2841159872, 2079971952, 2912997657, 3037904646, 552222278, 2155205598, 4294855488, 487843692, 667268740, 316258955, 3479900121, 2398066069, 2945753278, 2951463761, 384896999, 3988155630, 3702629259, 3932234193, 506289301, 2329038390, 303678920, 2359413558, 905473219, 2847916415, 3681831997, 2517853307, 1579173658, 2016648517, 2017581019, 1684247979, 416246455, 1940797414, 3317137329, 1290781266, 3128029007, 3027217218, 3088307075, 472780280, 341029782, 2233083149, 2719157618, 3403421884, 485028403, 2166629083, 3223966716, 3929204218, 871811346, 3859110804, 27977352, 3196881632, 3500147208, 3709308235, 1610859781, 2627287153, 2622475485, 3090956832, 2569260935, 1303323714, 141702884, 1692603307, 2414583702, 995587729, 1454876010, 3695609364, 1665146544, 1004788480, 1399640714, 3278661166, 914140034, 4181864942, 4083616466, 1049705221, 2231768074, 53846692, 2735269409, 98568996, 4174156476, 3271751579, 767032814, 1907512322, 3836629202, 3012155077, 3808959363, 3038707035, 870533060, 3405425588, 2879844340, 3249658057, 1109764943, 4155087663, 1149550786, 1960546198, 2743135655, 1394762725, 3150541068, 797388640, 2904007579, 3728560164, 2919768056, 1176015572, 1618339851, 2865551759, 2471469348, 1513122248, 789586864, 926785261, 3743483758, 2730280881, 1397117346, 3105476103, 2224869954, 669368783, 92333757, 160110497, 2667685326, 3152132079, 4181184877, 4144535807, 2674627794, 511704981, 2192336048, 402333241, 452555907, 3725649539, 3965158398, 2524148862, 728233367, 3878317488, 1087097858, 1325720955, 258491891, 1638929441, 1011115613, 2074943258, 3337952652, 2874511404, 47406470, 1829658648, 4055958212, 1093330768, 4068729548, 1876369001, 2758112042, 4148650082, 1465787789, 4263988424, 698011250, 114035271, 4187865975, 3473368061, 2031122238, 3618772779, 3333981102, 4098977072, 3626167181, 3814766442, 2342767603, 9173415, 3590203971, 525480076, 3457328088, 2953808481, 3756708641, 2057293555, 609281070, 2749080332, 2899318592, 3908060767, 2463134799, 1903517467, 2602646233, 718881095, 2718640575, 3311870910, 542617946, 2432599960, 2787616795, 3346827401, 2897024136, 3914476968, 1543956234, 3209321257, 1004628629, 2014256058, 3850957743, 930176483, 577949415, 2602510855, 3465312733, 2783357399, 1796687566, 3966849315, 3604383511, 656950527, 1397705992, 96916189, 4240496328, 4182970841, 1031370161, 564867701, 2384732535, 1318650696, 1110024024, 1727310331, 270526533, 2661854250, 938001632, 639495412, 2155709267, 795444252, 1975762716, 2140837083, 3804411178, 1125054437, 2173962251, 3034418893, 1935436357, 2316469247, 1633988600, 1502251001, 2226599618, 128135400, 3496085807, 2114099592, 2339117660, 278496609, 1484151983, 4205714595, 376588239, 4027940519, 2634005002, 1467975340, 1862606465, 1103494920, 1908207914, 2117154890, 1263248719, 1315033707, 1587320866, 3380941188, 1503082138, 2325433031, 421207349, 476759617, 876813245, 1859034271, 1445696462, 598175996, 470772924, 1336574261, 326712384, 390455047, 1541678691, 1367099981, 1541819952, 133468482, 3893666886, 1628726082, 3386070854, 960462772, 1955574645, 3403042969, 1306173238, 1316041060, 2058354524, 281933592, 4228952478, 3936585735, 2984747857, 927550830, 736401545, 205813061, 1469474622, 3750483616, 4233091001, 4043476191, 4188274906, 1294280408, 1046712562, 2227633163, 2367029717, 1201238090, 52286645, 1877754015, 210240525, 2342093159, 3923921476, 4159004844, 2940553097, 870468206, 398035220, 230840525, 3866008332, 152500296, 3574519790, 3240325126, 3710664432, 2315738871, 2166761733]
state3 = [337831377, 3760306872, 59362890, 4072104155, 3957213089, 125809983, 4294342009, 593313936, 1416023537, 3188872435, 450545958, 4184190538, 2461993976, 3124280708, 298867001, 1841803912, 3336412864, 4257018800, 2442239322, 160418380, 3743187934, 2066852176, 2728066675, 1221357746, 3459624527, 2347745288, 462012618, 77582399, 938834173, 1617767638, 2990639414, 923048631, 3190478023, 309224048, 1344946771, 217545431, 1202275588, 3469466436, 3068182643, 3346465760, 554481736, 2579063521, 2876959738, 3908226696, 1814096321, 958725415, 351693144, 2451447313, 3427408583, 1662413092, 1473513818, 2703048701, 897999495, 3399513669, 1930208877, 332046410, 706285648, 659025768, 316633811, 750721528, 3317147475, 1146129496, 811175740, 2894477086, 2714463866, 1386045484, 1890116466, 3052696756, 1831700473, 2456063864, 1341365166, 3962882152, 2506574461, 2858394859, 4121098960, 78102902, 1313206565, 1332855544, 4074563115, 4287604318, 2416953842, 2997389197, 1982913522, 961855497, 3839838173, 3489221712, 4291743265, 2459370555, 2692251799, 3084220351, 1699232551, 1165370688, 205663400, 3232783264, 1343910076, 3400454033, 3207709384, 724829034, 3944073096, 1078129325, 1026760019, 1324012047, 2760547939, 2833663657, 2129098133, 840005756, 2101776491, 57281017, 3354825559, 2292378633, 2607212572, 145345140, 1741748408, 3506951322, 1899171711, 1683694868, 1492784706, 34409573, 673941294, 2075181236, 3133637426, 2932391053, 2514752954, 4226174369, 736167612, 1399279546, 4076262803, 238270973, 174614188, 3051826826, 4294494425, 3550204622, 1859164963, 2070341028, 3354490737, 1275763143, 1547031792, 4191315847, 1032456132, 203251246, 3501559446, 76736094, 2236938174, 3301924603, 3047020438, 1627726879, 3911730343, 271459315, 1284471105, 32904422, 3265428913, 386246079, 443065237, 1128832260, 2130335053, 330223348, 3658147697, 552209423, 2985062377, 3624186776, 889190796, 3698163174, 1385910914, 3664877884, 122977780, 3410395463, 2607957781, 804290402, 925640068, 4108377399, 4175325856, 2646502150, 2536342544, 3396488353, 4078387474, 1225967058, 3552215870, 2222818940, 2491271538, 1095104581, 848748980, 1991059149, 3241361449, 1798658251, 2294012221, 2495388527, 3280115229, 2956970851, 1276641631, 1930312053, 227689488, 1860473839, 178031482, 178861634, 248901267, 3691057428, 2536011213, 435256083, 997485696, 3244120427, 688494172, 1635411101, 2553854471, 763803574, 2233502396, 1933555036, 1828018847, 472836273, 2250989199, 1260267889, 3736851715, 3500790714, 3672333787, 1026928728, 3013950035, 2355287986, 4197034488, 206689494, 3114790242, 1298863784, 4159579782, 522833504, 2306597629, 1977414386, 3748777973, 3823100258, 4073429308, 2546476553, 2710484832, 4067077299, 1765402671, 1753484445, 2171202876, 1345044114, 4128727602, 959836377, 1597723259, 425531207, 1727335858, 1238082721, 3303626165, 3595535880, 1401536379, 2650373104, 3853038079, 3935873860, 2035156383, 1139025837, 2012966442, 1791676089, 335929457, 1073462793, 3743943031, 2918379369, 402426682, 2239226270, 3526278147, 2553315314, 4004113526, 2333946758, 3888508205, 1323874545, 3697978374, 2782901608, 1472461767, 2026514647, 1235617095, 4186128093, 3108253152, 2764030776, 3427279950, 3311591352, 1171459606, 1878263136, 822180563, 3137532746, 1441430008, 366351494, 976867394, 575230101, 3922321694, 2539500410, 3239283121, 3265616158, 2539451527, 887903114, 103973079, 3141461435, 329923827, 1762809300, 3770627069, 2628505480, 2581154531, 2734534654, 2028910088, 482089857, 501374119, 2718042304, 4107107839, 3631446273, 801885152, 2849255091, 1441056678, 1845163714, 3225961004, 1771839376, 2771096153, 1202436561, 2058321401, 2248506088, 2602179626, 90687947, 2379336298, 2648641459, 1244997366, 563364080, 3713607067, 1868547893, 2759947550, 3770474411, 2473196616, 1846240266, 3140425132, 241747993, 2140690186, 2531863216, 3482987262, 1740260048, 513789228, 2763028364, 3608765193, 812549667, 569615166, 3978493425, 3185000138, 428468546, 3748183126, 1436268907, 3671719256, 1359728335, 643282304, 2634755912, 2990881665, 1569927513, 1258417793, 779838133, 3091482122, 923849554, 1517955660, 1206196056, 2499178028, 2398124225, 4132377736, 1506783129, 2606546041, 868187487, 238297485, 2576296432, 1470862774, 887574146, 3194469562, 2313580941, 1176715276, 3350230697, 2832982334, 1491340186, 3680606184, 1227829028, 1686507424, 4031612227, 2637445746, 2258598492, 567301979, 4134404567, 2021532407, 3138129723, 3909043899, 1441157462, 3224040206, 1182171781, 2530331160, 405653356, 395826566, 1903419003, 656393156, 1968137342, 4083114285, 450673286, 2915922622, 1332395778, 4089966713, 652365539, 2423837830, 2815647714, 1447295499, 4050389209, 4133738290, 3108289522, 355641545, 3588063618, 4128507391, 194939392, 533281573, 3949177151, 3056250389, 1420923599, 2848539995, 4044435398, 794592559, 3830322675, 1055272753, 1902871942, 1822883351, 1633610581, 3531451138, 1987430036, 4224122745, 4245407037, 1929390953, 1566514378, 2234144592, 1640711809, 2332368616, 4096015527, 2965585865, 3071979672, 2298120697, 1142006456, 1995601221, 447661486, 35009537, 1299601851, 446471565, 3916500291, 1583382928, 1288769207, 3503745776, 1131867660, 3744006493, 505100019, 3634817073, 1361692403, 3285655003, 740222701, 218621582, 1800589985, 3642694710, 1106175256, 1761742751, 3259128002, 3110582502, 3974428973, 2210006883, 1279351646, 158643247, 140381615, 1967140674, 1424975778, 1274970715, 3569558826, 289542225, 3230683710, 30765499, 1068376531, 538764833, 2283156057, 1543052596, 3209356676, 619193361, 1822038303, 3375635657, 2143683587, 1331624480, 2277835966, 1064049714, 3307918688, 160862062, 1848465129, 3403840272, 2929218242, 1898691151, 3467757366, 914375776, 2642912325, 3208195614, 799447449, 2111892169, 58899083, 1556138726, 3448208768, 4088905416, 3132319799, 2829754927, 2819889685, 1830490990, 1965047196, 749922104, 2935731601, 2504591125, 1303137754, 2783928754, 3417804360, 3981736206, 558067500, 2077583107, 3163835657, 3870381312, 3587075267, 1016167026, 61052831, 1251249842, 64737627, 3399671739, 3452527843, 3467986652, 3164218557, 2607916672, 706978141, 3037489420, 36868946, 2627585178, 2639236667, 3674739078, 2487186754, 1008248996, 2474769499, 4184323757, 2243506114, 953379406, 1521521075, 906925234, 3544626262, 4037701350, 4070527063, 2102027871, 3697968971, 3076792445, 1670764295, 2628091153, 1320664531, 2105117262, 3593787350, 1361450764, 1754584760, 1829002324, 3880840554, 1367698403, 3966283916, 1807575332, 1785423811, 3143325329, 3687311748, 1155053960, 1855464818, 700817365, 1965035130, 171591699, 4160461965, 145817270, 518733595, 1368366985, 66021152, 919053651, 4222235796, 961552934, 1184688356, 2223960202, 2976540287, 505549385, 472565009, 1988556990, 1523734271, 545051883, 110736975, 1051479410, 3369104656, 4078941366, 625015765, 2734907353, 4122303529, 1841692090, 3956706776, 391567100, 1386978903, 985677973, 3955756325, 1376387353, 2573149192, 3031535139, 1313192832, 4189597286, 1149408738, 2568973037, 2160406879, 3319124927, 4222387677, 3683038940, 3002192162, 1638932831, 3227099627, 2327577018, 518828443, 2755512130, 1939114081, 2321932643, 2749778731, 3740325888, 942627464, 2271311285, 2337514986, 92470105, 1559065490, 3152377701, 2863547418, 285244940, 841281031, 2086531716, 3075247197, 207955220, 4041829509, 3376758938, 2320033199, 687320196, 628757765]

recover_state1 = backtrace(state2)
recover_state2 = backtrace(state3)

print(recover_state1)
print(recover_state2)

运行结果：

1
2
[1642261423, 3276889435, 1198910394, 2731152330, 1221055980, 2110667654, 2498345801, 2558461854, 712277140, 4004272749, 1197902704, 2284551328, 3209223670, 2016617809, 2421524638, 1142841755, 3312315346, 1447551622, 2823265877, 3227453286, 2419455981, 1652734048, 3370493787, 3700497871, 2395401620, 2428174919, 1507971667, 2816728181, 1763879439, 2517669283, 402993571, 1628557422, 1536926443, 2600239219, 1970415031, 1009862385, 3137271353, 3623467116, 3091344113, 3418094854, 45449249, 2685679150, 69921670, 2510529033, 2912145795, 3170283794, 696609662, 3768309477, 3955678958, 2268973234, 680943010, 1658626845, 1511675456, 1817432282, 2983434653, 2903159538, 596314344, 2348198849, 814882601, 2188524648, 4165767182, 1537657438, 129216185, 91484220, 334619628, 484194397, 60228083, 3426996258, 2114569801, 3236938413, 680062188, 1329841507, 1208766962, 3327942696, 1997927489, 1763679627, 3951952318, 3055539422, 2239543066, 2312639687, 2998968073, 2556994216, 1257973604, 2901317676, 2060757114, 3278719964, 3201451601, 3235719702, 1968822177, 3325473401, 3530404988, 1046031734, 1488786922, 4039207188, 288146801, 3463077620, 696952531, 717208736, 569838466, 3291356333, 1145859850, 2262938300, 182793052, 745373619, 577711367, 1143374636, 295687723, 2094629474, 4249644155, 1820001221, 1810391234, 3620440158, 97620513, 1573474422, 599617125, 445881164, 3379294576, 1509019092, 1616917119, 174807597, 47687993, 892617974, 2705382280, 2363062253, 243546311, 4261275136, 2740476589, 153906826, 2742384370, 3666763057, 241731388, 2722133807, 3245414981, 412668963, 247950677, 1736679440, 3557703741, 867337983, 883341861, 2993176100, 3882670986, 1546514074, 3708622517, 2655738973, 1656965387, 2959616899, 4108858231, 995189079, 1368651495, 650870611, 3031541589, 2751829226, 2772166688, 4039821315, 4245219482, 2167186936, 3712370238, 2415614894, 1676556154, 1359591206, 2716475907, 2274948102, 3054135862, 1012775719, 2352199175, 317881758, 1446452732, 280377976, 1450658304, 1706146830, 3039574421, 1818593342, 1739683975, 3056485259, 1193539259, 2270159377, 1426414895, 1581081047, 4235010080, 2721409410, 1997021236, 2363757214, 4130657346, 2721417052, 2209486, 4290993663, 1464070438, 3589080094, 2525046061, 1445122888, 835612043, 3252525974, 834936713, 1073726158, 1523194376, 2078938960, 4178349241, 1247350823, 2010232260, 2489721984, 224655890, 935545827, 1524526169, 4163098499, 4176971340, 2964407544, 4004512112, 3931905582, 2444819857, 1890891472, 1490614855, 2339648625, 672087347, 640184564, 3105039642, 1729067855, 960128158, 1010057519, 1405673317, 3649611599, 2542120408, 180175327, 1711559897, 50663959, 441414387, 2390844864, 416282732, 1894961023, 1430801306, 3409496076, 1558181329, 4153953271, 862424108, 387045957, 3149728547, 1987120624, 1218935297, 2690458349, 3841568825, 1063752145, 2577162597, 1755549076, 2321455547, 2007345136, 517094409, 458326402, 3355749184, 1548971366, 2219264411, 3853642582, 561337987, 2687253930, 1846230084, 798143798, 72705356, 1039836155, 4118873607, 3258680469, 1669961264, 2919201624, 3057964422, 1174921753, 667094142, 2434096317, 3376992099, 2354328041, 3982194113, 2808629397, 2334028703, 2486018814, 2803772026, 3706255975, 3735441028, 4048829268, 2640181605, 2791081398, 3187283224, 1420508759, 138780420, 2393694635, 1184332229, 3997757293, 4276770176, 2496387274, 417828868, 1602877105, 2235729038, 3691067483, 503993304, 3420040537, 2686226340, 1773044641, 799706948, 2949769977, 91162925, 3438458088, 3573556447, 4006365173, 1221921592, 429780904, 237532788, 1787220209, 596697054, 1460150725, 1285764996, 901649834, 1027376964, 4028678919, 1248204232, 1617832578, 1842078181, 3398378539, 1642769664, 1597164446, 1666936309, 311817855, 3884791895, 3894947425, 3042623464, 350745233, 776555893, 4153552234, 1893211311, 1566470121, 1333612492, 381694502, 1001660484, 2234589211, 1128139813, 1089867645, 197228854, 1168947609, 530551364, 2400655905, 1276054557, 875480155, 1610951735, 2754435231, 2996501571, 3119206392, 4017707254, 908998398, 3298533772, 2579842498, 627590680, 2588836049, 1840168857, 664924243, 3804577051, 3509253077, 1967766220, 1386834240, 2465288453, 1220720676, 2388751611, 2463852704, 2415721294, 543085153, 816179883, 2327321054, 3313299764, 2481101596, 2201764416, 2919855989, 854315615, 523753448, 4209727478, 3030307352, 4157525938, 3415518022, 2888990891, 3345364256, 2511844163, 3006169882, 1261015534, 3087563714, 2278724664, 3439167067, 1498618418, 4063470234, 781322457, 1346936858, 1326620453, 3011448499, 3805578837, 773261167, 2316916557, 3269573294, 3333438661, 3849843107, 3556832678, 2069444768, 3790111245, 79089423, 2924984693, 18734206, 2604232002, 4125055949, 4091705300, 1700550754, 2540755871, 1649978242, 895076161, 4141115192, 3282587355, 2340467917, 808656449, 2669853244, 2651892238, 4259808341, 4169350536, 2592320626, 1682635212, 31343742, 3066721620, 4093989517, 1227461030, 2347358084, 3292708736, 2808589138, 4123289652, 532909656, 867975774, 2707193533, 881539587, 386826200, 2047543778, 400188218, 1993945486, 3458143768, 4090834261, 3451382429, 2825920518, 91932485, 1828162795, 175756293, 1017795757, 1665072886, 185452585, 2175593188, 657966198, 2019404359, 3439175000, 2265772450, 1355412956, 3914090222, 3381121599, 1102843755, 3075985554, 3358743185, 5496668, 4012072207, 3776127872, 1193484148, 350488559, 1371474450, 3343394375, 4157439645, 3676800032, 4249018010, 1454421289, 2562843285, 3974248033, 1493690489, 1456402728, 3805485054, 3641302435, 2011107827, 1094359118, 2513002496, 1424094368, 91663964, 1067845668, 1608023053, 522149526, 4011366665, 3856710862, 2622436286, 3356690186, 461674860, 2472498556, 2815371927, 412650411, 1285201754, 3083178955, 327737650, 904043680, 1352232199, 1795832646, 1202938860, 29049707, 3789741602, 2252885489, 1373818316, 3409504463, 261949035, 2186267943, 1447542410, 1226019273, 2855570907, 3012827537, 3525493748, 307724649, 3869655396, 912846491, 2303989792, 805681508, 1144302191, 687742306, 1336478631, 1048014972, 4088774379, 2184608648, 543267187, 3083147105, 1643853586, 2652563331, 2265473258, 1216505230, 2125765234, 1628273767, 4037979207, 3572915422, 2733632060, 1018468994, 2877196631, 4257066391, 3435508083, 2953048896, 227233051, 1677058233, 3393987243, 1630377564, 352262598, 165290804, 2253568411, 3810860149, 152658599, 1398820093, 3642047879, 1642654512, 1629029746, 1559147389, 2694721035, 323615917, 421807970, 2704383436, 1588101737, 4145880364, 3009653936, 4003227232, 1731486262, 2746953947, 2817353926, 3675732862, 996892540, 3554282008, 4012601812, 1827732225, 3462793519, 3646827660, 3018399132, 858013576, 2953108187, 2465692369, 3424871028, 1592298025, 2328226815, 3679158793, 3014109739, 2387940711, 3787948052, 199416399, 1669163624, 2471243435, 1957026796, 3348929473, 2859616203, 704636303, 515381934, 3349915370, 2137689394, 2868839013, 1941312490, 3337330943, 1258381749, 4039172686, 3780083628, 3246066007, 3738477681, 1292100936, 2302445852, 4061473062, 2439056106, 1987540954, 1464041146, 3884979483, 717892813, 3378013239, 1793810139, 3029669978, 3544298769, 240194676, 2300258335, 4109982413, 2073760675, 2736681800, 96213137, 3293727893, 3750657935, 38682782, 902172345, 2819871329, 1881013876, 2587165583, 3400261128, 2783936447, 3708062970, 2299257255, 888427908, 2898617216, 1554962103, 3369868860, 1925228618]
[1300186559, 2421719561, 1949913479, 4078121321, 1556067905, 2787486266, 3136021751, 2526179473, 635316516, 1400921081, 2604074092, 3249849589, 418817570, 4037671367, 1636052064, 1190923301, 1795011901, 1004604065, 2485834046, 2554059407, 4205349812, 2033769714, 1344771434, 2997296894, 3465985956, 3326352296, 732242008, 3641892827, 2232321494, 2936087020, 659720973, 3256635428, 1516889854, 275025745, 1252522298, 738716613, 1854282611, 2849909068, 1873029766, 3841467490, 1932846561, 1226358250, 309693247, 3908476008, 640086734, 2554269927, 776579599, 623549099, 2865930935, 2647457006, 3923439162, 2589653938, 4263228156, 2175968077, 3114665078, 2966857716, 3687905867, 3584407716, 1350964262, 3144576576, 2585664434, 1106699171, 4294649476, 1598571743, 262622820, 1948321351, 2133196904, 2965545683, 1538016887, 2370677717, 3379970973, 1698476215, 3068612628, 3059990111, 2834419782, 174131451, 81237602, 1570833691, 855385013, 629687189, 3497747178, 2909705400, 234083706, 3996451137, 2256113529, 3740866652, 754190929, 1415694532, 2845509841, 1557415582, 263584700, 1196732851, 2144589670, 3492122892, 3336040792, 1267052103, 1153242012, 3687017742, 3028465890, 3765041826, 1429694420, 207685735, 621445853, 1001078733, 4029776482, 2207308451, 3637149781, 2445699193, 1717643549, 99715333, 1875996224, 4078855341, 1632478108, 3064035217, 4277957453, 2793636656, 1285128089, 519945857, 4257622747, 108626880, 2643608209, 1478625354, 2714800475, 3209154779, 3461373767, 475185495, 3866746233, 755900923, 1597052688, 3129601545, 1156397627, 1236520637, 3637483477, 4255049420, 4186829475, 3525445277, 3559844454, 2323762937, 2674304649, 2425582000, 1729074666, 3840833400, 255337334, 2306998122, 3760562284, 3214023193, 1681796735, 2726868737, 2471053332, 576847545, 212486172, 2776688956, 1376680046, 2417496621, 664940746, 3440907204, 3759195409, 2866815171, 334464239, 1512549318, 2900822999, 938855962, 155214947, 1179600720, 4203750227, 406827382, 3093284839, 3117211601, 4277910643, 3715507772, 4244058080, 1906019989, 834157361, 1959550693, 2070462915, 4167615495, 3580586588, 2910502587, 633302829, 3155725275, 2885701252, 1390776238, 1336072448, 2277211533, 3649278738, 3244227318, 1497403877, 346260150, 537921553, 1898931284, 3248599655, 9549388, 3240838422, 1617356876, 3033105076, 1469833125, 1833251366, 1302310200, 1567649018, 2703353874, 2820880867, 2101338820, 3488744901, 3371096956, 2333677421, 2030638284, 4231341832, 623744218, 62998731, 377142964, 2567877238, 157115091, 3432663029, 516411923, 3746104257, 3029262382, 4144983612, 718920930, 2137472368, 3995969875, 22191306, 587299604, 2893966416, 954886694, 1542349911, 2226905610, 3551625002, 1742430322, 3049580047, 2203982768, 1373086797, 84701271, 883292103, 1044238777, 3987404393, 2558862587, 3668343376, 1883466927, 118471874, 2368742991, 2230861581, 4255371362, 1026482141, 4238089190, 910805600, 2955445406, 4128402492, 1636016038, 199240025, 2576715508, 2729508907, 3113427334, 3515695411, 697275134, 1592213241, 650556938, 1460949881, 1452687381, 3571707272, 21728317, 3933195906, 1497792261, 3179672900, 2469055517, 1996259687, 2147557561, 776253687, 2947771633, 51276949, 1106943490, 529158532, 1232459148, 3767864653, 4193248866, 1980029040, 4096763963, 1855050522, 3992461752, 67386296, 72924865, 798909476, 3335728822, 4206054289, 2544054857, 1667887907, 1378309729, 1281770162, 3575329374, 4245849552, 2952094038, 2996286928, 410126790, 4206969828, 2761503777, 2528901287, 2820990151, 1663252720, 2904344065, 1777485667, 2985519918, 438855416, 3107569577, 3102582982, 579210656, 1199443918, 744644631, 2224067273, 3041421326, 2639888889, 2719913303, 1383736203, 4136425977, 4049632659, 2219904116, 3290661668, 55911461, 2982732145, 1427678280, 2486171684, 4060070147, 3958147001, 666062800, 4230097260, 1661187194, 3500373021, 2841159872, 2079971952, 2912997657, 3037904646, 552222278, 2155205598, 4294855488, 487843692, 667268740, 316258955, 3479900121, 2398066069, 2945753278, 2951463761, 384896999, 3988155630, 3702629259, 3932234193, 506289301, 2329038390, 303678920, 2359413558, 905473219, 2847916415, 3681831997, 2517853307, 1579173658, 2016648517, 2017581019, 1684247979, 416246455, 1940797414, 3317137329, 1290781266, 3128029007, 3027217218, 3088307075, 472780280, 341029782, 2233083149, 2719157618, 3403421884, 485028403, 2166629083, 3223966716, 3929204218, 871811346, 3859110804, 27977352, 3196881632, 3500147208, 3709308235, 1610859781, 2627287153, 2622475485, 3090956832, 2569260935, 1303323714, 141702884, 1692603307, 2414583702, 995587729, 1454876010, 3695609364, 1665146544, 1004788480, 1399640714, 3278661166, 914140034, 4181864942, 4083616466, 1049705221, 2231768074, 53846692, 2735269409, 98568996, 4174156476, 3271751579, 767032814, 1907512322, 3836629202, 3012155077, 3808959363, 3038707035, 870533060, 3405425588, 2879844340, 3249658057, 1109764943, 4155087663, 1149550786, 1960546198, 2743135655, 1394762725, 3150541068, 797388640, 2904007579, 3728560164, 2919768056, 1176015572, 1618339851, 2865551759, 2471469348, 1513122248, 789586864, 926785261, 3743483758, 2730280881, 1397117346, 3105476103, 2224869954, 669368783, 92333757, 160110497, 2667685326, 3152132079, 4181184877, 4144535807, 2674627794, 511704981, 2192336048, 402333241, 452555907, 3725649539, 3965158398, 2524148862, 728233367, 3878317488, 1087097858, 1325720955, 258491891, 1638929441, 1011115613, 2074943258, 3337952652, 2874511404, 47406470, 1829658648, 4055958212, 1093330768, 4068729548, 1876369001, 2758112042, 4148650082, 1465787789, 4263988424, 698011250, 114035271, 4187865975, 3473368061, 2031122238, 3618772779, 3333981102, 4098977072, 3626167181, 3814766442, 2342767603, 9173415, 3590203971, 525480076, 3457328088, 2953808481, 3756708641, 2057293555, 609281070, 2749080332, 2899318592, 3908060767, 2463134799, 1903517467, 2602646233, 718881095, 2718640575, 3311870910, 542617946, 2432599960, 2787616795, 3346827401, 2897024136, 3914476968, 1543956234, 3209321257, 1004628629, 2014256058, 3850957743, 930176483, 577949415, 2602510855, 3465312733, 2783357399, 1796687566, 3966849315, 3604383511, 656950527, 1397705992, 96916189, 4240496328, 4182970841, 1031370161, 564867701, 2384732535, 1318650696, 1110024024, 1727310331, 270526533, 2661854250, 938001632, 639495412, 2155709267, 795444252, 1975762716, 2140837083, 3804411178, 1125054437, 2173962251, 3034418893, 1935436357, 2316469247, 1633988600, 1502251001, 2226599618, 128135400, 3496085807, 2114099592, 2339117660, 278496609, 1484151983, 4205714595, 376588239, 4027940519, 2634005002, 1467975340, 1862606465, 1103494920, 1908207914, 2117154890, 1263248719, 1315033707, 1587320866, 3380941188, 1503082138, 2325433031, 421207349, 476759617, 876813245, 1859034271, 1445696462, 598175996, 470772924, 1336574261, 326712384, 390455047, 1541678691, 1367099981, 1541819952, 133468482, 3893666886, 1628726082, 3386070854, 960462772, 1955574645, 3403042969, 1306173238, 1316041060, 2058354524, 281933592, 4228952478, 3936585735, 2984747857, 927550830, 736401545, 205813061, 1469474622, 3750483616, 4233091001, 4043476191, 4188274906, 1294280408, 1046712562, 2227633163, 2367029717, 1201238090, 52286645, 1877754015, 210240525, 2342093159, 3923921476, 4159004844, 2940553097, 870468206, 398035220, 230840525, 3866008332, 152500296, 3574519790, 3240325126, 3710664432, 2315738871, 2166761733]

从运行结果会发现，除了无法恢复seed，其他的状态是完全可以恢复的

逆向 init 函数

分析可见文末xenny师傅博客，代码实现：

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
from gmpy2 import invert

def _int32(x):
    return int(0xFFFFFFFF & x)

def init(seed):
    mt = [0] * 624
    mt[0] = seed
    for i in range(1, 624):
        mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
    return mt

seed = 3989032602

def invert_right(res,shift):
    tmp = res
    for i in range(32//shift):
        res = tmp^res>>shift
    return _int32(res)

def recover(last):
    n = 1<<32
    inv = invert(1812433253,n)
    for i in range(623,0,-1):
        last = ((last-i)*inv)%n
        last = invert_right(last,30)
    return last

state = init(seed)

print(recover(state[-1]) == seed)

这里的state = init(seed)，其实索引为0的那个值就是seed，根本不需要调用recover

于是我用上面通过逆向twist的state进行验证

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
from gmpy2 import invert

def _int32(x):
    return int(0xFFFFFFFF & x)

def init(seed):
    mt = [0] * 624
    mt[0] = seed
    for i in range(1, 624):
        mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
    return mt

def invert_right(res,shift):
    tmp = res
    for i in range(32//shift):
        res = tmp^res>>shift
    return _int32(res)

def recover(last):
    n = 1<<32
    inv = invert(1812433253,n)
    for i in range(623,0,-1):
        last = ((last-i)*inv)%n
        last = invert_right(last,30)
    return last

state = [1642261423, 3276889435, 1198910394, 2731152330, 1221055980, 2110667654, 2498345801, 2558461854, 712277140, 4004272749, 1197902704, 2284551328, 3209223670, 2016617809, 2421524638, 1142841755, 3312315346, 1447551622, 2823265877, 3227453286, 2419455981, 1652734048, 3370493787, 3700497871, 2395401620, 2428174919, 1507971667, 2816728181, 1763879439, 2517669283, 402993571, 1628557422, 1536926443, 2600239219, 1970415031, 1009862385, 3137271353, 3623467116, 3091344113, 3418094854, 45449249, 2685679150, 69921670, 2510529033, 2912145795, 3170283794, 696609662, 3768309477, 3955678958, 2268973234, 680943010, 1658626845, 1511675456, 1817432282, 2983434653, 2903159538, 596314344, 2348198849, 814882601, 2188524648, 4165767182, 1537657438, 129216185, 91484220, 334619628, 484194397, 60228083, 3426996258, 2114569801, 3236938413, 680062188, 1329841507, 1208766962, 3327942696, 1997927489, 1763679627, 3951952318, 3055539422, 2239543066, 2312639687, 2998968073, 2556994216, 1257973604, 2901317676, 2060757114, 3278719964, 3201451601, 3235719702, 1968822177, 3325473401, 3530404988, 1046031734, 1488786922, 4039207188, 288146801, 3463077620, 696952531, 717208736, 569838466, 3291356333, 1145859850, 2262938300, 182793052, 745373619, 577711367, 1143374636, 295687723, 2094629474, 4249644155, 1820001221, 1810391234, 3620440158, 97620513, 1573474422, 599617125, 445881164, 3379294576, 1509019092, 1616917119, 174807597, 47687993, 892617974, 2705382280, 2363062253, 243546311, 4261275136, 2740476589, 153906826, 2742384370, 3666763057, 241731388, 2722133807, 3245414981, 412668963, 247950677, 1736679440, 3557703741, 867337983, 883341861, 2993176100, 3882670986, 1546514074, 3708622517, 2655738973, 1656965387, 2959616899, 4108858231, 995189079, 1368651495, 650870611, 3031541589, 2751829226, 2772166688, 4039821315, 4245219482, 2167186936, 3712370238, 2415614894, 1676556154, 1359591206, 2716475907, 2274948102, 3054135862, 1012775719, 2352199175, 317881758, 1446452732, 280377976, 1450658304, 1706146830, 3039574421, 1818593342, 1739683975, 3056485259, 1193539259, 2270159377, 1426414895, 1581081047, 4235010080, 2721409410, 1997021236, 2363757214, 4130657346, 2721417052, 2209486, 4290993663, 1464070438, 3589080094, 2525046061, 1445122888, 835612043, 3252525974, 834936713, 1073726158, 1523194376, 2078938960, 4178349241, 1247350823, 2010232260, 2489721984, 224655890, 935545827, 1524526169, 4163098499, 4176971340, 2964407544, 4004512112, 3931905582, 2444819857, 1890891472, 1490614855, 2339648625, 672087347, 640184564, 3105039642, 1729067855, 960128158, 1010057519, 1405673317, 3649611599, 2542120408, 180175327, 1711559897, 50663959, 441414387, 2390844864, 416282732, 1894961023, 1430801306, 3409496076, 1558181329, 4153953271, 862424108, 387045957, 3149728547, 1987120624, 1218935297, 2690458349, 3841568825, 1063752145, 2577162597, 1755549076, 2321455547, 2007345136, 517094409, 458326402, 3355749184, 1548971366, 2219264411, 3853642582, 561337987, 2687253930, 1846230084, 798143798, 72705356, 1039836155, 4118873607, 3258680469, 1669961264, 2919201624, 3057964422, 1174921753, 667094142, 2434096317, 3376992099, 2354328041, 3982194113, 2808629397, 2334028703, 2486018814, 2803772026, 3706255975, 3735441028, 4048829268, 2640181605, 2791081398, 3187283224, 1420508759, 138780420, 2393694635, 1184332229, 3997757293, 4276770176, 2496387274, 417828868, 1602877105, 2235729038, 3691067483, 503993304, 3420040537, 2686226340, 1773044641, 799706948, 2949769977, 91162925, 3438458088, 3573556447, 4006365173, 1221921592, 429780904, 237532788, 1787220209, 596697054, 1460150725, 1285764996, 901649834, 1027376964, 4028678919, 1248204232, 1617832578, 1842078181, 3398378539, 1642769664, 1597164446, 1666936309, 311817855, 3884791895, 3894947425, 3042623464, 350745233, 776555893, 4153552234, 1893211311, 1566470121, 1333612492, 381694502, 1001660484, 2234589211, 1128139813, 1089867645, 197228854, 1168947609, 530551364, 2400655905, 1276054557, 875480155, 1610951735, 2754435231, 2996501571, 3119206392, 4017707254, 908998398, 3298533772, 2579842498, 627590680, 2588836049, 1840168857, 664924243, 3804577051, 3509253077, 1967766220, 1386834240, 2465288453, 1220720676, 2388751611, 2463852704, 2415721294, 543085153, 816179883, 2327321054, 3313299764, 2481101596, 2201764416, 2919855989, 854315615, 523753448, 4209727478, 3030307352, 4157525938, 3415518022, 2888990891, 3345364256, 2511844163, 3006169882, 1261015534, 3087563714, 2278724664, 3439167067, 1498618418, 4063470234, 781322457, 1346936858, 1326620453, 3011448499, 3805578837, 773261167, 2316916557, 3269573294, 3333438661, 3849843107, 3556832678, 2069444768, 3790111245, 79089423, 2924984693, 18734206, 2604232002, 4125055949, 4091705300, 1700550754, 2540755871, 1649978242, 895076161, 4141115192, 3282587355, 2340467917, 808656449, 2669853244, 2651892238, 4259808341, 4169350536, 2592320626, 1682635212, 31343742, 3066721620, 4093989517, 1227461030, 2347358084, 3292708736, 2808589138, 4123289652, 532909656, 867975774, 2707193533, 881539587, 386826200, 2047543778, 400188218, 1993945486, 3458143768, 4090834261, 3451382429, 2825920518, 91932485, 1828162795, 175756293, 1017795757, 1665072886, 185452585, 2175593188, 657966198, 2019404359, 3439175000, 2265772450, 1355412956, 3914090222, 3381121599, 1102843755, 3075985554, 3358743185, 5496668, 4012072207, 3776127872, 1193484148, 350488559, 1371474450, 3343394375, 4157439645, 3676800032, 4249018010, 1454421289, 2562843285, 3974248033, 1493690489, 1456402728, 3805485054, 3641302435, 2011107827, 1094359118, 2513002496, 1424094368, 91663964, 1067845668, 1608023053, 522149526, 4011366665, 3856710862, 2622436286, 3356690186, 461674860, 2472498556, 2815371927, 412650411, 1285201754, 3083178955, 327737650, 904043680, 1352232199, 1795832646, 1202938860, 29049707, 3789741602, 2252885489, 1373818316, 3409504463, 261949035, 2186267943, 1447542410, 1226019273, 2855570907, 3012827537, 3525493748, 307724649, 3869655396, 912846491, 2303989792, 805681508, 1144302191, 687742306, 1336478631, 1048014972, 4088774379, 2184608648, 543267187, 3083147105, 1643853586, 2652563331, 2265473258, 1216505230, 2125765234, 1628273767, 4037979207, 3572915422, 2733632060, 1018468994, 2877196631, 4257066391, 3435508083, 2953048896, 227233051, 1677058233, 3393987243, 1630377564, 352262598, 165290804, 2253568411, 3810860149, 152658599, 1398820093, 3642047879, 1642654512, 1629029746, 1559147389, 2694721035, 323615917, 421807970, 2704383436, 1588101737, 4145880364, 3009653936, 4003227232, 1731486262, 2746953947, 2817353926, 3675732862, 996892540, 3554282008, 4012601812, 1827732225, 3462793519, 3646827660, 3018399132, 858013576, 2953108187, 2465692369, 3424871028, 1592298025, 2328226815, 3679158793, 3014109739, 2387940711, 3787948052, 199416399, 1669163624, 2471243435, 1957026796, 3348929473, 2859616203, 704636303, 515381934, 3349915370, 2137689394, 2868839013, 1941312490, 3337330943, 1258381749, 4039172686, 3780083628, 3246066007, 3738477681, 1292100936, 2302445852, 4061473062, 2439056106, 1987540954, 1464041146, 3884979483, 717892813, 3378013239, 1793810139, 3029669978, 3544298769, 240194676, 2300258335, 4109982413, 2073760675, 2736681800, 96213137, 3293727893, 3750657935, 38682782, 902172345, 2819871329, 1881013876, 2587165583, 3400261128, 2783936447, 3708062970, 2299257255, 888427908, 2898617216, 1554962103, 3369868860, 1925228618]

print(recover(state[-1]))
# 114514

赛题

2020 网鼎杯白虎组——random

这题的本质是给出700个random.getrandbits(32)，要求预测第701个getrandbits(32)，那么思路就是用给出的700个值利用逆向extract_number得到state，再往后预测随机数

我们可以自行测试

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
import random

def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def recover(y):
    y = inverse_right_mask(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right_mask(y,11)
    return y&0xffffffff

outputs = [3856320579, 582346195, 3618983146, 2042063976, 1184168896, 396290811, 172396203, 1865207412, 3513099586, 2068572360, 1068542070, 2748673688, 3223623448, 3405563534, 3988198879, 2760302757, 682475183, 664583410, 3748223341, 430704012, 3625001104, 3357182041, 2074997633, 4220987130, 3071322516, 3699451070, 3668390600, 2308851921, 3722345414, 640871845, 4040807500, 68505531, 2722397716, 152975230, 3396499459, 611884180, 2780014634, 1762213421, 3727058429, 3279075094, 2020811567, 1955079559, 1982049705, 618514519, 782628428, 2231787577, 3958418339, 3619191692, 3262044252, 3239486806, 2091920859, 1649794832, 2049988981, 3950537809, 3494642440, 2373203533, 3908938509, 4260665545, 3992436207, 55233433, 3678164019, 3382125549, 1031050744, 475668950, 2712640527, 3262072084, 270947538, 747369005, 2449233680, 168550240, 3472526026, 4236638624, 2353167392, 338773947, 3102391394, 4106050694, 2101907501, 1511485944, 2540533755, 291407666, 1388779576, 1581113430, 1005505294, 3737919939, 2574230177, 1506489003, 791427607, 3039232414, 4290205147, 334372227, 4192207263, 11583436, 1091806965, 959404673, 1550692802, 743550782, 3015066354, 1843787256, 1089162969, 3282721857, 3947303971, 1447391170, 3549321293, 3883434277, 3156541810, 457481521, 998989161, 353007883, 2154611512, 3500086770, 291601413, 809079524, 4096216221, 1972316626, 3392166890, 826467439, 2251471337, 3810124886, 1174971249, 3448439560, 622493039, 2661871054, 514732941, 1285876333, 1325623476, 942537583, 474391642, 3222347875, 3598063610, 1390260164, 1368857781, 1586104057, 4169375007, 560089657, 3871863081, 3664033451, 360130987, 1338114992, 1386653770, 141908613, 1087817361, 2578440356, 4238690391, 2491333789, 1313554240, 2659158617, 2026626952, 3758863748, 31333958, 1515192303, 1980512149, 1523102569, 1015648738, 402013118, 668083749, 1613274796, 3266155997, 1388893607, 2234359768, 3039773093, 1754072774, 1255047196, 3008000059, 2814267560, 4087098288, 3612111948, 2783546052, 2422793522, 2054512708, 2157246187, 3896113834, 3091314347, 4066054956, 697611949, 4293436184, 4178028304, 1232448137, 462706657, 2546090314, 2580413378, 2991884731, 3477559744, 819828518, 2378581444, 261974330, 48554242, 1125904908, 743303927, 283943396, 2239687403, 3397561838, 1936983918, 813124442, 1372261461, 2675158527, 2811298655, 3600392264, 3081073716, 3285423961, 2470299114, 35562143, 2374487620, 523196833, 837053452, 442383295, 1642526474, 633356203, 934212664, 2541169652, 2218324371, 2293743808, 533650099, 3922760511, 2796518408, 1233841965, 1331867338, 911224321, 1878236230, 3997425837, 263502568, 2427147217, 377222419, 980472509, 3718192901, 4207766, 1900019200, 2494403882, 2608467619, 2531637576, 3316511918, 3064471002, 2357840013, 1494395355, 2760712913, 1301257467, 3639957765, 266103064, 4195520357, 606353778, 625335058, 245993933, 210040927, 1719447395, 4182661980, 2096278341, 2308071160, 3916671207, 3875154215, 3042399609, 1892589882, 2055655644, 4162222987, 2619931041, 2862794713, 2660510520, 3979077509, 830949746, 1046088983, 752539852, 2079596180, 707323337, 4181110498, 3320112802, 2675358193, 2013709407, 797600224, 3977215055, 1660380026, 2330229635, 3780677230, 1765339288, 50797844, 1326458332, 2704700279, 3388388140, 2949009302, 2652386153, 4070023754, 663847171, 2530173162, 1787912129, 2133212070, 585187560, 3412976489, 1109974365, 1388102174, 3763930833, 603205256, 790728101, 285097555, 1986002544, 4136614930, 2730768819, 1422358203, 4207378229, 1305416929, 3253570173, 614096292, 4006108012, 3997549750, 2963994445, 390402033, 148705559, 2400665295, 1629175351, 3175584699, 531068763, 3547563920, 951205529, 3951721422, 2045335509, 2061079714, 1020389523, 1398264757, 388342296, 1113940071, 2884073722, 3909877149, 1554456027, 4166045208, 3292049984, 2047607647, 2406249956, 1165134100, 1492019858, 438786476, 2455620417, 1045115687, 2298575790, 2641273358, 3428151066, 1771684405, 1469667266, 245779746, 3780673506, 159637867, 1974818756, 1417299436, 1757616882, 2931609965, 272261657, 2992310526, 1640699729, 1550869638, 2831720525, 3188206484, 2147244773, 2702236061, 2845925972, 2472472340, 1950271077, 1073077867, 2669473456, 1017796207, 3398740200, 149898285, 969790886, 3976683028, 4100426487, 236528673, 2275913926, 70804541, 1015988608, 2288793751, 1516397338, 36466183, 1810140379, 35027792, 3515304008, 3369816002, 4218943237, 1292859807, 2868585129, 1344314860, 2966363405, 1270384480, 3430972215, 2905554740, 2834517081, 2277787053, 3369281826, 2330136701, 2811934643, 437795454, 790307084, 3938433156, 2696231004, 2864065004, 2071195617, 3450944719, 2593258395, 4156266153, 2933408715, 314356055, 3838824165, 2208826112, 673615301, 451826871, 2653901210, 1091115010, 3494549155, 2126719717, 492550938, 2486431133, 673318550, 1873965526, 2615574806, 3022521670, 3153122841, 316109818, 1358644343, 371632675, 3079378052, 3394493516, 1042427109, 4083513993, 2879031841, 1188720143, 3764965656, 2934659446, 3645520948, 3761388578, 1399281780, 1467393315, 2748507851, 3916290285, 162638517, 3503680397, 1202087557, 1797301343, 4038743012, 498411215, 1906945487, 1269012684, 616165911, 2689362140, 2954293400, 2749974859, 372077473, 526599366, 2719433559, 445270887, 1787930323, 414594410, 1531788692, 655371094, 1134528247, 922864801, 577427318, 2476882905, 3762554878, 1263109260, 889201305, 3756246995, 3505662458, 1792412776, 3096524063, 4010213023, 1822791406, 498896760, 2895851116, 194376912, 3834164906, 921981686, 195822201, 486251241, 3027841388, 177205766, 2237855353, 2426431616, 1243779662, 3596629671, 3198684268, 383794333, 4088735022, 84096876, 2597108436, 943661592, 3010249765, 651609816, 2028864217, 88066893, 416774877, 3406354028, 1131222595, 3257056160, 2047423822, 466652966, 540014760, 3575349728, 97598377, 3860944863, 3358078401, 2576759735, 3026694340, 1542421979, 1208350673, 730717774, 1548179769, 3866316925, 1524301730, 177925641, 4040163095, 3647937899, 1566223024, 851510626, 3763176296, 3748357246, 3163985940, 1188874855, 3744613224, 2298060224, 3290018347, 3524287701, 546532864, 2202356429, 4090704033, 153373528, 3624854156, 3619995514, 971161525, 1651704710, 3184983159, 3904044857, 2631074289, 2994477708, 466922481, 1185754575, 2236625463, 2574503930, 2271362108, 2352028513, 2348762614, 185909629, 2681195010, 1957314281, 1664135627, 1653223437, 1007998044, 2059226119, 107468870, 349013320, 3069230899, 573256156, 3065294197, 2888682091, 4188263099, 3052015975, 3252740424, 3819272656, 4036891979, 251329729, 3274617160, 2479410099, 2524686476, 1381270898, 3911980232, 3575282849, 3279515129, 4266855886, 1665575754, 1479237476, 2990196390, 3190994678, 3006848624, 2519770216, 3136161554, 511739068, 1786433701, 1713816087, 1641600232, 2961791165, 4243634468, 3458215124, 2879399149, 2899139587, 3344687724, 1344768212, 1987847167, 1317563177, 2998618925, 600607120, 580705122, 2796148254, 3695708628, 203562398, 3020286723, 4105783504, 4212275211, 497705671, 2158484700, 986009433, 4041195051, 3569002127, 862242677, 1369976294, 4138172444, 315810932, 3741340107, 1042036777, 3727198761, 347247004, 3928525886, 3727331951, 4157809556, 1897317622, 3338188695, 3742860698, 268219460, 459374679, 1641077364, 891407958, 2714939388, 3564273440, 3690128793, 1750444640, 3290494688, 3759527045, 3705846216, 663551340, 3669286435, 63793922, 2552809954, 912695183, 6040685, 3485374653, 3703861882, 2703476363, 2988768795, 2308363444, 1140391792, 1961672168, 594823203, 1106597270, 1875618248, 2319530228, 1049439924, 2061432103, 1692840785, 1079740283, 2352424790, 3403787086, 47324887, 1832435850, 1613238108, 1448314858, 1459605180, 2364440437, 3247443276, 1262170458, 492220272, 3683373765, 3679148921, 866864270, 2477814155, 2065864431, 4188808041, 1198808728, 2933465169, 261694304, 2229917088, 3493329678, 673544611, 224852180, 4229537516, 3676005877, 2594310223, 3955303385, 2694125916, 639404191, 2427452820, 2829149388, 2566455212, 2946677059, 228963779, 1917238465, 2381366147, 1916689453, 39849223, 2324519978, 3422879216, 2715013754, 4278642992, 700303459, 3354052905, 4061459792, 1428274751, 2146294147, 3905217098, 1617406780, 408601626, 3776149665, 4131141161, 581113184, 3051175634, 3839200652, 516810624, 1935938682, 3289303720, 1155849673]
x = 4126744556
state = [recover(outputs[i]) for i in range(624)]
RNG = random.Random()
RNG.setstate((3,tuple(state+[0]),None))	# 这里的0表示的是索引
for _ in range(700):
    RNG.getrandbits(32)

recover_x = RNG.getrandbits(32)
print(recover_x == x)
# True

2020 VN 招新赛——Backtrace

task.py

1
2
3
4
5
6
import random
flag = "flag{" + ''.join(str(random.getrandbits(32)) for _ in range(4)) + "}"
with open('output.txt', 'w') as f:
    for i in range(1000):
        f.write(str(random.getrandbits(32)) + "n")
print(flag)

给出后面4~1003这1000个随机数要求恢复第0，1，2，3个随机数。

我们知道生成新的state[i]只与原来的state[i],state[i+1],state[i+397]有关

1
2
3
4
624 625 626 627
 0   1   2   3
 1   2   3	 4
397 398 399 400

如上，假如我们要恢复state[3]，就需要知道state[4],state[400],state[627]，这些值我们都有。所以可以恢复state[3]，再恢复state[2],state[1],state[0]

exp.py

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
import random

def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def recover(y):
    y = inverse_right_mask(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right_mask(y,11)
    return y&0xffffffff

def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(3,-1,-1):
        tmp = state[i+624]^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+624]^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

outputs = [1804671209, 2922063510, 982379708, 2464792029, 2279859639, 4192963638, 452357623, 4132693504, 1670542619, 2862253188, 438444339, 2079581686, 1366572261, 3590214900, 2319202187, 931063565, 2346715284, 1213698793, 131046035, 2055116434, 2020298725, 1367424316, 2241749902, 297076859, 2365196575, 3277854092, 1879357622, 1797510832, 3530412999, 1563276058, 297778141, 633291943, 2012139813, 1713908450, 179565811, 3768228415, 3621459563, 641786681, 4311896, 3789346845, 2627264570, 3107085356, 1466667492, 1297394685, 51245732, 4269055538, 1681463096, 2449172061, 3986761220, 4239108714, 1786470635, 1195565318, 1494228645, 2331017985, 4280559218, 3370269929, 3637069883, 2669762830, 2530922211, 3766805033, 1947934816, 784834577, 506178037, 2277430206, 2102460806, 3791496810, 1481793757, 649412979, 1886729484, 1196818092, 112603133, 2149292951, 14248690, 2418042093, 18681599, 3666467881, 4097621725, 2300591192, 970351245, 2351169329, 74344968, 424638826, 256514923, 3110590321, 261313939, 765554639, 2603908959, 1722030051, 4100196523, 15614906, 1128199392, 3858664581, 3957413342, 1690096984, 3804922505, 3035847650, 967122609, 339595431, 3666291525, 3348490553, 2797300559, 793352202, 1322582353, 1618309162, 3192842490, 1166436135, 250408731, 2257445542, 20450594, 1801793086, 183031318, 2617979445, 578014449, 1341923011, 3730690997, 482392182, 2207491223, 3683140597, 4278507384, 4004660414, 3050973569, 2749567532, 1753608470, 3191366926, 3275447454, 431251176, 3513077796, 3021445304, 2150780435, 1011516397, 4126768105, 3956170349, 3053379608, 4017545930, 1849695707, 106947830, 4041980616, 29134296, 2844330679, 3358520004, 2120680048, 857645488, 3571836532, 3610004372, 1641667223, 1406368469, 1160310536, 2256091502, 1200902294, 4054039541, 3639946217, 3786291139, 1352751210, 2977986351, 1910599729, 209471044, 2232574666, 3616274023, 3376363234, 1903952569, 3552966887, 3593859495, 2717534809, 42959387, 187698299, 3883809630, 856731268, 3910747061, 907775227, 2928927204, 4081693478, 3955495837, 2142003593, 3746756893, 249265437, 2495197443, 941182492, 3703605091, 2681355671, 723911707, 3470840379, 1434547184, 529161886, 2636831176, 2822486818, 3471189015, 1513478010, 3356287845, 1869706704, 679091668, 2383482353, 2143693501, 199815085, 4236474935, 144033792, 833985848, 4290347454, 3517268693, 4230402381, 2985005670, 2550569910, 444595279, 4207941159, 3449400944, 3393809088, 2840774178, 2782199449, 3924359065, 558423647, 925255465, 4101077039, 4075577051, 2425366506, 2785054252, 178902415, 2392449510, 3621528509, 3238774753, 964426270, 2865540864, 234875917, 1580908594, 2105493500, 1684686652, 2327670241, 310526764, 2009697107, 3955577194, 1654978722, 382085028, 1280304430, 4217869423, 2239567035, 698475741, 2758310735, 4207600994, 1547108566, 397184543, 4136031884, 2537911943, 302343125, 841434537, 12311784, 3061367072, 1336001590, 1364007977, 3600115935, 3479786959, 3463921743, 2923213199, 1852358558, 4107068894, 3320404724, 1941634133, 3964964656, 615840392, 3853790685, 2259407865, 1341169078, 98341588, 2575314704, 435137897, 3558750888, 210904882, 3279251760, 1977481875, 3750538206, 2951076292, 3259540110, 1037829634, 1019064060, 1624487857, 3557157064, 453278517, 1997203275, 3526376259, 1648439207, 3508442145, 519537525, 1608487942, 1861353689, 2159984795, 523981662, 385641968, 1092941911, 3455149514, 3519379501, 1531854086, 2523777950, 2097885523, 4186683569, 3998881974, 1070109105, 843613269, 2477944313, 1353211789, 3584381026, 970904128, 2511689463, 2039884234, 3361343641, 1546075085, 2684250257, 2063901071, 687437087, 4286773169, 440356712, 725842843, 3865626108, 2472843267, 1452486843, 3427178195, 3892564172, 2433729005, 1957819593, 3340106040, 1860833850, 3593441485, 3116897241, 3827153355, 4273093885, 3520772876, 1981630614, 3896362499, 2173708978, 4161270666, 3414069041, 2299636418, 3467917329, 4196143926, 1724129788, 4084657553, 126994973, 3335896948, 25789124, 2666223946, 1948458478, 2352250823, 3983356639, 3584817808, 1978974039, 1999870993, 3076066566, 677925554, 935423362, 3673655441, 3186635480, 3818566611, 4183049188, 2746805953, 2095957033, 2682147580, 869189034, 2779097594, 3608428095, 3513611157, 755774505, 3808579345, 3693318911, 1839166699, 490814908, 3143472566, 3812486276, 2273855376, 3822549578, 2998813123, 486999089, 2485672763, 576709591, 2428238981, 2165688575, 62919364, 1372202352, 2188973499, 3160921780, 250246630, 1092998590, 1448896904, 2553019271, 819544935, 836137214, 3141978292, 642366793, 547934351, 1425622018, 132772933, 325392879, 1505743917, 3513406682, 3147243677, 2436174815, 2211221215, 2589011325, 3155697488, 3230919533, 3872590594, 519917897, 1897289742, 1742132001, 358501373, 2013561845, 1552541463, 3040550447, 2168305800, 3556728906, 2281430717, 2967589499, 3224106771, 3545160301, 4292207714, 39759152, 2551106886, 2035978838, 458767025, 4120756128, 4238783027, 30128300, 2324881505, 3206294273, 4243159219, 1539976766, 2594977046, 106193658, 3006838718, 711591954, 1631205080, 2055422509, 3220791016, 2211454015, 1684293308, 4097039749, 1950827819, 596270726, 3949026618, 889300608, 1474069298, 3689944987, 517015298, 1929617999, 2440031896, 2709812101, 1992955924, 4274956952, 2444627438, 1959460115, 582069911, 2419904717, 3222968174, 3399960494, 3144995592, 3407724325, 2444014512, 3959150538, 4285851741, 4079378961, 832382130, 904017537, 229548363, 93000443, 2440031554, 2400145592, 3894768702, 3306376113, 2064753071, 2520029593, 2289772340, 1863760194, 759985554, 2440361346, 2646486175, 3828340148, 3690476425, 3952521366, 1818853914, 3741487901, 1939261261, 2522131855, 4263166822, 389813606, 733497630, 3364518596, 1731487900, 3471982991, 774566785, 3061220186, 1670746657, 3364896019, 257688296, 2212175202, 2200932587, 458338439, 3070098357, 2769742051, 3731458422, 3112982787, 2370551593, 1357388415, 689717848, 2474014809, 2090597022, 1733516418, 2303805959, 133232025, 3047633045, 1517049212, 4283541802, 1001889723, 2375959444, 4243450364, 4168200824, 3231795488, 2650394352, 1574410332, 86126802, 3758445831, 2340719748, 4115977672, 3798145365, 77324638, 2643593782, 634790561, 3358486700, 4140032295, 3513246850, 261272711, 2220124969, 2897469143, 4198241230, 2456337431, 1981544167, 1249742357, 106387114, 2060633623, 3173024725, 1489283527, 510143932, 1243349100, 2298772697, 3898067472, 466814336, 2098853148, 83390745, 343787359, 2538403891, 1409671714, 1444158150, 3335793145, 4226110080, 2968674376, 4156094751, 3856849035, 2710375881, 1822021241, 2472348939, 27109603, 901956173, 1606776692, 3109594349, 1160160161, 4079063811, 3773912133, 2585704643, 3232895223, 2121801358, 1026952079, 583614097, 3824579802, 1380685627, 3652460459, 2028089458, 3175057906, 4068861409, 2515606890, 1200775571, 3314622745, 2289228806, 2646556019, 3687287145, 49195901, 1798788309, 591957085, 3929804275, 1689134041, 2396654796, 1126677730, 3880693177, 2706798188, 2926253562, 675988773, 3092145194, 1110289401, 2781751897, 2460708698, 2300555350, 3105548417, 2687966933, 1944880991, 1946066440, 323729559, 198758259, 846089862, 2055735049, 986255431, 3903265597, 2578706952, 326562597, 3041585079, 945078860, 1313161403, 410061813, 1875226375, 4212298012, 12181578, 1436289796, 2646424052, 783968191, 2296237075, 2514394580, 4048299958, 301817307, 4184456419, 1942975051, 2919339051, 3501922263, 4162022536, 3630366026, 3721271779, 1913934486, 2336935816, 2577035298, 2970413319, 2019488980, 2714459625, 1142206555, 2536005590, 206897342, 3510979210, 3796491959, 1776313757, 782863260, 2012142818, 3436192835, 2898073146, 3130308109, 4274710928, 1969954984, 1290470001, 2126172027, 3079056575, 1662723122, 3834154279, 1509844752, 1879507382, 243461236, 3263993681, 527941040, 2960667151, 437845417, 925496821, 1532313974, 1649607266, 421206050, 2648509518, 3766566857, 3537376560, 4056193064, 1077967822, 1307860259, 2569990067, 1896535739, 495691568, 2491860991, 1884037256, 3658585973, 2004809564, 1201319320, 698236773, 3179165673, 3128142447, 2969734009, 1938769280, 3816534949, 3967462278, 314256685, 3401644041, 141163388, 2139836122, 2186165576, 880507946, 1075680415, 590095951, 781161014, 1885882245, 1415340529, 676870166, 3098324703, 1603740967, 933186052, 2188444967, 1380155075, 325075865, 1826119902, 657002558, 2251435414, 1638195740, 339678650, 3669082568, 1796805010, 2141050149, 654717883, 4003791182, 1664663632, 1791829182, 259621495, 1501507869, 426821083, 4011249694, 2287808720, 1030313919, 1534049880, 3370703691, 2893327247, 3884350708, 252032180, 3517235610, 3106783933, 980527030, 3504106133, 2084789728, 3793438714, 995575458, 2288315137, 4111859009, 3921864816, 3721487765, 2793219118, 746638554, 1549812168, 2700267409, 1853734662, 1748279701, 3892771410, 4288430018, 3686995103, 3434770368, 3367913996, 1168390523, 725767781, 3092288760, 2591847798, 903957053, 2504294653, 347477166, 1017481488, 2470321729, 3672335375, 533737623, 1610987374, 2765681913, 208872518, 1965977476, 2620202455, 883316392, 3699766142, 2994493820, 1812755424, 2735350105, 3950705917, 1476668479, 1493462761, 2815529253, 806646294, 3645423519, 2013669614, 3129486607, 3144614215, 288595162, 3817835069, 267874362, 3043915018, 503418590, 4121632504, 3180856289, 4032347928, 3291631906, 1562033533, 442863943, 3466166285, 278810154, 1494382527, 3574923557, 1998156211, 3601671137, 3487174754, 279104055, 1252510103, 3487132312, 1621100800, 25161472, 2561260209, 965612285, 1832250248, 52415796, 3154169940, 2243747062, 254479611, 677387201, 1358172452, 3921571652, 618761969, 363666210, 3162780940, 3666074031, 1665264787, 1503573736, 911086726, 2321382060, 2488029747, 3937816868, 1422278816, 360698969, 2905431783, 1651373133, 1002394393, 2463677024, 3847067039, 4109151996, 3692875187, 3957213415, 337774859, 1627457381, 2352921901, 1179122457, 792596339, 2058169995, 98826108, 184541385, 573041636, 1718503267, 2373979624, 1539423106, 2133802553, 2718932930, 2899602984, 1708749378, 1493281076, 3826992689, 3187379881, 2712719707, 1836233390, 1513079935, 2948529391, 1284828221, 1934418973, 2112847098, 4006425883, 1052931751, 758501987, 3223983720, 3073673083, 836081105, 1472754488, 2487029702, 1801093799, 928502313, 2759231771, 289737457, 1206688708, 3140526342, 104209388, 1361386155, 3960807502, 482386571, 459903450, 2680652306, 2508629297, 286409773, 3483104433, 3871176786, 729736313, 2712461087, 4246130450, 3293470502, 1864992810, 3993063846, 1448244981, 3620828636, 1054531830, 1459388713, 858014894, 4183748064, 1582214994, 3953275394, 727377185, 3491687643, 2796129215, 3668426666, 3557506333, 3144306538, 4281464076, 3011495069, 2962568386, 4184263382, 1508606659, 205231019, 3386764677, 127956607, 1929240858, 2548967515, 3414626647, 2679328453, 4115330272, 2138199538, 528646513, 930913501, 2289236352, 1450362023, 3715782672, 1564424064, 1483557512, 1925447364, 4033938968, 948886720, 1934701201, 3443512270, 3764216731, 1916644786, 1384731002, 1287076013, 2018652058, 2958813289, 2447620542, 3796146048, 1622854988, 686433039, 253693283, 2111793939, 2306433090, 4080191525, 2224402081, 59703913, 3958459307, 200336724, 1145854569, 3663609709, 2415681691, 2296226043, 392158285, 188412176, 1602068724, 3672007681, 3351358685, 77226497, 2761914402, 4182346783, 1761752133, 3379796480, 1432182970, 2888348707, 1802155620, 616220107, 3016445592, 3865489237, 2995611525, 2625430625, 2137676831, 3606331449, 1226821679, 2631807346, 2059447310, 230230491, 170274047, 2996095768, 430212978, 2288854251, 848196586, 3756171416, 3810330367, 2274580015, 535135238, 2912469751, 1239590861, 59737234, 1876188585, 1963377303, 934928269, 1508581017, 716112306, 1249284798, 2477368019, 1268762080, 3319914811, 471096890, 2932800245, 1107822578, 1924574171, 2720637936, 2154900827, 3462641388, 3566142421]
state = [recover(outputs[i]) for i in range(len(outputs))]
# 这里是索引4 - 1003的状态序列，我们需要知道索引0～3的状态序列
state = backtrace([0,0,0,0] + state)[:624]
RNG = random.Random()
RNG.setstate((3,tuple(state + [0]),None))
for _ in range(4):
    print(RNG.getrandbits(32))

进行修改的部分为backtrace中的

1
2
3
4
5
for i in range(3,-1,-1):
    tmp = state[i+624]^state[(i+397)%624]
		...
    ...
    tmp = state[i-1+624]^state[(i+396)%624]

其余地方没变

ExtendMT19937Predictor

项目url见文末

通过输入 32×624 位生成的数字来预测和回溯 MT19937 线性同余生成器。

1
pip install extend_mt19937_predictor

只要我们有了32 * 624个输出，便可以用如下方法进行预测和回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
from extend_mt19937_predictor import ExtendMT19937Predictor

predictor = ExtendMT19937Predictor()

for _ in range(624):
    predictor.setrandbits(random.getrandbits(32), 32)

for _ in range(1024):
    assert predictor.predict_getrandbits(32) == random.getrandbits(32)
    assert predictor.predict_getrandbits(64) == random.getrandbits(64)
    assert predictor.predict_getrandbits(128) == random.getrandbits(128)
    assert predictor.predict_getrandbits(256) == random.getrandbits(256)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import random
from extend_mt19937_predictor import ExtendMT19937Predictor

numbers = [random.getrandbits(64) for _ in range(1024)]

predictor = ExtendMT19937Predictor()

for _ in range(78):
    predictor.setrandbits(random.getrandbits(256), 256)

_ = [predictor.backtrack_getrandbits(256) for _ in range(78)]

for x in numbers[::-1]:
    assert x == predictor.backtrack_getrandbits(64)

gf2bv

项目地址见文末

ExtendMT19937Predictor这个工具要求提交的随机数必须是32bit的倍数，并且需要连续的随机数。如果题目提供的值不满足上述要求，我们可以用gf2bv这个工具

最最最极限的情况就是给出19968个getrandbits(1)的值，可以看我2025强网杯的ezran和Blurred

不过这个工具用于预测随机数会比较方便，如果是要回溯的话，结合ExtendMT19937Predictor可能会比较不错

Python random模块分析

从20250xGame——Week4——MT19937这题入手

0xGame——MT19937

task.py

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
#!/usr/local/bin/python
from secret import flag
import random

seed = random.randint(0, 2**32 - 1)
RNG = random.Random(seed)

MENU = """
MT19937 Seed Challenge
======================
[G]et random number
[C]heck seed
"""

def challenge():
    while True:
        inputs = input(">> ")
        if inputs.strip().upper() == "G":
            print(RNG.getrandbits(2))
        elif inputs.strip().upper() == "C":
            guess = int(input("Guess the seed: "))
            if guess == seed:
                print(f"Correct! Here is your flag: {flag.decode()}")
            else:
                print("Incorrect seed. Exiting...")
            break
        else:
            print("Invalid option. Please choose G or C.")

if __name__ == "__main__":
    print("Welcome to the MT19937 Seed Challenge!")
    print("A random seed has been generated. You can get random numbers or try to guess the seed.")
    print(MENU)
    challenge()

  • 题目随机生成一个32bit以内的值作为seed

  • 通过seed生成一个新的随机数生成器RNG

  • 可以获得若干个getrandbits(2)的值

  • 要求恢复seed

其实思路蛮清晰的，通过19968 // 2个getrandbits(2)的值结合gf2bv恢复随机数的状态序列，然后求seed。我们需要注意的是，Python中random模块的random.seed(seed)调用之后，并不是简单的把seed当作状态序列的第一个值去生成整个状态序列（这是模块与MT19937的区别）

那首要目的就是知道一下首先对seed做了什么处理，经过多次拷打AI，在python中调用random.seed(seed)会执行一个叫init_by_array的函数产生一个state再去生成随机数：

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
def init_by_array(init_key, key_length):
    N = 624
    state = [0] * N
    # init_genrand(19650218)
    state[0] = 19650218 & 0xFFFFFFFF
    for i in range(1, N):
        state[i] = (1812433253 * (state[i-1] ^ (state[i-1] >> 30)) + i) & 0xFFFFFFFF
    # 混合 init_key
    i = 1
    j = 0
    k = N if N > key_length else key_length
    while k:
        state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1664525)) + init_key[j] + j
        state[i] &= 0xFFFFFFFF
        i += 1
        j += 1
        if i >= N:
            state[0] = state[N-1]
            i = 1
        if j >= key_length:
            j = 0
        k -= 1
    # 第二次循环
    for k in range(N-1):
        state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1566083941)) - i
        state[i] &= 0xFFFFFFFF
        i += 1
        if i >= N:
            state[0] = state[N-1]
            i = 1
    state[0] = 0x80000000  # 2147483648
    return state

# 模拟
seed = 114514
state = init_by_array([seed], 1)
print("Simulated state[:4]:", state[:4])

# Python
import random
random.seed(114514)
right_state = random.getstate()[1][:-1]
print("Python state[:4]:", right_state[:4])

经过验证是没有问题的，那接下来的问题就是如何通过state回推seed，又经过多次拷打AI，给出了求解脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_seed_by_z3(mt_state):
    """
    mt_state: list of 624 python integers (each 0..2**32-1) - the internal state you have
    returns: list of solutions (could be empty). We'll search iteratively for multiple solutions.
    """
    if len(mt_state) != 624:
        raise ValueError("mt_state must be length 624")
    seed = BitVec('seed', 32)
    solver = Solver()
    computed = init_by_array_bv(seed)
    # add constraints: computed[i] == mt_state[i]
    for i in range(624):
        solver.add(computed[i] == BitVecVal(mt_state[i] & 0xffffffff, 32))
    sols = []
    # get up to some number (say up to 4) solutions (there may be 0, 1 or multiple)
    while solver.check() == sat and len(sols) < 4:
        m = solver.model()
        s_val = m[seed].as_long()
        sols.append(s_val)
        # block this solution to search for another
        solver.add(seed != BitVecVal(s_val, 32))
    return sols

那么现在进行19968 // 2次交互，并用gf2bv获得state，再回推seed就可以拿到flag了

exp.py

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
from z3 import BitVec, BitVecVal, Solver, LShR, sat
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from pwn import *

def init_by_array_bv(seed_bv):
    N = 624
    state = [BitVecVal(0, 32) for _ in range(N)]
    state[0] = BitVecVal(19650218, 32)
    # first loop
    for i in range(1, N):
        prev = state[i-1]
        # state[i] = (1812433253 * (state[i-1] ^ (state[i-1] >> 30)) + i) & 0xffffffff
        temp = prev ^ LShR(prev, 30)
        state[i] = (BitVecVal(1812433253, 32) * temp) + BitVecVal(i, 32)
    # second (mixing) phase with init_key = [seed], key_length = 1
    i = 1
    j = 0
    key_length = 1
    k = N if N > key_length else key_length  # here k = 624
    # note: use seed_bv for init_key[j] (always seed_bv because key_length==1)
    for _ in range(k):
        prev = state[i-1]
        temp = prev ^ LShR(prev, 30)
        # multiplication by 1664525
        mul = BitVecVal(1664525, 32) * temp
        # state[i] = (state[i] ^ mul) + seed + j
        state[i] = (state[i] ^ mul) + seed_bv + BitVecVal(j, 32)
        i += 1
        j += 1
        if i >= N:
            state[0] = state[N-1]
            i = 1
        if j >= key_length:
            j = 0
    # third loop
    for kk in range(N-1):
        prev = state[i-1]
        temp = prev ^ LShR(prev, 30)
        mul = BitVecVal(1566083941, 32) * temp
        state[i] = (state[i] ^ mul) - BitVecVal(i, 32)
        i += 1
        if i >= N:
            state[0] = state[N-1]
            i = 1
    state[0] = BitVecVal(0x80000000, 32)
    return state

def find_seed_by_z3(mt_state):
    """
    mt_state: list of 624 python integers (each 0..2**32-1) - the internal state you have
    returns: list of solutions (could be empty). We'll search iteratively for multiple solutions.
    """
    if len(mt_state) != 624:
        raise ValueError("mt_state must be length 624")
    seed = BitVec('seed', 32)
    solver = Solver()
    computed = init_by_array_bv(seed)
    # add constraints: computed[i] == mt_state[i]
    for i in range(624):
        solver.add(computed[i] == BitVecVal(mt_state[i] & 0xffffffff, 32))
    sols = []
    # get up to some number (say up to 4) solutions (there may be 0, 1 or multiple)
    while solver.check() == sat and len(sols) < 4:
        m = solver.model()
        s_val = m[seed].as_long()
        sols.append(s_val)
        # block this solution to search for another
        solver.add(seed != BitVecVal(s_val, 32))
    return sols

def mt19937(out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = []
    for o in out:
        zeros.append(rng.getrandbits(2) ^ int(o))
    zeros.append(mt[0] ^ int(0x80000000))
    sol = lin.solve_one(zeros)
    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    return pyrand

context.log_level = 'debug'
sh = remote("nc1.ctfplus.cn",14170)
sh.recvuntil(b"[C]heck seed")
bits = []
for i in range(19968 // 2):
    sh.sendlineafter(b'>>',b'G')
    bits.append(int(sh.recvline().strip().decode()))

RNG = mt19937(bits)
mt_state = RNG.getstate()[1][:-1]
seed = find_seed_by_z3(mt_state)[0]
sh.sendlineafter(b'>>',b'C')
sh.sendlineafter(b"Guess the seed:",str(seed).encode())
sh.interactive()

分析

Python的random模块底层是调用的cpython/Modules/_randommodule.c

https://github.com/python/cpython/blob/3.13/Modules/_randommodule.c

定位到关键的两个函数init_genrand()，init_by_array()

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
/* initializes mt[N] with a seed */
static void
init_genrand(RandomObject *self, uint32_t s)
{
    int mti;
    uint32_t *mt;

    mt = self->state;
    mt[0]= s;
    for (mti=1; mti<N; mti++) {
        mt[mti] =
        (1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
        /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
        /* In the previous versions, MSBs of the seed affect   */
        /* only MSBs of the array mt[].                                */
        /* 2002/01/09 modified by Makoto Matsumoto                     */
    }
    self->index = mti;
    return;
}

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
static void
init_by_array(RandomObject *self, uint32_t init_key[], size_t key_length)
{
    size_t i, j, k;       /* was signed in the original code. RDH 12/16/2002 */
    uint32_t *mt;

    mt = self->state;
    init_genrand(self, 19650218U);
    i=1; j=0;
    k = (N>key_length ? N : key_length);
    for (; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U))
                 + init_key[j] + (uint32_t)j; /* non linear */
        i++; j++;
        if (i>=N) { mt[0] = mt[N-1]; i=1; }
        if (j>=key_length) j=0;
    }
    for (k=N-1; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U))
                 - (uint32_t)i; /* non linear */
        i++;
        if (i>=N) { mt[0] = mt[N-1]; i=1; }
    }

    mt[0] = 0x80000000U; /* MSB is 1; assuring non-zero initial array */
}

init_genrand和MT19937的__init__一样，init_by_array的python实现如上

关于init_by_array的逆向，可以看文末sean师傅的博客

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 _int32(x):
    return int(0xFFFFFFFF & x)
 
def _re_init_by_array_part(index, mt, multiplier):
    return _int32((mt[index]+index) ^ (mt[index-1] ^ mt[index-1] >> 30) * multiplier)
 
def _init_genrand(seed,mt):
    mt[0] = seed
    for i in range(1, 624):
        mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
 
def re_init_by_array(mt=None):
    if mt is None:
        seed = random.randint(0, 2**32-1)
        RNG = random.Random(seed)
        _, mt, _ = RNG.getstate()
 
    tmp = [_re_init_by_array_part(i, mt[:-1], 1566083941) for i in [622,623]]
 
    original_mt = [0] * 624
    _init_genrand(19650218, original_mt)
 
    predict_seed = _int32(tmp[-1] - _int32((tmp[-2] ^ (tmp[-2] >> 30)) * 1664525 ^ original_mt[-1]))
    if "seed" in locals():
        print(predict_seed, seed)
        print(predict_seed == seed % 2**32)
    else:
        return predict_seed

Reference

MT19937分析 | Xenny 的博客

MT19937 - SeanDictionary | 折腾日记

浅析MT19937伪随机数生成算法

https://github.com/NonupleBroken/ExtendMT19937Predictor

https://github.com/maple3142/gf2bv

-------------已经到底啦！-------------