Week8~ 线性分析

Intro

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

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

给出概率：

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

其中 $\text{\#}$ 是counter，满足条件时加1。

这里面提到的掩码类似于子网掩码的概念，假设有一个4bits的Sbox，$\alpha =0101\mathrm{\&}\beta =1010$，则对于输入 $X=x_0{x}_1{x}_2{x}_3$ 和 $Y=y_0{y}_1{y}_2{y}_3$，就相当于判断 $x_1\oplus x_3\oplus y_0\oplus y_2==0$。

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

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