1、数据加密标准数据加密标准(DES)应用密码学应用密码学背景资料背景资料1973年年NBS国家标准局国家标准局 （NIST国家标准与技术研究所）国家标准与技术研究所）算法要求：算法要求：算法公开，安全性依赖于密钥而不是算法算法公开，安全性依赖于密钥而不是算法 算法应能测试和验证算法应能测试和验证 不同的设备可以相互通信不同的设备可以相互通信背景资料背景资料19681974，IBM研制研制1976 被定为联邦标准被定为联邦标准 并命名为并命名为DES(Data Encryption Standard)1981、1987、1993 分别被分别被NIST再次认证再次认证Feistel网络网络加密过程：
2、加密过程：1.把一个分组分成长度相等的把一个分组分成长度相等的 左右两部份：左右两部份：L,R2.进行进行n次叠代，次叠代，其第其第i 轮的输出取决于前一轮的输出：轮的输出取决于前一轮的输出：Li=Ri-1 Ri=Li-1(Ri-1，Ki)Ki是第是第i轮使用的子密钥轮使用的子密钥 是任意的轮函数是任意的轮函数3.最后交换左右两部分最后交换左右两部分Feistel网络网络解密过程与加密过程的区别解密过程与加密过程的区别:子密钥的顺序正好相反：子密钥的顺序正好相反：加密：加密：K1,K2,K3,K(n-1),Kn 解密：解密：Kn,K(n-1),K3,K2,K1L0R0R2L2L2=R1R2L1
3、=R0R1(R0,K1)(R1,K2)K1K2加密加密R2L2L0R0R0L0L2R0(L2,K2)(R0,K1)K2K1解密解密1010,11100011,11100001,10011111,1010加密加密1010,11100011,11100100,11011000,10011000,10010100,11010011,11101000,10010010,01110111,00110001,10011111,1010加密加密0100,11011000,10011111,10100001,1001解密解密0100,11011000,10011010,11100011,11100011,11
4、101010,11101000,10010011,11100111,00110010,01111111,10100001,1001解密解密采用采用Feistel网络的著名的分组密码网络的著名的分组密码DESFEAL：由日本电报电话公司的：由日本电报电话公司的 Akihiro Shimizu 和和 Shooji Miyaguchi 设计设计 LOKI：由澳大利亚人于由澳大利亚人于 1990 年首先提出作为年首先提出作为DES的一种潜的一种潜在替换算法在替换算法 GOST 是前苏联设计的分组密码算法是前苏联设计的分组密码算法 CAST 由加拿大的由加拿大的 C.Adams 和和 S.Tavares
5、 设计设计 Blowfish 由由 Bruce Schneier 设计设计 DES的参数：的参数：分组长度分组长度：64位位密钥长度：密钥长度：64位位 其中其中第第8，16，24，56,64为校验位为校验位有效密钥长度：有效密钥长度：56位位密钥空间：密钥空间：256DES的加密过程：的加密过程：64位明文位明文初始置换初始置换乘积变换乘积变换逆初始变换逆初始变换64位密文位密文初始置换初始置换5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292
6、1135635547393123157逆初始置换逆初始置换40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725乘积变换乘积变换16次叠代的次叠代的Feistel网络网络需要解决的问题：需要解决的问题：1.函数的构造函数的构造 2.把把64位主密钥转换为位主密钥转换为16个个48位的子密钥位的子密钥函数函数 S盒代替盒代替扩展置换扩展置换P盒置换盒置换子密钥子密钥Ki48bit48bit32bit32bit扩展置
7、换扩展置换 下图显示了扩展置换，有时它也叫做下图显示了扩展置换，有时它也叫做E盒。对每个盒。对每个4位输入分组，第位输入分组，第1和第和第4位分别表示输出分组中的两位分别表示输出分组中的两位，而第位，而第2和第和第3位分别表示输出分组中的一位。位分别表示输出分组中的一位。扩展置换扩展置换下表是从下表是从32位到位到48位的扩展置换，给出了哪一输出位对应于位的扩展置换，给出了哪一输出位对应于哪一输入位。例如，处于输入分组中第哪一输入位。例如，处于输入分组中第3位的位置的位移到位的位置的位移到了输出分组中第了输出分组中第4位的位置，而输入分组中第位的位置，而输入分组中第21位的位置的位的位置的位移
8、到了输出分组中第位移到了输出分组中第30和第和第32位的位置。位的位置。尽管输出分组大于输入分组，但每一个输入分组产生唯一的尽管输出分组大于输入分组，但每一个输入分组产生唯一的输出分组。输出分组。3212345456789891011121312131415161716171819202120212223242524252627282928293031321S-S-盒代替盒代替S1S2S3S4S5S6S7S848位输入位输入32位输出位输出6bit4bitSi:416矩阵矩阵S10123456789abcdef014413121511831061259071015741421311061211
9、95382411481362111512973105031512824917511314100613b0b1b2b3b4b5行号：行号：03列号：列号：015S盒的设计准则盒的设计准则没有一个没有一个S的输出位是接近输入位的线性函数的输出位是接近输入位的线性函数如果将输入位的最左及最右端的位固定，变化中间如果将输入位的最左及最右端的位固定，变化中间的的4位，每个可能的位，每个可能的4位数出只能得到一次位数出只能得到一次如果如果s盒的两个输入仅有盒的两个输入仅有1位的差异，则输出至少必位的差异，则输出至少必须有须有2位不同位不同如果如果s盒的两个输入仅有中间盒的两个输入仅有中间2位不同，则输出至
10、少位不同，则输出至少必须有必须有2位不同位不同如果如果s盒的两个输入仅前盒的两个输入仅前2位不同，后位不同，后2位已知则输出位已知则输出必不同必不同对于输入之间的任何非零的对于输入之间的任何非零的6位差分，位差分，32对中至多有对中至多有8对显示出的差分导致了相同的输出差分对显示出的差分导致了相同的输出差分P盒置换盒置换 S盒代替运算后的盒代替运算后的32位输出依照位输出依照P盒进行置换。该置换把每盒进行置换。该置换把每输入位映射到输出位，任意一位不能被映射两次，也不能输入位映射到输出位，任意一位不能被映射两次，也不能被略去，这个置换叫做直接置换。下表给出了每位移到的被略去，这个置换叫做直接置
11、换。下表给出了每位移到的位置。例如，第位置。例如，第21位移到了第位移到了第4位处，同时第位处，同时第4位移到了第位移到了第31位处。最后，将位处。最后，将P盒置换的结果与最初的盒置换的结果与最初的64位分组的左位分组的左半部分异或，然后左、右半部分交换，接着开始另一轮。半部分异或，然后左、右半部分交换，接着开始另一轮。1672021291228171152326518311028241432273919133062211425子密钥生成子密钥生成PC-1密钥置换密钥置换PC-15749413325179158504234261810259514335271911360524436635547
12、393123157625446383022146615345372921135282012464比特的密钥比特的密钥K，经过经过PC-1后，生成后，生成56比特的串。其下比特的串。其下标如表所示：标如表所示：PC-2压缩置换压缩置换PC-21417112415328156211023191242681672720132415231374755304051453348444939563453464250362932每轮移位的位数每轮移位的位数迭代顺序迭代顺序12345678910111213141516左移位数左移位数1122222212222221DES解密解密加密和解密可使用相同的算法。加密
13、和解密可使用相同的算法。DES使得用相同的函数来加密或解密每个分组成为使得用相同的函数来加密或解密每个分组成为可能，二者的唯一不同之处是密钥的次序相反。这可能，二者的唯一不同之处是密钥的次序相反。这就是说，如果各轮的加密密钥分别是就是说，如果各轮的加密密钥分别是K1，K2，K3，K16,那么解密密钥就是那么解密密钥就是K16，K15，K14，K1。差分密码分析差分密码分析1900年年Eli Biham 和和Adi Shamir 提出了差分密码分提出了差分密码分析。析。利用这种方法，利用这种方法，Eli Biham 和和Adi Shamir 对对DES算算法进行了选择明文攻击，比穷举攻击有效法进
14、行了选择明文攻击，比穷举攻击有效对于对于DES的差分密码分析，如果选择明文攻击，需的差分密码分析，如果选择明文攻击，需要要247对于对于DES的差分密码分析，如果已知明文攻击，需的差分密码分析，如果已知明文攻击，需要要255线性密码分析线性密码分析线性密码分析是线性密码分析是Mitsuru Matsui提出的提出的是一种已知明文攻击是一种已知明文攻击如果将明文的一些位、密文的一些位进行异或运算如果将明文的一些位、密文的一些位进行异或运算，然后再对这两个结果异或，那么将得到一个位，然后再对这两个结果异或，那么将得到一个位，这一位是将密钥的一些位进行异或运算的结果这一位是将密钥的一些位进行异或运算
15、的结果对于对于DES的线性密码分析，已知明文攻击数为的线性密码分析，已知明文攻击数为243X X1717Y Y33Y Y88Y Y1414Y Y25=25=K Ki,26i,261/2-5/161/2-5/16 DES的安全强度的安全强度 密钥长度问题密钥长度问题56-bit 密钥有密钥有256=72,057,584,037,927,936 7.2亿亿亿亿之多之多技术进步使穷举搜索成为可能技术进步使穷举搜索成为可能1997年年1月月28日，日，RSA公司发起破译公司发起破译RC4、RC5、MD2、MD5，以及，以及DES的活动，破译的活动，破译DES奖励奖励10000美金。明文是：美金。明文是
16、：Strong cryptography makes the world a safer place.结果仅搜索了结果仅搜索了24.6%的密钥空间便得到结果，耗时的密钥空间便得到结果，耗时96天。天。1998年在一台专用机上年在一台专用机上(EFF)只要几天时间即可只要几天时间即可 1999年在超级计算机上只要年在超级计算机上只要22小时小时!S-box问题，其设计标准没有公开问题，其设计标准没有公开 线性密码分析攻击问题，线性密码分析攻击问题，DES不能抵御线形分析不能抵御线形分析二重二重DES 为了提高为了提高DES的安全性，并利用实现的安全性，并利用实现DES的现有软硬件，的现有软硬件，
17、可将可将DES算法在多密钥下多重使用。算法在多密钥下多重使用。二重二重DES是多重使用是多重使用DES时最简单的形式，如图时最简单的形式，如图3.8所示。所示。其中明文为其中明文为P，两个加密密钥为两个加密密钥为K1和和K2，密文为：密文为：解密时，以相反顺序使用两个密钥：解密时，以相反顺序使用两个密钥：21 KKCEEP12 KKPDDC二重二重DES对二重对二重DES的中途相遇攻击的中途相遇攻击21 KKCEEP12 KKXEPDC对二重对二重DES的中途相遇攻击的中途相遇攻击 如果已知一个明文密文对如果已知一个明文密文对(P,C)，攻击的实施可如下攻击的实施可如下进行：进行：首先，用首先
18、，用256个所有可能的个所有可能的K1对对P加密，将加密结果加密，将加密结果存入一表并对表按存入一表并对表按X排序，排序，然后用然后用256个所有可能的个所有可能的K2对对C解密，在上述表中查解密，在上述表中查找与找与C解密结果相匹配的项，如果找到，则记下相应解密结果相匹配的项，如果找到，则记下相应的的K1和和K2。最后再用一新的明文密文对最后再用一新的明文密文对(P,C)检验上面找到的检验上面找到的K1和和K2，用用K1和和K2对对P两次加密，若结果等于两次加密，若结果等于C，就可确定就可确定K1和和K2是所要找的密钥。是所要找的密钥。对二重对二重DES的中途相遇攻击的中途相遇攻击 对已知的
19、明文对已知的明文P，二重二重DES能产生能产生264个可能的密文个可能的密文,而可能的密钥个数为而可能的密钥个数为2112，所以平均来说，对一个已，所以平均来说，对一个已知的明文，有知的明文，有2112/264=248个密钥可产生已知的密文个密钥可产生已知的密文。而再经过另外一对明文密文的检验，误报率将下降而再经过另外一对明文密文的检验，误报率将下降到到248-64=2-16。所以在实施中途相遇攻击时，如果已知两个明文密所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为文对，则找到正确密钥的概率为1-2-16。两个密钥的三重两个密钥的三重DES三个密钥的三重三个密钥的三重DES例题例题已知：在已知：在DES算法中第轮的输出为：算法中第轮的输出为：R1=1011,0011,0000,0010,0111,0011,1101,0100L1=0000,0000,1111,1111,1001,0010,1010,1000第轮子密钥为：第轮子密钥为：K2=111000,001011,111011,110110,100110,111011,111000,111100求求R2答案：答案：1001,0111,0111,1101,1011,0101,0001,0111下此课内容下此课内容AES下次课再见！下次课再见！
