第2章流密码(LFSR)

第2章流密码(序列密码),一、流密码的基本概念二、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示四、m序列的伪随机性五、m序列密码的破译,流密码的基本概念,流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0,1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术。,加密,解密,流密码的框图,kI安全信道kI,KGKGkikimicicimiEki(mi)Eki(mi),流密码的框图,消息流：m=m1m2mi，其中miM。密文流：c=c1c2ci=Ek1(m1)Ek2(m2)Eki(mi)，ciC。密钥流：ki，i0。一个完全随机的非周期序列，可以实现一次一密体制。但需要无限存储单元和复杂的输出逻辑函数f。i是第i时刻密钥流生成器的内部状态，以存储单元的存数矢量描述。,流密码的分类(1),同步流密码SSC(SynchronousStreamCipher)：i与明文消息无关，密钥流将独立于明文。特点：对于明文而言，这类加密变换是无记忆的。但它是时变的。只有保持两端精确同步才能正常工作。对主动攻击时异常敏感而有利于检测无差错传播(ErrorPropagation),流密码的分类(2),自同步流密码SSSC(Self-SynchronousStreamCipher)i依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1,m2,mi-1有关。一般在有限的n级存储下将与mi-1,mi-n有关。优点：具有自同步能力，强化了其抗统计分析的能力缺点：有n位长的差错传播。,密钥流与明文流不相互独立！,同步流密码,密钥流产生器加密变换器主要问题：设计一个滚动的密钥产生器，使k经其扩展成一个密钥流具有以下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。,有限状态自动机FA,有限状态自动机FA(FinitestateAutomation),具有离散输入和输出（输入集和输出集均有限）的一种数学模型有限状态集S=si|i=1,2,l有限输入字符集X=Xi|i=1,2,m有限输出字符集Y=Yk|k=1,2,n转移函数Yjf1(sj,Xj)Sj+1f2(sj,Xj),第j时刻输入XjX，输出YjY,第j时刻输入XjX，状态变为Sj+1S,例,S=s1,s2,s3,X=x1,x2,x3,Y=(y1,y2,y3)转移函数,FA的状态图表示,若输入为x1x2x1x3x3x1初始状态s1,状态序列：s1s2s2s3s2s1s2,输出序列：y1y1y2y1y3y1,作为FA的密钥流产生器,同步流密码的密钥流产生器可看为一个参数为k的FA输出集Z，状态集，状态转移函数和输出函数，初态0设计的关键是和,采用非线性函数,作为FA的密钥流产生器,具有非线性的的FA理论很不完善，通常采用线性状态转移函数以及非线性的输出函数可将此类产生器分为驱动部分和非线性组合部分。驱动部分控制状态转移非线性组合部分提供统计特性良好的序列,LFSR,两种常见的密钥流产生器,第四章流密码,一、流密码的基本概念二、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示四、m序列的伪随机性五、m序列密码的破译,线性反馈移位寄存器序列概念,移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如图所示。,每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列表示:a1,a2,an,例：3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表求出,非线性反馈移位寄存器,如果移位寄存器的反馈函数f(a1,a2,an)是a1，a2，an的线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如上图所示。,输出序列at满足an+t=cnatcn-1at+1c1an+t-1其中t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。,例，下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为：,1001101001000010101110110001111100110,输出序列为,反馈函数：,周期：31,在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0，这样的话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定c0=1。,线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期小于等于2n-1。其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。,第四章流密码,一、流密码的基本概念二、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示四、m序列的伪随机性五、m序列密码的破译,设n级LFSR的输出序列满足递推关系an+k=c1an+k-1c2an+k-2cnak(*)对任何k1成立。这种递推关系可用一个一元高次多项式P(x)=1+c1x+cn-1xn-1cnxn表示，称这个多项式为LFSR的特征多项式。,4.3线性移位寄存器的一元多项式表示,实例：（画出下列个移存器的逻辑框图，写出相应的线性递推式，并讨论由它们所产生的序列）,1、不可约多项式2、可约多项式3、本原多项式4、环式移存器,答案：1、该移存器产生三类周期相同（全为5）的序列及一个全零序列。2、该移存器产生五类周期分别为6、3、3、2、1的序列及一个全零序列。3、该移存器产生周期为15的m序列及一个全零序列。,1、不可约多项式2、可约多项式3、本原多项式4、环式移存器,本原多项式,设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或者阶。仅能被非0常数或自身的常数倍除尽，但不能被其他多项式除尽的多项式称为不可约多项式。若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。以本原多项式为连接多项式产生的非零序列均是m序列。,例：本原多项式,因为，f(x)|(x15-1)，但不存在比15小的常数m，使f(x)|(xm-1)，所以f(x)的阶是15。,因为，一次