资源描述:
《现代密码学(第二版) 教学课件 作者 陈鲁生第6章 序列密码与移位寄存器.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第6章序列密码与移位寄存器主要内容序列密码的基本原理移位寄存器与移位寄存器序列线性移位寄存器的表示线性移位寄存器序列的周期性线性移位寄存器的序列空间线性移位寄存器序列的极小多项式m序列的伪随机性B-M算法与序列的线性复杂度线性移位寄存器的非线性组合6.1序列密码的基本原理设明文、密钥、密文都是一个(0,1)序列,他们分别为则加密变换为解密变换为点击查看序列密码体制的模型6.2移位寄存器与移位寄存器序列一个q元域GF(q)上的n阶反馈移位寄存器由n个寄存器和一个反馈函数构成,如图所示.反馈移位寄存器的工作原理:当一个时钟脉冲来临时,第i级寄存器的内容传送给第i-1级寄存器,i=2,3,···
2、,n.第1级寄存器的内容为反馈移位寄存器的输出.反馈函数f的值传送给第n级寄存器.t≥0时状态t+1时状态反馈移位寄存器序列反馈移位寄存器的状态序列,点此查看定义6.16.3线性移位寄存器的表示线性移位寄存器的一元多项式表示线性移位寄存器的矩阵表示点击各项查看详细的表示方法6.4线性移位寄存器序列的周期性定义6.2设是GF(q)上的一个无穷序列,如果存在正整数p,使得对任意i≥0,都有则称为周期序列.满足该式的最小正整数称为该序列的周期,通常记为定理6.1设是GF(q)上的一个无穷序列,p是一个正整数,如果对任意i≥0,都有成立则的周期一定整除p,即定义6.3设是一个GF(q)上的n阶线性
3、移位寄存器序列.如果则称为GF(q)上的n阶m序列.定理6.2一个GF(q)上的n阶线性移位寄存器序列一定是周期序列,并且6.5线性移位寄存器的序列空间定理6.3设f(x)是GF(q)上的一个常数项为1的一元n次多项式,则由f(x)所确定的线性移位寄存器的序列空间G(f)是GF(q)上的一个n维线性空间.定理6.4设f(x)和h(x)是GF(q)上的两个常数项为1的一元多项式.如果f(x)
4、h(x),即f(x)整除h(x),则由f(x)所确定的线性移位寄存器的序列空间G(f)是由h(x)所确定的线性移位寄存器的序列空间G(h)的子空间,即G(f)⊆G(h).6.6线性移位寄存器序列极小多项
5、式定理6.5设是GF(q)上的一个周期序列,则一定存在唯一的一元多项式m(x),使得∈G(m),并且对任意满足的一元多项式f(x),都有m(x)
6、f(x).这里m(x)和f(x)都是GF(q)上的常数项为1的一元多项式定义6.4设是GF(q)上的一个周期序列,令I中次数最低的多项式称为的极小多项式定义6.5设,并且常数项不为0,满足的最小正整数r称为一元多项式f(x)的周期,记为p(f(x)).定理6.6设,并且常数项不为0,则f(x)的周期存在并且定理6.7设是GF(q)上的一个周期序列,为的极小多项式,则定义6.6设,,如果存在使得f(x)=g(x)h(x),则称f(x)为上的可约多项
7、式;否则,f(x)称为上的不可约多项式。定义6.7设,并且常数项不为0,如果f(x)是不可约多项式并且则称f(x)为上的本原多项式。定理6.8设f(x)是上的常数项为1的一元多项式,是以f(x)为联系多项式的线性移位寄存器的非零输出序列。如果f(x)是不可约的,则f(x)是的极小多项式。定理6.9设f(x)是上的常数项为1的一元多项式,。如果任意非零序列都是m序列,即则f(x)一定是不可约的。定理6.10设f(x)是上的常数项为1的一元多项式,。则任意非零序列,都是m序列,即当且仅当f(x)是本原多项式。6.7m序列的伪随机性GF(2)上的随机序列的一般特性1.分布特性对任意的都有2.相关
8、特性对任意的有3.游程特性对任意的i≥0,k≥1,有点击查看GF(2)上伪随机序列的性质6.7m序列的伪随机性定义6.8设是GF(2)上的一个周期为T的序列。称为序列的自相关函数。6.7m序列的伪随机性定理6.11设是GF(2)上的一个n阶m序列,则①在一个周期内,0和1的出现次数分别为和②在一个周期内,游程总数为;对任意的长为i的0游程和1游程都有个;长为的0游程有一个,长为n的1游程有一个.③的自相关函数为6.8B-M算法与序列的线性复杂度设是一个非负整数,满足而取假设已求出,设则计算如果则取如果则一定存在非负整数m,满足取6.9线性移位寄存器的非线性组合非线性滤波生成器通过非线性地滤
9、波一个线性移位寄存器的状态来得到一个非线性的密钥序列,如图所示非线性组合生成器通过非线性地组合一些线性移位寄存器的输出来得到一个非线性的密钥序列,如图所示ThankYou!点击此处返回定义6.1如果一个GF(q)上的n阶反馈移位寄存器的反馈函数形如其中则称其为线性反馈移位寄存器;否则,称其为非线性反馈移位寄存器.显然,一个n阶线性移位寄存器序列满足递推关系式点击此处返回点击此处返回设一个GF(q)上的n阶线性移位寄存器的