对1≤8,长度为6bi的串a和长度为4bi的串b可和b 为给定的差分,分别是输入差分和输出差分) 定义3.2:IN(aj,bj)={Bj∈Z2Sj(Bj)由SjBj曲aj)=bj}, Nj(aj,bj)=INj(aj, bj) N(ajb)是S盒S具有输入异或a和输出异或b的明文 对数量。书上给出的是IN(110100,b)(bj∈Z24) 对8个S盒中的每一个,都有64个可能的输入异或,所 以共需计算512个分布,这可通过利用计算机得到。 在DES中,第谛轮S盒的输入可表示为B=E⊕J,其中 E=E(R1)是R1的扩展,J=K为第轮的工作密钥。输入 异或BAB=EAJ(E*J=EE*。输入异或与工作密 钥无关。但输出异或则与工作密钥有关。 B=B1B2B3B4B5BB2B3(48bi每个B为6bi
对 1 j 8，长度为6bit的串aj和长度为4bit的串bj(aj 和bj 为给定的差分，分别是输入差分和输出差分 ) 定义3.2：INj(aj,bj)={Bj Z 2 6|Sj(Bj) Sj(Bj aj)=bj}， Nj(aj,bj)=|INj(aj,bj)| Nj(aj,bj) 是S- 盒Sj具有输入异或aj和输出异或bj的明文 对数量。书上给出的是IN1(110100,bj)(bj Z 2 4 ) 对 8 个 S盒中的每一个，都有64个可能的输入异或，所 以共需计算512个分布，这可通过利用计算机得到。 在DES中，第 i 轮S-盒的输入可表示为B=E J，其中 E=E(Ri-1 ) 是 Ri-1的扩展，J=Ki为第 i轮的工作密钥。输入 异或 B B*=(E J) (E* J)=E E*。输入异或与工作密 钥无关。但输出异或则与工作密钥有关。 B=B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8(48bit,每个 Bi 为6bit)
E三E1E2E3E4E5E6E8 102304506708 B,E*也类似表示 攻击的目的是获得工作密钥,由此导出主密 钥。 假定对某个j(18)知道E和E的值,以及 S的输出异或b=S(BjS(B)Bj*= Bjeaj) INEi,b)={Pj∈Z2°Sj(Pj)⊕Sj(Pj⊕Ei)=bj}, 这里Ej=EjE。则正确的加密结果 EjJj∈INj(E'j,bj)
E=E 1 E 2 E 3 E 4 E 5 E 6 E 7 E 8 J=J 1 J 2 J 3 J 4 J 5 J 6 J 7 J 8 B *,E *也类似表示 攻击的目的是获得工作密钥，由此导出主密 钥。 假定对某个j(1 j 8)知道Ej 和Ej*的值，以及 Sj的输出异或bj=Sj(Bj) Sj(Bj*)(Bj*=Bj aj) 。 INj(E'j,bj)={Pj Z 2 6|Sj(Pj) Sj(Pj E'j)=bj} ， 这里E'j= Ej Ej*。则正确的加密结果 Ej Jj INj(E'j,bj)
tes(Ej,Ej,bj)={Bj⊕EjBj∈INj(Ej}。该集合是所有 j(Eib)中元素与E异或的值全体,故元素个数为 IINjCEj, bJNI(Ej,bj) 由于EJ∈INE,b,所以(EJ)E∈test(E,E,b), 即J;∈test(E;,E,b) 因此test(EiEj,b)中必有正确的工作密钥。 例3:设E1=00000,E1*=110101,b1=1101。故EI E1E1*=110100。 因为N(E1,b1)=8,故test(E"1,E1*,b1)有8个元素。从表中 可知IN(110100,1101 ={000110,010000,010110,011100,100010,100100,101000,11001 0},所以可以求得 testI(E'1,E1x,b1)={000111,010001,01011,011101,100011,100 101,101001,110011
testj(Ej,Ej*,bj)={Bj Ej|Bj INj(E'j,bj)}。该集合是所有 INj(E'j,bj)中元素与Ej异或的值全体，故元素个数为 |INj(E'j,bj)|=N1(E'j,bj) 。 由于 Ej Jj INj(E‘j,bj),所以(Ej Jj ) Ej testj(Ej,Ej *,bj )， 即 Jj testj(Ej,Ej*,bj ) 。 因此testj(E'j,Ej*,bj)中必有正确的工作密钥。 例3.2：设E1=000001,E1*=110101, b1=1101。故E1'= E1 E1*=110100 。 因为N1(E1',b1)=8，故test1(E'1,E1*,b1) 有 8个元素。从表中 可知IN1(110100,1101) ={000110,010000,010110,011100,100010,100100,101000,11001 0},所以可以求得 test1(E'1,E1*,b1)={000111,010001,010111,011101,100011,100 101,101001,110011}
如果还有第2组这样的三元组(E1,E1,b1 就可获得包含工作密钥J的第2个 test1,自 然』是这两个集合的交的元素。 ■如果拥有一系列三元组,就可确定J1。最直 接的方法是:建立一个有64个计数器的矩阵 记录工作密钥J1的64种可能情况。每计算 次test1,如果某些元素6bi在test中,则这 些元素所对应的计数器加1,否则不变。给 定个三元组(E1,E1,b1),希望能找到唯 的计数器,使得其值为t,则该计数器所对应 的6bit就是工作密钥J1
如果还有第 2组这样的三元组(E‘1,E1*,b1) ， 就可获得包含工作密钥J1的第 2 个test1，自 然J1是这两个集合的交的元素。 如果拥有一系列三元组，就可确定J1。最直 接的方法是：建立一个有64个计数器的矩阵， 记录工作密钥J1 的64种可能情况。每计算一 次test1，如果某些元素(6bit) 在test1中，则这 些元素所对应的计数器加 1，否则不变。给 定 t个三元组(E'1,E1*,b1)，希望能找到唯一 的计数器，使得其值为 t，则该计数器所对应 的6bit就是工作密钥J1
■对一个r轮迭代密码的差分分析攻击基本步骤是 (1)寻找第r-1轮差分(a,b)使概率 P(b=△X(r-1)a=△B)的值尽可能为最大。 (2)随机选择明文B,求另一明文B',使得B与B的差 分为a。 ◆(3)在密钥k下对B和B进行加密得到X(r)和X'(r), 并求出能使△X(r-1)=b的所有可能的第r轮密钥kr 并对各子密钥k(计数, 若选定的△B=a,明文对(B,B)在k(下产生的(X,X) 满足△X(r-1)=b,就将相应的k(的计数加1 (4)重复(2)、(3)步,直到计数的某个或几个字符串的 值,明显大于其他字符串的计数值,这一字符串或 几个子密钥就可作为对实际子密钥k的分析结果
对一个 r轮迭代密码的差分分析攻击基本步骤是： (1)寻找第r-1轮差分(a,b)使概率 P(b= X(r-1)|a= B)的值尽可能为最大。 (2)随机选择明文 B，求另一明文B'，使得 B 与B'的差 分为 a 。 (3)在密钥 k下对 B 和B'进行加密得到X(r) 和X'(r)， 并求出能使 X(r-1)=b的所有可能的第 r轮密钥 k(r)， 并对各子密钥 k i(r)计数， 若选定的 B=a，明文对(B,B') 在 k i(r)下产生的(X,X') 满足 X(r-1)=b，就将相应的 k i(r)的计数加 1 。 (4)重复(2) 、(3)步，直到计数的某个或几个字符串的 值，明显大于其他字符串的计数值，这一字符串或 几个子密钥就可作为对实际子密钥 k r的分析结果