差分分析在序列密码攻击中的应用(3)

２期

李超等：差分分析在序列密码攻击中的应用

项式仍为／（Ｔ），自然周期和线性复杂度都不变．

推论ｌ

设“为”级埘序列，垒为其第一类差分

序列，则６仍为”级Ⅲ序列．２．２第二类差分序列的性质

定理２

没以是周期为了１的二元序列，其母函数

表示为：以（Ｔ）一等罱，厂’（Ｔ）是其极小联结多项式，垒

为“的第二类差分序列．如果（１ｑ－ｘ）ｌｇ（Ｔ），则垒的极小联结多项式为／（丁），周期和线性复杂度不变；否

则６的极小联结多项式为ｕ厂‘（ｚ）（１＋丁），周期和线性

复杂度不减．

证明

由定义６和定义７知

“，一ｂ，，十ｂ，，？一０，１，…，其中ｂＩ＿ｌ一０．设６的母函数为Ｂ（ｚ），则有

４（ｚ）一∑“≯’一∑（６，。＋６，）上’一（１＋丁）

＞？ｂ，。’一（１＋ｚ）Ｂ（ｚ）

故跳扣篙一而骞怎㈩

若（１ｑ－ｘ）｝譬（一），设ｇ（ｚ）一（１＋Ｔ）ｇＩ（』、），此时

Ｂ（ｚ）一等岩，由母函数的表示知垒的极小联结多项

式为、，’（、１２），周期和线性复杂度不变．

否则，由母函数的表示知ｂ的极小联结多项式为／（ｚ）（１＋丁），再由引理２～４知周期和线性复杂度不减．

定理３设“是周期为了１的，＂序列，６为其第二类差分序列，则６与“周期相同．

证明

由于“的周期为７’，故其母函数可表示为

Ａ（ｄ一器

其中ｇ（』）一（ｔｏ＋（、】』、＋…＋“㈡Ｔ丁．

由定理２的证明过程，我们可以把序列６的母函数表示为

Ｂ（ｒ）一丌苦‰（２）

由于“为ｍ序列，故有ｇ（１）一０，也即满足（１＋．７８）ｊｇ（ｘ）．再根据式（２）即知ｂ的周期仍为７１．２．３两类差分序列的相互关系

定理４

设“为二元域上的一条序列，６为其第

一类差分序列，Ｃ为６的第二类差分序列，贝，ｌｌａ和ｆ是相

同的序列．

证明

直接代入验证即得证（略）．

万　

方数据定理５设“为。－）ｇ域上的一条序列，垒为其第

二类差分序列，ｒ为６的第一类差分序列，则堕和￡是相

同的序列．

证明

直接代人验证即得证（略）．

上述两定理告诉我们两类差分序列可以相互转

化，而这是下面差分分析法的理论依据．

３分析方法与实例

在密码编码学中，人们习惯上假定密码分析者

拥有加密器和解密器，这个假设称为Ｋｅｒｃｋｈｏｆｆ假

设．这样密码的安全性依赖于密钥．而通常将一个密

码系统的攻击分为以下几种：唯密文攻击；已知明文攻击；选择明文攻击；选择密文攻击．这４种攻击类

型的强度按序递增．本文主要探讨在唯密文攻击时

差分密码分析的一些应用，并假定一般密码分析者

仅知道以下参数：足够长的密文序列；所用ＬＦＳＲ的

级数；布尔函数；明文编码及统计特性．３．１差分分析法

有了定理４和定理５，现在来考虑一下，如何从

密文中恢复明文和密钥．由于已知明文编码及统计

特性，因此可以利用这些编码规律和统计特性．为了讨论方便，以下不妨假设：

Ｐ：１

０１０１０１０１０１

０…

Ｋ：ｋｏｋｌｋ，ｅｋ３ｋ４ｋ５矗６志７ｋ８ｋ９…

（１：ＣｏＣｌ（、２（－、ｊｆ４ｆ；Ｃ６ｆ７ｆ８ｆ９…

现对（、进行移位差分，则有

ＡＣ：△（‘，一Ａｋ，ｏ

１，

？≥０

（３）

由式（３）可以知道密钥差分序列就等于密文差分取

反序列，因此要研究密钥差分序列，只需研究密文差分取反后的序列即可．当然此时还可以对△（１再移位差分一次，这样就可以完全消除明文中比特１的影响．如果此时的密文差分序列的反馈多项式和初

态能够求出，那么就可以求出整条密文差分序列．再通过密文差分序列和密钥差分序列之间的对应关

系，即可求出密钥差分序列．而上面两个定理则保证

差分后的序列可以很容易还原为原始序列，由此就

可求出原始密钥序列．至于Ｐ为其他情况，则只要运用截断差分的思想，比如采样取出序列，再进行类

似的差分，同样可以求出密钥差分序列与密文差分序列之间的对应关系，只是会稍微复杂一些．

由此可见，对密文进行差分可以消除明文的一些影响，使我们获得部分密钥序列．而这对于进一步