3.4密码攻击方法 3.42差分密码分析法 ■差分密码分析是采用选择明文统计分析 来攻击迭代分组密码的。 ■它主要分析明文差分和密文差分之间的 统计相关性
3.4 密码攻击方法 3.4.2差分密码分析法 差分密码分析是采用选择明文统计分析 来攻击迭代分组密码的。 它主要分析明文差分和密文差分之间的 统计相关性
■对于给定的r轮迭代密码,对已知分组长为n 的明文对B和B‘,其差分△B=B⑧B-1,其中⑧ 是所有n-bi构成的集合中所定义的群运算, B4-1是B在群中的逆元。 在密钥k控制下,各轮迭代所产生的中间密文 差分为: △X(i)=x(i)(x(i)10≤i≤r 当i=0时,X(0)=B,X(O=B',△X(0)=△B,而 最终的密文差分△X=△X(r) 由于明文对B≠B',故△X(i)≠e(群的单位元), 即△X(i)∈{0,1}n-{e}o 每轮迭代所用子密钥k与明文统计独立,并认 为是服从均匀分布的
对于给定的 r轮迭代密码，对已知分组长为 n 的明文对 B 和B‘，其差分 B=B B’-1，其中 是所有n-bit构成的集合中所定义的群运算， B‘-1 是B’在群中的逆元。 在密钥 k控制下，各轮迭代所产生的中间密文 差分为： X(i)=X(i) (X'(i))-1 0 ≤ i ≤ r 当i=0时，X(0)=B，X'(0)=B'，X(0)= B，而 最终的密文差分 X= X(r) 。 由于明文对 B B'，故 X(i) e(群的单位元 )， 即 X(i) {0,1} n-{e} 。 每轮迭代所用子密钥 k i与明文统计独立，并认 为是服从均匀分布的
■定义31:设a是两个不同明文B和B'的差分,b 是密码第轮输出X(i)和X()之间的差分,称 (a,b)为第轮差分。在给定明文的差分=△B条 件下,第轮出现一对输出的差分是b的概率称 为第论轮差分概率,记为P(b=△X(i)a=△B) ■以DES加密1轮为例了解差分分析攻击的过程
定义3.1：设 a是两个不同明文 B 和B'的差分， b 是密码第 i轮输出X(i) 和X'(i)之间的差分，称 (a,b)为第 i轮差分。在给定明文的差分a= B 条 件下，第 i轮出现一对输出的差分是 b的概率称 为第 i轮差分概率，记为P(b= X(i)|a= B) 。 以DES加密 1轮为例了解差分分析攻击的过程
DES的关键是S盒,设S是一个特定的S盒(is8 (B;B是一对长度为6b的串。B④B*作为S的输 入异或,S(BBS(B则为S的输出异或。 首先考虑对给定的a1∈Z26,把所有异或值为1的 (B,B“)拿来构成集合,即△(a)=(B,B1)B田B:*=a}。 △(a1)=2=64, 因为BB1=a;,所以B=Ba;,即 △(a)={(B,Ba)B1∈Z2} 对△(a)中的每一对,计算出S;的一个输出异或 共可计算出64个输出异或, S盒输出是4bit,只有24=16个可能的输出值 即64个输出异或分布在16个可能值上, 将这些分布列成表,分布的不均匀性就是差分攻击 的基础
DES的关键是 S盒，设 S j是一个特定的S- 盒(1 j 8)， (B j, B j*)是一对长度为6bit的串。 B j B j *作为 S j的输 入异或， S j(B j ) S j(B j*)则为 S j的输出异或。 首先考虑对给定的 a j Z 2 6，把所有异或值为 aj 的 (B j,B j*)拿来构成集合，即 (a j)={(B j,B j*)|B j B j*=a j } 。 |(a j)|=2 6=64， 因为 B j B j*=a j，所以 B j*=B j a j，即 (a j)={(B j,B j aj)|B j Z 2 6 } 。 对 (a j )中的每一对，计算出 Sj 的一个输出异或， 共可计算出64个输出异或， S j盒输出是4bit，只有 2 4=16个可能的输出值， 即64个输出异或分布在16个可能值上， 将这些分布列成表，分布的不均匀性就是差分攻击 的基础
■例3.1:S0的一个输入异或为110100,则 △(110100)={(0000010100),(000001, l10101),,(1111,001011}。 对△(110100)中的所有元素计算输出异或,并由 此统计各输出的分布,得表 00000001001000110100010101100111 8 16 0 12 10001001101010111100110111101111 0 8 0 6 16个可能的输出异或中实际仅出现了8个。实验表明,所 有可能的输出异或中实际上出现约75%~80%
例3.1：S0的一个输入异或为110100，则 (110100)={(000000,110100),(000001, 110101),, (111111,001011)}。 对(110100)中的所有元素计算输出异或，并由 此统计各输出的分布，得表： 0000 0001 0010 0011 0100 0101 0110 0111 0 8 16 6 2 0 0 12 1000 1001 1010 1011 1100 1101 1110 1111 60 0 0 0 8 0 6 16个可能的输出异或中实际仅出现了8个。实验表明，所 有可能的输出异或中实际上出现约75%～80%