相 关 攻 击 从 对 基 于 线 性 反 馈 移 位 寄 存 器 (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 定 理
n 个变元(也称变量)的布尔函数 f(x)是从 F2n 到 F
2
的一个函数或映射,记为
f(x): F2n→F
2
。
定义 1 设 f(x): F2n→F
2
,x=(x
1
,x
2
,…,x
n
),w=(w
1
,w
2
,…,w
n
)∈ F2n,x 和 w 的点
积定义为 w·x=w
1
x
1
+w
2
x
2
+…+w
n
x
n
∈F
2
。n 个变元的布尔函数 f(x)在点 w 的沃尔
什变换定义为
S
f
(w)=2
-n
∑x∈F2nf(x)(-1)
w ·x
。
(1)
式(1)的逆变换(又称反演公式)为
f(x)= ∑w∈F2nS
f
(w)(-1)
w ·x
。
(2)
上面各式中的求和是指实数求和,式(2)可由式(1)推导出。