MT19937算法

这里学习一种新的算法：梅森旋转算法（Mersenne Twister），产生随机数的速度快，周期长，周期可以达到$2^{19937}-1$。

特点：产生32位整数序列，能在$1≤k≤623$的维度之间均等分布。

python的random库的函数getrandbits()就是利用了MT19937算法，函数getrandbits(32)就是生成32位随机数。

下面是MT19937-32的生成代码：

__init__可以意为initialize（初始化），理解为实例化出某个类的对象时调用的初始化方法，例如定义一些变量供后面的其它方法使用。

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
# 返回一个32位二进制代码
def _int32(x):
    return int(0xFFFFFFFF & x)
 
class MT19937:
    # 根据seed初始化624的state，seed为种子
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        # 623个循环为通过state之间的变换求出剩下的state块
        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)
 
    # 对state进行旋转求得新的624个不同的state值进入新循环
    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

种子：以一个真随机数（种子）作为初始条件，然后用一定的算法不停迭代产生伪随机数。

注意到MT算法生成的是32位随机数序列。首先需要一个种子，然后生成有624个32位数组的状态数组，然后进行一次旋转，输出624个随机的int32，重复执行。

随机数生成方式

针对不是32位等情况的随机数的生成，它的生成方式也存在着一些规律，举几个例子：

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

for i in range(1,33):
    #确定好生成随机数的种子，可以保证生成随机数的顺序一致
    seed(64)
    print(bin(getrandbits(i))[2:],i)

'''
0 1
1 2
11 3
111 4
1111 5
11110 6
111100 7
1111001 8
11110011 9
111100111 10
1111001111 11
11110011110 12
111100111100 13
1111001111001 14
11110011110010 15
111100111100101 16
1111001111001011 17
11110011110010110 18
111100111100101100 19
1111001111001011000 20
11110011110010110000 21
111100111100101100000 22
1111001111001011000001 23
11110011110010110000010 24
111100111100101100000100 25
1111001111001011000001000 26
11110011110010110000010000 27
111100111100101100000100001 28
1111001111001011000001000011 29
11110011110010110000010000110 30
111100111100101100000100001100 31
1111001111001011000001000011000 32
'''

这里我们以64作为种子来生成1-32位的随机数，由于每次生成之前都重置一遍种子，所以保证接下来生成的随机数都是相同变换后的首个32位随机数，可以看到对于不满足32位的随机数，生成时从32位的序列的高位往低位截取对应的位数作为这个位数的随机数。发现实际上这里生成的每个随机数都要比位数少1位，是因为在最前面省略了这轮序列的首位0，这个32位随机数应该是01111001111001011000001000011000。

MT19937算法是如何生成更高位的随机数的呢？根据上面的理论继续扩大生成位数：

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

for i in range(1,65):
    seed(64)
    print(bin(getrandbits(i))[2:],i)

'''
0 1
1 2
11 3
111 4
1111 5
11110 6
111100 7
1111001 8
11110011 9
111100111 10
1111001111 11
11110011110 12
111100111100 13
1111001111001 14
11110011110010 15
111100111100101 16
1111001111001011 17
11110011110010110 18
111100111100101100 19
1111001111001011000 20
11110011110010110000 21
111100111100101100000 22
1111001111001011000001 23
11110011110010110000010 24
111100111100101100000100 25
1111001111001011000001000 26
11110011110010110000010000 27
111100111100101100000100001 28
1111001111001011000001000011 29
11110011110010110000010000110 30
111100111100101100000100001100 31
1111001111001011000001000011000 32
1111001111001011000001000011000 33
1111001111001011000001000011000 34
1111001111001011000001000011000 35
101111001111001011000001000011000 36
1101111001111001011000001000011000 37
11101111001111001011000001000011000 38
111101111001111001011000001000011000 39
1111101111001111001011000001000011000 40
11111101111001111001011000001000011000 41
111111101111001111001011000001000011000 42
1111111101111001111001011000001000011000 43
11111111101111001111001011000001000011000 44
111111111001111001111001011000001000011000 45
1111111110101111001111001011000001000011000 46
11111111101101111001111001011000001000011000 47
111111111011001111001111001011000001000011000 48
1111111110110001111001111001011000001000011000 49
11111111101100001111001111001011000001000011000 50
111111111011000101111001111001011000001000011000 51
1111111110110001101111001111001011000001000011000 52
11111111101100011101111001111001011000001000011000 53
111111111011000111101111001111001011000001000011000 54
1111111110110001111001111001111001011000001000011000 55
11111111101100011110001111001111001011000001000011000 56
111111111011000111100001111001111001011000001000011000 57
1111111110110001111000001111001111001011000001000011000 58
11111111101100011110000001111001111001011000001000011000 59
111111111011000111100000001111001111001011000001000011000 60
1111111110110001111000000001111001111001011000001000011000 61
11111111101100011110000000001111001111001011000001000011000 62
111111111011000111100000000001111001111001011000001000011000 63
1111111110110001111000000000101111001111001011000001000011000 64
'''

可以直接挑中间几行来看：

1
2
3
4
5
6
7
8
9
10
1111001111001011000001000011 29
11110011110010110000010000110 30
111100111100101100000100001100 31
1111001111001011000001000011000 32
1111001111001011000001000011000 33
1111001111001011000001000011000 34
1111001111001011000001000011000 35
101111001111001011000001000011000 36
1101111001111001011000001000011000 37
11101111001111001011000001000011000 38

事先知道第一个32位序列的首位为0，根据之前生成第一组序列的方式可以推测第二组也应该是高位往低位截取对应的位数，这里生成33-35位卡住没有增加位数的原因是第二组getrandbits(32)序列的首位连续为0，在生成36位随机数时，得到了第二个序列的1同时补齐了第一个序列的首位0，接下来继续补齐低位的位数，最终得到64位两个完整的序列时这里只为61位，因为第二个序列开头存在3个0没有显示。

这样可以得知64位甚至更高位的随机数的生成方式：生成64位随机数时首先生成2个32位，第二个数左移32位加上第一个数，得到这个随机数，验证一下：

1
2
3
4
5
6
7
8
import random
 
random.seed(1)
a,b=random.getrandbits(32),random.getrandbits(32)
print((b<<32)+a)#10499958131665514997

random.seed(1)
print(random.getrandbits(64))#10499958131665514997

此外，也能发现利用getrandbits(32)生成的随机数，不是总能生成真正的32位随机数，因为序列的最高位不确定是否为0，为0的话也不知道有几个0，所以也能得到31,30,29甚至更低位的随机数：

1
2
3
4
5
6
import random

while 1:
    a=int(random.getrandbits(32))
    if a.bit_length()!=32:
        print(a.bit_length())

下面来看几道实际的题目来加深一下对随机数的理解：

[GKCTF 2021]Random

这道题就利用了MT19937随机数的破解：

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
from hashlib import md5
 
def get_mask():
    file = open("random.txt","w")
    for i in range(104):
        file.write(str(random.getrandbits(32))+"\n")
        file.write(str(random.getrandbits(64))+"\n")
        file.write(str(random.getrandbits(96))+"\n")
    file.close()
get_mask()
flag = md5(str(random.getrandbits(32)).encode()).hexdigest()
print(flag)
1
2
3
4
5
6
7
8
9
10
11
12
13
2584323193
1099154419438958164
35367876945070316311325317953
481304047
12782770146993102006
24789628292419559503661788402
2776391832
9046887565683900291
50006261016517120573540241998
4167723109
8540277546428614473
5932047064656933473553742683
#共104组，每组3个数据

题目随机数全部为32位整数序列产生，32位需要1个随机数，64位需要2个随机数，96位需要3个随机数，题目所给信息总共需要624个随机数，就对应了state块的个数，所以需要推算出624个state块的状态，进而推出接下来产生的随机数，得到flag。

randcrack库可以帮助我们直接得到原始的state。

所以，首先我们可以把给我们的这些数全部转为32位随机数，共624个，可以利用之前学过的位运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
with open("random.txt",'r') as f:
    f=f.readlines()
num=[]
num1=[int(i) for i in f]
t=0
for i in num1:
    if t%3==0:
        num.append(i)
    elif t%3==1:
        num.append(i&(2**32-1))
        num.append(i>>32)
    else:
        num.append(i&(2**32-1))
        num.append(i>>32 & (2**32-1))
        num.append(i>>64)
    t+=1

得到了这组随机数之后可以利用randcrack直接得到flag：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import hashlib
from randcrack import RandCrack

with open("random.txt",'r') as f:
    f=f.readlines()
num=[]
num1=[int(i) for i in f]
t=0
for i in num1:
    if t%3==0:
        num.append(i)
    elif t%3==1:
        num.append(i&(2**32-1))
        num.append(i>>32)
    else:
        num.append(i&(2**32-1))
        num.append(i>>32 & (2**32-1))
        num.append(i>>64)
    t+=1
r = RandCrack()
for i in num:
    r.submit(i)
flag = r.predict_getrandbits(32)
print('flag{'+hashlib.md5(str(flag).encode()).hexdigest()+"}")

当然，不用randcrack库直接用random库推也可以，代码就是直接利用MT算法来推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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from random import Random

def invert_right(m,l,val=''):
    length = 32
    mx = 0xffffffff
    if val == '':
        val = mx
    i,res = 0,0
    while i*l<length:
        mask = (mx<<(length-l)&mx)>>i*l
        tmp = m & mask
        m = m^tmp>>l&val
        res += tmp
        i += 1
    return res

def invert_left(m,l,val):
    length = 32
    mx = 0xffffffff
    i,res = 0,0
    while i*l < length:
        mask = (mx>>(length-l)&mx)<<i*l
        tmp = m & mask
        m ^= tmp<<l&val
        res |= tmp
        i += 1
    return res

def invert_temper(m):
    m = invert_right(m,18)
    m = invert_left(m,15,4022730752)
    m = invert_left(m,7,2636928640)
    m = invert_right(m,11)
    return m

def clone_mt(record):
    state = [invert_temper(i) for i in record]
    gen = Random()
    gen.setstate((3,tuple(state+[0]),None))
    return gen

f = open("random.txt",'r').readlines()
prng = []
j=0
for i in f:
    i = i.strip('\n')
    print(int(i).bit_length())
    #分离随机数
    if(j%3==0):
        prng.append(int(i))
    elif(j%3==1):
        prng.append(int(i)& (2 ** 32 - 1))
        prng.append(int(i)>> 32)
    else:
        prng.append(int(i)& (2 ** 32 - 1))
        prng.append(int(i)& (2 ** 64 - 1) >> 32)
        prng.append(int(i)>>64)
    j+=1
g = clone_mt(prng[:624])
for i in range(624):
    g.getrandbits(32)#产生前624个随机数，让state状态到生成flag前
key = g.getrandbits(32)
print(key)
from hashlib import md5
flag = md5(str(key).encode()).hexdigest()
print(flag)
#14c71fec812b754b2061a35a4f6d8421

PRNG(pseudorandom number generator)伪随机数生成器是指通过特定算法生成一系列的数字，使得这一系列的数字看起来是随机的，但是实际是确定的，所以叫伪随机数。

[HGAME 2022 week4]PRNG

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
import re
from random import randrange
from libnum import s2n
from secret import flag

class PRNG:
    def __init__(self, seed = 0):
        self.__register = [0] * 624
        self.__state = 0
        self.__register[0] = seed
        for i in range(1, 624):
            prev = self.__register[i - 1]
            temp = 0x6c078965 * (prev ^ (prev >> 30)) + i
            self.__register[i] = temp & 0xffffffff

    def __call__(self):
        if self.__state == 0:
            for i in range(624):
                y = (self.__register[i] & 0x80000000) + (self.__register[(i + 1) % 624] & 0x7fffffff)
                self.__register[i] = self.__register[(i + 397) % 624] ^ (y >> 1)
                if y % 2:
                    self.__register[i] ^= 0x9908b0df
        y = self.__register[self.__state]
        y = y ^ (y >> 11)
        y = y ^ (y << 7) & 0x9d2c5680
        y = y ^ (y << 15) & 0xefc60000
        y = y ^ (y >> 18)
        self.__state = (self.__state + 1) % 624
        return y

    def load_register(self,register):
        self.__register = register

mt = PRNG(randrange(0, 1 << 32))
print([mt() for _ in range(624)])
print([part ^ mt() for part in map(s2n, re.findall(".{1,4}", flag))])

'''
[888058162, 3094055443, 1404990361, 1012543603, 448723884, 2580444236, 201608779, 1062995809, 1348787313, 2980019361, 2245025385, 494977308, 4042503808, 275744301, 406611131, 142226472, 3871761759, 3888795536, 2617489687, 1220227074, 342928858, 3728958896, 1477077966, 1433151407, 1119405037, 330145973, 3547181160, 2123007249, 3739964132, 1794129718, 2739743522, 2291585121, 3013727731, 1536788463, 247633572, 408079265, 3025555185, 1604681922, 2848997116, 3646041955, 1059445774, 2849764176, 2638965889, 1232303180, 759521642, 2257008531, 3932082254, 1052428413, 4017559916, 3505694223, 1418363972, 477751107, 4266295945, 3832138928, 245251422, 1964323108, 2453472918, 3029032760, 323619451, 2548825339, 3410027991, 278143595, 816124107, 245705463, 4173686519, 4100831820, 3599257115, 2274885516, 3954736394, 198254482, 1050449178, 3933150558, 899220021, 597474632, 1823539097, 3340511318, 2144918682, 2310527451, 264391694, 69923676, 3266017310, 3199627722, 4035962745, 932969905, 2832951013, 2182887504, 1374919242, 2978944795, 1840647233, 3510878043, 3250544991, 4255542321, 804377010, 1286980519, 1980427321, 2893246724, 1745353148, 1406140332, 4101848568, 3227434698, 1869729934, 2638181242, 1270111849, 2387910792, 3411542702, 2793303435, 2455337459, 2802808043, 2418872990, 1043274549, 144911746, 2312236858, 780373658, 1527499811, 3402753408, 2617924770, 1659648360, 2714315441, 4202103851, 244677433, 1963258902, 3851363324, 3454195559, 813228826, 3944899734, 3697685234, 1613584167, 1874570879, 1592343033, 4194241173, 551902434, 3460909265, 4122075287, 176665387, 152849760, 3593212904, 952880017, 1793357635, 2052902220, 807859486, 334839380, 3485132343, 2113403566, 3259106798, 1443078482, 2434820318, 1347902400, 2344061487, 141766876, 2641586235, 287277458, 2385094526, 1510128758, 348957861, 2861038633, 1135611795, 4289024199, 1021202791, 2460872523, 3837050794, 4092005952, 52622948, 387056916, 3102913460, 4098715316, 154916530, 2890197932, 1441566957, 2368779800, 271808452, 3566810840, 2227022452, 316480679, 603893066, 2121889912, 4208763743, 3098334580, 721958838, 3848020801, 1029884135, 832405094, 2276817394, 981553190, 246940442, 1069231974, 3275216531, 58945988, 4100121200, 230446475, 2396021649, 4608139, 3468707911, 3249498323, 315898153, 3280797960, 388108494, 1110548082, 2357147660, 2336724751, 4047583630, 2108667879, 2784078579, 1170844412, 3920262445, 3564073655, 590490534, 1645945278, 2487463163, 434409966, 1563546251, 888601967, 1913513318, 1327448740, 2504517969, 304688984, 1443685450, 4040619940, 3601250858, 4097529433, 4260590151, 575843085, 1114360271, 2186035374, 2821388594, 3763206347, 4283149630, 4097168778, 1924538037, 3272064650, 1689166701, 1352331676, 520525342, 2954296222, 2629516330, 3674317458, 231784130, 1930132422, 4169222397, 1638784833, 1245667959, 1253759350, 1154928813, 66021172, 3217915692, 4159785573, 3798512628, 2945489695, 700725579, 3940231312, 1960713279, 3289722468, 2970919839, 1356139680, 1141841193, 629177162, 3696263539, 1084872874, 4294077062, 1115547807, 3421092527, 611575307, 7808529, 2784523837, 1267307982, 1538837032, 4038330055, 3262951566, 3139820067, 1249725729, 757191354, 3025188720, 291705345, 575676661, 3023956263, 1045504889, 205204207, 1777650027, 1956698897, 996147619, 1470431, 2275722398, 2666078800, 470333070, 1306693906, 2968672077, 2476023772, 2645573325, 3939390068, 2874886754, 4226430090, 2290851636, 3707585663, 109770347, 127373916, 815817847, 1565834917, 636869794, 4062053412, 583594822, 3782553071, 3293311273, 2801932604, 2647080862, 1514083254, 3534640458, 342361004, 3266111849, 2157351044, 1851728420, 3412596866, 2793236910, 3758306563, 1799548561, 952631672, 912455646, 2894404493, 2194084105, 119615608, 2071058651, 1524462411, 900936180, 3697554830, 3501838982, 2874465656, 2501478689, 1069024222, 3135689372, 1168458702, 1966524629, 36400028, 2704775319, 4030739700, 3985599923, 2778920518, 2669538325, 1951594393, 795749079, 665593501, 3007338649, 1535343068, 2031873237, 3202423789, 560224943, 1290838890, 2545130826, 695695377, 3048615291, 1957903923, 1986693779, 2594986519, 3396211122, 2625687092, 575329062, 2852671310, 3472799759, 715985207, 1660331651, 958648594, 305711662, 75621441, 548447557, 2473842353, 2110558182, 3321750402, 2415793078, 815198061, 1258834500, 972966677, 3267046345, 2923564883, 518207679, 1662309775, 278933232, 4294256390, 2444117793, 2241879973, 3915962245, 3836532482, 3449260219, 1092128833, 3177300913, 874588042, 1185436845, 2064537788, 364292705, 3802247898, 3122264959, 186651829, 2789447523, 797964681, 897671294, 1504956985, 2294012382, 3916152546, 177325516, 2741945226, 4188655695, 2738134558, 557326292, 1625014790, 2945266389, 1843516240, 644046640, 3853456819, 3456105042, 3467742754, 2885173326, 812088996, 1238970324, 766072156, 2675925963, 1667463511, 2808303112, 1638756770, 260047996, 1117661655, 346883777, 2268712532, 1904918136, 513102466, 1024624509, 2154277089, 4147814745, 3681688842, 2233642964, 3135674550, 1259551210, 3286048484, 4271168802, 4227197378, 3310884772, 2063705584, 791399172, 4069266828, 1511606526, 1047713396, 615906401, 2805111822, 499223767, 740832370, 351782725, 2258776891, 1837046713, 3969757168, 2873152110, 4214869805, 3416771254, 2527945969, 3279116532, 1217038009, 4014402228, 3696705795, 1877774112, 3928347956, 959715122, 1612979629, 4045688071, 2403021083, 424891533, 1887765641, 2090726432, 2897940431, 268403838, 3447542890, 575011346, 2559143209, 532649938, 3625398853, 2077769196, 1598653066, 3104923961, 3594500739, 675029389, 579180583, 2024117612, 1351780728, 654841863, 769835263, 1431012736, 2369300321, 4157341752, 1968305076, 2086919554, 3075265115, 2128974418, 3144501489, 3993066430, 1121959765, 1373765135, 4232964375, 2264170351, 11814235, 1797654983, 3382686935, 2541491040, 3540726136, 1330685654, 4123114026, 2521290625, 3357439706, 3331159097, 2298656231, 3446738535, 290996369, 3020977553, 849241175, 3469792522, 4119898263, 1339695718, 2125209134, 3620160106, 1063375386, 1656465852, 2505508266, 3958528861, 3497875682, 3112358345, 3675237811, 1109625127, 2672368219, 1983461371, 3579663373, 1969195060, 225618775, 653511251, 3508369415, 4127429853, 828877800, 4286770015, 1474706143, 870777512, 804917422, 3913439258, 2433991646, 2742831709, 4289045475, 2899508500, 185462457, 4178107803, 2671443073, 2701796854, 1170522896, 1599880638, 1410722361, 3977867960, 1263177666, 2159508450, 2704509681, 1540819416, 1836499452, 1667451095, 3799477506, 157146600, 3717470672, 89865758, 3815588203, 1929105788, 861643665, 684514017, 3519778437, 2712956097, 1004423983, 1540346552, 2617389519, 2754800020, 870994822, 1702399767, 3526294475, 3251290865, 2365820957, 1915675760, 1828371367, 3737352795, 2511512700, 1080446781, 2565191059, 2412448535, 3719988291, 1434643780, 4163492408, 1359345746, 1457543102, 2389534435, 2800945892, 2646700564, 1719588203, 999665519, 3120652917, 1800116770, 3247314137, 4261164550, 1503462948, 3017762189, 263481701, 1754772485, 869168639, 604192231, 498759780, 2602535702, 3346756344, 2836267314, 2073734260, 3445425559, 4051271696, 1647518162, 401835417, 1968629992, 2854677838, 2381566661, 3144829468, 519547510, 3058642603, 3944140819, 1248923220, 1050321901, 3218172519, 376999645, 184187381, 3837095155, 3363256702, 751966993, 3419533016, 4028456468, 1156797460]
[3437104340, 508103176, 1635844121, 878522509, 1923790547, 1727955782, 1371509208, 3182873539, 156878129, 1757777801, 1472806960, 3486450735, 2307527058, 2950814692, 1817110380, 372493821, 729662950, 2366747255, 774823385, 387513980, 1444397883]
'''

代码print([part ^ mt() for part in map(s2n, re.findall(".{1,4}", flag))])这行代码中的.{1,4}对flag做了切割处理，四个字符分一组，剩下的如果不少于1个字符的再额外分一组，举个例子：

1
2
3
4
5
import re

flag='flag{randcrack_mt19937}'
print(re.findall(".{1,4}", flag))
#['flag', '{ran', 'dcra', 'ck_m', 't199', '37}']

这题所以也是基于MT19937的一道题，他已经给我们生成了624个随机数，之后的随机数和分块的flag进行了异或运算，我们得到之后的随机数之后直接异或运算即可求得flag，非常简单：

1
2
3
4
5
6
7
8
9
10
11
from randcrack import RandCrack
from Crypto.Util.number import *

m=[888058162, 3094055443, 1404990361, 1012543603, 448723884, 2580444236, 201608779, 1062995809, 1348787313, 2980019361, 2245025385, 494977308, 4042503808, 275744301, 406611131, 142226472, 3871761759, 3888795536, 2617489687, 1220227074, 342928858, 3728958896, 1477077966, 1433151407, 1119405037, 330145973, 3547181160, 2123007249, 3739964132, 1794129718, 2739743522, 2291585121, 3013727731, 1536788463, 247633572, 408079265, 3025555185, 1604681922, 2848997116, 3646041955, 1059445774, 2849764176, 2638965889, 1232303180, 759521642, 2257008531, 3932082254, 1052428413, 4017559916, 3505694223, 1418363972, 477751107, 4266295945, 3832138928, 245251422, 1964323108, 2453472918, 3029032760, 323619451, 2548825339, 3410027991, 278143595, 816124107, 245705463, 4173686519, 4100831820, 3599257115, 2274885516, 3954736394, 198254482, 1050449178, 3933150558, 899220021, 597474632, 1823539097, 3340511318, 2144918682, 2310527451, 264391694, 69923676, 3266017310, 3199627722, 4035962745, 932969905, 2832951013, 2182887504, 1374919242, 2978944795, 1840647233, 3510878043, 3250544991, 4255542321, 804377010, 1286980519, 1980427321, 2893246724, 1745353148, 1406140332, 4101848568, 3227434698, 1869729934, 2638181242, 1270111849, 2387910792, 3411542702, 2793303435, 2455337459, 2802808043, 2418872990, 1043274549, 144911746, 2312236858, 780373658, 1527499811, 3402753408, 2617924770, 1659648360, 2714315441, 4202103851, 244677433, 1963258902, 3851363324, 3454195559, 813228826, 3944899734, 3697685234, 1613584167, 1874570879, 1592343033, 4194241173, 551902434, 3460909265, 4122075287, 176665387, 152849760, 3593212904, 952880017, 1793357635, 2052902220, 807859486, 334839380, 3485132343, 2113403566, 3259106798, 1443078482, 2434820318, 1347902400, 2344061487, 141766876, 2641586235, 287277458, 2385094526, 1510128758, 348957861, 2861038633, 1135611795, 4289024199, 1021202791, 2460872523, 3837050794, 4092005952, 52622948, 387056916, 3102913460, 4098715316, 154916530, 2890197932, 1441566957, 2368779800, 271808452, 3566810840, 2227022452, 316480679, 603893066, 2121889912, 4208763743, 3098334580, 721958838, 3848020801, 1029884135, 832405094, 2276817394, 981553190, 246940442, 1069231974, 3275216531, 58945988, 4100121200, 230446475, 2396021649, 4608139, 3468707911, 3249498323, 315898153, 3280797960, 388108494, 1110548082, 2357147660, 2336724751, 4047583630, 2108667879, 2784078579, 1170844412, 3920262445, 3564073655, 590490534, 1645945278, 2487463163, 434409966, 1563546251, 888601967, 1913513318, 1327448740, 2504517969, 304688984, 1443685450, 4040619940, 3601250858, 4097529433, 4260590151, 575843085, 1114360271, 2186035374, 2821388594, 3763206347, 4283149630, 4097168778, 1924538037, 3272064650, 1689166701, 1352331676, 520525342, 2954296222, 2629516330, 3674317458, 231784130, 1930132422, 4169222397, 1638784833, 1245667959, 1253759350, 1154928813, 66021172, 3217915692, 4159785573, 3798512628, 2945489695, 700725579, 3940231312, 1960713279, 3289722468, 2970919839, 1356139680, 1141841193, 629177162, 3696263539, 1084872874, 4294077062, 1115547807, 3421092527, 611575307, 7808529, 2784523837, 1267307982, 1538837032, 4038330055, 3262951566, 3139820067, 1249725729, 757191354, 3025188720, 291705345, 575676661, 3023956263, 1045504889, 205204207, 1777650027, 1956698897, 996147619, 1470431, 2275722398, 2666078800, 470333070, 1306693906, 2968672077, 2476023772, 2645573325, 3939390068, 2874886754, 4226430090, 2290851636, 3707585663, 109770347, 127373916, 815817847, 1565834917, 636869794, 4062053412, 583594822, 3782553071, 3293311273, 2801932604, 2647080862, 1514083254, 3534640458, 342361004, 3266111849, 2157351044, 1851728420, 3412596866, 2793236910, 3758306563, 1799548561, 952631672, 912455646, 2894404493, 2194084105, 119615608, 2071058651, 1524462411, 900936180, 3697554830, 3501838982, 2874465656, 2501478689, 1069024222, 3135689372, 1168458702, 1966524629, 36400028, 2704775319, 4030739700, 3985599923, 2778920518, 2669538325, 1951594393, 795749079, 665593501, 3007338649, 1535343068, 2031873237, 3202423789, 560224943, 1290838890, 2545130826, 695695377, 3048615291, 1957903923, 1986693779, 2594986519, 3396211122, 2625687092, 575329062, 2852671310, 3472799759, 715985207, 1660331651, 958648594, 305711662, 75621441, 548447557, 2473842353, 2110558182, 3321750402, 2415793078, 815198061, 1258834500, 972966677, 3267046345, 2923564883, 518207679, 1662309775, 278933232, 4294256390, 2444117793, 2241879973, 3915962245, 3836532482, 3449260219, 1092128833, 3177300913, 874588042, 1185436845, 2064537788, 364292705, 3802247898, 3122264959, 186651829, 2789447523, 797964681, 897671294, 1504956985, 2294012382, 3916152546, 177325516, 2741945226, 4188655695, 2738134558, 557326292, 1625014790, 2945266389, 1843516240, 644046640, 3853456819, 3456105042, 3467742754, 2885173326, 812088996, 1238970324, 766072156, 2675925963, 1667463511, 2808303112, 1638756770, 260047996, 1117661655, 346883777, 2268712532, 1904918136, 513102466, 1024624509, 2154277089, 4147814745, 3681688842, 2233642964, 3135674550, 1259551210, 3286048484, 4271168802, 4227197378, 3310884772, 2063705584, 791399172, 4069266828, 1511606526, 1047713396, 615906401, 2805111822, 499223767, 740832370, 351782725, 2258776891, 1837046713, 3969757168, 2873152110, 4214869805, 3416771254, 2527945969, 3279116532, 1217038009, 4014402228, 3696705795, 1877774112, 3928347956, 959715122, 1612979629, 4045688071, 2403021083, 424891533, 1887765641, 2090726432, 2897940431, 268403838, 3447542890, 575011346, 2559143209, 532649938, 3625398853, 2077769196, 1598653066, 3104923961, 3594500739, 675029389, 579180583, 2024117612, 1351780728, 654841863, 769835263, 1431012736, 2369300321, 4157341752, 1968305076, 2086919554, 3075265115, 2128974418, 3144501489, 3993066430, 1121959765, 1373765135, 4232964375, 2264170351, 11814235, 1797654983, 3382686935, 2541491040, 3540726136, 1330685654, 4123114026, 2521290625, 3357439706, 3331159097, 2298656231, 3446738535, 290996369, 3020977553, 849241175, 3469792522, 4119898263, 1339695718, 2125209134, 3620160106, 1063375386, 1656465852, 2505508266, 3958528861, 3497875682, 3112358345, 3675237811, 1109625127, 2672368219, 1983461371, 3579663373, 1969195060, 225618775, 653511251, 3508369415, 4127429853, 828877800, 4286770015, 1474706143, 870777512, 804917422, 3913439258, 2433991646, 2742831709, 4289045475, 2899508500, 185462457, 4178107803, 2671443073, 2701796854, 1170522896, 1599880638, 1410722361, 3977867960, 1263177666, 2159508450, 2704509681, 1540819416, 1836499452, 1667451095, 3799477506, 157146600, 3717470672, 89865758, 3815588203, 1929105788, 861643665, 684514017, 3519778437, 2712956097, 1004423983, 1540346552, 2617389519, 2754800020, 870994822, 1702399767, 3526294475, 3251290865, 2365820957, 1915675760, 1828371367, 3737352795, 2511512700, 1080446781, 2565191059, 2412448535, 3719988291, 1434643780, 4163492408, 1359345746, 1457543102, 2389534435, 2800945892, 2646700564, 1719588203, 999665519, 3120652917, 1800116770, 3247314137, 4261164550, 1503462948, 3017762189, 263481701, 1754772485, 869168639, 604192231, 498759780, 2602535702, 3346756344, 2836267314, 2073734260, 3445425559, 4051271696, 1647518162, 401835417, 1968629992, 2854677838, 2381566661, 3144829468, 519547510, 3058642603, 3944140819, 1248923220, 1050321901, 3218172519, 376999645, 184187381, 3837095155, 3363256702, 751966993, 3419533016, 4028456468, 1156797460]
c=[3437104340, 508103176, 1635844121, 878522509, 1923790547, 1727955782, 1371509208, 3182873539, 156878129, 1757777801, 1472806960, 3486450735, 2307527058, 2950814692, 1817110380, 372493821, 729662950, 2366747255, 774823385, 387513980, 1444397883]

r = RandCrack()
for i in m:
    r.submit(i)
for i in c:
    print(long_to_bytes(i^r.predict_getrandbits(32)).decode(),end='')

[HNCTF 2022 WEEK4]random

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import *
from flag import flag
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

f = open('output.txt','w')

for i in range(666):
    f.write(f'{getrandbits(32)}\n')
f.close()

r = getrandbits(32)
key = bytes.fromhex(hex(r)[2:])
key = md5(key).digest()
cipher = AES.new(key,AES.MODE_CBC)
c = cipher.encrypt(pad(flag,16))
print(f'c = \'{cipher.iv.hex() + c.hex()}\'')

#c = '91fd1824ddc0a35e845e87f59e53a103334df418e6a65a7d7769699c3ca2119019361cd23a46a61d4e7f6cdff5f5200f586f90b66eabfd8ecff4ddf11ee444d37f80ada0bbe8af09e4fc32c1a51e3f29e2771b51c71d2ba4acb84fda61904b96'

这题用了AES-CBC加密，需要用随机数预测得到key进行解密，给了666个数，用不着那么多，省去前面一部分即可，还是用randcrack：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from randcrack import RandCrack
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *

with open('output.txt','r') as f:
    f=f.readlines()
    num=[int(i) for i in f]
    r = RandCrack()
    for i in range(666-624,666):
        r.submit(num[i])
    k = r.predict_getrandbits(32)
    key = bytes.fromhex(hex(k)[2:])
    key = md5(key).digest()
    iv=long_to_bytes(0x91fd1824ddc0a35e845e87f59e53a103)
    cipher = AES.new(key,AES.MODE_CBC,iv)
    c=long_to_bytes(0x334df418e6a65a7d7769699c3ca2119019361cd23a46a61d4e7f6cdff5f5200f586f90b66eabfd8ecff4ddf11ee444d37f80ada0bbe8af09e4fc32c1a51e3f29e2771b51c71d2ba4acb84fda61904b96)
    flag = cipher.decrypt(pad(c,16))
    print(flag)