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

第七章 序列密码的设计与分析,序列的随机性 线性反馈移位寄存器 线性移位寄存器的一元多项式表示 m序列的伪随机性 线性反馈移位寄存器的分析方法 m序列密码的破译 序列的线性复杂度 B-M算法 非线性反馈移位寄存器的序列密码 非线性反馈移位寄存器序列 利用进位寄存器反馈的移位寄存器 非线性前馈序列 习题,1. 序列的随机性,序列密码中必须解决的问题是： 密钥流的质量（随机性）如何刻画？如何保证？ 无限长密钥流如何产生？ 合法用户如何很容易地获得或再生该密钥流？加密、解密如何同步？,真正的随机序列,看起来是随机的 不可预测性 不能重复产生 如果采用完全相同的输入对序列发生器操作两次，将得到两个不相关的随机序列,目的：产生具有随机数统计特性，并且不可再现的数数学描述：随机变量序列ξ1ξ2…ξi…，其中ξi（i = 1，2，…）是相互独立的、等概率取值0，1的随机变量密码学意义上安全的伪随机序列,看起来是随机的 不可预测性 即使给出产生序列的算法或硬件和所有以前产生的位序列的全部知识，也不可能通过计算来预测下一个随机位是什么,伪随机序列,看起来是随机的 满足伪随机序列的Golomb三条公设 0和1的个数相等 r游程基本上占游程总数的1/2r 异相自相关函数是一个常数能通过我们所能找到的所有随机性统计检验,两个基本概念,[定义] 在序列{ki | i=1，2，…}的周期为p，在它的一个周期kl+1，kl+2，…，kl+p中，如果：km≠km+1= km+2=…= km+r≠km+r +1，l+1≤m+1

例： 设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程两个基本概念,[定义] 设序列{ki | i=1，2，…}的周期为p，令nτ= #{i | 1≤i≤p，ki = ki +τ}， dτ= #{i | 1≤i≤p，ki ≠ ki +τ}，则R(τ) = ，τ = 0，1，2，…称为序列{ki | i=1，2，…}的自相关函数显然，R(np)= 1，（ n = 0，1，2，…，）这称为同相自相关函数 ；当τ≠np时，称R(τ)为异相自相关函数nτ就是延迟时间τ后的序列与原序列在一个周期内相同比特的个数，反映了序列比特的均匀分布特性如果nτ是一个常数，则说明分布完全均匀，也就是说，通过这种平移比较得不到任何其它信息随机序列的特性,Golomb随机性公设： ① 在序列的一个周期内，0与1的个数相差至多为1 ② 在序列的一个周期内，长为i的游程占游程总数的1/2i (i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等 ③ 异相自相关函数是一个常数。

①说明{ai}中0与1出现的概率基本上相同; ②说明0与1在序列中每一位置上出现的概率相同; ③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息伪随机序列应满足的条件,从密码系统的角度看，一个伪随机序列还应满足下面的条件： ① {ai}的周期相当大 ② {ai}的确定在计算上是容易的 ③ 由密文及相应的明文的部分信息，不能确定整个{ai}[例1],讨论序列：1010 1110 1100 0111 1100 1101 0010 0001010 1110 1100 0111 1100 1101 0010 000…的随机性小结,寻找生成一个具有良好随机特性密码序列的方法： 线性移位寄存器LFSR、 非线性移位寄存器NLFSR、 有限自动机、 线性同余等方法 混沌密码序列技术这些方法都是通过一个种子（有限长）产生具有足够长周期的、良好随机性的序列，在传递、存储序列时，只需传递、存储生成器的方法和种子2. 线性移位寄存器的结构与设计,移位寄存器与移位寄存器序列 n阶反馈移位寄存器 m序列及其随机性 LFSR的软件实现,2.1 移位寄存器与移位寄存器序列,一个8位移位寄存器,,移入一个0以后的寄存器内容,,2.1 移位寄存器与移位寄存器序列,,带反馈的移位寄存器,[例2],2.2 n阶反馈移位寄存器,几个术语 反馈移位寄存器的状态 初始状态 反馈移位寄存器序列 状态序列,,线性反馈移位寄存器的定义,如果一个GF(q)上的n阶反馈移位寄存器的反馈函数形如：f（x1,x2,…,xn-1,xn）= cn x1 + cn-1 x2 + … + c1 xn，其中ci∈GF(q)，1≤i≤n，则称其为线性反馈移位寄存器，用LFSR（Linear Feedback Shift Register）表示；否则，称其为非线性反馈移位寄存器，用NLFSR（Nonlinear Feedback Shift Register）表示。

线性反馈移位寄存器,显然，一个n阶线性反馈移位寄存器序列a0,a1, a2,…,an,… 满足递推关系式an+t=c1 an+t -1 + c2 an+t -2 + … + cn at，t≥0 其中c1, c2,., cn称为反馈系数，也叫抽头系数线性反馈移位寄存器,性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去一般对于n级线性反馈移位寄存器，总是假定cn=1[例3],写出例2的反馈函数，当初始状态为1010时，求输出序列的周期？,解：由图 可知反馈移位寄存器的阶数是4， 其反馈函数是：f（x1,x2,x3,x4）= x1 + x3 从表 7.2.1可知其输出序列为101000 101000…，周期为6[例4],设n=4，s0=（1,0,1,1），f（x1,x2,x3,x4）= x1 + x2，计算输出序列解：输出序列为101111000100110 1011110001 00110…可见该序列具有周期15，是否序列都是周期的呢？,[定理1 ],n级线性反馈移位寄存器的输出序列是周期的，周期最大为2n-1。

证明,密码设计者感兴趣序列 是什么？,2.3 m序列及其随机性,定义：周期为2n-1的LFSR序列称为m序列 m序列的特点： 长周期,m序列是伪随机序列 [定理],随机性如何？,如何生成？,结论m序列是我们要寻找的序列[定理] GF(2)上的n长m序列{ai}具有如下性质： ① 0,1平衡性：在一个周期内，0、1出现的次数分别为2n-1-1和2n-1 ②游程特性：在一个周期内，总游程数为2n-1；对1≤i≤n-2，长为i的游程有2n-i-1个，且0、1游程各半；长为n-1的0游程一个，长为n的1游程一个 ③ {ai}的自相关函数为,m序列的特性,,证明： ① Golomb第一公设：在n长m序列的一个周期内，除了全0状态外，每个n长状态（共有2n-1个）都恰好出现一次，这些状态中有2n-1个在a1位是1，其余2n-1-2n-1=2n-1-1个状态在a1位是0 ②Golomb第二公设：对n=1,2，易证结论成立 对n>2，当1≤i≤n-2时，n长m序列的一个周期内，长为i的0游程数目等于序列中如下形式的状态数目： 100…01*…*，其中n-i-2个*可任取0或1这种状态共有2n-i-2个。

同理可得长为i的1游程数目也等于 2n-i-2，所以长为i的游程总数为2n-i-1m序列是伪随机序列的证明,,由于寄存器中不会出现全0状态，所以不会出现0的n游程，但必有一个1的n游程，而且1的游程不会更大，因为若出现1的n+1游程，就必然有两个相邻的全1状态，但这是不可能的这就证明了1的n游程必然出现在如下的串中：当这n+2位通过移位寄存器时，便依次产生以下状态：,m序列是伪随机序列的证明,,由于 ， 这两个状态只能各出现一次，所以不会有1的n-1游程 于是在一个周期内，总游程数为,m序列是伪随机序列的证明,,③ Golomb第三公设：{ai}是周期为2n-1的m序列，对于任一正整数τ(0<τ<2n-1)，{ai}+{ai+τ}在一个周期内为0的位的数目正好是序列{ai}和{ai+τ}对应位相同的位的数目 设序列{ai}满足递推关系：ah+n=c1ah+n-1c2ah+n-2…cnah 故ah+n+τ=c1ah+n+τ-1c2ah+n+τ-2…cnah+τah+nah+n+τ=c1(ah+n-1ah+n+τ-1)c2(ah+n-2ah+n+τ-2)…cn(ahah+τ),m序列是伪随机序列的证明,,令bj=ajaj+τ，由递推序列{ai}可推得递推序列{bi}，{bi}满足 bh+n=c1bh+n-1c2bh+n-2…cnbh{bi}也是m序列。

为了计算R(τ)，只要用{bi}在一个周期中0的个数减去1的个数，再除以2n-1，即（证毕）,m序列是伪随机序列的证明,线性移位寄存器的特征多项式,注意：线性反馈移位寄存器与特征多项式是一一对应的，如果知道了线性反馈移位寄存器的结构，可以写出它的特征多项式，同样可以根据特征多项式画出移位寄存器的结构线性移位寄存器的特征多项式,下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列设Pn(x)为n次多项式，则l=min{k: Pn(x) | (xk-1)}称为多项式Pn(x)的阶阶为2n-1的不可约多项式称为本原多项式不可约多项式是指那些不能表示成f(x) g(x)的形式的多项式 例：P4(x)= x4+ x3+ x2 + x +1是不可约多项式线性移位寄存器的特征多项式,[例5],证明P4(x)= x4 + x +1是本原多项式，求以它为特征多项式的线性移位寄存器的输出序列和周期，该序列是m序列吗？,[例5-解],解：由P4(x)| x15-1，但不存在k<15，使得P4(x)| xk-1，所以P4(x)的阶为15P4(x)的不可约性由多项式x，x +1，x2 + x +1，不能整除 P4(x)即得，于是P4(x) = x4 + x +1是本原多项式。

P4(x)为特征多项式的输出序列满足递推关系假设初始状态为1001，对任何k≥5，用ak=ak-1⊕ak-4就可得出其输出序列，其输出序列为100100011110101 10010001110101.，它的周期是15=24-1，故该序列是m序列本原多项式,是否m序列和本原多项式之间有某些联系？,[定理2-3],定理2： {ai}∈ G(Pn)是m序列的充要条件是：Pn(x)是本原多项式 证明略 定理3： 生成m序列的n阶LFSR的个数是 ，其中φ为欧拉函数2.4 LFSR的软件实现,设p(x) = x32 + x7 + x5 + x3 + x2 + x + 1 可以使用32-位移位寄存器，且通过对第32，7，5，3，2和1位进行异或产生一个新的位作为反馈输入位（如图所示），得到的LFSR将是最大长度LFSR，它的周期是232-1有时把这种简单地将反馈抽头进行异或形成的LFSR，叫作Fibonacci配置（Fibonacci Configuration）2.4 LFSR的软件实现,C语言实现代码如下：int LFSR () {static unsigned long ShiftRegister = 1;/* Anything but 0. */ShiftRegister = ((((ShiftRegister >> 31)^ (ShiftRegister >> 6)^ (ShiftRegister >> 4)^ (ShiftRegister >> 2)^ (ShiftRegister >> 1)^ ShiftRegister))},。