第讲--序列密码的编码层次

其中，系数c 等于0或1，加法是模2加 对应的n级线性反馈移位 其中，系数ci等于0或1，加法是模2加。对应的n级线性反馈移位 结构图为： 寄存器 结构图为：
8/15
第9章 序列密码
基于LFSR LFSR的序列密码 9.3 基于LFSR的序列密码 对一个LFSR LFSR进行非线性组合 对一个LFSR进行非线性组合
ci = Ek (mi )(i = 1, 2,L , n)
i
序列密码的加解密规则一般都非常简单，其关 键在于密钥流的产生。
3/15
第9章 序列密码
概述（ 9.1 概述（续） 序列密码的主要特点如下： 序列密码的主要特点如下： 序列密码以一个符号（如一个字符或一个比特） 序列密码以一个符号（如一个字符或一个比特） 作为基本的处理单元， 作为基本的处理单元，而分组密码以一定大小的分组 作为基本的处理单元； 作为基本的处理单元； 序列密码使用一个随时间变化的简单的加密变换 即不同时刻所用的密钥不同， ，即不同时刻所用的密钥不同，而分组密码在不同时 刻所用的密钥是相同的。 刻所用的密钥是相同的。 序列密码可以进一步划分成同步序列密码和自同 步序列密码两种。 步序列密码两种。
13/15
第9章 序列密码
序列密码RC4 9.4 序列密码RC4 RC4是 Rivest在1987年为RSA公司设计的一种 年为RSA RC4是Ron Rivest在1987年为RSA公司设计的一种 序列密码，它是一个可变密钥长度、 序列密码，它是一个可变密钥长度、面向字节操作的 序列密码。 序列密码。 RC4密码与基于移位寄存器的序列密码不同 密码与基于移位寄存器的序列密码不同， RC4密码与基于移位寄存器的序列密码不同，它是 一种基于非线性数据表变换的序列密码。 一种基于非线性数据表变换的序列密码。它以一个足 够大的数据表为基础，对表进行非线性变换， 够大的数据表为基础，对表进行非线性变换，产生非 线性的密钥流。RC4密码的密钥长度可变 密码的密钥长度可变， 线性的密钥流。RC4密码的密钥长度可变，其长度取 值在8位到2048位之间。 2048位之间 值在8位到2048位之间。 一旦密钥流产生好，RC4的加解密就非常简单 的加解密就非常简单， 一旦密钥流产生好，RC4的加解密就非常简单，即 明文（密文） ，明文（密文）字节与相应的密钥流字节进行异或操 作。 RC4算法的优点是算法简单、高效，特别适合软件 RC4算法的优点是算法简单、高效， 算法的优点是算法简单 实现，但它的安全性存在争议。 实现，但它的安全性存在争议。

，其中 ci G F(q),1in，则称其为线性反馈寄存 器；否则称其为非线性反馈移为寄存器。
其中 cn 0 ，若 cn 0 我们说该寄存器是退化 的，否则是非退化的。
4
移位寄存器序列空间
符号说明：G(f)表示以f(x)为联结多项式的n级线 性移位寄存器序列构成的空间
定理1：G(f)是GF(q)上的一个n维线性空间。 证明：只需证明G(f)中的任意两个序列的任意线
状态转移矩阵： 满足：st+1=stTf 称st=(at,at+1,at+2,…,at+n-1)为n维状态
2
实例（画出移存器的逻辑框图，写出相应的线性
递推式）
多项式
f(x)x4 x3 x2 1
答案： 线性递推式： at=at-4+at-3+at-2
x1
x2
x3
x4
3
非退化的移位寄存器
若反馈函数形如：f( x 1 ,x 2 ,,x n ) c n x 1 c n 1 x 2 c 1 x n
称f(x)是可约多项式；否则，称其为不可约多 项式。
6
定理2：若f(x)|h(x)，则G(f) G(h).
例1：联结多项式为
f(x)=x4+x3+x+1=(x+1)2(x2+x+1)
线性递推式：at=at-4+at-3+at-1 输出序列：000111//000111//…… 周期为6
011//011//……
12
m序列的游程分布规律
性质2：将r级m序列的一个周期段首尾相接，其游程 总数为N=2r-1；其中没有长度大于r的游程；有1个长 度为r的1游程，没有长度为r的0游程；没有长度为

反馈移存器是序列密码设计中常用的一种初始乱源， 其目的是：
（1）以种子密钥为移存器的初态，按照确定的递推关 系，产生周期长、统计特性好的初始乱源序列。
（2）继而利用非线性函数、有记忆变换、采样变换等 手段，产生抗破译能力强的乱数序列。
在序列密码设计中，大多使用周期达到最大的那些 序列，包括：
（1）二元域GF(2)上的线性递归序列 （2）2n元域GF(2n)上的线性递归序列 （3）剩余类环Z/(2n)上的线性递归序列 （4）非线性递归序列
3.2.2 线性反馈移存器（LFSR）简介
c0=1
c1
c2 …
…
x1
x2
am-1
am-2
cn-2 xn-1
cn-1
cn
xn am-n
一、当ci=1时，开关闭合，否则断开；c0=1表示总有 反馈；一般cn=1，否则退化。
二、反馈逻辑函数
f(x1, x2, …, xn)=c1x1+c2x2+…+cnxn 三、线性递推式
= c0am+c1Dam+c2D2am+…+cnDnam) = (c0+c1D+c2D2+…+cnDn)am 因此反馈多项式（也称特征多项式）为：
g(x)= c0+c1x+c2x2+…+cnxn
五、状态转移矩阵
给定两个相邻状态：
则有
Sm=(am+n-1,…,am+1,am) Sm+1=(am+n,…,am+2,am+1)
管理问题！
因而人们设想使用少量的真随机数（种子密钥） 按一定的固定规则生成的“伪随机”的密钥序 列代替真正的随机序列ki，这就产生了序列密 码。

4.4 线性移位寄存器的一元多项式表示
设 n 级线性移位寄存器的输出序列满足递推 关系 an+k=c1an+k-1 c2an+k-2 … cnak (*) 对任何 k 1 成立。这种递推关系可用一个一 元高次多项式 P(x)=1+c1x+…＋cn-1xn-1＋cnxn 表示，称这个多项式为LFSR的联系多项式或 特征多项式。
初始状态由用户确定，当第i个移位时钟脉冲 到来时，每一级存储器ai都将其内容向下一级 ai-1传递，并根据寄存器此时的状态a1,a2,…,an 计算f(a1,a2,…,an)，作为下一时刻的an。反馈函 数f(a1,a2,…,an)是n元布尔函数，即n个变元 a1,a2,…,an可以独立地取0和1这两个可能的值， 函数中的运算有逻辑与、逻辑或、逻辑补等运 算，最后的函数值也为0或1。
图4-4 GF(2)上的n级线性反馈移位寄存器
输出序列{at}满足 an+t=cnat cn-1at+1 … c1an+t-1 其中t为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、 有较为成熟的理论等优点而成为构造密钥流生 成器的最重要的部件之一。
例4.2 图4-5是一个5级线性反馈移位寄存器， 其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可 求出输出序列为 1001101001000010101110110001111100110 … 周期为31。
即输出序列为101110111011…，周期为4。 如果移位寄存器的反馈函数f(a1,a2,…,an)是a1 ，a2，…，an的线性函数，则称之为线性反馈 移位寄存器LFSR（linear feedback shift register ）。此时f可写为 f(a1,a2,…,an)=cna1 cn-1a2 … c1an 其中常数ci=0或1 2加法。ci=0或1可 用开关的断开和闭合来实现，如图4-4所示。

yi=zi xi。
K
K
安全信道
……
滚动密钥生成器
zi
xi
yi……滚动密钥生器ziyixi
同步序列密码
一次一密密码是加法序列密码的原型。事实上，如 果密钥使用滚动密钥流，则加法序列密码就退化成 一次一密密码。
实际使用中，密码设计者的最大愿望是设计出的滚 动密钥生成器，使得密钥经其扩展成的密钥流序列 具有如下性质：极大的周期、良好的统计特性、抗 线性分析、抗统计分析
基本概念
分组密码与序列密码的区别在于有无记忆性 序列密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指
定的初态σ0完全确定。此后，由于输入加密器的明文 可能影响加密器中内部记忆元件的存储状态，因而 σi(i>0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。
同步序列密码
根据加密器中记忆元件的存储状态σi是否依赖 于输入的明（或密）文字符，序列密码可进一 步分成同步和自同步两种。
和σi产生的函数。
9
基本概念
序列密码将明文消息 M连续地分成字符
bit，并用密钥流来 加密每个字符bit
基本上，序列密码体
制只使用混乱技术，
而不使用散布技术。 这使得这种体制没有
错误扩散
基本情况
序列密码有广泛的理论基础，对于其各种设计原则已经 进行了详尽的分析。然而在公开的文献中详尽的序列密 码系统却相对较少 造成这种状况的部分原因是，在实际中使用的大部分序 列密码归私人所有或需要保密。相比之下，大量的分组 密码建议已经出版，其中的一些已经被标准化或公开
却希望它的输出（密钥序列k）对不知情的人来 说象是随机的。 到底该从哪些角度把握随机性等，才使所设计出 来的KG能够具有我们需要的安全程度？

24
密钥流生成器的分解
k
k
驱动子 系统
非线性 组合子 系统
zi
25
常见的两种密钥流产生器
目前最为流行和实用的密钥流产生器如 图所示，其驱动部分是一个或多个线性反馈 移位寄存器。
LFSR
………
LFSR1
LFSR2 ……
F
zi
F
zi
LFSRn
26
KG的一般结构
通常，人们总是把KG设计得具有一定 的结构特点，从而可以分析和论证其强度， 以增加使用者的置信度。一般有以下模式：
23
同步序列密码密钥流产生器
由于具有非线性的υ的有限状态自动机理 论很不完善，相应的密钥流产生器的分析工 作受到极大的限制。相反地，当采用线性的 φ和非线性的ψ时，将能够进行深入的分析 并可以得到好的生成器。为方便讨论，可将 这类生成器分成驱动部分和非线性组合部分 （如下图）。 驱动部分控制生成器的状态转移，并为 非线性组合部分提供统计性能好的序列；而 非线性组合部分要利用这些序列组合出满足 要求的密钥流序列。
6
1.1 同步序列密码
根据加密器中记忆元件的存储状态σi是 否依赖于输入的明文字符，序列密码可进一 步分成同步和自同步两种。 σi独立于明文字符的叫做同步序列密码， 否则叫做自同步序列密码。由于自同步序列 密码的密钥流的产生与明文有关，因而较难 从理论上进行分析。目前大多数研究成果都 是关于同步序列密码的。
18
密钥序列生成器(KG)基本要求
人们就目前的想象和预见，对KG提出 了以下基本要求： 种子密钥k的变化量足够大，一般应 在2128以上； KG产生的密钥序列k具极大周期，一 般应不小于255； k具有均匀的n-元分布，即在一个周 期环上，某特定形式的n-长bit串与其求反， 两者出现的频数大抵相当(例如，均匀的游 程分布)；

＋ 容易验证该线性反馈移位寄存器的输出序列为 1001101001000010101110110001111100110…， 这个线性移位寄存器序列是一个周期序列，周期为31。
四川大学电子信息学院 24
3 线性反馈移位寄存器的一元多项式表示
设一个GF（2）上的n阶线性移位寄存器的反馈函数为： f（x1，x2，… ， xn）＝－cnx1－cn－1x2－…－c1xn， 其中ci∈GF（2）, 1≤i≤n。 该线性移位寄存器的输出序列a0a1a2…满足递推关系式 an＋t＝－c1an＋t－1－c2an＋t－2－…－cnat，t≥0， 即 an＋t＋c1an＋t－1＋c2an＋t－2＋…＋cnat＝0，t≥0。
0
a0 1
S1=(1, 1, 0)
四川大学电子信息学院
21
在第二个时钟到来时
第3级 第2级 第1级 输出
1 1 f(x1,x2,x3)=x1x2⊕x3 x1=1, x2=1, x3=0
1
a0 0
S2=(1, 1, 1)
则其输出序列和状态序列如下 状态序列: (1,0,1) (1,1,0) (1,1,1) (0,1,1) (1,0,1) (1,1,0) …. 输出序列: 1 0 1 1 1 0 …. 由上面的结果可以看出，这个反馈移位寄存器的状态序 列和输出序列都是周期序列，其周期为4。
序列密码基础
唐
龙
四川大学电子信息学院
1
主要内容
• 序列密码的概述 • 伪随机序列的常规特性 • 序列密码的分类 • 有限域上的线性反馈移存器（LFSR）
• RC4
四川大学电子信息学院
2
1、序列密码的概述 、
1.1 序列密码定义
• 香农的保密理论提出：一次一密是理论完全保密的密码体 香农的保密理论提出： 但是必须满足随机的密钥序列必须满足与明文等长。 制，但是必须满足随机的密钥序列必须满足与明文等长。 • 设想使用少量的真随机数按一定的固定规则生成“伪随机” 设想使用少量的真随机数按一定的固定规则生成“伪随机” 的密钥序列，代替真正的随机序列。这就产生了序列密码。 的密钥序列，代替真正的随机序列。这就产生了序列密码。 序列密码关键就是如何设计伪随机序列。 序列密码关键就是如何设计伪随机序列。 • 少量的真随机数，就是序列密码的密钥，也有人称为种子 少量的真随机数，就是序列密码的密钥， 密钥。 密钥。 • 序列密码的安全性基础在于如何刻画密钥序列“随机性” 序列密码的安全性基础在于如何刻画密钥序列“随机性”， 如何保障密钥序列的“随机性” 如何保障密钥序列的“随机性”不会造成加密算法在实际 中被攻破。 中被攻破。

1、真值表
例如 f (x) f (x1, x2 )
x
f(x)
0
0
0
0
1
1
1
0
1
1
1
0
2、小项表示 小项表示实际上是布尔代数表达方式，即逻辑表达
方式，此方法常用于布尔函数的设计实现。 上例的小项表示为 f (x) x1x2 x1 x2
3、多项式表示 因为 x 1 x ，将小项表示中的逻辑非的形式换掉 即得多项式表示。
任意正整数k有 ak ak p 成立，称满足该式的最小正 整数p为序列的周期。
r级线性反馈移存器的最长周期: 2r 1 ，能 达到最长周期的线性移存器序列称为m序列。
在密码学中，我们希望参与变换的序列周期越长越好，因 此对线性反馈移存器我们更感兴趣的是能达到最长周期的序 列，即m序列。
（五）、实例（画出下列个移存器的逻辑框图，写出相
预备知识：布 尔 函 数
一般地，我们把n元布尔函数定义为如下映射：
记为
，其中f : F2n F2
f (x)
x (x1, x2 ,, xn ) F2n , f (x) F2 , F2 0, 1
布尔函数是研究数字逻辑电路的重要数学工具， 在序列密码、分组密码和公钥密码中，布尔函数都有 重要的应用。特别在序列密码中，布尔函数是重要的 数学工具之一。
应的线性递推式，并讨论由它们所产生的序列）
1、不可约多项式 f (x) x4 x3 x2 x 1
2、可约多项式 f (x) x4 x3 x 1 (x3 1)(x 1)
3、本原多项式
f (x) x4 x 1
4、环式移存器
f (x) x4 1
答案： 1、该移存器产生三类周期相同（全为5）的序列及一 个全零序列。 2、该移存器产生五类周期分别为6、3、3、2、1的序 列及一个全零序列。 3、该移存器产生周期为15的m序列及一个全零序列。

010
101
100
000
110
011
001
111
二、线性移位寄存器 （LFSR：Linear Feedback Shift Register）
反馈函数为线性函数。否则为非线性反馈移位寄存器。
我们总要求第一级的系数不为0，称之为非退化的。 如果第一级的系数为0，则不是n阶反馈了，称为退化的。 例6.2(P103)
同时产生与明文相同长度的密钥流:
r r0r1r3 , ri GF (2)
加密为： y y0 y1 y2 , yi xi ri ,
yi GF (2)
解密为： xi yi ri
如果每隔固定的r个字符或比特，以后密钥重复使用，
则为周期序列密码；密钥不重复的为非周期序列密码。
同步方式（synchronous）；自同步方式（self-synchronous
c1 (ain1 bin1) c2 (ain2 bin2 ) cn (ai b)
c1d in1c2d in2 cn di 故 d G( f ) 又， a b (a0a1 an ) (b0b1 bn ) . 证毕.
定理 6.4： f (x) | h(x) G( f ) G(h) .
周期为 24 1 15
p(a ) 2n 1 的序列称为n 阶 m序列。
第一个初态！
1000
1100
0001
1110
0010
1111 0000
0100
0111 1001
1011 0101
0110 0011
1010 1101
只要进入， 就得循环！
第二个初态！
由例子可得出以下结论： （1）n-LFSR的结构由其结构常数唯一确定； （2）n-LFSR的结构常数与反馈函数互相唯一确定； （3）n-LFSR序列由其结构常数和初态唯一确定；