第 7章 序列密码
序列密码又称流密码。它是将明文消息字符
串逐位地加密成密文字符。
7.1 布尔函数
7.1.1 布尔函数的表示
? 真值表
? 小项表示
? 多项式表示
? Walsh谱表示
? 定义 7.1 设,,x
与 w的点积定义为
, n元布尔函数 f(x)的 Walsh变换定义为
,其逆变换为
。 称为的第一种谱或 Walsh谱。
? 定义 7.2 定义 为 f(x)的
第二种谱或循环谱。
),,( 1 nxxx ?? nn GFwww )2(),,( 1 ?? ?
)2(11 GFwxwxwx nn ????? ?
??
?
?? ?? 12
0
)()1(2)(
n
x
xwn
f xfwS ?
?
?
?? ?? 12
0
)1)((2)(
n
w
xwfn wSxf
))2()(( nf GFwwS ?
??
?
?? ??? 12
0
)(
)( )1()1(2)(
n
x
xwxfn
f wS
? 定理 7.1 与 关系如下,
? 定理 7.2 设,, f(x)
是 n元布尔函数，则
,这里 P(.)表示概率。
)()( wS f )(wSf
?
?
?
??
???
0),(21
0),(2)(
)( wwS
wwSwS
f
f
f
),,( 1 nxxx ?? nn GFwww )2(),,( 1 ?? ?
2
)(1))(( )( wSwxxfP f???
2
)(1))(( )( wSwxxfP f???
7.1.2 布尔函数的非线性
? 定义 7.3 设 f(x)是一个 n元布尔函数，记
为所有 n元线性函数（包括仿射函数）之集。
f(x)的非线性度定义为
记为 Nf，即 f(x)的非线性度为其与所有线性
函数之最短距离，于是线性函数的非线性度
为 0。称 为 f(x)的线性度，记为 Cf。即
的线性度是 f(x)与所有线性函数的最大距离。
? 定义 7.4 若 l(x)使得,则称 l(x)为
f(x)的最佳线性逼近。
][xLn
)(m in),(m in ][][ lfwlfd xLlxLl nn ?? ??
),(m ax ][ lfdxLl
n?
fNlfd ?),(
? 定理 7.3 任意 n元布尔函数 f(x)的非线性度满
足,使等式成立（即非线性度最高）的
函数定义为 Bent函数。
? 定义 7.5 若对任意,有
,即 是平衡函数，则
称 f(x)满足严格雪崩准则。若将 f(x)的任意 k个分
量固定为常数，得到 n-k的元函数均满足严格雪崩
准则，则 f(x)称满足 k(0≤k≤n -2)阶雪崩准则。严
格雪崩准则记为 SAC,k阶雪崩准则记为 SAC(k)。
满足严格雪崩准则的函数称为 SAC函数。
121 22 ?? ?? nn
fN
1)(,)2(),,( 1 ??? cwGFccc nn?
12))()(( ???? ncxfxfw )()( cxfxf ??
? 定义 7.6 设,若 是
平衡函数，即
,则称 f(x)关于 α 满足扩散准则。若对任意
满足 1≤w( α )≤k 的 α, f(x)关于 α 满足扩
散准则，则称 f(x)满足 k次扩散准则。
0,)2( ?? ?? nGF )()( ??? xfxf
12))()(( ???? nxfxfw ?
7.1.3 布尔函数的相关免疫性
? 定义 7.7 设 是 n个彼此独立，对称的二
元随机变量的布尔函数，称 f(x)是 m阶相关免疫的，
当且仅当 z与 中的任 m个随机变量 统
计独立，或者，当且仅当互信息,
对任一组 成立。
? 当 m=1时，称 f(x)是 1阶相关免疫函数，或一般地
称为相关免疫函数；当 m≥2时，亦称 f(x)为高阶
免疫函数。
? 一个函数 f(x)是相关免疫的，也说 f(x)具有相关免
疫性，或说 f(x)满足相关免疫准则。
),,( 1 nxxfz ??
nxx,,1 ?
mii xx,,1 ? 0),,;( 1 ?mii xxzI ?
niixx mii m ??? ?? 11,,,1
7.1.4 布尔函数不同性质之间的关系
? 一种性质表示了函数在某一应用中的性能，
其量化便是这种性能的衡量指标，如非线性
是密码系统中为抵抗线性攻击而提出的性能，
非线性度则是衡量其非线性性能强弱的指标。
若从这个意义上讲，非线性度越高越好，但
非线性度达到最高的函数，其他性能将变弱。
如当非线性度达到最高时，将失去相关免疫
性。因此，研究不同性质之间的关系，特别
是不同性能指标之间的数量关系是布尔函数
研究中的一个重要课题。
7.1.5 多输出布尔函数
? 定义 7.8 设 是 到 的
多输出布尔函数，令
则称 D(F)为 F(x)的代数次数。这里
是 n元布尔函数,deg(, )表示布尔函数的
代数次数。当 D(F)=k时，称 F(x)为 k次函
数。
))(,),(()( 1 xfxfxF m?? nGF )2( mGF )2(
? ?
})2(),,(,0),,(|))(m in { d e g (
)2(,0|d e g (m in)(
1
11?
?
????
????
m
i
m
mmii
m
GFbbbbxfb
GFFFD
?? ?
???
)1)(( mixf i ??
? 定义 7.9 设,若对任意
,集合
中恰好有 个元素，则称 F(x)是正交的。
? 定义 7.10 设,称
为 F(x)的差分
均匀性，记为 δ (F)或 δ F,F(x)称为差分
δ F均匀的。
nmxfxfxF m ?? )),(,),(()( 1 ?
mGF )2(?? })(,)2(|{ ???? ?? FGF
n
mn?2
))(,),(()( 1 xfxfxF m??
????? ?????? )()(|{m a xm a x )2(0,)2( xFxFxmn GFGF
? 定义 7.11 设,如果对任意
时,是平衡的，则称
F(x)满足严格雪崩准则（ SAC）。称 F(x)是
SAC函数。
? 定义 7.12 设,若,
则称 F(x)是完全非线性函数。
? 定义 7.13 设,称
为 F(x)的非线性度。
这里 Ln[x]表示全体线性函数（包括仿射函
数）之集。
))(,),(()( 1 xfxfxF m??
1)(,)2( ?? ?? wGF n )1)(()( mixfxf ii ???? ?
nmxfxfxF m ?? )),(,),(()( 1 ? mnF ?? 2?
nmxfxfxF m ?? )),(,),(()( 1 ?
))(),((m a x ][)(,)2(0 xlxFudN xLxlGFuF
nm
?? ???
? 定理 7.4 设,则
。
? 定理 7.5 F(x)是完全非线性函数，当且仅当
。
nmxfxfxF m ?? )),(,),(()( 1 ?
121 22 ?? ?? nn
FN
121 22 ?? ?? nn
FN
7.2 序列密码的原理
信源 编码器 加密器
译码器 解密器 信宿
信
源
加
密
器
解
密
器
信
宿
恢复的明文序列
明文序列
m i
密 钥序列生成器
器
密钥序列生成器
器
密钥源
器
秘密信道
?
?
im
ik
Ik
Ik
ic
7.3 序列的伪随机性
? 定义 7.3.1序列 {ai}称为周期序列，若存在
正整数使得
(7.3.1)
满足 (7.3.1)式的最小正整数 T称为序列 {ai}
的周期。若存在 n0，使得 是周期
序列，则称 {ai}是终归周期的。
? 定义 7.3.2 序列 {ai}的一个周期中，若
则称 为
序列的一个长为 l的游程。
a a ii T i? ? ?,,,,0 1 2 ?
?,,100 ?nn aa
ltltttt aaaaa ????? ????? 111 ? ),,,( 11 ??? lttt aaa ?
? 定义 7.3.3 GF(2)上周期为 T的序列 {ai}的自
相关函数定义为
? Golomb
? 随机性假设,
? 1) 在序列的一个周期内,0与 1的个数相差至
多为 1；
? 2) 在序列的一个周期圈内，长为 1的游程数占
总游程数的 1/2，长为 2的游程数占总游程数
的 1/22,…,长为 i的游程数占总游程数的
且在等长的游程中 0,1游程各占一半；
? 3) 自相关函数为二值。
??? ?????? ?10,10,)1()1(1)( Tk aaa TTR kk ?? ?
1 2/,,i ?
7.4 序列密码对密钥流的要求
? (1) 极大的周期。周期不少于 3× 1016或 255。
? (2) 良好的统计特性。即满足或部分满足 Golomb
的三个随机性假设。
? (3) 不能用级数较小的 (可实现长度 )线性移位寄存
器近似代替。即有很高的线性复杂度。
? (4) 用统计方法由密钥序列提取密钥生成器结构或
密钥源的足够信息在计算上是不可能的。
以上要求对保证系统安全性是必要的，但不是充分
的。
7.5 密钥流生成器
密钥流生成器
7.6 线性移位寄存器
? 反馈移位寄存器
? 例 7.6.1 有一个三级移位寄存器如图
其中初态为 。则
此移位寄存器输出序列为
1 0 1 1 1 0 1 1 1 0 1 1 …
它是周期为 4的序列。
)1,0,1(),,( 3211 ?? aaas 状态 输出
1 0
1
1 1 0
1 1 1
0 1 1
1 0 1
1 1 0
… …
1
0
1
1
1
0
…
nnnn acacacaaaf 121121,,,),.,,,,( ???? ?
? 定义 7.6.1 当 n级线性移位寄存器产生的序列 {ai}
的周期为 T=2n+1时，则称 {ai}为 n级 m序列。
? 定理 7.6.1 n级 m序列 {ai}具有如下性质,
(i)在一个周期内,0,1出现次数分别为 2n-1-1和 2n-1
次,
(ii)在一个周期圈内，总游程数为 2n-1，对 1≤i≤n -2，
长为 i的游程有 2n-i-1个，且 0,1游程各半，长为 n-1
的 0游程一个，长为 n的 1游程 1个。
(iii) {ai}的自相关函数为二值,
??
???
????
?
?
10,1
0,1
)(
T
T
R a
?
?
?
当
当
? 定理 7.6.2 设线性移位寄存器的特征多项
式为,递推序列 。
令,则,其中 。
? 定义 7.6.2 设 p(x)为 GF(2)上的多项式，
使得 p(x)|xp-1的最小 p称为 p(x)的周期或
的 p(x)阶。
? 定理 7.6.3 若 p(x)为 GF(2)上的 n次多项式，
且 p(x)是序列 {ai}的特征多项式,p为 p(x)
的阶，则 {ai}的周期 r|p。
? ? ?
?
? n
i
i
i xcxp
0
? ? ))(( xpa j ??
? ? ??
?
??
1
1
i
ii xaxA
)(
)()(
xp
xxA ?? ??
?
?
?
?
??
i
j
j
j
n
i
in
in xaxcx
1
1
1
)(?
? 定理 7.6.4 设 m(x)是产生线性移位寄存器序列
{ai}的极小多项式，则 {ai}的周期等于多项式 m(x)
的阶。
? 定理 7.6.5 n级线性移位寄存器产生的状态序列有
最大周期 2n-1的必要条件是其特征多项式 p(x)是
不可约的。
? 定义 7.6.3 p(x)为 n次不可约多项式，若 p(x)阶为
2n-1,称 p(x)为 n次本原多项式。
? 定理 7.6.6 {ai}为 n级 m序列的充要条件是其特征
多项式 p(x)为 n次本原多项式。
? 定义 7.6.4 二元序列 的线性复
杂度 C(a)定义为产生该序列的级数
最少的线性移位寄存器的级数。对全零序列
a，约定 C(a)=0。
? 定理 7.6.7 设 α = {ai}是二元周期序列，
且序列 {ai}的线性复杂度 C(α )=L≥1，则
只要知道 {ai}中任意相继的 2L位就可确定整
个序列 {ai}及产生 {ai}的极小多项式。
110,.,,,,?? Naaaa
7.7 非线性序列
7.7.1 非线性移位寄存器序列
? 定理 7.7.1 在 n级 M序列的一个周期内，
0与 1的个数各为 2n-1，在 M序列的一个周期
圈中，总游程为 2n-1,对 1≤i≤n -2,长为 i
的游程数为 2n-1-1，其中 0,1游程各半，长
为 n-1的游程不存在，长为 n的 0游程和 1游
程各 1个。
? 定理 7.7.2 GF(2)上 n级 M序列的数目
为 。 nn ??122
7.7.2 非线性前馈序列
? 引理 7.7.1 在图 7.7.1中 n级 LFSR为 n级 m
序列生成器时，对任一组不全为 0的
,存在唯一的前馈函数 f(x)，使前馈序列
是周期序列
? 这里 f(0)=0。
)22,,2,1,0( ?? nj jk ?
?? 101210 kkkkkk n ??
? 定理 7.7.2 设 LFSR为 n级 m序列生成器，
。若 f(x)的次数为 k，则
{kj}的线性复杂度 C({kj})满足
),,,()( 110 ?? nxxxfxf ?
? ? jnk
i
j CkC ?
?
?
1
)(
7.7.3非线性组合序列
? 定理 7.7.3 设,如前所述。
若 ri两两互素,f(x)与各变元均有关，则 {kj}
的周期为
线性复杂度为
其中 按实数域上运算。
),,2,1(,),(,,nirxfka ii ??
)12(
1
??
?
ir
n
i
? ? ),,()( 1 nj rrfkC ??
),,( 1 nrrf ?
7.8 序列密码分析
7.8.1 二元加法非线性组合流密码的相关攻击
? DC攻击的基本思想是，根据非线性组合器
的输出序列 {zk}与组合函数 f(x)的每个输入
序列 之间的相关性，用统计方法恢复出
LFSRi的初态和反馈函数。
}{ ikx
7.8.2 二元加法非线性组合流密码的线性逼近攻击
? 假定分析者已知如下参数,
1 非线性组合函数 f(x)；
2 LFSRi的级数 ri(i=1,…,n)
3 明文编码及语言统计特性；
4 m比特密钥流 z1z2… zm(m>2(r1+…+rn)。
? 攻击的目的不是恢复原密钥流生成器，而是利用已
知信息构造一个新生成器，级数不超过,以此
代替原密钥流生成器，从而达到对密文的近似解密。
?ir
? 定义 7.8.1 若线性函数 wx+w0使得
取最大值，则称 wx+w0是 f(x)的最佳线性
逼近。
? 定理 7.8.2设 f(x)是 n 元布尔函数,w满足
,则
当 时, wx是 f(x)的最佳线性逼近。
当 时,wx+1是 f(x)的最佳线性
逼近。
f(x)与其最佳线性逼近的符合率为 (1+a)2。
))2(,)2(())(( 00 GFwGFwwwxxfp n ????
aws f ?)()(
0)()( ?ws f
0)()( ?ws f
小结
? 有限域和移位寄存器序列是流密码的基础。
? 构作流密码的方法归纳为四种：信息论方法、
系统论方法、复杂度方法、随机化方法。
? 布尔函数。
? 有限域与环上的序列设计。
序列密码又称流密码。它是将明文消息字符
串逐位地加密成密文字符。
7.1 布尔函数
7.1.1 布尔函数的表示
? 真值表
? 小项表示
? 多项式表示
? Walsh谱表示
? 定义 7.1 设,,x
与 w的点积定义为
, n元布尔函数 f(x)的 Walsh变换定义为
,其逆变换为
。 称为的第一种谱或 Walsh谱。
? 定义 7.2 定义 为 f(x)的
第二种谱或循环谱。
),,( 1 nxxx ?? nn GFwww )2(),,( 1 ?? ?
)2(11 GFwxwxwx nn ????? ?
??
?
?? ?? 12
0
)()1(2)(
n
x
xwn
f xfwS ?
?
?
?? ?? 12
0
)1)((2)(
n
w
xwfn wSxf
))2()(( nf GFwwS ?
??
?
?? ??? 12
0
)(
)( )1()1(2)(
n
x
xwxfn
f wS
? 定理 7.1 与 关系如下,
? 定理 7.2 设,, f(x)
是 n元布尔函数，则
,这里 P(.)表示概率。
)()( wS f )(wSf
?
?
?
??
???
0),(21
0),(2)(
)( wwS
wwSwS
f
f
f
),,( 1 nxxx ?? nn GFwww )2(),,( 1 ?? ?
2
)(1))(( )( wSwxxfP f???
2
)(1))(( )( wSwxxfP f???
7.1.2 布尔函数的非线性
? 定义 7.3 设 f(x)是一个 n元布尔函数，记
为所有 n元线性函数（包括仿射函数）之集。
f(x)的非线性度定义为
记为 Nf，即 f(x)的非线性度为其与所有线性
函数之最短距离，于是线性函数的非线性度
为 0。称 为 f(x)的线性度，记为 Cf。即
的线性度是 f(x)与所有线性函数的最大距离。
? 定义 7.4 若 l(x)使得,则称 l(x)为
f(x)的最佳线性逼近。
][xLn
)(m in),(m in ][][ lfwlfd xLlxLl nn ?? ??
),(m ax ][ lfdxLl
n?
fNlfd ?),(
? 定理 7.3 任意 n元布尔函数 f(x)的非线性度满
足,使等式成立（即非线性度最高）的
函数定义为 Bent函数。
? 定义 7.5 若对任意,有
,即 是平衡函数，则
称 f(x)满足严格雪崩准则。若将 f(x)的任意 k个分
量固定为常数，得到 n-k的元函数均满足严格雪崩
准则，则 f(x)称满足 k(0≤k≤n -2)阶雪崩准则。严
格雪崩准则记为 SAC,k阶雪崩准则记为 SAC(k)。
满足严格雪崩准则的函数称为 SAC函数。
121 22 ?? ?? nn
fN
1)(,)2(),,( 1 ??? cwGFccc nn?
12))()(( ???? ncxfxfw )()( cxfxf ??
? 定义 7.6 设,若 是
平衡函数，即
,则称 f(x)关于 α 满足扩散准则。若对任意
满足 1≤w( α )≤k 的 α, f(x)关于 α 满足扩
散准则，则称 f(x)满足 k次扩散准则。
0,)2( ?? ?? nGF )()( ??? xfxf
12))()(( ???? nxfxfw ?
7.1.3 布尔函数的相关免疫性
? 定义 7.7 设 是 n个彼此独立，对称的二
元随机变量的布尔函数，称 f(x)是 m阶相关免疫的，
当且仅当 z与 中的任 m个随机变量 统
计独立，或者，当且仅当互信息,
对任一组 成立。
? 当 m=1时，称 f(x)是 1阶相关免疫函数，或一般地
称为相关免疫函数；当 m≥2时，亦称 f(x)为高阶
免疫函数。
? 一个函数 f(x)是相关免疫的，也说 f(x)具有相关免
疫性，或说 f(x)满足相关免疫准则。
),,( 1 nxxfz ??
nxx,,1 ?
mii xx,,1 ? 0),,;( 1 ?mii xxzI ?
niixx mii m ??? ?? 11,,,1
7.1.4 布尔函数不同性质之间的关系
? 一种性质表示了函数在某一应用中的性能，
其量化便是这种性能的衡量指标，如非线性
是密码系统中为抵抗线性攻击而提出的性能，
非线性度则是衡量其非线性性能强弱的指标。
若从这个意义上讲，非线性度越高越好，但
非线性度达到最高的函数，其他性能将变弱。
如当非线性度达到最高时，将失去相关免疫
性。因此，研究不同性质之间的关系，特别
是不同性能指标之间的数量关系是布尔函数
研究中的一个重要课题。
7.1.5 多输出布尔函数
? 定义 7.8 设 是 到 的
多输出布尔函数，令
则称 D(F)为 F(x)的代数次数。这里
是 n元布尔函数,deg(, )表示布尔函数的
代数次数。当 D(F)=k时，称 F(x)为 k次函
数。
))(,),(()( 1 xfxfxF m?? nGF )2( mGF )2(
? ?
})2(),,(,0),,(|))(m in { d e g (
)2(,0|d e g (m in)(
1
11?
?
????
????
m
i
m
mmii
m
GFbbbbxfb
GFFFD
?? ?
???
)1)(( mixf i ??
? 定义 7.9 设,若对任意
,集合
中恰好有 个元素，则称 F(x)是正交的。
? 定义 7.10 设,称
为 F(x)的差分
均匀性，记为 δ (F)或 δ F,F(x)称为差分
δ F均匀的。
nmxfxfxF m ?? )),(,),(()( 1 ?
mGF )2(?? })(,)2(|{ ???? ?? FGF
n
mn?2
))(,),(()( 1 xfxfxF m??
????? ?????? )()(|{m a xm a x )2(0,)2( xFxFxmn GFGF
? 定义 7.11 设,如果对任意
时,是平衡的，则称
F(x)满足严格雪崩准则（ SAC）。称 F(x)是
SAC函数。
? 定义 7.12 设,若,
则称 F(x)是完全非线性函数。
? 定义 7.13 设,称
为 F(x)的非线性度。
这里 Ln[x]表示全体线性函数（包括仿射函
数）之集。
))(,),(()( 1 xfxfxF m??
1)(,)2( ?? ?? wGF n )1)(()( mixfxf ii ???? ?
nmxfxfxF m ?? )),(,),(()( 1 ? mnF ?? 2?
nmxfxfxF m ?? )),(,),(()( 1 ?
))(),((m a x ][)(,)2(0 xlxFudN xLxlGFuF
nm
?? ???
? 定理 7.4 设,则
。
? 定理 7.5 F(x)是完全非线性函数，当且仅当
。
nmxfxfxF m ?? )),(,),(()( 1 ?
121 22 ?? ?? nn
FN
121 22 ?? ?? nn
FN
7.2 序列密码的原理
信源 编码器 加密器
译码器 解密器 信宿
信
源
加
密
器
解
密
器
信
宿
恢复的明文序列
明文序列
m i
密 钥序列生成器
器
密钥序列生成器
器
密钥源
器
秘密信道
?
?
im
ik
Ik
Ik
ic
7.3 序列的伪随机性
? 定义 7.3.1序列 {ai}称为周期序列，若存在
正整数使得
(7.3.1)
满足 (7.3.1)式的最小正整数 T称为序列 {ai}
的周期。若存在 n0，使得 是周期
序列，则称 {ai}是终归周期的。
? 定义 7.3.2 序列 {ai}的一个周期中，若
则称 为
序列的一个长为 l的游程。
a a ii T i? ? ?,,,,0 1 2 ?
?,,100 ?nn aa
ltltttt aaaaa ????? ????? 111 ? ),,,( 11 ??? lttt aaa ?
? 定义 7.3.3 GF(2)上周期为 T的序列 {ai}的自
相关函数定义为
? Golomb
? 随机性假设,
? 1) 在序列的一个周期内,0与 1的个数相差至
多为 1；
? 2) 在序列的一个周期圈内，长为 1的游程数占
总游程数的 1/2，长为 2的游程数占总游程数
的 1/22,…,长为 i的游程数占总游程数的
且在等长的游程中 0,1游程各占一半；
? 3) 自相关函数为二值。
??? ?????? ?10,10,)1()1(1)( Tk aaa TTR kk ?? ?
1 2/,,i ?
7.4 序列密码对密钥流的要求
? (1) 极大的周期。周期不少于 3× 1016或 255。
? (2) 良好的统计特性。即满足或部分满足 Golomb
的三个随机性假设。
? (3) 不能用级数较小的 (可实现长度 )线性移位寄存
器近似代替。即有很高的线性复杂度。
? (4) 用统计方法由密钥序列提取密钥生成器结构或
密钥源的足够信息在计算上是不可能的。
以上要求对保证系统安全性是必要的，但不是充分
的。
7.5 密钥流生成器
密钥流生成器
7.6 线性移位寄存器
? 反馈移位寄存器
? 例 7.6.1 有一个三级移位寄存器如图
其中初态为 。则
此移位寄存器输出序列为
1 0 1 1 1 0 1 1 1 0 1 1 …
它是周期为 4的序列。
)1,0,1(),,( 3211 ?? aaas 状态 输出
1 0
1
1 1 0
1 1 1
0 1 1
1 0 1
1 1 0
… …
1
0
1
1
1
0
…
nnnn acacacaaaf 121121,,,),.,,,,( ???? ?
? 定义 7.6.1 当 n级线性移位寄存器产生的序列 {ai}
的周期为 T=2n+1时，则称 {ai}为 n级 m序列。
? 定理 7.6.1 n级 m序列 {ai}具有如下性质,
(i)在一个周期内,0,1出现次数分别为 2n-1-1和 2n-1
次,
(ii)在一个周期圈内，总游程数为 2n-1，对 1≤i≤n -2，
长为 i的游程有 2n-i-1个，且 0,1游程各半，长为 n-1
的 0游程一个，长为 n的 1游程 1个。
(iii) {ai}的自相关函数为二值,
??
???
????
?
?
10,1
0,1
)(
T
T
R a
?
?
?
当
当
? 定理 7.6.2 设线性移位寄存器的特征多项
式为,递推序列 。
令,则,其中 。
? 定义 7.6.2 设 p(x)为 GF(2)上的多项式，
使得 p(x)|xp-1的最小 p称为 p(x)的周期或
的 p(x)阶。
? 定理 7.6.3 若 p(x)为 GF(2)上的 n次多项式，
且 p(x)是序列 {ai}的特征多项式,p为 p(x)
的阶，则 {ai}的周期 r|p。
? ? ?
?
? n
i
i
i xcxp
0
? ? ))(( xpa j ??
? ? ??
?
??
1
1
i
ii xaxA
)(
)()(
xp
xxA ?? ??
?
?
?
?
??
i
j
j
j
n
i
in
in xaxcx
1
1
1
)(?
? 定理 7.6.4 设 m(x)是产生线性移位寄存器序列
{ai}的极小多项式，则 {ai}的周期等于多项式 m(x)
的阶。
? 定理 7.6.5 n级线性移位寄存器产生的状态序列有
最大周期 2n-1的必要条件是其特征多项式 p(x)是
不可约的。
? 定义 7.6.3 p(x)为 n次不可约多项式，若 p(x)阶为
2n-1,称 p(x)为 n次本原多项式。
? 定理 7.6.6 {ai}为 n级 m序列的充要条件是其特征
多项式 p(x)为 n次本原多项式。
? 定义 7.6.4 二元序列 的线性复
杂度 C(a)定义为产生该序列的级数
最少的线性移位寄存器的级数。对全零序列
a，约定 C(a)=0。
? 定理 7.6.7 设 α = {ai}是二元周期序列，
且序列 {ai}的线性复杂度 C(α )=L≥1，则
只要知道 {ai}中任意相继的 2L位就可确定整
个序列 {ai}及产生 {ai}的极小多项式。
110,.,,,,?? Naaaa
7.7 非线性序列
7.7.1 非线性移位寄存器序列
? 定理 7.7.1 在 n级 M序列的一个周期内，
0与 1的个数各为 2n-1，在 M序列的一个周期
圈中，总游程为 2n-1,对 1≤i≤n -2,长为 i
的游程数为 2n-1-1，其中 0,1游程各半，长
为 n-1的游程不存在，长为 n的 0游程和 1游
程各 1个。
? 定理 7.7.2 GF(2)上 n级 M序列的数目
为 。 nn ??122
7.7.2 非线性前馈序列
? 引理 7.7.1 在图 7.7.1中 n级 LFSR为 n级 m
序列生成器时，对任一组不全为 0的
,存在唯一的前馈函数 f(x)，使前馈序列
是周期序列
? 这里 f(0)=0。
)22,,2,1,0( ?? nj jk ?
?? 101210 kkkkkk n ??
? 定理 7.7.2 设 LFSR为 n级 m序列生成器，
。若 f(x)的次数为 k，则
{kj}的线性复杂度 C({kj})满足
),,,()( 110 ?? nxxxfxf ?
? ? jnk
i
j CkC ?
?
?
1
)(
7.7.3非线性组合序列
? 定理 7.7.3 设,如前所述。
若 ri两两互素,f(x)与各变元均有关，则 {kj}
的周期为
线性复杂度为
其中 按实数域上运算。
),,2,1(,),(,,nirxfka ii ??
)12(
1
??
?
ir
n
i
? ? ),,()( 1 nj rrfkC ??
),,( 1 nrrf ?
7.8 序列密码分析
7.8.1 二元加法非线性组合流密码的相关攻击
? DC攻击的基本思想是，根据非线性组合器
的输出序列 {zk}与组合函数 f(x)的每个输入
序列 之间的相关性，用统计方法恢复出
LFSRi的初态和反馈函数。
}{ ikx
7.8.2 二元加法非线性组合流密码的线性逼近攻击
? 假定分析者已知如下参数,
1 非线性组合函数 f(x)；
2 LFSRi的级数 ri(i=1,…,n)
3 明文编码及语言统计特性；
4 m比特密钥流 z1z2… zm(m>2(r1+…+rn)。
? 攻击的目的不是恢复原密钥流生成器，而是利用已
知信息构造一个新生成器，级数不超过,以此
代替原密钥流生成器，从而达到对密文的近似解密。
?ir
? 定义 7.8.1 若线性函数 wx+w0使得
取最大值，则称 wx+w0是 f(x)的最佳线性
逼近。
? 定理 7.8.2设 f(x)是 n 元布尔函数,w满足
,则
当 时, wx是 f(x)的最佳线性逼近。
当 时,wx+1是 f(x)的最佳线性
逼近。
f(x)与其最佳线性逼近的符合率为 (1+a)2。
))2(,)2(())(( 00 GFwGFwwwxxfp n ????
aws f ?)()(
0)()( ?ws f
0)()( ?ws f
小结
? 有限域和移位寄存器序列是流密码的基础。
? 构作流密码的方法归纳为四种：信息论方法、
系统论方法、复杂度方法、随机化方法。
? 布尔函数。
? 有限域与环上的序列设计。
