2010-5-14 1
第三章 流密码
一、流密码的基本概念
二、线性反馈移位寄存器序列
三, B-M综合算法
四,非线性序列
2010-5-14 2
二,线性反馈移位寄存器序列
2010-5-14 3
m序列的性质
定理 3-5 以 f(x)为特征多项式的 LFSR的输出序列是 m序列的
充要条件为 f(x)是本原的 。
系 n级 LFSR生成的不等价 m序列共有 ?(2n－ 1)/n个 。
定理 3-6 m序列满足 Golomb的三条伪随机假设 。
2010-5-14 4
m序列的性质
m序列否满足密码要求？
? m-C1,n级 m序列的周期为 2n－ 1,n大, 周期指数地
加大, 例如 n=166时, p=1050(9.353610465× 1049)。
? m-C2,只要知道 n次本原多项式, m序列极易生成 。
? m-C3,m序列极不安全, 只要泄露 2n位连续数字,
就可完全确定出反馈多项式系数 。
2010-5-14 5
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
2010-5-14 6
三,B-M综合算法
2010-5-14 7
根据密码学的需要，对于 LFSR主要考虑下面两问题：
(1)如何利用级数尽可能小的 LFSR产生周期长、统计特性
好的序列；
(2)已知一个序列 a，如何构造一个尽可能短的 LFSR来产
生 a。
2010-5-14 8
B-M综合算法
2010-5-14 9
2010-5-14 10
B
－M
综
合
算
法
的
描
述
2010-5-14 11
2010-5-14 12
四,非线性序列
2010-5-14 13
非线性序列
? 线性复杂度：
能产生周期序列 {ki}i ?0的 LFSR的最小级数 n。
显然, n级 m序列的线性复杂度为 n。
? 线性复杂度是研究和设计密码的重要指标和工具 。
? 一个伪随机序列若其线性复杂度低，就易于由部分序
列综合出生成它的 LFSR。 一般移存器序列的线性复杂
度 n<L<2n。 L大不一定就安全；但 L小肯定是不安全的 !
2010-5-14 14
非线性前馈序列
? LFSR虽然不能直接作为密钥流用，但可作为驱动源以其
输出推动一个非线性组合函数所决定的电路来产生非线
性序列。这就是所谓非线性前馈序列生成器。
? LFSR用来保证密钥流的周期长度、平衡性等
? 非线性组合函数用来保证密钥流的各种密码性质，以抗
击各种可能的攻击。
2010-5-14 15
非线性前馈序列
? ? ? ?
LFSR?
…
F
ki
研究的中心问题：前馈函数 F与输出序列的周期性、随机
性、线性复杂度以及相关免疫性之间的关系。
2010-5-14 16
多路选择 (Multiplexing)序列
有 n种输入序列 b0(t),…,bn-1(t), 在地址
序列 a1(t),…,am -1 (t)的控制下决定输出取自某
个输入比特 。
例如取 m级 LFSR生成 m序列作地址控制, 取 n级
LFSR生成的 m序列作为输入序列 。
2010-5-14 17
多路选择 (Multiplexing)序列
可供选择的输入
…
多路选择器
多路选择密码
?? ??? ??
)()()( 110 tbtbtb n ?
?
?
?
?
?
?
?
? )(
)(
)(
1
1
0
ta
ta
ta
m
?
制
控
址
地
2010-5-14 18
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
2010-5-14 19
Geffe生成器
2中择 1多路选择器
LFSR-2
? 选择 b(t)
LFSR-3
LFSR-1
图 3-3-9 Geffe生成器
多路复合器输入两两成对, 并以 J-K触发器进行复合后送
入多路复用器 。 这类生成器的安全性不高, 易受相关攻击 。
2010-5-14 20
钟控序列生成器
钟控序列 10多年前提出的一种新的密钥流生
成法, 这种方法所生序列的线性复杂度与生成器
输入参数间具有指数的关系 。 这类序列易于由硬
件实现 。 钟控移位寄存器的级连是一种重要的序
列的流密码备选体制 。
2010-5-14 21
第三章 到此
结束 。 。
谢谢大家！
第三章 流密码
一、流密码的基本概念
二、线性反馈移位寄存器序列
三, B-M综合算法
四,非线性序列
2010-5-14 2
二,线性反馈移位寄存器序列
2010-5-14 3
m序列的性质
定理 3-5 以 f(x)为特征多项式的 LFSR的输出序列是 m序列的
充要条件为 f(x)是本原的 。
系 n级 LFSR生成的不等价 m序列共有 ?(2n－ 1)/n个 。
定理 3-6 m序列满足 Golomb的三条伪随机假设 。
2010-5-14 4
m序列的性质
m序列否满足密码要求？
? m-C1,n级 m序列的周期为 2n－ 1,n大, 周期指数地
加大, 例如 n=166时, p=1050(9.353610465× 1049)。
? m-C2,只要知道 n次本原多项式, m序列极易生成 。
? m-C3,m序列极不安全, 只要泄露 2n位连续数字,
就可完全确定出反馈多项式系数 。
2010-5-14 5
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
2010-5-14 6
三,B-M综合算法
2010-5-14 7
根据密码学的需要，对于 LFSR主要考虑下面两问题：
(1)如何利用级数尽可能小的 LFSR产生周期长、统计特性
好的序列；
(2)已知一个序列 a，如何构造一个尽可能短的 LFSR来产
生 a。
2010-5-14 8
B-M综合算法
2010-5-14 9
2010-5-14 10
B
－M
综
合
算
法
的
描
述
2010-5-14 11
2010-5-14 12
四,非线性序列
2010-5-14 13
非线性序列
? 线性复杂度：
能产生周期序列 {ki}i ?0的 LFSR的最小级数 n。
显然, n级 m序列的线性复杂度为 n。
? 线性复杂度是研究和设计密码的重要指标和工具 。
? 一个伪随机序列若其线性复杂度低，就易于由部分序
列综合出生成它的 LFSR。 一般移存器序列的线性复杂
度 n<L<2n。 L大不一定就安全；但 L小肯定是不安全的 !
2010-5-14 14
非线性前馈序列
? LFSR虽然不能直接作为密钥流用，但可作为驱动源以其
输出推动一个非线性组合函数所决定的电路来产生非线
性序列。这就是所谓非线性前馈序列生成器。
? LFSR用来保证密钥流的周期长度、平衡性等
? 非线性组合函数用来保证密钥流的各种密码性质，以抗
击各种可能的攻击。
2010-5-14 15
非线性前馈序列
? ? ? ?
LFSR?
…
F
ki
研究的中心问题：前馈函数 F与输出序列的周期性、随机
性、线性复杂度以及相关免疫性之间的关系。
2010-5-14 16
多路选择 (Multiplexing)序列
有 n种输入序列 b0(t),…,bn-1(t), 在地址
序列 a1(t),…,am -1 (t)的控制下决定输出取自某
个输入比特 。
例如取 m级 LFSR生成 m序列作地址控制, 取 n级
LFSR生成的 m序列作为输入序列 。
2010-5-14 17
多路选择 (Multiplexing)序列
可供选择的输入
…
多路选择器
多路选择密码
?? ??? ??
)()()( 110 tbtbtb n ?
?
?
?
?
?
?
?
? )(
)(
)(
1
1
0
ta
ta
ta
m
?
制
控
址
地
2010-5-14 18
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
2010-5-14 19
Geffe生成器
2中择 1多路选择器
LFSR-2
? 选择 b(t)
LFSR-3
LFSR-1
图 3-3-9 Geffe生成器
多路复合器输入两两成对, 并以 J-K触发器进行复合后送
入多路复用器 。 这类生成器的安全性不高, 易受相关攻击 。
2010-5-14 20
钟控序列生成器
钟控序列 10多年前提出的一种新的密钥流生
成法, 这种方法所生序列的线性复杂度与生成器
输入参数间具有指数的关系 。 这类序列易于由硬
件实现 。 钟控移位寄存器的级连是一种重要的序
列的流密码备选体制 。
2010-5-14 21
第三章 到此
结束 。 。
谢谢大家！
