胡建勇，张文政，董新锋

(保密通信重点实验室，四川 成都 610041)



序列低频重乘积关系计算算法的研究*

胡建勇，张文政，董新锋

(保密通信重点实验室，四川 成都 610041)

摘要：针对周期序列实现有效的离散傅里叶频谱攻击，前提条件是寻找到序列的一对低频重乘积关系。基于低频重乘积关系如何计算的问题，在时域上提出了通常的低频重乘积关系计算算法。为了减少计算算法的遍历复杂性，利用序列的频域特性和迹表示，在频域上提出了更加有效的低频重乘积关系计算算法。最后，针对频域上的低频重乘积关系计算算法，分别利用迹函数的乘积关系以及满足乘积关系序列在频域上的等价条件，给出了关于乘积序列迹表示的两种适用计算方法。

关键词：频谱攻击；低频重；乘积关系；频域特性；迹表示

0引言

离散傅里叶频谱攻击[1-3]是针对周期序列的一类代数攻击[4-9]，其在频域上建立起以参照序列与输出序列时间间隔为未知量的方程并求解，最后恢复出密钥或者计算出输出序列的后续比特。离散傅里叶频谱攻击的有效实现严重依赖于序列低频重乘积关系[1,2,10]的计算。当已知的输出序列比特数小于该序列的线性复杂度时，对周期序列进行离散傅里叶频谱攻击的先决条件，是寻找到该周期序列的一组低频重乘积关系，并且这对低频重乘积关系的线性复杂度严重影响离散傅里叶频谱攻击的数据复杂度。事实上，在给定序列a的一组低频重乘积关系b和u时，离散傅里叶频谱攻击的数据复杂度为l(b)+l(u)。……