密码学概论第2讲流密码资料

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2024/8/12,1,2.1,流密码的基本概念,2.2,线性反馈移位寄存器,2.3,线性移位寄存器的一元多项式表示,2.4 m,序列的伪随机性,2.5 m,序列密码的破译,2.6 非线性序列,第2章 流密码,2024/8/12,2,2.1,流密码的基本概念,流密码的基本思想,y=y,0,y,1,y,2,=E,z0,(x,0,)E,z1,(x,1,)E,z2,(x,2,)。,密钥流,z=z,0,z,1,，,明文串,x=x,0,x,1,x,2,：,2024/8/12,3,E,的选取,二元加法流密码,E,可表示为,yi=zi xi。,2024/8/12,4,流加密举例,0110011111,1100,1011010111,1001,1101001000,0101,0110011111,1100,1011010111,1001,1101001000,0101,0110011111,1101001000,1011010111,1011010111,1101001000,0110011111,2024/8/12,5,2.,1.3,密钥流产生器,状态转移函数,:,i,i+1,输出函数,:,i,z,i,，,目前最为流行和实用的密钥流产生器是线性反馈移位寄存器。,密钥流由密钥流发生器,f,产生：,zi=f(k,i)，,i,是加密器中的记忆元件（,存储器,）在时刻,i,的状态，,f,是由密钥,k,和,i,产生的函数。,2024/8/12,6,2.2,线性反馈移位寄存器,2024/8/12,7,反馈移位寄存器,状态：,每一时刻的状态对应于,GF(2),上的一个,n,维向量(,a1,a2,an),，,ai,是第,i,级存储器的内容。共有2,n,种可能的状态。,工作原理：,当第,i,个移位时钟脉冲到来时，根据寄存器此时的状态计算,f(a,1,a,2,a,n,)，,作为,a,n+1,每一级存储器,a,i,都将其内容向下一级,a,i-1,传递，（计算、移位、反馈、输出 ）,反馈函数,f(a,1,a,2,a,n,),：,n,元布尔函数，即,n,个变元,a,1,a,2,a,n,可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算。,2024/8/12,8,线性反馈移位寄存器,LFSR,线性反馈移位寄存器,LFSR（linear feedback shift register）:,反馈函数,f(a,1,a,2,a,n,),是线性函数,. f(a,1,a,2,a,n,)=c,n,a,1,c,n-1,a,2,c,1,a,n,其中常数,c,i,=0,或1，是模2加法。,c,i,=0,或1可用开关的断开和闭合来实现，,GF(2),上的,n,级线性反馈移位寄存器,输出序列,a,n+1,线性反馈移位寄存器实现简单、速度快、理论成熟,是构造密钥流生成器的最重要的部件。,例下图是一个5级线性反馈移位寄存器，其初始状态为（,a,5,，,a,4,，,a,3,，,a,2,，,a,1,）=(1,1, 0,0,1),输出序列为满足递推关系,a,k+5,=a,k+3,+ a,k,10011,01001000010101110110001111,10011,0,(a5,a4,a3,a2,a1),输出,0 1 0 1 1,1,1 1 0 0 1,1,0 0 1 0 1,1,0 1 1 0 0,0,1 0 0 1 0,0,1 0 1 1 0,0,0 1 0 0 1,1,反馈函数,f(a1,a2,a3,a4,a5)=a4 + a1,周期,31,LFSR,反馈函数,f(a,1,a,2,a,3,a,4,a,5,)=C,2,a,4,+ C,5,a,1,定义,LFSR,特征多项式（连接多项式）,P(x)=1+x,2,x,5,C,5,=1,C,2,=1,2024/8/12,11,2.3,线性移位寄存器的特征多项式与序列周期,n,级线性移位寄存器的输出序列满足,递推关系,a,n+k,=c,1,a,n+k-1,c,2,a,n+k-2,c,n,a,k,用,一个一元高次多项式表示,P(x)=1+c,1,x+,c,n-1,x,n-1,c,n,x,n,称这个多项式为,LFSR,的,特征多项式,（,连接多项式,）,2024/8/12,12,序列周期,序列周期,使对所有,k,，,ak+r=ak,成立的的最小整数,r,多项式的周期,使,f(x),除尽,x,p,-1,的最小整数,p,的取值。,序列的周期,r,与特征多项式的周期,p,密切相关。,(,r/p,),特征,多项式是,n,次既约多项式周期为,p,，则生成序列的周期为,p,。,输出序列最大周期为,2,n,-1,。,不可约多项式最大周期达到2,n,-1,。,序列为,m,序列,的充要条件特征多项式为,本原多项式。,本原多项式,m,序列,特征多项式,x,3,+x+1,多项式,周期,7,输出序列,a,k+3,=a,k,+a,k+2,1 0 1 0 0 1 1 1 0 1 0,1 0 1 0 0 1 1 1 0 1 0,序列,周期,7,x,3,+x,2,+1,7,a,k+3,=a,k,+a,k+1,1 0 1 1 1 0 0,1 0 1 1,7,特征多项式,x,3,+x,2,+x,+1,多项式,周期,4,输出序列,a,k+3,=a,k,+a,k+1,+a,k+2,1 0 1 0 1 0 1 0,序列周期,2,x,3,+1,3,a,k+3,=a,k,1 0 1 1 0 1,3,初始,101,2024/8/12,15,m,序列的伪随机性,随机性,:,如果密钥流是周期的，要完全做到随机性是困难的。,游程,:,设,ai=(a,1,a,2,a,3,),为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。,自相关函数,:,R()=(1/T),k=1,T,(-1),ak,(-1),ak+,序列向后平移,位，,0T-1,定义中的和式表示序列,a,i,与,a,i+,在一个周期内对应位相同的位数与对应位不同的位数之差。当,=0,时，,R()=1；,当,0,时，称,R(),为异相自相关函数。,1 0 1 0 0 1 1,1 0 1 0,R(1)=R(2)=,.=-1/7,2024/8/12,16,在序列一个周期内，0与1出现,个数相差至多为,1,;,（,0,和,1,出现概率基本相同）,长为,l,的,游程,占1/2,l,，,在等长的游程中，,“,0,”,游程,和,“,1,”,游程,个数相等或至多差一个。,（,0,和,1,在各位置上出现概率基本相同）,异相自相关函数是常数,与白噪声的自相关函数(,函数)相近,（序列平移不能提供更多信息）,PN,序列可用于通信中同步序列、码分多址(,CDMA)、,导航中多基站码、雷达测距码等。,PN,序列虽与,白噪声序列相似,，但远还不能满足密码体制要求。,Golomb,随机性假设,PN,序列,m,序列满足,Golomb,的三条伪随机假设,。,1 0 1 0 0 1 1,1 0 1 0,2024/8/12,17,满足密码体制的另外三个条件,周期,p,要足够大，如大于10,50,；,序列,a,i,产生易于高速生成；,当序列,a,i,的任何部分暴露时，要分析整个序列，在计算上是不可行的,条件,决定了密码的强度，是流密码理论的核心。它包含了流密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等,。,2024/8/12,18,2.4 m,序列的伪随机性,m,序列否满足密码要求？,n,级,m,序列的周期为2,n,1，,n,大，周期指数地加大，例如,n,=166,时，,p,=10,50,(9.353610465 10,49,)。,只要知道,n,次本原多项式，,m,序列极易生成。,m,序列极不安全，只要泄露,2,n,位,连续数字，就可完全确定出反馈多项式系数。,定理,m,序列满足,Golomb,的三条伪随机假设,。,2024/8/12,19,由于,X,可逆,序列递推关系,:,限制了其在密码学中的应用,2.5 m,序列密码破译,n,级,LFSR,2024/8/12,20,若,X,可逆,序列递推关系,:,令,限制了其在密码学中的应用,因为,X,是由,S,1,S,2,S,n,作为列向量，要证,X,可逆，只要证明这,n,个向量线性无关。,设,m,是使,S,1,S,2,S,m,线性相关的最小整数，即存在不全为0的系数,l,1,l,2,l,m,，,其中不妨设,l,1,=1，,使得,证明,X,是可逆的,设序列,a,i,满足线性递推关系：,S,h+1,=M,S,h,密钥流的级数,m-1=n,故,m=n+1,S1,S2,Sn,线性无关，由此构成的,X,可逆,攻击实例：,设敌手得到密文串,1011010111,10010和相应的明文串,0110011111,11001，因此可计算出相应的密钥流为,1101001000,01011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可用密钥流的前,10,个比特建立如下方程,已知明文攻击,2024/8/12,25,非线性移位寄存器序列,f(a1,a2,a3)=a1a2+a3,输出序列,10111011.,，周期为,4.,对线性移位寄存器序列进行非线性组合,非线性移位寄存器研究困难，,对线性移位寄存器研究充分。,2.6 非线性序列,2024/8/12,26,密钥流生成器,驱动子系统,一个或多个,LFSR,来实现,非线性组合子系统,用非线性组合函数,F,来实现,生成序列评价,周期极大化,线性复杂度,最短,LFSR,级数,极小特征多项式：最短,LFSR,的特征多项式,非线性组合,2024/8/12,27,2.6.2,J-K,触发器,令,c,-1,=0,驱动序列,ak,和,bk,分别为,m,级和,n,级,m,序列,m,、,n,互素,a0+b0=1,C,k,周期,p = (2,m,-1)(2,n,-1),2024/8/12,28,例 令,m=2,n=3，,两个驱动,m,序列分别为,a,k,=0,1,1,0,1,1,和,b,k,=1,0,0,1,0,1,1,输出序列,c,k,其周期为(2,2,-1)(2,3,-1)=21。,0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,如果知道,ck,中相邻位的值,ck-1,和,ck，,就可以推断出,ak,和,bk,中的一个，通过密码分析的方法得到序列,ak,和,bk。,为了克服上述缺点，,Pless,提出了由多个,J-K,触发器序列驱动的多路复合序列方案,2024/8/12,29,2.6.3,Pless,生成器,2024/8/12,30,2.6.4 钟控序列生成器,钟控序列最基本的模型是用一个,LFSR,控制另外一个,LFSR,的移位时钟脉冲,.,易于由硬件实现。,当,LFSR1,输出1时，移位时钟脉冲通过与门使,LFSR2,进行一次移位。,当,LFSR1,输出0时，移位时钟脉冲无法通过与门影响,LFSR2,LFSR2,状态不改变。,2024/8/12,31,前提：,LFSR1,和,LFSR2,输出序列分别是,a,k,和,b,k,对应极小特征多项式分别为,GF(2),上的,m,和,n,次本原多项式,f,1,(x),和,f,2,(x)，,且,m|n,结论：序列,c,k,周期,p=(2,m,-1)(2,n,-1),线性复杂度为,n(2,m,-1),极小特征多项式为,相关结论,例设,LFSR1,为3级,m,序列生成器，其特征多项式为,f,1,(x)=1+x+x,3,。,设初态为,(1,1,1)，,输出序列为,a,k,=1,1,1,0,1,0,0,。,又设,LFSR2,为3级,m,序列生成器，其特征多项式为,f,2,(x)=1+x,2,+x,3,且初态为,(1,1,1),则,b,k,=1,1,1,0,0,1,0，。,LFSR2,状态向量为,k,，,则变化为,:,c,k,的周期为(2,3,-1),2,=49,a,k+3,=a,k,+a,k+2,b,k+3,=b,k,+b,k+1,ck=,1,1,1,0,0,0,0,0,1,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0,.,序号,状态,输出,0,1,1,1,1,1,0,1,1,1,2,0,0,1,1,3,1,0,0,0,3,1,0,0,0,4,0,1,0,0,4,0,1,0,0,4,0,1,0,0,ck=,1,1,1,0,0,0,0,0,b,k+3,b,k+1,b,k,c,k,bk=1,1,1,0,0,1,0，,。,2024/8/12,34,c,k,的周期（2,3,-1）* （2,3,-1）,=49,极小特征多项式为1+,x,14,+x,21,线性复杂度为3,（2,3,-1）=21,线性等价生成器如下图,f,2,(x)=1+x,2,+x,3,周期,p=(2,m,-1)(2,n,-1),线性复杂度为,n(2,m,-1),极小特征多项式,2024/8/12,35,有限状态自动机,具有离散输入和输出的一种数学模型,由3部分组成：, 有限状态集,S=s,i,|i=1,2,l。,有限输入字符集,A,1,=A,(1),j,|j=1,2,m,和有限输出字符集,A,2,=A,(2),k,|k=1,2,n。,输出函数,A,(2),k,=f,1,(s,i,A,(1),j,)，,转移函数,s,h,=f,2,(s,i,A,(1),j,),即在状态为,s,i,，,输入为,A,(1),j,时，输出为,A,(2),k,，,而状态转移为,s,h,。,2024/8/12,36,例,S=s,1,s,2,s,3,，A,1,=A,(1),1,A,(1),2,A,(1),3,，A,2,=A,(2),1,A,(2),2,A,(2),3,，,转移函数由表2.1给出。,输入序列为,A,(1),1,A,(1),2,A,(1),1,A,(1),3,A,(1),3,A,(1),1,，,初始状态为,s,1,，,则得到状态序列,s,1,s,2,s,2,s,3,s,2,s,1,s,2,输出字符序列,A,(2),1,A,(2),1,A,(2),2,A,(2),1,A,(2),3,A,(2),1,2024/8/12,37,同步流密码的,密钥流产生器,可看成一个,有限状态自动机,。,由一个输出符号集,Z、,一个状态集、两个函数,和,以及一个初始状态,0,组成。,2024/8/12,38,蓝牙是一种用于替代某些电子设备上使用电缆或连线的短距离无线连接技术。,具有同样蓝牙接口的设备连接可以实现无线连接，有效连接距离达,10,米，一般的传输速度都有,1M,目前配置蓝牙接口的电子设备却不是很多；没有蓝牙接口的电脑可通过加装蓝牙适配器来实现无线连接，适配器一般都是,USB,接口，可以插在电脑上，使用方便。,采用无线电波为载体，安全性差，信息传输需加密,加密算法使用流密码,.,流密码的应用,蓝牙,Bluetooth,2024/8/12,39,蓝牙流加密原理,2024/8/12,40,4,个,LFSR,比特长度分别为,25,，,31,，,33,，,39,；长度之和是,128bit,特征多项式都是本原多项式,设,xti,为,LSFRi,的第,t,个符号,2024/8/12,41,IEEE 802.11,是当今无线局域网,WLAN,通用的标准，,IEEE 802.11,安全框架中包括站点接入认证方法、数据加密,WEP,协议等。,WEP,是基于,RC4,加密和,CRC-32,校验的安全协议。,RC4,是大名鼎鼎的,RSA,三人组中的头号人物,Ron Rivest,在,1987,年设计的密钥长度可变的流加密算法。该算法的速度可以达到,DES,加密的,10,倍左右，且具有很高级别的非线性。,RC4,序列密码,2024/8/12,42,以一个足够大的数据表为基础，对表进行非线性变化，产生非线性的密钥序列。,基于非线性数据表的序列密钥,RC4,特点,2024/8/12,43,RC4,算法,S,表初始化,对,S,表进行随机处理过程，只有初始化后，才可以产生密钥流,密钥流产生器（有限状态自动机）,S,表状态转移函数,输出函数,加密解密,明文,S,表,+,输出密钥,2024/8/12,44,（一）,S,表初始化,S,表线性填充，如,S0=0,S1=1,S2=2,.,S255=255,用密钥填充,R,表，,R0,R1,R2,.,R255,J=0,I=0,到,255,，重复,J=J+S(I)+R(I) mod 256,交换,S(I),和,S(J),2024/8/12,45,（二）密钥流产生器,S,表状态转移函数,I=0,J=0,I=I+1 mod 256,J=J+S(I) mod 256,交换,S(I),和,S(J),输出函数,h=S(I)+S(J),k=S(h),循环执行状态转移和输出，循环次数取决于明文字节数,2024/8/12,46,运行结果,2024/8/12,47,作业,33,页,3,、,6,设,g(x)=x,4,+x,2,+1,，,g(x),为,GF,（,2,）上的多项式，以其为连接多项式组成线性移位寄存器。画出逻辑框图。设法遍历其所有状态，并写出其状态变迁及相应的输出序列。,人有了知识，就会具备各种分析能力，,明辨是非的能力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”通过阅读科技书籍，我们能丰富知识，,培养逻辑思维能力；,通过阅读文学作品，我们能提高文学鉴赏水平，,培养文学情趣；,通过阅读报刊，我们能增长见识，扩大自己的知识面。,有许多书籍还能培养我们的道德情操，,给我们巨大的精神力量，,鼓舞我们前进,。,