第5次课流密码1讲义教材.ppt

第三章 流密码一、流密码的基本概念二、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示四、m序列的伪随机性五、m序列密码的破译Date1单击此处编辑母版标题样式单击此处编辑母版副标题样式*2一、流密码的基本概念 流密码的基本概念n流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0, 1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现n流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)n核心问题是密钥流生成器的设计n保持收发两端密钥流的精确同步是实现可靠解密的关键技术加密解密Date3 流密码的框图n消息流：m=m1m2mi，其中miMn密文流： c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ciCn密钥流：ki，i0 一个完全随机的非周期序列，可以实现一次一密体制但需要无限存储单元和复杂的输出逻辑函数fi是第i时刻密钥流生成器的内部状态，以存储单元的存数矢量描述Date5 流密码的分类(1)n同步流密码SSC(Synchronous Stream Cipher)： i与明文消息无关，密钥流将独立于明文。

n特点：n对于明文而言，这类加密变换是无记忆的但它是时变的n只有保持两端精确同步才能正常工作n对主动攻击时异常敏感而有利于检测n无差错传播(Error Propagation) Date6流密码的分类(2)n自同步流密码SSSC(Self-Synchronous Stream Cipher) i依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1, m2 ,mi-1有关一般在有限的n级存储下将与mi-1,mi-n有关n优点：具有自同步能力，强化了其抗统计分析的能力n缺点：有n位长的差错传播密钥流与明文流不相互独立！Date7同步流密码n密钥流产生器n加密变换器n主要问题：设计一个滚动的密钥产生器，使k经其扩展成一个密钥流具有以下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析有限状态自动机FADate8有限状态自动机FA(Finite state Automation)n具有离散输入和输出（输入集和输出集均有限）的一种数学模型n有限状态集S=si|i=1,2,ln有限输入字符集X= Xi|i=1,2,mn有限输出字符集Y= Yk|k=1,2,nn转移函数nYjf 1(sj ,Xj)nSj+1 f 2(sj ,Xj)第j时刻输入Xj X ，输出YjY第j时刻输入Xj X ，状态变为Sj+1SDate9例nS=s1,s2,s3,X=x1, x2,x3,Y=(y1,y2,y3)n转移函数f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s2Date10FA的状态图表示 若输入为x1x2x1x3x3x1初始状态s1状态序列：s1s2s2s3s2s1s2输出序列： y1 y1 y2 y1 y3 y1Date11作为FA的密钥流产生器n同步流密码的密钥流产生器可看为一个参数为k的FAn输出集Z，状态集，状态转移函数和输出函数，初态0n设计的关键是和ikkkzi采用非线性函数Date12作为FA的密钥流产生器n具有非线性的的FA理论很不完善，通常采用线性状态转移函数以及非线性的输出函数n可将此类产生器分为驱动部分和非线性组合部分。

n驱动部分控制状态转移n非线性组合部分提供统计特性良好的序列LFSRDate13两种常见的密钥流产生器LFSR非线性组合函数ziLFSRLFSRLFSR非线性组合函数ziDate14第三章 流密码一、流密码的基本概念二、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示四、m序列的伪随机性五、m序列密码的破译Date15线性反馈移位寄存器序列概念移位寄存器是流密码产生密钥流的一个主要组成部分GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如图所示每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态每一时刻的状态可用n长序列表示: a1,a2,anDate16132第7时刻 0 0 1第0时刻 0 0 1第1时刻 1 0 0第2时刻 1 1 0第3时刻 1 1 1第4时刻 0 1 1第5时刻 1 0 1第6时刻 0 1 0产生序列为：1001110例：3级LFSRDate17例： 3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表求出状态（a1,a2,a3)输出1 0 11 1 01 1 10 1 11 0 11 1 0 101110非线性反馈移位寄存器Date18 如果移位寄存器的反馈函数f(a1,a2,an)是a1，a2，an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。

此时f可写为其中常数ci=0或1， 是模2加法ci=0或1可用开关的断开和闭合来实现，如上图所示Date19输出序列at满足an+t=cnat cn-1at+1 c1an+t-1其中t为非负正整数线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一Date20例，下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为：1001101001000010101110110001111100110输出序列为反馈函数：周期：31Date21 性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0，这样的话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去 若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置一般对于n级线性反馈移位寄存器，总是假定cn=1Date22线性反馈移位寄存器输出序列的性质完全由其反馈函数决定n级线性反馈移位寄存器最多有2n个不同的状态若其初始状态为0，则其状态恒为0若其初始状态非0，则其后继状态不会为0。

因此n级线性反馈移位寄存器的状态周期小于等于2n-1其输出序列的周期与状态周期相等，也小于等于2n-1只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列Date23第三章 流密码一、流密码的基本概念二、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示四、m序列的伪随机性五、m序列密码的破译Date24设n级LFSR的输出序列满足递推关系an+k=c1an+k-1 c2an+k-2 cnak (*)对任何k1成立这种递推关系可用一个一元高次多项式 P(x)=1+c1x+cn+1xn-1cnxn表示，称这个多项式为LFSR的特征多项式2.3 线性移位寄存器的一元多项式表示Date25实例：（画出下列个移存器的逻辑框图，写出相应的线性递推式，并讨论由它们所产生的序列）1、不可约多项式2、可约多项式3、本原多项式4、环式移存器Date26答案：1、该移存器产生三类周期相同（全为5）的序列及一个全零序列2、该移存器产生五类周期分别为6、3、3、2、1的序列及一个全零序列3、该移存器产生周期为15的m序列及一个全零序列1、不可约多项式2、可约多项式3、本原多项式4、环式移存器Date27本原多项式n设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或者阶。

n仅能被非0常数或自身的常数倍除尽，但不能被其他多项式除尽的多项式称为不可约多项式n若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式以本原多项式为连接多项式产生的非零序列均是m序列Date28例：本原多项式因为，f(x)|(215-1)，但不存在比15小的常数m，使f(x)|(2m-1)，所以f(x)的阶是15因为，一次多项式x、x+1不能整除f(x)，所以任一个三次多项式也不能整除f(x);二次多项式x2+x+1不能整除f(x)；所以f(x)是不可约多项式若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式所以f(x)是本原多项式Date29例：（32，7，5，3，2，1，0） C语言代码？Date30。