第14-15讲 数据加密技术(序列加密).ppt

第第14-15讲讲 数据加密技数据加密技术术(序列加密序列加密)一、序列密码的基本概念一、序列密码的基本概念 明文、密文、密钥以位（字符）为单位加明文、密文、密钥以位（字符）为单位加解密解密；模型模型 密钥序列产生器种子密钥种子密钥密钥序列：密钥序列：k k1 1,k k2 2,密文密文:c c1 1,c c2 2,明文明文:m m1 1,m m2 2,C Ci i=m mi i k ki i一、序列密码的基本概念一、序列密码的基本概念人们用序列密码模仿人们用序列密码模仿 “一次一密一次一密 ”密码；密码；加密运算最简单，而且是对合运算；加密运算最简单，而且是对合运算；安全取决于密钥序列产生算法；安全取决于密钥序列产生算法；理论和技术都十分成熟；理论和技术都十分成熟；一、序列密码的基本概念一、序列密码的基本概念1 1、序列密码的分类、序列密码的分类同步序列密码同步序列密码同步序列密码同步序列密码（Synchronous Stream CipherSynchronous Stream Cipher）军方称为密钥自动密钥。军方称为密钥自动密钥。军方称为密钥自动密钥。军方称为密钥自动密钥。密钥序列产生算法与明文无关，所产生的密钥序列也密钥序列产生算法与明文无关，所产生的密钥序列也密钥序列产生算法与明文无关，所产生的密钥序列也密钥序列产生算法与明文无关，所产生的密钥序列也与明文无关。与明文无关。与明文无关。与明文无关。一位一位一位一位一位一位一位一位“吐出吐出吐出吐出”密钥。密钥。密钥。密钥。在通信过程中，通信的双方必须保持精确的同步，收在通信过程中，通信的双方必须保持精确的同步，收在通信过程中，通信的双方必须保持精确的同步，收在通信过程中，通信的双方必须保持精确的同步，收方才能正确解密，如果失步收方将不能正确解密。方才能正确解密，如果失步收方将不能正确解密。方才能正确解密，如果失步收方将不能正确解密。方才能正确解密，如果失步收方将不能正确解密。例如，如果通信中例如，如果通信中例如，如果通信中例如，如果通信中丢失丢失丢失丢失或或或或增加增加增加增加了一个密文字符，则收了一个密文字符，则收了一个密文字符，则收了一个密文字符，则收方的解密将一直错误。方的解密将一直错误。方的解密将一直错误。方的解密将一直错误。一、序列密码的基本概念一、序列密码的基本概念同步序列密码同步序列密码同步序列密码同步序列密码设密文设密文失步失步失步失步 c c=c c1 1,c c3 3,c c4 4,c cn-1n-1,c cn n （c c2 2 丢失丢失）k k=k k1 1,k k2 2,k k3 3,k kn-1n-1,k kn n（密钥正确）（密钥正确）m m=m m1 1,（m m1 1 后的明文全错后的明文全错）密钥序列产生算法密钥序列产生算法m m1 1,m m2 2,m m1 1,m m2 2,c c1 1,c c2 2,k k1 1,k k2 2,k k1 1,k k2 2,C Ci i=m mi i k ki i种子密钥种子密钥k k种子密钥种子密钥k k一、序列密码的基本概念一、序列密码的基本概念同步序列密码同步序列密码同步序列密码同步序列密码对失步的敏感性，使我们能够容易检测插入、对失步的敏感性，使我们能够容易检测插入、对失步的敏感性，使我们能够容易检测插入、对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。删除、重播等主动攻击。删除、重播等主动攻击。删除、重播等主动攻击。另一个优点是没有错误传播，当通信中某些密另一个优点是没有错误传播，当通信中某些密另一个优点是没有错误传播，当通信中某些密另一个优点是没有错误传播，当通信中某些密文字符产生了错误（文字符产生了错误（文字符产生了错误（文字符产生了错误（不是插入和删除不是插入和删除不是插入和删除不是插入和删除），只影），只影），只影），只影响相应字符的解密，不影响其它字符。响相应字符的解密，不影响其它字符。响相应字符的解密，不影响其它字符。响相应字符的解密，不影响其它字符。注意：错误与失步是不同的概念！注意：错误与失步是不同的概念！注意：错误与失步是不同的概念！注意：错误与失步是不同的概念！设密文错误设密文错误 c c=c c1 1,c c2 2,c c3 3,c cn-1n-1,c cn n （c c2 2 错错）k k=k k1 1,k k2 2,k k3 3,k kn-1n-1,k kn n （密钥正确）（密钥正确）m m=m m1 1,m,m3 3,m,mn-1n-1,m,mn n （仅（仅 m m2 2 错错）一、序列密码的基本概念一、序列密码的基本概念自自自自同步序列密码同步序列密码同步序列密码同步序列密码（Self-Synchronous Stream Cipher Self-Synchronous Stream Cipher）密钥流的每一位是前面固定数量密文位的函数。军方密钥流的每一位是前面固定数量密文位的函数。军方密钥流的每一位是前面固定数量密文位的函数。军方密钥流的每一位是前面固定数量密文位的函数。军方称为密文自动密钥称为密文自动密钥称为密文自动密钥称为密文自动密钥 密钥序列产生算法与明文（密文）相关，则所产生的密钥序列产生算法与明文（密文）相关，则所产生的密钥序列产生算法与明文（密文）相关，则所产生的密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明文（密文）相关。密钥序列与明文（密文）相关。密钥序列与明文（密文）相关。密钥序列与明文（密文）相关。设密钥序列产生器具有设密钥序列产生器具有设密钥序列产生器具有设密钥序列产生器具有 n n位存储，则加密时一位密文错位存储，则加密时一位密文错位存储，则加密时一位密文错位存储，则加密时一位密文错误将影响后面连续误将影响后面连续误将影响后面连续误将影响后面连续 n n个密文错误。在此之后恢复正确。个密文错误。在此之后恢复正确。个密文错误。在此之后恢复正确。个密文错误。在此之后恢复正确。解密时一位密文错误也将影响后面连续解密时一位密文错误也将影响后面连续解密时一位密文错误也将影响后面连续解密时一位密文错误也将影响后面连续 n n个明文错。在个明文错。在个明文错。在个明文错。在此之后恢复正确。此之后恢复正确。此之后恢复正确。此之后恢复正确。加解密会造成错误传播。在错误过去之后恢复正确。加解密会造成错误传播。在错误过去之后恢复正确。加解密会造成错误传播。在错误过去之后恢复正确。加解密会造成错误传播。在错误过去之后恢复正确。一、序列密码的基本概念一、序列密码的基本概念自同步序列密码同步序列密码密钥序列产生算法n位存储密钥序列产生算法n位存储m m1 1,m m2 2,m m1 1,m m2 2,c c1 1,c c2 2,k k1 1,k k2 2,k k1 1,k k2 2,C Ci i 的错误将影响的错误将影响n n位位种子密钥种子密钥k k种子密钥种子密钥k k二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器（Linear Sift Registor）例例1例例2 增加反馈增加反馈S0S1Sn-2Sn1输入输入输出输出移位移位脉冲脉冲S0S1Sn-2Sn1输入输入输出输出移位移位脉冲脉冲二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器（Linear Sift Registor）例例3 增加运算增加运算S0S1Sn-2Sn1输入输入输出输出移位移位脉冲脉冲二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器（Linear Sift Registor）一般模型一般模型F(s0,s1,sn1)S0S1Sn-2Sn1输出输出二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器（Linear Sift Registor）图中图中图中图中s s s s0 0 0 0 ，s s s s1 1 1 1 ，.，s s s sn-1 n-1 n-1 n-1 组成左移移位寄存器，组成左移移位寄存器，组成左移移位寄存器，组成左移移位寄存器，并称每一时刻移位寄存器的取值为一个并称每一时刻移位寄存器的取值为一个并称每一时刻移位寄存器的取值为一个并称每一时刻移位寄存器的取值为一个状态状态状态状态。移位寄存器的输出同时要送入移位寄存器的输出同时要送入移位寄存器的输出同时要送入移位寄存器的输出同时要送入s s s sn-1n-1n-1n-1，其值要通过函，其值要通过函，其值要通过函，其值要通过函数数数数 F(sF(sF(sF(s0 0 0 0,s,s,s,s1 1 1 1,.,s,.,s,.,s,.,sn-1n-1n-1n-1)计算产生。计算产生。计算产生。计算产生。称函数称函数称函数称函数 F(sF(sF(sF(s0 0 0 0,s,s,s,s1 1 1 1,.,s,.,s,.,s,.,sn-1n-1n-1n-1)为反馈函数。为反馈函数。为反馈函数。为反馈函数。如果反馈函数如果反馈函数如果反馈函数如果反馈函数 F(sF(sF(sF(s0 0 0 0,s,s,s,s1 1 1 1,.,s,.,s,.,s,.,sn-1n-1n-1n-1)是是是是s s s s0 0 0 0,s,s,s,s1 1 1 1 ,.,s,.,s,.,s,.,sn-1n-1n-1n-1 的线性函数，则称为线性移位寄存器，的线性函数，则称为线性移位寄存器，的线性函数，则称为线性移位寄存器，的线性函数，则称为线性移位寄存器，否则称为非线性移位寄存器。否则称为非线性移位寄存器。否则称为非线性移位寄存器。否则称为非线性移位寄存器。二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器设设F F(s s0 0,s s1 1,.,.,s sn-1n-1)为线性函数，则可写成为线性函数，则可写成 F F(s s0 0,s s1 1,.,.,s sn-1n-1)=g g0 0s s0 0+g g1 1s s1 1+,.,+,.,+g gn-1n-1s sn-1n-1 其中，其中，g g0 0,g g1 1,.,.,g gn-1n-1为为反馈系数。反馈系数。在在二二进进制制的的情情况况下下，式式中中的的+即即为为，反反馈馈系系数数g gi i GFGF(2(2)，如如果果g gi i=0=0，则则表表示示式式中中的的g gi is si i 项项不不存存在在，因因此此表表示示s si i不不连连接接 。同同理理，g gi i=1=1表表示示s si i连连接。故接。故 g gi i的作用相当于一个的作用相当于一个开关开关。二、二、线性移位寄存器序列密码线性移位寄存器序列密码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、线性移位寄存器、线性移位寄存器S0S1Sn1Sn2g gn n=1=1g gn-1n-1g g2 2g g1 1g g0 0=1=1二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器n n级级线线性性移移位位寄寄存存器器最最多多有有2 2n n个个不不同同的的状状态态。若若其其初初始始状状态态为为零零，则则其其后后续续状状态态恒恒为为零零。若若其其初初始始状状态态不不为为零零，则则其其后后续续状状态态也也不不为为零零。因因此此，n n级级线线性性移移位位寄寄存存器器的的状状态态周周期期2 2n n 11，其其输输出出序序列列的周期的周期2 2n n 11。只只要要选选择择合合适适的的连连接接多多项项式式便便可可使使线线性性移移位位寄寄存存器器的的输输出出序序列列周周期期达达到到最最大大值值2 2n n 11，并并称称此此时时的的输输出出序序列列为为最最大大长长度度线线性性移移位位寄寄存存器器输输出出序序列列，简称为简称为mm序列序列序列序列。二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器仅当连接多项式仅当连接多项式g g(x x)为为本原多项式本原多项式时，其线性移时，其线性移位寄存器的输出序列为位寄存器的输出序列为m m序列。序列。设设f f(x x)为为GFGF（2 2）上上的的多多项项式式，使使f f(x x)|x x p p1 1的的最最小小正正整整数数p p称称为为f f(x x)的的周周期期。如如果果f f(x x)的的次次数数为为n n，且且其其周周期期为为2 2 n n1 1，则则称称f f(x x)为为本本原原多多项式。项式。已已经经证证明明，对对于于任任意意的的正正整整数数n n，至至少少存存在在一一个个n n次次本原多项式。而且有有效的产生算法。本原多项式。而且有有效的产生算法。二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器举例：设举例：设g g(x)=(x)=x x4 4+x x+1+1，g g(x x)为本原多项式，为本原多项式，以其为连接多项式的线性移位寄存器的输出序列以其为连接多项式的线性移位寄存器的输出序列为为100110101111000100110101111000 ，它是周期为，它是周期为2 2 4 4-1=15-1=15的的m m序列。序列。S0S1S2S3g g4 4=1=1g g3 3=0=0g g2 2=0=0g g1 1=1=1g g0 0=1=10000001 1 010 0101 10010010 0 101 1011 10100100 0 011 0111 11001001 1 111 1111 10010011 1 111 1110 00110110 0 110 1100 01101101 1 100 1000 01011010 0二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器m序列具有良好的随机性：游程：称序列中连续的游程：称序列中连续的i i个个1 1为长度等于为长度等于i i的的1 1游程，同样，称序列中连续的游程，同样，称序列中连续的i i个个0 0为为长度等于长度等于i i的的0 0游程。游程。在一个周期内，0和 1出现的次数接近相等，即0出现的次数为2 n-1-1，1出现的次数为2 n-1；二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器 将序列的一个周期首尾相接，其游程总数N=2 n-1 。其中1游程和0游程的数目各占一半。当n2时，游程分布如下（1in-2）：长为长为i i的的1 1游程有游程有N/N/2 2 i+1i+1个；个；长为长为i i的的0 0游程有游程有N/N/2 2 i+1i+1个；个；长为长为n-1n-1的的0 0游程有游程有1 1个；个；长为长为n n的的1 1游程有游程有1 1个个.二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器 自相关函数 定义：定义：定义：定义：设设 k ki i 是周期为是周期为p p的序列，的序列，k k0 0,k k1 1,k kp-1p-1是其是其中一个周期子段，则中一个周期子段，则 k k0+0+,k k1+1+,k kp-1+p-1+也是一个周也是一个周期子段。记这两个子段中相同的位数为期子段。记这两个子段中相同的位数为A A，不相，不相同的位数为同的位数为D D，则自相关函数定义为：，则自相关函数定义为：A-D A-D P P自相关函数反映一个周期内平均每位的相同程度。自相关函数反映一个周期内平均每位的相同程度。自相关函数反映一个周期内平均每位的相同程度。自相关函数反映一个周期内平均每位的相同程度。R(j)=R(j)=二、二、线性移位寄存器序列密码线性移位寄存器序列密码1、线性移位寄存器、线性移位寄存器 自相关函数 1 ,=0 -1/P ，0P-1 例：例：1 0 0 1 1 0 1 0 1 1 1 1 0 0 01 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 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1R(R()=)=mm序列的自相关函数达到最佳值。序列的自相关函数达到最佳值。序列的自相关函数达到最佳值。序列的自相关函数达到最佳值。A A7 D7 D8 8R()=-1/15R()=-1/15二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码（第二次开课、线性移位寄存器序列密码（第二次开课始处）始处）m序列具有良好的随机性；50年代开始用作密钥序列，并用于军用。60年代发现其是不安全的。二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码 设设m m序列线性移位寄存器的状态为序列线性移位寄存器的状态为 S S=（s s0 0,s s1 1,.,.,s sn n-1-1）T T，下一状态为下一状态为S S=（s s0 0,s s1 1,.,.,s sn n-1-1）T T ，其中其中 s s0 0 =s s1 1 s s1 1 =s s2 2 .s sn n-2-2=s sn n-1-1 s sn n-1-1=g g0 0s s0 0+g g1 1s s1 1+,.,+,.,+g gn-1n-1s sn-1n-1二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码写成矩阵形式：写成矩阵形式：S S=HS HS mod 2 mod 2 0 1 0 0 1 0.0 0 s s0 0 s s0 0 0 0 1 0 0 1.0 0 s s1 1 s s1 1 0 0 0 0 0 0.0 0 H=H=.S S =S S=0 0 0 0 0 0.1 1 g g0 0 g g1 1.g gn-1 n-1 s sn-1 n-1 s sn-1 n-1 矩阵矩阵H H称为连接多项式的伴侣矩阵。称为连接多项式的伴侣矩阵。二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码进进一一步步假假设设攻攻击击者者知知道道了了一一段段长长2 2n n位位的的明明密密文文对对，即已知：即已知：MM=m m1 1,m m2 2,.,.,m m2n2n C C=c c1 1,c c2 2,.,.,c c2n2n于是可求出一段长于是可求出一段长2 2n n位的密钥序列，位的密钥序列，K K=k k1 1,k k2 2,.,.,k k2n2n，其中其中 k ki i=m mi ic ci i=m mi i (m mi ik ki i)。二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码 由此可以推出线性移位寄存器由此可以推出线性移位寄存器连续连续连续连续 n+1 n+1个状态个状态个状态个状态：S S1 1 =（k k1 1,k k2 2,.,.,k kn n）T T S S2 2 =（k k2 2,k k3 3,.,.,k kn+1n+1）T T S Sn+1n+1 =（k kn+1n+1,k kn+2n+2,.,.,k k2n2n）T T作矩阵作矩阵 X X =（S S1 1,S S2 2,.,.,S Sn n）T T Y Y =（S S2 2,S S3 3,.,.,S Sn+1n+1）T T二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码根据根据S S=HSHS mod 2 mod 2，有，有 S S2 2=HSHS1 1 S S3 3=HSHS2 2 .S Sn+1n+1=HSHSn n于是，于是，Y Y=HXHX mod 2 mod 2二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码 因因为为m m序序列列的的线线性性移移位位寄寄存存器器连连续续 n n个个状状态态向向量量彼彼此此线线性性无无关关，因因此此X X矩矩阵阵为为满满秩秩矩矩阵阵，故故存存在逆矩阵在逆矩阵X X -1-1，于是，于是 H H=YXYX -1-1 mod 2 mod 2 求求出出H H矩矩阵阵，便便确确定定出出连连接接多多项项式式g g(x)(x)，从从而而完全确定线性移位寄存器的结构。完全确定线性移位寄存器的结构。例：例：例：例：m m序列序列 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 连续连续4 4个状态个状态 10011001，00110011，01100110，11011101线性无关线性无关线性无关线性无关二、二、线性移位寄存器序列密码线性移位寄存器序列密码2、线性移位寄存器序列密码、线性移位寄存器序列密码 求求逆逆矩矩阵阵X X-1-1的的计计算算复复杂杂度度为为O O（n n 3 3）。一一般般，对对于于n=1000n=1000的的线线性性移移位位寄寄存存器器序序列列密密码码，用用每每秒秒100100万次的计算机，一天之内便可破译。万次的计算机，一天之内便可破译。三、非三、非线性序列密码线性序列密码线线性性移移位位寄寄存存器器序序列列密密码码在在已已知知明明文文攻攻击击下下是是可可破破译译的的，可可破破译译的的根根本本原原因因在在于于线线性性移移位位寄寄存存器器序序列列是是线线性性的的，这这一一事事实实促促使人们向使人们向非线性非线性领域探索。领域探索。目前研究得比较充分的方法：目前研究得比较充分的方法：非线性移位寄存器序列非线性移位寄存器序列 对线性移位寄存器序列进行非线性组合对线性移位寄存器序列进行非线性组合 利用非线性分组码产生非线性序列利用非线性分组码产生非线性序列三、非三、非线性序列密码线性序列密码非线性移位寄存器序列非线性移位寄存器序列 令反馈函数f(s0,s1,.,sn-1)为非线性函数便构成非线性移位寄存器，其输出序列为非线性序列。称输出序列的周期达到最大值2n的非线性移位寄存器序列为M序列序列。M序列的0，1分布和游分布是均匀的，而且周期最大。三、非三、非线性序列密码线性序列密码非线性移位寄存器序列非线性移位寄存器序列非线性移位寄存器反馈函数的数量极大非线性移位寄存器反馈函数的数量极大 GF（2）上的）上的n级移位寄存器共有级移位寄存器共有 2 n n个状个状 态，因此共有态，因此共有 种不同的反馈函数，其中种不同的反馈函数，其中 线性反馈函数只有线性反馈函数只有 2n-1n-1种，其余均为非线性。种，其余均为非线性。显然，非线性移位寄存器的空间极大！显然，非线性移位寄存器的空间极大！2 2n n 2 2三、非三、非线性序列密码线性序列密码非线性移位寄存器序列非线性移位寄存器序列例例例例：令令n n=3=3，f f(s s0 0,s s1 1,s s2 2)=)=s s0 0s s2 211s s1 1 s s2 2，由由于于与与运运算算为为非非线线性性运运算算，故故反反馈馈函函数数为为非非线线性性反反馈馈函数，其输出序列为函数，其输出序列为1011010010110100.，为，为M M 序列。序列。s0s1s2 输出输出三、非三、非线性序列密码线性序列密码对线性移位寄存器序列进行非线性组合对线性移位寄存器序列进行非线性组合 非线性移位寄存器序列的研究比较困非线性移位寄存器序列的研究比较困难，但人们对线性移位寄存器序列的研究难，但人们对线性移位寄存器序列的研究却比较充分和深入。于是人们想到，利用却比较充分和深入。于是人们想到，利用线性移位寄存器序列设计容易、随机性好线性移位寄存器序列设计容易、随机性好等优点，对一个或多个线性移位寄存器序等优点，对一个或多个线性移位寄存器序列进行非线性组合可以获得良好的非线性列进行非线性组合可以获得良好的非线性序列。序列。三、非三、非线性序列密码线性序列密码对线性移位寄存器序列进行非线性组合对线性移位寄存器序列进行非线性组合对一个对一个LSR进行非线性组合进行非线性组合在这里在这里在这里在这里用线性移位寄存器作为驱动源用线性移位寄存器作为驱动源用线性移位寄存器作为驱动源用线性移位寄存器作为驱动源来驱动非线来驱动非线来驱动非线来驱动非线性电路产生非线性序列。其中性电路产生非线性序列。其中性电路产生非线性序列。其中性电路产生非线性序列。其中用线性移位寄存器用线性移位寄存器用线性移位寄存器用线性移位寄存器序列来确保所产生序列的长周期和均匀性序列来确保所产生序列的长周期和均匀性序列来确保所产生序列的长周期和均匀性序列来确保所产生序列的长周期和均匀性，用非用非用非用非非线性电路来确保输出序列的非线性和其它密码非线性电路来确保输出序列的非线性和其它密码非线性电路来确保输出序列的非线性和其它密码非线性电路来确保输出序列的非线性和其它密码性质性质性质性质。通常称这里的非线性电路为。通常称这里的非线性电路为。通常称这里的非线性电路为。通常称这里的非线性电路为前馈电路前馈电路前馈电路前馈电路，称，称，称，称这种输出序列为这种输出序列为这种输出序列为这种输出序列为前馈序列前馈序列前馈序列前馈序列。对多个对多个LSR进行非线性组合进行非线性组合三、非三、非线性序列密码线性序列密码对线性移位寄存器序列进行非线性组合对线性移位寄存器序列进行非线性组合对一个对一个LSR进行非线性组合进行非线性组合非线性组合线性移位寄存器输出输出三、非三、非线性序列密码线性序列密码对线性移位寄存器序列进行非线性组合对线性移位寄存器序列进行非线性组合对多个对多个LSR进行非线性组合进行非线性组合线性移位寄存器 1输出输出线性移位寄存器 2线性移位寄存器 n非线性组合四、四、RC4序列密码序列密码 RC4RC4序列密码是美国序列密码是美国RSARSA数据安全公司设数据安全公司设计的一种序列密码。计的一种序列密码。RSARSA数据安全公司将数据安全公司将其收集在加密工具软件其收集在加密工具软件BSAFEBSAFE中。最初并中。最初并没有公布没有公布RC4RC4的算法。人们通过对软件进的算法。人们通过对软件进行逆向分析得到了算法。行逆向分析得到了算法。在这种情况下在这种情况下RSARSA数据安全公司于数据安全公司于19971997年公布了年公布了RC4RC4密码算法。密码算法。密钥密钥4040位的位的RC4RC4，通过通过Internet 32Internet 32小时小时攻破。攻破。四、四、RC4序列密码序列密码RC4RC4密码与基于移位寄存器的序列密码不密码与基于移位寄存器的序列密码不同。同。它是一种基于非线性数据表变换的序列密它是一种基于非线性数据表变换的序列密码。码。它以一个足够大的数据表为基础，对表进它以一个足够大的数据表为基础，对表进行非线性变换，产生非线性的密钥序列。行非线性变换，产生非线性的密钥序列。四、四、RC4序列密码序列密码RC4RC4使用使用256256个字节的个字节的S S表和两个指针（表和两个指针（I I 和和J J）。）。S S表的值表的值S S0 0,S S1 1,，S S255255是是0,1,0,1,，255255的一个排的一个排列。列。I I和和J J的初值为的初值为0 0。我们把我们把RC4RC4算法看成一个有限状态自动机。把算法看成一个有限状态自动机。把S S表表和和I I、J J指针的具体取值称为指针的具体取值称为RC4RC4的一个状态：的一个状态：T T=对对状状态态T T进进行行非非线线性性变变换换，产产生生出出新新的的状状态态 ，并并输出密钥序列中一个字节输出密钥序列中一个字节k 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序列密码序列密码在在用用RC4RC4加加解解密密之之前前，应应当当首首先先对对S S表表初初始始化化。初初始化的过程如下：始化的过程如下：对对S S S S表进行线性填充表进行线性填充，即令，即令 S0S00 0，S1S11 1，S2S22 2，S255S255 255255；用用密密钥钥填填充充另另一一个个256256字字节节的的R R R R表表R0,R1,R0,R1,，R255R255，如如果果密密钥钥的的长长度度小小于于R R R R表表的的长长度度，则则依次重复填充，直至将依次重复填充，直至将R R表填满。表填满。四、四、RC4序列密码序列密码 J J0;0;对于对于I=0 I=0 到到255255重复以下操作，重复以下操作，J J（J+J+S S S SI+I+R R R RII）mod 256;mod 256;交换交换S S S SII和和S S S SJJ 。注注注注意意意意，对对对对S S表表表表初初初初始始始始化化化化的的的的过过过过程程程程实实实实质质质质上上上上是是是是对对对对S S表表表表进进进进行行行行随随随随机机机机化化化化处处处处理理理理的的的的过过过过程程程程，只只只只有有有有当当当当这这这这一一一一过过过过程程程程完完完完成成成成后后后后，才才才才能能能能计计计计算算算算产产产产生生生生密密密密钥钥钥钥字符，才能进行加解密，否则将是不安全的。字符，才能进行加解密，否则将是不安全的。字符，才能进行加解密，否则将是不安全的。字符，才能进行加解密，否则将是不安全的。RC4RC4RC4RC4算法的优点是算法简单，高效，特别适合软件实现。算法的优点是算法简单，高效，特别适合软件实现。算法的优点是算法简单，高效，特别适合软件实现。算法的优点是算法简单，高效，特别适合软件实现。RC4RC4RC4RC4是目前应用最广的商密级序列密码。是目前应用最广的商密级序列密码。是目前应用最广的商密级序列密码。是目前应用最广的商密级序列密码。复习题复习题设设g g(x x)=)=x x4 4+x x3 3+1+1，g g(x x)为本原多项式，以其为本原多项式，以其为连接多项式组成线性移位寄存器。画出逻辑为连接多项式组成线性移位寄存器。画出逻辑图，写出输出序列及状态变迁。图，写出输出序列及状态变迁。令令n n=3=3，f f(s s0 0,s s1 1,s s2 2)=)=s s0 0s s2 211s s1 1 s s2 2，以其以其为连接多项式组成非线性移位寄存器。画出逻为连接多项式组成非线性移位寄存器。画出逻辑图，辑图，求出非线性移位寄存器的求出非线性移位寄存器的状态变迁及输状态变迁及输出。出。复习题复习题令令n n=3=3，f f(s s0 0,s s1 1,s s2 2)=1)=1s s0 0s s1 1s s2 2s s0 0s s1 1s s1 1 s s2 2s s2 2 s s3 3，以其为连接多项式组成非线性移位以其为连接多项式组成非线性移位寄存器。画出逻辑图，寄存器。画出逻辑图，求出非线性移位寄存器求出非线性移位寄存器的的状态变迁及输出。状态变迁及输出。证明：证明：证明：证明：GFGF（2 2）上的）上的）上的）上的 n n级移位寄存器共有级移位寄存器共有级移位寄存器共有级移位寄存器共有 2 2 n n n n个个个个状态，因此共有状态，因此共有状态，因此共有状态，因此共有 种不同的反馈函数，其中种不同的反馈函数，其中种不同的反馈函数，其中种不同的反馈函数，其中 线线线线性反馈函数只有性反馈函数只有性反馈函数只有性反馈函数只有 2 2n-1n-1n-1n-1种，其余均为非线性。种，其余均为非线性。种，其余均为非线性。种，其余均为非线性。2 2n n 2 2谢 谢！