密 码 学序列密码xxx鲁东大学计算机学院一、序列密码的基本概念①明文、密文、密钥以位（字符）为单位加 解密； ②模型密钥序列 产生器种子密钥种子密钥密钥序列：密钥序列：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、序列密码的分类 ①同步序列密码（Synchronous Stream Cipher） ·军方称为密钥自动密钥 ·密钥序列产生算法与明文无关，所产生的密钥序列也 与明文无关 ·一位一位“吐出”密钥 ·在通信过程中，通信的双方必须保持精确的同步，收 方才能正确解密，如果失步收方将不能正确解密 ·例如，如果通信中丢失或增加了一个密文字符，则收 方的解密将一直错误一、序列密码的基本概念①同步序列密码设密文失步 c = c1, c3, c4, … cn-1, cn （ c2 丢失）⊕ k= k1, k2, k3, … kn-1, kn （密钥正确）m=m1,×, ×, … ×, × （ m1 后的明文全错）密钥序列 产生算法密钥序列 产生算法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 = 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个密文错误在此之后恢复正 确 ·解密时一位密文错误也将影响后面连续 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-2Sn－1输入输入输出输出移位移位 脉冲脉冲S0S1Sn-2Sn－1输入输入 输出输出移位移位 脉冲脉冲二、线性移位寄存器序列密码1、线性移位寄存器（Linear Sift Registor） ·例3 增加运算S0S1Sn-2Sn－1输入输入 输出输出移位移位 脉冲脉冲⊕二、线性移位寄存器序列密码1、线性移位寄存器（Linear Sift Registor） ·一般模型F(s0,s1,…,sn－1)S0S1Sn-2Sn－1输出输出二、线性移位寄存器序列密码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 )是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 项不 存在，因此表示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、线性移位寄存器S0S1Sn－1Sn－2g gn n=1=1g gn-1n-1g g2 2g g1 1g g0 0=1=1二、线性移位寄存器序列密码1、线性移位寄存器 ·n级线性移位寄存器最多有2n个不同的状态若其 初始状态为零，则其后续状态恒为零若其初始 状态不为零，则其后续状态也不为零因此，n级 线性移位寄存器的状态周期≤2n –1，其输出序列 的周期≤2n –1 只要选择合适的连接多项式便可使线性移位寄存 器的输出序列周期达到最大值2n –1，并称此时的 输出序列为最大长度线性移位寄存器输出序列， 简称为m序列二、线性移位寄存器序列密码1、线性移位寄存器 •仅当连接多项式g(x)为本原多项式时，其线性移 位寄存器的输出序列为m序列设f(x)为GF（2）上的多项式，使f(x)| x p－1的 最小正整数p称为f(x)的周期如果f(x)的次数为 n，且其周期为2 n－1，则称f(x)为本原多项式已经证明，对于任意的正整数n，至少存在一个n 次本原多项式而且有有效的产生算法。
二、线性移位寄存器序列密码1、线性移位寄存器 举例：设g(x)=x4 +x +1， g(x)为本原多项式， 以其为连接多项式的线性移位寄存器的输出序列 为100110101111000··· ，它是周期为2 4- 1=15的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 1 0010010 0 101 1011 1 0100100 0 011 0111 1 1001001 1 111 1111 1 0010011 1 111 1110 0 0110110 0 110 1100 0 1101101 1 100 1000 0 1011010 0二、线性移位寄存器序列密码1、线性移位寄存器 ·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游程的数目各占一半当 n>2时，游程分布如下（1≤i≤n-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-DP自相关函数反映一个周期内平均每位的相同程度 R(j)=R(j)=二、线性移位寄存器序列密码1、线性移位寄存器④自相关函数1 ,τ=0 -1/P ，0 对状态T进行非线性变换，产生出新的状态 ，并 输出密钥序列中一个字节k 四、RC4序列密码RC4的下一状态函数定义如下：⑴ I＝0，J＝0;⑵ I= I+1 mod 256; ⑶ J=J+S[I] mod 256; ⑷ 交换S[I]和S[J] RC4的输出函数定义如下：⑴ h= S[I] + S[J] mod 256;⑵ k = S[h] 。
四、RC4序列密码在用RC4加解密之前，应当首先对S表初始化初 始化的过程如下： ⑴ 对S表进行线性填充，即令S[0]＝0，S[1]＝1，S[2]＝2，…，S[255] ＝ 255； ⑵ 用密钥填充另一个256字节的R表R[0],R[1],… ，R[255]，如果密钥的长度小于R表的长度，则 依次重复填充，直至将R表填满四、RC4序列密码⑶ J＝0; ⑷ 对于I=0 到255重复以下操作，① J＝（J+S[I]+R[I]） mod 256; ② 交换S[I]和S[J] ·注意，对S表初始化的过程实质上是对S表进行随机化处 理的过程，只有当这一过程完成后，才能计算产生密钥 字符，才能进行加解密，否则将是不安全的 ·RC4算法的优点是算法简单，高效，特别适合软件实现 ·RC4是目前应用最广的商密级序列密码复习题①设g(x)=x4 +x3 +1， g(x)为本原多项式，以其为 连接多项式组成线性移位寄存器画出逻辑图 ，写出输出序列及状态变迁②令n=3，f(s0,s1,s2)= s0⊕s2⊕1⊕s1 s2，以其 为连接多项式组成非线性移位寄存器画出逻 辑图，求出非线性移位寄存器的状态变迁及输 出。
复习题③令n=3，f(s0,s1,s2)=1⊕s0⊕s1⊕s2⊕s0s1⊕s1 s2⊕s2 s3 ，以其为连接多项式组成非线性移位 寄存器画出逻辑图，求出非线性移位寄存器 的状态变迁及输出④证明：GF（2）上的 n级移位寄存器共有 2 n个状态，因此共有 种不同的反馈函数，其中 线性反馈函数只有 2n-1种，其余均为非线性2 2n n2 2谢 谢！。