现代密码学第4章2：DES

1、1分组密码：分组密码：数据加密标准数据加密标准DESDES算法算法现代密码学现代密码学第第4章章(2)2本节主要内容本节主要内容n1 1、数据加密标准、数据加密标准DESDES的产生的产生n2 2、S-DESS-DES算法算法n3 3、DESDES加密与解密过程加密与解密过程n4 4、DESDES的安全性分析的安全性分析n5 5、DESDES的改进与实现的改进与实现n6 6、作业、作业31.数据加密标准数据加密标准DES的产生的产生 美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告

2、。加密算法要达到的目的（通常称为DES 密码算法要求）主要为以下四点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）实现经济，运行有效，并且适用于多种完全不同的应用。 4n1977年1月，美国政府颁布：采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DES Data Encryption Standard）。1.数据加密标准数据加密标准DES的产生的产生5 数据加密标准（data

3、encryption standard, DES）是迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为64比特，密钥长度为56比特，它是由美国IBM公司研制的，是早期的称作Lucifer密码的一种发展和修改。 DES在1975年3月17日首次被公布在联邦记录中，经过大量的公开讨论后，DES于1977年1月15日被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。1.数据加密标准数据加密标准DES的产生的产生6 规定每隔5年由美国国家保密局（national security agency, NSA）作出评估，并重新批准它是否继续作为联邦加密标准。最近

4、的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。 1997年DESCHALL小组经过近4个月的努力，通过Internet搜索了31016个密钥，找出了DES的密钥，恢复出了明文。1.数据加密标准数据加密标准DES的产生的产生7n 1998年5月美国EFF(electronics frontier foundation)宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56 比特密钥的DES。美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之为 AES(advanced encryption standard) 的新加密标准。尽管

5、如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值，下面首先来描述这一算法。1.数据加密标准数据加密标准DES的产生的产生8 Simplified DES方案，简称方案，简称S-DES方方案。它是一个供教学而非安全的加密算法，案。它是一个供教学而非安全的加密算法，它与它与DES的特性和结构类似，但参数小。的特性和结构类似，但参数小。注：注：1.* 加密算法涉及五个函数：加密算法涉及五个函数：(1)初始置换初始置换IP(initial permutation)(2)复合函数复合函数fk1，它是由密钥，它是由密钥K确定的，

6、具有置换确定的，具有置换和代换的运算。和代换的运算。 (3)置换函数置换函数SW(4)复合函数复合函数fk2(5)初始置换初始置换IP的逆置换的逆置换IP-12.2.简化的简化的DESDES9 加密加密S-DESS-DES方案示意图方案示意图10bit密钥 解密解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K110nIP-1*fk2*SW*fk1*IP也可写为也可写为密文密文=IP-1（fk2(SW(fk1(IP(明文明文)其中其中 K1=P8(移位移位(P10(密钥密钥K)K2=P8(移位移位(移位移位(

7、P10(密钥密钥K)n解密算法的数学表示：解密算法的数学表示：明文明文=IP-1（fk1(SW(fk2(IP(密文密文)S-DES加密算法的数学表示加密算法的数学表示11对对S-DESS-DES的深入描述的深入描述（1） S-DES的密钥生成：的密钥生成：设设10bit的密钥为（的密钥为（ k1,k2,k10 )置换置换P10是这样定义的是这样定义的P10(k1,k2,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) P8= (k1,k2,k10)=(k6,k3,k7,k4,k8,k5,k10,k9 ) LS-1为循环左移为循环左移1位，位， LS-2为循环左移为循环

8、左移2位位 按照上述条件按照上述条件,若若K选为选为(1010000010), 产生的产生的两个子密钥分别为两个子密钥分别为K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)12(2) S-DES的加密运算的加密运算: 初始置换用初始置换用IP函数函数: IP= 1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7 末端算法的置换为末端算法的置换为IP的逆置换的逆置换:IP-1= 1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6 易见易见IP-1(IP(X)=X 13S-DES加密图加密图8-bit 明文明文IP+P4+LR4K1844f

9、kF414S-DES加密图加密图(续续)+8K2P4+IP-18-bit 密文密文4844fkF44228SW15 函数函数fk，是加密方案中的最重要部分，它可表示为：，是加密方案中的最重要部分，它可表示为：fk(L,R)=(L F(R,SK),R)，其中，其中L，R为为8位输入位输入, 左右左右各为各为4位位, F为从为从4位集到位集到4位集的一个映射位集的一个映射, 并不要求是并不要求是1-1的。的。SK为子密钥。为子密钥。 对映射对映射F来说：来说： 首先输入是一个首先输入是一个4-位数（位数（n1,n2,n3,n4），第一步），第一步运算是扩张运算是扩张/置换（置换（E/P）运算：）运

10、算： E/P 4 1 2 3 2 3 4 1 事实上，它的直观表现形式为：事实上，它的直观表现形式为： n4 n1 n2 n3 n2 n3 n4 n1168-bit子密钥：子密钥： K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与然后与E/P的结果作异或运算得：的结果作异或运算得：n4+k11 n1+k12 n2+k13n3+k14n2+k15 n3+k16n4+k17n1+k18 把它们重记为把它们重记为8位：位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3 上述第一行输入进上述第一行输入进S-盒盒S0，产生，产生2-位的输

11、出；位的输出；第二行的第二行的4位输入进位输入进S盒盒S1，产生，产生2-位的输出。位的输出。17两个两个S盒按如下定义：盒按如下定义：2313312001232301321032100S3012010331023210321032101S18S盒按下述规则运算：盒按下述规则运算： 将第将第1和第和第4的输入比特做为的输入比特做为2- bit数，指示为数，指示为S盒的一个行；将第盒的一个行；将第2和第和第3的输入比特做为的输入比特做为S盒的盒的一个列。如此确定为一个列。如此确定为S盒矩阵的（盒矩阵的（i,j）数。）数。 例 如 ： （例 如 ： （ P0 , 0 , P0 , 3） = ( 0

12、 0 ) , 并 且并 且(P0,1,P0,2)=(1 0)确定了确定了S0中的第中的第0行行2列（列（0，2）的系数为）的系数为3，记，记为（为（1 1）输出。由）输出。由S0, S1输出输出4-bit经置换经置换 P4 2 4 3 1它的输出就是它的输出就是F函数的输出。函数的输出。19S-DES的密钥生成的密钥生成10-bit密钥密钥P10LS-1LS-1LS-2LS-2K18K25555820S-DES的安全性分析的安全性分析对10 bit密钥的强行攻击是可行的密钥空间：210=1024密码分析：利用已知明文攻击：已知: 明文（p1,p2,p8), 及对应的密文（c1,c2,c8),未

13、知：(k1,k2, ，k10)Ci是pjs和kjs的函数这些加密算法可以表示成8个含10个变量的非线性方程非线性是由S盒作用的结果21 S0的非线性表示如下： 设a,b,c,d为输入的4个比特，输出的两个比特分别为q,r. 则 q=abcd+ab+ac+b+d mod2 r=abcd+abd+ab+ac+ad+a+c+1 mod2 线性映射与非线性映射交替产生了复杂的密文比特输出函数，使得密码分析很困难。（可以试图寻找8个密文比特的复杂度）S-DES的安全性分析的安全性分析22 图4.5是DES加密算法的框图，其中明文分组长为64比特，密钥长为56比特。图的左边是明文的处理过程，有3个阶段，首

14、先是一个初始置换IP，用于重排明文分组的64比特数据。然后是具有相同功能的16轮变换，每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置换IP-1（为IP的逆）从而产生64比特的密文。除初始置换和逆初始置换外，DES的结构和图4.3所示的Feistel密码结构完全相同。3.DES描述描述23图4.5 DES加密算法框图DES加密算法框图加密算法框图24 图4.5的右边是使用56比特密钥的方法。密钥首先通过一个置换函数，然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥

15、不相同。25DES加密算法描述加密算法描述64比特明文初始置换第1轮第2轮第16轮左右交换初始逆置换64比特密文56比特密钥置换选择1左循环移位置换选择11K左循环移位置换选择12K左循环移位置换选择116KDES加密算法框图加密算法框图26DES一轮加密的简图一轮加密的简图Li-1 Ri-1F+Li RiKi27 DES加加密过程密过程描述描述28DES加密算法描述加密算法描述第 i轮迭代PRi-1 (32bit)Ki(48bit)EE(Ri-1) (48bit)B1B2B3B4B5B6B7B8f(Ri-1 ,Ki)S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8(重排：有重

16、复)M(64bit)L0(32bit)R0(32bit)Li-1Ri-1IP-1C (64bit)LiRifKi(48bit)IP(置换)R16(32bit) L16(32bit)29IP初始置换初始置换(a)初始置换IP30(b)初始逆置换31DES的描述的描述在前面函数f的图示中，扩展置换（选择运算）E的定义为：3 212345456789891 0111 21 31 21 31 41 51 61 71 61 71 81 92 02 12 02 12 22 32 42 52 42 52 62 72 82 92 82 93 03 13 21置换运算P的定义为：32轮结构轮结构Des加密算法的

17、轮结构1iL32比特1iR32比特扩展/置换（E表）XOR代换/选择（S盒）置换(p)XORiRiL484832321iC28比特1iD28比特左移位左移位置换选择2iDiCiK33 首先看图的左半部分。将64比特的轮输入分成各为32比特的左、右两半，分别记为L和R。和Feistel网络一样，每轮变换可由以下公式表示：111(,)iiiiiiLRRLF RK34DES加密算法的轮结构加密算法的轮结构35R(32比特)ER(48比特)K(48比特)S1S1S1S1S1S1S1S1P32比特函数函数F(R，K)的计算过程的计算过程 36每个每个S盒的输入为盒的输入为6比特，输出为比特，输出为4 比

18、特，其变换关系如下：比特，其变换关系如下：S盒盒 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15列行0123S114 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 613S1盒的变换表盒的变换表37n（类比于（类比于S-DESS-DES）,F,F（R Ri-1i-1, K, Ki i）函数）函数F F以长以长度为度为3232的比特

19、串的比特串A=RA=R（32bits32bits）作第一个输）作第一个输入，以长度为入，以长度为4848的比特串变元的比特串变元J=K(48bits)J=K(48bits)作为第二个输入。产生的输出为长度为作为第二个输入。产生的输出为长度为3232的的位串。位串。(1)(1)对第一个变元对第一个变元A A，由给定的扩展函数，由给定的扩展函数E E，将其扩展成将其扩展成4848位串，位串，E E（A A）(2)(2)计算计算E E（A A）+J+J，并把结果写成连续的，并把结果写成连续的8 8个个6 6位串位串,B=b,B=b1 1b b2 2b b3 3b b4 4b b5 5b b6 6b

20、b7 7b b8 8对对F函数的说明函数的说明38n(3)使用8个S盒，每个Sj是一个固定的416矩阵，它的元素取015的整数。给定长度为6个比特串，如Bj=b1b2b3b4b5b6,计算Sj(Bj)如下：b1b6两个比特确定了Sj的行数, r(0=r=3); 而b2b3b4b5四个比特确定了Sj的列数c（0=c=15）。最后Sj(Bj)的值为S-盒矩阵Sj中r行c列的元素（r,c）, 得Cj=Sj(Bj)。(4) 最后，P为固定置换。对对F函数的说明函数的说明39n n DES 轮函数轮函数F()40 其中轮密钥Ki为48比特，函数F(R,K)的计算过程如图4.7所示。轮输入的右半部分R为3

21、2比特，R首先被扩展成48比特，扩展过程由表3.2(c)定义，其中将R的16个比特各重复一次。扩展后的48比特再与子密钥Ki异或，然后再通过一个S盒，产生32比特的输出。该输出再经过一个由表3.2(d)定义的置换，产生的结果即为函数F(R,K)的输出。41图4.7 函数F(R,K)的计算过程42 F中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为4比特，其变换关系由表3.3定义，每个S盒给出了4个代换（由一个表的4行给出）。（见42页表3.3）43 对每个盒Si，其6比特输入中，第1个和第6个比特形成一个2位二进制数，用来选择Si的4个代换中的一个。6比特输入中，中间4位用来选择列。

22、行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。例如，S1 的输入为011001，行选为01（即第1行），列选为1100（即第12列），行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。S盒的每一行定义了一个可逆代换，图4.2（在3.1.1节）表示S1第0行所定义的代换。44n A=R(32 bits)J=K(48 bits)EE(A)为48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B写成8个6比特串DES

23、 的的F函数函数45n初始置换初始置换IPIP：对明文输入进行次序的打乱。对明文输入进行次序的打乱。n逆置换逆置换IPIP-1-1：n扩展函数扩展函数E E；（3232到到4848）n置换函数置换函数P P。DESDES中使用的特定函数中使用的特定函数46n初始置换初始置换IP：从表：从表3.2中看出中看出X的第的第58个比个比特是特是IP（X）的第一个比特；）的第一个比特；X的第的第50个比个比特是特是IP（X）的第二个比特）的第二个比特n逆置换逆置换IP-1；扩展函数；扩展函数E；置换函数；置换函数P。DES中使用的其它特定函数中使用的其它特定函数47 再看图4.5和图4.6，输入算法的5

24、6比特密钥首先经过一个置换运算，该置换由表3.4(a)给出，然后将置换后的56比特分为各为28比特的左、右两半，分别记为C0和D0。在第i 轮分别对Ci-1和Di-1进行左循环移位，所移位数由表3.4(c)给出。移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择2的输入。通过置换选择2产生的48比特的Ki，即为本轮的子密钥，作为函数F(Ri-1,Ki)的输入。其中置换选择2由表3.4(b)定义。（见44页表3.4）密钥的产生密钥的产生48从密钥从密钥K计算子密钥计算子密钥n 实际上，实际上，K是长度为是长度为64的位串，其中的位串，其中56位是密钥，位是密钥，8位是奇偶校验位（为了检错）

25、，位是奇偶校验位（为了检错），在密钥编排的计算中，这些校验位可略去。在密钥编排的计算中，这些校验位可略去。(1). 给定给定64位的密钥位的密钥K，放弃奇偶校验位，放弃奇偶校验位（8，16，64）并根据固定置换）并根据固定置换PC-1（见（见144页图页图4-4-9）来排列）来排列K中剩下的位。中剩下的位。我们写我们写 PC-1(K)=C0D0其中其中C0由由PC-1（K）的前）的前28位组成；位组成；D0由由后后28位组成。位组成。49n(2)对对1=i=16，计算，计算Ci=LSi(Ci-1);Di=LSi(Di-1)LSi表示循环左移表示循环左移2或或1个位置，取决于个位置，取决于i的的

26、值。的的值。i=1,2,9和和16 时移时移1个位置，否则移个位置，否则移2位置。位置。Ki=PC-2(CiDi), PC-2为固定置。为固定置。n注：注：一共一共16轮，每一轮使用轮，每一轮使用K中中48位组成一个位组成一个48比特比特密钥。可算出密钥。可算出16个表，第个表，第i个表中的元素可对应上第个表中的元素可对应上第i轮密钥使用轮密钥使用K中第几比特！如：中第几比特！如：第第7轮的表轮的表7：K7取取K中的比特情况：中的比特情况：52 57 11 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 1828 7 14 29 4

27、7 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 650DES的密钥扩展的密钥扩展各轮迭代一共使用16个加密子密钥K1,K2,K16，它们依据所给56bit主密钥K按下述扩展算法产生：K(56bit)C0(28bit)D0(28bit)PC-1(置换)LS1LS1C1D1C16D16LS16LS16PC-2PC-2K1(48bit)K16(48bit)(选取：有舍弃)其中，其它, 216, 9 , 2 , 1, 1 iLSi51密钥的产生密钥的产生KPC-1C0D0LS1LS1C1D1LS2LS2PC-2K1C2D2LS3LS3PC-2K

28、2 LSi表示循环左移一个或两个位置其中i为1，2，9，16移一个位置其余移两个位置5257494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124141711241328156212319124261672720134152313747304051453344493956344642503629PC-1置换PC-2置换在前面密钥扩展的图示中，置换PC-1与选取PC-2分别为：53DES的描述的描述注. 对i=1,2,Ci、Di分别是由C0、D0左

29、旋若干比特而得到，至i=16，刚好左旋了28比特位而回复当初，即:C16=C0，D16=D0。 人们往往把主密钥K顺序地每7bit归为一组，共计8组，每一组都按应含奇数个1而在后面补上一个校验bit：0或1。如此，K被扩展为一个长是64的比特串K+，可用16位十六进制数表示。 K+由安全信道传送，其带上8个校验比特（分别在第8位、16位、64位）就是为了对传输过程中可能出错进行检测和校对。54n 取取16进制明文进制明文X：0123456789ABCDEF 密钥密钥K为：为： 133457799BBCDFF1 去掉奇偶校验位以二进制形式表示的密钥是去掉奇偶校验位以二进制形式表示的密钥是0001

30、0010011010010101101111001001101101111011011111111000应用应用IP，我们得到：，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进行然后进行16轮加密。最后对轮加密。最后对L16, R16使用使用IP-1得到密文：得到密文：85E813540F0AB405DES加密的一个例加密的一个例子子55DES的解密过程的解密过程u脱密过程采用与加密过程一样的算法，只不过须将加密过程中16轮迭代所用的子密钥(亦称为轮密钥)K1,K2,K16反序进

31、行使用。(在前面讲过的密钥扩展过程中若改LSi为则也就可以依次产生这逆序的子密钥。)其它, 216, 9 , 2, 11, 0iiRSi56DES解密解密DES解密与加密使用相同的算法，但子密钥的使用顺序相反。解密与加密使用相同的算法，但子密钥的使用顺序相反。EE1K2KPXC加密EE2K1KCXP解密二重二重DES57DES的设计特色的设计特色在DES算法中，函数 是最基本的关键环节，其中用S-盒实现小块的非线性变换，达到混乱目的；用置换P实现大块的非线性变换，达到扩散目的。置换P的设计使每层S-盒的4bit输出进入到下一层的4个不同S-盒；每个S-盒的输入由分属上一层中4个不同S-盒的输出

32、构成。322482322:FFFf58DES的设计特色的设计特色S-盒的设计准则还没有完全公开。一些密码学家怀疑美国NSA(the National Se-curity Agency)设计S-盒时隐藏了“陷门”，使得只有他们才知道破译算法，但没有证据能表明这一点。591976年，美国NSA披露了S-盒的下述几条设计原则：每个S-盒的每一行是整数015的一个全排列；每个S-盒的输出都不是其输入的线性或仿射函数；改变任一S-盒任意1bit的输入，其输出至少有2bit发生变化；DES的设计特色的设计特色60对任一S-盒的任意6bit输入x,S(x)与S(x001100)至少有2bit不同；对任一S-

33、盒的任意6bit输入x，及,0,1，都有S(x)S(x1100)；对任一S-盒，当它的任一位输入保持不变，其它5位输入尽情变化时，所有诸4bit输出中，0与1的总数接近相等。DES的设计特色的设计特色61DESDES的争论的争论nDES的核心是的核心是S盒，除此之外的计算是属盒，除此之外的计算是属线性的。线性的。S盒作为该密码体制的非线性组盒作为该密码体制的非线性组件对安全性至关重要。件对安全性至关重要。nS盒的设计准则：盒的设计准则：1. S盒不是它输入变量的线性函数盒不是它输入变量的线性函数2.改变改变S盒的一个输入位至少要引起两位盒的一个输入位至少要引起两位的输出改变的输出改变3. 对任

34、何一个对任何一个S盒，如果固定一个输入盒，如果固定一个输入比特，其它输入变化时，输出数字中比特，其它输入变化时，输出数字中0和和1的总数近于相等。的总数近于相等。62n公众仍然不知道公众仍然不知道S盒的构造中是否还使用盒的构造中是否还使用了进一步的设计准则（有陷门？）。了进一步的设计准则（有陷门？）。n密钥长度是否足够？密钥长度是否足够？n迭代的长度？（迭代的长度？（8、16、32？）？）634.DES4.DES的安全问题的安全问题DES的安全性完全依赖于所用的密钥。自从其算法作为标准公开以来，人们对它的安全性就有激烈的争论。下面简要介绍20年来人们就其安全方面的一些主要研究结果。取反特性.

35、对于明文组M，密文组C和主密钥K，若C=DESK(M)则 ，其中 , 和 分别为M,C和K的逐位取反。)(MDESCKMCK64证明. 若以K为主密钥扩展的16个加密子密钥记为K1,K2,K16，则以 为主密钥扩展的16个加密子密钥为注意到 ，不难看出注意到 ，不难看出 K1621,KKKbababa)1 ()1 (16, 2 , 1),(),(11iKRfKRfiiiibabababa)(1)1 (16, 2 , 1,11 iRLRLRLiiiiJiiiKDES的安全问题的安全问题65上述取补特性会使DES在选择明文攻击下所需工作量减少一半：攻击者为破译所使用的密钥，选取两个明密文对 与 ，

36、并对于可能密钥 ，计算出DESK(M)=C。若C=C1或 ，则分别说明K或 为实际密钥。),(1CM),(2CM562FK K2CC DES的安全问题的安全问题66弱密钥与半弱密钥. 大多数密码体制都有某些明显的“坏密钥”，DES也不例外。对于 ，若由K扩展出来的加密子密钥为：K1,K2,K15,K16，而由K扩展出来的加密子密钥却是：K16,K15,K2,K1，即有 ，则称K与K互为对合。下面我们分析一下 中到底有些什么样的对合对？KKDESDES1562FKK、562FDES的安全问题的安全问题67在DES的主密钥扩展中，C0与D0各自独立地循环移位来产生加(解)密子密钥。若C0与D0分别

37、是00,11,10,01中任意一个的14次重复，则因这样的C0与D0都对环移(无论左或右)偶数位具有自封闭性，故若 ，则由K扩展出来的加密子密钥为：K1,K2,K2,K2,K2,K2,K2,K2,K1,K1,K1,K1,K1,K1,K1,K2；KDCPC)(1001DES的安全问题的安全问题68把C0与D0各自左环移一位得C1与D1，设 ，则由K扩展出来的加密子密钥为：K2,K1,K1,K1,K1,K1,K1,K1,K2,K2,K2,K2,K2,K2,K2,K1。因此，由上述C0、D0导致的K与K互为对合；实际上，除了这些以外，在 中似乎不再有其它的对合对了。DES的安全问题的安全问题KDCP

38、C)(1111562F69对于 ，若K是自己的对合，则称K为DES的一个弱密钥；若K存在异于自己的对合，则称K为DES的一个半弱密钥。显然，C0与D0分别是00,11,10,01中任意一个的14次重复的情况共有42=16种，其中C0与D0分别是00,11中任意一个的14次重复的情况(计22=4种)对应弱密钥；剩下的(16-4=12种)对应半弱密钥。562FKDES的安全问题的安全问题70弱密钥与半弱密钥直接引起的“危险”是在多重使用DES加密中，第二次加密有可能使第一次加密复原；另外，弱密钥与半弱密钥使得扩展出来的诸加密子密钥至多有两种差异，如此导致原本多轮迭代的复杂结构简化和容易分析。所幸在

39、总数256个可选密钥中，弱密钥与半弱密钥所占的比例极小，如果是随机选择，(半)弱密钥出现的概率很小，因而其存在性并不会危及DES的安全。DES的安全问题的安全问题71密文与明文、密文与密钥的相关性. 人们的研究结果表明：DES的编码过程可使每个密文比特都是所有明文比特和所有密钥比特的复杂混合函数，而要达到这一要求至少需要DES的迭代：5轮。人们也用2-检验证明：DES迭代8轮以后，就可认为输出和输入不相关了。DES的安全问题的安全问题72密钥搜索机. 在对DES安全性的批评意见中，较一致的看法是DES的密钥太短！其长度56bit，致使密钥量仅为2561017，不能抵抗穷搜攻击，事实证明的确如此

40、。1997年1月28日，美国RSA数据安全公司在RSA安全年会上发布了一项“秘密密钥挑战”竞赛，分别悬赏1000美金、5000美金和10000美金用于攻破不同长度的RC5密码算法，同时还悬赏10000美金破译密钥长度为56bit的DES。RSA公司发起这场挑战赛是为了调查在Internet上分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为56bit的DES算法的相对强度。DES的安全问题的安全问题73结果是：密钥长度为40bit和48bit的RC5算法被攻破；美国克罗拉多州的程序员Verser从1997年3月13日起用了96天的时间，在Internet上数万名志愿者的协同工作下，于

41、1997年6月17日成功地找到了DES的密钥，获得了RSA公司颁发的10000美金的奖励。这一事件表明，依靠Internet的分布式计算能力，用穷搜方法破译DES已成为可能。因此，随着计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度。DES的安全问题的安全问题741977年，Diffe和Hellman曾建议制造每秒能测试106个密钥的VLSI芯片，将这样的100104个芯片并行操作搜索完整个密钥空间大约需1天时间。他们估计制造这样一台机器需耗资大约2000万美金。1993年，Wiener给出了一个详细的设计密钥搜索机的方案。他建议制造每秒能测试5107个密钥的芯片，基于这种芯

42、片的机器将流水作业，使得16次加密同时DES的安全问题的安全问题75发生。目前制造这种芯片每片需耗资10.5美金，耗资10万美金能建造一个由5760个芯片组成的框架，这使得搜索一个密钥平均大约需要1.5天。使用十个这样框架的机器将耗资100万美金，搜索一个密钥平均大约3.5小时。据新华社1998年7月22日消息,电子边境基金学会(EFF)使用一台25万美金的电脑在56小时内破译了56位密钥的DES。DES的安全问题的安全问题76DES的攻击方法.目前攻击DES的主要方法有时间-空间权衡攻击、差分攻击、线性攻击和相关密钥攻击等方法，在这些攻击方法中，线性攻击方法是最有效的一种方法。除了上面介绍的

43、几个方面外，20年来人们还发表了许多有关DES的其它方面的研究文章，这些研究不仅深入分析、检验了DES的各个方面，而且也大大地推动了密码学的研究和发展。DES的安全问题的安全问题775.DES的强化变形的强化变形利用随机因素对8个S-盒的排列顺序进行置换. 随意选取一个正整数，比如今天的日期：1106。对于k=8,7,2，依次求出1106 (mod k)：(2,0,2,1,2,2,0) （注意到2,3,8的最小公倍数为357 8=840，进行上述计算时可将1106用1106(mod 840)=266替代）。785.DES的强化变形的强化变形按照上面的数组求出18的一个全排列：1（其实，由已知全

44、排列34165827也可以求出对应的数组：34165827( , , , , , , )）。按照上面求得的全排列，把8个S-盒重排成：S3,S4,S1,S6,S5,S8,S2,S7。12312341234152341652341652734165827202 1 2 20795.DES的强化变形的强化变形u三重DES(the Triple DES). 为了克服DES之56bit密钥长度较短的弱点，人们想到采用下述以DES作为基本环节的加密方式：称之为三重DES。三重DES使进行密钥穷搜攻击的复杂度从O(256)增至O(2112)，并且采用一定的技巧编程，三重DES的加密时间仅为DES的2倍、而

45、不是通常想象的3倍！)(211121KKCDESDESDESMKKK加密变换80 为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。 二重DES是多重使用DES时最简单的形式，如图4.8所示。其中明文为P，两个加密密钥为K1和K2，密文为： 解密时，以相反顺序使用两个密钥：21 KKCEEP12 KKPDDC二重二重DES81图4.8 二重DES二重二重DES82 因此，二重DES所用密钥长度为112比特，强度极大地增加。然而，假设对任意两个密钥K1和K2，能够找出另一密钥K3，使得213 KKKEEPEP二重二重DES83 那么，二重DES以及多重DES

46、都没有意义，因为它们与56比特密钥的单重DES等价，好在这种假设对DES并不成立。将DES加密过程64比特分组到64比特分组的映射看作一个置换，如果考虑264个所有可能的输入分组，则密钥给定后，DES的加密将把每个输入分组映射到一个惟一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对264个输入分组，总映射个数为 。2064102!10二重二重DES84 另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为2561017。因此，可假定用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中。 这一假定已于1992年被证

47、明。所以使用二重DES产生的映射不会等价于单重DES加密。但对二重DES有以下一种称为中途相遇攻击的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下：二重二重DES85如果有那么（见图4.8）21 KKCEEP12 KKXEPDC二重二重DES86 如果已知一个明文密文对(P,C)，攻击的实施可如下进行：首先，用256个所有可能的K1对P加密，将加密结果存入一表并对表按X排序，然后用256个所有可能的K2对C解密，在上述表中查找与C解密结果相匹配的项，如果找到，则记下相应的K1和K2。最后再用一新的明文密文对(P,C)检验上面找到的K1和K2，用K1和K2

48、对P两次加密，若结果等于C，就可确定K1和K2是所要找的密钥。二重二重DES87 对已知的明文P，二重DES能产生264个可能的密文,而可能的密钥个数为2112，所以平均来说，对一个已知的明文，有2112/264=248个密钥可产生已知的密文。而再经过另外一对明文密文的检验，误报率将下降到248-64=2-16。所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为1-2-16。二重二重DES88 抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密，从而可使已知明文攻击的代价增加到2112。然而，这样又会使密钥长度增加到563=168比特，因而过于笨重。一种实用的方法是

49、仅使用两个密钥做3次加密，实现方式为加密|解密|加密，简记为EDE( encryptdecryptencrypt)，见图4.9，即：两个密钥的三重两个密钥的三重DES121 KKKCEDEP89图4.9 两个密钥的三重DES90两个密钥的三重两个密钥的三重DESDES三重三重DESED1K2KPAB加密DE1K2KCBA解密E1KCD1KP91 此方案已在密钥管理标准ANS X.917和ISO 8732中被采用。92 三个密钥的三重DES密钥长度为168比特，加密方式为 令K3=K2或K1=K2，则变为一重DES。三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用。三个

50、密钥的三重三个密钥的三重DES321 KKKCEDEP93三个密钥的三重三个密钥的三重DESDES三重三重DESED1K2KPAB加密DE3K2KCBA解密E3KCD1KP94DES的软件实现的软件实现u用8086/8088宏汇编语言编写DES程序的技巧和要点. 将第16轮迭代结果L16R16的交换与置换IP-1复合成一个新的置换(记为IP)：在R16L16中,大于32的位置t应出现在L16里，对应在L16R16里便是t-32；32以内的位置t应出现在R16里，对应在L16R16里便是t+32。8 40 16 48 24 56 32 64 7 39 15 47 23 55 31 63 6 38

51、 14 46 22 54 30 62 5 37 13 45 21 53 29 61 4 36 12 44 20 52 28 60 3 35 11 43 19 51 27 59 2 34 10 42 18 50 26 58 1 33 9 41 17 49 25 57 95DES的软件实现的软件实现IP,IP,E,P,PC-1,PC-2基于同一个底层程序来实现：该底层程序主要应用诸移位指令来完成数据比特的重新选取。按照000000(0,0)，000001(1,0)，011110(0,15)，011111(1,15)100000(2,0)，100001(3,0)，111110(2,15)，111111(3,15)重排每个S-盒数