MT19937（梅森旋转）实践训练
MT19937（梅森旋转算法（Mersenne Twister Algorithm，简称 MT））
算法
整个算法主要分为三个阶段：
- 第一阶段：获得基础的梅森旋转链；
- 第二阶段：对于旋转链进行旋转算法；
- 第三阶段：对于旋转算法所得的结果进行处理；
第一阶段
导入seed，初始化伪随机数发生器
使用一个循环从索引1到623的范围，为 mt 列表的其他元素赋值。赋值的方式基于 Mersenne Twister 算法的核心公式。
-
_int32()是一个辅助函数，用于确保结果是32位有符号整数。 -
(self.mt[i - 1] ^ self.mt[i - 1] >> 30)表示对mt列表中前一个元素进行右移30位的操作，然后与前一个元素进行异或运算。 -
1812433253是一个常数。 -
+ i表示将索引值加到结果中，以产生不同的种子序列。
第二阶段
进行 twist() 函数
twist() 方法==用于对生成器的状态进行旋转操作。它的操作步骤如下：
- 使用一个循环从索引0到623的范围，依次处理每个状态元素。
- 根据状态元素的索引，获取当前元素和下一个元素的值。
- 对获取的值进行位操作，包括按位与和按位异或，以改变当前元素的值。（
-
(self.mt[i] & 0x80000000)获取当前元素的最高位，(self.mt[(i + 1) % 624] & 0x7fffffff)获取下一个元素的其余31位。这样可以将当前元素的最高位和下一个元素的其余31位合并成一个32位的值。将获取的值存储到变量y中，并使用_int32()函数将其转换为32位有符号整数。对当前元素进行状态扭曲操作。首先，使用右移运算符将y的值向右移动1位，然后与索引为(i + 397) % 624的状态元素进行按位异或运算。如果y的值除以2的余数不为0，即y % 2 != 0，则将当前元素与常数0x9908b0df进行按位异或运算。） - 将结果存储回
mt列表的当前元素位置。
第三阶段
extract_number() 方法==用于从生成器中提取一个伪随机数。它的操作步骤如下：
- 首先，检查
mti（mti 是用于追踪 mt 列表中当前使用的元素的索引) 是否等于0，如果等于0，则调用twist()方法进行状态的扭曲操作，以生成新的伪随机数序列。 - 接下来，从
mt列表中获取当前的随机数，存储到变量y中。 - 对
y执行一系列的位运算操作，包括右移、异或、左移和按位与，以改变y的值。 - 更新
mti的值，将其加1并对624取模，以确保它在0到623之间循环。 - 返回
_int32(y)，其中_int32()是一个辅助函数，用于确保结果是32位有符号整数。
实现
使用MT19937算法生成范围在 [232−1] 的均匀分布的32位整数。
def _int32(x):
return int(0xFFFFFFFF & x)
class MT19937:
# 用于初始化伪随机数生成器的类的构造函数
# 根据seed初始化624的state
def __init__(self, seed):
#创建一个名为 mt 的列表，包含624个元素，初始值都为0。这是用于存储生成器状态的主要数据结构。
self.mt = [0] * 624
#将输入参数 seed 的值赋给 mt 列表的第一个元素。它用于初始化生成器的种子。
self.mt[0] = seed
#mti 是用于追踪 mt 列表中当前使用的元素的索引。
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
破解
Mersenne Twister 梅森旋转算法笔记 | 独奏の小屋 (hasegawaazusa.github.io)
右移位后异或逆向
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
提取伪随机数逆向
b = 0x9d2c5680
c = 0xefc60000
def untemper(self, v):
v = self.unshiftRight(v, 18)
v = self.unshiftLeft(v, 15, self.c)
v = self.unshiftLeft(v, 7, self.b)
v = self.unshiftRight(v, 11)
return v
通过输出参数逆向
# forward 表示是否需要回到目前状态
def go(self, outputs, forward=True):
# 还原的寄存器状态
result_state = None
# 至少需要 624 个寄存器状态
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:
# 如果刚好是 624 个寄存器状态
result_state = (3, tuple(ivals+[624]), None)
# 利用 python 自带的 mt19937 random 库
rand = random.Random()
rand.setstate(result_state)
# 如果需要到输出后的状态，则进行比较判断
if forward:
for i in range(624, len(outputs)):
assert rand.getrandbits(32) == outputs[i]
return rand
python库
python中有可以直接用的库randcrack，extend_mt19937_predictor
求后随机数
import random
from randcrack import RandCrack
#random预测的时候默认以当前时间作为随机数种子
rc = RandCrack()#实例化randcrack类
for i in range(624):#循环624次
rc.submit(random.getrandbits(32))#每次循环提交一个32位random生成的随机数
print(random.getrandbits(32))#利用random库获取一个64位的随机数（你可以修改为任意位数）
print(rc.predict_getrandbits(32))#利用randcrack获取的下一个随机数
求前随机数
import random
from extend_mt19937_predictor import ExtendMT19937Predictor
#生成1024个64位的伪随机数并存储在列表numbers中：
numbers = [random.getrandbits(64) for _ in range(1024)]
predictor = ExtendMT19937Predictor()
#使用256位的随机数值(随机种子)来初始化预测器状态
for _ in range(78):
#循环78次，每次迭代都会使用256位的随机数值来初始化预测器状态
predictor.setrandbits(random.getrandbits(256), 256)
#回溯78次
_ = [predictor.backtrack_getrandbits(256) for _ in range(78)]
#验证回溯是否正确
for x in numbers[::-1]:
assert x == predictor.backtrack_getrandbits(64)
例题
XYCTF2024 Random_rr
题目
from Crypto.Util.number import *
from random import randint
flag=b'XYCTF{uuid}'
flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
def generate():
fw = open("random", "w")
for i in range(648):
fw.write(str(random.getrandbits(32))+"\n")
fw.close()
generate()
key = str(random.getrandbits(32))
key1= int(str(key)[0])
ks = [randint(0, rr**(i+key1-1)) for i in range(16)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), 127, n)
c2 = pow(flag, 65537, n)
ks = [pow(69, k+key, rr**(i+key1)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")
分析
generate（）生成648组32bit数，生成fw文件，然后再生成Key,ks是16个随机数组成的列表
首先，random文件已知，即相当于我们拿到了648组随机数，要想恢复key，只需要624个32bit，key的值通过extend_mt19937_predictor或者randcrack可以预测出来
randcrack：
from hashlib import md5
from randcrack import RandCrack
with open(r'random', 'r') as f:
random = f.readlines()
r = [int(i.strip()) for i in random]
t = []
#实例化randcrack类
rc = RandCrack()
for i in range(24, 648):
rc.submit(r[i])
key = str(rc.predict_getrandbits(32))
key1 = int(str(key)[0])
print(key)
print(key1)extend_mt19937_predictor：
from extend_mt19937_predictor import ExtendMT19937Predictor
predictor = ExtendMT19937Predictor()
with open(r'random', 'r') as f:
random = f.readlines()
r = [int(i.strip()) for i in random]
for i in range(24,648):
predictor.setrandbits(r[i], 32)
key = predictor.predict_getrandbits(32)
key1= int(str(key)[0])
print(key)
print(key1)恢复key之后，key=3168111950,key1=3
已知key1,rr,kks,q求ks （由于是练习mt19937，后面不涉及这个知识点，便省略了wp）
GKCTF Random
题目
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)
题解
random.getrandbits(32)生成32位随机数
random.getrandbits(64)生成64位随机数
random.getrandbits(96)生成96位随机数
MT生成的是32位随机数，那该如何生成64，96位呢
96位
64位同理
生成一个32位随机数a，然后再生成一个32位随机数b，将b左移32位去加上a，得到一个64位的随机数
每次循环给出（32+64+96）//32=6组32位随机数，共给了6*104=624组
flag是下一位随机数
import random
from hashlib import md5
from randcrack import RandCrack
#random预测的时候默认以当前时间作为随机数种子
with open(r'D:\\fj\\random.txt', 'r') as f:
l = f.readlines()
print(l)
#['2584323193\n', '1099154419438958164\n',
l = [int(i.strip()) for i in l]
#[2584323193, 1099154419438958164
t=[]#读取624组随机数
for i in range(len(l)):
if i % 3 == 0:
t.append(l[i])
elif i % 3 == 1:
#此时l[i]64位
#取后32位
t.append(l[i] & (2 ** 32 - 1))
#取前32位
t.append(l[i] >> 32)
else:
t.append(l[i] & (2 ** 32 - 1))
t.append(l[i] & (2 ** 64 - 1) >> 32)
t.append(l[i] >> 64)
rc = RandCrack()#实例化randcrack类
for i in t:#遍历t
rc.submit(i)
flag = rc.predict_getrandbits(32)
print(md5(str(flag).encode()).hexdigest())
#14c71fec812b754b2061a35a4f6d8421
第五空间 data_protection
题目
# run under python3
import random
from secret import flag, name, phone, mail, address, school, seed
from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
random.seed(seed)
def encrypt1(m):
a = random.getrandbits(96)
b = random.getrandbits(96)
p = next_prime(a)
q = next_prime(b)
n = p * q
e = 65537
assert (m < n)
print(pow(m, e, n))
print(n)
def encrypt2(m):
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
q = random.randrange(
11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997,
11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526563615762644)
nq = next_prime(q)
n = p * q
e = 65537
assert (m < n)
print(pow(m, e, n))
print(n)
def encrypt3(msg):
q = getPrime(33)
key = [[] for i in range(34)]
for i in range(len(key)):
for j in range(len(msg)):
tmp = random.getrandbits(32)
assert (tmp < q)
key[i].append(tmp)
cipher = []
for l in key:
tmp = 0
for x, y in zip(l, msg):
tmp = (tmp + x * y) % q
cipher.append(tmp)
print(q)
print(key)
print(cipher)
def encrypt4(msg):
key = long_to_bytes(random.getrandbits(128))
a = AES.new(key, AES.MODE_ECB)
cipher = a.encrypt(msg)
print(bytes_to_long(cipher))
def encrypt5(msg):
q = getPrime(512)
g = random.randrange(q - 1)
x = random.randrange(q - 1)
h = pow(g, x, q)
y = random.randrange(q - 1)
s = pow(h, y, q)
c1 = pow(g, y, q)
c2 = (msg * s) % q
print(q, g, h)
print(c1, c2)
msg1 = bytes_to_long(name)
encrypt1(msg1)
msg2 = bytes_to_long(phone + long_to_bytes(random.getrandbits(160)))
encrypt2(msg2)
msg3 = [x for x in mail]
encrypt3(msg3)
# Note the address incude digits,letters, '.' and '_'
msg4 = address
encrypt4(msg4)
msg5 = bytes_to_long(school)
encrypt5(msg5)
flag = 'flag{' + sha256(name).hexdigest()[:8] + '-' + sha256(phone).hexdigest()[:4] + '-' + sha256(mail).hexdigest()[
:4] + '-' + sha256(
address).hexdigest()[:4] + '-' + sha256(school).hexdigest()[:12] + '}'
# print (flag)
题解
flag是五段明文拼接
encrypt1
msg1 = bytes_to_long(name)
encrypt1(msg1)
m1的加密
a = random.getrandbits(96)
b = random.getrandbits(96)
p = next_prime(a)
q = next_prime(b)
n = p * q
e = 65537
assert (m < n)
print(pow(m, e, n))
print(n)
#659742747933803685159824618024154814230816386382620824215
#1428634580885297528425426676577388183501352157100030354079n很小，直接分解
然后rsa
#
import gmpy2
e= 65537
p= 22186905890293167337018474103
q= 64390888389278700958517837593
c=659742747933803685159824618024154814230816386382620824215
n=1428634580885297528425426676577388183501352157100030354079
assert n == p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m1 = pow(c,d,n)
print(m1)
#6370730279097167463
encrypt2
msg2 = bytes_to_long(phone + long_to_bytes(random.getrandbits(160)))
encrypt2(msg2)
def encrypt2(m):
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
q = random.randrange(11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997,11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526563615762644)
nq = next_prime(q)
n = p*q
e = 65537
assert(m<n)
print (pow(m,e,n))
print (n)
#93823394819893781294145893595876176392272709588141239765465056990025264756001551662286866510606348927770275357928084190921646652273213088016700645013648101794273512066846822716422789921137430035251019936921307446229894438817835962711632983943326022431165313426682669557098482175573639354190037351152748781943
#134949786048887319137407994803780389722367094355650515833817995038306119197600539524985448574053755793699799863164150565217726975197643634831307454431403854861515253009970594684699064052739820092115115614153962139870020206132705821506686959283747802946805730902605814619499301779892151365118901010526138311982
p,q相差很小
但这里n,p都给出来了，直接解
e = 65537
c=93823394819893781294145893595876176392272709588141239765465056990025264756001551662286866510606348927770275357928084190921646652273213088016700645013648101794273512066846822716422789921137430035251019936921307446229894438817835962711632983943326022431165313426682669557098482175573639354190037351152748781943
n=134949786048887319137407994803780389722367094355650515833817995038306119197600539524985448574053755793699799863164150565217726975197643634831307454431403854861515253009970594684699064052739820092115115614153962139870020206132705821506686959283747802946805730902605814619499301779892151365118901010526138311982
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
q=n//p
#q=11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526563112454006
assert n == p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m2 = pow(c,d,n)
print(m2)
#6999059562390230153204185325520574593712506454949907937061847451104049682008722729968510417799544130417502794091718255709643478595632521249674781160307383240437880832757143443029704377456417889073516619765360461991280267427605530029993965524257618938079026160825243292862056705306015903376827071229251731733
encrypt3
msg3 = [x for x in mail]
encrypt3(msg3)
def encrypt3(msg):
q = getPrime(33)
key = [[] for i in range(34)]
for i in range(len(key)):
for j in range(len(msg)):
tmp = random.getrandbits(32)
assert (tmp < q)
key[i].append(tmp)
cipher = []
for l in key:
tmp = 0
for x, y in zip(l, msg):
tmp = (tmp + x * y) % q
cipher.append(tmp)
print(q)
print(key)
print(cipher)
#q=6457637957
#key=[]
#cipher=[678819070, 3817412512, 301055013, 3114443682, 1912121740, 6169688434, 3834848760, 720680768, 3243307544, 2416524053, 3681314853, 2462958278, 1788315814, 1598431410, 3242718726, 1781508823, 5681795746, 5178418664, 6449543467, 1237772319, 6209249676, 3838512107, 3752816369, 1313804600, 1188836210, 3446064361, 143393929, 3810070519, 5753849566, 4918185832, 1289703820, 6211307915, 1782532569, 4395333125]cipher^T=key*msg^T
solve_right求解矩阵即可
求矩阵X满足XA=B , X = A.solve_right(B)
from Crypto.Util.number import long_to_bytes
q=6457637957
key=[]
#len(cipher)
#34
key=matrix(GF(q), key)
cipher=matrix(GF(q),34,1,cipher)
msg = key.solve_right(cipher)
msg=msg.list()
m=b''
for i in msg:
m+=long_to_bytes(int(i))
#b'Xiaoming@cmail.com'
encrypt4
msg4 = address
encrypt4(msg4)
def encrypt4(msg):
key = long_to_bytes(random.getrandbits(128))
a = AES.new(key, AES.MODE_ECB)
cipher = a.encrypt(msg)
print(bytes_to_long(cipher))
152306929817910220077778723987104768071key是随机产生的128位的随机数，通过上几轮加密，
第一轮
a = random.getrandbits(96) b = random.getrandbits(96) p = next_prime(a) q = next_prime(b)
泄露96*2//32=6个随机数
遍历寻找前6个随机数
for a in tqdm(range(prep1,p1)): for b in range(preq1,q1):
第二轮
q = random.randrange(11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997,11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526563615762644)
msg2 = bytes_to_long(phone + long_to_bytes(random.getrandbits(160)))泄露6个
第12个：
由q=11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526563112454006
第三轮 产生了Key(上一轮的key)msg(3418 ,612)个随机数
所以共泄露了624个随机数，预测下一随机数
encrypt5
def encrypt5(msg):
q = getPrime(512)
g = random.randrange(q - 1)
x = random.randrange(q - 1)
h = pow(g, x, q)
y = random.randrange(q - 1)
s = pow(h, y, q)
c1 = pow(g, y, q)
c2 = (msg * s) % q
print(q, g, h)
print(c1, c2)所有参数都可知,可预测，求个乘法逆元即可
#decrypt4.5
import sympy
import gmpy2
from Crypto.Cipher import AES
from Crypto.Util.number import *
from tqdm import tqdm
from randcrack import RandCrack
def move(m,t):
for i in range(t):
rc.submit(m%(2**32))
m=m>>32
p1 = 22186905890293167337018474103
q1 = 64390888389278700958517837593
prep1 = sympy.prevprime(p1)
preq1 = sympy.prevprime(q1)
with open('out') as f:
s = f.read().splitlines()
n = eval(s[3])
p=11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
e = 65537
q = (n // p)%(2**31)
key = eval(s[5])
key = [x for y in key for x in y]
pads=b'\\xf1\\x0f\\xb5\\xb5\\xae\\xf0\\x05\\x92BWR\\xd0>\\x91\\x0cv\\xbc ]\\x81'
pads = bytes_to_long(pads)
msg=long_to_bytes(152306929817910220077778723987104768071)
qq=12217466470388578339925921504697419805922316645286268670005262949923786678953775204218792050281040210171698682980282116705949902617753168109140673704093013
c1=1206086806846740801537809351203441891991149258137979326257729133418947335751911053166910334440727360724054611656176111461530487297130872946166550101453709
c2=9595419621184859047616076479725843810995669805509369406782913078875593428769072592975736393012907744950510239492901380211367555005217818487881050318849564
for a in tqdm(range(prep1,p1)):
for b in range(preq1,q1):
for r in range(2):
rc=RandCrack()
move(a,3)
move(b,3)
move(pads,5)
move((q<<1)+r,1)
for i in range(len(key)):
move(key[i],1)
aeskey = long_to_bytes(rc.predict_getrandbits(128))
try:
pt = AES.new(aeskey, AES.MODE_ECB)
m=pt.decrypt(msg)
if '_' in str(m) and '.' in str(m):
print(m)
gg=rc.predict_randrange(qq-1)
x=rc.predict_randrange(qq-1)
y=rc.predict_randrange(qq-1)
m2=c2*(gmpy2.invert(pow(c1,x,qq),qq))%qq
print(long_to_bytes(m2))
except:
continue
#No.007_hack_road
#MakeUSAGreatAgain_University
flag:
from hashlib import sha256
name=b'Xiaoming'
phone=b'15412134151'
mail=b'Xiaoming@cmail.com'
address=b'No.007_hack_road'
school=b'MakeUSAGreatAgain_University'
flag = 'flag{'+sha256(name).hexdigest()[:8]+'-'+sha256(phone).hexdigest()[:4]+'-'+sha256(mail).hexdigest()[:4]+'-'+sha256(address).hexdigest()[:4]+'-'+sha256(school).hexdigest()[:12]+'}'
print(flag)
转载
分享
0 条评论
可输入 255 字
发布投稿
热门文章
优秀作者
