当前位置：首页 > news >正文

S盒的代数免疫度

news 2026/6/11 7:57:42

1. 代数免疫度

1.1 代数攻击背景

代数攻击是一种针对对称密码体制的新型攻击方法，其核心思想是：

将密码算法表示为多元多项式方程组
通过求解方程组来恢复密钥
特别适用于基于寄存器的流密码，但也对分组密码构成威胁

1.2 代数免疫度的定义

设 \(f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2\) 是一个 \(n\) 元布尔函数。

零化子：布尔函数 \(g: \mathbb{F}_2^n \rightarrow \mathbb{F}_2\) 称为 \(f\) 的零化子，如果对于所有 \(x \in \mathbb{F}_2^n\)，满足：

\[f(x) \cdot g(x) = 0 \]

代数免疫度：\(f\) 的代数免疫度 \(\text{AI}(f)\) 定义为使得 \(f\) 或 \(f \oplus 1\) 存在非零 \(d\) 次零化子的最小正整数 \(d\)。即：

\[\text{AI}(f) = \min\{ \deg(g) \mid g \neq 0, \, g \in \text{An}(f) \cup \text{An}(f \oplus 1) \} \]

其中 \(\text{An}(f) = \{ g \mid f \cdot g = 0 \}\) 是 \(f\) 的零化子集合。

2. 计算代数免疫度的方法

2.1 一般计算步骤

确定布尔函数：给定 \(f\) 的真值表或代数正规型(ANF)
建立方程组：对于次数 \(d\)，设零化子 \(g\) 的通用ANF形式
施加约束：在 \(f(x)=1\) 的点上要求 \(g(x)=0\)（对 \(f\) 的零化子）
求解线性系统：解齐次线性方程组，检查非零解的存在性
对 \(f \oplus 1\) 重复：在 \(f(x)=0\) 的点上要求 \(h(x)=0\)
找到最小次数：从 \(d=1\) 开始递增，直到找到非零零化子

2.2 线性系统的规模

对于 \(n\) 元布尔函数，\(d\) 次零化子 \(g\) 的 ANF 有 \(\sum_{i=0}^{d} \binom{n}{i}\) 个未知系数。约束条件为所有 \(f(x)=1\) 的点（假设有 \(w\) 个），产生 \(w\) 个线性方程。

3. 例题详解

3.1 例题1：线性函数

函数定义：\(f(x_1, x_2, x_3) = x_1 \oplus x_2 \oplus x_3\)

真值表：

\(x_1x_2x_3\)	\(f(x)\)
000	0
001	1
010	1
011	0
100	1
101	0
110	0
111	1

步骤1：寻找 \(f\) 的1次零化子

设 \(g(x) = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3\)

在 \(f(x)=1\) 的点上施加 \(g(x)=0\)：

(0,0,1): \(a_0 \oplus a_3 = 0\)
(0,1,0): \(a_0 \oplus a_2 = 0\)
(1,0,0): \(a_0 \oplus a_1 = 0\)
(1,1,1): \(a_0 \oplus a_1 \oplus a_2 \oplus a_3 = 0\)

解得：\(a_1 = a_0, a_2 = a_0, a_3 = a_0\)，取 \(a_0=1\) 得：

\[g(x) = 1 \oplus x_1 \oplus x_2 \oplus x_3 \]

验证：当 \(f(x)=1\) 时，\(x_1 \oplus x_2 \oplus x_3 = 1\)，故 \(g(x)=1 \oplus 1=0\)。

步骤2：寻找 \(f \oplus 1\) 的1次零化子

设 \(h(x) = b_0 \oplus b_1 x_1 \oplus b_2 x_2 \oplus b_3 x_3\)

在 \(f(x)=0\) 的点上施加 \(h(x)=0\)：

(0,0,0): \(b_0 = 0\)
(0,1,1): \(b_0 \oplus b_2 \oplus b_3 = 0\)
(1,0,1): \(b_0 \oplus b_1 \oplus b_3 = 0\)
(1,1,0): \(b_0 \oplus b_1 \oplus b_2 = 0\)

解得：\(b_0=0, b_1=b_2=b_3\)，取 \(b_1=1\) 得：

\[h(x) = x_1 \oplus x_2 \oplus x_3 \]

结论：\(\text{AI}(f) = 1\)（存在1次零化子）

3.2 例题2：非线性函数

（达到最大代数免疫度）
函数定义：\(f(x_1, x_2, x_3) = x_1 x_2 \oplus x_3\)

真值表：

\(x_1x_2x_3\)	\(f(x)\)
000	0
001	1
010	0
011	1
100	0
101	1
110	1
111	0

步骤1：检查1次零化子

对 \(f\) 的零化子 \(g(x) = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3\)：

在 \(f(x)=1\) 的点上：

(0,0,1): \(a_0 \oplus a_3 = 0\)
(0,1,1): \(a_0 \oplus a_2 \oplus a_3 = 0\)
(1,0,1): \(a_0 \oplus a_1 \oplus a_3 = 0\)
(1,1,0): \(a_0 \oplus a_1 \oplus a_2 = 0\)

解得唯一解：\(a_0 = a_1 = a_2 = a_3 = 0\)，无非零1次零化子。

对 \(f \oplus 1\) 的零化子同样无非零1次解。

步骤2：寻找2次零化子

设 \(g(x) = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \oplus a_{12} x_1 x_2 \oplus a_{13} x_1 x_3 \oplus a_{23} x_2 x_3\)

在 \(f(x)=1\) 的点上：

(0,0,1): \(a_0 \oplus a_3 = 0\)
(0,1,1): \(a_0 \oplus a_2 \oplus a_3 \oplus a_{23} = 0\)
(1,0,1): \(a_0 \oplus a_1 \oplus a_3 \oplus a_{13} = 0\)
(1,1,0): \(a_0 \oplus a_1 \oplus a_2 \oplus a_{12} = 0\)

解得：
\(a_3 = a_0, \quad a_{23} = a_2, \quad a_{13} = a_1, \quad a_{12} = a_0 \oplus a_1 \oplus a_2\)

取 \(a_0=1, a_1=0, a_2=0\)：

\[g(x) = 1 \oplus x_3 \oplus x_1 x_2 \]

验证：在 \(f(x)=1\) 的点上：

(0,0,1): \(1 \oplus 1 \oplus 0 = 0\)
(0,1,1): \(1 \oplus 1 \oplus 0 = 0\)
(1,0,1): \(1 \oplus 1 \oplus 0 = 0\)
(1,1,0): \(1 \oplus 0 \oplus 1 = 0\)

结论：\(\text{AI}(f) = 2\)，达到 \(n=3\) 时的最大可能值 \(\lceil n/2 \rceil = 2\)

4. 重要性质

4.1 代数免疫度的上界

对于 \(n\) 元布尔函数 \(f\)，其代数免疫度满足：

\[1 \leq \text{AI}(f) \leq \lceil n/2 \rceil \]

达到上界的函数称为具有最优代数免疫度。

4.2 与其他指标的关系

与非线性度的关系：
- 高代数免疫度不一定意味着高非线性度
- 但具有最优代数免疫度的函数通常具有较高的非线性度
与代数次数的关系：
- 若 \(\text{AI}(f) = d\)，则 \(f\) 的代数次数至少为 \(d\)
- 即 \(\deg(f) \geq \text{AI}(f)\)
与平衡性的关系：
- 平衡函数的代数免疫度至少为 1
- 最优代数免疫函数可以是平衡的