首页 > 编程学习 > Python实现线性反馈移位寄存器实例信息安全导论期中小作业

我们先来了解一下什么是线性反馈移位寄存器(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将与历史序列构成内循环,所以程序停止
在这里插入图片描述

学习了学习了

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000