对称密码学及其应用 第7章 序列密码的设计与分析

《对称密码学及其应用 第7章 序列密码的设计与分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章序列密码的设计与分析序列的随机性线性反馈移位寄存器线性移位寄存器的一元多项式表示m序列的伪随机性线性反馈移位寄存器的分析方法m序列密码的破译序列的线性复杂度B-M算法非线性反馈移位寄存器的序列密码非线性反馈移位寄存器序列利用进位寄存器反馈的移位寄存器非线性前馈序列习题1.序列的随机性序列密码中必须解决的问题是：密钥流的质量（随机性）如何刻画？如何保证？无限长密钥流如何产生？合法用户如何很容易地获得或再生该密钥流？加密、解密如何同步？真正的随机序列看起来是随机的不可预测性不能重复产生如果采用完全相同的输入对序列发生器操作两次，将得到两个不相关的随机序列目的：产生具有随机数统计特性，并且不

2、可再现的数。数学描述：随机变量序列ξ1ξ2…ξi…，其中ξi（i=1，2，…）是相互独立的、等概率取值0，1的随机变量。密码学意义上安全的伪随机序列看起来是随机的不可预测性即使给出产生序列的算法或硬件和所有以前产生的位序列的全部知识，也不可能通过计算来预测下一个随机位是什么伪随机序列看起来是随机的满足伪随机序列的Golomb三条公设0和1的个数相等r游程基本上占游程总数的1/2r异相自相关函数是一个常数能通过我们所能找到的所有随机性统计检验两个基本概念[定义]在序列{ki

3、i=1，2，…}的周期为p，在它的一个周期kl+1，kl+2，…，kl+p中，如果：km≠km+1=km+2=…=km+

4、r≠km+r+1，l+1≤m+1

5、i=1，2，…}的周期为p，令nτ=#{i

6、1≤i≤p，ki=ki+τ}，dτ=#{i

7、1≤i≤p，ki≠ki+τ}，则R(τ)=，τ=0，1，2，…称为序列{ki

8、i=1，2，…}的自相关函数。显然，R(np)=1，（n=0，1，2，…，）这称为同相自相关函数；当τ≠np时，

9、称R(τ)为异相自相关函数。nτ就是延迟时间τ后的序列与原序列在一个周期内相同比特的个数，反映了序列比特的均匀分布特性。如果nτ是一个常数，则说明分布完全均匀，也就是说，通过这种平移比较得不到任何其它信息。随机序列的特性Golomb随机性公设：①在序列的一个周期内，0与1的个数相差至多为1。②在序列的一个周期内，长为i的游程占游程总数的1/2i(i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。③异相自相关函数是一个常数。①说明{ai}中0与1出现的概率基本上相同;②说明0与1在序列中每一位置上出现的概率相同;③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息。伪

10、随机序列应满足的条件从密码系统的角度看，一个伪随机序列还应满足下面的条件：①{ai}的周期相当大。②{ai}的确定在计算上是容易的。③由密文及相应的明文的部分信息，不能确定整个{ai}。[例1]讨论序列：10101110110001111100110100100001010111011000111110011010010000…的随机性。小结寻找生成一个具有良好随机特性密码序列的方法：线性移位寄存器LFSR、非线性移位寄存器NLFSR、有限自动机、线性同余等方法混沌密码序列技术。这些方法都是通过一个种子（有限长）产生具有足够长周期的、良好随机性的序列，在传递、存储序列时，只需传递、存储生成器

11、的方法和种子。2.线性移位寄存器的结构与设计移位寄存器与移位寄存器序列n阶反馈移位寄存器m序列及其随机性LFSR的软件实现2.1移位寄存器与移位寄存器序列一个8位移位寄存器移入一个0以后的寄存器内容2.1移位寄存器与移位寄存器序列带反馈的移位寄存器移入单元1单元2单元3单元4输出001011000100100011010000101000010100001011000100100011010000101000010100[例2]2.2n阶反馈移位寄存器几个术语反馈移位寄存器的状态初始状态反馈移位寄存器序列状态序列线性反馈移位寄存器的定义如果一个GF(q)上的n阶反馈移位寄存器的反馈函数形如：

12、f（x1,x2,…,xn-1,xn）=cnx1+cn-1x2+…+c1xn，其中ci∈GF(q)，1≤i≤n，则称其为线性反馈移位寄存器，用LFSR（LinearFeedbackShiftRegister）表示；否则，称其为非线性反馈移位寄存器，用NLFSR（NonlinearFeedbackShiftRegister）表示。线性反馈移位寄存器显然，一个n阶线性反馈移位寄存器序列a0,a1,a2,…,an,…