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

１３０

应用科学学报

２２卷

分析密码系统无疑是大有帮助的．比如ＢＡＡ¨。攻击

需要有一定量的密钥，尤其是当系统中的各个ＬＦ—

ＳＲ级数增大时，密钥量需求随之增加，此时如果辅

以本文的差分分析方法，则可以保证密钥量的需求，

提高攻击成功的概率．

３．２攻击实例

为了更好地说明问题，下面举一个例子进行分析，主要目的是让大家对差分分析在序列密码分析中的应用有个感性的认识．这个例子是文献［７］中设计的一个密钥流序列．其方法是这样的：当用规级线性反馈移位寄存器的≠（２”～１）／，ｚ种不同反馈组合中的某种反馈组合和某种初始状态产生的ｍ序列达到一个周期时，通过另一个伪随机序列（可以是ｍ序列）控制选择另一种反馈组合，并且将先前各级移位寄存器的末态作为产生新的ｍ序列的各级移位寄存器的初态；当该ｍ序列输出为一个周期时，又以此时各级移位寄存器的末态作为下一个具有不同反馈组合的以级线性反馈移位寄存器的初态，进入下一个ｍ序列；如此循环，即可通过改变卵级线性反馈移位寄存器的反馈结构和改变各级移位寄存器的初值，产生周期非常长的伪随机序列．为方便起见，下面给出文献［７］中的新序列构成框图（如图

示）：

图密钥流生成器

Ｆｉｇ．

Ｋｅｙｓｔｒｅａｍ

ｓｅｑｕｅｎｃｅ

ｇｅｎｅｒａｔｏｒ

仍旧延用文献［７］中的两个优序列，其中

ｆｌ（ｚ）一ｚ７＋ｚ＋１，初态为１１１１１１１；ｆ２（ｚ）一ｚ７＋ｚ３＋１，初态为００００００１．设控制序列也为ｍ序列，ｇ（ｚ）一ｚ２＋ｚ＋１，初态为０１．

由文献［７］中的结论，图中产生的密钥流序列的

周期Ｔ一（２２—１）（２７—１）一３８１．以下即为一个周期

的密钥流序列，记为Ｋ：

００００００１０００００１１００００１０１０００１１１１００１０００１０１１００１１１０１０１００１１１１１０１００００１１１０００１００１００１１０１１０１０１１０１１１１０

万　

方数据１１０００１１０１００１０１１１０１１１００１１００１０１０１０１１１１１１１００００００１０００００１１００００１０１０００１１１１００１０００１０１１００１１１０１０１００１１１１１０１００００１１１０００１００１００１１０１１０１０１１０１１１１０１１０００１１０１００１０１１１０１１１００１１００１０１０１０１１１１１１１００００１１１０１１１１００１０１１００１００１００００００１０００１００１１０００１０１１１０１０１１０１１０００００１１００１１０１０１００１１１００１１１１０１１０１００００１０１０１０１１１１１０１００１０１０００１１０１１１０００１１１１１１１

现在不妨假设明文Ｐ为

０００００００００００００００１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００００１１００１１００１１００１１００１１００１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０１０

则密文Ｃ为

００００００１０００００１１０ｌＯｌｌｌｌｌ０１１０１００１１１０１１１１００１１０１１１１１１００１０１００１００００１１１０００１００１００１１０１１０１０１１０１１１１０１１０００１１０１００１０１１１０１１１００１１００１０１０１０１１１１１１１１１００１１１０１１００００００１１１０００１００１０１１０００１００００１１００１００００００１１０１０１１１１０１００１００１０００１１１００１１１０００００１１１０１０００１１０１１００００１１１１０１１１０１１００１１００００００００１０１０１００１０１１０１１１０１００１１１１００１１１０００１０１０１１１０１１１００１１０１１１１０１１１１１０００１１０１０１１００１１００００００１１０１１００１０１１１００００１０１１１１１１１１０１０１１１１０００００１００１１１０１１０１１０１０１０１

现在暂且不讨论其他情况下的攻击，只考虑唯密文攻击．对于密文序列Ｃ，我们先把它按ｆ。（ｚ）的周期１２７划分为３组子序列，分别设为ａ，ｂ，Ｃ．对这三组子序列分别进行移位差分，得到第一类差分序

列，设为△口，△６，△ｆ．然后用Ｂ—Ｍ（Ｂｅｒｌｅｋａｍｐ—

Ｍａｓｓｅｙ）算法分别求序列△口，△６，△ｆ的极小多项式，具体算法如下：

Ｓｔｅｐｌ把第一类差分序列分成１２７—２ｎ＋１（咒一７）个截断序列，对每个截断序列用Ｂ—Ｍ算法求出

其反馈多项式．

Ｓｔｅｐ２统计所有截断序列的反馈多项式出现的次数，找出出现次数最多的那个反馈多项式．

ＳｔｅｐＳ

用ｓｔｅｐ２中找出的反馈多项式生成一

条序列，与第一类差分序列进行符合．若符合率较高（比如大于６０％），则我们可以基本判断该反馈多项式即为所求．