《数据加密技术（序列加密）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） 密钥流的每一位是前面固定数量密文位的函数。军方称为密文自动密钥 密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明
4、文（密文）相关。 设密钥序列产生器具有 n位存储，则加密时一位密文错误将影响后面连续 n个密文错误。在此之后恢复正确。 解密时一位密文错误也将影响后面连续 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,输入,输出,移
5、位脉冲,S0,S1,Sn-2,Sn1,输入,输出,移位脉冲,二、线性移位寄存器序列密码,1、线性移位寄存器（Linear Sift Registor） 例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 组成左移移位寄存器，并称每一时刻移位寄存器的取值为一个状态。 移位寄存器的输出同时要送入s
6、n-1，其值要通过函数 F(s0 ,s1 ,.,sn-1 )计算产生。 称函数 F(s0 ,s1 ,.,sn-1 )为反馈函数。 如果反馈函数 F(s0 ,s1 ,.,sn-1 )是s0 ,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 项不
7、存在，因此表示si不连接 。同理，gi=1表示si连接。故 gi的作用相当于一个开关。,二、线性移位寄存器序列密码,1、线性移位寄存器 形式地，用xi与si 相对应，则根据反馈函数可导出一个文字x的多项式：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、线性移位
8、寄存器 n级线性移位寄存器最多有2n个不同的状态。若其初始状态为零，则其后续状态恒为零。若其初始状态不为零，则其后续状态也不为零。因此，n级线性移位寄存器的状态周期2n 1，其输出序列的周期2n 1。 只要选择合适的连接多项式便可使线性移位寄存器的输出序列周期达到最大值2n 1，并称此时的输出序列为最大长度线性移位寄存器输出序列，简称为m序列。,二、线性移位寄存器序列密码,1、线性移位寄存器 仅当连接多项式g(x)为本原多项式时，其线性移位寄存器的输出序列为m序列。设f(x)为GF（2）上的多项式，使f(x)| x p1的最小正整数p称为f(x)的周期。如果f(x)的次数为n，且其周期为2 n
9、1，则称f(x)为本原多项式。已经证明，对于任意的正整数n，至少存在一个n次本原多项式。而且有有效的产生算法。,二、线性移位寄存器序列密码,1、线性移位寄存器 举例：设g(x)=x4 +x +1， g(x)为本原多项式，以其为连接多项式的线性移位寄存器的输出序列为100110101111000 ，它是周期为2 4-1=15的m序列。,S0,S1,S2,S3,g4=1,g3=0,g2=0,g1=1,g0=1,0001 0101 0010 1011 0100 0111 1001 1111 0011 1110 0110 1100 1101 1000 1010,二、线性移位寄存器序列密码,1、线性移位
10、寄存器 m序列具有良好的随机性：游程：称序列中连续的i个1为长度等于i的1游程，同样，称序列中连续的i个0为长度等于i的0游程。在一个周期内，0和 1出现的次数接近相等，即0出现的次数为2 n - 1 -1，1出现的次数为2 n-1 ；,二、线性移位寄存器序列密码,1、线性移位寄存器将序列的一个周期首尾相接，其游程总数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、线性移位寄存器自相关函数定义：设
11、ki是周期为p的序列，k0, k1, kp-1是其中一个周期子段，则 k0+, k1+, kp-1+也是一个周期子段。记这两个子段中相同的位数为A，不相同的位数为D，则自相关函数定义为：A-DP 自相关函数反映一个周期内平均每位的相同程度。,R(j)=,二、线性移位寄存器序列密码,1、线性移位寄存器自相关函数1 ,=0 -1/P ，0P-1 例： 1 0 0 1 1 0 1 0 1 1 1 1 0 0 00 0 1 1 0 1 0 1 1 1 1 0 0 0 1,R()=,m序列的自相关函数达到最佳值。,A7 D8 R( ) = -1/15,二、线性移位寄存器序列密码,2、线性移位寄存器序列密
12、码（第二次开课始处） m序列具有良好的随机性； 50年代开始用作密钥序列，并用于军用。 60年代发现其是不安全的。,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码设m序列线性移位寄存器的状态为 S=（s0,s1 ,.,sn-1）T， 下一状态为S=（s0,s1 ,.,sn-1）T ，其中s0 = s1s1 = s2. sn-2= sn-1sn-1= g0s0+g1s1+,.,+gn-1sn-1,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 写成矩阵形式：S=HS mod 20 1 0 .0 s0 s00 0 1 .0 s1 s10 0 0 .0H= . S = S = 0 0
13、 0 .1g0 g1.gn-1 sn-1 sn-1 矩阵H称为连接多项式的伴侣矩阵。,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 进一步假设攻击者知道了一段长2n位的明密文对，即已知：M= m1,m2 ,.,m2nC= c1,c2 ,.,c2n 于是可求出一段长2n位的密钥序列，K= k1 ,k2,.,k2n， 其中ki= mici = mi (miki)。,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码由此可以推出线性移位寄存器连续 n+1个状态：S1 =（k1,k2 ,.,kn）TS2 =（k2,k3 ,.,kn+1）TSn+1 =（kn+1,kn+2 ,.,k2n）T
14、 作矩阵X =（S1,S2 ,.,Sn）TY =（S2,S3 ,.,Sn+1）T,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码 根据S=HS mod 2，有S2=HS1S3=HS2. Sn+1=HSn 于是，Y=HX mod 2,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码因为m序列的线性移位寄存器连续 n个状态向量彼此线性无关，因此X矩阵为满秩矩阵，故存在逆矩阵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，0
15、011，0110，1101线性无关,二、线性移位寄存器序列密码,2、线性移位寄存器序列密码求逆矩阵X -1的计算复杂度为O（n 3）。一般，对于n=1000的线性移位寄存器序列密码，用每秒100万次的计算机，一天之内便可破译。,三、非线性序列密码,线性移位寄存器序列密码在已知明文攻击下是可破译的，可破译的根本原因在于线性移位寄存器序列是线性的，这一事实促使人们向非线性领域探索。 目前研究得比较充分的方法：非线性移位寄存器序列对线性移位寄存器序列进行非线性组合利用非线性分组码产生非线性序列,三、非线性序列密码,非线性移位寄存器序列令反馈函数f(s0,s1 ,.,sn-1 )为非线性函数便构成非线性移位寄存器，其输出序列为非线性序列。 称输出序列的周期达到最大值2n的非线性移位寄存器序列为M序列。 M序列的0，1分布和游分布是均匀的，而且周期最大。,
