这篇博客记录一下平时做到的LRSF题型吧
Num.01(攻防世界streamgame1)
题目如下：
from flag import flag
assert flag.startswith("flag{")
# 作用：判断字符串是否以指定字符或子字符串开头flag{
assert flag.endswith("}")
# 作用：判断字符串是否以指定字符或子字符串结尾}，flag{}，6个字节
assert len(flag)==25
# flag的长度为25字节，25-6=19个字节
#3<<2可以这么算，bin(3)=0b11向左移动2位变成1100，0b1100=12(十进制)
def lfsr(R,mask):
output = (R << 1) & 0xffffff #将R向左移动1位，bin(0xffffff)='0b111111111111111111111111'=0xffffff的二进制补码
i=(R&mask)&0xffffff #按位与运算符&：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
lastbit=0
while i!=0:
lastbit^=(i&1) #按位异或运算符：当两对应的二进位相异时，结果为1
i=i>>1
output^=lastbit
return (output,lastbit)
R=int(flag[5:-1],2)
mask = 0b1010011000100011100
f=open("key","ab") #以二进制追加模式打开
for i in range(12):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out #按位异或运算符：当两对应的二进位相异时，结果为1
f.write(chr(tmp)) #chr() 用一个范围在 range（256）内的（就是0～255）整数作参数，返回一个对应的字符。
f.close()我们把里面的函数和加密流程进行分析：
def lfsr(R,mask):
output = (R << 1) & 0xffffff #将R向左移动1位，bin(0xffffff)='0b111111111111111111111111'=0xffffff的二进制补码
i=(R&mask)&0xffffff #按位与运算符&：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
lastbit=0
while i!=0:
lastbit^=(i&1) #按位异或运算符：当两对应的二进位相异时，结果为1
i=i>>1
output^=lastbit
return (output,lastbit)传入两个参数R和mask，R左移1位（相当于在后面补零）然后赋值给output。i是R和mask相与的结果，lastbit初值为0。进入循环，lastbit和i的最后一位异或，i右移一位。最后output和lastbit异或，函数返回output和lastbit。
再来看看加密过程：
f=open("key","ab") #以二进制追加模式打开
for i in range(12):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out #按位异或运算符：当两对应的二进位相异时，结果为1
f.write(chr(tmp)) #chr() 用一个范围在 range（256）内的（就是0～255）整数作参数，返回一个对应的字符。
f.close()这一步是分成12个字节，每一个字节进行lfsr加密，在tmp中记录每一位的异或结果（也就是一个字节的key）。
很显然，这题的解题大致思路就是通过key和mask进行异或得到原来的明文。这里直接套用别人的图来看看加密过程：
转换成矩阵形式更加放便于理解：
矩阵中对应元素相乘之后的结果进行异或运算，由于mask的第一位是1（矩阵中的），根据与的性质，任何数与1与都是这个数本身，所以这里直接把第一列提出来，转换成如下形式：
根据异或性质，可以对调k和b矩阵：
再将k还原至原矩阵：
根据最后一个矩阵的算法就可以算出明文，脚本如下：
from gmpy2 import c_div
def lfsr(R,mask):
output = (R << 1) & 0xffffff
i=(R&mask)&0xffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
def cal(s,mask):
lm=len(bin(mask))-2
R=int(s[-1:]+s[:-1],2)
ss=''
for j in range(lm,0,-1):
(_,tk)=lfsr(R,mask)
ss=str(tk)+ss
R=int(s[j-2]+str(ss)+bin(R)[2:].rjust(lm,'0')[1:-1],2)
return ss
def solve():
mask=0b1010011000100011100
lm=len(bin(mask))-2
with open("C:/Users/LENOVO/Desktop/key",'rb') as f:
stream=f.read(c_div(lm,8))
s=''.join([bin(256+ord(it))[3:]for it in stream])
flag='flag{'+cal(s[:lm],mask)+'}'
return flag
if __name__=='__main__':
print(solve())BUU [第七章 CTF之CRYPTO章]LFSR
题目如下：
seed = 0x00000000 # you need to solve this
flag = 'n1book{%x}' % seed
state = seed
mask = 0b10000000000000000000000001010111
def lfsr():
global state, mask
output = state & 1
now = state & mask
new = 0
while now:
new ^= now & 1
now >>= 1
state = (new << 31) | (state >> 1)
return output
for i in range(32):
lfsr()
print '%x' % state # 155a796b这题和上一题差不多，就是异或出来的数据是插入到了最前面而不是插到后面。这里依然使用矩阵的形式进行对题目的分析：
矩阵中s是“state”，n是“new”，乘法是&运算。n的生成通过s&mask中1相异或的结果，所以我们要想得到原始的state，需要从最后一个state逆向求得上一个state，循环32次就可以得到最原始的state。由于我们知道由上一个state得到的n，就可以猜测出上一个state的最后一位是多少（因为不是0就是1）。脚本如下：
from Crypto.Util.number import *
mask = "10000000000000000000000001010111"
state = "00010101010110100111100101101011"
s = ""
def lfsr(state, mask):
global s
for i in range(0, 32):
des = state[0]
print(des)
state = state[1 : 32]
print(state)
a = str(1)
state = state + a
print(state)
now = int(state, 2) & int(mask, 2)
new = 0
while(now):
new ^= now & 1
now >>= 1
if (str(new) == des):
state = state
print(state)
else:
state = state[0 : 31] + str(0)
print(state)
return state
print(lfsr(state, mask))
print(hex(int("01011111001101110101100111011111", 2)))flag{5f3759df}去掉’0x’是真的坑。。。
[AFCTF2018]Tiny LFSR
题目如下：
Encrypt.py
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
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")
ff = open(sys.argv[3],"wb")
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'))
for i in range(len(a), lent):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
ff.write((tmp^ord(s[i])).to_bytes(1, byteorder='big'))
ff.close()
------------------------------------------------------------------------------------------------------------
Plain.txt
sdgfjkahblskdjxbvfskljdfbguisldfbvghkljsdfbghsjkldhbgjklsdbgvlkjsdgbkljb sdkljfhwelo;sdfghioeurthgbnjl k
------------------------------------------------------------------------------------------------------------
cipher.txt
rG"憷瑖z'羾)t熩\ ?P
隑\[jSWKJ P匜 J悽馮w€鼲 ?儳"?
?緉?効 #Y彼屹脮榍mB遝膒?掓_fPO0%钓`鐁 j,?
------------------------------------------------------------------------------------------------------------
flag_encode.txt
HMe嫫綒l"軏a>啒S ?HC隕^JaAXD N婬埓騕f擆AT??l??鼁? 氺6!F€娦栮辬
羘豭峯旈L.PSu1珙a顄r[j没饬坘嫑o齑FOx? )扥菊焚鍋暭uVK@?舽?-qc齛?豤G齍?箶亷a?E鸜摇c1`o鴄魛?琲敶牉)?捏ЯY嘉驌SM>舄湼~^7?/?倕湏?潳 ?詛蛝銥?荨t樀飤鞵燿颔嬠i外卂uu$`?F醧bt?*s1 抸蝱;<豭掉??;Z卺?瓷|~吢CcC偠芵f饸X麿8 禫枘# 3??殍歼齵拆/惉莘m蜚閱@R
?p▽傺??g-BJ彸?馐?雯鴔?牶櫉FY?E鹍?a
?耸瓉ゝ頉?
+魤傌+哙桒?$鰇>]燤?榎鮭脎畅烄_?)?绪顸_ 蘸??8綗Q_qB奎?@G?飈t肣枉?E~h*? 裸軞仂 E野ez窘頷鲸4S术?櫅? i?C?唆3?P祆)嘕怑%讠?{疷q踾楑瓮
/n飐j栰?i??燉楁C躚縏?>澘p?g刜Q??搡i藴?€>ya硅鹭淿i俰矊2X廭)藆?Z沅Ⅴ湉1JA?l卵`:绺f%忢7@肴0R?蠡夋M4$乥?埈s€慐 蒟攧+奊€e漐1?k芡忠?:
悾偡韭趄辶、?E酄虬懨}Xi痃H<uu?Ua殖&纣KY?#M6?
`峴?璤靷6K淎 QtD?Z?荠?t纄g)e樖k遮骔襞?孶\M鐤1_沟拍=怖湓?[&贓鈳Uu瘩dE|z灀葲L}郏 }娺鉈蝒??鵷倹嵂 梁廑d訍踋磺e衭'槼鲌②0坍抑e?荵:湘[殬麨l.i!烽]itD3氍⒗+瓤<濈躘?肞M%騾?
褄
穠晪? 躈枉AY懔? 竈觗8!?yま糒吷€;}m?蓜t?細"
<D ?嵠R 桙O?鎊核 镧?@ ??謹寔唀 趠]S椧~Q添€嘧R糇?荆)耳胙?諩j@峖b?
7\ξ_y濋羨€黚+? 傄=茀{y?徖<贮.撬懾?z簡躔*?(υ禃??荖絅铉輑湜榍 樵'~鞳GJ!訙sE?
------------------------------------------------------------------------------------------------------------
.bash_history.txt
python Encrypt.py key.txt Plain.txt cipher.txt
python Encrypt.py key.txt flag.txt flag_encode.txt
rm flag.txt
rm key.txt首先看到Encrypt.py文件，明文一部分是和key异或，另外一部分是key先通过lfsr加密后再和明文异或。可见，解题的关键在于获取key。压缩表中还有其他四个文件，我们先看看.bash_history.txt文件，里面记载的是两个加密流程。一个是Plain.txt->cipher.txt，另外一个是flag.txt->flag_encode.txt。因为加密算法是一样的，所以我们可以通过第一组的两个文件Plain.txt和cipher.txt文件来获取key。由于本质上明文到密文的过程是通过异或运算来实现的，所以在获取到key后可以直接和密文再做一次加密运算就可以得到明文了。脚本如下：
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
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")
ff = open(sys.argv[3],"wb")
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'))
for i in range(len(a), lent):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
ff.write((tmp^ord(s[i])).to_bytes(1, byteorder='big'))
ff.close()注意：文件中数据的类型需要关注！