分支数与多轮轨迹的密码学分析

### 分支数与多轮轨迹的密码学分析 在密码学的块密码设计中，分支数和多轮轨迹的特性对于构建安全且高效的加密算法至关重要。下面我们将深入探讨分支数的概念、相关性质以及它们在多轮轨迹中的应用。 #### 分支数基础概念 分支数为任意两轮轨迹的最小束权重提供了一个下限。束分支数的范围在 2（表示完全没有扩散）到状态中束的总数 $n_t$ 加 1 之间。对于超过两轮的轨迹，$\rho$ 的扩散特性更为复杂。显然，任何 2n 轮轨迹都是 n 个两轮轨迹的序列，因此其束权重下限为 n 倍的 $\rho$ 的分支数。 为了实现高效的设计，$\lambda$ 可以由两个步骤构成： 1. **$\theta$ 步骤**：提供高局部扩散。在块密码设计中，$\theta$ 是一个线性砌砖置换，其每个组件置换操作于有限数量的束，并且相对于其维度具有较高的分支数。 2. **$\pi$ 步骤**：提供高分散性。$\pi$ 将在 $\theta$ 操作中彼此接近的位或束移动到距离较远的位置。 $\theta$ 和 $\pi$ 联合起来对低汉明权重的模式有显著影响：通过 $\theta$ 传播为高汉明权重的局部模式，再由 $\pi$ 将其分散到整个状态。 #### 分支数的正式定义 我们正式定义布尔变换相对于束分区的分支数。状态的束权重等于非零束的数量，用 $w_b(a)$ 表示。对于差分模式 $a'$，$w_b(a')$ 是 $a'$ 中活动束的数量；对于选择模式 $v$，$w_b(v)$ 是 $v$ 中活动束的数量。我们区分变换的差分分支数和线性分支数。 - **差分分支数**：变换 $\varphi$ 的差分分支数定义为 $B_d(\varphi) = \min_{a,b\neq a}\{w_b(a \oplus b) + w_b(\varphi(a) \oplus \varphi(b))\}$ 对于线性变换 $\lambda$，有 $\lambda(a) \oplus \lambda(b) = \lambda(a \oplus b)$，则上式可简化为 $B_d(\lambda) = \min_{a'\neq 0}\{w_b(a') + w_b(\lambda(a'))\}$ - **线性分支数**：变换 $\varphi$ 的线性分支数定义为 $B_l(\varphi, \alpha) = \min_{\alpha,\beta,C(\alpha^Tx,\beta^T\varphi(x))\neq 0}\{w_b(\alpha) + w_b(\beta)\}$ 若 $\varphi$ 是由矩阵 $M$ 表示的线性变换，即 $\lambda(x) = M \cdot x$，则上式可简化为 $B_l(\lambda) = \min_{\alpha\neq 0}\{w_b(\alpha) + w_b(M^T\alpha)\}$ 布尔变换 $\varphi$ 的（差分或线性）分支数的上限由状态中束的总数 $n_{\alpha}$ 给出，即 $B(\varphi) \leq n_{\alpha} + 1$。一般情况下，变换相对于分区的线性和差分分支数不相等，但在某些条件下（如矩阵 $M$ 对称或具有最大可能的差分或线性分支数），两者相等。 #### 示例说明 考虑在 $GF(4)$ 上的变换 $\lambda : x \to A \cdot x$，其中 $A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}$ 由于 $A \cdot (1, 0, 0, 0)^T = (1, 0, 0, 0)^T$，可得 $B_d(\theta) \leq 2$。但简单枚举表明，不存在 $\alpha$ 使得 $w_b(\alpha) + w_b(A^T\alpha) \leq 2$，因此 $B_l(\theta) \geq 3$。 #### 分支数的派生性质 从分支数的定义对称性可知，变换及其逆变换的分支数相同。此外，还有以下性质： 1. （差分或选择）模式 $a$ 不受密钥加法的影响，因此其束权重 $w_b(a)$ 不变。 2. 对单个束操作的砌砖置换不会将活动束变为非活动束，反之亦然，因此不影响束权重 $w_b$。 如果变换 $\varphi$ 是变换 $\varphi_1$ 和对束操作的砌砖变换 $\varphi_2$ 的序列，即 $\varphi = \varphi_2 \circ \varphi_1$，由于 $\varphi_2$ 不影响传播模式中活动束的数量，所以 $\varphi$ 和 $\varphi_1$ 的分支数相同。对于 $\gamma\lambda$ 轮变换 $\rho$，其（线性或差分）束分支数就是其线性部分 $\lambda$ 的分支数。 #### 两轮传播定理 下面的定理将 $B(\lambda)$ 的值与轨迹中活动束的数量上限联系起来。该证明对线性轨迹和差分轨迹都有效：在线性轨迹中 $B$ 表示 $B_l$，在差分轨迹中 $B$ 表示 $B_d$。 **定理 9.3.1（两轮