MT的提取算法逆向
学习出处:https://liam.page/2018/01/12/Mersenne-twister/
题目
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
| from Crypto.Random import random
from Crypto.Util import number
from flag import flag
def convert(m):
m = m ^ m >> 13
m = m ^ m << 9 & 2029229568
m = m ^ m << 17 & 2245263360
m = m ^ m >> 19
return m
def transform(message):
assert len(message) % 4 == 0
new_message = ''
for i in range(len(message) / 4):
block = message[i * 4 : i * 4 +4]
block = number.bytes_to_long(block)
block = convert(block)
block = number.long_to_bytes(block, 4)
new_message += block
return new_message
transformed_flag = transform(flag[5:-1].decode('hex')).encode('hex')
print 'transformed_flag:', transformed_flag
|
分析
逆提取算法
向右移位异或
1
| result=value^value>>shift
|
result的前shift位和value相同
使用比特遮罩或截取result的前shift位得到value的前shift位
tmp=value>>shift
由此可以得到tmp的前shift*2位
与result异或 得到value的前shift*2位
循环往复，可以得到value
1
2
3
4
5
6
7
8
9
| def right(result, shift):
i,value=0,0
while i*shift<32:
part_mask=((kMaxBits << (32 - shift)) & kMaxBits)>>(i*shift)
part=result&part_mask
result^=part>>shift
value|=part
i+=1
return value
|
向左移位异或
1
| result=value^value<<shift&mask
|
tmp=value<<shift
同理，result的后shift位与value相同，比特遮罩取后shift位
可知value的前shift*2位
循环往复
与右移不同的是此处mask取对应的位，逆算法中也要取相应的位
1
2
3
4
5
6
7
8
9
| def left(result,shift,mask):
i,value=0,0
while i*shift<32:
part_mask=((kMaxBits>>(32-shift)&kMaxBits))<<(i*shift)
part=result&part_mask
result^=(part<<shift)&mask
value|=part
i+=1
return value
|
解题
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
| from Crypto.Util.number import *
kMaxBits = 0xffffffff
c1 = 0x641460a9
c2 = 0xe3953b1a
c3 =0xaa21f3a2
c='641460a9e3953b1aaa21f3a2'
def right(result, shift):
i,value=0,0
while i*shift<32:
part_mask=((kMaxBits << (32 - shift)) & kMaxBits)>>(i*shift)
part=result&part_mask
result^=part>>shift
value|=part
i+=1
return value
def left(result,shift,mask):
i,value=0,0
while i*shift<32:
part_mask=((kMaxBits>>(32-shift)&kMaxBits))<<(i*shift)
part=result&part_mask
result^=(part<<shift)&mask
value|=part
i+=1
return value
def decrypt(m):
m = right(m, 19)
m = left(m, 17, 2245263360)
m = left(m, 9, 2029229568)
m = right(m, 13)
return m
s1=hex(decrypt(c1))[2:]
s2=hex(decrypt(c2))[2:]
s3=hex(decrypt(c3))[2:]
print(s1+s2+s3)
|
