现代密码学理论与实践中文

现代密码学理论与实践中文现代密码学理论与实践中文现代密码学理论与实践中文考虑到对信息安全专业人才的大量需求,并相信专业人才的密码学知识不能仅囿于教科书式密码学,作者写了这本“非教科书式密码学”教材。本书致力于在强调“非教科书式的情况下,广泛介绍有关密码算法、方案和协议。●通过展示对这类系统的大量攻击和总结典型的攻击技术,来说明“教科书式密码”的不安全性。●通过对标准的关注,为密码系统和协议的设计、分析与实施提供原理和指导原则。研究严格建立密码系统和协议的强而实用安全性表示的形式化技术和方法。●为希望系统了解这一领域的读者精心选取学习现代密码学必备的理论素材。本书范围在过去的30年里,现代密码学的研究可谓突飞猛进,其研究领域非常广泛和深人。本书集中讨论一个方面的问题:对以其强安全性能明确建立起来的实用密码方案和协议进行介绍。本书分为6部分:第一部分这一部分共有两章内容(第1章,第2章),是本书和密码学与信息安全的人门性介绍。其中第1章以解决一个微妙的通信问题为开场白,来阐述密码学的效用。本章将给出一个在电话上实现公平掷币的简单密码协议(本书的第一个协议)并对其进行讨论。然后对要研究领域的文化和“贸易”进行介绍。第2章使用一系列的简单认证协议,来表明该领域的一个不幸的事实:缺陷处处存在。作为人门性介绍,这一部分是为想进入该领域的新手写的。第二部分这一部分介绍学习本书必备的数学背景知识,它包含4章内容(第3章~第6章)。只想“知其然”,即了解如何使用实用密码方案和协议的读者,可以跳过这一部分而基本上不影响大多数后续章节的阅读。要想知道“所以然”,即为什么这些方案和协议具有强安全性的读者将会发现,这里给出的数学背景知识是足够的。当我们揭示方案和协议的工作原理指出其中的一些方案和协议是不安全的,或者论述别的协议和方案是安全的时候,我们就能在这里找到相应的理论根据。这一部分也可作为学习现代密码学理论基础的系统背景知识。第三部分这部分也有4章内容(第7章~第10章),介绍提供保密和数据完整性保护最基本的密码算法和技术。其中第7章是对称加密方案,第8章是非对称加密技术,第9章讨论的是,在数据是随机的理想条件下,利用基本通用的非对称密码函数所拥有的一个重要的安全特性。最后的第10章是数据完整性技术。由于这里介绍的是最基本的方案和技术,其中多数属于“教科书式密码”,因而是不安全的。在介绍这些方案的同时,也给出不少相应的攻击,并明确阐述了告诫注释。对于那些不想对实用密码和它们的强安全性概念做深入研究的实际工作人员,教科书式密码部分也仍会就教科书式密码的不安全性向他们提出明确的预警信号。第四部分这部分有3章内容(第11章~第13章),介绍应用密码学和信息安全中一个重要的概念—认证。这些章节的研究范围很广,第11章介绍技术背景、原理、一系列的基础协议和标准,以及常规的攻击技术和防护措施。第12章是对四个著名的认证协议系统在现实应用案例的研究。第13章介绍特别适合于开放系统的有关最新技术。8企业中信息安全系统的管理者、安全产品的软/硬件开发商们将会发现这一部分对他们是非常有用的。第五部分这部分有4章内容(第14章~第17章),对公钥密码技术(加密、签名和签密)的强实用)安全性概念进行严格的形式化处理,并给出认证协议的形式化分析方法。第14章介绍强安全性概念的形式化定义,接着的两章是和第三部分教科书式密码方案相对的实用密码方案,具有形式化建立起(即明确推理)的强安全性。最后,第17章对在第四部分尚未进行分析的认证协议,给出其形式化的分析方法和技术。第六部分这是本书的最后一部分,包括两个技术章节(第18章~第19章)和一个简短的评述(第20章)。其主要的技术章节,第18章,介绍了一类被称为笭知识协议的密码协议。这类协议能提供一种重要的安全性业务,它为“想像中”的各种电子商务和事务处理应用所必需,在对所声明的内容保持严格保密性的情况下,对一个秘密数所宣称的性质进行证实(例如,符合商业上的需求)。这部分要引入零知识协议,说明了在各种现实应用中对特定安全性需求的多样性。这种多样性超越了机密性、完整性、认证和不可否认性。在本书的最后一个技术章节(第19章)中,我们将解决本书一开始介绍的协议中的遗留问题实现“通过电话公平掷币”。最后的实现协议不但在效率上适宜实用,而且也明确地建立起了强安全性。不用说,对每一个实用密码协议或方案的描述,都是要先给出与之相应的教科书式密码不适用的原因。我们总是以给出相应存在的攻击来说明原因,就相应的攻击而言,这些方案和协议往往存在某些微妙之处。另外,一个实用密码协议和方案的描述,也必是以其所宣称的必须包含的强(实用)安全性成立的分析来结束。因而,本书一些部分不可避免地要包含有数学和逻辑推理、为明示和对付攻击所需的归纳和变换。实用密码学并不是一个轻易驾驭或者稍稍读读就能掌握的论题。尽管如此,本书并不是本仅为专业密码学家所感兴趣的高深研究课题的书。这里所介绍的东西对密码学家来说都是已知的和相当基本的。作者相信,在有充足的解释、实例、足够的数学背景知识和参考材料的情况下,这些东西完全能被非专业人士理解。本书针对的读者对象为:已经或即将完成计算机信息科学、应用数学第一学位课程并计划从事信息安全行业的学生。对他们来说,本书可以作为应用密码学的高级教程·在高科技公司从事信息安全系统设计和开发的安全工程师。如果我们说在科学研究计划中,教科书式密码所产生的危害不是很大的话,至多是出现一种令人尴尬的场面,那么在信息安全产品中使用教科书式密码将会造成严重损失。因此对这类读者来说,了解教科书式密码在现实中的不适用性是非常必要的。而且,这类读者应该对隐藏在实用方案和协议下的安全原理有很好的理解,以便能正确地使用这些方案和原理。第Ⅱ部分所给出的自足的数学基础材料使得本书很适合这类读者自学。对企业信息安全系统管理人员或者生产安全产品的软(硬件开发商这类读者来说,第部分是简单而基本的文化和“商务”方面的培训教程,第Ⅲ部分和第Ⅳ部分是一个适当裁减的密码学和信息安全知识集。这三部分包含有很多基本的密码方案和协议,以及很多对应的攻击方法和防护措施。这些攻击方法和防护措施能被大多数读者理解,不需要有所谓理论基础的负担ε●对于刚开始从事密码学或计算机安全方面研究的博士生这类读者来说,将会欣赏一本能包含强安全性概念的形式化处理并对其进行适当和详细解释的书感兴趣。本书将能帮助他们快速深入地进入这一浩瀚的研究领域。对这类人员来说,第I、Ⅳ、V和Ⅵ部分构成了一个适当深度的文献综述材料,这将能引导他们找到更进一步的文献,并能帮助他们明确自己的研究课题。●本书的适当取舍(如第1章、第2章、第3章和第6章〕也可以组成适合计算机、信息科学和应用数学大学高年级学生学习用的应用密码学教程。致谢非常感谢 Feng bao、 Colin boyd、 Steven galbraith、 Dieter gollmann、 Keith harrison、 Marcus leech、Helger Lipmaa、Hoi- Kwong Lo、 Javier lopez、 John Malone-le、 Cary Meltzer、 Christian Paquin、KenyPaterson、 David pointcheval、 Vincent Rijmen、 Nigel Smart、 David soldera、 Paul van Oorschot Serge Vaudenny和 Steek Zabao他们花费了大量时间校阅有关章节或全书,并提供了非常有价值的评论、批评和建议,使得本书更加完善。本书还得益于向下列人士的请教: Mihir bellare、 Jan Camenisch、 Neil dunbar、 Yair Frankel shaiHalevi, Antoine Joux、 Marc Joye、 Chalie kaufman Adrian Kent、 Hugo Krawczyk、 Catherine Meadows、lMunro、 Phong Nguyen、 adia perlman、 Marco ricca、 Ronald rivest、 Steve Schneider、 ictor Shoup、lgorShparlinski FH Moti Yung作者还要感谢 Prientice-Hall PTR的 Jill harry和 HP Professional books的 Susan Wright,他们鼓励并引导我写作了本书,并在我漫长的写作中提供了技术帮助,感谢 Prientice-Hall PtR的Jennifer Blackwell, Robin carroll、 Brenda mulligan、 Justin Somma和 Mary Sudul以及 HP ProfessionalBok的 Walter bruce和 Pat Pekaryo还要感谢我在布里斯托尔 Hewlett-packart实验室的同事们在技术修辞和管理方面给予的支持,他们是 David Ball, Rachard Cardwell, Liqun Chen、 Lan cole、 Gareth Jones、 Stephen Pearson和Martin Sadler作者于英国布里斯托尔2003年5月月录第一部分引言备◆甲p▲合●▲命P●●▲●●P●d血●p●◆自q◆唱鲁即·◆·号·鲁冒中·即·罪●b●鲁即●罪申中?鲁中银。■甲第1章一个简单的通信游戏1.1一个通信游戏21.1.1我们给出密码学的第一个应用示例…1.1.2对密码学基础的初步提示…1..3信息安全基础:计算困难性的背后1.1.4密码学的新作用:保证游戏的公平性····4···●■■·■■4■幽■自■■12描述密码系统和协议的准则1.2.1保护的程度与应用需求相符合566中t·■dp即“画.2.2对安全性的信心要依据所建立的“种系”1.2.3实际效率中■中●·甲甲●中····自争··q4◆如甲·电命“4即·自“·甲q甲●中甲↓·甲p■·q1.24采用实际的和可用的原型和服务1.2.5明确性…■哥■■■■↓命1.2.6开放性13本章小结…2习题第2章防守与攻击…∷…1421引言………142.1.1本章概述………………1442,2加密………………………1423易受攻击的环境( doley-Yao威胁模型)…24认证服务器……………1725认证密钥建立的安全特性…1826利用加密的认证密钥建立协议26.1消息保密协议…62攻击、修复、攻击、修复…2.63消息认证协议……26.4询问-应答协议26.5实休认诳协议…266一个使用公钥密码体制的协议·◆中·日t日甲自晋节p即甲晋骨qp日2827本章小结习题第二部分数学基础自D■d■自●画看画画画中自甲甲·即↓甲聊标准符号第3章概率论和信息论………q血●自曲血31引言………3.1.1本章纲要……363.2概率论的基本概念363.3性质34基本运算……………………383.4.1加法规则■pp口■342乘法规则3.4.3全概率定律……35随机变量及其概率分布包t命此·q6阜q司导·1号4103.5.1均匀分布。看P电电352二项式分布3.53大数定律36生日悖论……………………………3.6.1生日悖论的应用:指数计算的 Pollard袋鼠算法37信息论3.7.1熵的性质血日甲:4::日3.8自然语言的冗余度39本章小结…………习题…■鲁中1p第4章计算复杂性嚼争中中中4.11本章概述鲁ψ■·■■q卡ψ自■■·4命ψ◆;。d··哥b●自p甲■4申P■■4即命甲444甲44m甲甲■日日日甲甲日日甲日甲·日日日甲甲·噜2图灵机4.3确定性多项式时间看管甲4.3.1多项式时间计算性问题43.2算法与计算复杂度表示…44概率多项式时间…6544.1差错概率的特征…4.4.2“总是快速且正确的”子类…684.4.3“总是快速且很可能正确的”子类■冒4◆甲罪甲·■司吧甲甲p甲4.44“很可能快且总是正确的”子类…甲■●◆■甲■●甲■q即鲁■甲甲看旨了044.5“很可能快且很可能正确的”子类4.46有效算法4.5非确定多项式时间………4.5.1非确定多项式时间完全中上p■■唱4q·即甲导●中·q·q4.6非多项式界∴等看乱?冒争兽《自节烟%·甲冒号t晋音首背即节·甲了即如甲甲?q鲁↓即即■看824.7多项式时间不可区分性计算复杂性理论与现代密码学4.8.1必要条件……4.8.2非充分条件864.9本章小结习题12第5章代数学基础…p鲁由山●看山◆:4.bad5.1引言由·“司·“』日●血乱卡角4日●自D中中日曲山d■啁5.1.1章节纲要888q·甲甲52群………………………………5.2.1拉格朗日定理……………915.22群元素的阶………935.2.3循环群524乘法群Z……即日··b日即日甲自·早·甲甲看日·甲早鲁即44D严甲}t·4“●D■p■◆9653环和域…………9754有限域的结构9854]含有素数个元素的有限域■自■口■甲司54.2模不可约多项式的有限域4●■斷●·命甲1pp…100543用多项式基构造有限域104544本原根…申中·即即。甲·■甲■晋看pp【bd。■4■55用椭圆曲线上的点构造群……10855.1群运算………109552点乘112553椭圆曲线离散对数问题11256本章小结…113习题114第6章数论1156.1引言………11561.1本章概述11562同余和剩余类..早...··吾↓·4·44····:.:4···‘“·.▲:·4:"◆●·4+s115621Z中运算的同余性质………622求解Z,中的线性同余式117623中国剩余定理…11863欧拉函数帽省■■·自日·甲dp申垂4甲◆·一。看d■64费马定理欧拉定理拉格朗日定理65二次剩余…651二次剩余的判定25652勒让德雅可比符号……66模—个整数的平方根………………128661求模为素数时的平方根……128662求模为合数时的平方根67Bhum整数…68本章小结习题……第三部分基本的密码学技术……………·137第7章加密——对称技术1387引言……137.1.1本章概述命鲁■·■p自■备ppb7.2定义…73代换密码7.31简单的代换密码1407.3.2多表密码14273.3弗纳姆密码和一次一密7.4换位密码7.5古典密码:使用和安全性…7.5.1古典密码的使用4575.2古典密码的安全性………1457.6数据加密标准(DES)…………76.1介绍DES…………62DES的核心作用:消息的随机非线性分布14876.3DES的安全性……罪斷昏■●●。b4晋ψpbb7.7高级加密标准(AFS)…1507.7.1 Rijndael密码概述………7.72 Rijndael密码的内部函数…7.7.3 Rijndael内部函数的功能小结快速而安全的实现775ABS对应用密码学的积极影响运行的保密模式15578.1电码本模式(ECB)…………1567.82密码分组链接模式(CBC)……………157783密码反馈模式(CFB)……1607.84输出反馈模式(OFB)…785计数器模式(CIR)……………16179对称密码体制的密钥信道建立…………1617.10本章小结…163第8章加密——非对称技术81引言………………8.1.1本章概述……………………82“教科书式加密算法”的不安全性8.3 Diffie-Hellman密钥交换协议16783.1中间人攻击16884 Diffie-Hellman问题和离散对数问题…841任意参数对于满足困难假设的重要性85RsA密码体制(教科书式)……86公钥密码体制的分析…17587RsA问题……88整数分解问题89教科书式RSA加密的不安全性t791489l中间相遇攻击和教科书式FSA上的主动攻击………∴……1798.0Rain加密体制〔教科书式)181811教科书式 Rabin加密的不安全性8.12 ElGamal密码体制(教科书式)…8.13教科书式 Gamal加密的不安全性…8.13.1教科书式EGam加密的中间相遇攻击和主动攻击…187814公钥密码系统需要更强的安全定义815非对称密码与对称密码的组合……8.16公钥密码系统密钥信道的建立…·■●b看 MT1b加看89817本章小结………………………习题………………190第9章理想情况下甚本公钥密码函数的比特安全性…………l9291前言9.11本章概述92RSA比特19293 Rabin比特93.1Bum- Blum-Shul伪随机比特生成器…94 ElGamal比特19695离散对数比特96本章小结习题…………第10章数据完整性技术……………………201101引言…●』血■自4■L·噜自自t一自唱■自■自4吾自血山画血自甲pbm10.1.1本章概述0.2定义4●中即即冒司看p自命ψ电■dd·唱晋伊■罪命着血◆……………2010.3对称技术……20210.3.1密码杂凑函数…10.3.2基于密钥杂凑函数的MAC…20510.3.3基于分组加密算法的MAC206104非对称技术Ⅰ:数字签名201041数字签名的教科书式安全概念208104.2RSA签字体制(教科书式版本)20910.4.3RsA签字安全性的非形式化论证……2091044 Rabin签名体制(教科书式版本)………·21010.4.5关于Rhin签名的一个自相矛盾的安全性基础……………………………2101046 ElGamal签名体制………212104.7E〔叫l签名体制安全性的非形式化论证1048 ElGamal签名族中的签名体制……215104.9数字签名体制安全性的形式化证明………自自■自血。·自218105非对称技术Ⅱ:无源识别的数据完整性21810.6本章小结………嗶唱■申q·b聊看ψ··电晋申自■看自·嵋昏b■·噜看d■郾bb自画■习题…………22115