2012-3-19 1
第二章 序列密码
一、序列密码的基本概念
二、线性反馈移位寄存器
三,B-M综合算法
四、非线性序列
2012-3-19 2
一、序列密码的基本概念
2012-3-19 3
序列密码的分类
? 同步序列密码 SSC(Synchronous Stream Cipher),
?i与明文消息无关, 密钥流将独立于明文 。
? 特点,
– 对于明文而言, 这类加密变换是无记忆的 。 但它是
时变的 。
– 只有保持两端精确同步才能正常工作 。
– 对主动攻击时异常敏感而有利于检测
– 无差错传播 (Error Propagation)
2012-3-19 4
序列密码的分类
? 自 同 步 序 列 密 码 SSSC(Self-Synchronous Stream
Cipher)
?i依赖于 (kI,?i-1,mi),使密文 ci不仅与当前输入
mi有关, 而且由于 ki对 ?i的关系而与以前的输入 m1,
m2,…,mi-1有关 。 一般在有限的 n级存储下将与 mi-
1,…,mi-n有关 。
? 优点：具有自同步能力，强化了其抗统计分析的能力
? 缺点,有 n位 长的差错传播 。
2012-3-19 5
序列密码的分类
n级移存器 n 级移存器
… …
… …
ki f f ki
ki ki
mi Eki(·) ci ci Dki(·) mi
2012-3-19 6
序列的伪随机性
? 周期
序列 {ki}i?0,使 对所有 i,ki+p=ki 成立的的最小整数 p
? 长为 l的串 (run) (kt,kt+1… kt+l -1)
序列 {ki}的一个周期中, kt-1?kt=kt+1=…= kt+l -1? kt+l
例：长为 l的 1串和长为 l的 0串,
???? ?????? ?? 10001,01110,ll
2012-3-19 7
序列的伪随机性
? 周期自相关函数
周期为 p的序列 {ki}i?0,其周期自相关函数
R(j)=(A－ D)/p, j=0,1,…
式中, A=?{0?i<p|,ki=ki+j}?,D=?{0?i<p,ki?ki+j}?
。
? 同相自相关函数
当 j为 p的倍数, 即 p?j时为, R(j)=1；
? 异相自相关函数
当 j不是 p的倍数时
2012-3-19 8
例 2－ 2
二元序列 111001011100101110010…
周期 p=7
同相自相关函数 R(j)=1
异相自相关函数 R(j)=－ 1/7。
2012-3-19 9
Golomb随机性假设－ PN序列
G1,若 p为偶, 则 0,1出现个数相等, 皆为 p/2。 若 p为奇
,则 0出现个数为 (p?1)/2。
G2,长为 l的串占 1/2l,且, 0” 串和, 1” 串个数相等或
至多差一个 。
G3,R(j)为双值, 即所有异相自相关函数值相等 。 这与白
噪声的自相关函数 (?函数 )相近, 这种序列又称为双值序
列 (Two Value Sequence)。
PN序列可用于通信中同步序列, 码分多址 (CDMA)、
导航中多基站码, 雷达测距码等 。 但仅满足 G1～ G3特性
的序列虽与白噪声序列相似, 但远还不能满足密码体制
要求 。
2012-3-19 10
满足密码体制的另外三个条件
C1,周期 p要足够大, 如大于 1050；
C2,序列 {ki}i?0产生易于高速生成；
C3,当序列 {ki}i?0的任何部分暴露时, 要分析整个序列,
提取产生它的电路结构信息, 在计算上是不可行的, 称
此为不可预测性 (Unpredictability)。
C3决定了密码的强度, 是序列密码理论的核心 。 它
包含了序列密码要研究的许多主要问题, 如线性复杂度
,相关免疫性, 不可预测性等等 。
2012-3-19 11
二、线性反馈移位寄存器序列
2012-3-19 12
线性反馈移位寄存器序列概念
? 级数 (Stages),存储单元数 。
? 状态 (State),n个存储单元的存数 (ki,…,ki+n-1)
? 反馈函数,f(ki,ki+1,…,ki+n-1)是状态 (ki,…,ki+n-1)的函数
。
? 线性反馈移位寄存器 (LFSR),f 为线性函数
? 非线性反馈移位寄存器,f 为非线性函数
2012-3-19 13
反馈移位寄存器
x1,x2,… xn
f (ki,ki+1,… ki+n-1)
ki+n
ki+n-1 ki+n-2 ki+1 ki ki-1.,…,k1 k0
xn xn-1 x2 x1
2012-3-19 14
线性反馈移位寄存器
f(x)为线性函数，输出序列满足下式
cn -cn-1 -cn-2 -c1 -c0
ki+n-1 ki+n-2 ki+1 ki ki-1,…,k1,k0
xn xn-1 x2 x1
?
?
?
???? ????
1
0
1 0),,(
n
j
jijniini ikckkfk ?
2012-3-19 15
二元线性移位寄存器
二元条件下 ki?{0,1},cj ?{0,1},即断开或连通，
?为模 2加，反馈函数可写成 n阶线性递推关系式
cn cn-1 cn-2 c1 c0
ki+n-1 ki+n-2 ki+1 ki ki-1,…,k1,
x x x x
?
?
? ?
n
j
jij kc
0
0
2012-3-19 16
线性反馈移位寄存器
例 n=4的 LFSR。 输出序列满足 ki－ 4＋ ki－ 3＋ ki=0。初始状
态为 1000。序列的周期为 15=24－ 1。
c4 c3 c2 c1 c0 ki
0 0 0 1
线性移存器序列的最长周期为 2n－ 1。
2012-3-19 17
状态转移和相应输出
时刻 状 态 输 出
3 2 1 0 0
0 0 0 0 1 1
1 1 0 0 0 0
2 0 1 0 0 0
3 0 0 1 0 0
4 1 0 0 1 1
5 1 1 0 0 0
6 0 1 1 0 0
7 1 0 1 1 1
8 0 1 0 1 1
9 1 0 1 0 0
10 1 1 0 1 1
2012-3-19 18
m序列
? 为 2n－ 1的 LFSR序列称为 m序列。 m序列是一类 PN
序列 。
? n级 m序列 {ki}i?0循环地遍历所有 2n－ 1个非零状态，
且任一非零输出皆为 {ki}i?0的移位，或为其循环等价
(Cyclically equivalent)序列 。
? 初始状态不同 2n－ 1个的 m序列共有 2n－ 1个,他们的
全体记为 ?(f),他们只是状态前后次序之别 。
2012-3-19 19
特征多项式
? 以 LFSR的反馈系数所决定的多项式
又称 反馈多项式 。 式中, c0=cn=1
? 反多项式
称作是 LFSR的 联接多项式 。 cn?0称之为非奇异 LFSR。
?
?
?
? ???????
n
j
j
j
nn
n xcxxcxcxccxf
0
1
1
2
210,..)(
nn
nnn cxcxcxc
x
fxxfxc ??????? ?? 1110*,..)1()()(
2012-3-19 20
特征多项式
定义,给定序列 {ki}i?0,幂级数
称为该序列的 生成函数
定理 3-1 令 {ki}i?0??(f),f(x)是反馈多项式, 令 k(x)是
{ki}i?0的生成函数, 则
其中
?
?
?
?
0
)(
i
i
i xkxk
)(
)()(
* xf
xaxk ?
? ?
?
? ?
???
1
0 0
)()(
n
j
j
j
l
ljln xkcxa
2012-3-19 21
特征多项式
证,
)(
)()()(
))((
))(()()(
0
)(
1
0 0 0
0
)m i n (
0
00
*
,
xa
tlnxkcxa
xkcxkc
xkc
xcxkxfxk
nj
j
n
j
tnjt
n
j
j
l nj
n
l
j
ljln
j
ljln
j
nj
l
j
ljln
n
l
l
ln
i
i
i
?
????
??
?
?
? ?
? ? ? ?
? ?
??
? ?
??
?
? ? ? ?
????
?
? ?
??
?
?
?
?
a(x)就是移存器初始值所对应的多项式
2012-3-19 22
特征多项式
系,
证, ?(f)的每个元素均可由 a(x)/f ?(x)惟一决定, 式
中, deg(a(x))<n,另一方面, ?(f)有 2n个元素 。
而 deg(a(x))<n的多项式也恰有 2n个 。
}))(d e g ()(/)({)( nxaxfxaf ?? ?＝
2012-3-19 23
多项式的周期
? 多项式 f(x)的周期 p为使 f(x)除尽 xn-1的最小整数 n的取
值 。
? 序列的周期与生成序列特征多项式的周期密切相关 。
引理 3-2,
令 f(x)为 n次式, 周期为 p,令 {ki}i?0??(f),则 {ki}i?0的
周期 p’?p。
2012-3-19 24
多项式的周期
引理 3-3 令 f(x)是周期为 p的 n次既约多项式, 令
{ki}i?0??(f),则 {ki}i?0的周期为 p。
证,令 {ki}i?0周期为 p’,由引理 3-2-3,有 p’?p,则有,
deg(u(x))<p, 由 ( 3 - 2 - 12)式有 k(x)=a(x)/f*(x),故有,
由此可得
因为 f(x)为 n次既约式, deg(a(x))<n,因此有 f(x)?(1＋ xp’)
但 f(x)的周期为 p,故有 p|p’所以 p’=p。
)()()()1( xfxuxax p ?? ?? ＇
)()()()1( " xfxuxax p ???
2012-3-19 25
多项式的周期
引理 3-4 令 f(x)为 n次式, 令 {ki}i?0??(f)为 m序列, 则 f(x)
为既约的 。
证：采用反证法 。 假定 f(x)=f1 (x)·f2(x),f1(x)为既约式
,次 数 为 n1,n2>0,n1 >n2。 由 ( 3 - 2 - 14) 式,
1/f1*(x)??(f1),故由引理 3-2-3及附录 3A,1/f1* (x)的
周期除尽 。 类似地有 。 由定理 3-2-1知 1/f1*(x)应是
{ki}i?0的移位,,因而其周期为 2n－ 1,惟一可能是
n=n1,即 f(x)=f1(x)。
2012-3-19 26
m序列的性质
定理 3-5 以 f(x)为特征多项式的 LFSR的输出序列是 m
序列的充要条件为 f(x)是本原的 。
系 n级 LFSR生成的不等价 m序列共有 ?(2n－ 1)/n个 。
定理 3-6 m序列满足 Golomb的三条伪随机假设 。
2012-3-19 27
m序列的性质
m序列否满足密码要求？
? m-C1,n级 m序列的周期为 2n－ 1,n大, 周期指数地
加大, 例如 n=166时, p=1050(9.353610465 × 1049)。
? m-C2,只要知道 n次本原多项式, m序列极易生成 。
? m-C3,m序列极不安全, 只要泄露 2n位连续数字, 就
可完全确定出反馈多项式系数 。
2012-3-19 28
m序列的破译
已知 ki,ki+1,…,ki+2n,由递推关系式可得出下式
式中有 n个线性方程和 n个未知量, 故可惟一解出 ci，
0?i?n-1。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?????
???
???
12
1
1
1
0
21
21
11
.
.
.
.
.
.
.,,,,,
....
....
....
.,,,,,
.,,,,,
ni
ni
ni
nninini
niii
niii
k
k
k
c
c
c
kkk
kkk
kkk
2012-3-19 29
三,B-M综合算法
2012-3-19 30
根据密码学的需要，对于 LFSR主要考虑下面两问题,
(1)如何利用级数尽可能小的 LFSR产生周期长、统计特性
好的序列；
(2)已知一个序列 a，如何构造一个尽可能短的 LFSR来产
生 a。
2012-3-19 31
B-M综合算法
2012-3-19 32
2012-3-19 33
B
－M
综
合
算
法
的
描
述
2012-3-19 34
2012-3-19 35
四,非线性序列
2012-3-19 36
非线性序列
? 线性复杂度,能产生周期序列 {ki}i ?0的 LFSR的最小级
数 n。
显然,n级 m序列的线性复杂度为 n。
? 线性复杂度是研究和设计密码的重要指标和工具。
? 一个伪随机序列若其线性复杂度低，就易于由部分序列综
合出生成它的 LFSR。 一般移存器序列的线性复杂度 n<L<2n
。 L大不一定就安全；但 L小肯定是不安全的 !
2012-3-19 37
非线性前馈序列
? LFSR虽然不能直接作为密钥流用，但可作为驱动源以其
输出推动一个非线性组合函数所决定的电路来产生非线
性序列。这就是所谓非线性前馈序列生成器。
? LFSR用来保证密钥流的周期长度、平衡性等
? 非线性组合函数用来保证密钥流的各种密码性质，以抗
击各种可能的攻击。
2012-3-19 38
非线性前馈序列
? ? ? ?
LFSR?
…
F
ki
研究的中心问题：前馈函数 F与输出序列的周期性、随机
性、线性复杂度以及相关免疫性之间的关系。
2012-3-19 39
多路选择 (Multiplexing)序列
有 n种输入序列 b0(t),…,bn-1(t), 在地址
序列 a1(t),…,am -1 (t)的控制下决定输出取自某
个输入比特 。
例如取 m级 LFSR生成 m序列作地址控制, 取 n级
LFSR生成的 m序列作为输入序列 。
2012-3-19 40
多路选择 (Multiplexing)序列
可供选择的输入
…
多路选择器
多路选择密码
?? ??? ??
)()()( 110 tbtbtb n ?
?
?
?
?
?
?
?
?
)(
)(
)(
1
1
0
ta
ta
ta
m
?
制
控
址
地
2012-3-19 41
J-K触发器
J-K触发器是一个非线性器件, 有两个输入端 j,k和一个内部
状态, 即输出为 qi,,其逻辑真值如表 3-3-2所示 。 一般令 q-1=0
。
表 3-3-2
J K qi Geffe[1973]采用三个 LFSR,其中两个的输
0 0 qi-1 出通过一个 J-K触发器进行复合。如图 3-3- 9
0 1 0 所示。还可进一步推广由 s＋ 1个 LFSR
1 0 1 进行复合。 LFSR-1的时钟必须较其它 s
1 1 个 LFSR的时钟快 log2(s)倍，其中 s为 2的
幂次。
1?iq
2012-3-19 42
Geffe生成器
2中择 1多路选择器
LFSR-2
? 选择 b(t)
LFSR-3
LFSR-1
图 3-3-9 Geffe生成器
多路复合器输入两两成对, 并以 J-K触发器进行复合后送
入多路复用器 。 这类生成器的安全性不高, 易受相关攻击
。
2012-3-19 43
钟控序列生成器
钟控序列 10多年前提出的一种新的密钥流生
成法, 这种方法所生序列的线性复杂度与生成器
输入参数间具有指数的关系 。 这类序列易于由硬
件实现 。 钟控移位寄存器的级连是一种重要的序
列的流密码备选体制 。
2012-3-19 44
第二章 到此结束 谢谢大家！
第二章 序列密码
一、序列密码的基本概念
二、线性反馈移位寄存器
三,B-M综合算法
四、非线性序列
2012-3-19 2
一、序列密码的基本概念
2012-3-19 3
序列密码的分类
? 同步序列密码 SSC(Synchronous Stream Cipher),
?i与明文消息无关, 密钥流将独立于明文 。
? 特点,
– 对于明文而言, 这类加密变换是无记忆的 。 但它是
时变的 。
– 只有保持两端精确同步才能正常工作 。
– 对主动攻击时异常敏感而有利于检测
– 无差错传播 (Error Propagation)
2012-3-19 4
序列密码的分类
? 自 同 步 序 列 密 码 SSSC(Self-Synchronous Stream
Cipher)
?i依赖于 (kI,?i-1,mi),使密文 ci不仅与当前输入
mi有关, 而且由于 ki对 ?i的关系而与以前的输入 m1,
m2,…,mi-1有关 。 一般在有限的 n级存储下将与 mi-
1,…,mi-n有关 。
? 优点：具有自同步能力，强化了其抗统计分析的能力
? 缺点,有 n位 长的差错传播 。
2012-3-19 5
序列密码的分类
n级移存器 n 级移存器
… …
… …
ki f f ki
ki ki
mi Eki(·) ci ci Dki(·) mi
2012-3-19 6
序列的伪随机性
? 周期
序列 {ki}i?0,使 对所有 i,ki+p=ki 成立的的最小整数 p
? 长为 l的串 (run) (kt,kt+1… kt+l -1)
序列 {ki}的一个周期中, kt-1?kt=kt+1=…= kt+l -1? kt+l
例：长为 l的 1串和长为 l的 0串,
???? ?????? ?? 10001,01110,ll
2012-3-19 7
序列的伪随机性
? 周期自相关函数
周期为 p的序列 {ki}i?0,其周期自相关函数
R(j)=(A－ D)/p, j=0,1,…
式中, A=?{0?i<p|,ki=ki+j}?,D=?{0?i<p,ki?ki+j}?
。
? 同相自相关函数
当 j为 p的倍数, 即 p?j时为, R(j)=1；
? 异相自相关函数
当 j不是 p的倍数时
2012-3-19 8
例 2－ 2
二元序列 111001011100101110010…
周期 p=7
同相自相关函数 R(j)=1
异相自相关函数 R(j)=－ 1/7。
2012-3-19 9
Golomb随机性假设－ PN序列
G1,若 p为偶, 则 0,1出现个数相等, 皆为 p/2。 若 p为奇
,则 0出现个数为 (p?1)/2。
G2,长为 l的串占 1/2l,且, 0” 串和, 1” 串个数相等或
至多差一个 。
G3,R(j)为双值, 即所有异相自相关函数值相等 。 这与白
噪声的自相关函数 (?函数 )相近, 这种序列又称为双值序
列 (Two Value Sequence)。
PN序列可用于通信中同步序列, 码分多址 (CDMA)、
导航中多基站码, 雷达测距码等 。 但仅满足 G1～ G3特性
的序列虽与白噪声序列相似, 但远还不能满足密码体制
要求 。
2012-3-19 10
满足密码体制的另外三个条件
C1,周期 p要足够大, 如大于 1050；
C2,序列 {ki}i?0产生易于高速生成；
C3,当序列 {ki}i?0的任何部分暴露时, 要分析整个序列,
提取产生它的电路结构信息, 在计算上是不可行的, 称
此为不可预测性 (Unpredictability)。
C3决定了密码的强度, 是序列密码理论的核心 。 它
包含了序列密码要研究的许多主要问题, 如线性复杂度
,相关免疫性, 不可预测性等等 。
2012-3-19 11
二、线性反馈移位寄存器序列
2012-3-19 12
线性反馈移位寄存器序列概念
? 级数 (Stages),存储单元数 。
? 状态 (State),n个存储单元的存数 (ki,…,ki+n-1)
? 反馈函数,f(ki,ki+1,…,ki+n-1)是状态 (ki,…,ki+n-1)的函数
。
? 线性反馈移位寄存器 (LFSR),f 为线性函数
? 非线性反馈移位寄存器,f 为非线性函数
2012-3-19 13
反馈移位寄存器
x1,x2,… xn
f (ki,ki+1,… ki+n-1)
ki+n
ki+n-1 ki+n-2 ki+1 ki ki-1.,…,k1 k0
xn xn-1 x2 x1
2012-3-19 14
线性反馈移位寄存器
f(x)为线性函数，输出序列满足下式
cn -cn-1 -cn-2 -c1 -c0
ki+n-1 ki+n-2 ki+1 ki ki-1,…,k1,k0
xn xn-1 x2 x1
?
?
?
???? ????
1
0
1 0),,(
n
j
jijniini ikckkfk ?
2012-3-19 15
二元线性移位寄存器
二元条件下 ki?{0,1},cj ?{0,1},即断开或连通，
?为模 2加，反馈函数可写成 n阶线性递推关系式
cn cn-1 cn-2 c1 c0
ki+n-1 ki+n-2 ki+1 ki ki-1,…,k1,
x x x x
?
?
? ?
n
j
jij kc
0
0
2012-3-19 16
线性反馈移位寄存器
例 n=4的 LFSR。 输出序列满足 ki－ 4＋ ki－ 3＋ ki=0。初始状
态为 1000。序列的周期为 15=24－ 1。
c4 c3 c2 c1 c0 ki
0 0 0 1
线性移存器序列的最长周期为 2n－ 1。
2012-3-19 17
状态转移和相应输出
时刻 状 态 输 出
3 2 1 0 0
0 0 0 0 1 1
1 1 0 0 0 0
2 0 1 0 0 0
3 0 0 1 0 0
4 1 0 0 1 1
5 1 1 0 0 0
6 0 1 1 0 0
7 1 0 1 1 1
8 0 1 0 1 1
9 1 0 1 0 0
10 1 1 0 1 1
2012-3-19 18
m序列
? 为 2n－ 1的 LFSR序列称为 m序列。 m序列是一类 PN
序列 。
? n级 m序列 {ki}i?0循环地遍历所有 2n－ 1个非零状态，
且任一非零输出皆为 {ki}i?0的移位，或为其循环等价
(Cyclically equivalent)序列 。
? 初始状态不同 2n－ 1个的 m序列共有 2n－ 1个,他们的
全体记为 ?(f),他们只是状态前后次序之别 。
2012-3-19 19
特征多项式
? 以 LFSR的反馈系数所决定的多项式
又称 反馈多项式 。 式中, c0=cn=1
? 反多项式
称作是 LFSR的 联接多项式 。 cn?0称之为非奇异 LFSR。
?
?
?
? ???????
n
j
j
j
nn
n xcxxcxcxccxf
0
1
1
2
210,..)(
nn
nnn cxcxcxc
x
fxxfxc ??????? ?? 1110*,..)1()()(
2012-3-19 20
特征多项式
定义,给定序列 {ki}i?0,幂级数
称为该序列的 生成函数
定理 3-1 令 {ki}i?0??(f),f(x)是反馈多项式, 令 k(x)是
{ki}i?0的生成函数, 则
其中
?
?
?
?
0
)(
i
i
i xkxk
)(
)()(
* xf
xaxk ?
? ?
?
? ?
???
1
0 0
)()(
n
j
j
j
l
ljln xkcxa
2012-3-19 21
特征多项式
证,
)(
)()()(
))((
))(()()(
0
)(
1
0 0 0
0
)m i n (
0
00
*
,
xa
tlnxkcxa
xkcxkc
xkc
xcxkxfxk
nj
j
n
j
tnjt
n
j
j
l nj
n
l
j
ljln
j
ljln
j
nj
l
j
ljln
n
l
l
ln
i
i
i
?
????
??
?
?
? ?
? ? ? ?
? ?
??
? ?
??
?
? ? ? ?
????
?
? ?
??
?
?
?
?
a(x)就是移存器初始值所对应的多项式
2012-3-19 22
特征多项式
系,
证, ?(f)的每个元素均可由 a(x)/f ?(x)惟一决定, 式
中, deg(a(x))<n,另一方面, ?(f)有 2n个元素 。
而 deg(a(x))<n的多项式也恰有 2n个 。
}))(d e g ()(/)({)( nxaxfxaf ?? ?＝
2012-3-19 23
多项式的周期
? 多项式 f(x)的周期 p为使 f(x)除尽 xn-1的最小整数 n的取
值 。
? 序列的周期与生成序列特征多项式的周期密切相关 。
引理 3-2,
令 f(x)为 n次式, 周期为 p,令 {ki}i?0??(f),则 {ki}i?0的
周期 p’?p。
2012-3-19 24
多项式的周期
引理 3-3 令 f(x)是周期为 p的 n次既约多项式, 令
{ki}i?0??(f),则 {ki}i?0的周期为 p。
证,令 {ki}i?0周期为 p’,由引理 3-2-3,有 p’?p,则有,
deg(u(x))<p, 由 ( 3 - 2 - 12)式有 k(x)=a(x)/f*(x),故有,
由此可得
因为 f(x)为 n次既约式, deg(a(x))<n,因此有 f(x)?(1＋ xp’)
但 f(x)的周期为 p,故有 p|p’所以 p’=p。
)()()()1( xfxuxax p ?? ?? ＇
)()()()1( " xfxuxax p ???
2012-3-19 25
多项式的周期
引理 3-4 令 f(x)为 n次式, 令 {ki}i?0??(f)为 m序列, 则 f(x)
为既约的 。
证：采用反证法 。 假定 f(x)=f1 (x)·f2(x),f1(x)为既约式
,次 数 为 n1,n2>0,n1 >n2。 由 ( 3 - 2 - 14) 式,
1/f1*(x)??(f1),故由引理 3-2-3及附录 3A,1/f1* (x)的
周期除尽 。 类似地有 。 由定理 3-2-1知 1/f1*(x)应是
{ki}i?0的移位,,因而其周期为 2n－ 1,惟一可能是
n=n1,即 f(x)=f1(x)。
2012-3-19 26
m序列的性质
定理 3-5 以 f(x)为特征多项式的 LFSR的输出序列是 m
序列的充要条件为 f(x)是本原的 。
系 n级 LFSR生成的不等价 m序列共有 ?(2n－ 1)/n个 。
定理 3-6 m序列满足 Golomb的三条伪随机假设 。
2012-3-19 27
m序列的性质
m序列否满足密码要求？
? m-C1,n级 m序列的周期为 2n－ 1,n大, 周期指数地
加大, 例如 n=166时, p=1050(9.353610465 × 1049)。
? m-C2,只要知道 n次本原多项式, m序列极易生成 。
? m-C3,m序列极不安全, 只要泄露 2n位连续数字, 就
可完全确定出反馈多项式系数 。
2012-3-19 28
m序列的破译
已知 ki,ki+1,…,ki+2n,由递推关系式可得出下式
式中有 n个线性方程和 n个未知量, 故可惟一解出 ci，
0?i?n-1。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?????
???
???
12
1
1
1
0
21
21
11
.
.
.
.
.
.
.,,,,,
....
....
....
.,,,,,
.,,,,,
ni
ni
ni
nninini
niii
niii
k
k
k
c
c
c
kkk
kkk
kkk
2012-3-19 29
三,B-M综合算法
2012-3-19 30
根据密码学的需要，对于 LFSR主要考虑下面两问题,
(1)如何利用级数尽可能小的 LFSR产生周期长、统计特性
好的序列；
(2)已知一个序列 a，如何构造一个尽可能短的 LFSR来产
生 a。
2012-3-19 31
B-M综合算法
2012-3-19 32
2012-3-19 33
B
－M
综
合
算
法
的
描
述
2012-3-19 34
2012-3-19 35
四,非线性序列
2012-3-19 36
非线性序列
? 线性复杂度,能产生周期序列 {ki}i ?0的 LFSR的最小级
数 n。
显然,n级 m序列的线性复杂度为 n。
? 线性复杂度是研究和设计密码的重要指标和工具。
? 一个伪随机序列若其线性复杂度低，就易于由部分序列综
合出生成它的 LFSR。 一般移存器序列的线性复杂度 n<L<2n
。 L大不一定就安全；但 L小肯定是不安全的 !
2012-3-19 37
非线性前馈序列
? LFSR虽然不能直接作为密钥流用，但可作为驱动源以其
输出推动一个非线性组合函数所决定的电路来产生非线
性序列。这就是所谓非线性前馈序列生成器。
? LFSR用来保证密钥流的周期长度、平衡性等
? 非线性组合函数用来保证密钥流的各种密码性质，以抗
击各种可能的攻击。
2012-3-19 38
非线性前馈序列
? ? ? ?
LFSR?
…
F
ki
研究的中心问题：前馈函数 F与输出序列的周期性、随机
性、线性复杂度以及相关免疫性之间的关系。
2012-3-19 39
多路选择 (Multiplexing)序列
有 n种输入序列 b0(t),…,bn-1(t), 在地址
序列 a1(t),…,am -1 (t)的控制下决定输出取自某
个输入比特 。
例如取 m级 LFSR生成 m序列作地址控制, 取 n级
LFSR生成的 m序列作为输入序列 。
2012-3-19 40
多路选择 (Multiplexing)序列
可供选择的输入
…
多路选择器
多路选择密码
?? ??? ??
)()()( 110 tbtbtb n ?
?
?
?
?
?
?
?
?
)(
)(
)(
1
1
0
ta
ta
ta
m
?
制
控
址
地
2012-3-19 41
J-K触发器
J-K触发器是一个非线性器件, 有两个输入端 j,k和一个内部
状态, 即输出为 qi,,其逻辑真值如表 3-3-2所示 。 一般令 q-1=0
。
表 3-3-2
J K qi Geffe[1973]采用三个 LFSR,其中两个的输
0 0 qi-1 出通过一个 J-K触发器进行复合。如图 3-3- 9
0 1 0 所示。还可进一步推广由 s＋ 1个 LFSR
1 0 1 进行复合。 LFSR-1的时钟必须较其它 s
1 1 个 LFSR的时钟快 log2(s)倍，其中 s为 2的
幂次。
1?iq
2012-3-19 42
Geffe生成器
2中择 1多路选择器
LFSR-2
? 选择 b(t)
LFSR-3
LFSR-1
图 3-3-9 Geffe生成器
多路复合器输入两两成对, 并以 J-K触发器进行复合后送
入多路复用器 。 这类生成器的安全性不高, 易受相关攻击
。
2012-3-19 43
钟控序列生成器
钟控序列 10多年前提出的一种新的密钥流生
成法, 这种方法所生序列的线性复杂度与生成器
输入参数间具有指数的关系 。 这类序列易于由硬
件实现 。 钟控移位寄存器的级连是一种重要的序
列的流密码备选体制 。
2012-3-19 44
第二章 到此结束 谢谢大家！
