一种优化的CJS型快速相关攻击算法

刘好莉++任义++杨晗

摘 要快速相关攻击是序列密码的重要分析方法，本文提出了一种基于CJS型算法的优化算法，利用线性分组码的译码方法来解决流密码的攻击问题，通过寻找校验等式对，构造子线性分组码，该码维数较小，译码速度提高。采用ML-译码算法对子码进行译码，通过对LFSR的状态进行分割，独立实施ML-译码，可最终获得序列的初始状态，该算法显著降低了算法中的译码复杂度。

【关键词】快速相关攻击 序列密码 奇偶校验码 分段译码

1 引言

快速相关攻击核心思想是利用非线性组合生成器的输入和输出的相关性，并且将LFSR的初始状态的恢复问题转化为纠错码的译码问题。文献[1]提出算法A和算法B只适于与抽头数较少的情况，抽头数较少时（t<10）算法攻击效果很好，而当抽头数较大（t>10）时，其算法复杂度趋近于无穷，此时其攻击并不是很有效。文献[2]提出的CJS型算法与截取长度N和子码信息长度k有关，而与抽头数t无关。与文献[1]相比，文献[2]的算法不受制于反馈多项式抽头数的限制。但是算法的缺点在于查找校验等式对的复杂度为0（NlogN），从而限制译码器输出。本文给出一种基于文献[2]的改进算法，对查找校验等式对的算法部分进行优化，显著降低文献[2]中算法的计算复杂度和译码复杂度。

2 问题描述

典型的二元加法序列密码由n个线性反馈移位寄存器序列通过一个非线性组合生成器生成密钥流{zi}，明文序列与密钥序列逐位模2加能够得到密文序列{ci}。移位寄存器的反馈多项式是已知的，各个移位寄存器的初始状态为密码的密钥。相关攻击认为各个移位寄存器序列与密钥序列存在一定的相关性。利用这一性质，可以逐个攻击各个寄存器的初始状态，从而最终破解该密码。

已知条件：反馈多项式为f（x），阶数为L=60。CJS算法是利用已知组合生成器生成序列的截短序列构成[N，L]线性分组码C，通过LFSR的生成矩阵G的列向量L，构造出一个维数比较小的线性分组码[n2，k]（k0.5，i=1，2，...，N.（p接近0.5）这样序列z可以看成是序列 a通过一个误码率为1-p的二元对称信（BSC）后的输出，而寄存器的初态攻击问题也就转化为线性分组码的译码问题。译码时采用最大似然译码算法进行恢复，通过对LFSR的状态进行分割，分别独立实施ML-译码。

3 基于CJS算法的快速相关攻击算法

3.1 算法描述

设发送端序列为{ai}，接收端序列为{zi}，根据LFSR的特征多项式，得到（N-L）*N校验矩阵H。生成矩阵和校验矩阵是正交的，即H*GT=0。

根据gi（x）=xi-1mod f（x），i=1，2，...N，

得出线性分组码的（L*N）生成矩陣G。

（1）

假设k

（2）

构成一个[n2，k]的线性分组码C2，信息比特是（a1，a2，…ak），信息维数k，则C2的生成矩阵表示为G2=[gi1k+gj1k]；则在接收端有Z1=zi+zj（0

3.2 算法优化

在查找校验等式对时的算法改进：

建立两个数组，在第一次遍历后第一个数组中顺序放置已查找到的相同的列，另一数组中放置与已查找到的不同的列。再次遍历时便可直接从第二个数组中的第一个列数开始，以此类推。遍历完毕后，可直接从第一个数组中显示查找到的等式对，大大降低了原算法的复杂度。

4 相关数学问题的算法实现

通过理论部分对本题题意以及算法的分析，得到如下解题步骤：

Ⅰ.数据：已知LFSR的级数L=60，特征多项式如下：

f（x）=x60⊕x56⊕x47⊕x37⊕x35⊕x16⊕x9⊕x3⊕1

Ⅱ.预计算：将k置为一固定值且k

Ⅲ.译码：输入数据作为接收序列（z1，z2，...zN）。

Step 1：计算子序列（）

Step 2：利用最大似然译码算法使生成矩阵G2对线性分组码C2译码，对C2的2k个码字进行穷举搜索从中选择相关概率较高的信息比特（a1，a2，...，ak），接下来做类似处理便可以得到LFSR的初始状态（此处所用的方法为分段译码）。

5 结束语

本文对文献[2]提出的CJS型快速相关攻击算法进行改进，利用线性分组码的译码方法来解决流密码的攻击问题，通过寻找校验等式对，并采用ML-译码算法对子码进行译码，最终获得序列的初始状态。通过优化寻找校验等式对的计算复杂度，大幅度降低了算法的译码复杂度。

参考文献

[1]Meier W.and Staffelbach O.：Fast correlation attacks on certain stream ciphers， Journal of Cryptology，1（03），pp.159-176，1989.

[2]ChepyzhovV.V.，Johansson T.，Smeets B.：Asimplealgorithm for fastcorrelationattacks on stream ciphers.In： GoosG.，HartmanisJ.，vanLeeuwen J.， Schneier B.（eds） Fast Software Encryption， FSE 2000，Lecture Notes in Computer Science，vol.1978，181-195.Springer，Berlin，Heidelberg.

[3]李兴旺.基于LDPC码的截短线性序列快速相关攻击及其在极低信噪比通信的应用[D].电子科技大学，2010.

[4]伍文君，唐贵林，黄芝平.一种快速相关攻击算法[J].计算机工程，2009，35（17）：129-131.

作者单位

沈阳建筑大学信息学院 辽宁省沈阳市 110168