密码学概论

《密码学概论》是新一代信息技术网络空间安全高等教育系列教材之一，系统介绍了现代密码学设计、分析及实现的基本理论与技术，主要内容包括对称密码、公钥密码与密码协议三部分。对称密码部分涉及对称加密、杂凑函数、消息认证码等，公钥密码部分涉及公钥加密、数字签名等，作为对称密码与公钥密码的综合应用，密码协议部分介绍密钥建立、零知识证明、电子支付等。《密码学概论》精选密码学典型理论技术，注重阐述密码方案的研究动机与研究思路，探讨方案所蕴含的安全性（隐患），强调对称密码、公钥密码和密码协议在设计、分析与应用上的内在关联，引导读者抽丝剥茧，把握各类技术发展的继承关系，理解密码学理论体系。同时，密码实现技术相关章节介绍**的密码快速实现技术，帮助读者初步掌握密码应用方法。通过扫描二维码，即可访问配套电子课件和关键知识点的教学视频，方便广大教师和同学们参考。

第1章密码学概述
　　密码对于大多数人来说是一个既“熟悉”又“陌生”的概念.对它熟悉，是因为生活中我们经常会用到“密码”，例如，在银行提款时要输入提款“密码”，在网上购物时要输入支付“密码”，以及在登录社交账号时要输入账号“密码对它陌生，是因为密码的含义与应用领域远比上述场景更为丰富，从古代的军事战争到现在的量子通信卫星，从网页浏览到医疗、教育、金融、交通等基础设施，都有密码的身影.可以说，当今社会，密码无处不在.那么，究竟什么是密码？我们为什么需要密码？在本章，我们将通过介绍密码学发展历史解答上述问题，并进一步介绍密码学的基本概念与思想.
　　1.1密码学发展史
　　密码学是一门古老而又年轻的科学.说它古老，因为人类使用密码的历史已逾千年，说它年轻，因为密码真正成为一门科学也不过几十年.下面我们将介绍密码学发展历史中的典型事件，让读者初步了解密码的含义.
　　密码学发展史可大体划分为以下阶段.
　　1.1.1**阶段：古代到1949年
　　这个时期的密码被称为朴素的古典密码，称其为朴素是因为该时期的密码设计主要是基于设计者的直觉和经验，而缺乏系统的理论支撑，其安全性通常依赖于对设计方法的保密.典型的古典密码包括古希腊斯巴达时期的密码棒、高卢战争时期的凯撒密码、16世纪晚期的维吉尼亚密码等.
　　？斯巴达密码棒斯巴达密码棒*早应用于2400多年前的伯罗奔尼撒战争，用于隐藏军事情报.斯巴达密码棒由腰带与木棒组成，腰带表面上看是一条布满无序字母排列的普通腰带，难以分辨出任何有意义的文字信息，但是当把腰带规则地缠绕在木棒上时，它的意义(情报内容）便显现出来，如图1.1所示.
　　？凯撒密码凯撒密码同样是一种传递军事情报的简易密码装置，相传是距今2000余年的罗马帝国统帅凯撒所使用.该密码由内外两个圆环嵌套构成，如图1.2所示，两个圆环上都标有按顺序排列的26个英文字母，使用者可根据外环字母和内环字母的位置对应关系进行消息的加密与解密.
　　？维吉尼亚密码维吉尼亚密码实际上是一种升级版的凯撒密码，曾被用于美国南北战争，且一度被称为“不可破解的密码但是，19世纪50年代英国科学家查尔斯？巴贝奇(Charles Babbage)*先破解了该密码，随后在1863年普鲁士少校弗里德里希？卡西斯基(Friedrich Kasiski)也提出了他的破解方法.
　　图1.1 斯巴达密码棒
　　值得一提的是，中国古代出现过许多非常巧妙的密码方案，例如，虎符与阴书.？虎符虎符*早出现于战国时期，是一种铜制的虎形令牌.与上述古典密码的功能不同，该令牌并非用于隐藏机密信息，而是作为中央发给地方驻军*领的调兵凭证，用于证明所下达的军令来源的真实性——证明军令确实由国君下达，防范假传军令.
　　？阴书阴书则是古代兵书《六韬》记载的一种军事文书，使用时将所要传递的机密消息拆解为三个部分，分别由三位信使携带，即每位信使只传递消息的一部分，即所谓的“一合而再离，三发而一知这实际也是现代密码学领域一种**的秘密分享思想，通过将秘密进行“分散”，降低秘密泄露的风险.
　　随着人类机械技术与电子通信技术的发展，第二次世界大战(以下简称二战)时期的密码成为古典密码技术发展的顶峰.二战期间*具有代表性的密码装置当属德国的恩尼格玛(Enigma)机.Enigma机是德军采用的一种机械电子装置，用于加密军事情报，该装置所采用的加密算法能够很好地隐藏密文的统计规律，同时，Enigma机使用的机械电子技术极大提升了加解密效率，使其成为当时可以进行大规模量产的先进密码设备.但是，从来就没有“不可破解的密码”，密码破译者们扮演了扭转战局的英雄角色.波兰数学家马里安？雷耶夫斯基(Marian Rejewski)*先成功破解了Enigma机，然而德军随后对Enigma机进行了改进，极大提升了破解难度，马里安的破解方法不再适用.面对升级版Enigma机的破解挑战，英国数学家、计算机之父艾伦？图灵(Alan Turing)设计了人类历史上**台用于密码破解的电子计算机，并利用它彻底破解了德军的Enigma机，加速了盟军夺取欧洲战场胜利的进程.二战期间另一个典型的密码案例是日本的“紫密”，它是日本采用的一种机械电子加密装置.但是，美国在1940年就已成功破解了“紫密”，从而能够提前获知日本进攻中途岛的作战计划，并在中途岛战役中大获全胜，一举扭转了太平洋战争局势.
　　1.1.2第二阶段：1949年～1975年
　　1949年，美国数学家、信息论之父克劳德？香农(Claude Shannon)发表了论文《保密系统的通信理论》％这是密码学发展史上一项具有里程碑意义的工作，它为密码学奠定了坚实的理论基础，从此密码成为一门学科，其发展有了严谨的理论支撑.
　　另一项代表性工作是20世纪70年代初期IBM公司的技术报告《Lucifer密码的设计》，其中Lucifer密码正是日后美国数据加密标准DES的雏形.
　　1.1.3第三阶段：1976年至今
　　密码学理论和应用在该阶段得到了蓬勃发展，密码设计、分析与证明理论不断成熟，密码技术不再局限于军事和外交领域，开始进入人们工作与生活的方方面面.这个时期产生了三个具有代表性工作.
　　1.DES数据加密标准DES(data encryption standard)全称数据加密标准，是美国国家安全局(NSA)基于Lucifer密码设计的商用加密算法，该算法于1977年正式成为美国商用数据加密标准.DES是历史上**个公开算法技术细节的商用密码标准，随后在国际上被广泛使用.
　　2.公钥密码诞生1976年，惠特菲尔德？迪菲(Whitfield Diffie)与马丁？赫尔曼(MartinHeilman)发表了论文《密码学的新方向》创造性地解决了对称密码密钥预分配的问题，提出了公钥密码的概念与设计方法，公钥密码由此诞生.
　　3.RSA密码体制1977年，罗纳德？瑞维斯特(RonaldRivest)，阿迪？沙米尔(AdiShamir)和伦纳德？阿德曼(LeonardAdleman)提出了**个具体的公钥密码方案，相关方案(包括加密与签名）以三人姓氏*字母命名，即著名的RSA密码体制.RSA密码体制的提出为公钥密码走向大规模应用跨出了重要一步.
　　现在，各类密码方案被广泛应用于国防、金融、交通、医疗、教育等领域，帮助我们保护数据隐私、确认数据真实性等.然而随着量子技术的不断成熟，目前所采用的大部分密码算法将难以抵抗未来量子计算机的破解.为了防范量子计算机的威胁，近年来各类抗量子计算的密码算法相继提出，密码研究与应用开始跨入后量子时代.当前被广泛应用的各类密码算法未来终将被能够抵抗量子计算的密码技术所取代.
　　从上述密码发展历史可以看出，密码学主要研究如何保障信息不被非法获取、
　　篡改伪造等.密码方案在密码设计者与密码破解者之间的反复较量中伴随人类科技飞速发展，这场较量已从古代的军事战争扩散至当今网络空间的各个角落——密码已成为保障网络空间安全的核心技术与基础支撑.近年来，各类网络安全事件层出不穷，大至破坏国家基础设施的大规模网络攻击，小至植入手机应用窃取个人隐私的恶意代码，对国家安全与个人财产甚至生命安全造成严重威胁.因此，在万物互联的时代，人们更加向往一个安全可靠、风清气朗的网络空间.这种向往源自于人们对安全的根本需求，而这种根本需求正是密码学不断发展的原动力.
　　1.2现代密码学基本概念与观点
　　密码学的研究内容可划分为密码设计与密码分析，简单来说，密码设计是寻求消息保密性与认证性的方法，即研究如何设计安全的密码方案(达成安全性).密码分析是研究加密消息的破解或消息的伪造，
　　即研究如何破解密码方案(破坏安全性).两个方向并非相互*立，而是相辅相成的：设计安全的密码方案需要充分掌握其可能遭受的攻击，而这离不开对方案长期深入的密码分析;成功的密码分析需要充分理解方案各组件的功能与局限性，而这依赖于对密码设计方法、动机与原理的深刻理解.那么，究竟什么是安全的密码方案？或者说密码方案所谓的安全性究竟意味着什么？围绕该问题，我们将介绍现代密码学的基本概念与观点.
　　1.2.1基本概念
　　为了方便介绍现代密码学的基本观点，我们以加密场景为例，引入以下几个基本概念.
　　现代密码学基本概念与观点
　　1.2现代密码学基本概念与观点
　　？明文(plaintext):需要被隐藏(加密）的消息.
　　？密文(ciphertext):隐藏(加密）后输出的消息.
　　？加密(encryption):将明文转换成密文的过程.
　　？加密算法(encryption algorithm):对明文进行加密时具体所采用的规则.
　　？解密(decryption):由密文恢复出原明文的过程.
　　？解密算法(decryption algorithm):对密文进行解密时具体所采用的规则.
　　？密钥(key):加密算法/解密算法通常在一组密钥(encryptionkey/decryptionkey)的控制下进行.
　　如图1.3所示，发送者要加密一条明文，需运行加密算法，以明文与加密密钥h为输入，生成密文.密文通过公开(不安全的）信道发送给接收者.在密文传递过程中，可能会遭受到来自敌手的攻击，例如，监听、篡改等.接收者收到密文后，运行解密算法，以密文与解密密钥k2为输入，输出明文.
　　根据密钥可以将密码体制大体分为两类.
　　？对称密码(symmetric cipher)，这一类密码的发送者和接收者具有相同的密钥，例如，图1.3中k1=k2.
　　？非对称密码(asymmetric cipher)，也被称为公钥(publickey)密码.这一类密码的发送者和接收者使用的密钥是不相等的，例如，图1.3中k1≠k2.
　　注意，对称密码与非对称密码的研究对象非常丰富，并不局限于加密算法，本节仅以加密算法为例阐述密码基本理念.
　　1.2.2安全性与攻击
　　密码用于保障数据安全，但密码学中的安全性(security)究竟是什么？不同的密码方案拥有不同的安全性刻画，其中两个*根本的安全属性是保密性和认证性.简单来说，保密性是指保护信息不被泄露，而认证性是指期望的接收者能够检验消息的合法性，确认消息来源的真实性.实际上，密码学安全性的含义比上述描述更为丰富，各种对于安全性的刻画总有其局限性，这是因为密码的安全性是相对于攻击而言的，而攻击变化多样.提到攻击一般会涉及两个方面——攻击目的与攻击方法.
　　1.2.2.1攻击目的
　　针对不同功能的密码方案，敌手有不同的攻击目的.在密码学中，存在许多不同功能的密码方案，例如，加密方案用来隐藏消息，数字签名方案用来验证消息来源的真实性.针对上述密码方案，敌手对应的攻击目的也有所区别：对于加密方案，敌手的攻击目的是获取目标密文所对应的明文信息.如果敌手能够有效地确定其密钥或目标明文的相关信息，就称该加密方案是可破解的(不安全的而对于数字签名，敌手的攻击目的是伪造合法签名者的签名.如果敌手(在没有签名密钥的条件下）能够有效地伪造签名，则称该签名是可破解的(不安全的).
　　1.2.2.2攻击方法
　　关于攻击方法通常有两种分类方式.
　　**种分类，根据敌手的能动性可以分为被动攻击和主动攻击.被动攻击的敌手可以针对通信信道实施监听，通过监听截获密文后进行分析.主动攻击的敌手的能动性会更强，可以对系统进行串扰、删除、更改、增填、重放、伪造等攻击.
　　第二种分类，根据攻击者已具备的前提条件进行划分，以加密算法为例，主要有以下四种攻击手段：
　　1.唯密文攻击(ciphertext-only attack):敌手只具备密文，根据密文进