线性密码分析(简单笔记)
关于差分密码分析的可以看差分密码分析读书报告。欢迎大家讨论留言。
1、发现
在1993年的欧洲密码年会上，日本学者Matsui提出了对DES算法的一种新的攻击方法，即线性密码分析.同年的国际密码年会上，Matsui发现了DES算法中2条新的线性逼近关系，他利用这两条新的逼近关系对DES算法进行攻击，并引入了纠错码中的阵列译码思想来优化攻击过程.在动用12台工作站，花费50天左右的时间后，Matsui成功地破译了DES算法，这是公开文献中第一个对DES算法的实验分析结果。
2、简介
这是已知明文攻击。对于迭代型分组密码，期待找到一个线性区分器来恢复最后一轮密钥（或者部分密钥信息）。与差分分析类似，同样是利用前 n − 1 n-1 n−1轮的某些特征来恢复最后一轮的子密钥。不同的是，这里找的是线性区分器。
3、原理
一个分析密码的角度可以这么看：给定个明文 P P P及其对应的密文 C C C，根据 C = E ( K , P ) C = E(K, P) C=E(K,P)，我们可以建立 n n n个涉及密钥比特的方程，求解这个方程组，便可以恢复密钥K。这种通过求解代数方程组（有限域上多元多项式方程组）来恢复密钥的方法，称作代数攻击。显然这是一个困难问题，但是我们想，会不会存在某个线性方程是隐含在加密过程中呢？这正是线性分析的由来。
3.1 提前工作
对于一个上图所示的一轮加密，设 ( α ⋅ β ) (\alpha \cdot \beta) (α⋅β)表示二元域上的内积，因为 m = k 0 ⊕ u 、 v = k 1 ⊕ c m=k_{0} \oplus u 、v=k_{1}\oplus c m=k0⊕u、v=k1⊕c，所以对 ∀ α , β \forall \alpha,\beta ∀α,β，有 ( α ⋅ m ) = ( α ⋅ k 0 ) ⊕ ( α ⋅ u ) (\alpha\cdot m)=(\alpha \cdot k_{0} )\oplus(\alpha \cdot u) (α⋅m)=(α⋅k0)⊕(α⋅u)和 ( β ⋅ v ) = ( β ⋅ k 1 ) ⨁ ( β ⋅ c ) (\beta\cdot v)=(\beta \cdot k_{1} )\bigoplus(\beta \cdot c) (β⋅v)=(β⋅k1)⨁(β⋅c)成立，但是 ( α ⋅ u ) ≠ ( β ⋅ v ) (\alpha \cdot u)\neq(\beta \cdot v) (α⋅u)=(β⋅v)。
假设 ( α ⋅ u ) = ( β ⋅ v ) (\alpha \cdot u)= (\beta \cdot v) (α⋅u)=(β⋅v)成立，且成立的概率为 p p p，我们有
( α ⋅ m ) ⊕ ( β ⋅ c ) = ( α ⋅ k 0 ) ⊕ ( β ⋅ k 1 ) (\alpha\cdot m)\oplus (\beta \cdot c)=(\alpha\cdot k_{0})\oplus (\beta \cdot k_{1}) (α⋅m)⊕(β⋅c)=(α⋅k0)⊕(β⋅k1)
（这个式子成立的概率也为 p p p），那么有
( α ⋅ m ) ⊕ ( β ⋅ c ) ≠ ( α ⋅ k 0 ) ⊕ ( β ⋅ k 1 ) ⟺ ( α ⋅ m ) ⊕ ( β ⋅ c ) ⊕ 1 = ( α ⋅ k 0 ) ⊕ ( β ⋅ k 1 ) (\alpha\cdot m)\oplus (\beta \cdot c)\neq(\alpha\cdot k_{0})\oplus (\beta \cdot k_{1})\iff (\alpha\cdot m)\oplus (\beta \cdot c) \oplus 1=(\alpha\cdot k_{0})\oplus (\beta \cdot k_{1}) (α⋅m)⊕(β⋅c)=(α⋅k0)⊕(β⋅k1)⟺(α⋅m)⊕(β⋅c)⊕1=(α⋅k0)⊕(β⋅k1)
这个式子成功概率为 1 − p 1-p 1−p。
进一步，考虑两个S盒的情况
有
这样，
( α ⋅ m ) ⊕ ( γ ⋅ c ) = ( α ⋅ k 0 ) ⊕ ( β ⋅ k 1 ) ⊕ ( γ ⋅ k 2 ) (\alpha \cdot m)\oplus (\gamma \cdot c)=(\alpha \cdot k_{0})\oplus (\beta \cdot k_{1})\oplus(\gamma \cdot k_{2}) (α⋅m)⊕(γ⋅c)=(α⋅k0)⊕(β⋅k1)⊕(γ⋅k2)
成立的概率为 p 1 p 2 + ( 1 − p 1 ) ( 1 − p 2 ) p_{1}p_{2}+(1-p_{1})(1-p_{2}) p1p2+(1−p1)(1−p2)，等式成立：p1,p2同时发生或者p1,p2同时不发生(同时不发生就同时异或1)
令 ε 1 = p 1 − 1 2 , ε 2 = p 2 − 1 2 \varepsilon _{1}=p_{1}-\frac{1}{2},\varepsilon _{2}=p_{2}-\frac{1}{2} ε1=p1−21,ε2=p2−21，有
p 1 p 2 + ( 1 − p 1 ) ( 1 − p 2 ) = 1 2 + 2 ε 1 ε 2 p_{1}p_{2}+(1-p_{1})(1-p_{2}) = \frac{1}{2} + 2\varepsilon_{1} \varepsilon_{2} p1p2+(1−p1)(1−p2)=21+2ε1ε2
进而可以归纳出堆积引理
(堆积引理:pilling-up lemma):
设 m m m个独立的 { 0 , 1 } \lbrace 0,1\rbrace {0,1}随机变量 Z i ， 1 ≤ i ≤ m Z_{i}，1\le i \le m Zi，1≤i≤m，且 P r [ Z i = 0 ] = p i Pr\left[ Z_{i}=0 \right] = p_{i} Pr[Zi=0]=pi，则有
P r [ Z 1 ⊕ Z 2 ⊕ ⋯ ⊕ Z m = 0 ] = 1 2 + 2 m − 1 ∏ i = 1 m ( p i − 1 2 ) Pr\left[ Z_{1} \oplus Z_{2} \oplus \cdots \oplus Z_{m} = 0 \right] = \frac{1}{2} + 2^{m-1} \prod \limits_{i=1}^{m}(p_{i} - \frac{1}{2}) Pr[Z1⊕Z2⊕⋯⊕Zm=0]=21+2m−1i=1∏m(pi−21)
变形后的形式更常用
2 P r [ Z 1 ⊕ Z 2 ⊕ ⋯ ⊕ Z m = 0 ] − 1 = ∏ i = 1 m ( 2 p i − 1 ) 2Pr\left[ Z_{1} \oplus Z_{2} \oplus \cdots \oplus Z_{m} = 0 \right]-1 =\prod \limits_{i=1}^{m}(2p_{i} - 1) 2Pr[Z1⊕Z2⊕⋯⊕Zm=0]−1=i=1∏m(2pi−1)
利用这样的区分器，可以完成线性攻击。
4、步骤
参考文献
[1] M. Matsui, Linear cryptanalysis method for DES cipher, in Advances in Cryptology—Eurocrypt’93, ed.by T. Helleseth. LNCS, vol. 765 (Springer, Berlin, 1993), pp. 386–397
