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

１２８

应用科学学报

２２卷

均指异或运算．

定义３Ⅲ

设ｙ，，ｙ，。为两个粗比特串，则比特串

ｙ。，ｙ。’的差分定义为

ＡＹ，一Ｙ，ｏ

Ｙ，’＿１

其中。表示，ｚ比特串集上的一个特定群运算，ｙ，＋＿１

表示ｙ？在此群中的逆元．

定义４…设ａ，是ａ的子序列，ｂ。是６的子序列，

则

△。．，ｂ一口ｌＩ１

ｏｂＶ称为序列ａ，６关于子序列ａ，，ｂ。的截断差分，其中。表示序列集上的一个特定群运算，６ｆ１表示ｂ。在此序

列集上的一个特定群中的逆元．

定义５设“，６为两条序列，则

△¨一ｄ

ｏ

ｂ叫

称为序列“，６的差分，简称差分序列，其中。表示序列集上的一个特定群运算，ｂ“表示ｂ在此序列集上

的一个特定群中的逆元．

定义６设ａ１，ａ２，以３，．“，ａ。…，为二元域上的一条序列，对其作如下运算

ａＩ，ａｌ

ｏ

ａ２，ａ２

ｏａ

３＇．”，ａ州ｏ

ａ。，…，

则称此运算为移位差分，所生成的序列称为第一类

差分序列．

定义７设ａｌ，ａ：，Ⅱ３，．一，以。…，为二元域上的一条序列，对其作如下运算

ａｌ，￡／１０“２，ｎｌｏｎ２０盘３．．一炳ｏ…ｏｎＨ①口∥一，则称此运算为累次差分，所生成的序列称为第二类

差分序列．

２差分序列的若干性质

在讨论差分序列的性质之前，先给出一些需要

用到的引理．

引理ｌ［５］设，ｚ级ＬＦＳＲ的特征多项式为厂（ｚ）一，２７”＋ｆｌｚ一１＋…＋ｆ。（ｆ。≠０），则ＬＦＳＲ以（以ｏ，ａｌ，…，ａ，。）为初态产生的ｑ元序列的母函数表示为：

Ａ（ｚ）一—掣兰｝，其中而为ＬＦＳＲ的联结多项

ＪＬｚ）

式，而ｇ（ｚ）一６０＋６１ｚ＋…＋ｂ—ｌｚ一１由初态（日。，ａ１，…，ａ，，）和反馈系数（ｆ。，…，Ｃ。）给出．

厂一两两互素，则每个有理真分式万石‰均可

引理２口］设ｆ。（ｚ），…，厂。（ｚ）ＥＦ。Ｉｘ］，ｆ１’．一，

万　

方数据唯一表示成若干个真分式之和：万石‰一

鱼玉兰）Ｌ…土兰！！兰！

ｆ，（ｚ）‘

‘＾（ｚ）。

引理３‘５１设ｓＦ，…，ｓＦ为ＧＦ（ｑ）上的ｋ条周期

序列，且“（ｚ）／六。（ｚ），…儿＊（丁）／Ａ＊（Ｔ）分别为它们的生成函数的既约有理分式表示．再设ｔ“１一

芝：ｓ？’为这ｋ条序列的和序列．令：ｇ（Ｔ）一

＾

｛

＞？＾，（ｚ）Ｈｉ。（ｚ），ｆ（ｘ）一ｌ－Ｉｆ．。，（ｚ），则有—ｊ＝—ｌ

。＃Ｊ

５１

（１）六（Ｔ）一厂（ｚ）／ｇｃｄ（／’（ｚ），ｇ（ｚ））；

（２）ｐｅｒ（ｆ“’）一ｏｒｄ（厂（ｚ）／ｇｃｄ（厂（ｚ），ｇ（ｚ）））≤

ｌｃｍ［ｐｅｒ（５７’），…，ｐｅｒ（ｓ；’）］，其中等号在六ｌ（Ｔ），…，

＾；（Ｔ）两两互素时成立；

（３）Ｌ（ｆ～）≤≥：Ｌ（ｓＴ’），当且仅当六。（ｚ），…，＾（Ｔ）两两互素时等号成立．

引理４［６３

设Ｆ。为一特征为Ｐ的有限域，厂∈

Ｆ。Ｉｘ］是一个次数大于０且厂（ｏ）≠０的多项式．设厂

一以一一 乃为厂在Ｆ。Ｉｘ］中的标准分解式，其中“Ｅ

Ｆ。，ｂ１＇．“，ｂ。ＥＮ，且厂１，．一，＾是Ｆ。ｋ］中两两不同的

首一不可约多项式．则ｏｒｄ（厂）一ｅｐ７，其中Ｐ—ｌｃｍ（ｏｒｄ（／１），…，ｏｒｄ（＾）），ｔ是满足户‘≥ｍａｘ（６ｌ，…，ｂ。）的最小整数．

２．１第一类差分序列的性质

定理１

设ａ是周期为丁的二元序列，ｆ（ｘ）是

其极小联接多项式，序列６为日的第一类差分序列．如

果（１＋ｚ）ｌｆ（ｚ），则ｂ的极小联接多项式为

厂（ｚ）／（１＋ｚ），周期和线性复杂度不增；否则，６的极小联接多项式为厂（ｚ），周期和线性复杂度不变．

证明

由引理１，ａ的母函数可表示为：Ａ（ｚ）一

甓詈．设以一。一ｏ，则垒的母函数可表示为

Ｂ（Ｔ）一∑（叭。＋ｎ，）ｚ（１州舭）一警

５一（１＋Ｔ）∑哪’一

若（１＋Ｔ）Ｉ厂（ｚ），设厂（Ｔ）一（１＋Ｔ）厂，（ｚ），此时

有：Ｂ（ｚ）一芳暑．因此由母函数的表示知垒的极小

联结多项式为ｆ。（ｚ），再由引理２～４知周期和线性

复杂度不增．

否则的话，由母函数的表达式知垒的极小联接多