2013-8-4 5
2.2线性反馈移位寄存器
2013-8-4
6
反馈移位寄存器
状态：每一时刻的状态对应于GF(2)上的一个n维向量 (a1,a2,…,an) ，ai是第i级存储器的内容。共有2n种可能的状态。 反馈函数f(a1,a2,…,an)：n元布尔函数，即n个变元a1,a2,…,an 可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、 逻辑或、逻辑补等运算。 工作原理：当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容 向下一级ai-1传递，并根据寄存器此时的状态计算f(a1,a2,…,an)，作为 an+1。（输出-计算-移位-反馈）
2.3线性移位寄存器的特征多项式与序列周期
n级线性移位寄存器的输出序列满足递推关系
an+k=c1an+k-1 c2an+k-2 … cnak 用一个一元高次多项式表示 P(x)=1+c1x+…＋cn-1xn-1＋cnxn
称这个多项式为LFSR的特征多项式（连接多 项式）
2013-8-4 11
第2章 流密码
2.1 2.2 2.3 2.4 2.5 2.6 流密码的基本概念 线性反馈移位寄存器 线性移位寄存器的一元多项式表示 m序列的伪随机性 m序列密码的破译 非线性序列
1
2013-8-4
2.1 流密码的基本概念
流密码的基本思想 y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。 密钥流z=z0z1…，明文串x=x0x1x2…： 密钥流由密钥流发生器f产生：zi=f(k,σi)， σi是加密器中的记忆元件（存储器）在时刻i的状态， f是由密钥k和σi产生的函数。
2013-8-4
R(1)=R(2)=….=-1/7
15
Golomb随机性假设－PN序列
①在序列一个周期内，0与1出现个数相差至多为1; （0和1出现概率基本相同） ②长为l的游程占1/2l，在等长的游程中，“0”游 程和“1”游程个数相等或至多差一个。 （0和1在各位置上出现概率基本相同） ③异相自相关函数是常数,与白噪声的自相关函数( 函数)相近 m序列满足Golomb的三 条伪随机假设。 （序列平移不能提供更多信息） PN序列可用于通信中同步序列、码分多址(CDMA)、 导航中多基站码、雷达测距码等。PN序列虽与白噪 声序列相似，但远还不能满足密码体制要求。
线性反馈移位寄存器 实现简单、速度快、 理论成熟, 是构造密 钥流生成器的最重要 GF(2)上的n级线性反馈移位寄存器 的部件。
2013-8-4 8
例下图是一个5级线性反馈移位寄存器，其初始状态为 （a5，a4，a3， a2， a1 ）=(1,1, 0,0,1)
反馈函数f(a1,a2,a3,a4,a5)=a4 + a1
(a5,a4,a3,a2,a1) 11001 01100 输出 1 0 01011 00101 10010 1 1 0
10110
0
01001
1
输出序列为满足递推关系ak+5=ak+3+ ak
周期31
1001101001000010101110110001111100110…
C2=1
C5=1
LFSR反馈函数 f(a1,a2,a3,a4,a5)=C2a4+ C5a1 定义LFSR特征多项式（连接多项式） P(x)=1+x2＋x5
序列周期
a3
a2 +
a1
特征多项式
x3+x2+x+1
多项式周期 4 输出序列 ak+3=ak+ak+1+ak+2
10101010…
x3+1 3
ak+3=ak
101101… 3
序列周期
2
m序列的伪随机性
随机性:如果密钥流是周期的，要完全做到随机性是困难的。 游程:设{ai}=(a1a2a3…)为0、1序列，例如00110111， 其前两个数字是00，称为0的2游程；接着是11，是1的2游 程；再下来是0的1游程和1的3游程。 自相关函数:R(τ)=(1/T)∑k=1T-1 (-1)ak(-1)ak+τ, 序列向后 平移τ位，0≤τ≤T-1定义中的和式表示序列{ai}与{ai+τ}在 一个周期内对应位相同的位数与对应位不同的位数之差。当 τ=0时，R(τ)=1；当τ≠0时，称R(τ)为异相自相关函数。 10100111010

对线性移位寄存器序列进行非线性组合

2013-8-4
25
非线性组合
密钥流生成器
驱动子系统
一个或多个LFSR来实现
非线性组合子系统
用非线性组合函数F来实现
生成序列评价
周期极大化 线性复杂度
最短LFSR级数
极小特征多项式：最短LFSR的特征多项式
2013-8-4 26
2.6.2 J-K触发器

2013-8-4
0110011111 1101001000 1011010111

1011010111 1101001000 0110011111
4
2.1.3 密钥流产生器
状态转移函数 υ:σi→σi+1 输出函数 ψ:σi→zi，
密钥流发生器f: zi=f(k,σi)
目前最为流行和实用的密钥流产生器是线性反馈移位寄存器。
1
a6
a7 a8 a9 a10 c5 c4 c3 c2 c1
0
1 0 0 0 c5 c4 c3 c2 c1
1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0
0 1 c5 c4 c3 c2 c1 0 1 0 0 0 0 0 1
Sm l2 Sm1 l3 Sm 2 lm S1 0
Sm lm S1 lm1S2 l2 Sm1 l j 1Sm j
j 1 m 1
设序列{ai}满足线性递推关系：
ah1 0 1 0 0 ah ah 2 0 0 1 0 ah 1 a c c c c a 1 h n 1 h n n n 1 n 2 Sh+1=M· h S
2013-8-4
17
2.4 m序列的伪随机性
定理 m序列满足Golomb的三条伪随机假设。
m序列否满足密码要求？
① n级m序列的周期为2n－1，n大，周期指数地加大，
例如n=166时，p=1050(9.353610465 ×1049)。 ② 只要知道n次本原多项式，m序列极易生成。
③ m序列极不安全，只要泄露2n位连续数字，就可
由于X可逆
n级LFSR
cn cn 1 c1 an 1 an 2 a2 n X 1
2013-8-4
限制了其在密码学中的应用
19
序列递推关系:
ah n c1ah n1 c2 ah n2 cn ah
an1
an 2 a2 n cn cn 1 c1 a1 a2 an a2 a3 an 1 a a a n n 1 2 n 1

序列为m序列的充要条件特征多项式为本原多项式。
2013-8-4 12
初始101a3 +来自a2a1a3
a2 +
a1
特征多项式
x3+x+1 7
多项式周期
输出序列
x3+x2+1 7
ak+3=ak+ak+2
7
+
ak+3=ak+ak+1
10111001011… 7
a3 a2 a1
10100111010…101001 11010…
2013-8-4
2
加解密变换的选取

二元加法流密码 加密变换可表示为yi=zi xi。
2013-8-4
3
流加密举例
11010010000101 01100111111100
10110101111001 11010010000101 01100111111100
10110101111001
序列周期

序列周期 使对所有k，ak+r=ak 成立的的最小整数r 多项式的周期使f(x)除尽xp-1的最小整数p的取值。 序列的周期r与特征多项式的周期p密切相关。(r/p) 特征多项式是n次既约多项式周期为p ，则生成序列的 周期为p。 输出序列最大周期为2n-1。 不可约多项式最大周期达到2n-1。 m序列 本原多项式
1 0 0 1 0 0 1 0 0 0 0 1 1 0 11 0 11 0
c5
c4 c3 c2 c1 1 0 0 1 0
ak 5 c5 ak c2 ak 3 ak ak 3
2.6 非线性序列

非线性移位寄存器序列

f(a1,a2,a3)=a1a2+a3 输出序列10111011....，周期为4. 非线性移位寄存器研究困难， 对线性移位寄存器研究充分。
2013-8-4 7
线性反馈移位寄存器LFSR
线性反馈移位寄存器LFSR（linear feedback shift register）:反馈函数f(a1,a2,…,an)是线性函数. f(a1,a2,…,an)=cna1cn-1a2…c1an 输出序列an+1 其中常数ci=0或1，是模2加法。 ci=0或1可用开关的断开和闭合来实现，
a1 a2 a3 a4 a 5 a2 a3 a4 a5 a3 a4 a5 a6 a4 a5 a6 a7 a5 a6 a7 a8 a6 a7 a8 a9