Streamcipher Learning
MT19937
简介
即Mersenne Twister(梅森旋转)算法，得名于梅森素数219937-1
MT19937是一种周期很长的伪随机数生成算法，可以快速产生高质量伪随机数
由三部分组成
1.利用seed初始化624的状态
2.对状态进行旋转
3.根据状态提取伪随机数
python实现
32位MT19937的python代码如下:
def int32(x):
return int(x&0xffffffff)
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*(slef.mt[i-1]^self.mt[i-1]>>30)+i)
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
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.mt=(self.mti+1)%624
return int32(y)
梅森旋转算法的设计目的是优秀的伪随机数生成算法，而不是产生密码学上安全的随机数。从梅森算法的结构上来说extract_number基于按位异或，是可逆的，这说明攻击者可以从梅森旋转算法的输出逆推产生该输出的内部寄存器状态mt[i]，若攻击者能获得连续的n个寄存器状态，那么攻击者就能预测接下来的随机数序列
算法逆向
下面我们分别对梅森算法的各个部分进行逆向
1.extract_number
矩阵运算写法
G=GF(2)
E=Matrix.zero(32)
for i in range(32):
E[i,i]=1
a1=2636928640
a1=bin(a1)[2:].rjust(32,'0')
a2=4022730752
a2=bin(a2)[2:].rjust(32,'0')
A1=Matrix.zero(32)
A2=Matrix.zero(32)
for i in range(32):
A1[i,i]=int(a1[i])
A2[i,i]=int(a2[i])
B11=Matrix.zero(32)
for i in range(21):
B11[i+11,i]=1
B7=Matrix.zero(32)
for i in range(25):
B7[i,i+7]=1
B15=Matrix.zero(32)
for i in range(17):
B15[i,i+15]=1
B18=Matrix.zero(32)
for i in range(14):
B18[i+18,i]=1
E=Matrix(G,E)
A1=Matrix(G,A1)
A2=Matrix(G,A2)
B11=Matrix(G,B11)
B7=Matrix(G,B7)
B15=Matrix(G,B15)
B18=Matrix(G,B18)
c=''
v=[]
for i in range(len(c)):
v.append(c[i])
v=vector(GF(2),v)
v=(E+B18)^(-1)*v
v=(E+A2*B15)^(-1)*v
v=(E+A1*B7)^(-1)*v
v=(E+B11)^(-1)*v
m=list(v)
for i in range(len(m)):
print(m[i],end='')
位运算写法
def backtrace(y):
y1=y&(2**32-2**18)
y=y^y1>>18
y1=y&(2**17-2**2)
y=y^y1<<15&4022730752
for i in range(1,5):
y1=y&(2**(7*i)-2**(7*(i-1)))
y=y^y1<<7&2636928640
y=y&0xffffffff
y1=y&(2**32-2**21)
y=y^y1>>11
y1=y&(2**21-2**10)
y=y^y1>>11
return y
相比之下，两种方法各有优势，使用矩阵的思维难度更小，但是代码冗长，而使用位运算虽然思维难度稍大但是代码简洁
2.twist
用矩阵的方式没有减少思维难度只是换了种写法，故不考虑
但是在逆向的过程中发现了个问题，就是第一位数的后31bits是缺失的，但是这个31bits并不会影响后面的数的变换，也就是说不同的状态如果除了第一位的后31bits不同其他一致，在使用旋转后的状态提取出的随机数是一致的(但是我觉得按MT19937的初始化来说这种情况应该是达不到的)
def backtrace(state):
high=0x80000000
low=0x7fffffff
r=0x9908b0df
for i in range(623,-1,-1):
s1=state[i]
s2=state[(i+397)%624]
s=s1^s2
if s&high==1<<31:
s=s^r
y=s<<1
y=y+1
else:
y=s<<1
temp1=y&high
s1 = state[i-1]
s2 = state[(i + 396) % 624]
s = s1 ^ s2
if s & high == 1<<31:
s=s^r
y = s <<1
y = y + 1
else:
y = s << 1
temp2 = y & low
state[i]=temp1+temp2
return state
示例
[网鼎杯2020]random
import base64
import random
flag = "flag{************************************}"
hexadecimalcontrast = {
'0': '0000',
'1': '0001',
'2': '0010',
'3': '0011',
'4': '0100',
'5': '0101',
'6': '0110',
'7': '0111',
'8': '1000',
'9': '1001',
'a': '1010',
'b': '1011',
'c': '1100',
'd': '1101',
'e': '1110',
'f': '1111',
}
IP = [58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7]
IP_1 = [40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25]
E = [32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1]
S = [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9, ],
[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12, ],
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13, ],
[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14, ],
[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, ],
[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13, ],
[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12, ],
[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11, ]]
PC_1 = [57, 49, 41, 33, 25, 17, 9, 1,
58, 50, 42, 34, 26, 18, 10, 2,
59, 51, 43, 35, 27, 19, 11, 3,
60, 52, 44, 36, 63, 55, 47, 39,
31, 23, 15, 7, 62, 54, 46, 38,
30, 22, 14, 6, 61, 53, 45, 37,
29, 21, 13, 5, 28, 20, 12, 4, ]
PC_2 = [14, 17, 11, 24, 1, 5, 3, 28,
15, 6, 21, 10, 23, 19, 12, 4,
26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40,
51, 45, 33, 48, 44, 49, 39, 56,
34, 53, 46, 42, 50, 36, 29, 32, ]
P = [16, 7, 20, 21,
29, 12, 28, 17,
1, 15, 23, 26,
5, 18, 31, 10,
2, 8, 24, 14,
32, 27, 3, 9,
19, 13, 30, 6,
22, 11, 4, 25, ]
movnum = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
def HexToBin(string):
"Convert sixteen to binary"
Binstring = ""
string = string.lower()
for i in string:
try:
Binstring += hexadecimalcontrast[i]
except:
return -1
return Binstring
def BinToStr(strbin):
"Turn the binary string to a ASCII string"
strten = ""
for i in range(len(strbin) // 8):
num = 0
test = strbin[i * 8:i * 8 + 8]
for j in range(8):
num += int(test[j]) * (2**(7 - j))
strten += chr(num)
return strten
def StrToHex(string):
"Converts a string to HEX"
hexStr = ''
for i in string:
tmp = str(hex(ord(i)))
if len(tmp) == 3:
hexStr += tmp.replace('0x', '0')
else:
hexStr += tmp.replace('0x', '')
return hexStr
def Binxor(string1, string2):
"If the length is different, only the short one is returned."
strlen = 0
xorstr = ""
if len(string1) > len(string2):
strlen = len(string2)
else:
strlen = len(string1)
for i in range(strlen):
if string1[i] == string2[i]:
xorstr += '0'
else:
xorstr += '1'
return xorstr
def SubstitutionBox(keyfield, sub):
newkeyfield = ''
for i in range(len(sub)):
newkeyfield += keyfield[sub[i] - 1]
return newkeyfield
def SubkeyGeneration(freq, C, D):
for i in range(movnum[freq]):
C = C[1:] + C[:1]
D = D[1:] + D[:1]
return C, D, SubstitutionBox(C + D, PC_2)
def enkey(secretkey):
netss = SubstitutionBox(HexToBin(StrToHex(secretkey)), PC_1)
C, D = netss[:28], netss[28:]
key = []
for i in range(16):
C, D, keyone = SubkeyGeneration(i, C, D)
key.append(keyone)
return key
def Sbox(plaintext, sub):
return HexToBin("%x" % S[sub][int(plaintext[:1] + plaintext[-1:], 2) * 16 + int(plaintext[1:-1], 2)])
def Function(plaintext, secretkey):
plaintext = Binxor(SubstitutionBox(plaintext, E),
secretkey)
sout = ''
for i in range(8):
sout += Sbox(plaintext[i * 6:(i + 1) * 6], i)
sout = SubstitutionBox(sout, P)
return sout
def endecrypt(plaintext, secretkey):
netss = SubstitutionBox(HexToBin(StrToHex(plaintext)), IP)
L, R = netss[:32], netss[32:]
for i in range(16):
L, R = R, Binxor(L, Function(R, secretkey[i]))
return SubstitutionBox(R + L, IP_1)
def encryption(plaintext, secretkey):
plaintext = plaintext + (8 - len(plaintext) % 8) * '\0'
keys = enkey(secretkey[:8])
ciphertext = ''
for i in range(len(plaintext) / 8):
ciphertext += endecrypt(plaintext[i * 8:(i + 1) * 8], keys)
return base64.b64encode(BinToStr(ciphertext))
def generate():
fw = open("random", "w")
for i in range(700):
fw.write(str(random.getrandbits(32))+"\n")
fw.close()
generate()
f = open("flag.txt", "w")
key = str(random.getrandbits(32))
ciphertext = encryption(flag, key)
f.write(ciphertext)
f.close()
这是一道密码题代码审计题，不知道为什么不使用库函数，还一个一个定义，看傻了，后面了解到使用的加密方式是Feistel体系，虽然DES的*还没具体了解，但是我们知道DES在使用相同密钥进行二重加密的时候会还原，于是我们只需在知道key后对密文再次进行加密即可
key是python的random模块随机生成的32bits数，采用的是mt19937，我们可以根据前624个随机数预测第701个随机数key
import base64
from Crypto.Util.number import *
def int32(x):
return int(x&0xffffffff)
def twist(mt):
for i in range(0,624):
y=int32((mt[i]&0x80000000)+(mt[(i+1)%624]&0x7fffffff))
mt[i]=(y>>1)^mt[(i+397)%624]
if y%2!=0:
mt[i]=mt[i]^0x9908b0df
return mt
def extract_number(mt,m):
for i in range(624):
y=mt[i]
y=y^y>>11
y=y^y<<7&2636928640
y=y^y<<15&4022730752
y=y^y>>18
m.append(int32(y))
return m
def backtrace(y):
y1=y&(2**32-2**18)
y=y^y1>>18
y1=y&(2**17-2**2)
y=y^y1<<15&4022730752
for i in range(1,5):
y1=y&(2**(7*i)-2**(7*(i-1)))
y=y^y1<<7&2636928640
y=y&0xffffffff
y1=y&(2**32-2**21)
y=y^y1>>11
y1=y&(2**21-2**10)
y=y^y1>>11
return y
f=open('random','r')
rs=[]
for i in range(624):
r=f.readline()[:-1]
rs.append(int(r))
state=[]
for i in range(624):
state.append(backtrace(rs[i]))
state=twist(state)
rr=[]
rr=extract_number(state,rr)
key=str(rr[76])
c='t2GzuEfVDaJsNLBqC8N7C3/2UgIeCoQLC2qLkT1ukFULskzMc1u9QeFizVUfFYfA'
c=base64.b64decode(c)
print(len(c))
hexadecimalcontrast = {
'0': '0000',
'1': '0001',
'2': '0010',
'3': '0011',
'4': '0100',
'5': '0101',
'6': '0110',
'7': '0111',
'8': '1000',
'9': '1001',
'a': '1010',
'b': '1011',
'c': '1100',
'd': '1101',
'e': '1110',
'f': '1111',
}
IP = [58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7]
IP_1 = [40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25]
E = [32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1]
S = [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9, ],
[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12, ],
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13, ],
[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14, ],
[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, ],
[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13, ],
[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12, ],
[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11, ]]
PC_1 = [57, 49, 41, 33, 25, 17, 9, 1,
58, 50, 42, 34, 26, 18, 10, 2,
59, 51, 43, 35, 27, 19, 11, 3,
60, 52, 44, 36, 63, 55, 47, 39,
31, 23, 15, 7, 62, 54, 46, 38,
30, 22, 14, 6, 61, 53, 45, 37,
29, 21, 13, 5, 28, 20, 12, 4, ]
PC_2 = [14, 17, 11, 24, 1, 5, 3, 28,
15, 6, 21, 10, 23, 19, 12, 4,
26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40,
51, 45, 33, 48, 44, 49, 39, 56,
34, 53, 46, 42, 50, 36, 29, 32, ]
P = [16, 7, 20, 21,
29, 12, 28, 17,
1, 15, 23, 26,
5, 18, 31, 10,
2, 8, 24, 14,
32, 27, 3, 9,
19, 13, 30, 6,
22, 11, 4, 25, ]
movnum = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
def HexToBin(string):
"Convert sixteen to binary"
Binstring = ""
string = string.lower()
for i in string:
try:
Binstring += hexadecimalcontrast[i]
except:
return -1
return Binstring
def BinToStr(strbin):
"Turn the binary string to a ASCII string"
strten = ""
for i in range(len(strbin) // 8):
num = 0
test = strbin[i * 8:i * 8 + 8]
for j in range(8):
num += int(test[j]) * (2**(7 - j))
strten += chr(num)
return strten
def StrToHex(string):
"Converts a string to HEX"
hexStr = ''
for i in string:
tmp = str(hex(ord(i)))
if len(tmp) == 3:
hexStr += tmp.replace('0x', '0')
else:
hexStr += tmp.replace('0x', '')
return hexStr
def Binxor(string1, string2):
"If the length is different, only the short one is returned."
strlen = 0
xorstr = ""
if len(string1) > len(string2):
strlen = len(string2)
else:
strlen = len(string1)
for i in range(strlen):
if string1[i] == string2[i]:
xorstr += '0'
else:
xorstr += '1'
return xorstr
def SubstitutionBox(keyfield, sub):
newkeyfield = ''
for i in range(len(sub)):
newkeyfield += keyfield[sub[i] - 1]
return newkeyfield
def SubkeyGeneration(freq, C, D):
for i in range(movnum[freq]):
C = C[1:] + C[:1]
D = D[1:] + D[:1]
return C, D, SubstitutionBox(C + D, PC_2)
def enkey(secretkey):
netss = SubstitutionBox(HexToBin(StrToHex(secretkey)), PC_1)
C, D = netss[:28], netss[28:]
key = []
for i in range(16):
C, D, keyone = SubkeyGeneration(i, C, D)
key.append(keyone)
return key
def Sbox(plaintext, sub):
return HexToBin("%x" % S[sub][int(plaintext[:1] + plaintext[-1:], 2) * 16 + int(plaintext[1:-1], 2)])
def Function(plaintext, secretkey):
plaintext = Binxor(SubstitutionBox(plaintext, E),
secretkey)
sout = ''
for i in range(8):
sout += Sbox(plaintext[i * 6:(i + 1) * 6], i)
sout = SubstitutionBox(sout, P)
return sout
def decrypt(cipher, secretkey):
netss = SubstitutionBox(bin(bytes_to_long(cipher))[2:].rjust(64,'0'), IP)
L, R = netss[:32], netss[32:]
for i in range(16):
L, R = R, Binxor(L, Function(R, secretkey[i]))
return BinToStr(SubstitutionBox(R + L, IP_1))
def decryption(cipher,secretkey):
keys=enkey(secretkey[:8])[::-1]
plaintext=''
for i in range(len(cipher)//8):
plaintext+=decrypt(cipher[8*i:8*(i+1)],keys)
return plaintext
print(decryption(c,key))
[V&N2020 公开赛]Backtrace
# !/usr/bin/env/python3
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)
非连续的624位输出的twist逆向同样能够实现，即把前一个624的部分数据当成后部分已经逆向完成的数据，按照连续624位数据逆向的思路进行下去即可
def int32(x):
return int(x&0xffffffff)
def backtrace(y):
y1=y&(2**32-2**18)
y=y^y1>>18
y1=y&(2**17-2**2)
y=y^y1<<15&4022730752
for i in range(1,5):
y1=y&(2**(7*i)-2**(7*(i-1)))
y=y^y1<<7&2636928640
y=y&0xffffffff
y1=y&(2**32-2**21)
y=y^y1>>11
y1=y&(2**21-2**10)
y=y^y1>>11
return y
def backtracetwist(mt):
high=0x80000000
low=0x7fffffff
mask=0x9908b0df
for i in range(3,-1,-1):
y=mt[i+624]^mt[i+397]
if y&high==high:
y=y^mask
y=y<<1
y+=1
else:
y=y<<1
temp1=y&high
y = mt[i-1 + 624] ^ mt[i-1 + 397]
if y & high == high:
y = y ^ mask
y = y << 1
y+=1
else:
y = y << 1
temp2 = y & low
mt[i]=temp1+temp2
return mt
def extract_number(mt,m):
for i in range(624):
y=mt[i]
y=y^y>>11
y=y^y<<7&2636928640
y=y^y<<15&4022730752
y=y^y>>18
m.append(int32(y))
return m
f=open('output.txt','r')
rs=[0,0,0,0]
for i in range(1000):
r=f.readline()
rs.append(backtrace(int(r)))
rr=backtracetwist(rs)[:624]
m=[]
m=extract_number(rr,m)
flag='flag{'+str(m[0])+str(m[1])+str(m[2])+str(m[3])+'}'
print(flag)