使用数学公式证明:将一个随机数序列与SM4算法子密钥进行异或后得到新的32位值那么当输入明文发生单字节差分故障时,输出密文也会发生单字节差分故障的概率很小。
时间: 2024-01-24 16:20:14 浏览: 29
假设随机数序列为 $R = \{r_1, r_2, \dots, r_n\}$,SM4算法子密钥为 $K$,输入的明文为 $P$,加密后的密文为 $C$。
根据SM4算法的加密过程可知,SM4加密算法可以被表示为 $C = SM4(K, P)$。我们将输入的明文 $P$ 改变一个字节,得到 $P'$,则相应的密文为 $C' = SM4(K, P')$。
现在,我们将 $R$ 与 $K$ 进行异或,得到 $K' = \{k'_1, k'_2, \dots, k'_n\}$。然后,再将 $R$ 中的每个元素依次与 $P$ 的每个字节进行异或,得到 $P'' = \{p''_1, p''_2, \dots, p''_n\}$。最后,我们使用 $K'$ 加密 $P''$,得到密文 $C'' = SM4(K', P'')$。
现在,我们来考虑单字节差分故障的情况。假设输入的明文 $P$ 中的第 $i$ 字节发生了单字节差分故障,即将 $P$ 的第 $i$ 字节从 $p_i$ 变为 $p'_i$。我们需要证明的是,输出的密文 $C$ 中的第 $i$ 字节和 $C'$ 中的第 $i$ 字节之间的差别很小。
由于 SM4 算法是分组密码,它将明文分成多个 16 字节的块进行加密。因此,我们需要对明文和密文的每个块进行分析。
对于明文块 $P_j$,我们有 $P_j' = P_j \oplus \delta_{ij}$,其中 $\delta_{ij}$ 表示只在第 $i$ 个字节上有一个比特位被翻转。然后,我们将 $P_j'$ 分成 $n$ 个字节,即 $P_j' = \{p_{j1}', p_{j2}', \dots, p_{jn}'\}$,其中 $p_{jk}'$ 表示 $P_j'$ 中的第 $k$ 个字节。接下来,我们将 $R$ 中的每个元素依次与 $p_{jk}'$ 进行异或,得到 $p_{jk}'' = p_{jk}' \oplus r_k$。最后,我们使用 $K'$ 加密 $P_j''$,得到密文块 $C_j''$。
对于密文块 $C_j$,我们可以按照同样的方式得到 $C_j''$。
现在,我们来比较 $C_j$ 和 $C_j''$ 之间的差别。根据 SM4 算法的加密过程,我们有 $C_j = SM4(K, P_j)$,$C_j'' = SM4(K', P_j'')$。因此,我们可以将它们展开成以下形式:
$$C_j = F_{r}(F_{r-1}(\cdots F_{2}(F_{1}(P_j \oplus K_0) \oplus K_1) \cdots ) \oplus K_{r-1}) \oplus K_r$$
$$C_j'' = F_{r}(F_{r-1}(\cdots F_{2}(F_{1}(P_j'' \oplus K_0') \oplus K_1') \cdots ) \oplus K_{r-1}') \oplus K_r'$$
其中,$F$ 表示 SM4 算法中的轮函数,$K_0, K_1, \dots, K_r$ 是 SM4 算法的轮密钥,$K_0', K_1', \dots, K_r'$ 是 $K'$ 与 $P_j''$ 生成的轮密钥。
我们需要比较 $C_j$ 和 $C_j''$ 中的第 $i$ 个字节,即 $C_{ji}$ 和 $C_{ji}''$。根据 SM4 算法的加密过程,我们可以将 $C_{ji}$ 和 $C_{ji}''$ 表示为以下形式:
$$C_{ji} = F_{r}(F_{r-1}(\cdots F_{2}(F_{1}(P_{ji} \oplus K_{0i}) \oplus K_{1i}) \cdots ) \oplus K_{ri}$$
$$C_{ji}'' = F_{r}(F_{r-1}(\cdots F_{2}(F_{1}(P_{ji}'' \oplus K_{0i}') \oplus K_{1i}') \cdots ) \oplus K_{ri}'$$
其中,$P_{ji}$ 和 $P_{ji}''$ 分别表示 $P_{j}$ 和 $P_{j}''$ 中的第 $i$ 个字节,$K_{0i}, K_{1i}, \dots, K_{ri}$ 是 SM4 算法的轮密钥中的第 $i$ 个字节,$K_{0i}', K_{1i}', \dots, K_{ri}'$ 是 $K'$ 与 $P_j''$ 生成的轮密钥中的第 $i$ 个字节。
现在,我们来比较 $C_{ji}$ 和 $C_{ji}''$ 之间的差别。根据 SM4 算法的加密过程,我们知道轮函数 $F$ 是一个 S 盒,它将输入的 8 位二进制数映射到输出的 8 位二进制数。因此,我们可以将 $F$ 表示为以下形式:
$$F(x) = S_1(x_1) \oplus S_2(x_2) \oplus \cdots \oplus S_8(x_8)$$
其中,$S_1, S_2, \dots, S_8$ 是 S 盒中的 8 个子 S 盒,$x_1, x_2, \dots, x_8$ 是输入的 8 个二进制位。
假设 $C_{ji}$ 和 $C_{ji}''$ 之间的差别是 $\Delta_i$,即 $C_{ji}'' = C_{ji} \oplus \Delta_i$。我们需要证明的是,$\Delta_i$ 很小。
我们可以将 $C_{ji}$ 和 $C_{ji}''$ 展开成以下形式:
$$C_{ji} = S_1(K_{0i} \oplus P_{ji}) \oplus S_2(F_1(K_{1i} \oplus S_1(K_{0i} \oplus P_{ji})) \oplus K_{1i}) \oplus \cdots \oplus S_8(F_r(K_{ri} \oplus S_7(F_{r-1}(K_{r-1} \oplus \cdots \oplus S_1(K_{0i} \oplus P_{ji}))))) \oplus K_{ri}$$
$$C_{ji}'' = S_1(K_{0i}' \oplus P_{ji}'') \oplus S_2(F_1(K_{1i}' \oplus S_1(K_{0i}' \oplus P_{ji}'')) \oplus K_{1i}') \oplus \cdots \oplus S_8(F_r(K_{ri}' \oplus S_7(F_{r-1}(K_{r-1}' \oplus \cdots \oplus S_1(K_{0i}' \oplus P_{ji}''))))) \oplus K_{ri}'$$
因此,$\Delta_i$ 可以表示为:
$$\Delta_i = C_{ji}'' \oplus C_{ji} = S_1(K_{0i}' \oplus P_{ji}'') \oplus S_2(F_1(K_{1i}' \oplus S_1(K_{0i}' \oplus P_{ji}'')) \oplus K_{1i}') \oplus \cdots \oplus S_8(F_r(K_{ri}' \oplus S_7(F_{r-1}(K_{r-1}' \oplus \cdots \oplus S_1(K_{0i}' \oplus P_{ji}''))))) \oplus K_{ri}' \oplus$$$$S_1(K_{0i} \oplus P_{ji}) \oplus S_2(F_1(K_{1i} \oplus S_1(K_{0i} \oplus P_{ji})) \oplus K_{1i}) \oplus \cdots \oplus S_8(F_r(K_{ri} \oplus S_7(F_{r-1}(K_{r-1} \oplus \cdots \oplus S_1(K_{0i} \oplus P_{ji}))))) \oplus K_{ri}$$
我们需要证明的是,$\Delta_i$ 很小。注意到 $K_{0i}, K_{1i}, \dots, K_{ri}$ 和 $K_{0i}', K_{1i}', \dots, K_{ri}'$ 是两个随机数序列,而 $P_{ji}$ 和 $P_{ji}''$ 只相差一个比特位。因此,$K_{0i} \oplus P_{ji}$ 和 $K_{0i}' \oplus P_{ji}''$ 也只相差一个比特位。由于 $S_1, S_2, \dots, S_8$ 是 S 盒,它们将任意的 8 位二进制数映射到另一个 8 位二进制数。因此,对于任意的 $x, x' \in \{0, 1\}^8$,我们有 $|S_i(x) \oplus S_i(x')| \leq 2$。因此,我们有:
$$|\Delta_i| \leq 16 + \sum_{j=1}^{r} 16 \cdot 2^j = 16 \cdot (2^{r+1} - 1)$$
由于 $r$ 取决于 SM4 算法的轮数,通常为 32 轮或者 24 轮。因此,当 $r=32$ 或者 $r=24$ 时,$\Delta_i$ 的绝对值最大只有 $16 \cdot (2^{33}-1)$ 或者 $16 \cdot (2^{25}-1)$。由于 $C_{ji}$ 和 $C_{ji}''$ 都是 32 位的二进制数,因此 $\Delta_i$ 相对于 $C_{ji}$ 和 $C_{ji}''$ 来说非常小。
综上所述,将随机数序列与 SM4 算法子密钥进行异或后得到新的 32 位值时,当输入明文发生单字节差分故障时,输出密文也会发生单字节差分故障的概率很小。