Python实现线性反馈移位寄存器实例&信息安全导论期中小作业

大家好，欢迎来到IT知识分享网。

我们先来了解一下什么是线性反馈移位寄存器（LFSR）

线性反馈移位寄存器（LFSR）简介

这里直接引用了大佬的博客

LFSR用于产生可重复的伪随机序列PRBS，该电路有n级触发器和一些异或门组成，如下图所示。

其中，gn为反馈系数，取值只能为0或1，取为0时表明不存在该反馈之路，取为1时表明存在该反馈之路；这里的反馈系数决定了产生随机数的算法的不同。用反馈函数表示成y=a0x^0+a1x+a2x^2…反馈函数为线性的叫线性移位反馈序列，否则叫非线性反馈移位序列。

简单来说LFSR就是给定前一状态的输出，将该输出再用作输入，用于产生下一次的随机输出，异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。

正文&LFSR的一种实现

今天，笔者的信息安全导论的期中小作业以及下方，要求实现一个遵循以下规则的线性反馈移位寄存器：
1.初始序列为：学号后三位的二进制，并补齐9位
2.反馈函数为：初始序列中，数值为’1’的下标进行异或运算
*当然，这样定义的反馈函数不够完善，有可能默认的学号转成二进制后只有一个1，这种情况将无法参与异或运算
例如：学号后三位为 360 的同学，应该首先将360转成2进制并补齐9位得到 101101110 （最低位为x0,最高位为x8），而对应的反馈函数为：f(x1,x2,x3,x5,x6,x8)=x1^x2^x3^x5^x6^x8
了解了基本的规则之后，我们就开始实现这个代码，然后就随便拿了一个学号试试

代码如下：

''' python3 实现反馈移位寄存器的输出序列 author:monster date:2021/4/16 '''
#encoding=utf-8
def get_s_cur(s):
	print("当前序列为：",s,"本次参与异或的是：",end='')
	res=int(s[int(index[0])])
	print(' ',s[int(index[0])],end='')
	for i in range(1,len(index)):
		res^=int(s[int(index[i])])
		print(' ',s[int(index[i])],end='')
	print(" 异或的结果为: ",res,end=' ')
	print(" 本次输出是: ",s[-1])
	out.append(s[-1])
	s=str(res)+s[:-1]
	return s
def get_res(out):
	re=''
	for i in out:
		re+=i
	return re
s0=str(bin(int(input("请输入你学号的后三位："))))[2:].zfill(9) #首先确定最初的序列
#s0='100'
index=[]
out=[] #输出序列
cycle=1
for i in range(len(s0)):	#把位值为1的下标找到
	if(s0[i]=='1'):
		index.append(i)
	else:
		continue
print("初始序列为：",s0)
print("需要参与反馈函数作异或运算的位数为：",end='')
for i in index:
	print('b',str(8-i+1),sep='',end=' ')
print()
s=get_s_cur(s0)
history.append(s)
while(True):
	if(s==s0):
		break
	else:
		print('*第',str(cycle).zfill(3),'次循环* ',end='',sep='')
		cycle+=1	
		s=get_s_cur(s)
re=get_res(out)
print("该序列的周期为：",cycle)
print("最终得到的生成序列为：",re)

芜湖，感觉很完美呐，正当我感觉可以收工的时候，突然有同学就开始找我说某些学号算不出来，比如这个168，每两位之间构成了循环，进入循环之后永远也不能再回到最开始的序列010101000

发现这种情况之后当然是先用代码把构成了内循环的学号都算出来，当然这里的原理是9位序列的线性反馈移位寄存器的最大周期是2^9-1也就是511，所以我们用以下代码将不可被计算的学号都列举出来，当然我们这里仅列举了100~200的学号

''' python3 爆破不可被计算的学号 author:monster date:2021/4/16 '''
#encoding=utf-8
def get_s_cur(s):
	#print("当前的产生序列为 -->",s,"需参与异或的位值为：",end='')
	res=int(s[int(index[0])])
	#print(' ',s[int(index[0])],end='')
	for i in range(1,len(index)):
		res^=int(s[int(index[i])])
		#print(' ',s[int(index[i])],end='')
	#print(" 异或的结果为: ",res)
	out.append(s[-1])
	s=str(res)+s[:-1]
	return s

for j in range(1,201):
	s0=str(bin(int(str(j))))[2:].zfill(9)
	#s0=str(bin(int(input("请输入你学号的后三位："))))[2:].zfill(9) #首先确定最初的序列
	#s0='100'
	index=[]
	out=[] #输出序列
	cycle=1
	for i in range(len(s0)):	#把位值为1的下标找到
		if(s0[i]=='1'):
			index.append(i)
		else:
			continue
	#index=[0,2]
	#print("初始序列为：",s0)
	#print("需要参与反馈函数作异或运算的位数为：",end='')
	''' for i in index: print('b',str(8-i+1),sep='',end=' ') print() '''
	s=get_s_cur(s0)
	m=1
	while(True):
		if(s==s0 or m>512):
			break
		else:
			m+=1
			cycle+=1	
			s=get_s_cur(s)
	if(m>512):
		print('学号',str(j).zfill(3),'不可被计算')

于是乎得到了如下一些计算结果

应该是这个算法设计有问题了，所以这里赶紧联系了老师，于是

好吧，姑且当作内循环也是循环吧，于是乎继续设计了如下代码，将每次运算的结果都进行储存，若在运算过程中出现了内循环则退出

''' python3 实现反馈移位寄存器的输出序列 author:monster date:2021/4/16 '''
#encoding=utf-8
def get_s_cur(s):
	print("当前序列为：",s,"本次参与异或的是：",end='')
	res=int(s[int(index[0])])
	print(' ',s[int(index[0])],end='')
	for i in range(1,len(index)):
		res^=int(s[int(index[i])])
		print(' ',s[int(index[i])],end='')
	print(" 异或的结果为: ",res,end=' ')
	print(" 本次输出是: ",s[-1])
	out.append(s[-1])
	s=str(res)+s[:-1]
	return s
def get_res(out):
	re=''
	for i in out:
		re+=i
	return re
s0=str(bin(int(input("请输入你学号的后三位："))))[2:].zfill(9) #首先确定最初的序列
#s0='100'
index=[]
out=[] #输出序列
cycle=1
for i in range(len(s0)):	#把位值为1的下标找到
	if(s0[i]=='1'):
		index.append(i)
	else:
		continue
#index=[0,2]
print("初始序列为：",s0)
print("需要参与反馈函数作异或运算的位数为：",end='')
for i in index:
	print('b',str(8-i+1),sep='',end=' ')
print()
history=[]
flag=0
s=get_s_cur(s0)
history.append(s)
while(True):
	if(s==s0):
		break
	else:
		print('*第',str(cycle).zfill(3),'次循环* ',end='',sep='')
		cycle+=1	
		s=get_s_cur(s)
		for i in history:
			if s==i:
				flag=1
				break
		if flag==1:
			print("该序列因产生内循环终止！")
			break
		history.append(s)
re=get_res(out)
print("该序列的周期为：",cycle)
print("最终得到的生成序列为：",re)
# print(history)
# print(s)

这样当再次发生内循环时，就能够正确退出程序，下面的例子可以看到当程序继续运行时，得到的序列111010011将与历史序列构成内循环，所以程序停止

学习了学习了