冯登国

(中国科学院 软件研究所，北京 100190)

相关攻击从对基于线性反馈移位寄存器(Linear Feedback Shift Register，LFSR)的序列密码的分析起步，最早是由BLASER等人[1]提出的。真正有价值的工作是由SIEGENTHALER[2]提出的非线性组合生成器的分别征服相关攻击，其基本思想是利用组合函数的输出与输入分量或者某些输入分量子集之和的相关性，穷搜索某个特定LFSR的初始状态或者某几个LFSR 的初始状态，而各个LFSR 的初始状态就是非线性组合生成器的子密钥，这就是最早的相关攻击。“分别征服(divide-and-conquer)”起名于一种图论算法，体现了“分而治之”的思想，意为将一个待求解的问题分成许多子问题，然后对每个子问题求解，最后再综合求解。为了对抗这种相关攻击方法，SIEGENTHALER提出了布尔函数的相关免疫的概念[3]，用于度量和刻画非线性组合序列密码抵抗分别征服相关攻击的能力。相关免疫布尔函数是一类重要的密码函数，其频谱特征刻画是构造和分析这类函数的理论基础。肖国镇(G.Z.Xiao)教授和梅西(J.L.Massey)教授于1988年给出了相关免疫布尔函数的沃尔什(Walsh)频谱特征刻画[4]，这一工作被国内外学者称之为Xiao-Massey定理。关于相关免疫函数更多的进展可参阅文献[5-6]及其参考文献。

首先回顾了Xiao-Massey定理，其次简述了Xiao-Massey定理的意义，然后阐释了Xiao-Massey定理的作用，最后总结了全文。

1 Xiao-Massey定理

(1)

式(1)的逆变换(又称反演公式)为

(2)

上面各式中的求和是指实数求和，式(2)可由式(1)推导出。

计算沃尔什变换有快速算法[5]，称之为快速沃尔什变换，其时间和存储复杂度分别为O(n2n)和O(2n)。……