Week5~7 差分分析

差分分析

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

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

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

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

• 若 $a\ne 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\ne 0]=0$，也都是偶数。

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

密钥恢复

假设有如下5 rounds算法:

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