2010-5-14 1
第三章 流密码
一、流密码的基本概念
二、线性反馈移位寄存器序列
三, B-M综合算法
四,非线性序列
2010-5-14 2
一、流密码的基本概念
2010-5-14 3
流密码的分类
? 同步流密码 SSC(Synchronous Stream Cipher)：
?i与明文消息无关, 密钥流将独立于明文 。
? 特点：
? 对于明文而言, 这类加密变换是无记忆的 。 但它是时变
的 。
? 只有保持两端精确同步才能正常工作 。
? 对主动攻击时异常敏感而有利于检测
? 无差错传播 (Error Propagation)
2010-5-14 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位 长的差错传播 。
2010-5-14 5
流密码的分类
n级移存器 n 级移存器
… …
… …
ki f f ki
ki ki
mi Eki(·) ci ci Dki(·) mi
2010-5-14 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
2010-5-14 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的倍数时
2010-5-14 8
例 2－ 2
二元序列 111001011100101110010…
周期 p=7
同相自相关函数 R(j)=1
异相自相关函数 R(j)=－ 1/7。
2010-5-14 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特性
的序列虽与白噪声序列相似, 但远还不能满足密码体制
要求 。
2010-5-14 10
满足密码体制的另外三个条件
C1,周期 p要足够大, 如大于 1050；
C2,序列 {ki}i?0产生易于高速生成；
C3,当序列 {ki}i?0的任何部分暴露时, 要分析整个序列,
提取产生它的电路结构信息, 在计算上是不可行的, 称
此为不可预测性 (Unpredictability)。
C3决定了密码的强度, 是流密码理论的核心 。 它包
含了流密码要研究的许多主要问题, 如线性复杂度, 相
关免疫性, 不可预测性等等 。
2010-5-14 11
二,线性反馈移位寄存器序列
2010-5-14 12
线性反馈移位寄存器序列概念
? 级数 (Stages),存储单元数 。
? 状态 (State),n个存储单元的存数 (ki,…,ki+n-1)
? 反馈函数,f(ki,ki+1,…,ki+n-1)是状态 (ki,…,ki+n-1)的函数 。
? 线性反馈移位寄存器 (LFSR),f为线性函数
? 非线性反馈移位寄存器,f 为非线性函数
2010-5-14 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
2010-5-14 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 ?
2010-5-14 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,
xn xn-1 x2 x1
?
?
? ?
n
j
jij kc
0
0
2010-5-14 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。
2010-5-14 17
状态转移和相应输出
时刻 状 态 输 出
3 2 1 0 00 0 0 0 1 1
1 1 0 0 0 02 0 1 0 0 0
3 0 0 1 0 04 1 0 0 1 1
5 1 1 0 0 06 0 1 1 0 0
7 1 0 1 1 18 0 1 0 1 1
9 1 0 1 0 010 1 1 0 1 1
11 1 1 1 0 012 1 1 1 1 1
13 0 1 1 1 114 0 0 1 1 1
15 0 0 0 1 1
2010-5-14 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),他们只是状态前后次序之别 。
2010-5-14 19
特征多项式
? 以 LFSR的反馈系数所决定的多项式
又称 反馈多项式 。 式中, c0=cn=1
? 反多项式
称作是 LFSR的 联接多项式 。 cn?0称之为非奇异 LFSR。
?
?
?
? ???????
n
j
j
j
nn
n xcxxcxcxccxf
0
1
1
2
210,..)(
nn
nnn cxcxcxc
xfxxfxc ??????? ?
?
1
1
10
*,,,)1()()(
2010-5-14 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
2010-5-14 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)就是移存器初始值所对应的多项式
2010-5-14 22
特征多项式
系,
证, ?(f)的每个元素均可由 a(x)/f ?(x)惟一决定, 式中,
deg(a(x))<n,另一方面, ? ( f) 有 2n 个元素 。 而
deg(a(x))<n的多项式也恰有 2n个 。
}))(d e g ()(/)({)( nxaxfxaf ?? ?＝
2010-5-14 23
多项式的周期
? 多项式 f(x)的周期 p为使 f(x)除尽 xn-1的最小整数 n的取
值 。
? 序列的周期与生成序列特征多项式的周期密切相关 。
引理 3-2:
令 f(x)为 n次式, 周期为 p,令 {ki}i?0??(f),则 {ki}i?0的
周期 p’?p。
2010-5-14 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 ???
2010-5-14 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)。
第三章 流密码
一、流密码的基本概念
二、线性反馈移位寄存器序列
三, B-M综合算法
四,非线性序列
2010-5-14 2
一、流密码的基本概念
2010-5-14 3
流密码的分类
? 同步流密码 SSC(Synchronous Stream Cipher)：
?i与明文消息无关, 密钥流将独立于明文 。
? 特点：
? 对于明文而言, 这类加密变换是无记忆的 。 但它是时变
的 。
? 只有保持两端精确同步才能正常工作 。
? 对主动攻击时异常敏感而有利于检测
? 无差错传播 (Error Propagation)
2010-5-14 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位 长的差错传播 。
2010-5-14 5
流密码的分类
n级移存器 n 级移存器
… …
… …
ki f f ki
ki ki
mi Eki(·) ci ci Dki(·) mi
2010-5-14 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
2010-5-14 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的倍数时
2010-5-14 8
例 2－ 2
二元序列 111001011100101110010…
周期 p=7
同相自相关函数 R(j)=1
异相自相关函数 R(j)=－ 1/7。
2010-5-14 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特性
的序列虽与白噪声序列相似, 但远还不能满足密码体制
要求 。
2010-5-14 10
满足密码体制的另外三个条件
C1,周期 p要足够大, 如大于 1050；
C2,序列 {ki}i?0产生易于高速生成；
C3,当序列 {ki}i?0的任何部分暴露时, 要分析整个序列,
提取产生它的电路结构信息, 在计算上是不可行的, 称
此为不可预测性 (Unpredictability)。
C3决定了密码的强度, 是流密码理论的核心 。 它包
含了流密码要研究的许多主要问题, 如线性复杂度, 相
关免疫性, 不可预测性等等 。
2010-5-14 11
二,线性反馈移位寄存器序列
2010-5-14 12
线性反馈移位寄存器序列概念
? 级数 (Stages),存储单元数 。
? 状态 (State),n个存储单元的存数 (ki,…,ki+n-1)
? 反馈函数,f(ki,ki+1,…,ki+n-1)是状态 (ki,…,ki+n-1)的函数 。
? 线性反馈移位寄存器 (LFSR),f为线性函数
? 非线性反馈移位寄存器,f 为非线性函数
2010-5-14 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
2010-5-14 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 ?
2010-5-14 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,
xn xn-1 x2 x1
?
?
? ?
n
j
jij kc
0
0
2010-5-14 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。
2010-5-14 17
状态转移和相应输出
时刻 状 态 输 出
3 2 1 0 00 0 0 0 1 1
1 1 0 0 0 02 0 1 0 0 0
3 0 0 1 0 04 1 0 0 1 1
5 1 1 0 0 06 0 1 1 0 0
7 1 0 1 1 18 0 1 0 1 1
9 1 0 1 0 010 1 1 0 1 1
11 1 1 1 0 012 1 1 1 1 1
13 0 1 1 1 114 0 0 1 1 1
15 0 0 0 1 1
2010-5-14 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),他们只是状态前后次序之别 。
2010-5-14 19
特征多项式
? 以 LFSR的反馈系数所决定的多项式
又称 反馈多项式 。 式中, c0=cn=1
? 反多项式
称作是 LFSR的 联接多项式 。 cn?0称之为非奇异 LFSR。
?
?
?
? ???????
n
j
j
j
nn
n xcxxcxcxccxf
0
1
1
2
210,..)(
nn
nnn cxcxcxc
xfxxfxc ??????? ?
?
1
1
10
*,,,)1()()(
2010-5-14 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
2010-5-14 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)就是移存器初始值所对应的多项式
2010-5-14 22
特征多项式
系,
证, ?(f)的每个元素均可由 a(x)/f ?(x)惟一决定, 式中,
deg(a(x))<n,另一方面, ? ( f) 有 2n 个元素 。 而
deg(a(x))<n的多项式也恰有 2n个 。
}))(d e g ()(/)({)( nxaxfxaf ?? ?＝
2010-5-14 23
多项式的周期
? 多项式 f(x)的周期 p为使 f(x)除尽 xn-1的最小整数 n的取
值 。
? 序列的周期与生成序列特征多项式的周期密切相关 。
引理 3-2:
令 f(x)为 n次式, 周期为 p,令 {ki}i?0??(f),则 {ki}i?0的
周期 p’?p。
2010-5-14 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 ???
2010-5-14 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)。
