Week5~7 差分分析

差分分析

对于加密 $C = P \oplus K$，有 $P \oplus P' = P \oplus K \oplus P' \oplus K = C \oplus C'$，对于一个n比特加密算法和随机置换的区别，常有：$DP(\alpha,\beta) > 1/2^n$，所以可以通过构造特定差分的方式建立区分器并且进一步恢复密钥

S 盒差分分布表项为何为偶数

设 $S:\mathbb{F}_2^n \to \mathbb{F}_2^m$，差分分布表（DDT）定义

$D[a,b] = \bigl|\{\, x \in \mathbb{F}_2^n \mid S(x)\oplus S(x\oplus a)=b \,\}\bigr|.$

• 若 $a\neq 0$：映射 $\tau(x)=x\oplus a$ 将域划分为 $2^{n-1}$ 个不相交二元组 $\{x, x\oplus a\}$。在每个二元组内，若 $x$ 满足等式，则 $x\oplus a$ 也满足，因为

  $S(x\oplus a)\oplus S((x\oplus a)\oplus a)=S(x\oplus a)\oplus S(x)=b.$

  解成对出现，因此 $D[a,b]$ 为偶数。
• 若 $a=0$：恒有 $S(x)\oplus S(x)=0$，故 $D[0,0]=2^n$、$D[0,b\neq 0]=0$，也都是偶数。

该结论对任意 $S$（不要求为置换）成立，关键在差分运算使用异或（特征为 2），从而可以配对 $x$ 与 $x\oplus a$。若改为普通加法模 $2^n$ 等运算，上述“必为偶数”的性质不一定成立。

密钥恢复

假设有如下5 rounds算法:

已知有一条高概率为 $p$ 的4轮差分路线，则可以猜测第五轮轮密钥 $k5$，通过反推比对第四轮输出差分与期望(概率为 $p$)，从而恢复轮密钥 $k5$。