密码学
（第七讲）
序列密码
张焕国
武汉大学计算机学院
目录
1、密码学密码学的基本概念的基本概念
2、古典、古典密码密码
3、数据加密标准（、数据加密标准（DESDES））
4、高级高级数据加密标准（数据加密标准（AESAES））
5、中国商用密码（、中国商用密码（SMS4SMS4））
6、分组密码的应用技术
7、序列密码
8、习题课：复习对称密码
9、公开密钥密码（、公开密钥密码（11）
目录
10、公开密钥密码（10、公开密钥密码（22）
11、数字签名（1）
12、数字签名（2）
13、13、HASH 函数
14、14、认证
15、15、密钥管理
16、16、PKI PKI技术技术
17、习题课：复习公钥密码17、习题课：复习公钥密码
18、总复习18、总复习//检查：综合实验
一、序列密码的基本概念①明文、密文、密钥以位（字符）为单位加解密；
种子密钥②模型
密钥序列
产生器
明文: m 1, m 2,…密钥序列：k 1, k 2,…密文: c 1, c 2,…
C i = m i ⊕k i
一、序列密码的基本概念③人们用序列密码模仿“一次一密”密码；④加密运算最简单，而且是对合运算；⑤安全取决于密钥序列产生算法；⑥理论和技术都十分成熟；
⑦核心密码的主流密码。
一、序列密码的基本概念
1、序列密码的分类
①同步序列密码（Synchronous Stream Cipher）•密钥序列产生算法与明文无关，所产生的密钥序列也与明文无关。
•在通信过程中，通信的双方必须保持精确的同步，收方才能正确解密，如果失步收方将不能正确解密。例如，如果通信中丢失或增加了一个密文字符，则收方的解密将一直错误。
一、序列密码的基本概念①同步序列密码
种子密钥k
密钥序列
产生算法
1, m 2,
k 1, k 2,… c 1, c 2,…种子密钥k 密钥序列产生算法C i = m i ⊕k i k 1, k 2,… m 1, m 2,…
设密文失步c =c 1, c 3, c 4, … c n -1, c n （c 2丢失）
⊕k =k 1, k 2, k 3, … k n -1, k n （密钥正确）
m =m 1, ×, ×, … ×, ×（m 1后的明文全错）
一、序列密码的基本概念①同步序列密码
•对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。
•另一个优点是没有错误传播，当通信中某些密文字符产生了错误（不是插入和删除），只影响相应字符的解密，不影响其它字符。•注意：错误与失步是不同的概念！
设密文错误c =c 1, c 2, c 3, … c n -1, c n （c 2错）
⊕k =k 1, k 2, k 3, … k n -1, k n （密钥正确）
m =m 1, ×, m3, … mn -1, mn （仅m 2错）
一、序列密码的基本概念②自同步序列密码（Self Self--Synchronous Stream Cipher ）•密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明文（密文）相关。•设密钥序列产生器具有n 位存储，则加密时一位密文错误将影响后面连续n 个密文错误。在此之后恢复正确。
•解密时一位密文错误也将影响后面连续n 个明文错。在此之后恢复正确。
•加解密会造成错误传播。在错误过去之后恢复正确。
一、序列密码的基本概念②自同步序列密码
种子密钥k
密钥序列
产生算法
n 位存储
k 1, k 2,…
m 1212种子密钥k 密钥序列产生算法n 位存储k 1, k 2,…
m 1, m 2,…
C i 的错误将影响n 位
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•例1
输出S 0S 1S n-2S n －1输入
移位
脉冲
•例2 增加反馈
输出S 0S 1S n-2S n －1输入
移位
脉冲
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•例3 增加运算
输出S 0S 1S n-2S n －1输入
移位
脉冲
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•一般模型
F (s 0, s 1,…,s n －1)
S 0S 1S n-2S n －1输出
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•图中图中ss 0，s 1，... ...，，s n -1 组成左移移位寄存器，并称每一时刻移位寄存器的取值为一个状态。•移位寄存器的输出同时要送入移位寄存器的输出同时要送入ss n -1，其值要通过函数F(s0 ,s 1,...,s n -1) 计算产生。•称函数F(s0 ,s 1,...,s n -1) 为反馈函数。•如果反馈函数F(s0 ,s 1,...,s n -1) 是s 0 ,s 1,...,s n -1的线性函数，则称为线性移位寄存器，否则称为非线性移位寄存器。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•设F (s 0, s 1, ... ..., , s n -1) 为线性函数为线性函数，，则可写成F (s 0, s 1, ... ..., , s n -1) =g 0s 0+g 1s 1+,+,......,+,+g n -1s n -1其中，其中，g 0, g 1, ... ..., , g n -1为反馈系数反馈系数。。•在二进制的情况下，在二进制的情况下，式中的+即为即为⊕⊕，反馈系数g i ∈GF (2) ，如果g i =0，则表示式中的g i s i 项不存在，存在，因此表示s i 不连接。同理同理，，g i =1表示s i 连接。故g i 的作用相当于一个开关。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
i •形式地形式地，，用x 与s i 相对应相对应，，则根据反馈函数可导出一个文字x 的多项式：
n n -1g(x)=g n x +gn -1x +,...+,...,+g,+g1x +g0•称g(x)为线性移位寄存器的连接多项式线性移位寄存器的连接多项式。。
•与图对照可知，与图对照可知，g n =g0=1。否则否则，，若g n =0则输出不反馈到输出不反馈到ss n -1，若g 1=0则s 0不起作用不起作用，，应将其去掉。应将其去掉。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
g 0=1
S 0g 1S 1g 2S n －2g n -1S n －1g n =1
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•n 级线性移位寄存器最多有2n 个不同的状态个不同的状态。。若其初始状态为零，则其后续状态恒为零初始状态为零，则其后续状态恒为零。。若其初始状态不为零，状态不为零，则其后续状态也不为零则其后续状态也不为零。。因此因此，，n 级线性移位寄存器的状态周期≤线性移位寄存器的状态周期≤2n –1，其输出序列的周期≤的周期≤2n –1。
•只要选择合适的连接多项式便可使线性移位寄存器的输出序列周期达到最大值2n –1，并称此时的输出序列为最大长度线性移位寄存器输出序列，输出序列为最大长度线性移位寄存器输出序列，简称为m 序列。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器•仅当连接多项式g (x ) 为本原多项式时，其线性移位寄存器的输出序列为m 序列。•设f (x ) 为GF （2）上的多项式上的多项式，，使f (x ) |x p －1的最小正整数p 称为f (x ) 的周期。如果f (x ) 的次数为n ，且其周期为且其周期为22n －1，则称f (x ) 为本原多项式为本原多项式。。•已经证明已经证明，，对于任意的正整数n ，至少存在一个n 次本原多项式本原多项式。。而且有有效的产生算法而且有有效的产生算法。。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•举例：设g (x)=x 4+x +1+1，，g (x ) 为本原多项式，以其为连接多项式的线性移位寄存器的输出序列为[***********][1**********]0······，它是周期为，它是周期为224-1=15的m 00010101序列。
g 0=1
S 0g 1=1S 1g 2=0S 2g 3=0S 3g 4=[***********]110
1101
[***********]1011001000
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•m 序列具有良好的随机性：
游程：称序列中连续的i 个1为长度等于为长度等于ii 的1游程，同样，称序列中连续的i 个0为长度等于i长度等于i 的0游程。
①在一个周期内，0和1出现的次数接近
n -n -1-1，1出现相等，即0出现的次数为2
n -1的次数为2 ；
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
②将序列的一个周期首尾相接，其游程总
n -1 。数N=2
③其中其中11游程和游程和00游程的数目各占一半。当n>2时，游程分布如下（n>2时，游程分布如下（1≤i≤n1≤i≤n--2）：•长为长为ii 的1游程有游程有N/N/2 i+1个；
•长为长为ii 的0游程有游程有N/N/2 i+1个；
•长为长为nn -1的0游程有游程有11个；
•长为长为nn 的1游程有游程有11个.
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
④自相关函数④自相关函数
定义：设{k i }是周期为p 的序列，k 0, k 1,…, k p -1是其中一个周期子段，则k 0+τ, k 1+τ,…, k p -1+τ也是一个周期子段。记这两个子段中相同的位数为A ，不相同的位数为D ，则自相关函数定义为：
A -D R(j)=P
自相关函数反映一个周期内平均每位的相同程度。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
④自相关函数④自相关函数
1, τ=0R(τ)=-1/P，0
m 序列的自相关函数达到最佳值。
[1**********]000
[**************]A ＝7 D＝8R(τ ) = - ) = -1/15
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
•m 序列具有良好的随机性；
•50年代开始用作密钥序列，并用于军用。•60年代发现其是不安全的。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
设m 序列线性移位寄存器的状态为
S =（s 0, s 1, ... ..., , s n -1）T ，
S ’=（s ’0, s ’1, ... ..., , s ’n -1）T ，其中
s ’0=s 1
s ’1=s 2
...
s ’n -2=s n -1
s ’n -1=g 0s 0+g 1s 1+,+,......,+,+g n -1s n -1
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
S ’=HS mod 2
s ’0s 0010... 0
001... 0s ’1s 1000... 0
S ’=S =H=...
000... 1
0g 1... g n -’n -1n -1H 称为连接多项式的伴侣矩阵称为连接多项式的伴侣矩阵。。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
2n 位的明密文对即已知：
..., , m 2n M =m 1, m 2, ...
C =c 1, c 2, ... ..., , c 2n
2n 位的密钥序列位的密钥序列，，
..., , k 2n ，K =k 1, k 2, ...
k i =m i ⊕c i =m i ⊕(m i ⊕k i ) 。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码由此可以推出线性移位寄存器连续n+n+11个状态：
..., , k n ）T S 1=（k 1, k 2, ...
T S 2=（k 2, k 3, ... ..., , k n+）n+11
…
T S n+=（k , k , ..., ... , k ）n+11n+1n+1n+2n+22n
X =（S 1, S 2, ... ..., , S n ）T
T Y =（S 2, S 3, ..., ... , S n+）n+11
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码S ’=HS mod 2，有
S 2=HS 1
S 3=HS 2
...
S n+n+11=HS n
，
Y =HX mod 2
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
因为，因此X 矩阵为满秩矩阵矩阵为满秩矩阵，，故存在逆矩阵X -1，于是
H =YX -1mod 2
求出H 矩阵矩阵，，便确定出连接多项式g (x)，从而完全确定线性移位寄存器的结构。完全确定线性移位寄存器的结构。例：m 序列[**************]连续4个状态1001，0011，0110，1101线性无关
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
求逆矩阵X -1的计算复杂度为O （n 3）。一般一般，，n=10001000的线性移位寄存器序列密码的线性移位寄存器序列密码，，用每对于n=
万次的计算机，，一天之内便可破译一天之内便可破译。。秒100万次的计算机
三、非线性序列密码三、非线性序列密码•线性移位寄存器序列密码在已知明文攻击下是可破译的，下是可破译的，可破译的根本原因在于线性移位寄存器序列是线性的，这一事实促使人们向非线性领域探索领域探索。。•目前研究得比较充分的方法：①非线性移位寄存器序列
②对线性移位寄存器序列进行非线性组合③利用非线性分组码产生非线性序列
三、非线性序列密码三、非线性序列密码非线性移位寄存器序列
令反馈函数f (s 0, s 1, ... ..., , s n -1) 为非线性函数便构成非线性移位寄存器，性函数便构成非线性移位寄存器，其输出序列为非线性序列。序列为非线性序列。
n •称输出序列的周期达到最大值2的非线性
移位寄存器序列为M 序列。•M 序列的0，1分布和游分布是均匀的分布和游分布是均匀的，，而且周期最大。且周期最大。
三、非线性序列密码三、非线性序列密码非线性移位寄存器序列
•非线性移位寄存器反馈函数的数量极大
n GF （2）上的n 级移位寄存器共有2个状
态，因此共有2n 种不同的反馈函数，种不同的反馈函数，其中2
线性反馈函数只有
性。
显然，显然，非线性移位寄存器的空间极大非线性移位寄存器的空间极大！！n -12种，其余均为非线
三、非线性序列密码三、非线性序列密码非线性移位寄存器序列
例：令n =3，f (s 0, s 1, s 2)=s 0⊕s 2⊕1⊕s 1•s 2，由于与运算为非线性运算，故反馈函数为非线性反馈与运算为非线性运算，
序列。。函数，函数，其输出序列为10110100... ...，，为M 序列
输出
s 0s 1s 2
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合
非线性移位寄存器序列的研究比较困难，但人们对线性移位寄存器序列的研究却比较充分和深入。于是人们想到，利用线性移位寄存器序列设计容易、随机性好等优点，对一个或多个线性移位寄存器序列进行非线性组合可以获得良好的非线性序列。
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合•对一个LSR 进行非线性组合•在这里用线性移位寄存器作为驱动源来驱动非线性电路产生非线性序列。其中前馈电路，称这种输出序列为前馈序列。•对多个LSR 进行非线性组合
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合•对一个LSR 进行非线性组合
线性移位寄存器
非线性组合
输出
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合•对多个LSR 进行非线性组合
线性移位寄存器1线性移位寄存器2非线
性
组
合输出线性移位寄存器n
四、RC4序列密码
RC4序列密码是美国RSARC4序列密码是美国RSA数据安全公司设数据安全公司设计的一种序列密码。RSA计的一种序列密码。RSA数据安全公司将数据安全公司将其收集在加密工具软件BSAFE 中。最初并没有公布RC4没有公布RC4的算法。人们通过对软件进的算法。人们通过对软件进行逆向分析得到了算法。
在这种情况下RSA在这种情况下RSA数据安全公司于数据安全公司于19971997年公布了RC4年公布了RC4密码算法。密码算法。
密钥40密钥40位的位的RC4RC4，，通过通过Internet 32Internet 32小时小时攻破。
四、RC4序列密码
•RC4RC4密码与基于移位寄存器的序列密码不密码与基于移位寄存器的序列密码不同。
•它是一种基于非线性数据表变换的序列密码。
•它以一个足够大的数据表为基础，对表进行非线性变换，产生非线性的密钥序列。
四、RC4序列密码
•RC4RC4使用使用256256个字节的个字节的S 表和两个指针（I 和J ）。•S 表的值S 0, S 1, …，S 255是0,1, …，255255的一个排的一个排列。
•I 和J 的初值为的初值为00。
•我们把我们把RC4RC4算法看成一个有限状态自动机。把算法看成一个有限状态自动机。把S 表
指针的具体取值称为RC4RC4的一个状态：的一个状态：和I 、J 指针的具体取值称为
T =
•对状态T 进行非线性变换进行非线性变换，，产生出新的状态，并输出密钥序列中一个字节k 。
四、RC4序列密码
•RC RC44的下一状态函数定义如下：⑴I ＝0，J ＝0;
⑵I=I+I+11mod 256256; ;
⑶J=J+S[I]mod 256256; ;
⑷交换交换S[I]S[I]和和S[J]。
•RC RC44的输出函数定义如下：
⑴h=S[I]+S[J]mod 256; 256; ⑵k =S[h]。
四、RC4序列密码
•在用在用RCRC44加解密之前加解密之前，，应当首先对应当首先对SS 表初始化表初始化。。初始化的过程如下：
对S 表进行线性填充，即令
S[0S[0]＝0，S[S[11]＝1，S[S[22]＝2，…，S[S[255255]]＝255；255；
用密钥填充另一个用密钥填充另一个256256字节的字节的R 表R[R[00],R[],R[11],…R[255R[255]]，如果密钥的长度小于R 表的长度表的长度，，则依次重复填充，次重复填充，直至将直至将RR 表填满表填满。。
四、RC4序列密码
J ＝0;
对于I=对于I=00到255255重复以下操作重复以下操作，，①J ＝（J+S [I]+R [I][I]））mod 256256; ; ②交换S [I][I]和和S [J]。
•注意，注意，对S 表初始化的过程实质上是对S 表进行随机化处理的过程，理的过程，只有当这一过程完成后只有当这一过程完成后，，才能计算产生密钥字符，字符，才能进行加解密才能进行加解密，，否则将是不安全的否则将是不安全的。。•RC RC44算法的优点是算法简单算法的优点是算法简单，，高效高效，，特别适合软件实现特别适合软件实现。。•RC RC44是目前应用最广的商密级序列密码是目前应用最广的商密级序列密码。。
复习题
①设g (x )=x 4+x 3+1+1，，g (x ) 为本原多项式，以其为连接多项式组成线性移位寄存器。画出逻辑图，写出输出序列及状态变迁。
②令n =3=3，，f (s 0, s 1, s 2)= s 0⊕s 2⊕1⊕s 1 s 2，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出辑图，求出非线性移位寄存器的非线性移位寄存器的状态变迁及输状态变迁及输出。
复习题
③令n =3=3，，f (s 0, s 1, s 2)=1⊕s 0⊕s 1⊕s 2⊕s 0s 1⊕s 1 s 2⊕s 2 s 3 ，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出寄存器。画出逻辑图，求出非线性移位寄存器非线性移位寄存器的状态变迁及输出。
④证明：GF （2）上的n 级移位寄存器共有2 n 个
n 2状态，因此共有2种不同的反馈函数，其中线
性反馈函数只有2n -1种，其余均为非线性。
谢谢！
密码学
（第七讲）
序列密码
张焕国
武汉大学计算机学院
目录
1、密码学密码学的基本概念的基本概念
2、古典、古典密码密码
3、数据加密标准（、数据加密标准（DESDES））
4、高级高级数据加密标准（数据加密标准（AESAES））
5、中国商用密码（、中国商用密码（SMS4SMS4））
6、分组密码的应用技术
7、序列密码
8、习题课：复习对称密码
9、公开密钥密码（、公开密钥密码（11）
目录
10、公开密钥密码（10、公开密钥密码（22）
11、数字签名（1）
12、数字签名（2）
13、13、HASH 函数
14、14、认证
15、15、密钥管理
16、16、PKI PKI技术技术
17、习题课：复习公钥密码17、习题课：复习公钥密码
18、总复习18、总复习//检查：综合实验
一、序列密码的基本概念①明文、密文、密钥以位（字符）为单位加解密；
种子密钥②模型
密钥序列
产生器
明文: m 1, m 2,…密钥序列：k 1, k 2,…密文: c 1, c 2,…
C i = m i ⊕k i
一、序列密码的基本概念③人们用序列密码模仿“一次一密”密码；④加密运算最简单，而且是对合运算；⑤安全取决于密钥序列产生算法；⑥理论和技术都十分成熟；
⑦核心密码的主流密码。
一、序列密码的基本概念
1、序列密码的分类
①同步序列密码（Synchronous Stream Cipher）•密钥序列产生算法与明文无关，所产生的密钥序列也与明文无关。
•在通信过程中，通信的双方必须保持精确的同步，收方才能正确解密，如果失步收方将不能正确解密。例如，如果通信中丢失或增加了一个密文字符，则收方的解密将一直错误。
一、序列密码的基本概念①同步序列密码
种子密钥k
密钥序列
产生算法
1, m 2,
k 1, k 2,… c 1, c 2,…种子密钥k 密钥序列产生算法C i = m i ⊕k i k 1, k 2,… m 1, m 2,…
设密文失步c =c 1, c 3, c 4, … c n -1, c n （c 2丢失）
⊕k =k 1, k 2, k 3, … k n -1, k n （密钥正确）
m =m 1, ×, ×, … ×, ×（m 1后的明文全错）
一、序列密码的基本概念①同步序列密码
•对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。
•另一个优点是没有错误传播，当通信中某些密文字符产生了错误（不是插入和删除），只影响相应字符的解密，不影响其它字符。•注意：错误与失步是不同的概念！
设密文错误c =c 1, c 2, c 3, … c n -1, c n （c 2错）
⊕k =k 1, k 2, k 3, … k n -1, k n （密钥正确）
m =m 1, ×, m3, … mn -1, mn （仅m 2错）
一、序列密码的基本概念②自同步序列密码（Self Self--Synchronous Stream Cipher ）•密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明文（密文）相关。•设密钥序列产生器具有n 位存储，则加密时一位密文错误将影响后面连续n 个密文错误。在此之后恢复正确。
•解密时一位密文错误也将影响后面连续n 个明文错。在此之后恢复正确。
•加解密会造成错误传播。在错误过去之后恢复正确。
一、序列密码的基本概念②自同步序列密码
种子密钥k
密钥序列
产生算法
n 位存储
k 1, k 2,…
m 1212种子密钥k 密钥序列产生算法n 位存储k 1, k 2,…
m 1, m 2,…
C i 的错误将影响n 位
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•例1
输出S 0S 1S n-2S n －1输入
移位
脉冲
•例2 增加反馈
输出S 0S 1S n-2S n －1输入
移位
脉冲
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•例3 增加运算
输出S 0S 1S n-2S n －1输入
移位
脉冲
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•一般模型
F (s 0, s 1,…,s n －1)
S 0S 1S n-2S n －1输出
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器（Linear Sift Registor）•图中图中ss 0，s 1，... ...，，s n -1 组成左移移位寄存器，并称每一时刻移位寄存器的取值为一个状态。•移位寄存器的输出同时要送入移位寄存器的输出同时要送入ss n -1，其值要通过函数F(s0 ,s 1,...,s n -1) 计算产生。•称函数F(s0 ,s 1,...,s n -1) 为反馈函数。•如果反馈函数F(s0 ,s 1,...,s n -1) 是s 0 ,s 1,...,s n -1的线性函数，则称为线性移位寄存器，否则称为非线性移位寄存器。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•设F (s 0, s 1, ... ..., , s n -1) 为线性函数为线性函数，，则可写成F (s 0, s 1, ... ..., , s n -1) =g 0s 0+g 1s 1+,+,......,+,+g n -1s n -1其中，其中，g 0, g 1, ... ..., , g n -1为反馈系数反馈系数。。•在二进制的情况下，在二进制的情况下，式中的+即为即为⊕⊕，反馈系数g i ∈GF (2) ，如果g i =0，则表示式中的g i s i 项不存在，存在，因此表示s i 不连接。同理同理，，g i =1表示s i 连接。故g i 的作用相当于一个开关。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
i •形式地形式地，，用x 与s i 相对应相对应，，则根据反馈函数可导出一个文字x 的多项式：
n n -1g(x)=g n x +gn -1x +,...+,...,+g,+g1x +g0•称g(x)为线性移位寄存器的连接多项式线性移位寄存器的连接多项式。。
•与图对照可知，与图对照可知，g n =g0=1。否则否则，，若g n =0则输出不反馈到输出不反馈到ss n -1，若g 1=0则s 0不起作用不起作用，，应将其去掉。应将其去掉。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
g 0=1
S 0g 1S 1g 2S n －2g n -1S n －1g n =1
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•n 级线性移位寄存器最多有2n 个不同的状态个不同的状态。。若其初始状态为零，则其后续状态恒为零初始状态为零，则其后续状态恒为零。。若其初始状态不为零，状态不为零，则其后续状态也不为零则其后续状态也不为零。。因此因此，，n 级线性移位寄存器的状态周期≤线性移位寄存器的状态周期≤2n –1，其输出序列的周期≤的周期≤2n –1。
•只要选择合适的连接多项式便可使线性移位寄存器的输出序列周期达到最大值2n –1，并称此时的输出序列为最大长度线性移位寄存器输出序列，输出序列为最大长度线性移位寄存器输出序列，简称为m 序列。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器•仅当连接多项式g (x ) 为本原多项式时，其线性移位寄存器的输出序列为m 序列。•设f (x ) 为GF （2）上的多项式上的多项式，，使f (x ) |x p －1的最小正整数p 称为f (x ) 的周期。如果f (x ) 的次数为n ，且其周期为且其周期为22n －1，则称f (x ) 为本原多项式为本原多项式。。•已经证明已经证明，，对于任意的正整数n ，至少存在一个n 次本原多项式本原多项式。。而且有有效的产生算法而且有有效的产生算法。。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•举例：设g (x)=x 4+x +1+1，，g (x ) 为本原多项式，以其为连接多项式的线性移位寄存器的输出序列为[***********][1**********]0······，它是周期为，它是周期为224-1=15的m 00010101序列。
g 0=1
S 0g 1=1S 1g 2=0S 2g 3=0S 3g 4=[***********]110
1101
[***********]1011001000
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
•m 序列具有良好的随机性：
游程：称序列中连续的i 个1为长度等于为长度等于ii 的1游程，同样，称序列中连续的i 个0为长度等于i长度等于i 的0游程。
①在一个周期内，0和1出现的次数接近
n -n -1-1，1出现相等，即0出现的次数为2
n -1的次数为2 ；
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
②将序列的一个周期首尾相接，其游程总
n -1 。数N=2
③其中其中11游程和游程和00游程的数目各占一半。当n>2时，游程分布如下（n>2时，游程分布如下（1≤i≤n1≤i≤n--2）：•长为长为ii 的1游程有游程有N/N/2 i+1个；
•长为长为ii 的0游程有游程有N/N/2 i+1个；
•长为长为nn -1的0游程有游程有11个；
•长为长为nn 的1游程有游程有11个.
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
④自相关函数④自相关函数
定义：设{k i }是周期为p 的序列，k 0, k 1,…, k p -1是其中一个周期子段，则k 0+τ, k 1+τ,…, k p -1+τ也是一个周期子段。记这两个子段中相同的位数为A ，不相同的位数为D ，则自相关函数定义为：
A -D R(j)=P
自相关函数反映一个周期内平均每位的相同程度。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器
④自相关函数④自相关函数
1, τ=0R(τ)=-1/P，0
m 序列的自相关函数达到最佳值。
[1**********]000
[**************]A ＝7 D＝8R(τ ) = - ) = -1/15
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
•m 序列具有良好的随机性；
•50年代开始用作密钥序列，并用于军用。•60年代发现其是不安全的。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
设m 序列线性移位寄存器的状态为
S =（s 0, s 1, ... ..., , s n -1）T ，
S ’=（s ’0, s ’1, ... ..., , s ’n -1）T ，其中
s ’0=s 1
s ’1=s 2
...
s ’n -2=s n -1
s ’n -1=g 0s 0+g 1s 1+,+,......,+,+g n -1s n -1
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
S ’=HS mod 2
s ’0s 0010... 0
001... 0s ’1s 1000... 0
S ’=S =H=...
000... 1
0g 1... g n -’n -1n -1H 称为连接多项式的伴侣矩阵称为连接多项式的伴侣矩阵。。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
2n 位的明密文对即已知：
..., , m 2n M =m 1, m 2, ...
C =c 1, c 2, ... ..., , c 2n
2n 位的密钥序列位的密钥序列，，
..., , k 2n ，K =k 1, k 2, ...
k i =m i ⊕c i =m i ⊕(m i ⊕k i ) 。
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码由此可以推出线性移位寄存器连续n+n+11个状态：
..., , k n ）T S 1=（k 1, k 2, ...
T S 2=（k 2, k 3, ... ..., , k n+）n+11
…
T S n+=（k , k , ..., ... , k ）n+11n+1n+1n+2n+22n
X =（S 1, S 2, ... ..., , S n ）T
T Y =（S 2, S 3, ..., ... , S n+）n+11
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码S ’=HS mod 2，有
S 2=HS 1
S 3=HS 2
...
S n+n+11=HS n
，
Y =HX mod 2
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
因为，因此X 矩阵为满秩矩阵矩阵为满秩矩阵，，故存在逆矩阵X -1，于是
H =YX -1mod 2
求出H 矩阵矩阵，，便确定出连接多项式g (x)，从而完全确定线性移位寄存器的结构。完全确定线性移位寄存器的结构。例：m 序列[**************]连续4个状态1001，0011，0110，1101线性无关
二、线性移位寄存器序列密码二、线性移位寄存器序列密码
、线性移位寄存器序列密码
求逆矩阵X -1的计算复杂度为O （n 3）。一般一般，，n=10001000的线性移位寄存器序列密码的线性移位寄存器序列密码，，用每对于n=
万次的计算机，，一天之内便可破译一天之内便可破译。。秒100万次的计算机
三、非线性序列密码三、非线性序列密码•线性移位寄存器序列密码在已知明文攻击下是可破译的，下是可破译的，可破译的根本原因在于线性移位寄存器序列是线性的，这一事实促使人们向非线性领域探索领域探索。。•目前研究得比较充分的方法：①非线性移位寄存器序列
②对线性移位寄存器序列进行非线性组合③利用非线性分组码产生非线性序列
三、非线性序列密码三、非线性序列密码非线性移位寄存器序列
令反馈函数f (s 0, s 1, ... ..., , s n -1) 为非线性函数便构成非线性移位寄存器，性函数便构成非线性移位寄存器，其输出序列为非线性序列。序列为非线性序列。
n •称输出序列的周期达到最大值2的非线性
移位寄存器序列为M 序列。•M 序列的0，1分布和游分布是均匀的分布和游分布是均匀的，，而且周期最大。且周期最大。
三、非线性序列密码三、非线性序列密码非线性移位寄存器序列
•非线性移位寄存器反馈函数的数量极大
n GF （2）上的n 级移位寄存器共有2个状
态，因此共有2n 种不同的反馈函数，种不同的反馈函数，其中2
线性反馈函数只有
性。
显然，显然，非线性移位寄存器的空间极大非线性移位寄存器的空间极大！！n -12种，其余均为非线
三、非线性序列密码三、非线性序列密码非线性移位寄存器序列
例：令n =3，f (s 0, s 1, s 2)=s 0⊕s 2⊕1⊕s 1•s 2，由于与运算为非线性运算，故反馈函数为非线性反馈与运算为非线性运算，
序列。。函数，函数，其输出序列为10110100... ...，，为M 序列
输出
s 0s 1s 2
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合
非线性移位寄存器序列的研究比较困难，但人们对线性移位寄存器序列的研究却比较充分和深入。于是人们想到，利用线性移位寄存器序列设计容易、随机性好等优点，对一个或多个线性移位寄存器序列进行非线性组合可以获得良好的非线性序列。
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合•对一个LSR 进行非线性组合•在这里用线性移位寄存器作为驱动源来驱动非线性电路产生非线性序列。其中前馈电路，称这种输出序列为前馈序列。•对多个LSR 进行非线性组合
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合•对一个LSR 进行非线性组合
线性移位寄存器
非线性组合
输出
三、非线性序列密码三、非线性序列密码对线性移位寄存器序列进行非线性组合•对多个LSR 进行非线性组合
线性移位寄存器1线性移位寄存器2非线
性
组
合输出线性移位寄存器n
四、RC4序列密码
RC4序列密码是美国RSARC4序列密码是美国RSA数据安全公司设数据安全公司设计的一种序列密码。RSA计的一种序列密码。RSA数据安全公司将数据安全公司将其收集在加密工具软件BSAFE 中。最初并没有公布RC4没有公布RC4的算法。人们通过对软件进的算法。人们通过对软件进行逆向分析得到了算法。
在这种情况下RSA在这种情况下RSA数据安全公司于数据安全公司于19971997年公布了RC4年公布了RC4密码算法。密码算法。
密钥40密钥40位的位的RC4RC4，，通过通过Internet 32Internet 32小时小时攻破。
四、RC4序列密码
•RC4RC4密码与基于移位寄存器的序列密码不密码与基于移位寄存器的序列密码不同。
•它是一种基于非线性数据表变换的序列密码。
•它以一个足够大的数据表为基础，对表进行非线性变换，产生非线性的密钥序列。
四、RC4序列密码
•RC4RC4使用使用256256个字节的个字节的S 表和两个指针（I 和J ）。•S 表的值S 0, S 1, …，S 255是0,1, …，255255的一个排的一个排列。
•I 和J 的初值为的初值为00。
•我们把我们把RC4RC4算法看成一个有限状态自动机。把算法看成一个有限状态自动机。把S 表
指针的具体取值称为RC4RC4的一个状态：的一个状态：和I 、J 指针的具体取值称为
T =
•对状态T 进行非线性变换进行非线性变换，，产生出新的状态，并输出密钥序列中一个字节k 。
四、RC4序列密码
•RC RC44的下一状态函数定义如下：⑴I ＝0，J ＝0;
⑵I=I+I+11mod 256256; ;
⑶J=J+S[I]mod 256256; ;
⑷交换交换S[I]S[I]和和S[J]。
•RC RC44的输出函数定义如下：
⑴h=S[I]+S[J]mod 256; 256; ⑵k =S[h]。
四、RC4序列密码
•在用在用RCRC44加解密之前加解密之前，，应当首先对应当首先对SS 表初始化表初始化。。初始化的过程如下：
对S 表进行线性填充，即令
S[0S[0]＝0，S[S[11]＝1，S[S[22]＝2，…，S[S[255255]]＝255；255；
用密钥填充另一个用密钥填充另一个256256字节的字节的R 表R[R[00],R[],R[11],…R[255R[255]]，如果密钥的长度小于R 表的长度表的长度，，则依次重复填充，次重复填充，直至将直至将RR 表填满表填满。。
四、RC4序列密码
J ＝0;
对于I=对于I=00到255255重复以下操作重复以下操作，，①J ＝（J+S [I]+R [I][I]））mod 256256; ; ②交换S [I][I]和和S [J]。
•注意，注意，对S 表初始化的过程实质上是对S 表进行随机化处理的过程，理的过程，只有当这一过程完成后只有当这一过程完成后，，才能计算产生密钥字符，字符，才能进行加解密才能进行加解密，，否则将是不安全的否则将是不安全的。。•RC RC44算法的优点是算法简单算法的优点是算法简单，，高效高效，，特别适合软件实现特别适合软件实现。。•RC RC44是目前应用最广的商密级序列密码是目前应用最广的商密级序列密码。。
复习题
①设g (x )=x 4+x 3+1+1，，g (x ) 为本原多项式，以其为连接多项式组成线性移位寄存器。画出逻辑图，写出输出序列及状态变迁。
②令n =3=3，，f (s 0, s 1, s 2)= s 0⊕s 2⊕1⊕s 1 s 2，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出辑图，求出非线性移位寄存器的非线性移位寄存器的状态变迁及输状态变迁及输出。
复习题
③令n =3=3，，f (s 0, s 1, s 2)=1⊕s 0⊕s 1⊕s 2⊕s 0s 1⊕s 1 s 2⊕s 2 s 3 ，以其为连接多项式组成非线性移位寄存器。画出逻辑图，求出寄存器。画出逻辑图，求出非线性移位寄存器非线性移位寄存器的状态变迁及输出。
④证明：GF （2）上的n 级移位寄存器共有2 n 个
n 2状态，因此共有2种不同的反馈函数，其中线
性反馈函数只有2n -1种，其余均为非线性。
谢谢！