现代密码学_杨波_9787302465553

本书全面而详细地介绍现代密码学的理论和相关算法，内容包括现代密码学的基本概念、流密码、分组密码、公钥密码、密钥分配与密钥管理、消息认证和哈希函数、数字签名和认证协议、密码协议、可证明安全、网络加密与认证等。

　　网络空间安全重点规划丛书编审委员会顾问委员会主任：沈昌祥（中国工程院院士）

　　特别顾问：姚期智（美国国家科学院院士、美国人文及科学院院士、中国科学院院士、“图灵奖”获得者）

　　何德全（中国工程院院士）蔡吉人（中国工程院院士）

　　方滨兴（中国工程院院士）

　　主任：封化民

　　副主任：韩臻李建华王小云张焕国冯登国

　　委员：（按姓氏拼音为序）

　　曹珍富陈克非陈兴蜀杜瑞颖段海新高岭

　　宫力谷大武何大可侯整风胡爱群胡道元

　　黄继武黄刘生荆继武寇卫东来学嘉李晖

　　刘建伟刘建亚马建峰毛文波裴定一钱德沛

　　秦玉海秦志光卿斯汉石文昌汪烈军王怀民

　　王劲松王军王丽娜王美琴王清贤王新梅

　　王育民吴晓平谢冬青徐明许进杨波

　　杨庚杨义先俞能海张功萱张红旗张宏莉

　　张敏情张玉清郑东周福才

　　丛书策划：张民21世纪是信息时代，信息已成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它会直接关系到国家安全、企业经营和人们的日常生活。随着信息安全产业的快速发展，全球对信息安全人才的需求量不断增加，但我国目前信息安全人才极度匮乏，远远不能满足金融、商业、公安、军事和政府等部门的需求。要解决供需矛盾，必须加快信息安全人才的培养，以满足社会对信息安全人才的需求。为此，教育部继2001年批准在武汉大学开设信息安全本科专业之后，又批准了多所高等院校设立信息安全本科专业，而且许多高校和科研院所已设立了信息安全方向的具有硕士和博士学位授予权的学科点。

　　信息安全是计算机、通信、物理、数学等领域的交叉学科，对于这一新兴学科的培养模式和课程设置，各高校普遍缺乏经验，因此中国计算机学会教育专业委员会和清华大学出版社联合主办了“信息安全专业教育教学研讨会”等一系列研讨活动，并成立了“高等院校信息安全专业系列教材”编审委员会，由我国信息安全领域著名专家肖国镇教授担任编委会主任，指导“高等院校信息安全专业系列教材”的编写工作。编委会本着研究先行的指导原则，认真研讨国内外高等院校信息安全专业的教学体系和课程设置，进行了大量前瞻性的研究工作，而且这种研究工作将随着我国信息安全专业的发展不断深入。系列教材的作者都是既在本专业领域有深厚的学术造诣、又在教学第一线有丰富的教学经验的学者、专家。

　　该系列教材是我国第一套专门针对信息安全专业的教材，其特点是：

　　①体系完整、结构合理、内容先进。

　　②适应面广：能够满足信息安全、计算机、通信工程等相关专业对信息安全领域课程的教材要求。

　　③立体配套：除主教材外，还配有多媒体电子教案、习题与实验指导等。

　　④版本更新及时，紧跟科学技术的新发展。

　　在全力做好本版教材，满足学生用书的基础上，还经由专家的推荐和审定，遴选了一批国外信息安全领域优秀的教材加入到系列教材中，以进一步满足大家对外版书的需求。“高等院校信息安全专业系列教材”已于2006年年初正式列入普通高等教育“十一五”国家级教材规划。

　　2007年6月，教育部高等学校信息安全类专业教学指导委员会成立大会暨第一次会议在北京胜利召开。本次会议由教育部高等学校信息安全类专业教学指导委员会主任单位北京工业大学和北京电子科技学院主办，清华大学出版社协办。教育部高等学校信息安全类专业教学指导委员会的成立对我国信息安全专业的发展起到重要的指导和推动作用。2006年教育部给武汉大学下达了“信息安全专业指导性专业规范研制”的教学科研项目。2007年起该项目由教育部高等学校信息安全类专业教学指导委员会组织实施。在高教司和教指委的指导下，项目组团结一致，努力工作，克服困难，历时5年，制定出我国第一个信息安全专业指导性专业规范，于2012年年底通过经教育部高等教育司理工科教育处授权组织的专家组评审，并且已经得到武汉大学等许多高校的实际使用。2013年，新一届“教育部高等学校信息安全专业教学指导委员会”成立。经组织审查和研究决定，2014年以“教育部高等学校信息安全专业教学指导委员会”的名义正式发布《高等学校信息安全专业指导性专业规范》（由清华大学出版社正式出版）。

　　现代密码学(第4版)出版说明2015年6月，国务院学位委员会、教育部出台增设“网络空间安全”为一级学科的决定，将高校培养网络空间安全人才提到新的高度。2016年6月，中央网络安全和信息化领导小组办公室（下文简称中央网信办）、国家发展和改革委员会、教育部、科学技术部、工业和信息化部及人力资源和社会保障部六大部门联合发布《关于加强网络安全学科建设和人才培养的意见》（中网办发文\[2016\]4号）。为贯彻落实《关于加强网络安全学科建设和人才培养的意见》，进一步深化高等教育教学改革，促进网络安全学科专业建设和人才培养，促进网络空间安全相关核心课程和教材建设，在教育部高等学校信息安全专业教学指导委员会和中央网信办资助的网络空间安全教材建设课题组的指导下，启动了“网络空间安全重点规划丛书”的工作，由教育部高等学校信息安全专业教学指导委员会秘书长封化民校长担任编委会主任。本规划丛书基于“高等院校信息安全专业系列教材”坚实的工作基础和成果、阵容强大的编审委员会和优秀的作者队伍，目前已经有多本图书获得教育部和中央网信办等机构评选的“普通高等教育本科国家级规划教材”、“普通高等教育精品教材”、“中国大学出版社图书奖”和“国家网络安全优秀教材奖”等多个奖项。

　　“网络空间安全重点规划丛书”将根据《高等学校信息安全专业指导性专业规范》（及后续版本）和相关教材建设课题组的研究成果不断更新和扩展，进一步体现科学性、系统性和新颖性，及时反映教学改革和课程建设的新成果，并随着我国网络空间安全学科的发展不断完善，力争为我国网络空间安全相关学科专业的本科和研究生教材建设、学术出版与人才培养做出更大的贡献。

　　我们的Email地址是：zhangm@tup.tsinghua.edu.cn，联系人：张民。

　　“网络空间安全重点规划丛书”编审委员会当今世界，互联网深刻改变了人们的生产和生活方式，但我们在网络安全方面却面临着严峻挑战。从宏观上说，网络安全是事关国家安全的重大战略问题——没有网络安全就没有国家安全；从微观上看，网络安全关乎我们每个人的信息安全。网络安全指网络系统中硬件、软件及其系统中的数据安全。从本质上说，网络安全就是网络上的信息安全。

　　信息安全又分为系统安全(包括操作系统的安全、数据库系统的安全等)、数据安全(包括数据的安全存储、安全传输)和内容安全(包括病毒的防护、不良内容的过滤等)3个层次，是一个综合、交叉的学科领域，要利用数学、电子、信息、通信、计算机等诸多学科的长期知识积累和最新发展成果。信息安全研究的内容很多，涉及安全体系结构、安全协议、密码理论、信息分析、安全监控、应急处理等，其中密码技术是保障数据安全的关键技术。

　　密码技术中的加密方法包括单钥密码体制(又称为对称密码体制)和公钥密码体制，而单钥密码体制又包括流密码和分组密码。本书在第1章介绍现代密码学的基本概念后，在第2～4章分别介绍流密码、分组密码、公钥密码。不管哪种密码体制都需要用到密钥，因此密钥分配与密钥管理也是密码技术的重要内容，这部分内容在第5章介绍。信息的安全性除要考虑保密性外，还需考虑信息的真实性、完整性、顺序性、时间性以及不可否认性。本书以3章的篇幅(第6章消息认证和哈希算法、第7章数字签字和认证协议、第8章密码协议)介绍这部分内容。第9章可证明安全介绍如何刻画公钥密码体制的语义安全性。第10章网络加密与认证介绍加密技术和认证技术在网络中的具体应用。书中4.1.5节的卡米歇尔定理、4.1.11节循环群、4.1.12节循环群的选取、8.3节安全多方计算协议、第9章可证明安全供研究生使用。

　　本书自2003年8月第1版以来，已被150余所学校作为教材，曾获批普通高等教育“十一五”国家级规划教材，2016年获得首届国家网络安全优秀教材奖。第4版在第3版的基础上进行修订，因为内容陈旧而去掉了原5.3节，重新编写了第9章，增加了3.7节、3.8节、6.1.4节、6.6节和7.4节。

　　本书的特点：一是内容新颖、深入、全面，涵盖了现代密码学的最新成果；二是内容的安排充分考虑到作为教材，如何方便地在教学中使用。在本书的编写过程中，参考了国内外的有关著作和文献，特别是Stallings、王育民、卢开澄、朱文余等人的著作。

　　西安电子科技大学通信工程学院的肖国镇教授作为本书的责任编委，认真审阅了全书并提出了许多宝贵的指导意见，对此表示特别的感谢。清华大学出版社张民编辑为本书的出版做了大量的工作，在此表示衷心的感谢。

　　由于作者水平有限，书中不足在所难免，恳请读者批评指正。

　　现代密码学(第4版)前言

　　作者2017年4月

　　第3章分组密码体制

　　3.1分组密码概述在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码(MAC)和哈希函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组密码可能会提出多方面的要求，除了安全性外，还有运行速度、存储量(程序的长度、数据分组长度、高速缓存大小)、实现平台(硬件、软件、芯片)、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择。

　　分组密码是将明文消息编码表示后的数字序列x0,x1,…,xi,…划分成长为n的组x=(x0,x1,…,xn－1)，各组(长为n的矢量)分别在密钥k=(k0,k1,…,kt－1)控制下变换成等长的输出数字序列y=(y0,y1,…,ym－1)(长为m的矢量)，其加密函数E：Vn×KVm，Vn和Vm分别是n维和m维矢量空间，K为密钥空间，如图31所示。它与流密码的不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为n的数字序列的代换密码。

　　图31分组密码框图

　　通常取m=n。若m>n，则为有数据扩展的分组密码。若m

　　(1)分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和LOKI等分组密码都采用n=64，在生日攻击下用232组密文成功概率为1/2，同时要求232×64比特=215Mbyte存储，故采用穷举攻击是不现实的。

　　(2)密钥量要足够大(即置换子集中的元素足够多)，尽可能消除弱密钥并使所有密现代密码学(第4版)第3章分组密码体制钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。DES采用56比特密钥，现在看来太短了，IDEA采用128比特密钥，据估计，在今后30～40年内采用80比特密钥是足够安全的。

　　(3)由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其他捷径可循。

　　(4)加密和解密运算简单，易于软件和硬件高速实现。如将分组n划分为子段，每段长为8、16或者32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免使用以软件难以实现的逐比特置换。为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可使用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现。此外，差错传播和数据扩展要尽可能小。

　　(5)数据扩展尽可能小。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。

　　(6)差错传播尽可能小。

　　要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法，而后进行严格的安全性检验，并且要易于实现。

　　下面介绍设计分组密码的一些常用方法。

　　3.1.1代换

　　如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算可逆(使解密运算可行)，明文的每一个分组都应产生唯一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。

　　图32代换结构图32表示n=4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。加密映射和解密映射可由代换表来定义，如表31所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。表31与图32对应的代换表

　　明文密文明文密文00001110100000110001010010011010001011011010011000110001101111000100001011000101010111111101100101101011111000000111100011110111密文明文密文明文00001110100001110001001110011101001001001010100100111000101101100100000111001011010111001101001001101010111000000111111111110101但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小，如n=4，系统则等价于古典的代换密码，容易通过对明文的统计分析而攻破。这个弱点不是代换结构固有的，只是因为分组长度太短。如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。

　　然而，从实现的角度来看，分组长度很大的可逆代换结构是不实际的。仍以表31为例，该表定义了n=4时从明文到密文的一个可逆映射，其中第二列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第二列是从所有可能的映射中决定某一特定映射的密钥。在这个例子中，密钥需要64比特。一般，对n比特的代换结构，密钥的大小是n×2n比特。如对64比特的分组，密钥大小应是64×264=270≈1021比特，因此难以处理。实际中常将n分成较小的段，例如可选n=r·n0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般n0都不太大，称每个子代换为代换盒，简称为S盒。例如DES中将输入为48比特、输出为32比特的代换用8个S盒来实现，每个S盒的输入端数仅为6比特，输出端数仅为4比特。

　　3.1.2扩散和混淆

　　扩散和混淆是由Shannon提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率，或可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，敌手就有可能得出加密密钥或其一部分，或包含加密密钥的一个可能密钥集合。在Shannon称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。图32讨论的代换密码就是这样的一个密码系统，然而是不实用的。

　　所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得密文中每一位由明文中多位产生。例如，对英文消息M=m1m2m3…的加密操作yn=chr(∑ki=1ord(mn+i)(mod26))其中ord(mi)是求字母mi对应的序号，chr(i)是求序号i对应的字母，密文字母yn是由明文中k个连续的字母相加而得。这时明文的统计特性将被散布到密文，因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。在二元分组密码中，可对数据重复执行某个置换再对这一置换作用以一个函数，便可获得扩散。

　　分组密码在将明文分组依靠密钥变换到密文分组时，扩散的目的是使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间统计关系复杂化，敌手无法得到密钥。使用复杂的代换算法可得预期的混淆效果，而简单的线性代换函数得到的混淆效果不够理想。

　　扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。

　　3.1.3Feistel密码结构

　　很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。Feistel提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果，Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。

　　1.Feistel加密结构

　　图33是Feistel网络示意图，加密算法的输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的输入为前轮输出的函数：Li=Ri－1

　　Ri=Li－1F(Ri－1,Ki)其中Ki是第i轮用的子密钥，由加密密钥K得到。一般，各轮子密钥彼此不同而且与K也不同。

　　图33Feistel网络

　　Feistel网络中每轮结构都相同，每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。每轮轮函数的结构都相同，但以不同的子密钥Ki作为参数。代换过程完成后，再交换左、右两半数据，这一过程称为置换。这种结构是Shannon提出的代换置换网络(SubstitutionPermutationNetwork，SPN)的特有形式。

　　Feistel网络的实现与以下参数和特性有关：

　　(1)分组大小。分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比特。

　　(2)密钥大小。密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥是不安全的，通常使用128比特长的密钥。

　　(3)轮数。单轮结构远不足以保证安全性，多轮结构可提供足够的安全性。典型地，轮数取为16。

　　(4)子密钥产生算法。该算法的复杂性越高，则密码分析的困难性就越大。

　　(5)轮函数。轮函数的复杂性越高，密码分析的困难性也越大。

　　在设计Feistel网络时，还要考虑以下两个问题：

　　(1)快速的软件实现。在很多情况下，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。

　　(2)算法容易分析。如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。

　　2.Feistel解密结构

　　Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第一轮使用Kn，第二轮使用Kn－1，一直下去，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。

　　图34的左边表示16轮Feistel网络的加密过程，右边表示解密过程，加密过程由上而下，解密过程由下而上。为清楚起见，加密算法每轮的左右两半用LEi和REi表示，解密算法每轮的左右两半用LDi和RDi表示。图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值的对应关系，即加密过程第i轮的输出是LEi‖REi(‖表示链接)，解密过程第16－i轮相应的输入是RDi‖LDi。

　　图34Feistel加解密过程

　　加密过程的最后一轮执行完后，两半输出再经交换，因此密文是RE16‖LE16。解密过程取以上密文作为同一算法的输入，即第一轮输入是RE16‖LE16，等于加密过程第16轮两半输出交换后的结果。现在显示解密过程第一轮的输出等于加密过程第16轮输入左右两半的交换值。

　　在加密过程中：LE16=RE15

　　RE16=LE15F(RE15,K16)在解密过程中：LD1=RD0=LE16=RE15

　　RD1=LD0F(RD0,K16)=RE16F(RE15,K16)

　　=LE15F(RE15,K16)F(RE15,K16)

　　=LE15所以解密过程第一轮的输出为LE15‖RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般，加密过程的第i轮有：LEi=REi－1

　　REi=LEi－1F(REi－1,Ki)因此REi－1=LEi

　　LEi－1=REiF(REi－1,Ki)=REiF(LEi,Ki)以上两式描述了加密过程中第i轮的输入与第i轮输出的函数关系，由此关系可得图34右边显示的LDi和RDi的取值关系。

　　最后可以看到，解密过程最后一轮的输出是RE0‖LE0，左右两半再经一次交换后即得最初的明文。

　　3.2数据加密标准DES(DataEncryptionStandard)是迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为64比特，密钥长度为56比特，它是由美国IBM公司研制的，是早期的称作Lucifer密码的一种发展和修改。DES在1975年3月17日首次被公布在联邦记录中，在做了大量的公开讨论后于1977年1月15日正式批准并作为美国联邦信息处理标准，即FIPS46，同年7月15日开始生效。规定每隔5年由美国国家保密局(NationalSecurityAgency，NSA)作出评估，并重新批准它是否继续作为联邦加密标准。最后一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。1997年，DESCHALL小组经过近4个月的努力，通过Internet搜索了3×1016个密钥，找出了DES的密钥，恢复出了明文。1998年5月美国EFF(ElectronicsFrontierFoundation)宣布，他们将一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56比特密钥的DES。美国国家标准和技术协会已征集并进行了几轮评估筛选，产生了称为AES(AdvancedEncryptionStandard)的新加密标准。尽管如此，DES对于推动密码理论的发展和应用起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值，下面是这一算法的描述。

　　3.2.1DES描述

　　图35是DES加密算法的框图，其中明文分组长为64比特，密钥长为56比特。图的左边是明文的处理过程，有3个阶段，首先是一个初始置换IP，用于重排明文分组的64比特数据。然后是具有相同功能的16轮变换，每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置换IP-1(为IP的逆)从而产生64比特的密文。除初始置换和逆初始置换外，DES的结构和图33所示的Feistel密码结构完全相同。

　　图35DES加密算法框图

　　图35的右边是使用56比特密钥的方法。密钥首先通过一个置换函数，然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥不相同。

　　1.初始置换

　　表32(a)和表32(b)分别给出了初始置换和逆初始置换的定义，为了显示这两个置换的确是彼此互逆的，考虑下面64比特的输入M：表32DES的置换表

　　(a)初始置换IP58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157(b)逆初始置换IP-140848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725(c)选择扩展运算E3212345456789891011121312131415161716171819202120212223242524252627282928293031321(d)置换运算P1672021291228171152326518311028241432273919133062211425M1M2M3M4M5M6M7M8

　　M9M10M11M12M13M14M15M16

　　M17M18M19M20M21M22M23M24

　　M25M26M27M28M29M30M31M32

　　M33M34M35M36M37M38M39M40

　　M41M42M43M44M45M46M47M48

　　M49M50M51M52M53M54M55M56

　　M57M58M59M60M61M62M63M64

　　其中Mi是二元数字。由表32(a)，得X=IP(M)为：M58M50M42M34M26M18M10M2

　　M60M52M44M36M28M20M12M4

　　M62M54M46M38M30M22M14M6

　　M64M56M48M40M32M24M16M8

　　M57M49M41M33M25M17M9M1

　　M59M51M43M35M27M19M11M3

　　M61M53M45M37M29M21M13M5

　　M63M55M47M39M31M23M15M7如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始顺序将被恢复。

　　2.轮结构

　　图36是DES加密算法的轮结构，首先看图的左半部分。将64比特的轮输入分为

　　图36DES加密算法的轮结构

　　各为32比特的左、右两半，分别记为L和R。和Feistel网络一样，每轮变换可由以下公式表示：Li=Ri－1

　　Ri=Li－1F(Ri－1,Ki)其中轮密钥Ki为48比特，函数F(R,K)的计算如图37所示。轮输入的右半部分R为32比特，R首先被扩展成48比特，扩展过程由表32(c)定义，其中将R的16个比特各重复一次。扩展后的48比特再与子密钥Ki异或，然后再通过一个S盒，产生32比特的输出。该输出再经过一个由表32(d)定义的置换，产生的结果即为函数F(R,K)的输出。

　　图37函数F(R,K)的计算过程

　　F中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为4比特，其变换关系由表33定义，每个S盒给出了4个代换(由一个表的4行给出)。表33DES的S盒定义

　　列

　　行0123456789101112131415S101441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S201518146113497213120510131347152814120110691152014711104131581269321531381013154211671205149S301009146315511312711428113709346102851412111512136498153011121251014731101306987415143115212续表

　　列

　　行0123456789101112131415S407131430691012851112415113811561503472121101492106901211713151314528433150610113894511127214S502124171011685315130149114112124713150151039862421111013781591256301431181271142136150910453S601211015926801334147511110154271295611314011382914155281237041011311634321295151011141760813S704112141508133129751061113011749110143512215862141113123714101568059236111381410795015142312S801328461511110931450127111513810374125611014922711419121420610131535832114741081315129035611对每个盒Si，其6比特输入中，第1个和第6个比特形成一个2位二进制数，用来选择Si的4个代换中的一个。在6比特输入中，中间4位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。例如，S1的输入为011001，行选为01(即第1行)，列选为1100(即第12列)，行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。

　　S盒的每一行定义了一个可逆代换，图32(在3.1.1节)表示S1第0行所定义的代换。

　　3.密钥的产生

　　再看图35和图36，输入算法的56比特密钥首先经过一个置换运算，该置换由表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)定义。表34DES密钥编排中使用的表

　　(a)置换选择1PC157494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124(b)置换选择2PC21417112415328156211023191242681672720132415231374755304051453348444939563453464250362932（c）左循环移位位数轮数12345678910111213141516位数11222222122222214.解密

　　和Feistel密码一样，DES的解密和加密使用同一算法，但子密钥使用的顺序相反。

　　3.2.2二重DES

　　……

我要评论