差分密码分析和线性密码分析原理.ppt

差分密码分析和线性密码分析原理CONTENTS0102差分密码分析线性密码分析PART ONE差分密码分析u差分密码分析差分密码分析是迄今为止已知的攻击迭代分组密码最有效的方法是迄今为止已知的攻击迭代分组密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值来之一，其基本思想是：通过分析明文对的差值对密文对的差值来影响来恢复某些密钥比特影响来恢复某些密钥比特u当当密码分析人员可以进行选择明文分析时，差分密码分析十分有密码分析人员可以进行选择明文分析时，差分密码分析十分有效。效。u已知明文的差分密码分析也是可行的，但是要求已知明密文的量已知明文的差分密码分析也是可行的，但是要求已知明密文的量很大很大差分密码分析简介设计DES的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)表示密文对，其异或后得到特定的值表示密文对，其异或后得到特定的值T T，使得使得 T T=T T=T T u带撇的值带撇的值总是总是表示表示差分，差分，P P,T T,a a,A A。例如，例如，a a=a a=a a 7差分密码分析_DESDES DES 的设计要求之一是确保尽可能的分的设计要求之一是确保尽可能的分布均匀布均匀例如，明文或密钥的例如，明文或密钥的1 1比特变化，将导比特变化，将导致致6464比特的密文中大约比特的密文中大约3232比特的看起来比特的看起来是不可预测和随机的变化是不可预测和随机的变化不过对于不过对于固定的密钥，固定的密钥，DESDES的差分并不呈现伪的差分并不呈现伪随机现象随机现象即对于固定明文即对于固定明文P P 和和P P 的异或的异或P PT T=TT=TT 不是均匀分布的不是均匀分布的8S-Box是非差分均匀的是非差分均匀的对于输入对于输入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=y y=y y =S(x)S(x=S(x)S(x)输出差分值有多少种可能？输出差分值有多少种可能？642=642=4096 4096 2626=64642 24 4=1616S-Box是非差分均匀的是非差分均匀的x01 23456789abcdefxfffe dcba9876543210S(x)e4 d12fb83a6c5907S(xff)70 95c6a38bf21d4ES(x)S(xff)94 44e91bb19e4449输入差分输入差分f f=1111=111110S1 的差分分布表的差分分布表.=26-=26-1 1出出现的的次次数数u6 6比特的差分输入比特的差分输入x x有有6464个值：个值：00-3F00-3F(16(16进制，进制，1010进制是进制是0-630-63)u4 4比特的差分输出比特的差分输出y y有有1616个值：个值：0-F0-F(16(16进制，进制，1010进制是进制是0-150-15)u可以看到：第一行除第一列外可以看到：第一行除第一列外全为全为0 0，因为当，因为当x x=x x=x x =0=0，同样的输入出现了两次，因同样的输入出现了两次，因此其输出此其输出y y=y y=y y =0=0u后面的行：后面的行：u例如，当例如，当 x x=01=01 时时,6 6个可能个可能的的y y中有中有5 5个值个值:0,1,2,4,80,1,2,4,8呈现呈现0 0可能次数，就是说不出现。可能次数，就是说不出现。uA A 出现的概率是出现的概率是12/6412/64u9 9 和和C C 出现的概率是出现的概率是10/6410/64u这就是说，这就是说，S1S1呈现出很强的不呈现出很强的不均匀分布均匀分布u这种差分不均匀性对于所有的这种差分不均匀性对于所有的S S盒盒S1,S2,.,S8S1,S2,.,S8都有体现都有体现u考虑输入异或值为考虑输入异或值为3434时，时，可能的输出异或是可能的输出异或是：u其中其中：34344 4有两种可能，有两种可能，这种输入对是成双的，即：这种输入对是成双的，即：(,)和和 (,)S1 的差分分布表的差分分布表对对S1S1构建差分表，发现当输构建差分表，发现当输入是入是13 13 和和27 27 时时(只看后面的只看后面的6 6位位)：12S1 的差分分布表的差分分布表12列出列出S1S1中输入中输入异或值为异或值为3434的的可能的输入可能的输入值值(16(16进制进制)：13确定密钥的原理确定密钥的原理假设已知假设已知S1S1的两个输入是的两个输入是0101和和3535，其异或的结果是，其异或的结果是3434，经过，经过S1S1之后之后输出异或的结果是输出异或的结果是D D。查。查S1S1的差分分布表，得到输入异或为的差分分布表，得到输入异或为3434，输，输出异或为出异或为D D时，可能的输入：时，可能的输入：14确定密钥的原理确定密钥的原理14实际上，输入异或的结果是实际上，输入异或的结果是3434，与密，与密钥无关，这是因为：钥无关，这是因为：因为因为所以所以这样就得到：这样就得到：所以，可能的密钥就是所以，可能的密钥就是15确定密钥的原理确定密钥的原理此外，假设已知此外，假设已知S1S1的两个输入是的两个输入是2121和和1515，它们异或后的结果是，它们异或后的结果是3434，输出异或后的结果是输出异或后的结果是3 3 。查。查S1S1的差分分布表，得到输入异或为的差分分布表，得到输入异或为3434，输出异或为输出异或为3 3时，可能的输入：时，可能的输入：。16确定密钥的原理确定密钥的原理16这样就可以从这样就可以从得到可能的密钥值得到可能的密钥值17确定密钥的原理确定密钥的原理17而正确的密钥值必定同时出现在两个集合而正确的密钥值必定同时出现在两个集合因此可以确定密钥是在因此可以确定密钥是在 中中的一个。的一个。要确定到底是哪一个，需要知道更多的输入输出异或要确定到底是哪一个，需要知道更多的输入输出异或对对。以此类推得到此轮密钥。以此类推得到此轮密钥18多轮多轮DES的特征的特征差分输入具有很高的或然性，可以直接追踪到多轮的情况，差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到：观察到：E扩展中的异或值是线性的：扩展中的异或值是线性的：异或值与密钥是无关的：异或值与密钥是无关的：192轮轮DES的特征差分密码分析的特征差分密码分析20在第一轮中，输入到函数在第一轮中，输入到函数f f的差分结果是的差分结果是 a a=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轮轮DES的特征差分密码分析的特征差分密码分析21察看察看S1S1的差分分布表，发现当输入异的差分分布表，发现当输入异或或x x=0C=0C时，最可能的差分输出时，最可能的差分输出y y是是 E=1110 E=1110，出现的概率是出现的概率是1414/64/64；其他；其他盒的输入一定是盒的输入一定是x x=0 0 且且 y y=0=0盒的输入通过置换盒的输入通过置换 成为成为f(R,K)f(R,K)的输出。的输出。如前所述，如前所述，f(R,K)f(R,K)的差分输出是的差分输出是而而 A A与与L L异或后得到异或后得到 00 00 00 0000 00 00 00，因为，因为 2轮轮DES的特征差分密码分析的特征差分密码分析000000001000000010000010000000101110000000000000000000000000000022所以所以,在第轮后，所有盒都得到差分输入在第轮后，所有盒都得到差分输入，产生的差分输出也是产生的差分输出也是；f(R,K)f(R,K)的输出在轮后是的输出在轮后是，差分输出则是，差分输出则是(00 00 (00 00 00 00 00 00,60 00 00 00),60 00 00 00)2轮轮DES的特征差分密码分析的特征差分密码分析23假定：去掉初始置换假定：去掉初始置换IPIP和最终置换和最终置换FPFP。2 2轮的差分分析共有轮的差分分析共有个步骤。个步骤。Step 1Step 1:产生明文对产生明文对(P,PP,P)，使得，使得办法是，随机产生一个办法是，随机产生一个P P，将其与下述值进行异，将其与下述值进行异或得到或得到P P 2轮轮DES的特征差分密码分析的特征差分密码分析24Step 2Step 2:对于产生的明文对对于产生的明文对(P,PP,P)，计算加密后产生密文对，计算加密后产生密文对(T,T,T T)（选择明文攻击）（选择明文攻击）Step 3Step 3:计算计算T T=TT=TT，检查结果是否等于检查结果是否等于如果不相等，就说明特征不符，这个明文对就不能用。重返第如果不相等，就说明特征不符，这个明文对就不能用。重返第一步，产生新的明文对；一步，产生新的明文对；如果相等，则特征相符，进入第四步如果相等，则特征相符，进入第四步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 个可能值可以通过把每个可能的个可能值可以通过把每个可能的S1S1K K 与相应的与相应的S1S1E E 和和S1S1 E E 的比的比特相异或来确定，计算特相异或来确定，计算S1S1的差分输出的差分输出S1S1，检查其是否等于检查其是否等于E,E,把把S1S1K K 的这的这1414个值放进表中个值放进表中26Step 5Step 5:计算这些表的交集计算这些表的交集因为正确的密钥必定同时出现在每张表中因为正确的密钥必定同时出现在每张表中如果有不止一个如果有不止一个S1S1K K值，就说明还需要更多的明文和密文值，就说明还需要更多的明文和密文差分对才能唯一确定密钥差分对才能唯一确定密钥S1S1K K，转到第一步，计算更多的，转到第一步，计算更多的数据数据需要的明文密文差分对的数量，大致等于使用的特征概率需要的明文密文差分对的数量，大致等于使用的特征概率的倒数，本例中需要的倒数，本例中需要6464/14 5/14 5对对如果只得到一个如果只得到一个S1S1K K ，就是正确的，转到第六步。，就是正确的，转到第六步。2轮轮DES的特征差分密码分析的特征差分密码分析27Step 6Step 6:这个阶段，要恢复构成这个阶段，要恢复构成S1S1K K的的6 6个比特。个比特。采用类似的特征，恢复第一轮中与采用类似的特征，恢复第一轮中与S2-S8S2-S8的输入相异或的的输入相异或的6 6比比特密钥特密钥Step 7Step 7:这个阶段已经有了构成这个阶段已经有了构成S1S1K K密钥的密钥的4848比特，等同于比特，等同于S1S1K K-S8-S8K K。其余的比特密钥，采用穷举方法在其余的比特密钥，采用穷举方法在6464个可能的值中搜寻个可能的值中搜寻2轮轮DES的特征差分密码分析的特征差分密码分析差分密码分析破解差分密码分析破解DES效率效率R轮迭代密码的差分攻击步骤轮迭代密码的差分攻击步骤定义R轮迭代密码的差分攻击步骤轮迭代密码的差分攻击步骤4)重复第2、3步,直到有一个或几个计数器的值明显高于其它计数器的值,输出它们所对应的子密钥（或部分比特）。攻击成功！对r轮迭代密码的差分攻击的步骤如下:PART TWO线性密码线性密码分析概述线性密码分析的基本思想是通过寻找一个给定密码算法有效的线性近似表达式来破译密码系统。由于每个密码系统均为非线性系统，因此只能寻找线性近似表达式。线性分析的分析者利用了包含明文、密文和子密钥的线性表达式发生的较大可能性。线性密码分析的基本方法随机给定的明文P和相应的密文C上面的等式成立的概率p1/2线性密码分析的基本方法相关定理线性密码分析的基本方法用堆积引理,我们可以将每轮变换中偏差最大的线性逼近式进行组合,组合后的所有轮变换的线性逼近式,也将拥有最佳的偏差,即寻找分组密码的最佳线性逼近式.由上述分析我们知道,分组密码的最佳线性逼近式的寻找,归结为每轮线性逼近式的寻找,而每轮的变换中,除了非线性变换(即S-盒)部分,线性部分是自然的线性关系,也就是说,每轮线性逼近式的寻找,只需寻求S-盒部分的最佳线性逼近式.subkeyK1mixingC1.ciphertextC16S11S12S13S14subkeyK2mixingS21S22S23S24subkeyK3mixingS31S32S33S34subkeyK4mixingsubkeyK5mixingS41S42S43S44P1.plaintextP16线性密码分析例子SPN算法的输入为16比特的数据块，并且重复四次相同操作处理数据块。每一轮包括1)S-box置换2）比特变换3）密钥混合。S-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 15481216P置换（其中的数字表示比特的位置，1表示最左边的比特，16表示最右边的比特）44S-boxX1X2X3X4Y1Y2Y3Y4分析加密部件在下图中的S-box中考虑表达式X2X3Y1Y3Y40或等价形式X2X3Y1Y3Y4。44S-boxX1X2X3X4Y1Y2Y3Y4线性密码分析例子SPN例子：对于16种可能的输入X和其相应的输出Y，有12种情况可以使得该式成立，因此线性可能性偏移量是12/161/21/4。相似的，对于等式X1X4Y2其线性可能性偏移量接近于0，而等式X3X4Y1Y4的线性可能性偏移量是2/161/23/8。S-box线性近似采样X1X2X3X4Y1Y2Y3Y4X2X3Y1Y3Y4X1X4Y2X3X4Y1Y400001110000101000101000011100010110110011000110001111001010000101100000101111111111001101011010010011110000110011000001100100110011010000011101001101111101011110011010111000101111101110110011000101110000000101011110111000101input0 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线性密码分析例子SPN例如一个输入变量的线性近似表达式a1X1a2X2a3X3a4X4，其中，ai0,1。“”为二进制的“与”运算，输入行的16进制的值是a1a2a3a4的组合。相似的，对于一个输出变量的线性近似表达式b1Y1b2Y2b3Y3b4Y4，其中，bi0,1，输出行的16进制的值是b1b2b3b4的组合。其中，Input表示表达式的输入系数，而output表示表达式的输出系数，行和列交集处的值表示以此行列值代表线性表达式成立的数量减去8。分析加密部件线性密码分析例子SPN线性近似偏移量 outputInput0123456789ABCDEF0+8 000000000000000100-2-2 00-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-2A 0+4-2+2-40+2-2+2+200+2+200B 0+40-4+40+4000000000C 0-2+4-2-20+20+20+2+40+20-2D 0+2+20-2+4 0+2-4-2+20+200+2E0+2+20-2-4 0+2-200-2-4+2-20F0-2-4-2-20+200-2+4-2-20+20分析加密部件线性密码分析例子SPN例子：线性表达式X3X4Y1Y4NL(3,9)=2(3,9)=-3/8分析加密部件线性密码分析例子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)并且a1X1a2X2a3X3a4X4b1Y1b2Y2b3Y3b4Y4=0偏差计算公式(a,b)=(NL(a,b)-8)/16例如：随机变量X1X4Y2可以表示成（9，4）通过构造一个关于明文和倒数第二轮输入的线性表达式就有可能恢复出最后一轮加密使用的子密钥的一个子集，以达到攻击的目的。构造加密函数的线性近似表达式线性密码分析例子SPN首先对于上图，有如下的S-box线性近似表达式：S12：X1X3X4Y2概率为12/16，偏移量为1/4S22：X2Y2Y4概率为4/16，偏移量为1/4S32：X2Y2Y4概率为4/16，偏移量为1/4S34：X2Y2Y4概率为4/16，偏移量为1/4构造加密函数的线性近似表达式线性密码分析例子SPN令Ui(Vi)作为第i轮S-box的16比特的输入（输出），并且Uij(Vij)作为第Ui块的第j比特。令Ki表示与第i轮输入进行XOR运算的子密钥。可知，K5表示与第四轮的输出进行XOR运算的子密钥。线性密码分析例子SPN因此，U1PK1，其中P表示16比特的明文，表示比特之间的XOR运算。利用第一轮S12的线性近似表达式，可得：V1,6U1,5U1,7U1,8(P5K1,5)(P7K1,7)(P8K1,8)表达式成立的概率为12/16。X1 X3 X4Y2 构造加密函数的线性近似表达式S12V1,6U1,5U1,7U1,8(P5K1,5)(P7K1,7)(P8K1,8)S22V2,6V2,8V1,6K2,6联合可得：V2,6V2,8P5P7P8K1,5K1,7K1,8K2,60由Piling-Up引理可得其成 立 的 概 率 为 1/22(3/41/2)(1/41/2)3/8（线性偏移量为1/8）。构造加密函数的线性近似表达式线性密码分析例子SPNX2Y2 Y4 对于第3轮，可得到：S32V3,6V3,8U3,6等式成立的概率为1/4S34V3,14V3,16U3,14等式成立的概率为1/4又由U3,6V2,6K3,6U3,14V2,8K3,14可得：V3,6V3,8V3,14V3,16V2,6K3,6V2,8K3,140等式成立的概率为1/22(1/41/2)25/8（线性可能性偏移量为1/8）。构造加密函数的线性近似表达式线性密码分析例子SPN应用Piling-Up引理联合V2,6V2,8P5P7P8K1,5K1,7K1,8K2,60V3,6V3,8V3,14V3,16V2,6K3,6V2,8K3,140可得构成四个S-box的线性近似表达式：V3,6V3,8V3,14V3,16P5P7P8K1,5K1,7K1,8K2,6K3,6K3,140。构造加密函数的线性近似表达式线性密码分析例子SPN计算U4,6V3,6K4,6，U4,8V3,16K4,8，U4,14V3,8K4,14U4,16V3,16K4,16可以得到：U4,6U4,8U4,14U4,16P5P7P8k0，其中，kK1,5K1,7K1,8K2,6K3,6K3,14K4,6K4,8K4,14K4,16利用Piling-Up引理，可以得出上述表达式成立的 概 率 为 1/2 23(3/4 1/2)(1/4 1/2)315/32（线性可能性偏移量为1/32）。构造加密函数的线性近似表达式线性密码分析例子SPNk是确定的（或者为0或者为1，取决于加密算法的密钥）。U4,6U4,8U4,14U4,16P5P7P80成立的概率为15/32或者(115/32)17/32（取决于k的值是0还是1）。换句话说，现在有前三轮加密过程的一个线性近似表达式，其线性偏移量是1/32。一旦获得了有R轮加密过程的加密算法的前R-1轮的线性近似表达式，且该表达式具有足够大的线性可能性偏移量，则恢复最后一轮的子密钥来攻击该密码算法是可行的。线性密码分析例子SPN把从最后一个子密钥中恢复出的密钥的一部分称为局部目标子密钥（或部分目标子密钥）。局部目标子密钥来自与最后一轮的S-box相关联的子密钥。获取密钥比特特别地，对于所有可能的局部目标子密钥，相应的密文比特与其进行XOR运算，运算的结果向后通过最后一轮相应的S-box进行运算。对所有的明文/密文对进行这种运算过程，并且设置一个计数器对每个局部目标子密钥进行计数。若对于输入到最后一轮S-box的比特和已知明文，线性近似表达式成立，则计数器增加。U4,6U4,8U4,14U4,16P5P7P8k0一个不正确的子密钥被认为导致一个向最后一轮S-box的随机猜测输入，因而线性表达式成立的可能性非常接近1/2。获取密钥比特线性密码分析例子SPN线性表达式U4,6 U4,8 U4,14U4,16P5P7P80对于每个明文/密文对，尝试 部 分 目 标 子 密 钥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运算得到的。获取密钥比特线性密码分析例子SPN对每个局部目标子密钥，当表达式U4,6 U4,8U4,14U4,16P5P7P80成立时，增加计数。若一个子密钥的计数值与明文/密文的数目的一半相差最多，被假定为正确的子密钥。(一个正确的子密钥将使得线性近似表达式成立的概率偏离1/2)产生10000个已知明文/密文对，取部分 子 密 钥 K5,5.K5,8 0010，K5,13.K5,160100来模拟前面描述的攻击。下表给出了部分子密钥对应的偏移量计数值（完整的应该有256条记录，每个目标子密钥对应一个），从中可以确认找到正确的子密钥。结合表中的数据，可以计算出线性可能性偏移量，公式如下：|bias|count5000|/10000其中count表示对应的子密钥的计数值。U4,6U4,8U4,14U4,16P5P7P8k0从表中可以看出偏移量最大的子密钥是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.0053200.00252E0.0062210.02202F0.0133220.0211300.0027230.0064310.0050240.0336320.0075250.0106330.0162260.0096340.0218270.0074350.0052280.0224360.0056290.0054370.0048线性近似表达式中包含的S-box称为活跃S-box。图中，从第1轮到第3轮中被粗线条标出的四个S-box都是活跃的。一个线性近似表达式成立的可能性，与S-box的线性可能性偏移量的大小，活跃S-box的数目有关。线性密码分析攻击的复杂度一般情况下，这些活跃S-box的线性可能性偏移量越大，整个线性近似表达式的线性可能性偏移量越大。同样，活跃S-box的线性可能性偏移量越小，整个线性表达式的线性可能性偏移量越小。一般地提高算法安全性抵抗线性分析的方法集中在优化S-box（例如，减小最大偏移量）和增加活跃S-box的数目。假如我们能够在一个明文比特子集和最后一轮即将进行代换的输入状态比特子集之间找到一个概率线性关系,换句话说,即存在一个比特子集使得其中元素的异或表现出非随机的分布（即明文和最后一轮输入的最佳线性逼近式）,再假设一个攻击者拥有大量的用同一未知密钥加密的明文密文对.对每一个明文密文对,将用所有的(最后一轮)候选密钥来对最后一轮解密密文.对每一个候选密钥,计算包含在线性关系式中的相关比特的异或的值,然后确定上述的线性关系式是否成立.如果成立,就在对应于特定候选密钥的计数器上加1.在这个过程的最后,我们希望计数频率离明-密文对数的一半最远的候选密钥含有那些密钥比特的正确值.可以看到,线性攻击成功只依赖于明文的个数N和|p1/2|,并且随着N或|p1/2|的增加而增加.要说明的是：在选择从一轮到多轮线性逼近式时，除了考虑有效性外，还需使得得到的最后关系式中，只包含明文、密文和最后一轮的密钥比特，才能实施有效攻击。线性密码分析攻击过程总结差分密码分析和线性密码分析是目前常用于攻击迭代分组密码的方法之一，但是有些密码为了抵抗差分密码分析和线性密码分析，设计得很复杂，很难用一般的差分密码分析和线性密码分析的理论去研究，如何把差分密码分析和线性密码分析的理论应用于不同类型的密码上，也是许多学者研究的问题。谢谢聆听谢谢聆听THANKS