密码的三子集划分性质探索

# 密码的三子集划分性质探索 ## 1. 密钥异或操作的BDPT的MILP模型构建 在密码分析中，构建密钥异或操作的BDPT（布尔差分划分性质）的混合整数线性规划（MILP）模型是一项重要任务。下面详细介绍如何构建该模型。 ### 1.1 相关符号说明 设 $E_r$ 是 $r$ 轮分组密码，$f_i$ 是第 $i$ 轮函数，$f_{i}^{k}$ 是第 $i$ 轮密钥异或操作。密钥异或操作的初始和输出BDPT分别表示为 $(K_{i - 1}^*, L_{i - 1}^*)$ 和 $(K_i, L_i)$。 ### 1.2 分解密钥异或操作 根据BDPT规则1，将 $f_{i}^{k}$ 分解为两个操作 $f_{i}^{1}$ 和 $f_{i}^{2}$： - **$f_{i}^{1}$ 操作**：从 $L_{i - 1}^*$ 的每个元素生成一些新元素。 - **$f_{i}^{2}$ 操作**：将新向量和 $K_{i - 1}^*$ 中的向量包含在 $K_i$ 中。 ### 1.3 建模 $f_{i}^{1}$ 操作 在许多密码中，轮密钥仅与块的一部分进行异或操作。不失一般性，假设轮密钥与最左边的 $s$（$0 \leq s \leq n - 1$）位进行异或。以 $L_{i - 1}^* \subseteq F_{2}^{4}$ 且 $s = 2$ 为例，即轮密钥与最左边的2位进行异或。根据BDPT规则1，$f_{i}^{1}$ 函数从 $l = (l_0, l_1, l_2, l_3)$ 创建 $l' = (l_0', l_1', l_2', l_3')$，对于每个满足 $l_i = 0$（$i \in \{0, 1\}$）的向量 $l \in L_{i - 1}^*$，有 $l_i' = l_i \vee 1$，且对于所有 $j = 2, 3$，$l_j' = l_j$。 对应的传播表如下： | $(l_0, l_1, l_2, l_3)$ | $(l_0', l_1', l_2', l_3')$ | | --- | --- | | $(0, 0, l_2, l_3)$ | $(0, 1, l_2, l_3), (1, 0, l_2, l_3), (1, 1, l_2, l_3)$ | | $(0, 1, l_2, l_3)$ | $(1, 1, l_2, l_3)$ | | $(1, 0, l_2, l_3)$ | $(1, 1, l_2, l_3)$ | | $(1, 1, l_2, l_3)$ | X | 线性不等式描述如下： \[ \begin{cases} l_j' \geq l_j, & \text{for } j = 0, 1 \\ l_j' = l_j, & \text{for } j = 2, 3 \\ 2\sum_{j = 0}^{1} l_j' - \sum_{j = 0}^{1} l_j \geq 2 \\ \sum_{j = 0}^{3} l_j' - \sum_{j = 0}^{3} l_j \geq 1 \end{cases} \] 其中 $l_0', l_1', l_2', l_3', l_0, l_1, l_2, l_3$ 是二进制数。 对于 $n$ 位分组密码，当 $L_{i - 1}^* \subseteq F_{2}^{n}$ 且轮密钥与最左边的 $s$ 位进行异或时，描述 $l \xrightarrow{f_{i}^{1}} l'$ 轨迹的线性不等式如下： \[ \begin{cases} l_j' \geq l_j, & \text{for } j = 0, 1, \cdots, s - 1 \\ l_j' = l_j, & \text{for } j = s, s + 1, \cdots, n - 1 \\ s\sum_{j = 0}^{s - 1} l_j' - (s - 1)\sum_{j = 0}^{s - 1} l_j \geq s \\ \sum_{j = 0}^{n - 1} l_j' - \sum_{j = 1}^{n} l_j \geq 1 \end{cases} \] 其中 $l_0', l_1', \cdots, l_{n - 1}', l_0, l_1, \cdots, l_{n - 1}$ 是二进制数。 ### 1.4 建模 $f_{i}^{2}$ 操作 对集合 $L_{i - 1}^*$ 的每个元素应用 $f_{i}^{1}$ 后，得到集合 $L_{i - 1}'$： $L_{i - 1}' = \{l' \in F_{2}^{n} | f_{i}^{1}(l) = l', \forall l \in L_{i - 1}^*\}$ 根据BDPT规则1，$f_{i}^{2}(K_{i - 1}^*, L_{i - 1}') = K_{i - 1}^* \cup L_{i - 1}' = K_i$。为了建模 $f_{i}^{2}$，定义函数 $g : (F_{2}^{2} \setminus \{(0, 0), (1, 1)\}) \times K_{i - 1}^* \times L_{i - 1}' \to K_i$ 如下： $g(\lambda_0, \lambda_1, k^*, l') = (\lambda_0 \wedge k_0^*, \cdots, \lambda_0 \wedge k_{n - 1}^*) \oplus (\lambda_1 \wedge l_0', \cdots, \lambda_1 \wedge l_{n - 1}')$ 其中 $\lambda = (\lambda_0, \lambda_1) \in F_{2}^{2} \setminus \{(0, 0), (1, 1)\}$，$k^* = (k_0^*, \cdots, k_{n - 1}^*)$，$l' = (l_0', \cdots, l_{n - 1}')$。 为了构建描述 $g$ 函数轨迹的线性不等式，首先需要构建描述 $(a, b) \xrightarrow{\wedge} c$ 传播的线性不等式： \[ \begin{cases} a - c \geq 0 \\ b - c \geq 0 \\ a + b - c \leq 1 \end{cases} \] 其中 $a, b, c$ 是二进制数。 使用上述不等式和 $g$ 函数的定义，可以得到描述 $g$ 函数传播的不等式： \[ \begin{cases} \lambda_0 - p_j \geq 0, & \text{for } j = 0, 1, \cdots, n - 1 \\ k_j^* - p_j \geq 0, & \text{for } j = 0, 1, \cdots, n - 1 \\ \lambda_0 + k_j^* - p_j \leq 1, & \text{for } i = 0, 1, \cdots, n - 1 \\ \lambda_1 - q_j \geq 0, & \text{for } i = 0, 1, \cdots, n - 1 \\ l_j' - q_j \geq 0, & \text{for } i = 0, 1, \cdots, n - 1 \\ \lambda_1 + l_j' - q_j \leq 1, & \text{for } i = 0, 1, \cdots, n - 1 \\ p_j + q_j - k_j = 0, & \text{for } j = 0, 1, \cdots, n - 1 \\ \lambda_0 + \lambda_1 = 1 \end{cases} \] 其中 $p_0, \cdots, p_{n - 1}, q_0, \cdots, q_{n - 1}, l_0', \cdots, l_{n - 1}', k_0, \cdots, k_{n - 1}, k_0^*, \cdots, k_{n - 1}^*, \lambda_0, \lambda_1$ 是二进制数，$p = (p_0, p_1, \cdots, p_{n - 1})$，$q = (q_0, q_1, \cdots, q_{n - 1})$ 是辅助变量。 综上，上述不等式描述了密钥异或操作的完整MILP模型。 ### 1.5 r轮函数的MILP模型构建 对于基于上述操作的所有函数，我们最终得到一组描述一轮BDPT传播的线性不等式。为了构建 $r