目录
流密码LFSR
[CISCN2018] oldstreamgame
flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14
# 1101
# (1101 & 0001) | 1
# 0101
def lfsr(R,mask):
output = (R << 1) & 0xffffffff
#R向左移位，高位丢弃，末尾补0，保留32位
i=(R&mask)&0xffffffff
#保留mask原本为1的位置，使其参与运算，形成lastbit
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
#i的每一位与1进行与运算，再与lastbit进行异或运算
#lastbit = i[3]^i[5]^i[8]^i[12]^i[20]^i[27]^i[30]^i[32],得到lastbit非0即1
output^=lastbit
#output末尾为0，与lastbit进行异或，相当于将lastbit进行末位补位
return (output,lastbit)
R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100
f=open("key","w")
for i in range(100):
tmp=0
for j in range(8):
(R,mask)=lfsr(R,mask)
tmp=(tmp << 1)^out
f.write(chr(tmp))
f.close()
打开key文件，取32位，也就是八位十六进制
key = '00100000111111011110111011111000'
mask = '10100100000010000000100010010100'
加密过程如下
R = ????????????????????????????????
x = int(c[-32])^int(R[-3])^int(R[-5])^int(R[-8])^int(R[-12])^int(R[-20])^int(R[-27])^int(R[-30])
R = ???????????????????????????????X
这样依次进行末位补位
R = ?1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx x
当进行到第31次加密时，如上述所示，此时我们已知32位提换位，第32位flag未知，根据异或的性质
?1 = key[-1]^R[-3]^R[-5]^R[-8]^R[-12]^R[-20]^R[-27]^R[-30]
R = ?2?1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx x
?2 = key[-2]^R[-3]^R[-5]^R[-8]^R[-12]^R[-20]^R[-27]^R[-30]
以次类推
flag = ?32?31?30?29?28?27?26?25?24?23?22?21?20?19?18?17?16?15?14?13?12?11?10?9?8?7?6?5?4?3?2?1
最后将flag进行倒置，再转十六进制解题
第一种解法
#mask = 10100100000010000000100010010100
key = '00100000111111011110111011111000'
c = key
flag = ''
for i in range(32):
output = "?"+key[:31]
#?0010000011111101111011101111100
#?1001000001111110111101110111110
a = int(c[-1-i])^int(output[-3])^int(output[-5])^int(output[-8])^int(output[-12])^int(output[-20])^int(output[-27])^int(output[-30])
flag += str(a)
key = str(a)+key[:31]
b = flag[::-1]
print(hex(int(b,2)))第二种解法
mask = [1,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0]
s = [0,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,0,0]
suf = []
def bitAnd(a, b):
return list(map(lambda x,y: int(x)&int(y), a, b))
for i in range(32):
if bitAnd([0] + suf + s[0:31 - i], mask).count(1) % 2 == s[31 - i]:
suf = [0] + suf
else:
suf = [1] + suf
print(suf)[AFCTF2018]Tiny LFSR
import sys
from binascii import unhexlify
if(len(sys.argv)<4):
print("Usage: python Encrypt.py keyfile plaintext ciphername")
exit(1)
def lfsr(R, mask):
output = (R << 1) & 0xffffffffffffffff #64位
i=(R&mask)&0xffffffffffffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
R = 0
key = ""
with open(sys.argv[1],"r") as f:
key = f.read()
R = int(key,16)
f.close
mask = 0b1101100000000000000000000000000000000000000000000000000000000000
a = ''.join([chr(int(b, 16)) for b in [key[i:i+2] for i in range(0, len(key), 2)]])
f=open(sys.argv[2],"r")
#打开Plain.txt flag.txt文件
ff = open(sys.argv[3],"wb")
#写入cipher.txt flag_encode.txt文件
s = f.read()
#密文
f.close()
lent = len(s)
for i in range(0, len(a)):
ff.write((ord(s[i])^ord(a[i])).to_bytes(1, byteorder='big'))
#密文的a位数与lsfr生成的密钥流进行异或
for i in range(len(a), lent):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
#tmp进行lfsr的加密
ff.write((tmp^ord(s[i])).to_bytes(1, byteorder='big'))
#将密文的后半段与tmp进行异或
ff.close()
首先根据题目所给的Plain.txt 和cipher.txt进行密钥流a的求解
#plain[i] ^ a[i] = cipher[i]
#a[i] = cipher[i] ^ plain[i]
#由于mask位64位，那么推断a也为64位
plain = "0111001101100100011001110110011001101010011010110110000101101000"
cipher = "0111001001000111001000100000000111100011110000001010110010000111"
key = ''
for i in range(64):
key +=str(int(plain[i])^int(cipher[i]))
#print(key)
from Crypto.Util.number import *
a = "0000000100100011010001010110011110001001101010111100110111101111"
s = "0100100001001101011001010000010011100110110001101011110110011010"
flag1 = ''
for i in range(0, len(a)):
flag1 += str(((int(s[i])))^((int(a[i]))))
print(flag1)再根据题目加密过程进行解密
from binascii import unhexlify
def lfsr(R, mask):
output = (R << 1) & 0xffffffffffffffff #64位
i=(R&mask)&0xffffffffffffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
R = 0
key = "0123456789abcdef"
R = int(key,16)
mask = 0b1101100000000000000000000000000000000000000000000000000000000000
a = ''.join([chr(int(b, 16)) for b in [key[i:i+2] for i in range(0, len(key), 2)]])
f=open("flag_encode.txt","rb").read()
lent = len(f)
flag = ''
for i in range(len(a), lent):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
flag +=(chr(tmp^f[i]))
print(flag)
De1CTF2019]Babylfsr
import hashlib
from secret import KEY,FLAG,MASK
assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')
LENGTH = 256
assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)
def pad(m):
pad_length = 8 - len(m)
return pad_length*'0'+m
class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1
def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output
self.init = nextdata
return output
if __name__=="__main__":
l = lfsr(KEY,MASK,LENGTH)
r = ''
for i in range(63):
b = 0
for j in range(8):
b = (b<<1)+l.next()
r += pad(bin(b)[2:])
with open('output','w') as f:
f.write(r)
#r = 001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010
key和mask的位数为256，唯一的已知量为504位的lsfr的加密序列，这样的话我们相当于得到了两组的加密序列，只是第二组加密后的序列缺少了8位，但由于位数较少，我们可以动过爆破得到符合条件的一组
assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')根据lsfr的反馈函数可以由此来计算mask
三组矩阵，我们相当于已经知道了两组，也就是r的前256位为已知的序列，通过lfsr的加密计算得到后256位的序列，那么想要求解mask就是相当于用后256位乘前256位的逆矩阵
得到mask的值后，正常求解即可
import itertools, hashlib, numpy as np
def bin2int(a):
return reduce(lambda x,y: x*2+y, a)
#进行lfsr的解密
def bitAnd(a, b):
assert len(a) == len(b)
return list(map(lambda x,y: int(x)&int(y), a, b))
def test(padding):
s = [int(x) for x in '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'] + padding
M = matrix(GF(2), 256, 256)
T = vector(GF(2), 256)
for i in range(len(s) - 256):
M[i] = s[i : i + 256]
T[i] = s[i+256]
try:
mask = M.inverse() * T
except:
return
suf = []
for i in range(256):
if bitAnd([0] + suf + s[0:255 - i], mask).count(1) % 2 == s[255 - i]:
suf = [0] + suf
else:
suf = [1] + suf
key = hex(bin2int(suf))[2:]
sha = hashlib.sha256(key.encode()).hexdigest()
if sha[:4] == '1224':
print('de1ctf{' + sha + '}')
#爆破后八位数字获取
for x in itertools.product([0, 1], repeat = 8):
test(list(x))