数据加密技术(序列加密).ppt

《数据加密技术(序列加密).ppt》由会员分享，可在线阅读，更多相关《数据加密技术(序列加密).ppt（47页珍藏版）》请在三一办公上搜索。

1、密 码 学,序列密码xxx鲁东大学计算机学院,一、序列密码的基本概念,明文、密文、密钥以位（字符）为单位加解密；模型,密钥序列产生器,种子密钥,密钥序列：k1,k2,密文:c1,c2,明文:m1,m2,Ci=miki,一、序列密码的基本概念,人们用序列密码模仿“一次一密”密码；加密运算最简单，而且是对合运算；安全取决于密钥序列产生算法；理论和技术都十分成熟；,一、序列密码的基本概念,1、序列密码的分类同步序列密码（Synchronous Stream Cipher）军方称为密钥自动密钥。密钥序列产生算法与明文无关，所产生的密钥序列也与明文无关。一位一位“吐出”密钥。在通信过程中，通信的双方必须

2、保持精确的同步，收方才能正确解密，如果失步收方将不能正确解密。例如，如果通信中丢失或增加了一个密文字符，则收方的解密将一直错误。,一、序列密码的基本概念,同步序列密码设密文失步 c=c1,c3,c4,cn-1,cn（c2 丢失）k=k1,k2,k3,kn-1,kn（密钥正确）m=m1,（m1 后的明文全错）,密钥序列产生算法,密钥序列产生算法,m1,m2,m1,m2,c1,c2,k1,k2,k1,k2,Ci=miki,种子密钥k,种子密钥k,一、序列密码的基本概念,同步序列密码对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。另一个优点是没有错误传播，当通信中某些密文字符产生了错误

3、（不是插入和删除），只影响相应字符的解密，不影响其它字符。注意：错误与失步是不同的概念！设密文错误 c=c1,c2,c3,cn-1,cn（c2 错）k=k1,k2,k3,kn-1,kn（密钥正确）m=m1,m3,mn-1,mn（仅 m2 错）,一、序列密码的基本概念,自同步序列密码（Self-Synchronous Stream Cipher）密钥流的每一位是前面固定数量密文位的函数。军方称为密文自动密钥密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明文（密文）相关。设密钥序列产生器具有 n位存储，则加密时一位密文错误将影响后面连续 n个密文错误。在此之后恢复正确。解密时一位密文错误

4、也将影响后面连续 n个明文错。在此之后恢复正确。加解密会造成错误传播。在错误过去之后恢复正确。,一、序列密码的基本概念,自同步序列密码,密钥序列产生算法n位存储,密钥序列产生算法n位存储,m1,m2,m1,m2,c1,c2,k1,k2,k1,k2,Ci 的错误将影响n位,种子密钥k,种子密钥k,二、线性移位寄存器序列密码,1、线性移位寄存器（Linear Sift Registor）例1例2 增加反馈,S0,S1,Sn-2,Sn1,输入,输出,移位脉冲,S0,S1,Sn-2,Sn1,输入,输出,移位脉冲,二、线性移位寄存器序列密码,1、线性移位寄存器（Linear Sift Registor）

5、例3 增加运算,S0,S1,Sn-2,Sn1,输入,输出,移位脉冲,二、线性移位寄存器序列密码,1、线性移位寄存器（Linear Sift Registor）一般模型,F(s0,s1,sn1),S0,S1,Sn-2,Sn1,输出,二、线性移位寄存器序列密码,1、线性移位寄存器（Linear Sift Registor）图中s0，s1，.，sn-1 组成左移移位寄存器，并称每一时刻移位寄存器的取值为一个状态。移位寄存器的输出同时要送入sn-1，其值要通过函数 F(s0,s1,.,sn-1)计算产生。称函数 F(s0,s1,.,sn-1)为反馈函数。如果反馈函数 F(s0,s1,.,sn-1)是s

6、0,s1,.,sn-1 的线性函数，则称为线性移位寄存器，否则称为非线性移位寄存器。,二、线性移位寄存器序列密码,1、线性移位寄存器设F(s0,s1,.,sn-1)为线性函数，则可写成 F(s0,s1,.,sn-1)=g0s0+g1s1+,.,+gn-1sn-1 其中，g0,g1,.,gn-1为反馈系数。在二进制的情况下，式中的+即为，反馈系数gi GF(2)，如果gi=0，则表示式中的gisi 项不存在，因此表示si不连接。同理，gi=1表示si连接。故 gi的作用相当于一个开关。,二、线性移位寄存器序列密码,1、线性移位寄存器形式地，用xi与si 相对应，则根据反馈函数可导出一个文字x的多

7、项式：g(x)=gn x n+gn-1 x n-1+,.,+g1x+g0 称g(x)为线性移位寄存器的连接多项式。与下图对照可知，gn=g0=1。否则，若gn=0则输出不反馈到sn-1，若g0=0则s0不起作用，应将其去掉。,二、线性移位寄存器序列密码,1、线性移位寄存器,S0,S1,Sn1,Sn2,gn=1,gn-1,g2,g1,g0=1,二、线性移位寄存器序列密码,1、线性移位寄存器n级线性移位寄存器最多有2n个不同的状态。若其初始状态为零，则其后续状态恒为零。若其初始状态不为零，则其后续状态也不为零。因此，n级线性移位寄存器的状态周期2n 1，其输出序列的周期2n 1。只要选择合适的连接

8、多项式便可使线性移位寄存器的输出序列周期达到最大值2n 1，并称此时的输出序列为最大长度线性移位寄存器输出序列，简称为m序列。,二、线性移位寄存器序列密码,1、线性移位寄存器仅当连接多项式g(x)为本原多项式时，其线性移位寄存器的输出序列为m序列。设f(x)为GF（2）上的多项式，使f(x)|x p1的最小正整数p称为f(x)的周期。如果f(x)的次数为n，且其周期为2 n1，则称f(x)为本原多项式。已经证明，对于任意的正整数n，至少存在一个n次本原多项式。而且有有效的产生算法。,二、线性移位寄存器序列密码,1、线性移位寄存器举例：设g(x)=x4+x+1，g(x)为本原多项式，以其为连接多

9、项式的线性移位寄存器的输出序列为，它是周期为2 4-1=15的m序列。,S0,S1,S2,S3,g4=1,g3=0,g2=0,g1=1,g0=1,0001 01010010 10110100 01111001 11110011 11100110 11001101 10001010,二、线性移位寄存器序列密码,1、线性移位寄存器m序列具有良好的随机性：游程：称序列中连续的i个1为长度等于i的1游程，同样，称序列中连续的i个0为长度等于i的0游程。在一个周期内，0和 1出现的次数接近相等，即0出现的次数为2 n-1-1，1出现的次数为2 n-1；,二、线性移位寄存器序列密码,1、线性移位寄存器 将

10、序列的一个周期首尾相接，其游程总数N=2 n-1。其中1游程和0游程的数目各占一半。当n2时，游程分布如下（1in-2）：长为i的1游程有N/2 i+1个；长为i的0游程有N/2 i+1个；长为n-1的0游程有1个；长为n的1游程有1个.,二、线性移位寄存器序列密码,1、线性移位寄存器 自相关函数 定义：设ki是周期为p的序列，k0,k1,kp-1是其中一个周期子段，则 k0+,k1+,kp-1+也是一个周期子段。记这两个子段中相同的位数为A，不相同的位数为D，则自相关函数定义为：A-D P自相关函数反映一个周期内平均每位的相同程度。,R(j)=,二、线性移位寄存器序列密码,1、线性移位寄存器

11、 自相关函数 1,=0-1/P，0P-1 例：1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1,R()=,m序列的自相关函数达到最佳值。,A7 D8R()=-1/15,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码（第二次开课始处）m序列具有良好的随机性；50年代开始用作密钥序列，并用于军用。60年代发现其是不安全的。,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 设m序列线性移位寄存器的状态为 S=（s0,s1,.,sn-1）T，下一状态为S=（s0,s1,.,sn-1）T，其中 s0=s1 s1=s2.

12、sn-2=sn-1 sn-1=g0s0+g1s1+,.,+gn-1sn-1,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码写成矩阵形式：S=HS mod 2 0 1 0.0 s0 s0 0 0 1.0 s1 s1 0 0 0.0 H=.S=S=0 0 0.1 g0 g1.gn-1 sn-1 sn-1 矩阵H称为连接多项式的伴侣矩阵。,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码进一步假设攻击者知道了一段长2n位的明密文对，即已知：M=m1,m2,.,m2n C=c1,c2,.,c2n于是可求出一段长2n位的密钥序列，K=k1,k2,.,k2n，其中 ki=mici=mi(mi

13、ki)。,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 由此可以推出线性移位寄存器连续 n+1个状态：S1=（k1,k2,.,kn）T S2=（k2,k3,.,kn+1）T Sn+1=（kn+1,kn+2,.,k2n）T作矩阵 X=（S1,S2,.,Sn）T Y=（S2,S3,.,Sn+1）T,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码根据S=HS mod 2，有 S2=HS1 S3=HS2.Sn+1=HSn于是，Y=HX mod 2,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 因为m序列的线性移位寄存器连续 n个状态向量彼此线性无关，因此X矩阵为满秩矩阵，故

14、存在逆矩阵X-1，于是 H=YX-1 mod 2 求出H矩阵，便确定出连接多项式g(x)，从而完全确定线性移位寄存器的结构。例：m序列 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 连续4个状态 1001，0011，0110，1101线性无关,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 求逆矩阵X-1的计算复杂度为O（n 3）。一般，对于n=1000的线性移位寄存器序列密码，用每秒100万次的计算机，一天之内便可破译。,三、非线性序列密码,线性移位寄存器序列密码在已知明文攻击下是可破译的，可破译的根本原因在于线性移位寄存器序列是线性的，这一事实促使人们向非线性领域探索

15、。目前研究得比较充分的方法：非线性移位寄存器序列 对线性移位寄存器序列进行非线性组合 利用非线性分组码产生非线性序列,三、非线性序列密码,非线性移位寄存器序列 令反馈函数f(s0,s1,.,sn-1)为非线性函数便构成非线性移位寄存器，其输出序列为非线性序列。称输出序列的周期达到最大值2n的非线性移位寄存器序列为M序列。M序列的0，1分布和游分布是均匀的，而且周期最大。,三、非线性序列密码,非线性移位寄存器序列非线性移位寄存器反馈函数的数量极大 GF（2）上的n级移位寄存器共有 2 n个状 态，因此共有 种不同的反馈函数，其中 线性反馈函数只有 2n-1种，其余均为非线性。显然，非线性移位寄存

16、器的空间极大！,2n 2,三、非线性序列密码,非线性移位寄存器序列例：令n=3，f(s0,s1,s2)=s0s21s1 s2，由于与运算为非线性运算，故反馈函数为非线性反馈函数，其输出序列为10110100.，为M 序列。,s0,s1,s2,输出,三、非线性序列密码,对线性移位寄存器序列进行非线性组合 非线性移位寄存器序列的研究比较困难，但人们对线性移位寄存器序列的研究却比较充分和深入。于是人们想到，利用线性移位寄存器序列设计容易、随机性好等优点，对一个或多个线性移位寄存器序列进行非线性组合可以获得良好的非线性序列。,三、非线性序列密码,对线性移位寄存器序列进行非线性组合对一个LSR进行非线性

17、组合在这里用线性移位寄存器作为驱动源来驱动非线性电路产生非线性序列。其中用线性移位寄存器序列来确保所产生序列的长周期和均匀性，用非非线性电路来确保输出序列的非线性和其它密码性质。通常称这里的非线性电路为前馈电路，称这种输出序列为前馈序列。对多个LSR进行非线性组合,三、非线性序列密码,对线性移位寄存器序列进行非线性组合对一个LSR进行非线性组合,非线性组合,线性移位寄存器,输出,三、非线性序列密码,对线性移位寄存器序列进行非线性组合对多个LSR进行非线性组合,线性移位寄存器 1,输出,线性移位寄存器 2,线性移位寄存器 n,非线性组合,四、RC4序列密码,RC4序列密码是美国RSA数据安全公司

18、设计的一种序列密码。RSA数据安全公司将其收集在加密工具软件BSAFE中。最初并没有公布RC4的算法。人们通过对软件进行逆向分析得到了算法。在这种情况下RSA数据安全公司于1997年公布了RC4密码算法。密钥40位的RC4，通过Internet 32小时攻破。,四、RC4序列密码,RC4密码与基于移位寄存器的序列密码不同。它是一种基于非线性数据表变换的序列密码。它以一个足够大的数据表为基础，对表进行非线性变换，产生非线性的密钥序列。,四、RC4序列密码,RC4使用256个字节的S表和两个指针（I 和J）。S表的值S0,S1,，S255是0,1,，255的一个排列。I和J的初值为0。我们把RC4

19、算法看成一个有限状态自动机。把S表和I、J指针的具体取值称为RC4的一个状态：T=对状态T进行非线性变换，产生出新的状态，并输出密钥序列中一个字节k。,四、RC4序列密码,RC4的下一状态函数定义如下：I0，J0;I=I+1 mod 256;J=J+SI mod 256;交换SI和SJ。RC4的输出函数定义如下：h=SI+SJ mod 256;k=Sh。,四、RC4序列密码,在用RC4加解密之前，应当首先对S表初始化。初始化的过程如下：对S表进行线性填充，即令 S00，S11，S22，S255 255；用密钥填充另一个256字节的R表R0,R1,，R255，如果密钥的长度小于R表的长度，则依次

20、重复填充，直至将R表填满。,四、RC4序列密码,J0;对于I=0 到255重复以下操作，J（J+SI+RI）mod 256;交换SI和SJ。注意，对S表初始化的过程实质上是对S表进行随机化处理的过程，只有当这一过程完成后，才能计算产生密钥字符，才能进行加解密，否则将是不安全的。RC4算法的优点是算法简单，高效，特别适合软件实现。RC4是目前应用最广的商密级序列密码。,复习题,设g(x)=x4+x3+1，g(x)为本原多项式，以其为连接多项式组成线性移位寄存器。画出逻辑图，写出输出序列及状态变迁。令n=3，f(s0,s1,s2)=s0s21s1 s2，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出非线性移位寄存器的状态变迁及输出。,复习题,令n=3，f(s0,s1,s2)=1s0s1s2s0s1s1 s2s2 s3，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出非线性移位寄存器的状态变迁及输出。证明：GF（2）上的 n级移位寄存器共有 2 n个状态，因此共有 种不同的反馈函数，其中 线性反馈函数只有 2n-1种，其余均为非线性。,2n 2,谢 谢！,