DES的差分密码分析 网络安全 NETWORK SECURITY 差分密码分析最初是针对DES提出的一种攻击方法 它虽然未能破译16-轮的DES,但是破译轮数低的 DES是很成功的(8轮的在个人计算机上只要几分 钟)。 ·属于选择明文攻击 12
12 DES的差分密码分析 • 差分密码分析最初是针对DES提出的一种攻击方法， 它虽然未能破译16-轮的DES，但是破译轮数低的 DES是很成功的（8轮的在个人计算机上只要几分 钟）。 • 属于选择明文攻击
DES的差分密码分析原理 网络安全 NETWORK SECURITY 由于DES中的初始置换IP及其逆置换IP1是公开的，所以在密码分析时 可以忽略。设n轮DES,LoR为明文，LnRn为密文，差分分析的基本观 点是比较两个明文的异或与相应的两个密文的异或。 。 定义6设S是一个特定的S-盒(1≤j≤8)，(BB;*)是一对长度为6比特的 串。我们说S的输入异或是B⊕B;*,S的输出异或是S(B)田S(B;*)。 对于任何B∈Z25,记△(B)={(BB*)1B⊕B;*=Bj}。易知，I△(B)川 =26=64,且△(B)={(B,B⊕B)1B1∈Z2}。对△(B)中的每一对， 我们能计算出S的一个输出异或，共可计算出64个输出异或，它们分布 在24=16个可能的值上，将这些分布列成表。这些分布的不均匀性将是 差分密码攻击的基础。 13
13 DES的差分密码分析原理 • 由于DES中的初始置换IP及其逆置换IP-1是公开的，所以在密码分析时 可以忽略。设n轮DES，L0R0为明文，LnRn为密文，差分分析的基本观 点是比较两个明文的异或与相应的两个密文的异或。 • 定义6 设Sj是一个特定的S-盒(1j 8)，(Bj , Bj *)是一对长度为6比特的 串。我们说Sj的输入异或是BjBj * ， Sj的输出异或是Sj(Bj) Sj(Bj *)。 • 对于任何Bj ’Z2 6，记(Bj ’)={(Bj ,Bj *)|BjBj *=Bj’}。易知，|(Bj ’)| =26 =64，且(Bj ’)={(Bj , BjBj ’)|BjZ2 6}。对(Bj ’)中的每一对， 我们能计算出Sj的一个输出异或，共可计算出64个输出异或，它们分布 在24=16个可能的值上，将这些分布列成表。这些分布的不均匀性将是 差分密码攻击的基础
DES的差分密码分析原理 网络安全 NETWORK SECURITY 例1设第一个S盒S1的输入异或为110100，那么△(110100)={(0000 00,110100),(000001,110101),.,(111111,001011)}。对集合 △(110100)中的每一个有序对，计算S1的输出异或，获得输出异或分布 0000 0001 0010 0011 0100 0101 0110 011 8 16 6 2 0 0 12 1000 1001 1010 1011 1100 1101 1110 1111 6 0 0 0 8 0 6 一 般，如果我们固定一个S-盒S和一个输入异或B',那么平均来讲，所 有可能的输出异或中实际上出现大约75%-80%。 定义7对于1≤j≤8，长度为6比特的串B'和长度为4比特的串C',定义 INj(Bj',C)={BjEZ26ISj(Bi)Sj(BjBj)=C},Nj(Bj',Cj)=|INj(Bj C)川，表示对S盒S具有输入异或为B',输出异或为C的对的数量。 14
14 DES的差分密码分析原理 • 例1 设第一个S盒S1的输入异或为110100，那么(110100)={(0000 00, 110100),(000001,110101),…,(111111,001011)}。对集合 (110100)中的每一个有序对，计算S1的输出异或，获得输出异或分布 • 一般，如果我们固定一个S-盒Sj和一个输入异或Bj ’，那么平均来讲，所 有可能的输出异或中实际上出现大约75%-80%。 • 定义7 对于1j8，长度为6比特的串Bj ’和长度为4比特的串Cj ’，定义 INj(Bj ’, Cj ’)={BjZ2 6|Sj(Bj)Sj(BjBj ’)=Cj ’}，Nj(Bj ’,Cj ’)=|INj(Bj ’ , Cj ’)|，表示对S盒Sj具有输入异或为Bj ’，输出异或为Cj ’的对的数量
DES的差分密码分析原理 网络安全 对于8个S盒，每一个都有64个可能的输入异或，共需拼釁芬 布，可以通过计算机很容易地算出。如IN1(110100,C1')的分布为 的出抖戏 能的输，入 00( 0001 000011,001113,011112,011111101010.lU1U11,1101」1,111011 0001 000011.001111,011110,011111101010,101011,110111,111011 000100,00101,001110.01000101(0010.010100+01101(0.U11)l1 0010 10000.1(00101,0101110,401}10上01111，上10000,110001,111010 0011 000001,000010,010101+100001110401,110110 0100 010011,100111 0101 0110 0心0000,001000,001101,0101111011900,011101,100011,101001 0111 101100,1101(00.111001.t11100 1000 001001,001100,017091,1011)111000、11上101 1001 1070 1011 11t0 1101 000110,31(0000,910110,01110U1U0010,100100,101000,110010 111U 1111 0001170)1010、001011、11Uw上111110,111111
15 DES的差分密码分析原理 • 对于8个S盒，每一个都有64个可能的输入异或，共需计算512个分 布，可以通过计算机很容易地算出。如IN1(110100, C1 ’)的分布为