​ 偶遇题目，拼尽全力无法战胜，故来学习

wiki 伪随机数

随机性、熵与随机数生成器:解析伪随机数生成器（PRNG）和真随机数生成器（TRNG）-CSDN博客

【密码学】流密码的基本概念-CSDN博客

MT19937_mt19937predictor-CSDN博客

浅析MT19937伪随机数生成算法-安全KER - 安全资讯平台

你没听过的梅森旋转算法 - CHNmuxii - 博客园

Mersenne Twister 梅森旋转算法笔记 这一篇很详细

相关知识

​ 既然聊到随机数生成了，就会想到PRNG嘛，所以我觉得顺带联系一下流密码会更透彻一点，下面是一些联系知识点，可跳过直接看梅森旋转算法介绍。

流密码

​ 流密码是一种对称密码，一般逐字节或逐比特处理信息（比如说采用异或加密）。现有的流密码是在一次一密的思想基础上发展来的。

​ 一次一密（One-Time Pad，简称OTP）也是一种流密码算法，它被认为是理论上最安全的加密算法之一，它必须遵循以下原则：

  1. 密钥必须和明文一样长
  2. 密钥必须是真正随机的（我们可以采用真随机数发生器TRNG来生成）
  3. 密钥必须只使用一次
  4. 密钥必须保密（感觉有点废话）

​ 看上面这几条原则，很容易就可以想到密钥的管理是困难的。密钥和明文一样长，且每个都只使用一次，密钥的存储和共享十分困难，这在实际运用上是不现实的

​ 于是人们在试图解决一次一密密钥管理和长度的问题时，想到了能不能有一种方法，只需要提供一小段密钥，就可以生成加密明文所需要的所有密钥。流密码就在此思想上发展。

​ 在流密码中，一个小的密钥（通常称为种子或初始向量）被用来通过一个伪随机数生成器（PRNG）产生一个与明文等长的伪随机密钥流。这个密钥流然后与明文进行异或操作，生成密文。同样，解密过程就是用相同的密钥流对密文进行异或，恢复出明文。

​ 像我们学过的比较简单的流密码RC4、LCG(也都是PRNG生成算法)都是采用这种思想。(我的理解是，一种流密码，其实就是一种PRNG生成算法，毕竟加密一般就是异或嘛，所以还是要看伪随机数的生成)

PRNG

​ 我们将要了解的这个算法，其实就是一种用于生成PRNG（即伪随机数生成器 pseudo random number generator）的一种算法。与PRNG相对的就是TRNG(真随机数生成器)，这里不做过多介绍。

​ PRNG可以使用随机种子（和种子状态）从任意初始状态启动，使用同一状态进行初始化时，它将始终生成相同的序列。PRNG的周期定义为：序列的无重复前缀长度在所有起始状态中的最大值。周期受状态数的限制，通常用比特位数表示。然而，每增加一个比特位，周期长度就可能增加一倍，所以构建周期足够长的PRNG对于许多实际应用程序来说是很容易的。(感觉有点绕，但是目前只要知道，用相同的seed，会生成相同的序列就行了)

​ PRNG所生成的序列，其特性近似于随机数序列。具有以下特点：

  1. 确定性，相同的种子值会生成相同的序列
  2. 高效性，PRNG能快速产生大量随机数
  3. 周期性，PRNG会在一定周期后重复，但是现代PRNG算法这个周期是很长的

分类

目前通用的伪随机数生成器主要有

  • 线性同余生成器，LCG
  • 线性回归发生器
  • Mersenne Twister (梅森旋转算法)
  • xorshift generators
  • WELL family of generators
  • Linear feedback shift register，LFSR，线性反馈移位寄存器

​ 后面翻资料的时候发现还有一种密码学PRNG(CSPRNG)：密码学伪随机数生成器(Cryptographically Secure Pseudo-Random Number Generator, CSPRNG)，只能后面再去了解了。LFSR之前做题也有遇到，只能又鸽了

​ 知道这样一个框架后，就可以进入重头戏，PRNG的一种算法——梅森旋转算法

介绍

​ 梅森旋转算法，是由松本真和西村拓士在1997年开发的一种能快速产生优质随机数的算法。

它之所以叫做是梅森旋转算法是因为它的循环节是$ 2^{19937}-1 $，这个叫做梅森素数。这个循环节(就是循环周期，理解为经过多少次后会回到第一次的随机数)是很长的，这也是为什么这个算法可以产生优质的随机数。

​ 常见的两种形式为基于32位的MT19937-32和基于64位的MT19937-64(其实是状态向量里整数的位数的区别)，而python中的random库主要用的还是MT19937-32，所以我们主要理解一下这个

代码实现

​ MT19937 算法可分为三个部分

  1. 初始化
  2. 旋转状态
  3. 提取伪随机数
其中 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
33
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

​ 其实如果简单过一遍的话，还是好理解的，就是根据一个seed进行初始化624的状态向量，然后旋转（怎么旋转的有点扣不懂了，浅放一下），提取，每624次提取后再旋转

Randon库

​ 了解了基本的原理后，我们来看看Python中random库的诸如getrandbits这些函数的具体用法和小特性

​ python中内置的Random类就是采用了MT19937算法，每次生成的随机数都是32位的。getrandbits(32)方法可以获得一个32位随机数

1
2
3
4
5
import random

print(random.getrandbits(32))

# 4027601637

​ random.seed(a)：设置初始化随机种子，可输出相同随机数序列；a取整数或浮点数，不设置时默认以系统时间为种子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import random

print(random.getrandbits(32))

random.seed(32)
print(random.getrandbits(32))

random.seed(32)
print(random.getrandbits(32))


# 863923632
# 332524003
# 332524003

​ getrandbits(8)获得的是32位随机数的前8位，而在这之后再次使用getrandbits(8)获取的是下一个32位随机数的前8位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import random

random.seed(32)
print(hex(random.getrandbits(32))[2:])
print(hex(random.getrandbits(32))[2:])

random.seed(32)
print(hex(random.getrandbits(8))[2:])
print(hex(random.getrandbits(8))[2:])

# 13d1e9e3
# ed2ef1c1
# 13
# ed

​ getrandbits(64)则是两个32位随机数的拼接，倒序拼接

1
2
3
4
5
6
7
8
9
10
11
12
import random

random.seed(32)
print(hex(random.getrandbits(32))[2:])
print(hex(random.getrandbits(32))[2:])

random.seed(32)
print(hex(random.getrandbits(64))[2:])

# 13d1e9e3
# ed2ef1c1
# ed2ef1c113d1e9e3

​ 还需要注意，向高位生长时其实跟小于32位一样是从高位开始取。

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

random.seed(32)
print(hex(random.getrandbits(32))[2:])
print(hex(random.getrandbits(32))[2:])

random.seed(32)
print(hex(random.getrandbits(40))[2:])

# 13d1e9e3
# ed2ef1c1
# ed13d1e9e3

​ getstate()的用法（相对应的是setstate()）

1
2
3
4
5
6
7
import random
rng = random.Random()
rng.seed(32)

print(rng.getstate())

# (3, (2147483648, 2981664610, 82649134, 1807122176, 302157071, 755388178, 2623462981, 851257013, 216974233, 1073938670, 323755660, 2384483883, 1744767122, 3695390407, 52014645, 459371615, 3906083420, 609507109, 610977697, 567019764, 2613493387, 916367194, 1292648220, 4281430835, 603958090, 1085002086, 1076867180, 801231231, 3803349301, 2028653073, 1458283220, 1919772958, 2834427473, 145396400, 3423484661, 652682164, 18482579, 482317922, 500545892, 4262442629, 259966470, 1065747013, 4129843740, 117008655, 3356700754, 405228818, 2146344620, 904962943, 2335240969, 3483444628, 2812342939, 243772448, 4052954505, 974896576, 293524298, 2204846868, 3801875453, 1589429472, 3392403291, 1025270310, 1005772097, 3550127576, 1790752761, 1606443774, 1328005442, 3963248671, 2816323641, 3138536632, 4291349728, 1196288615, 3153400508, 3934718159, 2790896303, 2028649333, 1451545150, 1014986440, 4186142173, 4086045459, 661114379, 2368957789, 2266586516, 2421168059, 1870394660, 1982958283, 3465622627, 609333992, 2700947100, 4114189243, 22625788, 3176992568, 896225921, 2344820312, 922443065, 2853383903, 3030451356, 658221849, 3254595837, 3668447465, 3208004282, 1804923500, 3882158971, 84112801, 3275442855, 1713196384, 2078103568, 1624721945, 1420515015, 80757766, 3036199207, 3175701083, 1288786439, 3231940832, 10031906, 91060640, 2788052507, 2104768957, 2495796052, 1167365945, 839068315, 3781468505, 313744802, 2615503802, 1872999469, 3542740129, 3517369250, 3966272654, 3439320817, 55090350, 1933659639, 2179729091, 3112466017, 1175975703, 1828407681, 105582466, 3589634096, 2282048609, 2446991225, 2212241085, 1502806219, 1438997647, 2921640279, 3736656255, 2894637459, 351604790, 427967470, 3097656137, 2565447163, 2472848566, 3662806121, 2837288467, 1359216601, 1211006512, 2485534644, 3645695355, 1767676058, 601956087, 1543053032, 204820565, 4133788867, 1060908608, 3855049815, 4015536910, 2971584352, 56962322, 3546815736, 3310579232, 1181351349, 581872004, 1104445211, 3199855229, 584304768, 2857640007, 3963080308, 1918026254, 3557712257, 717957697, 2605576760, 2839901208, 4041967724, 3871933765, 3579478960, 3561335339, 3496241806, 3323555189, 4199989126, 443971454, 2759899833, 1251185906, 585248642, 842743147, 1391919910, 2861045395, 816948222, 198625549, 3781980984, 3239677416, 2046972831, 1850626891, 468850643, 3740899351, 1224863120, 1845712388, 1342062971, 768279889, 1567226079, 2584712143, 1114840832, 3761226868, 2193432879, 2374470972, 2577173949, 1557186029, 3873247469, 957872477, 2394080002, 4023827162, 4188217292, 839158856, 2090482280, 53463168, 83974694, 1724965904, 650741183, 2778336473, 4277063498, 1456658756, 456107739, 3462352155, 1575608861, 4018132647, 2432365576, 2715236919, 1225680973, 2863498653, 674890329, 3473172628, 411076689, 3215056284, 3821524280, 1184977003, 2582060598, 2527134872, 3351823467, 3172733736, 4048514431, 2671275640, 3193496925, 2433639562, 3928579687, 2813396580, 3812638932, 1416650140, 3600892096, 3232545207, 1250740885, 3363297892, 2000437280, 3804682658, 2547870510, 3332317444, 3486657292, 2882851682, 1938388214, 3034661023, 3991043770, 3483788369, 1512472737, 1908682443, 1059047586, 2243622793, 3524945907, 2404115663, 990882311, 2471221882, 3072200400, 876342782, 3903939525, 3905347388, 1935550924, 2891758942, 3521138013, 3005767809, 2999009524, 1327279939, 1943800407, 640427466, 3084536079, 700645511, 1338782426, 2264697014, 938935645, 344738163, 2311466192, 1637326701, 1102012914, 4173606536, 802682715, 3063116242, 3802425104, 2724672801, 2230711586, 2413750001, 4255139566, 3954170358, 1302721114, 2732170767, 1139306538, 3695422750, 3547144070, 716263268, 4172405440, 3438102401, 2148842670, 3896935059, 2275750532, 2861664676, 93639066, 4103591988, 2522391420, 657968115, 144916106, 2437447734, 473423694, 2562322086, 1739841119, 3749273316, 2527951928, 2469057797, 2469057171, 3552507765, 2547872402, 2169450804, 2197564692, 1459768138, 1148433842, 2132426770, 2063580222, 2993639595, 508642970, 1492817956, 57022243, 1351740882, 3749501729, 314095794, 3322120215, 1519460267, 2045234971, 2675305001, 3648397390, 3619021619, 3851936312, 647782153, 655145155, 1223393823, 3845890350, 1510800397, 3675627882, 1029945969, 2378074523, 1455919460, 1838312376, 3370926044, 4196546489, 1274041036, 3016742944, 82756560, 3915887215, 4019075249, 2298314253, 3304259580, 1343841177, 607522726, 639997923, 1674712318, 2135847655, 3101388171, 63191086, 2770135294, 2530192008, 2188475789, 1620366947, 3038817640, 1241763876, 3979640425, 383261701, 2325895137, 2378407688, 3054432273, 1097038754, 773664257, 2762497941, 979233138, 1506650225, 2022134751, 1129927790, 3476182076, 3054136278, 2761190690, 1595650873, 1514097467, 509019484, 2990680402, 171266122, 5794339, 3046940969, 3816395130, 2115717995, 1940568737, 3289974461, 733344441, 3926583596, 321505248, 1874286757, 3682533796, 1274702259, 198520217, 828123087, 3368592821, 1591619265, 2494285061, 404073469, 3738926862, 953789241, 4032511973, 2460730661, 1012375673, 585792413, 2819670610, 2229887984, 2374016081, 2431497255, 3789681296, 670884029, 3903410055, 3762586428, 2450275213, 242955591, 3312815380, 2247560084, 3188866986, 2953117091, 3734162145, 641332960, 587712331, 2185195334, 3270498270, 584022697, 1311493692, 1706387626, 2402043314, 2473770888, 2342620662, 3005544869, 3816857950, 391899607, 2822448002, 3450091114, 3266591578, 2631029892, 1793928024, 3708130896, 372142539, 3386509210, 3916907799, 3042854929, 3735328056, 2874161759, 1844089759, 1882687817, 904490032, 1737874898, 3691589734, 3795674018, 717188390, 3880627804, 3296223810, 3177630739, 553466201, 2607251041, 2402207612, 3912741292, 3544977279, 679344905, 2421023657, 429467538, 2735205380, 1932519125, 2038123701, 2376985142, 1043259972, 193599666, 1050430870, 4175957367, 29365306, 1751954589, 2578680403, 3420562479, 4267733734, 467600736, 3311162776, 3037951919, 3926437922, 3165928232, 1232517126, 3257628202, 3895439459, 1616722311, 3027645040, 2550116418, 4220643369, 3627886577, 3578677455, 3395485167, 3339674257, 3765213326, 765805494, 482486297, 3480301331, 3955880588, 798768951, 3693847025, 420701721, 1151767317, 3914711615, 2577577392, 1080158294, 332747221, 1279867472, 2707768266, 2786128928, 3748455533, 3522857857, 2453723104, 2744868592, 1237637661, 2933112744, 1878673409, 1018701131, 4209888015, 263654486, 3017122881, 2691524399, 1053756612, 1187424032, 3257603881, 2352354616, 60236961, 2328160652, 152703480, 2630697922, 2689232765, 825147421, 1673724729, 1493962066, 897352027, 175335306, 4005774659, 2318883597, 519865390, 1913890232, 821345729, 2269093420, 1528572181, 4185395893, 2493530055, 40668990, 2034577100, 1920819529, 1646347693, 322244438, 693268627, 2444591237, 2081602764, 2292388262, 1550027624, 3878242529, 198232945, 1502012648, 2518060143, 824807254, 3067952308, 1842732054, 3065158519, 89344625, 1147397791, 3154513321, 3827308929, 2558819632, 2314588350, 3021440071, 3764176503, 2394771812, 3635650757, 755749977, 3880150197, 1483850587, 2144701659, 2299027958, 3229625002, 2941244074, 4105623027, 2342673337, 633689222, 2627198003, 3389683863, 425091459, 648407162, 402334000, 2345289546, 212958946, 4140303075, 1446126212, 1946371200, 3708392064, 2694950657, 3644622098, 3545174953, 3705151558, 392923605, 330618321, 3854576478, 3936935861, 767734276, 2853918368, 624), None)

考点

​ 既然说了是伪随机数，那就说明是有一定规律的，所以我们期望可以通过一些手段来预测随机数

逆向extract_number

​ 大概理解了一下就是将extract_number过程逆向，看了一遍后是理解了，但是让我复述一遍有点难，但是试着来吧

​ 首先 y = y ^ y >> 18这一块，很明显是y和y右移18位后的结果异或，那么高位的18位就是没有变化的，所以我们可以把y_result右移18位后再和自己异或，就又复原了18位，依此类推就可以回退回去，大概是下图这样（图画的有点丑）

代码如下

1
2
3
4
5
6
7
8
9
10
o = 2080737669
print(o.bit_length())#31
y = o^o>>18
# 控制位移的次数
for i in range(31//18):
    y = y^(y>>18)
print(y==o)
#如果o的位数大于36那么代码还需要做修改
#但是实际上y的大小应该是固定的，32位数，所以这段代码可以固定使用

​ 接着我们看y = y ^ y << 15 & 4022730752这个过程，y和 y左移15位与上4022730752 的结果进行异或，相当于y_result的低位15位是原y与y左移15位（其实低位15位都是0）与上4022730752 的结果（图我画不出来，但是就是循环这个过程，低位15知道后再左移15位与上4022730752 ，就又可以知道15位，重复下去）

代码如下 
1
2
3
4
5
6
7
8
o = 2080737669
y = o ^ o << 15 & 4022730752
tmp = y
for i in range(32 // 15):
    # (y<<15)&40022730752 每次可以恢复y的15位
    y = tmp ^ y << 15 & 4022730752
print(y==o)

​ extract_number剩下的两个过程就是一样的分析过程了，这样extract_number就逆向完了

​ 其他几个逆向过程实在扣不动了，放个总代码吧（放过自己）

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
class MT19937Recover:
    def unshiftRight(self, x, shift):
        res = x
        for i in range(32):
            res = x ^ res >> shift
        return res

    def unshiftLeft(self, x, shift, mask):
        res = x
        for i in range(32):
            res = x ^ (res << shift & mask)
        return res

    def untemper(self, v):
        v = self.unshiftRight(v, 18)
        v = self.unshiftLeft(v, 15, 0xefc60000)
        v = self.unshiftLeft(v, 7, 0x9d2c5680)
        v = self.unshiftRight(v, 11)
        return v

    def go(self, outputs, forward=True):
        result_state = None

        assert len(outputs) >= 624

        ivals = []
        for i in range(624):
            ivals.append(self.untemper(outputs[i]))

        if len(outputs) >= 625:
            challenge = outputs[624]
            for i in range(1, 626):
                state = (3, tuple(ivals+[i]), None)
                r = random.Random()
                r.setstate(state)

                if challenge == r.getrandbits(32):
                    result_state = state
                    break
        else:
            result_state = (3, tuple(ivals+[624]), None)

        rand = random.Random()
        rand.setstate(result_state)

        if forward:
            for i in range(624, len(outputs)):
                assert rand.getrandbits(32) == outputs[i]

        return rand

mtc = MT19937Recover()

randcrack库进行预测

​ python中的randcrack库为我们提供了预测的函数，只要我们输入624个32位的数，就可以进行预测

1
2
3
4
5
6
7
8
import random #导入random库（Python内置了）
from randcrack import  RandCrack
#你可以掷随机数种子来确保预测的有效性， 不过random预测的时候默认以当前时间作为随机数种子
rc = RandCrack()#实例化randcrack类
for i in range(624):#循环624次
    rc.submit(random.getrandbits(32))#每次循环提交一个32位random生成的随机数
print(random.getrandbits(64))#利用random库获取一个64位的随机数（你可以修改为任意位数）
print(rc.predict_getrandbits(64))#利用randcrack获取的随机数

​ 但是这个库有个缺点就是必须提交624次，少一次都不行，而且必须是32位的，多一位都不行，具体可以看看下面这篇博客，进行了测试

https://blog.51cto.com/u_16099213/6895353

矩阵状态破解

​ 这个感觉特别巧妙，就是发现了最后的输出和初始状态之间的一个线性关系，然后通过矩阵求解

我们把初始状态state[i]表示为二进制

$ x_0x_1···x_{30}x_{31} $

然后我们把输出的随机数也用二进制表示

$ z_0z_1···z_{30}z_{31} $

二者之间存在以下关系

真不知道这是怎么发现的，只能说太厉害了

那么在GF(2)域上存在一个矩阵使得x变为z

即$ XT=Z $

下面是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def extract_number(x):
    x ^^= x >> 11
    x ^^= (x << 7) & 2636928640
    x ^^= (x << 15) & 4022730752
    x ^^= x >> 18
    return x & 0xffffffff

T = []
for i in range(32):
    x = 1 << (31 - i)
    x = extract_number(x)
    T.append(x.digits(2, padto=32)[::-1])
T = matrix(GF(2), T)

def untemper(leak):
    Z = matrix(GF(2), ZZ(leak).digits(2, padto=32)[::-1])
    X = T.solve_left(Z)
    return reduce(lambda x, y: (ZZ(x) << 1) + ZZ(y), list(X[0]))

​ 如果我们能拿到连续的 624 个输出（比如用 random.getrandbits(32) 连续取 624 次），就能： 

1
2
3
4
5
state = []
for _ in range(624):
    output = random.getrandbits(32)
    state.append(untemper(output))

从而恢复初始状态，然后进行预测

​ 然后在m1n9师傅博客上看到另一种脚本写法，思路应该是一样的，这里就直接搬过来喽

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
def construct_a_row(RNG): 
    row = []
    for _ in range(19968//32):
        tmp = RNG.getrandbits(32)
        row += list(map(int, bin(tmp)[2:].zfill(32)))
    return row
 
# 构造线性方程组的矩阵 
L = [] 
for i in trange(19968): 
    state = [0]*624  # MT19937使用624个32位整数作为状态 
    # 构造一个只有一位为1,其他都为0的序列 
    temp = "0"*i + "1"*1 + "0"*(19968-1-i) 
    # 将这个序列分成624段,每段32位,转换为整数 
    for j in range(624): 
        state[j] = int(temp[32*j:32*j+32], 2) 
     
    RNG = Random() 
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG)) 
 
# 将L转换为GF(2)上的矩阵（二进制域） 
L = Matrix(GF(2),L)
print(L.nrows(), L.ncols())
 
def MT19937_re(state): 
    try: 
        # 构造目标向量R 
        R = []
        for i in state:
            R += list(map(int, bin(i)[2:].zfill(32)))
         
        R = vector(GF(2), R)
        s = L.solve_left(R)  # 这里可能会抛出异常 
         
        # 将解转换为二进制字符串 
        init = "".join(list(map(str,s))) 
        state = [] 
        # 将解重新分割成624个32位整数 
        for i in range(624): 
            state.append(int(init[32*i:32*i+32],2)) 
 
        # 创建新的RNG并设置恢复出的状态 
        RNG1 = Random() 
        RNG1.setstate((3,tuple(state+[624]),None)) 
 
        return RNG1
         
    except Exception as e: 
        print(f"[-]{e}")
        pass
 
RNG = MT19937_re() # 这里传入state

详细可以上m1n9师傅博客查看

MT19937

暂时看到的就这么多了，其他的等之后补充了

题目

Division（xyctf 2025）

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
# -*- encoding: utf-8 -*-
'''
@File    :   server.py
@Time    :   2025/03/20 12:25:03
@Author  :   LamentXU 
'''
import random 
print('----Welcome to my division calc----')
print('''
menu:
      [1]  Division calc
      [2]  Get flag
''')
while True:
    choose = input(': >>> ')
    if choose == '1':
        try:
            denominator = int(input('input the denominator: >>> '))
        except:
            print('INPUT NUMBERS')
            continue
        nominator = random.getrandbits(32)
        if denominator == '0':
            print('NO YOU DONT')
            continue
        else:
            print(f'{nominator}//{denominator} = {nominator//denominator}')
    elif choose == '2':
        try:
            ans = input('input the answer: >>> ')
            rand1 = random.getrandbits(11000)
            rand2 = random.getrandbits(10000)
            correct_ans = rand1 // rand2
            if correct_ans == int(ans):
                print('WOW')
                with open('flag', 'r') as f:
                    print(f'Here is your flag: {f.read()}')
            else:
                print(f'NOPE, the correct answer is {correct_ans}')
        except:
            print('INPUT NUMBERS')
    else:
        print('Invalid choice')

​ 一道靶机题，correct_ans = rand1 // rand2这里告诉我们，要想得到flag，我们必须预测出11000位的数整除10000位数的结果，我们回头看random.getrandbits(32)就可以知道，我们有办法搞到624个32位结果，那么运用randcrack库很容易就可以进行预测，交互代码甚至是ai给我写的，解题代码如下

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
from pwn import *
from randcrack import RandCrack

# 启动本地进程（若为远程服务，替换为remote('host', port)）
proc = remote('host', port)

# 初始化随机数破解器

rc = RandCrack()
# 收集624个32位随机数样本
for _ in range(624):
    proc.sendlineafter(b': >>> ', b'1')               # 发送选项1（bytes格式）
    proc.sendlineafter(b'input the denominator: >>> ', b'1')  # 分母输入1
    line = proc.recvline().decode().strip()         # 接收输出并解析
    numerator = int(line.split('//')[0])
    rc.submit(numerator)

# 预测大随机数（使用predict_getrandbits）
rand1 = rc.predict_getrandbits(11000)  # 直接预测11000位随机数
rand2 = rc.predict_getrandbits(10000)  # 直接预测10000位随机数
correct_ans = rand1 // rand2

# 提交答案获取flag
proc.sendlineafter(b': >>> ', b'2')
proc.sendlineafter(b'input the answer: >>> ', str(correct_ans).encode())

proc.interactive()

'''
WOW
Here is your flag: XYCTF{3bb2de1f-5bb3-486a-8da4-d1df6629067b}
'''

总结

写了两三天总算写完，但是应该还是不全，之后看有空再修修补补吧，不过总算了解了这么一个东西吧，道阻且长捏