5.7线性密码分析原理

第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准1第七节线性密码分析原理第七节线性密码分析原理第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准2对随机给定的明文对随机给定的明文P和相应的密文和相应的密文C上面的等 式成立的概率上面的等 式成立的概率p 1/2.线性密码分析的方法线性密码分析的方法是是寻找一个给定密码算法寻找一个给定密码算法的的具有下列形式的具有下列形式的“有效的有效的”线性表达式线性表达式 Pi1, i2, ia Cj1, j2, jb = Kk1, k2, kc (4.11)这里这里 i1, i2, ia ； j1, j2, jb和和 k1, k2, kc, 表表示固示固定定的比特位置。的比特位置。 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准31. 是否存在线性优势？是否存在线性优势？ 2. 如何求单轮变换的线性优势？如何求单轮变换的线性优势？ 3. 如何求多轮变换的线性优势？如何求多轮变换的线性优势？ 需要解决的问题需要解决的问题需要解决的问题需要解决的问题第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准4我们需要的是等式成立的概率我们需要的是等式成立的概率具有非均匀的具有非均匀的分布，所以用分布，所以用p 1/2来刻画等式的有效性来刻画等式的有效性(定义定义 i = pi 1/2 为偏差为偏差). 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准5我们把最有效的线性表达式（也就是我们把最有效的线性表达式（也就是 p 1/2 是最大的）称作是最大的）称作最佳线性逼近式最佳线性逼近式, 相应的概率相应的概率 p 称称作最佳概率作最佳概率. 为了计算等式为了计算等式(4.11)成立和有效的概成立和有效的概率率, 我们先给出一些理论上要用到的结果我们先给出一些理论上要用到的结果. 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准6设设 X1, X2, , Xk是取值于集合是取值于集合0,1的独立随机的独立随机变量变量. 设设p1, p2,.都是实数都是实数, 且对所有的且对所有的i, i =1,2, k有有 0 pi 1, 再设再设 PrXi = 0 = pi, 则则 PrXi = 1 = 1 pi.对取值于对取值于0,1的随机变量的随机变量, 用分布偏差来表示它的用分布偏差来表示它的概率分布概率分布. 随机变量随机变量 Xi的偏差定义为的偏差定义为 1 2iip= 堆积引理堆积引理第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准7引理（引理（堆积引理堆积引理. Piling-up lemma） 设设 1,., kiiXX是独立的随机变量是独立的随机变量, 1 2.ki ii表示随机变量表示随机变量 Xi1 Xi2- Xik的偏差的偏差, 则则 1 21 . 12 kjk k i iii j=证明：用数学归纳法。 首先证明：用数学归纳法。 首先k = 2时时第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准8推 论推 论 设设 1,., kiiXX是 独 立 的 随 机 变 量是 独 立 的 随 机 变 量 ,1 2.ki ii表示随机变量表示随机变量 Xi1 Xi2 Xik的偏差的偏差, 若若对某个对某个 j 有有0 ji=, 则则 1 2.0 ki ii=. 注：引理注：引理 4.1 只只在相关随机变量是统计独立在相关随机变量是统计独立的的情况下才成立情况下才成立. 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准9利用堆积引理利用堆积引理, 我们可以将每轮变换中偏差我们可以将每轮变换中偏差最大的线性逼近式进行组合最大的线性逼近式进行组合, 组合后的所有轮变组合后的所有轮变换的线性逼近式换的线性逼近式, 也将拥有最佳的偏差也将拥有最佳的偏差, 即寻找即寻找分组密码的最佳线性逼近式分组密码的最佳线性逼近式. 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准10由上述分析我们知道由上述分析我们知道, 分组密码的最佳线性逼近分组密码的最佳线性逼近式的寻找式的寻找, 归结为每轮线性逼近式的寻找归结为每轮线性逼近式的寻找, 而每轮的而每轮的变换中变换中, 除了非线性变换除了非线性变换(即即 S-盒盒)部分部分, 线性部分是自线性部分是自然的线性关系然的线性关系, 也就是说也就是说, 每轮线性逼近式的寻找每轮线性逼近式的寻找, 只只需寻求需寻求 S-盒部分的最佳线性逼近式盒部分的最佳线性逼近式. S-盒的线性逼近盒的线性逼近第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准11考虑如下一个考虑如下一个 S-盒盒:0,10,1mn s(我们并未假我们并未假定定s是一个置换是一个置换, 甚至也未假定甚至也未假定 m = n). m 重输入重输入X = (x1, x2, , xm) 均匀随机地从集合均匀随机地从集合0,1m中选取中选取,这就是说这就是说, 每一个坐标每一个坐标xi定义了一个随机变量定义了一个随机变量iX, iX取值于取值于0,1, 并且其偏差并且其偏差0i=即即 (0)(1)1/ 2iip Xp X=. 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准12进一步进一步, 假设这假设这 m 个随机变量相互独立个随机变量相互独立, n 重输出重输出 Y = (y1, y2, yn)中每一个坐标中每一个坐标 yi定义了一个随机定义了一个随机变量变量iY, iY取值于取值于0,1. 这这 n 个随机变量一般来说不是相互独立的个随机变量一般来说不是相互独立的, 与与 Xi也不相互独立也不相互独立. 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准13现在考虑计算如下形式的随机变量的偏差值：现在考虑计算如下形式的随机变量的偏差值：()() 11mmiijjiia Xb Y = 其中其中 a = (a1, am)和和 b = (b1, bn)分别为分别为 m 和和 n 维维随机向量随机向量, ai和和 bj为为 0 或或 1. 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准14设设 NL(a, b)表示满足如下条件的二元表示满足如下条件的二元 m + n 组组(x1,x2, xm, y1, yn)的个数的个数: (y1, yn) = s(x1, x2, xm)（ 记为条 件（ 记为条 件 B）且且11()()0mniijj ija Xb Y=（记为条件（记为条件 A） 则则 P(A / B) = P(A, B) / P(B) = (NL(a, b) / 2m+n) / (2m / 2m+n) = NL(a, b) / 2m, 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准15对于一个具有输入对于一个具有输入 a 与输出与输出 b 的的随机变随机变量量()() 11mmiijjiia Xb Y = 的偏差计算公式为的偏差计算公式为: （a, b）= NL(a, b)/2m 1/2 正是由于正是由于 S-盒的 （盒的 （a, b）的不同）的不同, 使使得线性分析的得线性分析的实实现成为可能现成为可能. 下面举一个例子。下面举一个例子。 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准16例：设例：设 S-盒盒44:0,10,1s。在下表中，给出了。在下表中，给出了 8 个随机变量个随机变量1414,.,.,XX YY所有可能的取值：输入所有可能的取值：输入 z 和输出和输出s(z)都以十六进制表示都以十六进制表示(0(0,0,0,0), 1 (0,0,0,1), ,F(1,1,1,1): z 0 1 2 3 4 5 6 7 s(z) E 4 D 1 2 F B 8 z 8 9 A B C D E F s(z) 3 A 6 C 5 9 0 7 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准17X1 X2X3X4Y1Y2Y3Y40 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准18X1 X2X3X4Y1Y2Y3Y41 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准19现在，我们考虑随机变量现在，我们考虑随机变量 X1 X4 Y2。通过计算通过计算表中表中 X1 X4 Y2=0 的行数，的行数，我们可以得到该随机变量我们可以得到该随机变量取值为取值为 0 的概率：的概率： p(X1 X4 Y2 = 0) = 1/2 因此因此 p(X1 X4 Y2 = 1) = 1/2 可见，随机变量可见，随机变量 X1 X4 Y2的偏差为的偏差为 0。 即即 NL(9, 4) = 8， (9,4)0=。 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准20如果再分析一下随机变量如果再分析一下随机变量 X3 X4 Y1 Y4。通通过计算表中过计算表中 X3 X4 Y1 Y4 = 0 的行数，的行数，我我们可们可以以得到该随机变量取值为得到该随机变量取值为 0 的概率：的概率： 3414(0)1/8p XXYY+= 即即 NL(3, 9) = 2， 3(3,9)8= 。 第五章第五章第五章第五章 分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准分组密码与数据加密标准21事实上，我