第二章：对称密码学
2.3.4 DES密码分析
差分密码分析是在1990年由埃利比哈姆（Eli
Biham）和阿迪沙米尔（Adi Shamir）两位密码学家首次提出的密码分析技术。他们利用该方法找到了针对DES密码的选择明文攻击，而且这种攻击比蛮力搜索攻击有效得多。差分密码分析依据所产生的密文对的差来检查明文对的差，并利用这些差来计算出哪些密钥比其它密钥的可能性更大，最后求出正确的密钥。由于DES密码中，只有f函数影响输入对的模2差，因此差分密码分析技术特别适合于对付DES密码。由于对于特定的输入，输出差根本不是随机的，经仔细选择输入，输出差值便会暴露密钥的统计信息。这种密码分析技术需要攻击者能知道某些明文。
图2-16是DES的轮函数。对于一对输入X和X’，对应的输出为Y和Y’，由此可得各自的差?X和?Y。由于扩展置换E和P置换都是已知的，因此由?X和?Y可以计算出?A和?C。对于某个特定的S盒来说，我们可以事先对所有可能的?B和?C进行统计，获得输入?B和输出?C的统计关系。而?B=?A，因此最终我们可以得到?A和?C之间的联系。将?A和?C联合起来，就可以猜出A异或Ki以及A’异或Ki’的位值，由于A和A’是已知的，故可能推出关于Ki的信息。
51
第二章：对称密码学
X ?X E E（X） Ki ?A ?B S盒 ?C P Y ?Y 图2-16 DES轮函数
线性密码分析(Linear Cryptanalysis)是Mitsuru Matsui提出的一种密码分析技术，这种方法通过寻找分组密码的线性近似来进行攻击。
记ｎ位明文组为P[1],???,P[n]，ｎ位密文组为C[1],???,C[n]，ｍ位密钥组为K[1],???,K[m]。然后定义
A[i,j,???,k]?A[i]?A[j]????A[k]
线性密码分析的目的就是要找到一个下列形式的有效线性等式：
P[?1,?2,???,?a]?C[?1,?2,???,?b]?K[?1,?2,???,?c]
其中1?a,b?n，1?c?m，?，?，?分别表示某个特定的位置。一旦确定上述关系，接下来就是对大量的明文和密文对计算上述等式的左边部分。若多数情况下结果为0，则假设K[?1,?2,???,?c]＝0，若多属情况下为1，则假设K[?1,?2,???,?c]=1。这就得到了密钥位的线性等式。只要获得足够多的上述等式就可以解出密钥。
52
第二章：对称密码学
图2.17给出第26位子密钥的线性等式。b26是S盒5的输入。b26由a26和子密钥的Ki,26异或得到，而a26则由输入的x17通过扩展置换E得到。S盒5对应的4个输出位为c17,c18,c19,c20，通过P盒运算成为轮函数的4位输出：y3,y8,y14,y。由此可得等式： 25x17?y3?y8?y14?y25?Ki,26
X x17 E E（X） Ki a26 b26 Ki,26 S盒 c17,c18,c19,c20 P Y y3,y8,y14,y25 图2-17 DES的一轮线性逼近
2.3.5
DES工作模式
DES有四种工作模式：电子密码本（ECB）、密码分组链接（CBC）、密文反馈（CFB）和输出反馈（OFB）。这四种工作模式同样适用于其它分组密码。 1、电子密本ECB模式：
53
第二章：对称密码学
这是直接应用密码算法的工作模式。对明文M分成一些64位的分组pi，对各明文组用给定的密钥k进行加密，得密文组：ci=DESk(pi)。将各密文组按顺序连接起来即得到明文的密文，如图2-18。
p1 pN p2
Key Key Key DES DES DES ……
加密 加密 加密
c1 c2 cN
c1 c2 cN
Key Key DES Key DES DES ……
解密 解密 解密 p1
p2 pN
图2-18 电子密码本（ECB）模式
缺点：在给定密钥的条件下，同一明文组总是得到同样的密文组，这会暴露明文数据的格式和统计特征。 2、密码分组链接CBC模式
在CBC模式下，每个明文组pi在加密之前先与前一密文组ci-1按位模2求和后，再对结果运用DES算法。对于第一个明文组，由于还没有反馈密文，需预置一个初始向量IV，如图2-19。即：
c1=DESk(p1?IV) c2=DESk(p2?c1) ci=DESk(pi?ci-1)
54