密码学基础（第二卷·中文版）

书籍
计算机书籍
　　 密码学涉及解决安全问题的计算系统的概念、定义及构造。密码系统的设计必须基于坚实的基础。本书对这一基础问题给出了系统而严格的论述：用已有工具来定义密码系统的目标并解决新的密码学问题。本书的重点是澄清基本概念并论述解决几个主要密码问题的可行性，而不侧重于对特殊方法的描述。
　　 《密码学基础》第一卷主要讨论的是单向函数、伪随机性和零知识证明。本书在第一卷的基础上接着讨论加密、签名和一般的密码协议。本书可作为密码学、应用数学、信息安全等专业的研究生教材，也可作为相关专业人员的参考用书。
　　 注意：本书第一卷内容共4章，为了体现顺序性，第二卷的章号与第一卷的章号衔接，因此本书（第二卷）正文从第5章开始。本书（第二卷）附录与第一卷的附录序号衔接，因此本书附录为附录c。本书第一卷已由人民邮电出版社出版，书名：《密码学基础》，书号：10355。
　　 密码学涉及解决安全问题的计算系统的概念、定义以及构造。密码系统的设计必须基于坚实的基础。本书对这一基础问题给出了系统而严格的论述：用已有工具来定义密码系统的目标并解决新的密码学问题。
　　 本书的重点是澄清基本概念并论述解决几个主要密码问题的可行性，而不侧重于对特殊方法的描述。
　　 《密码学基础》第一卷主要讨论的是单向函数。伪随机性和零知识证明。本书在第一卷的基础上接着讨论加密、签名和一般的密码协议。本书可作为研究生课程的密码学教材和相关专业人员的参考用书。本书假定读者熟悉算法设计与算法分析，对复杂性理论和概率论也有所了解。

第5章 加密体制
5．1 基本定义
5．1．1 私钥体制和公钥体制比较
5．1．2 加密体制的句法
5．2 安全的定义
5．2．1 语义安全
5．2．2 加密的不可分辨性
5．2．3 安全定义的等价性
5．2．4 多组消息
5．2．5* 均匀复杂度的处理方法
5．3 安全加密体制的构造
5。3．1* 序列密码
5．3．2 预备知识：分组密码
5．3．3 私钥加密体制
5．3．4 公钥加密体制
5．4* 高于窃听的安全性
5．4．1 概述
5．4．2 密钥依赖的被动攻击
5．4．3 选择明文攻击
5．4．4 选择密文攻击

　　 人类对密码的研究与应用已有几千年的历史，但密码学作为一门系统科学则仅仅是上个世纪50年代的事情。1949年，信息论的创始者Shannon发表的著名论文“保密通信的信息理论”将密码学的研究纳入了科学的轨道，使密码学正式成为一门科学。1976年，美国著名学者Diffie和Hellman的经典论文“密码学的新方向”奠定了公钥密码学的基础，它标志着密码学的研究和实践由传统走向现代。1977年，美国公布并实施的数据加密标准DES，揭开了密码学的神秘面纱，使密码学的研究和应用从秘密走向公开，吸引了众多学者和技术人员对其进行研究，从此密码学成为了一门蓬勃发展的学科。而今，随着因特网的迅速普及，信息安全问题引起了全人类的重视，密码学作为信息安全的核心更得到了长足发展。现在，大多数国家或地区都已经成立了密码学会，各种国际国内密码学术会议频繁召开，许多大学都开办了密码学专业并进行本科生和研究生的招生和培养。总之，与密码学相关的众多活动极大地促进了它的研究与应用。
　　 如今，密码学理论研究已比较成熟，国内外已出版了大量有关密码学的书籍，许多著名学者都基于自己的研究出版了专著，这些著作各具特色，其中有不少佳作适合做教材。Oded Goldreich教授所著的《密码学基础》一书就是一本很有特色的密码学教科书，其最显著的特点就是“基础”二字，正如该书前言中引用的那样：“没有根基也许可以造一座小屋，但绝不能造一座坚固的大厦”。密码学所关心的是构造一些能抵抗任何攻击的机制，这种密码机制的设计是一项十分困难的任务，它必须建立在坚实的基础之上。本书对这一基础问题给出了系统而严格的论述。
　　 根深才能叶茂。相信这本书对于希望在密码学的殿堂里能步步登高的学子大有裨益。这正是我们花费大量精力翻译本书的初衷。
　　 本书第一卷出版后，得到了同行专家的高度评价，许多研究工作者表示，该书基础深厚，中译本出版的非常必要和及时。于是，应出版社之约，我们又组织翻译了第二卷。在翻译过程中，得到了蔡吉人院士的支持与鼓励，他还花时间审阅了初稿。北京邮电大学信息安全中心的钮心忻教授、徐国爱博士等给予了大力的支持与协助，秦素娟博士协助校对了部分书稿。在此一并对他们表示衷心地感谢。
　　 本书的出版得到了国家973项目(编号：G1999035804)、国家自然科学基金项目(编号：90204017、60373059)、教育部博士点基金项目(编号：20040013007)和国家863项目(编号：2002AAl43041)的资助，在此表示感谢。
　　 译者
　　 2005年于北京
　　

　　 密码学所关心的问题是构造一些能抵抗任何攻击的体制。构造这样的体制，目的是在遭受企图使它们偏离规定函数性的恶意攻击下，依旧能保持某种期望的函数性。
　　 密码体制的设计是一个十分困难的任务。人们不能仅依靠对有关系统运行环境的典型状态的直观知识。的确，攻击系统的攻击者(adversary)可能企图控制操作环境使之成为非典型状态。人们也不可能对设计用来抵抗特定攻击的策略满意，因为攻击者(将在系统设计完成后才行动)可能试图以和设计者所预料的大不相同的方式来攻击此体制。虽然上述断言似乎是不证自明的，但是，仍有一些人期望在实践中忽略这些赘言不会导致实际损失。实验证明这样的愿望很少能达到，基于伪装的密码体制迟早会被破坏。
　　 按照上述观点，我们认为就攻击者可能使用的特定策略(strategy)进行假设是没有什么意义的。惟一合理的是可以对攻击者的计算能力(abilities)作假设。进一步说来，我们认为密码体制的设计必须建立在在坚实的基础(firm foundations)之上，专门方法和试探方法则是非常危险的。当设计者对体制即将运行的环境十分了解时，试探方法可能有意义，但是密码体制将不得不在恶意选择的环境中运行，这一环境是超出设计者所预想的。
　　 本著作旨在介绍坚实的密码学基础知识。密码学的基础包括：范例、方法、抽象化的技巧、定义，并提出对自然的“安全考虑”的解决方案。我们将介绍一些这样的范例、方法和技术，以及利用它们得到的一些基本结论。我们的重点是阐述这些基本概念，并论证解决这些核心密码问题的可行性。
　　 解决一个密码问题(或说明一种安全需求)是由定义阶段(definitional stage)和构造阶段(constructive stage)组成的。首先，在定义阶段，基于固有利害关系的函数性必须标识出来，适当的密码问题也必须被定义。试图列出所有未曾预料的情况是不可能的，而且容易出错。相反，人们应该按照理想模型中的操作方法定义此函数性，然后需要一种候选方案在真实且被明确定义的模型(表示攻击者的能力)中模拟此操作。定义阶段完成后，接着就是构造一个满足此定义的系统。这样的构造可能使用一些更简单的工具，它的安全性可以通过这些工具的性质来证明(当然，实际中这样的体制也必须满足某些特定的(specific)效率要求)。
　　 本著作重点在于几个最典型的密码问题(例如，加密和签名体制)和几个核心工具(例如，计算难题、伪随机性和零知识证明)。对于每个问题(或工具)，我们首先给出其固有的利害关系(或它的直观目标)，然后定义这个问题(或工具)，最后证明这个问题可以被解决(或这个工具可以被构造)。在最后一步中，我们的着重点在于证明解决此问题的可行性，而不是给出一个切实可行的方案。对于给定(或已知)解决方案的实用性(或不实用性)的级别，我们只作为次要问题来讨论。
　　 计算难题
　　 前面提及的特殊构造(和这个领域的大多数构造一样)只有当某种计算困难(即难题)存在时才存在。特别地，所有这些问题和工具(直接或间接)都要求有能生成难题的实例。这一能力在单向函数的定义(进一步讨论参见2．1节)中可以获得。于是，单向函数就成了大多数密码学问题的最低要求。正如我们将要看到的那样，实际上它们对许多密码学问题来说都足够了(其余的可以通过扩充和扩展单向函数存在这一假设来解决)。
　　 仅凭我们目前对有效计算的理解并不能证明单向函数存在。特别地，单向函数的存在性意味着NP不包含于BPP≥P(“大多数”都不是)，这一结论能够解决许多计算科学方面的著名难题。为了证明这一假设的合理性，我们只能给出数百(或数千)位学者的联合信任。而且，这些信任是关于一个简单描述的假设，其有效性是基于几个公认的猜想，这些猜想是某些领域的核心(例如，对整数进行因数分解是困难的这一猜想就是计算数论的核心)。
　　 既然无论如何我们都需要一定的假设，那么为何不假设我们想要的(即，某一固有的密码学问题的解决方案的存在性呢)?首先，我们要知道想做什么。如前所述，我们必须首先阐述要做什么，即：我们必须经过典型、复杂的定义阶段，但一旦完成定义，我们就能假设导出的定义满足要求吗?恰恰相反。事实是：导出的定义并不意味着它一定能满足，人们可以很容易定义不存在(没有定义中的明显事实)的对象。要证明一个定义是可行的(因此直观上的安全性条件可以完全满足)，方法是构造一个基于更易于理解的(better-understand)假设(即更普遍更为广泛认同的假设)。例如，考虑零知识证明的定义，这样的证明(在非平凡的意义上)是否存在事先并不很清楚。首先可以通过为二次剩余类命题提出一个零知识证明系统来证明这一概念的非平凡性，(没有附加信息)二次剩余类命题是难于校验的。接着，与先验信任相反，后面将证明单向函数的存在性意味着任意NP-断言都可以用零知识证明。这样，那些根本不知道是否成立的事实(以及那些被认为是错误的事实)都可以通过变形为广泛认同的假设(总之没有它们，许多现代密码学问题就失去依托)来证明其成立。总之，并非所有假设都是等价的，因此把一个复杂的、新的、有疑问的假设转变成一个被广泛认同的简单(或者仅仅是比较简单)假设是非常重要的。把新任务的解决方案转变成一个已知的简单任务的假定安全方案就意味着：给出一个使用已知原型的构造，可以解决新的任务。这就意味着，我们不但知道(或假设)新任务是可以解决的，而-且还能找到一个基于某一原型的解决方案，这一原型是已知的，并有几个可供选择的实现方法。
　　 结构和先决条件
　　 我们的目标是给出密码学的基本概念、技巧和结论。如前所述，我们的重点在于阐明基本概念及其相互关系。这可以通过一种中不依赖于某些通用数论例子的特性的方法来实现。这些特殊的例子在这个领域的发展中起着核心作用，并为所有密码学原型提供了最切合实际的实现方法，但是这并不表示我们的陈述必须和它们相关联。相反，当我们把概念在抽象层提出，并把它们从特定的实现方法中分离出来时，我们才能以最好的方式阐明它们。与本著作关系最紧密的背景知识都是以算法(包括随机化算法)的基本知识，可计算性和初等概率论的方式提出的。某些构造的实现需要基于(计算性的)数论的背景知识，但是本著作并非真的需要这一知识(为了证明本著作提出的一些实现方法的实例，本卷在附录中给出了包括与第一卷最密切相关的背景知识)。
　　 本著作的构成。本著作由两部分构成(参见图0．1)：基本工具和基本应用。第一卷(即，[108])包括一个介绍性的章节和第一部分内容(基本工具)。它包括关于计算难题(单向函数)，伪随机性和零知识证明这些章节。这些基本工具将用于第2卷中的基本应用，其中第二卷是由加密体制，数字签名和一般的密码协议组成的。
　　 本著作是按逻辑划分为两卷的。并且，这样划分还有如下优点：不必等第二部分完成就可以出版第一部分。开始时，还计划写第三部分，基础之上的知识。这一部分计划讨论密码学在计算机科学其他领域(特别是在复杂度理论中)的影响，并提供对更高深安全问题的各种不同的处理。回顾前面，我们感觉第——个问题已经在[106]中解决了，而第二个问题更适合于在测量集合中讨论。
　　 本卷的结构安排。本卷(第二卷)共有三章，分别讨论加密体制，数字签名和消息认证，以及一般密码协议。另外还包括一个对第一卷进行纠错和补充的附录。图0．2描述了一个更进一层的本卷的结构。由于本卷是对第一卷的继续，我们在两卷中使用同一计数系统(因此本卷的第一章定为第五章)。这就使得我们可以方便地参考第一卷中出现的小节，定义和定理(例如，1．3节介绍了本著作中所用的计算模型)。与这个规则惟——例外的就是在两卷中使用了不同的参考书目(因此参考书目的编号不同)。
　　 在每一章的末尾都给出了历史记录，关于进一步阅读的建议，未决问题和一些习题。习题大部分是用来帮助和测验对主要问题的理解，而不是用于测验并鼓励创新。未决问题都是很著名的，再者，我们建议读者核实一下它们目前的发展现状(例如，通过我们即时更新的布告站点)。
　　 本著作英文版的布告站点。我们打算维护一个列出各种修正的站点。站点地址是
　　 http://www.wisdom.weizmann.ac.il/～oded/foc-\book.html
　　 如何使用本书
　　 本书可以用作教科书和参考书。也就是说，它既是面向初学者又是面向专家学者的。为了达到此目标，本书对基础阅读材料的描述是非常详细的，这样大多数计算科学的大学生都能掌握它。程度高的学生(和专家学者)可能会觉得这些部分的进度太慢了，但是我们尝试让他们可以很容易就跳过这些细节部分。特别地，证明过程通常是按一种组合方式描述的。首先我们给出主要思想的高度概略，然后才开始具体细节的描述。从精练描述到具体细节的转变通常用“详述如下”的字眼来指示。

　　 1949年C．E．Shannon发表著名论文“Communication Theory ofSecrecy”之前的几千年时间里，密码学仅仅是一些加密技巧的组合，没有系统的理论基础。上世纪70年代初美国国家标准局正式向社会公开招标，以透明竞争的方式征集民用数据加密标准，至此，密码学的神秘面纱被揭开，密码学的研究和应用从秘密走向公开，从专用机构走向民间。1976年，美国学者W．Diffie和M．E．Hellman在其发表的论文“New Directions in Cryptography”中提出了一种崭新的密码体制，开创了公钥密码学的新纪元，标志着密码学的研究和实践由传统走向现代。如今工业界和学术界对现代密码的研究与应用都十分重视，大多数国家和地区都成立了密码学学会，定期举办各种学术会议，出版学术刊物和著作。特别是近年来，许多高等院校都先后开办了信息安全相关专业，并将“密码学”作为本科生和研究生教育的一门重要课程，因此，优秀的密码学教材的撰写和引进就成了当前我国教育界的一个重要课题。最近，教育部组织专家编写了“全国信息安全专业本科教学规范”，其中对《现代密码学》课程的教学大纲进行了明确的阐述，这对规范我国密码学的本科教材建设具有重要的推动作用。但是，针对密码学的研究生教育，目前还没有出台类似的规范。
　　 由Oded Goldreich教授编写的《密码学基础》一书是一本很有特色的针对研究生的密码学教科书。该书分为两卷，其中，第一卷已经出版。现在出版的是该书的第二卷。该书有以下特点：
　　 1．“数学味”较浓。全书特别突出“基础”，对所有内容的讨论几乎都是从最基础部分开始，所以，读者必须具有较好的数学功底和严谨的逻辑思维习惯。这样做的优点是有利于读者进行更深入的密码学后继学习和研究，缺点是可能使部分更关心应用的读者失去认真研读的耐心。
　　 2．系统性较强。书中对相关概念、定义、引理、定理、协议等的描述层次分明，非常规范和系统，逻辑推理深入且仔细。这样做的优点是能够有效训练高校学生的学习和科研能力，缺点是容易使部分特殊兴趣的读者陷入过多的精细概念之中从而“只见树木，难见森林”。
　　 3．目标明确。本书的选题很精简，重点讨论了密码学的核心部分(加密体制、数字签名、消息认证和通用密码协议)，对每个问题都是从研究意义、定义、被解决的可行性来加以论述。这样做的优点是对每个主题的研究非常深入且完整，缺点是容易忽略密码学的众多应用。
　　 综合各方面的情况，我认为本书不仅是广大密码学理论研究者非常有益的参考书，也是相关专业研究生密码学基础教育的参考教材。
　　 北京邮电大学信息安全中心杨义先教授和温巧燕教授组织科研力量相继翻译出版了这本经典著作的第一卷和第二卷，这是一件有意义的工作。据我所知，为了保证翻译质量，他们付出了辛勤劳动，比如，多次召开研讨会，讨论相关翻译难题；将翻译初稿提交给国内相关权威专家征求意见等。我衷心祝愿该书能为我国广大密码学研究工作者提供有意义的帮助，也希望该书的出版和发行能为我国密码学基础研究起到一定的推动作用。相信随着我国大批密码学优秀科班学生的毕业，我国密码学的理论和应用研究将会再上一个新台阶。
　　 中国工程院院士
　　 2005年4月13日