Week8~ 线性分析

Intro

对于n bits的非随机置换来说，给定线性掩码 $(\alpha,\beta)$，可以作为分组加密算法的近似：

$\alpha \cdot X \oplus \beta \cdot E(X) = \alpha \cdot X \oplus \beta \cdot Y$

给出概率：

Pr(\alpha,\beta) = \frac{#\{\alpha X \oplus \beta Y = 0\}}{2^n}

其中 # 是counter，满足条件时加1。

这里面提到的掩码类似于子网掩码的概念，假设有一个4bits的Sbox，\alpha = 0101 \And \beta = 1010，则对于输入 $X=x_0x_1x_2x_3$ 和 $Y=y_0y_1y_2y_3$，就相当于判断 $x_1 \oplus x_3 \oplus y_0 \oplus y_2 == 0$。

类似的，和差分分析类似，差分分析可以根据输入输出差分构建差分表DDT，线性分析也可以根据输入输出掩码构建线性表LAT。

而对于分组密码既一个非随机置换来说，存在一些掩码对 $(\alpha,\beta)$ 使得 $Pr(\alpha,\beta)$ 明显偏离 $1/2$，