第
5 
章　代数分析方
法


本章内容提要

相比于统计分析方法,代数分析是另一种对于基于线性反馈(如LFSR)的序列密码的
典型分析方法。虽然代数分析的思想可以追溯到Shannon[1]于1949 年发表的经典论述,但
直到2003 年,Courtois等[2]才正式提出了序列密码代数分析的思想,并对基于线性反馈的
序列密码进行了代数分析,将之应用于序列密码Toyocrypt和LILI-128 的分析。对基于线
性反馈的序列密码而言,由于线性关系无法增加代数次数,序列密码的内部状态和密钥流比
特通过非线性滤波(也称过滤)函数或者组合函数直接组合,缺乏动态增长,易导致关于一定
个数变量的大量固定次数代数关系式,从而易被线性化方法恢复出初始状态变量。如果非
线性组合函数的代数次数比较低,或者通过倍乘等化简技巧可以转化成代数次数较低的情
况,则线性反馈的初始状态可以通过线性化这些非线性方程所包含的单项式来恢复,这也是
目前为止唯一可进行理论分析的代数分析方法。其他方法,如采用Gr.bner基、XL 、SAT 
等,虽然只需较少的密钥流即可攻击成功,但缺乏对于序列密码本身构造的有效利用,只是
现有解方程方法的直接使用,从而难以获得广泛的关注和成功使用。在2003 年, 
Courtois[3]又进一步改进了代数分析方法,在获得连续密钥流的情况下,提出了快速代数分
析的思想,可以利用B-M算法等方法局部地降低代数方程的次数,从而减少单项式数目,降
低复杂度。作为代数分析方法的一个进展,在2009 年,Dinur等[4]提出了立方分析方法,其
基本思想是:利用高阶差分的性质来压缩原迭代函数,在获得的压缩结果是线性方程或者
低次方程的情况下,可以通过解方程获得初始密钥。随后,人们又提出了立方区分器、动态
立方分析、条件差分分析等方法,并被应用于序列密码Trivium 、Grain-128 和Grain-128a的
分析,其典型思想是:利用可控制的IV 变量来零化某些深度轮数的某些位置变量,得到较
易被区分的结果函数。

本章主要介绍代数分析、快速代数分析、改进的快速代数分析和立方分析4种代数分析

方法。

本章重点

● 代数分析方法的基本原理。
● 快速代数分析方法的基本原理。
● 改进的快速代数分析方法的基本原理。
● 立方分析的基本思想。
● 代数免疫度的发展背景、基本概念和特征。
5.基于线性反馈的序列密码的代数分析方法
本节主要介绍基于线性反馈(如LFSR)的序列密码(如滤波生成器、组合生成器)的代
数分析方法。这类密码的安全性已受到人们的高度关注,如相关分析。相关分析的应用范


第5 章　代数分析方法1 53 
围也在逐渐拓展。例如,文献[5]构造了一个使用所有变量的非线性低次数函数,它与原函
数具有相关性,或者说低次数非线性逼近,这种方法并不是新的,可参见文献[6]。然而,这
种方法的应用没有得到充分的重视,可能是由于最近人们才意识到求解低次数非线性多变
量方程组的有效算法的存在性[5,7-9]。文献[2]一般化了上述低次数非线性逼近方法,称之
为代数分析方法。这种一般化的方法,即使没有好的低次数线性逼近,仍可应用于序列密码
的分析,并可分析一大类序列密码。本节主要介绍文献[2]中的相关工作。
5.1.1 序列密码的代数分析方法
本节综述和扩展了文献[5]中的一般性策略,把序列密码的攻击归纳为求解一组多变量
方程。
1.可被攻击的序列密码模型
这里只考虑同步序列密码,每个状态独立于明文,从前一个状态产生。从原理上,我们
也只考虑以已知方式规则钟控的序列密码。然而这个条件有时能被放宽,如下面将要介绍
的对LILI-128的攻击。
为简单起见,将序列密码限制为二元序列密码,该密码的状态和密钥流由一系列比特组
成,并在每个时刻生成一个比特。我们也仅讨论计算下一状态的“连接函数”在F2 上是线
性的这种情况。把这个“连接函数”记为L,假定L 是公开的,只有状态是秘密的。我们也
假定从状态计算输出比特的函数f 是公开的,并不依赖于该序列密码的秘密密钥。函数
f 也被称为一个非线性滤波函数。这类序列密码包括滤波生成器和组合生成器。这类序列
密码的分析问题可描述为如下的问题。
设(k0,k1,…,kn-1)是初始状态,则这类序列密码的输出即密钥流可按如下方式给出: 
b0 =f(k0,k1,…,kn-1) 
b1 =f(L(k0,k1,…,kn-1)) 
b2 =f(L2(k0,k1,…,kn-1)) 
. 
ì
.
í
... 
... 
我们的问题是从某一密钥流比特bi(i=0,1,2,…)子集恢复密钥k=(k0,k1,…,kn-1)。将
执行一个部分已知明文攻击,即已知明文的一些比特和对应的密文比特。这些比特不必是
连续的。例如,如果明文用拉丁字母书写并且不使用太多的特殊字符,很可能所有的字符的
最高比特都等于0。如果文本是充分长的,这个对攻击者来说是足够的。这将是或几乎是
一个唯密文攻击。在这里的攻击中,仅假定有密钥流bi 中已知位置的m 个比特。
2.攻击的基本思想
在时刻t,当前的密钥流比特给出了一个等式:f(s)=bt,s 是当前的状态。主要的新
观点在于用g(s)乘以f(s),即,通常f(s)是高次数的,通过乘以一个良好选择的多变量多
项式g(s),使得f(s)g(s)具有较低的次数,记其次数为d。然后,如果bt=0,就得到一个
低次数方程f(s)g(s)=0。反过来,这也给出了一个关于内部状态比特ki(i=0,1,…,n- 
1)的低次数d 的多变量方程。如果有充分多的密钥流比特且对每一比特都得到一个这样
的方程,就能获得可被有效地求解的超定多变量方程组(也就是许多方程)。也就是说,代数
分析方法可将一类序列密码的分析问题转化为低次数多变量方程组的求解问题。

154
序列密码分析方法

3.
f 
的设计准则和已知攻击
设
f 
是用于组合密码的线性部分的输出的布尔函数,如函数的输入是LFSR 状态的一
些比特。对这样的函数的通常要求是:
f 
首先是平衡的并具有高的代数次数;为了抵抗线
性攻击和相关攻击,
f 
必须具有高的非线性度和高的相关免疫阶。

文献[5]中给出了关于
f 
的一个额外的准则:
f 
也不能与低次数非线性多变量函数有
很强的相关性,否则有效的攻击是可能的,如对Toyocrypt序列密码的攻击[5]。也就是说, 
如果
f 
满足下列两种情形之一,就有可能存在有效的攻击。

情形S1:布尔函数
f 
具有一个低的代数次数D(经典的准则)。
情形S2:
f 
能用一个具有低次数的布尔函数以接近1的概率逼近(文献[5]中的新准
则)。这个概率通常表示为1-
ε 
是某一较小的数。

ε,
文献[5]中使用情形S2 对Toyocrypt进行了实际的攻击
。


4.
f 
的新的假设和新的攻击情形
情形S3:多变量多项式
f 
有某一低次数(设其次数为d)倍式fg,
g 
是某一非零多变量
多项式。
情形S4:
f 
有某一倍式fg,使得fg 
能用一个具有低次数的函数以接近1即(1-ε)的
概率逼近,

ε 
是某一较小的数。
更重要的问题是如何使用低次数倍式,如果情形S3 和S4 都可利用,则说明新的攻击不
必要求
f 
具有一个低的代数次数或其良好逼近具有一个低的次数。
在情形S1 和S2 中,对每个在位置
t 
的已知密钥流比特bt,获得一个具体的值bt 
= 
s), 并且这样就可得到方程bk1,…,
f 
不得不具有低次数。

Lt())。对此
,
在情形S3 和S4 中,对每个在位置
t 
的已知密钥流比特bs), 得
到


f(t=f(k0,kn-1 

t=f(
f(s)g(=btg(

s)s) 
并且因为状态在时刻
t 
是s=Lt(k1,…,归结起来是

k0,1), 

knf(Lt(k1,1))Lt(k1,…,g(k0,1)) 

k0,…g(k0,1))Lt(k1,…,
对每个密钥流比特得到一个多变量方程。这个方程具有很低的次数,无须
f 
具有低次数, 
也无须
f 
有一个低次数逼近。在情形S3 下,攻击的基本形式也要求
g 
具有低次数,这一点
可通过将情形S3 分成以下4种情形来说明。

情形S3a:存在g,其次数比
f 
的次数低,使得
s)s)
当bt=1时, s)=
f(s)g(=btg(=0 
这样就能得到一组方程g(= 

kn-kn-=btkn

一定有g(0。因为
g 
的次数比
f 
的次数低, s)
0并且更易求解。
情形S3b:存在g,其次数比
f 
的次数低,使得
(s))s)1..b)g(=

1..f(g(=(ts)0 
当b0时,一定有g(0。因为
g 
的次数比
f 
的次数低,这样就能得到一组方程g(

t=s)=s)= 

0并且更易求解。
h 
的次数比
f 
的次数低, s)s)h(这种情形可归

情形S3c:存在
g 
和h,使得f(g(=s), 
结为情形S3b 。假定这种情形成立,则在f(g(=s) s) s) 

s), s))
s)s)h(的两边同乘以f(可得f(
g(s)=s)s)h(1..f(s)0,这正是情形S3b 。

f(h(=即(h(=


第
5 
章　代数分析方法

情形S3d:
f 
存在低次数因子,即存在低次数因子
g 
和h, s)g(h(

使得f(=s)s),这种
情形可归结为情形S3a。假定这种情形成立,则在f(s)=g(h(s)的两边同乘以1..g(

s)s) 
可得f(g(=g(h(=f(即(1..g(f(=0, s)具有低次数,这正

s)s)s)s)s), s))s)因为1..g(
是情形S3a
。


显然情形S3a和情形S3b是相互独立的,二者不相互影响。上述讨论可参阅文献[10 ]。
从上述讨论也可以看出,许多不同的情形可归结为情形S3a或情形S3b,其实从这里也可推
出文献[2]中给出的情形S3中的3种情况可归结为两种情况的结论。这意味着即使
f 
的
代数次数很高,只要存在一个非零的低次数多项式g,使得fg=0或(1..f)g=0,则代数分
析就能有效工作。下面给出一个重要概念———代数免疫度。一个函数
f 
的代数免疫度
(algebraicimmunity,AI)是使得fg=0或(1..f)g=0成立的非零函数
g 
的最小次数,即

AI(f)=min{deg(g):fg 
=0或(1..f)g=0,
g 
≠0} 
一个函数
f 
的代数免疫度刻画了其抵抗代数分析的能力,抵抗代数分析的问题也就变成了
寻找具有高的代数免疫度的布尔函数的问题。如果存在
g 
使得fg=0,也称
g 
为
f 
的零
化子。

现在的问题是,给定一个密码,这样的多项式
g 
是否存在,如何找到它们。这些问题留
到后面介绍。

值得一提的是,情形S1和S2分别是情形S3和S4的特殊情况,此时g=1。

5.求解超定多变量方程组
给定
m 
个密钥流比特,设
R 
是我们获得的次数为
d 
的
n 
个变量ki 
(0≤i≤n-1)的多
变量方程的个数。对一个
g 
而言,可使用R=m,但也许可以用同样的
f 
组合一些不同的
g,得到更多的方程,如R=14m。可用如下3种方法求解它们。

(1)线性化方法。有
n 
个变量ki(0≤i≤n-1)、次数不大小
d 
的单项式共有T≈Cdn
个
(假定d≤n/2)。把这些单项式中的每一个都视作一个新的变量Vj 
。给定R≥Cd 
个方程,
n 

d

得到一组关于T=Cn 
个变量Vj 
的R≥
T 
个线性方程,可通过Gaus 
消去法很容易地求解
这个有
T 
个变量的线性方程组。

d

(2)XL算法。m=O(Cn 
)个密钥流比特是不可能获得的,仍然可能需要使用XL算法
或Grobner基算法求解方程组,这样就需要较少的密钥流,但计算量较大,可参阅文献[5]。

(3)关于Gaus 
约化的复杂度。设
ω 
是Gaus 
约化的指数。理论上,376[11]。然
ω≤2.

而在该算法中可忽略的常数因子比预期要大。我们知道的最快的实际算法是Strasen算

法[12],需要大约7Tlog27个操作。因为我们的基本操作是在F2 上的,在一个CPU上,比特切

片技术在单一CPU时钟周期内可处理64个这样的操作。因此,求得的Gaus 
约化的复杂

度是7Tlog27/64个CPU时钟周期。

5..oorpt的代数分析

12 
Tycy

1.Toyocrypt 

Toyocrypt是由一个规则的钟控128b线性反馈移位寄存器(LFSR)和一个127个变量
的非线性布尔函数
f 
组成的伪随机序列生成器。函数
f 
被用作一个非线性滤波函数,生成
器被称为非线性滤波生成器。密钥流通过应用非线性函数到LFSR的128个段(也称级)中


序列密码分析方法

的127 个内容来产生。LFSR 每被钟控一次,输出1b 。

Toyocrypt密钥流生成器有两个128b 密钥,即一个固定密钥和一个流密钥。固定密钥
由LFSR 的特征多项式(特征多项式与反馈多项式为互反多项式)的系数组成,将这个特征
多项式选为F2上的本原多项式,大约有2120 个这样的多项式。流密钥被用于形成LFSR 的
初始状态,是一个非零的128b 随机串,大约有2128-1个可能的流密钥。因此,有效的密钥
长度是248b 。
d(0,t), 

设LFSR 的输出序列为d={t)}∞=LFSR 的128 个段的内容在时刻
t 
为x0(
x1(x127(则d(=t-t≥1 。将输入到滤波函数
f 
的序列表示为
X 
=

t),…,t), t)x0(1),(t) {X(∞0, t)x0(x1(t),t)没有作为
f 
的

t)}这里X(=(t),t),…,t))。注意,
输入。非(t) 线性滤波生成器的输出序列是密钥流z={t)}∞ 这里z(t)),
布尔函数
f 
的代数正规型表示如下: 
z(t=0, t)=f(X(t≥0 。

=x125(x127(x126(

f(x0,x1,…,x125,x127)=x127+x24x63+x41x64+x27x65+x32x66+x35x67+x50x68+ 

x8x69+x18x70+x1x71+x36x72+x53x73+x26x74+x3x75+ 

x7x76+x11x77+x6x78+x62x79+x37x80+ 

x31x81+x12x82+x9x83+x34x84+x51x85+x61x86+ 

x25x87+x23x88+x45x89+x14x90+x0x91+x20x92+ 

x46x93+x38x94+x40x95+x13x96+x28x97+x2x98+ 

x49x99+x54x100+x5x101+x60x102+x47x103+x4x104+ 

x16x105+x52x106+x59x107+x55x108+x10x109+x57x110+ 

x22x111+x15x112+x56x113+x48x114+x29x115+x44x116+ 

x39x117+x58x118+x17x119+x43x120+x19x121+ 

x21x122+x42x123+x33x124+x30x125+ 

x10x23x32x42+x1x2x9x12x18x20x23x25x26 

x28x33x38x41x42x51x53x59+x0x1…x62 

2.Toyocrypt的代数分析过程
在Toyocrypt中,有一个128b 的LFSR,这样n=128 。布尔函数具有如下形式: 
62 

s1,…,

f(s0,s127)=s127+ 
Σsisαi 
+s10s23s32s42+ 

i=0

62 

s1s2s9s12s18s20s23s25s26s28s33s38s41s42s51s53s59+ 
Πsi 

=

这里{α1,…是集合{62,64,…,的某一置换。这个系统容易受使用(i) 低(0) 阶逼近的

α0,α62} 125} 
攻击,只有一个次数为17 的单项式和一个次数为63 的单项式,高阶单项式几乎总是0。文
献[5]在情形S2 下给出了一个攻击,
f 
由一个次数为4的多变量函数以1-2-17 的概率逼
近,攻击运行在292 个CPU 时钟周期内。下面在情形S3 或S4 下介绍对Toyocrypt的一个
新的代数分析方法。

首先遇到的问题是如何找到一个函数
g 
使得fg 
具有低次数。一种方法是分解多变量
多项式f。考虑
f 
的高次项,不管低次项,看看这些高次项是否有共同的低次数因子g' 
,则
对F2 上的多项式,我们观察到f(g(其中g(=gs)1具有低次数。另一种方法

s)s), s)'(


第
5 
章　代数分析方法

将在5.3节和5.4节介绍。

1.1.
在Toyocrypt的情况下,我们观察到
f 
中的次数为4、17 和63 的项有共同因子s23s42 。
对每个密钥流比特bt, s)b并在两边同乘以g(=23-1。得到f(s23

从等式f(=开始, s)ss)
f((1)。等式左边在f 中被(t) 剩下的多项式是一个次数

s)=bts23-s23 整除的单项式已消失, 
为3的等式且以概率1相等。对s42 使用相同的技巧,即设g(1。这样就得到情形

s)=s42S3 下的一个简单的线性攻击。对每个密钥流比特,获得两个次数为3的关于si 
的方程,这
样也就获得了两个次数为3的关于ki 
的方程。一旦
R 
>T,就可使用线性方法,并且有
T=C318.4个单项式。有R=m, T/2≈217.对

128≈22并且有m=4个密钥流将是充分的。这样, 
Toyocrypt的新的攻击需要7/64·Tlog27=249 个CPU 时钟周期,需要16GB 的存储空间和
大约20KB 的非连续的密钥流。

通过实验模拟可发现,上述攻击过程中的线性依赖的方程的个数是可忽略的,因此,这
个攻击可恢复密钥。

5..II18的代数分析

13 
LL-2

从原理上说,前面设计的代数分析只适用于规则地钟控的序列密码或以一个已知的方
式钟控的序列密码。然而,在一些情况下,这个难点能被消除。LILI-128 就是这种情况, 
LILI-128 是一个提交到欧洲NESSIE 工程的算法。

1.LILI-128 

LILI-1.

128 密钥流生成器的结构如图5.1所示。它由两个二元LFSR和LFSRd 以及
生成一个伪随机二元密钥流序列的两个函数fc 和fd 组成。在初始化阶段,1(c) 28 比特密钥
为LFSR和LFSRd 提供了初始状态。基于它们完成的功能,生成器能被分成两个子系统: 
钟控子系统(c) 和数据生成子系统。钟控子系统产生一个用于控制数据生成子系统的整数序
列。LFSRc 的反馈多项式被选择为一个本原多项式,定义为

Gc(x)=1+x2+x14+x15+x17+x31+x33+x35+x39 

函数fc 取两个比特作为输入并产生一个整数ck 
∈{1,2,3,4}。ck 
的值计算如下: 

k 
=fc(y1,y2)=2y1+y2+1,
k 
≥1 
这里变量y1、应于(c) c i+13 si≥0), 中的+

y2 分别对LFSR的抽头位置s、i+21(需要注意的是fc 
是普通加法,其他+是模2加。


图5.1 
LILI128 
密钥流生成器的结构

1.-

LFSRd 由ck 
钟控每次运动至少一拍,至多4拍。LFSRd 的反馈多项式被选择为如下
的本原多项式: 


序列密码分析方法

Gd(x)=1+x+x39+x42+x53+x55+x80+x83+x89 

LFSRd 的10 个不同段的内容被作为一个非线性滤波函数fd 的输入。非线性滤波函数fd 
的输出zk 
是密钥流序列。fd 定义为

fd=x2+x3+x4+x5+x1x9+x1x8+x2x8+x3x9+x4x10+x6x7+x6x10+ 
x2x9x10+x3x9x10+x4x9x10+x5x9x10+x3x8x10+x4x8x10+x6x7x10+ 
x5x7x10+x4x7x10+x6x8x9+x3x8x9+x6x7x9+x4x7x9+x3x7x9+ 
x6x8x9x10+x4x8x9x10+x3x8x9x10+x1x8x9x10+x6x7x9x10+x4x7x9x10+ 
x2x7x9x10+x5x7x8x10+x3x7x8x10+x4x7x8x9+x2x7x8x9+x5x6x7x9+ 
x4x6x7x9+x3x7x8x9x10+x4x6x7x8x9+x4x6x7x9x10+x4x7x8x9x10+ 
x5x6x7x8x9+x5x6x7x9x10+x4x6x7x8x9x10+x5x6x7x8x9x10 

这里变量x1~x10 分别对应于LFSRd 的抽头位置si、si+1 、si+3 、si+7 、si+12 、si+20 、si+30 、si+44 、

、i≥0 )。
设LFSRc 的段由u0,u1,…,u37 从左到右标记。在每个时刻,用下列公式计算反馈
比特: 

si+65 si+80(

w 
=u37+u25+u24+u22+u8+u6+u4+u0 

设LFSR左移,。连续地循环,将产生一个线性伪随机序列。

c u38=
w 
LFSR
s1,…
,


设LFSRd 的段由s0,s88 从左到右标(c) 记。在时刻k,反馈比特由下列公式计算: 
w 
=s88+s50+s47+s36+s34+s9+s6+s0 

设LFSRd 左移,。根据上述循环,LFSRd 将产生一个线性伪随机序列。

u89=
w 

2. 消除第一个组件
LILI-128 是由两个基于LFSR 的组件组成的序列密码,第一个组件被用于钟控第二个
组件。有两种策略可绕过第一个组件。
策略A:因为第一个组件的密钥长度仅是39b,可以猜测这39b 并单独地攻击第二个组
件。在LILI-128 中,第一个组件提供给第二个组件的时钟为1、2、3或4。给定第一个组件
的状态,访问第二个组件中若干已知位置的非连续密钥流比特。攻击的复杂度是239 的
倍数。
13]

策略B:给定更多的密钥流比特,有可能避免重复整个攻击239 次。对此,使用文献[
中的引理1:在对LILI-128 的第一个LFSR 钟控239-1次后,第二个LFSR 恰好向前推进
Δd=5·238-1次。这样,就不是猜测时钟控制的子系统的状态,而是在一个时刻钟控它
239-1次,并应用任何XL 攻击,忽略第一个生成器的存在。

在上述两种情况下,攻击者访问的是第二个组件的密钥流中一些已知位置的比特,而不
是自己选择位置的比特。可直接将第二个组件当作一个单独的滤波生成器,应用情形S1 至
情形S4 的所有代数分析。

中间策略A-B:LILI-128 的第一个组件的周期不是一个素数,并且有239-1=7·79· 
121369·8191 。这暗示着人们能设计一个抽取攻击,对于一个适当的t,令生成器每次运行
t 
拍,可模拟一个较小的LFSR,详细讨论可参阅文献[14 ]。可给出一个在A和B之间的中
间攻击,密钥流需求和攻击复杂度都是某个量的倍数,都小于239 。

上面和文献[15]中都将LILI-128 中的输出函数记为fd,为了方便起见,下面将其记


第
5 
章　代数分析方法

159
为f。

3. 对LILI-128 的第一个攻击
现在讨论在情形S1 和S2 下对LILI-128 的攻击。在情形S1 下,攻击是可能的,此时
629.29.
d=6,0,则有T=C2个单项式。为了使得R>T, 2。可给出一

ε=R=m, 89≈2取
m 
≈2
个大约在239·7/64·Tlog27≈2118<2128 个CPU 时钟周期内的攻击。给定使用的布尔函数, 
不适合将这个攻击扩展到情形S2 下,因为对给定的ε>2-6,没有次数小于6的好的逼近, 
低次数的多项式与要逼近的函数的距离比较大。然而,可以用策略B改进这个攻击。改进
的攻击不是猜测钟控子系统的状态,而是在一个时刻钟控它239-1次,并应用上述简单的
线性化S1 型攻击,ε=0,而可忽略第一个生成器的存在。现在的复杂度仅是7/16·Tlog27≈ 
279,但需要更多的密钥流比特,即268b而不是229b。

4. 对LILI-128 较好的攻击
先使用前面提到的分解多变量多项式的观点对LILI-128 进行分析。考虑
f 
的次数为
5和6的部分,它可被分解成如下形式: 

x7x9(x3x8x10+x4x6x8+x4x6x10+x4x8x10+x5x6x8+x5x6x10+ 

x4x6x8x10+x5x6x8x10) 
这意味着当
f 
乘以x7+1 或x9+1 时,得到的多项式的次数从6+1=7降到4+1=5。然
后,分别考虑多项式f(x)(x7+1)和f(x)(x9+1)中次数为5和4的部分的分解。只有第
二个函数的相应部分仍然能被分解并可分解为如下形式: 

x10(x3x7x8x9+x5x7x8x9+x3x7x8+x3x8x9+x4x7x9+x4x8x9+ 
x5x7x8+x5x7x9+x6x7x9) 
由此可推断出显著的事实:f(x)(x9+1)(x10+1)的次数是4而不是8。
为了找到使得fg 
具有低次数的线性独立的
g 
的个数,我们寻找下列多项式集合的线
性依赖性(在
g 
的最大次数和fg 
的某一最大次数终止): 
{f(f(x1,x)f(x1x2,…;x1,x1x2,…} 

x),x)f(x2,…,x)1,x2,…,
我们注意到最大次数不可能高于10,因为仅有10 个变量。表5.1给出了fg≠0 的相关模

1.
拟结果,并与
g 
的次数相同的随机布尔函数进行了比较。通过计算和测试可知
f(x)x8x10=x8x10(x2x9+x3x7+x4x7+x5x9+x1+x4+x5+x6) 

表5.1 
使得fg 
具有低次数的线性独立的
g 
的个数的模拟结果

1.
函数LILI-128 的
f 
随机布尔函数
g 
的次数10 1 2 3 4 10 10 1 2 3 4 10 
fg 
的次数3 4 4 4 4 4 3 4 4 4 4 4 
g 
的个数0 0 4 8 14 14 0 0 0 0 0 0 

我们看到,LILI-128 的函数
f 
与随机布尔函数相比性质很弱。这表明LILI-128 的设
计不足以抵抗代数分析。事实上,在LILI-128 中,也存在次数为4的多项式使得fg=0。
给定
m 
个密钥流比特,可获得LILI-128 的次数为4的14m 
个关于密钥流比特ki 
的多
变量方程。我们将不得不解决一个次数为4的超定多变量方程组,这个方程组是真的概率


序列密码分析方法

为1,可由线性化方法来完成。对应于上述两种策略(即策略A和B)有两种攻击形式。
在攻击形式A中,第一个生成器的状态被猜测并且复杂度是239 的倍数。对每个密钥

421 

流比特,我们获得14 个次数为4的关于kj 
的方程。为了线性化,有T=C89≈2个单项式, 
并且为了使R>T,需要m=T/14≈218 个密钥流比特。对LILI-128 的这个攻击需要239· 
7·Tlog27/64≈296 个CPU 时钟周期。只要允许访问在一些已知位置的
m 
个密钥流比特,这
一攻击形式就有效。

在攻击形式B中,在某个时刻第一部分被钟控239-1个时钟周期,密钥流比特的数量

是239 的倍数。有同样的T=C421,复杂度是257 

89≈2个时钟周期。这种攻击需要762GB 的
存储空间和257 个连续的密钥流比特,或者只需要在形式为α+β(239-1)( 对一个固定的α) 
的一些位置的218 个密钥流比特。一旦第二个LFSR 在时刻
α 
的状态被恢复,则第一个
LFSR 的状态在239 次尝试内能被很快地找到。这不是对LILI-128 的最好的已知攻击,文
献[13]中的分析结果表明,LILI-128 可用246 个密钥流比特、245 个89b 字的查表和大约等效
于248 个DES 操作的计算努力破译。然而,攻击形式B更具有一般性。

5..使用LFSR 
比特的一个子集对序列密码的一般攻击

14 

本节将说明当只使用状态比特的一个小子集时,由线性反馈和一个无状态的高度非线
性滤波函数组成的生成器是不安全的。考虑一个具有
n 
个状态比特的序列密码,并且只使
用
k 
个状态比特的小子集来推导密钥流比特。这样,就有{x1,x2,…,xk 
}.{s1,…, 

s0,
sn-1}, 这里假定
k 
是一个小常数,
n 
是一个安全参数。例如,对LILI-128 的第二个部分, 
k=10,89 。

n=

这里将在情形S3 下进行一个攻击。寻找低次数多项式g≠0 使得fg 
也具有低次数。
为了达到这一目标,检查定义在下列的多项式集C=
A 
∪
B 
上的线性依赖性。首先考虑次
数不大于
d 
的所有可能的单项式(这一部分将构成fg), 记为A={1,x1,x2,…,x1x2,…}。
然后考虑次数不大于
d 
的
f 
的所有乘以单项式的倍式(这一次数对应
g 
的次数), 记为B= 
{f(f(x1,x)f(x1x2,…}。

x),x)f(x2,…,x)

设C=A∪B。A、B、
C 
中的所有元素可被视作xi 
的多变量多项式,因此需要用xi 
的
表达式代替f。具有
k 
个变量的多变量多项式集合的维数不能大于2k 
。如果在这个集合中
的元素多于2k 
个,则线性依赖性必将存在。这种组合允许找到一个函数
g 
使得fg 
具有比
f 
低的次数。更精确地,有如下的低次数关系定理。

定理5.设f:Fkk/2 
则有一个次数至多为

1.2→F2 是任意一个布尔函数, 
的布尔函
数g≠0,使得
1 
fg 
的次数至多为
k/2 =ΣCk

证明:如果
A 
中包括所有次数直到
。
i=0 
k/2 

的单项式,则|A|
k/2 
i 
。类似地,如果
B 

k/2 

中包括所有次数直到

的单项式与
f 
的积,则|B|=ΣCik。所以|C|=|A|+|B|=

k/2 

i=
0
k/
2


k/2

k/2CikCikk/2CikCk-ik>Cik=2k 
,而C=A∪
B 
的个数不能超过2k 
,这样就必

Σ +Σ =Σ +ΣΣ

i=0i=0i=0i=0i=
k0

然存在一定的线性依赖性。因为在集
C 
中的
A 
部分没有线性依赖性,所以g≠0 。
由定理5.1可知,对于任何基于线性反馈的非线性滤波序列密码,如果非线性滤波使

1.

第
5 
章　代数分析方法

用
k 
个变量,则在
n 
个密钥流比特中,可以至少产生一个次数约为k/2的方程。这些方程
通常可由线性化方法来解决。为了获得一个完全饱和的可通过线性化方法求解的方程组, 

k/2 

需要至多Σik/2个密钥流比特。再者,如果对一个给定的f,在
C 
中有一定的线性依

Cn 
≈Cn
i=
0


赖性,则可以使用一些线性独立的g,并对于每个密钥流比特将获得相应个数的方程。因
而,密钥流长度要求必须被整除,例如前面介绍的例子可被14 整除。
ε=

综上所述,可得到如下的对任意
k 
个输入的布尔函数的一般化攻击:d=k/2,0,数
据量为Ck/2, Ck/2)复杂度为(Ck/2 
ω 
。这个攻击可处理最坏的情况。而具体密

存储量为(2, )
-k=.1,码使用的函(n) 数有可能具有更(n) 低的安全性。例(n) 如,在LILI128 中,10,严格应用定理51.
最坏情况下的复杂度是O(对任意的布尔函数)。而在文献[的扩展版本中证明其平

n6ω 
)( 2] 
均复杂度是O(n5ω 
)( 对一个随机布尔函数)。对于使用在LILI-128 中的具体函数,前面介
绍的攻击的复杂度是O(

n4ω 
)。

如果
k 
是固定的,那么这个攻击是多项式的。如果k=O(n), 这个攻击关于
n 
仅是指
数的。使用在一个滤波函数中的比特数不会小。在实际中,谈论多项式或非多项式时间容
易引起误解并且总是用具体的结果来控制。假定知道滤波函数的最大次数不能超过k,则
可看到在情形S1 下,基于线性反馈的任何序列密码都能通过简单的线性化方法被破译,需
要给定Cn 
个密钥流比特,Cn 
)这个简单的攻击方法是

k 
[
复杂度大约为(kω 
。如果
k 
是固定的,
)

多项式的15]。许多以这种方式设计的序列密码的复杂度大约为(Cknω 
≈280 。实际中,攻击

的复杂度(Ck/2 
ω 
大约是(
k 
)80 的平方根, 40 。

n 
)Cnω 
≈2所以破译所有这些密码的复杂度大约是2

5..应对代数分析方法的措施

15 

由定理5.1可得出如下实现最优抵抗代数分析的要求:当集合
A 
和
B 
被生成直到任

1.
何严格地小于依赖性一定存在的次数时,确保没有线性依赖性存在。这可归结为如下的
准则。
1.k/2,则集合C=

最优抵抗准则5.1 
当集合
A 
和
B 
被生成直到关于xi 
的次数为
A∪
B 
的个数是最大的。
易知,这个准则暗含着要阻止情形S1 的攻击形式,
f 
的次数将是充分大的。然而,这个
要求不能保证情形S2 或S4 的攻击不存在[5]。
综合前面的分析结果可以看出,具有下列情况之一的滤波生成器都可用代数分析方法

来攻击: 

(1)
f 
使用一个小的状态比特子集,例如LILI-128 中使用的是10b 的子集。

(2)
f 
是很稀疏的,如Toyocrypt中使用的函数。

(3)能从
f 
中分解出一个低次数因子,如Toyocrypt中使用的函数。
(4)能用上述情况之一来逼近f。
(5)
f 
的高次数部分是上述情况之一。
从上述情况可以得出以下结论。首先,在滤波生成器中,滤波函数应使用许多状态比特
(如至少32b)并且不是太稀疏的,所以它也有许多很高次数的项(如至少32 项)。其次,高
次数部分不具有低次数因子,并且它本身也使用了许多状态比特。最后,高次数部分的近似
逼近同样不能具有低次数因子,或者只使用了一小部分状态比特。从LILI-128 中可以看