1、差分密码分析和线性密码分析原理CONTENTS0102u 差分密码分析差分密码分析是迄今为止已知的攻击迭代是迄今为止已知的攻击迭代分组密码最有效的方法之一，其基本思想分组密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差是：通过分析明文对的差值对密文对的差值来影响来恢复某些密钥比特值来影响来恢复某些密钥比特u 当当密码分析人员可以进行选择明文分析时，密码分析人员可以进行选择明文分析时，差分密码分析十分有效。差分密码分析十分有效。u 已知明文的差分密码分析也是可行的，但已知明文的差分密码分析也是可行的，但是要求已知明密文的量很大是要求已知明密文的量很大差分密码分析简介设计DES
2、的IBM小组知道了差分分析197419911990Biham和Shamir对多种加密算法和Hash函数进行差分密码分析攻击，结果发表在BIHA93中差分密码分析公开发表最早研究是Murphy分析分组密码FEAL【MURP90】差分密码分析的历史6符号定义uP P 表示明文表示明文，T T 表示密文表示密文u(P,PP,P)表示明文对，其异或后得表示明文对，其异或后得到特定的值：到特定的值：P,P,使得使得 P=P P=P P P u(T,TT,T)表示密文对，其异或后得表示密文对，其异或后得到特定的值到特定的值TT，使得，使得 T=T T=T T T u 带撇的值带撇的值总是总是表示表示差分，
3、差分，PP ,TT,aa,AA。例如，例如，a=a a=a a a 7差分密码分析_DESDES DES 的设计要求之一是确保尽可能的分的设计要求之一是确保尽可能的分布均匀布均匀例如，明文或密钥的例如，明文或密钥的1 1比特变化，将导比特变化，将导致致6464比特的密文中大约比特的密文中大约3232比特的看起来比特的看起来是不可预测和随机的变化是不可预测和随机的变化不过对于不过对于固定的密钥，固定的密钥，DESDES的差分并不呈的差分并不呈现伪现伪随机现象随机现象即对于固定明文即对于固定明文P P 和和P P 的的异或异或P PT=TTT=TT 不是均匀分布不是均匀分布的的8S-Box是非差分
4、均匀的是非差分均匀的v对于输入对于输入S S盒的盒的6 6比特比特的的(x x,x,x)值值对，一共对，一共有多少种可能？有多少种可能？考虑一个考虑一个S-boxS-box的差分现象：的差分现象：输入值对的差分为输入值对的差分为x x=x=x x x 差分值可能有多少差分值可能有多少种？种？对于其对于其4 4比特输出值，比特输出值，y=S(x),yy=S(x),y=S(x=S(x)，以及以及y=y yy=y y =S(x)S(x=S(x)S(x)输出差分值有多少种可输出差分值有多少种可能？能？64642 2=4096 4096 2 26 6=64642 24 4=1616S-Box是非差分均匀
5、的是非差分均匀的vx01 23456789abcdefxfffe dcba9876543210S(x)e4 d12fb83a6c5907S(xff)70 95c6a38bf21d4ES(x)S(xff)94 44e91bb19e4449输入差分输入差分f=1111f=111110S1 的差分分布表的差分分布表.=2=26 6-1-1出出现现的的次次数数u 6 6比特的差分输入比特的差分输入xx有有6464个值：个值：00-3F00-3F(16(16进制，进制，1010进制是进制是0-630-63)u 4 4比特的差分输出比特的差分输出yy有有1616个值：个值：0-F0-F(16(16进进制，
6、制，1010进制是进制是0-150-15)u 可以看到：第一行可以看到：第一行除第一列外全为除第一列外全为0 0，因为当因为当x=x xx=x x =0=0，同样的输入出同样的输入出现了两次，因此其现了两次，因此其输出输出y=y yy=y y =0=0u 后面的行：后面的行：u 例如，当例如，当 x=01 x=01 时时,6 6个可能的个可能的yy中有中有5 5个值个值:0,1,2,4,80,1,2,4,8呈现呈现0 0可能次数，就是说不可能次数，就是说不出现。出现。uA A 出现的概率是出现的概率是12/6412/64u 9 9 和和C C 出现的概率是出现的概率是10/6410/64u 这
7、就是说，这就是说，S1S1呈现出呈现出很强的不均匀分布很强的不均匀分布u 这种差分不均匀性对这种差分不均匀性对于所有的于所有的S S盒盒S1,S2,.S1,S2,.,S8.,S8都有体现都有体现u 考虑输入异或值考虑输入异或值为为3434时，可能的时，可能的输出异或是输出异或是：u 其中其中：34344 4有两有两种可能，这种输种可能，这种输入对是成双的，入对是成双的，即：即：(,)和和 (,)S1 的差分分布表的差分分布表对对S1S1构建差分表，构建差分表，发现当输入是发现当输入是13 13 和和27 27 时时(只看后面的只看后面的6 6位位)：12S1 的差分分布表的差分分布表12列出列
8、出S1S1中中输入异输入异或值为或值为3434的可能的可能的输入的输入值值(16(16进进制制)：13确定密钥的原理确定密钥的原理假设已知假设已知S1S1的两个输入是的两个输入是0101和和3535，其异或的，其异或的结果是结果是3434，经过，经过S1S1之后输出异或的结果是之后输出异或的结果是D D。查。查S1S1的差分分布表，得到输入异或为的差分分布表，得到输入异或为3434，输出异或为输出异或为D D时，可能的输入：时，可能的输入：14确定密钥的原理确定密钥的原理14实际上，输入异或的结果实际上，输入异或的结果是是3434，与密钥无关，这是，与密钥无关，这是因为：因为：因为因为所以所以
9、这样就得这样就得到：到：所以，可能的密钥就是所以，可能的密钥就是15确定密钥的原理确定密钥的原理此外，假设已知此外，假设已知S1S1的两个输入是的两个输入是2121和和1515，它，它们异或后的结果是们异或后的结果是3434，输出异或后的结果是，输出异或后的结果是3 3 。查。查S1S1的差分分布表，得到输入异或为的差分分布表，得到输入异或为3434，输出异或为，输出异或为3 3时，可能的输入：时，可能的输入：。16确定密钥的原理确定密钥的原理16这样就可以从这样就可以从得到可能的密钥值得到可能的密钥值17确定密钥的原理确定密钥的原理17而正确的密钥值必定同时出现在两个集合而正确的密钥值必定同
10、时出现在两个集合因此可以确定密钥是在因此可以确定密钥是在 中中的一个。的一个。要确定到底是哪一个，需要知道更要确定到底是哪一个，需要知道更多的输入输出异或对多的输入输出异或对。以此类推得。以此类推得到此轮密钥到此轮密钥18多轮多轮DES的特征的特征差分输入具有很高的或然性，可以直接差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到：追踪到多轮的情况，观察到：E扩展中扩展中的异或值是线性的：的异或值是线性的：异或值与密钥是无关异或值与密钥是无关的：的：192轮轮DES的特征差分密码分析的特征差分密码分析20在第一轮中，输入到函数在第一轮中，输入到函数f f的差分结果是的差分结果是 a a
11、=60 00 00 00=60 00 00 00经经f f 中的扩展变换后，中的扩展变换后，把这部分放进了每把这部分放进了每个个S S盒的中间盒的中间4 4个比特，顺序是个比特，顺序是 S1S1：6=01106=0110 S2 S2：0=00000=0000 S3,.,S8 S3,.,S8 等等等等因为所有边缘比特都是因为所有边缘比特都是0 0，所以，所以S1S1是唯一是唯一的得到非的得到非0 0差分输入的差分输入的S S盒。盒。S1S1的差分输入是的差分输入是 0 0110 0=0C 0 0110 0=0C 而其他所有盒而其他所有盒S2,.,S8S2,.,S8的差分输入都的差分输入都是是2轮
12、轮DES的特征差分密码分析的特征差分密码分析21察看察看S1S1的差分分布表，发现当输的差分分布表，发现当输入异入异或或x x=0C=0C时，最可能的差分输出时，最可能的差分输出yy是是 E=1110 E=1110，出现的概率是，出现的概率是1414/64/64；其他；其他盒的输入一定是盒的输入一定是x=0 x=0 且且 y=0 y=0盒的输入通过置换盒的输入通过置换 成为成为f(R,K)f(R,K)的输出。的输出。如前所述，如前所述，f(R,K)f(R,K)的差分输出是的差分输出是而而 AA与与LL异或后得到异或后得到 00 00 00 0000 00 00 00，因为，因为 2轮轮DES的
13、特征差分密码分析的特征差分密码分析000000001000000010000010000000101110000000000000000000000000000022所以所以,在第轮后，所有盒都得在第轮后，所有盒都得到差分输入到差分输入，产生的差分输出，产生的差分输出也是也是；f(R,K)f(R,K)的输出在轮后是的输出在轮后是，差分，差分输出则是输出则是(00 00 00 00 (00 00 00 00,60 00 00,60 00 00 00)00)2轮轮DES的特征差分密码分析的特征差分密码分析23假定：去掉初始置换假定：去掉初始置换IPIP和最终置换和最终置换FPFP。2 2轮的差分分
14、析共有个步骤。轮的差分分析共有个步骤。Step 1Step 1:产生明文对产生明文对(P,PP,P)，使得，使得办法是，随机产生一个办法是，随机产生一个P P，将其，将其与下述值进行异或得到与下述值进行异或得到P P 2轮轮DES的特征差分密码分析的特征差分密码分析24Step 2Step 2:对于产生的明文对对于产生的明文对(P,PP,P)，计算，计算加密后产生密文对加密后产生密文对(T,TT,T)（选择明文攻（选择明文攻击）击）Step 3Step 3:计算计算T=TTT=TT，检查结果是否等于检查结果是否等于如果不相等，就说明特征不符，这个明文如果不相等，就说明特征不符，这个明文对就不能
15、用。重返第一步，产生新的明文对就不能用。重返第一步，产生新的明文对；对；如果相等，则特征相符，进入第四步如果相等，则特征相符，进入第四步2轮轮DES的特征差分密码分析的特征差分密码分析25Step 4Step 4:因为因为S2,.,S8S2,.,S8的差分输入都为的差分输入都为，所以没有信息可以从，所以没有信息可以从S2S2K K,.,S8,.,S8K K得到得到。在在S1S1的差分分布表中，的差分分布表中，0C E0C E有有14/6414/64的的概率，即只有概率，即只有6464分之分之1414可以得到可以得到产生产生2轮轮DES的特征差分密码分析的特征差分密码分析这这14 14 个可能值
16、可以通过把每个可能的个可能值可以通过把每个可能的S1S1K K 与相与相应的应的S1S1E E 和和S1S1 E E 的比特相异或来确定，计算的比特相异或来确定，计算S1S1的差分输出的差分输出S1S1，检查其是否等于检查其是否等于E,E,把把S1S1K K 的这的这1414个值放进表中个值放进表中26Step 5Step 5:计算这些表的交集计算这些表的交集因为正确的密钥必定同时出现在每张表因为正确的密钥必定同时出现在每张表中中如果有不止一个如果有不止一个S1S1K K值，就说明还需要值，就说明还需要更多的明文和密文差分对才能唯一确定更多的明文和密文差分对才能唯一确定密钥密钥S1S1K K，
17、转到第一步，计算更多的数，转到第一步，计算更多的数据据需要的明文密文差分对的数量，大致等需要的明文密文差分对的数量，大致等于使用的特征概率的倒数，本例中需要于使用的特征概率的倒数，本例中需要6464/14 5/14 5对对如果只得到一个如果只得到一个S1S1K K ，就是正确的，转，就是正确的，转到第六步。到第六步。2轮轮DES的特征差分密码分析的特征差分密码分析27Step 6Step 6:这个阶段，要恢复构成这个阶段，要恢复构成S1S1K K的的6 6个个比特。比特。采用类似的特征，恢复第一轮中与采用类似的特征，恢复第一轮中与S2-S8S2-S8的输入相异或的的输入相异或的6 6比特密钥比
18、特密钥Step 7Step 7:这个阶段已经有了构成这个阶段已经有了构成S1S1K K密钥密钥的的4848比特，等同于比特，等同于S1S1K K-S8-S8K K。其余的比特密钥，采用穷举方法在其余的比特密钥，采用穷举方法在6464个可能的值中搜寻个可能的值中搜寻2轮轮DES的特征差分密码分析的特征差分密码分析差分密码分析破解差分密码分析破解DES效率效率R轮迭代密码的差分攻击步骤轮迭代密码的差分攻击步骤定义R轮迭代密码的差分攻击步骤轮迭代密码的差分攻击步骤4)重复第2、3步,直到有一个或几个计数器的值明显高于其它计数器的值,输出它们所对应的子密钥（或部分比特）。攻击成功！对r轮迭代密码的差分
19、攻击的步骤如下:线性密码线性密码分析概述 v线性密码分析的基本思想是通过寻找一个给定密码算法有效的线性近似表达式来破译密码系统。由于每个密码系统均为非线性系统，因此只能寻找线性近似表达式。v线性分析的分析者利用了包含明文、密文和子密钥的线性表达式发生的较大可能性。线性密码分析的基本方法v随机给定的明文P和相应的密文C上面的等式成立的概率p1/2线性密码分析的基本方法相关定理v线性密码分析的基本方法用堆积引理,我们可以将每轮变换中偏差最大的线性逼近式进行组合,组合后的所有轮变换的线性逼近式,也将拥有最佳的偏差,即寻找分组密码的最佳线性逼近式.由上述分析我们知道,分组密码的最佳线性逼近式的寻找,归
20、结为每轮线性逼近式的寻找,而每轮的变换中,除了非线性变换(即S-盒)部分,线性部分是自然的线性关系,也就是说,每轮线性逼近式的寻找,只需寻求S-盒部分的最佳线性逼近式.subkey K1 mixingC1.ciphertext C16 S11 S12 S13 S14subkey K2 mixing S21 S22 S23 S24subkey K3 mixing S31 S32 S33 S34subkey K4 mixingsubkey K5 mixing S41 S42 S43 S44P1.plaintext P16线性密码分析例子SPN 算法的输入为16比特的数据块，并且重复四次相同操作处理
21、数据块。v每一轮包括v1)S-box置换v2）比特变换v3）密钥混合。vS-box置换 S-box的最基本的性质是其非线性映射，S-box的输出不能通过输入的线性变换而得到。input0 1 2 3 4 5 6 7 8 9 A B C D E FoutputE 4 D 1 2 F B 8 3 A 6 C 5 9 0 7线性密码分析例子SPNinput1 2 34 5 6 7891011 1213141516output1 5 9132 610143711 15 481216 P置换（其中的数字表示比特的位置，1表示最左边的比特，16表示最右边的比特）44 S-boxX1X2X3X4Y1Y2Y3
22、Y4分析分析加密加密部件部件在下图中的S-box中 考虑表达式X2 X3 Y1 Y3 Y40或等价形式X2 X3Y1 Y3 Y4。44 S-boxX1X2X3X4Y1Y2Y3Y4线性密码分析例子SPN例子：对于16种可能的输入X和其相应的输出Y，有12种情况可以使得该式成立，因此线性可能性偏移量是12/161/21/4。相似的，对于等式X1 X4Y2其线性可能性偏移量接近于0，而等式X3 X4Y1 Y4的线性可能性偏移量是2/161/23/8。S-box线性近似采样 X1X2X3X4Y1Y2Y3Y4X2 X3Y1Y3Y4X1X4Y2X3X4Y1Y400001110000101000101000
23、0111000101101100110001100011110010100001011000001011111111110011010110100100111100001100110000011001001100110100000111010011011111010111100110101110001011111011101100110001011100000001010input0 1 2 3 4 5 6 7 8 9 A B C D E Foutput E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7线性密码分析例子SPNv 例如一个输入变量的线性近似表达式a1 X1 a2 X
24、2 a3 X3 a4 X4，其中，ai0,1。“”为二进制的“与”运算，输入行的16进制的值是a1 a2 a3 a4的组合。v 相似的，对于一个输出变量的线性近似表达式b1 Y1 b2 Y2 b3 Y3 b4 Y4，其中，bi0,1，输出行的16进制的值是b1 b2 b3 b4的组合。v 其中，Input表示表达式的输入系数，而output表示表达式的输出系数，行和列交集处的值表示以此行列值代表线性表达式成立的数量减去8。分析分析加密加密部件部件线性密码分析例子SPN线性近似偏移量 outputInput0123456789ABCDEF0+8 000000000000000100-2-2 00
25、-2+6+2+200+2+200200-2-2 00-2-200+2+200-6+2300000000+2-6-2-2+2+2-2-240+20-2-2-4-200-20+2+2-4+2050-2-20-20+4+2-20-4+20-2-2060+2-2+4+200+2 0-2+2+4-200-270-20+2+2-4+20-20+20+4+20+2800000000-2+2+2-2+2-2-2-6900-2-2 00-2-2-40-2+20+4+2-2分析分析加密加密部件部件线性密码分析例子SPN例子：线性表达式X3 X4Y1 Y4 NL(3,9)=2(3,9)=-3/8分析分析加密加密部件
26、部件线性密码分析例子SPN(a,b):表示随机变量 输入a:a=(a1,a2,a3,a4)输出b:b=(b1,b2,b3,b4)NL(a,b)：表示满足如下条件的二元8重组(x1,x2,x3,x4,y1,y2,y3,y4)的个数：(y1,y2,y3,y4)=f(x1,x2,x3,x4)并且 a1 X1 a2 X2 a3 X3 a4 X4 b1 Y1 b2 Y2 b3 Y3 b4 Y4=0偏差计算公式(a,b)=(NL(a,b)-8)/16例如：随机变量X1 X4 Y2 可以表示成（9，4）v通过构造一个关于明文和倒数第二轮输入的线性表达式v就有可能恢复出最后一轮加密使用的子密钥的一个子集，以达
27、到攻击的目的。构造加密函数的线性近似表达式线性密码分析例子SPNv 首先对于上图，有如下的S-box线性近似表达式：S12：X1 X3 X4Y2 概率为12/16，偏移量为1/4S22：X2Y2 Y4 概率为4/16，偏移量为1/4S32：X2Y2 Y4 概率为4/16，偏移量为1/4S34：X2Y2 Y4 概率为4/16，偏移量为1/4 构造加密函数的线性近似表达式线性密码分析例子SPNv令Ui(Vi)作为第i轮S-box的16比特的输入（输出），并且Uij(Vij)作为第Ui块的第j比特。v令Ki表示与第i轮输入进行XOR运算的子密钥。可知，K5表示与第四轮的输出进行XOR运算的子密钥。线
28、性密码分析例子SPN 因此，U1P K1，其中P表示16比特的明文，表示比特之间的XOR运算。利用第一轮S12的线性近似表达式，可得：V1,6U1,5 U1,7 U1,8(P5 K1,5)(P7 K1,7)(P8 K1,8)表达式成立的概率为12/16。X1 X3 X4Y2 构造加密函数的线性近似表达式v S12 V1,6U1,5 U1,7 U1,8(P5 K1,5)(P7 K1,7)(P8 K1,8)v S22 V2,6 V2,8V1,6 K2,6 联合可得：v V2,6 V2,8 P5 P7 P8 K1,5 K1,7 K1,8 K2,60 由Piling-Up引理可得其成 立 的 概 率
29、为 1/2 2(3/41/2)(1/41/2)3/8（线性偏移量为1/8）。构造加密函数的线性近似表达式线性密码分析例子SPNX2Y2 Y4 v 对于第3轮，可得到：S32 V3,6 V3,8U3,6 等式成立的概率为1/4 S34 V3,14 V3,16U3,14 等式成立的概率为1/4v 又由U3,6V2,6 K3,6 U3,14V2,8 K3,14 可得：V3,6 V3,8 V3,14 V3,16 V2,6 K3,6 V2,8 K3,140 等式成立的概率为1/22(1/41/2)25/8（线性可能性偏移量为1/8）。构造加密函数的线性近似表达式线性密码分析例子SPNv应用Piling-
30、Up引理联合V2,6 V2,8 P5 P7 P8 K1,5 K1,7 K1,8 K2,60V3,6 V3,8 V3,14 V3,16 V2,6 K3,6 V2,8 K3,140v可得构成四个S-box的线性近似表达式：V3,6 V3,8 V3,14 V3,16 P5 P7 P8 K1,5 K1,7 K1,8 K2,6 K3,6 K3,140。构造加密函数的线性近似表达式线性密码分析例子SPN计算U4,6V3,6 K4,6，U4,8V3,16 K4,8，U4,14V3,8 K4,14U4,16V3,16 K4,16可以得到：U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0，其中
31、，kK1,5 K1,7 K1,8 K2,6 K3,6 K3,14 K4,6 K4,8 K4,14 K4,16 利用Piling-Up引理，可以得出上述表达式成立的概率为1/223(3/41/2)(1/41/2)315/32（线性可能性偏移量为1/32）。构造加密函数的线性近似表达式线性密码分析例子SPNk是确定的（或者为0或者为1，取决于加密算法的密钥）。U4,6 U4,8 U4,14 U4,16 P5 P7 P80成立的概率为15/32 或者(115/32)17/32（取决于k的值是0还是1）。换句话说，现在有前三轮加密过程的一个线性近似表达式，其线性偏移量是1/32。一旦获得了有R轮加密过
32、程的加密算法的前R-1轮的线性近似表达式，且该表达式具有足够大的线性可能性偏移量，则恢复最后一轮的子密钥来攻击该密码算法是可行的。线性密码分析例子SPN把从最后一个子密钥中恢复出的密钥的一部分称为局部目标子密钥（或部分目标子密钥）。局部目标子密钥来自与最后一轮的S-box相关联的子密钥。获取密钥比特v 特别地，对于所有可能的局部目标子密钥，相应的密文比特与其进行XOR运算，运算的结果向后通过最后一轮相应的S-box进行运算。v 对所有的明文/密文对进行这种运算过程，并且设置一个计数器对每个局部目标子密钥进行计数。若对于输入到最后一轮S-box的比特和已知明文，线性近似表达式成立，则计数器增加。
33、v U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0v 一个不正确的子密钥被认为导致一个向最后一轮S-box的随机猜测输入，因而线性表达式成立的可能性非常接近1/2。获取密钥比特线性密码分析例子SPNv 线性表达式U4,6 U4,8 U4,14 U4,16 P5 P7 P80v 对于每个明文/密文对，尝试 部 分 目 标 子 密 钥K5,5.K5,8,K5,13.K5,16的256种可能。其中U5,5.U5,8,U5,13.U5,16是通过将相应的密文与子密钥K5,5.K5,8,K5,13.K5,16进行XOR运算，然后将运算结果向后经过S42，S44运算得到的。获取密钥比特
34、线性密码分析例子SPN 对每个局部目标子密钥，当表达式U4,6 U4,8 U4,14 U4,16 P5 P7 P80成立时，增加计数。若一个子密钥的计数值与明文/密文的数目的一半相差最多，被假定为正确的子密钥。(一个正确的子密钥将使得线性近似表达式成立的概率偏离1/2)v 产生 10000个已知明文/密文对，取部分子密钥K5,5.K5,80010，K5,13.K5,16 0100 来模拟前面描述的攻击。v 下表给出了部分子密钥对应的偏移量计数值（完整的应该有256条记录，每个目标子密钥对应一个），从中可以确认找到正确的子密钥。v 结合表中的数据，可以计算出线性可能性偏移量，公式如下：|bias
35、|count5000|/10000其中count表示对应的子密钥的计数值。vU4,6 U4,8 U4,14 U4,16 P5 P7 P8 k0v 从表中可以看出偏移量最大的子密钥是K5,5.K5,8,K5,13.K5,162,4，实际上，这个结果对于所有可能子密钥产生的结果也是正确的。线性攻击的实验数据 partial subkeyK5,5.K5,8,K5,13.K5,16|bias|partial subkeyK5,5.K5,8,K5,13.K5,16|bias|1C0.00312A0.00441D0.00782B0.01861E0.00712C0.00941F0.01702D0.00532
36、00.00252E0.0062210.02202F0.0133220.0211300.0027230.0064310.0050240.0336320.0075250.0106330.0162260.0096340.0218270.0074350.0052280.0224360.0056290.0054370.0048v线性近似表达式中包含的S-box称为活跃S-box。v图中，从第1轮到第3轮中被粗线条标出的四个S-box都是活跃的。v一个线性近似表达式成立的可能性，与S-box的线性可能性偏移量的大小，活跃S-box的数目有关。线性密码分析攻击的复杂度 一般情况下，这些活跃S-box的线性可
37、能性偏移量越大，整个线性近似表达式的线性可能性偏移量越大。同样，活跃S-box的线性可能性偏移量越小，整个线性表达式的线性可能性偏移量越小。一般地提高算法安全性抵抗线性分析的方法集中在优化S-box（例如，减小最大偏移量）和增加活跃S-box的数目。假如我们能够在一个明文比特子集和最后一轮即将进行代换的输入状态比特子集之间找到一个概率线性关系,换句话说,即存在一个比特子集使得其中元素的异或表现出非随机的分布（即明文和最后一轮输入的最佳线性逼近式）,再假设一个攻击者拥有大量的用同一未知密钥加密的明文密文对.对每一个明文密文对,将用所有的(最后一轮)候选密钥来对最后一轮解密密文.对每一个候选密钥,
38、计算包含在线性关系式中的相关比特的异或的值,然后确定上述的线性关系式是否成立.如果成立,就在对应于特定候选密钥的计数器上加1.在这个过程的最后,我们希望计数频率离明-密文对数的一半最远的候选密钥含有那些密钥比特的正确值.可以看到,线性攻击成功只依赖于明文的个数N和|p1/2|,并且随着N或|p 1/2|的增加而增加.要说明的是：在选择从一轮到多轮线性逼近式时，除了考虑有效性外，还需使得得到的最后关系式中，只包含明文、密文和最后一轮的密钥比特，才能实施有效攻击。线性密码分析攻击过程总结 差分密码分析和线性密码分析是目前常用于攻击迭代分组密码的方法之一，但是有些密码为了抵抗差分密码分析和线性密码分析，设计得很复杂，很难用一般的差分密码分析和线性密码分析的理论去研究，如何把差分密码分析和线性密码分析的理论应用于不同类型的密码上，也是许多学者研究的问题。
