线性密码分析

线性分析一般效率不如差分分析好，但对某些密码（如DES）效果要较差分更好。

且线性分析为已知明文分析（而非选择明文）场景限制更宽松（而一般差分分析是选择明文攻击）这是线性密码分析的一个显著优势。

Idea

假设一个最简单的 toycipher：

如果将其每一比特拆开（注意线性关系是满足叠加原理的，可以拆开），即可得到每一比特密文与每一比特明文和密钥的线性关系。因此可以推出密钥的每一比特值。

假设在四比特域上的上述 toycipher：

通过化简得到：

如何通过S盒？

以上简单的过程乍一看是有些画蛇添足，但如果toycipher涉及S盒，就无法完成上述过程了。

假设有个较复杂的toycipher：

现在，考虑将明文和密文进行逐比特拆分就可以将这个特征传播性问题拆分，并且以此来逐比特（有概率）的提取密钥信息。

具体而言，寻找一组掩码，来构建向量的标量积，一般来说如：

# 在S盒的前后各需要一组掩码，来以高概率将非线性的S盒逼近为线性关系，即 $\alpha \cdot u=\beta \cdot S[x]\backslash alpha\; \backslash cdot\; u\; =\; \backslash beta\; \backslash cdot\; S[x]$。当然，该式依一定概率成立，而对于二元域上的运算，总共只有四种情况：$\alpha \cdot u\backslash alpha\; \backslash cdot\; u$ 和 $\beta \cdot S[x]\backslash beta\; \backslash cdot\; S[x]$ 分别为：0,0; 0,1; 1,0; 11. 即一半概率相等一半概率不相等。（在二元域上，相等与否的偏差以绝对值形式存在）。而较大概率成立的 $\alpha \cdot u=\beta \cdot S[x]\backslash alpha\; \backslash cdot\; u\; =\; \backslash beta\; \backslash cdot\; S[x]$ 可以为整个密码体系提供高概率（对于该仅有一个S盒非线性的toycipher），从而通过化简得到密钥信息，形如 $k_i=c_i\oplus m_i\mathrm{.}\mathrm{.}\mathrm{.}k\_i=c\_i\backslash oplus\; m\_i\; ...$

显然，线性关系满足以概率1传播的特点；

而非线性的S盒无法以确定概率传播消息，所以假设消息（比特）通过S盒并得到满足条件值的概率为p。

将上图的toycipher拆分成符合以下概率的等式：

将左右分别组合在一起，可以得到满足概率为 p 的等式：

假设有如下S盒，我们仅需考虑非确定概率的一段传播，即 $(\alpha \cdot u)=(\beta \cdot v)\to (\alpha \cdot x)=(\beta \cdot S[x])(\backslash alpha\; \backslash cdot\; u)=(\backslash beta\; \backslash cdot\; v)\; \backslash rightarrow\; (\backslash alpha\; \backslash cdot\; x)=(\backslash beta\; \backslash cdot\; S[x])$