现代密码学精讲课件

第2章现代密码学精讲第2章现代密码学精讲1本章要点现代密码学框架现代密码学的理论基础对称加密标准：DES和AES公钥密码体制：RSA和ElGamal体制本章要点现代密码学框架22.1现代密码学框架

2.1.1什么是密码学

定义1

密码学是研究与信息安全各方面有关的(比如机密性、数据完整性、实体认证及数据源认证)数学技术的一门学科。2.1现代密码学框架2.1.1什么是密码学3

2.1.1什么是密码学(续)发送者Alice密钥源分析者Eve接收者Bob安全信道公共信道加密器Ek解密器Dk明文m密文c明文m密钥k密钥k图2.1Shannon保密系统2.1.1什么是密码学(续)发送者密钥源分析者接收者安全4

2.1.1什么是密码学(续)

通信中的参与者(1)发送者(Alice)：在双方交互中合法的信息发送实体。(2)接收者(Bob)：在双方交互中合法的信息接收实体。(3)分析者(Eve)：破坏通信接收和发送双方正常安全通信的其他实体。可以采取被动攻击和主动攻击的手段。

信道

(1)信道：从一个实体向另一个实体传递信息的通路。(2)安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道。(3)公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道。2.1.1什么是密码学(续)52.1.2现代密码学中的对称与非对称密码思想加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#对称密码加密密钥与解密密钥同：K1=K2代表系统：DES和AES2.1.2现代密码学中的对称与非对称密码思想加密器分析者解62.1.2现代密码学中的对称与非对称密码思想(续)若互联网上有n个用户，则需要个密钥，若n=1000，则NK500000。#如此众多的密钥如何建立，如何保存？2.1.2现代密码学中的对称与非对称密码思想(续)若互联网72.1.2现代密码学中的对称与非对称密码思想(续)加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#非对称密码加密密钥与解密密钥不同：K1

K2代表系统：RSA和ElGamal2.1.2现代密码学中的对称与非对称密码思想(续)加密器分82.1.3密码学的演进及目前的状态安全依赖于保密加密方法安全依赖于保密密钥安全依赖于保密部分密钥古典密码私钥密码公钥密码#公钥密码体制以其强大的功能使得私钥密码体制显得已经过时，但是强大的功能不是无代价获得的，公钥密码的计算量远大于相同情况下的私钥密码。因此，不适合加密大量数据，只适合于完成少量数据加密，如传送私钥密码的密钥、签名等等。2.1.3密码学的演进及目前的状态安全依赖于保密加密方法安92.1.4现代密码学主要技术SecurityPrimitivesPublic-keyPrimitivesSymmetric-keyPrimitivesUnkeyedPrimitivesArbitrarylengthhashfunctionsSymmetric-keyciphersRandomsequencesOne-waypermutationsBlockciphersStreamciphersArbitrarylengthhashfunctions(MACs)SignaturesPseudorandomsequencesIdentificationprimitivesPublic-keyciphersSignaturesIdentificationprimitives图2.2密码学本原分类2.1.4现代密码学主要技术SecurityPrimit102.1.4现代密码学主要技术(续)(1)加密

加密基本术语明文消息空间M:某个字母表集密文消息空间C:可能的密文消息集加/解密密钥空间K:可能的加/解密密钥集加/解密函数Ee

K(m

M)

/

Dd

K(c

C)

:一个从M到C/C到M的有效变换2.1.4现代密码学主要技术(续)(1)加密112.1.4现代密码学主要技术(续)

加密方案加密方案是由一个加密函数集{Ee:e

K}和解密函数集{Dd:d

K}构成，并且满足任意一个加密密钥e

K存在唯一一个解密密钥d

K使

Dd=Ee-1，也就是对于所有明文消息m

M

，存在Dd(Ee(m))=m，(e,d)称为密钥对。设计加密方案就是确定M、C、K、{Ee:e

K}、{Dd:d

K}的过程。定义2

一个加密方案可以被破译是指，第三方在没有事先得到密钥对(e,d)的情况下，可以在适当的时间里系统地从密文恢复出相对应的明文。#适当的时间由被保护数据生命周期来确定。2.1.4现代密码学主要技术(续)加密方案122.1.4现代密码学主要技术(续)私钥加密定义3

一个由加密函数集{Ee:e

K}和解密函数集{Dd:d

K}组成加密方案，每一个相关联的密钥对(e,d)，如果知道了e在计算上很容易确定d，知道了d在计算上很容易确定e，那么，就是私钥加密方案。#私钥加密需要一条安全信道来建立密钥对。

主要技术：分组密码与流密码定义4(分组密码)将明文消息在编码集按照固定长度t进行分组，再一组一组地加\解密明\密文消息。#著名的DES、AES都是这类密码。2.1.4现代密码学主要技术(续)私钥加密132.1.4现代密码学主要技术(续)

定义5K是加密变换集的密钥空间，序列

e1e2…

ei

K称为密钥流。定义6(流密码)消息m以串的形式(m1m2…mi)给出，密钥e1e2…ei是K上的密钥流。流密码通过ci=Eei(mi)给出密文消息(c1c2…ci)；如果di为ei的逆，解密则通过mi=Ddi(ci)完成。

2.1.4现代密码学主要技术(续)定义5K是加142.1.4现代密码学主要技术(续)

公钥加密

定义7一个由加密函数集{Ee:e

K}和解密函数集{Dd:d

K}组成加密方案，每一个相关联的加/解密密钥对(e,d)，加密密钥e公开，称为公开密钥，而解密密钥d保密，称为秘密密钥。#显然安全公钥密码系统要求从e计算d为不可能。2.1.4现代密码学主要技术(续)公钥加密152.1.4现代密码学主要技术(续)公钥加密实例Ee(m1)=c1A1Ee(m2)=c2A2Ee(m3)=c3A3Dd(c1)=m1Dd(c2)=m2Dd(c3)=m3Bobec1eec2c3#因为存在替代攻击问题，公钥系统中公开密钥e必须认证，一般是建立PKI。2.1.4现代密码学主要技术(续)公钥加密实例Ee(m1)162.1.4现代密码学主要技术(续)(2)数字签名技术基本术语明文消息空间M:某个字母表中串的集合签名空间S:可能的签名集合签名密钥空间K:用于生成签名的可能密钥集，具体取值k需要保密验证密钥空间K’:用于验证签名的可能密钥集，具体取值k’需要公开签名函数SK(m

M):从M到S的有效变换验证函数VK’(m

M,s):一个从M

S到输出{True,False}的有效变换2.1.4现代密码学主要技术(续)(2)数字签名技172.1.4现代密码学主要技术(续)

签名过程

签名(签名者完成)

1)对一条需要签名的消息m

M计算签名s=Sk(m)。

2)将对消息m的签名(m,s)发送出去。

验证(验证者完成)

1)得到对应签名者的验证算法Vk’

，计算u=Vk’

(m,s)。

2)如果u=True，接受签名；如果u=False，拒绝签名。2.1.4现代密码学主要技术(续)签名过程182.1.4现代密码学主要技术(续)签名和认证函数必须满足的性质1)当且仅当Vk’

(m,s)=True时，s是消息m的合法签名。

2)

对于任何签名者以外的实体在计算上不可能得到任意的一组mf和sf满足Vk’

(mf,sf)=True。

数字签名的争议解决(不可否认)

如果签名者和验证者对签名发生争议，可由验证者带着签名(m,s)提交给可信任第三方(TTP)，由TTP验证该签名，最后进行仲裁。2.1.4现代密码学主要技术(续)签名和认证函数必192.1.4现代密码学主要技术(续)数字签名技术在公钥基础设施(PKI)中的应用

除非对密钥产生的认证性和合法性有足够的信任，否则公钥密码的优势就十分有限。公钥基础设施或简称PKI是一个框架。这个框架主要由一组策略组成。策略确切定义了关于密码系统运行和密钥产生和发布与证书的规则。X.509是设计用来在大型计算机网络中提供目录认证服务的国际标准。由于它本身是ISO/ITU的一个标准，很多实用产品都基于它开发出来。例如，X.509被用在Visa和Mastercard的安全电子交易标准中。2.1.4现代密码学主要技术(续)数字签名技术在公202.1.4现代密码学主要技术(续)图2.3X.509的结构原理2.1.4现代密码学主要技术(续)图2.3X.509的结212.1.4现代密码学主要技术(续)2.1.4现代密码学主要技术(续)222.1.4现代密码学主要技术(续)图2.4证书认证过程A1A6认证VT(A6||e6,s6)秘密密钥d6A2,e2,ST(A2||e2)=s2A3,e3,ST(A3||e3)=s3A4,e4,ST(A4||e4)=s4e6,s6Dd6(c)=mc=Ee6(m)PublicfileA1,e1,ST(A1||e1)=s1A5,e5,ST(A5||e5)=s5A6,e6,ST(A6||e6)=s6A2,e2,ST(A2||e2)=s2#证书权威负荷小(离线、非交互、存储证书)，权限低2.1.4现代密码学主要技术(续)图2.4证书认证过程A232.1.4现代密码学主要技术(续)

公钥证书的产生

情况1可信方产生密钥对。可信方为实体产生公钥算法的密钥对，并将公开密钥和绑定身份的公钥证书通过公共信道发给该实体。实体在证明了自己的身份(例如，出示身份证或个人可信照片)后，将通过安全信道得到对应的秘密密钥。

情况2实体产生自己的密钥对。实体产生自己的公钥算法的密钥对，并安全地将公开密钥传送给可信方(例如，通过可信通道或派人送达)，这里主要是保证公开密钥的真实性。在验证了公开密钥来源的真实性后，可信方为公开密钥生成证书。2.1.4现代密码学主要技术(续)公钥证书的产生242.1.4现代密码学主要技术(续)证书链和证书路径图2.5证书链2.1.4现代密码学主要技术(续)证书链和证书路径图2.5252.1.4现代密码学主要技术(续)

(3)认证与鉴别技术

鉴别或实体认证定义9鉴别或实体认证是一个过程。在这个过程中一方通过获得一些确定的证据来确认参加实体认证的另一方的身份，而具有相应身份的实体也确实就是正在参与这一认证过程的另一方。例子1实体A与B通电话，如果A与B认识就可以通过声音来确定对方的真实性。例子2实体A通过信用卡在银行ATM机上取钱。#特点：时实性。2.1.4现代密码学主要技术(续)(3)认证与262.1.4现代密码学主要技术(续)直观安全目标：a在宣称者A和验证者B都诚实地执行认证时，A能向B成功地证明自己，也就是B将完成执行并接受A所宣称的身份。b(不可转移性)验证者B不能从与宣称者A交互中获得的信息，成功地向第三方C来冒充A。c(不可冒充性)任何一个非宣称者A的C想通过扮演A的身份，通过验证者B的认证，让B接受A的身份的可能性可以忽略。这里，可以忽略的含义是概率小到没有具体的实际意义，准确的度量需要根据实际应用而定。

d即使如下情况存在，以上三个条件仍然成立。d.1宣称者A和验证者B之间以前进行的多项式次认证会话且被窃听;d.2冒充者C以前参与了同宣称者A或（和）验证者B的认证执行;d.3冒充者C可能发起多个认证会话并行运行。2.1.4现代密码学主要技术(续)直观安全目标：272.1.4现代密码学主要技术(续)数据源认证定义10数据源认证或消息认证技术，提供一方通过一些附加的证据，确定消息的产生一方的真实身份。例子3实体A向实体B发送电子邮件，电子邮件通过网络传输并存储，在某个时间由B接收到，由于没有直接通信，B这时可能要求认证邮件确实来自A。2.1.4现代密码学主要技术(续)数据源认证282.1.4现代密码学主要技术(续)

(4)密码Hash函数技术定义11Hash函数h()是一个有效的计算方法，它将一个任意长度的二进制位串影射成固定长度的二进制位串，这个固定长度的二进制位串叫Hash值。

修改发现码(MDCs)附加性质1)Hash函数是单向函数，即给定y，找到任意x，满足y=h(x)计算不可能。2)已知x，找x'，满足h(x)=h(x')计算不可能。3)找一任意对x和x'，满足h(x)=h(x')计算不可能。#修改发现码可以进一步分类，单向Hash函数(1-2)(OWHFs)和碰撞抵抗Hash函数(2-3)(CRHFs)。2.1.4现代密码学主要技术(续)(4)密码Ha292.1.4现代密码学主要技术(续)

消息认证码(MACs)消息认证码的目的，通俗讲就是不附加任何其他机制，确保消息来源的真实性的Hash函数。消息认证码有两个不同功能的参数，即消息和秘密密钥。Hash函数无密钥有密钥修改发现码(MDCs)其他应用其他应用消息认证码(MACs)图2.6密码Hash函数的简单分类2.1.4现代密码学主要技术(续)消息认证码(M302.1.4现代密码学主要技术(续)(5)随机数与随机序列密码中以伪随机序列发生器代替随机序列发生器。伪随机序列发生器以短的随机数做种子，以固定方式产生伪随机序列。#伪随机序列与真随机序列不可区分假设，与安全数字签名、公钥密码的存在性等价。2.1.4现代密码学主要技术(续)(5)随机数与随312.1.5评价现代密码算法的标准

Kerckhoffs准则在评估一个密码系统安全性时，应该总是假定我们的敌人了解实际使用的各种方法。

#落实到现代密码算法中就是攻击者知道密码算法的所有执行细节，算法的安全不应该依赖于对算法的保密。2.1.5评价现代密码算法的标准Kerckhoffs322.1.5评价现代密码算法的标准(续)Shannon提出的“优质”密码算法特征(1)加解密的工作量应该由所要求的安全程度决定。(2)密钥集合和加密算法不应该过于复杂。(3)执行过程应该尽量简单。(4)密码中的差错不应该具有传播性，也不应该影响报文中的其他信息。(5)加密后的文本大小不应该比原始报文更大。2.1.5评价现代密码算法的标准(续)Shanno332.1.5评价现代密码算法的标准(续)“可信赖的”加密体制的特点(1)有可靠的数学基础。(2)经过专家的严格分析，证实是可靠的。(3)经得起时间的检验。2.1.5评价现代密码算法的标准(续)“可信赖的”加密体制342.2现代密码学的理论基础现代密码学要求很高的数学基础，包括：数论、抽象代数与有限域、计算复杂理论、信息论、概率论等。但是掌握基础的密码算法并不需要精通过多的底层数学理论。这里我们仅讲述掌握本章的密码算法所需要的计算复杂理论、数论等的基础知识。2.2现代密码学的理论基础现代密码学要求很高的数学基352.2.1计算复杂理论

如果加密算法建立在一个已知非常难解决的问题或者可能解的数目巨大的问题之上，那么攻击者要破译算法就注定要完成一个即便不是不可能，也是另人沮丧的任务。即使有计算机的支持，一个穷尽的暴力解答也是不可行的。NP完全问题就是这样一类具有计算复杂特点的问题。我们用非形式化的方式来描述NP完全问题。2.2.1计算复杂理论如果加密算法建立在一个已知非常362.2.1计算复杂理论(续)NP完全问题几个具体实例例子4可满足问题给定逻辑公式满足如下条件：(1)它由变量v1，v2，…，vn和它们的逻辑非¬v1，¬v2，…，¬vn组成。(2)它表现为一系列子句，且每个子句的形式是变量以及逻辑非的逻辑或(

)(3)它表示为这些子句的逻辑与(

)是否存在一种变量的赋值法(赋真或假)，使得公式为真？如果存在，说这个公式是可满足的。例如，(v1)

(v2

v3)

(¬

v1

¬

v3)为可满足的，(v1)

(v2

v3)

(¬

v1

¬

v3)(¬

v2)为不可满足的。2.2.1计算复杂理论(续)NP完全问题372.2.1计算复杂理论(续)例子5背包问题2.2.1计算复杂理论(续)例子5背包问题382.2.1计算复杂理论(续)例子6团给定一个图G和一个整数n，是否存在一个包含n个顶点的子图，使得子图中的每个顶点与其他顶点之间都有一条边[每个顶点都与其他所有顶点相连的图被称为团(clique)]?例如，图2.7有4顶点的团，但无5顶点的团。图2.7图的团子图2.2.1计算复杂理论(续)例子6团图2.7392.2.1计算复杂理论(续)

NP完全问题的特征(1)每个问题都有解法，且总有一个相对简单的解法(尽管该解法也许十分耗时)。(2)如果要列举所有可能性，就需要考虑2n中情况(n与问题有关)(3)这些问题是无关的，分别来自逻辑学、数论和图论。(4)如果能完全猜中，则可以在相对较少的时间内求解每一个问题。2.2.1计算复杂理论(续)NP完全问题的特征402.2.1计算复杂理论(续)

P类和NP类

P类问题是一类问题的集合，这个集合中的问题都可以在一个与问题大小相关的多项式函数时间内完成。NP类问题是所有这样一类问题的集合，假设能够完全猜中，这些问题可以在一个多项式函数时间内得到解决(猜测函数被称为是预言机或非确定性图灵机)。这种猜测是非确定性的。EXP类，它由所有存在指数时间cn内的确定性解法的问题组成，其中，c是一个常数。它们有如下关系，P

NP

EXP。2.2.1计算复杂理论(续)P类和NP类412.2.1计算复杂理论(续)NP完全的含义Cook证明了：如果可满足问题有一个确定性的、多项式时间的算法(不带猜测)，那么对NP中的每个问题都会有一个确定性、多项式时间的算法，即NP=P。Karp证明了背包问题和团问题具有和可满足问题一样的性质。这一问题的逆否命题是：如果可以证明这些问题中的某个问题没有在多项式时间内完成的确定性算法，那么它们中所有问题都不存在确定性多项式时间算法。这里对一个问题的解决是要求找到一个通用算法来解决它的每个实例。2.2.1计算复杂理论(续)NP完全的含义422.2.1计算复杂理论(续)图2.8复杂性的层次结构#P=NP或P

NP2.2.1计算复杂理论(续)图2.8复杂性的层次结构#432.2.1计算复杂理论(续)

已经有很多人对NP完全问题进行了长期研究，如果对确实存在多项式时间算法，那么我们有理由认为已经有人找到了解法。目前，已经有数以百计的问题被证明是NP完全问题。我们列举的这类问题越多，就越有理由确信不存在一个能解决所有问题的简单方法。2.2.1计算复杂理论(续)已经有很多人对NP完全问442.2.1计算复杂理论(续)NP完全性与密码学(1)一个NP完全问题不能保证不存在一种比指数时间更容易的算法，它仅表示我们不大可能找到这一算法。(2)每个NP完全问题都有一个确定性的指数时间算法，即可以与2n成比例的时间运行完成。(3)硬件的不断进步，越来越大规模的问题都能计算了。(4)即使一个加密算法是基于难解问题的，但攻击者未必总是去解这个难解问题才能破译加密算法。2.2.1计算复杂理论(续)NP完全性与密码学452.2.1计算复杂理论(续)其他固有的难解问题数论中存在大量难解问题，但大多数数论中的难解问题都是NP问题，不是NP完全问题。公钥密码体制主要依赖数论中的两个难解问题：大整数分解问题和离散对数问题。2.2.1计算复杂理论(续)其他固有的难解问题462.2.2数论知识(1)基本概念整除性2.2.2数论知识(1)基本概念472.2.2数论知识(续)2.2.2数论知识(续)482.2.2数论知识(续)素数2.2.2数论知识(续)素数492.2.2数论知识(续)200以内的素数：

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

2.2.2数论知识(续)200以内的素数：502.2.2数论知识(续)2.2.2数论知识(续)512.2.2数论知识(续)2.2.2数论知识(续)522.2.2数论知识(续)2.2.2数论知识(续)532.2.2数论知识(续)2.2.2数论知识(续)542.2.2数论知识(续)2.2.2数论知识(续)552.2.2数论知识(续)整数唯一分解定理2.2.2数论知识(续)整数唯一分解定理562.2.2数论知识(续)2.2.2数论知识(续)572.2.2数论知识(续)一次不定方程2.2.2数论知识(续)一次不定方程582.2.2数论知识(续)(2)同余同余定义与概念2.2.2数论知识(续)(2)同余592.2.2数论知识(续)2.2.2数论知识(续)602.2.2数论知识(续)剩余类和完全剩余类2.2.2数论知识(续)剩余类和完全剩余类612.2.2数论知识(续)缩系2.2.2数论知识(续)缩系622.2.2数论知识(续)2.2.2数论知识(续)632.2.2数论知识(续)2.2.2数论知识(续)642.2.2数论知识(续)一次同余式2.2.2数论知识(续)一次同余式652.2.2数论知识(续)2.2.2数论知识(续)662.2.2数论知识(续)(3)原根2.2.2数论知识(续)(3)原根672.2.2数论知识(续)2.2.2数论知识(续)682.2.2数论知识(续)2.2.2数论知识(续)692.2.2数论知识(续)2.2.2数论知识(续)702.2.3群环域的概念(1)群2.2.3群环域的概念(1)群712.2.3群环域的概念(续)2.2.3群环域的概念(续)722.2.3群环域的概念(续)(2)环2.2.3群环域的概念(续)(2)环732.2.3群环域的概念(续)2.2.3群环域的概念(续)742.2.3群环域的概念(续)(3)域2.2.3群环域的概念(续)(3)域752.3对称密码算法：DES和AES

对称密钥体制的问题(1)在安全加密体制中，密钥是需要经常变更的，使得已丢失的密钥只能泄露数量有限的信息。(2)密钥的分发必须保证安全。一种方式就是对密钥分解分发，如图2.9。(3)密钥数目的增长与交换信息的人数的平方成正比，在人数多的时候，可以考虑使用信任中心，如图2.10。2.3对称密码算法：DES和AES对称密钥体制的问762.3对称密码算法：DES和AES(续)图2.9密钥的分块分发图2.10加密信息分发中心2.3对称密码算法：DES和AES(续)图2.9密钥的分772.3对称密码算法：DES和AES(续)2.3.1DES算法描述1974年，IBM向国家标准局(NBS)提交了一个名为LUCIFER的加密算法。NBS将其转给了国家安全局(NSA)进行审定，之后就得到了一个名为数据加密标准DES的算法。1977年，NBS正式将其用于无限制级的政府通信。其间NBS和NSA可能存在某些误会。NSA原本打算DES仅用于硬件执行，但是NBS却公布了过多的技术细节以致于人们可以根据其写出DES加密软件。如果NSA预料到后续的情况发展变化，他们或许不会同意公布DES。2.3对称密码算法：DES和AES(续)2.3.1782.3.1DES算法描述(续)

DES是分组密码，每个分组为64比特数据。64比特明文通过加密最后成为64比特密文。DES的密钥通常写为64比特，但每8比特有一位奇偶效验位，可以忽略。因此，实际只有56比特。算法只使用不超过64位的标准算术操作和逻辑操作，所以在70年代仅使用硬件就可以容易地实现算法。算法的重复特性非常适合专用芯片执行。起初采用软件执行的DES显得笨拙，但目前的软件执行效果也相当不错。DES的核心是一个被称为Feistel系统的部件。2.3.1DES算法描述(续)DES是分组密码，每个792.3.1DES算法描述(续)图2.11DES算法总体流程2.3.1DES算法描述(续)图2.11DES算法总体流802.3.1DES算法描述(续)2.3.1DES算法描述(续)812.3.1DES算法描述(续)初始计算2.3.1DES算法描述(续)初始计算822.3.1DES算法描述(续)函数f(Ri-1,Ki)Ri-1扩张E(Ri-1)KiB1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8置换f(Ri-1,Ki)图2.12f函数计算结构2.3.1DES算法描述(续)函数f(Ri-1,Ki)832.3.1DES算法描述(续)2.3.1DES算法描述(续)842.3.1DES算法描述(续)图2.13DES的S盒2.3.1DES算法描述(续)图2.13DES的S盒852.3.1DES算法描述(续)2.3.1DES算法描述(续)862.3.1DES算法描述(续)密钥变换2.3.1DES算法描述(续)密钥变换872.3.1DES算法描述(续)2.3.1DES算法描述(续)882.3.2DES的安全

DES存在关于密钥长度、叠代次数、S-盒设计准则的问题。特别是S-盒以常量形式给出，但并未明确说明这些常量为何以这种形式出现。虽然IBM声称这些是经过17年大量密码分析得出的结果，但是人们还是十分担心NSA的介入可能为算法安装陷门以利于其解密。2.3.2DES的安全DES存在关于密钥长度、叠代次892.3.2DES的安全(续)(1)弱密钥与半弱密钥图2.144个DES弱密钥即EKEK(x)=x图2.156对DES半弱密钥即EK1EK2(x)=x2.3.2DES的安全(续)(1)弱密钥与半弱密钥图2.902.3.2DES的安全(续)

(2)关于S盒NSA曾公布了一些关于S盒选择的信息：1)没有一个S盒的输出是输入的线性或仿射函数；2)改变S盒的一位输入将至少引起2个输出位的变化；3)固定输入的某一位为0或1后，改变它周围的位不应导致输出的0或1的个数不成比例的变化。2.3.2DES的安全(续)(2)关于S盒912.3.2DES的安全(续)

(3)加密轮数与差分分析攻击差分分析通过微小差异的明文对，研究这些差异对所得密文的影响。如果同时更改输入位的某些组合，输出结果中的某些位也会以很高的概率、以特定方式变化。实践表明，DES在小于16轮的情况下，差分攻击的效率将明显快于搜索全部密钥空间的强力攻击。2.3.2DES的安全(续)(3)加密轮数与差分分922.3.2DES的安全(续)(4)密钥长度问题密钥长度偏小一直是DES的一个安全问题。1)1977年，Diffie和Hellman估计如果花费2千万美元建造一台机器，大约仅需一天就可以破译DES。2)1993年，Wiener利用开关技术设计了更加有效的破译DES设备。3)到1996年逐渐形成了3种破译DES的基本方法。一种方法是利用分布计算；一种是设计专用攻击芯片；折中的方法是使用可编程逻辑门阵列。2.3.2DES的安全(续)(4)密钥长度问题932.3.2DES的安全(续)

4)分布计算方法破译DES变得十分流行，特别是在Internet兴起和壮大的情况下。1997年，RSA数据安全公司开展了破译DES密钥和其加密消息的竞赛。仅仅5个月，RockeVerser就在搜索了25%的密钥空间后发现密钥。接下来，RSA数据安全公司又开展了第二次竞赛。结果用时39天搜索了密钥空间的85%发现了对应密钥。5)1998年，电子领域基金会(EFF)展开了一项名为DES破译的计划。计划的基本思想是：一般使用的计算机对于完成破译DES的任务来说不是最优的。计划使用的结构是，硬件用来判定排除大量不可能的密钥并返回那些可能的密钥；软件则用来处理每一个可能的密钥，判定这些密钥是否确实为密码系统使用的密钥。结果是计划使用1500个芯片平均在大约在4.5天可以完成对DES的破译。2.3.2DES的安全(续)4)分布计算方法破译942.3.2DES的安全(续)6)有传言说根据预先处理的不同，NSA可以在3到5分钟成功破译DES。而在机器方面的开销仅有5万美元。#上述结果说明对于90年代晚期的计算技术而言，加密系统使用56比特的密钥已经显得过短，不能提供强有力的安全保护。2.3.2DES的安全(续)6)有传言说根据预先952.3.2DES的安全(续)(5)增加安全性的DES变化2.3.2DES的安全(续)(5)增加安全性的DES变化962.3.2DES的安全(续)2.3.2DES的安全(续)972.3.3AES算法描述1997年1月2日，国家标准与技术研究所(NIST)宣布，启动设计新的对称分组加密算法，作为新一代加密标准替代DES。新的加密标准将被命名为高级加密标准(AES)。不同于暗箱设计过程的DES，AES的设计方案于1997年9月12向全世界公开征集。2.3.3AES算法描述1997年1月2日，国家标准982.3.3AES算法描述(续)AES需要满足下列要求：(1)必须详细和公开说明对称加密算法的设计原理。(2)算法必须支持最小128比特的消息分组，密钥长度可以为128，192，256比特，而安全强度至少与三重DES相当但效率应该高于三重DES。(3)算法适合于在各种硬件设备上执行。(4)如果算法被选种，不应该存在专利问题并可以在世界范围内使用。2.3.3AES算法描述(续)AES需要满足下列要求992.3.3AES算法描述(续)

1998年8月20日，NIST公布了15个AES侯选算法，这些算法由遍布世界的密码团体的成员提交。公众对这15个算法的评论被当作初始评论(公众的初始评论也被称为第一轮)。第一轮于1999年4月15日截止。根据收到的分析和评论，NIST从15个算法中选出5个算法。2.3.3AES算法描述(续)1998年8月20日，1002.3.3AES算法描述(续)5个参加决赛的AES侯选算法是：MARS(来自IBM，在大型机上的实现进行了优化，个人计算机上就不那么有效了)；RC6(来自RSA实验室，它是RC5的延续，设计非常简单，甚至可以靠记忆记住它)；Serpent(来自RossAnderson，EliBiham，和LarsKnudsen，该算法硬件实现很稳定，以4位子处理器的并行操作为基础)；Twofish(来自BruceSchneier，JohnKelsey，DougWhiting，DavidWagner，ChrisHall，和NielsFerguson，开发者设计了一个替换表的设计方案，该方案依赖于加密密钥而不是依赖固定的替换表)；Rijndael(来自JoanDaemen和VincentRijmen)。这些参加决赛的算法在又一次更深入的评论期(第二轮)得到进一步的分析。2.3.3AES算法描述(续)5个参加决赛的AES1012.3.3AES算法描述(续)

在第二轮中，要征询对候选算法的各方面的评论和分析，这些方面包括但不限于下面的内容：密码分析、知识产权、所有AES决赛侯选算法的剖析、综合评价以及有关实现问题。在2000年5月15日第二轮公众分析结束后，NIST汇集和研究了所有得到的信息，为最终选择提供依据。2000年10月2日，NIST宣布它选中了Rijndael作为AES。NIST指出，之所以选择Rijndael的原因是因为它是安全性、性能、效率、实现方便性和灵活性的最佳组合。2.3.3AES算法描述(续)在第二轮中，要征询对候1022.3.3AES算法描述(续)有限域GF(pn)的知识2.3.3AES算法描述(续)有限域GF(pn)的知识1032.3.3AES算法描述(续)2.3.3AES算法描述(续)1042.3.3AES算法描述(续)2.3.3AES算法描述(续)1052.3.3AES算法描述(续)2.3.3AES算法描述(续)1062.3.3AES算法描述(续)算法架构为使论述简单，我们以使用128比特密钥加密128比特消息为例说明，并且先对算法的整体架构予以说明。算法由10轮组成。每一轮使用一个由原始密钥产生的密钥。第0轮使用原始的128比特密钥。每一轮都是128比特输入128比特输出。AES的结构如图2.16。2.3.3AES算法描述(续)算法架构1072.3.3AES算法描述(续)图2.16AES的结构2.3.3AES算法描述(续)图2.16AES的结构1082.3.3AES算法描述(续)每一轮由四个基本步骤称为层(layers)组成：(1)字节转换(TheByteSubTransformation)：这是一个非线性层主要用于防止差分和线性分析攻击。(2)移动行变换(TheShiftRowTransformation)：这是一个线性组合，可以导致多轮之间各个比特位间的扩散。(3)混合列变换(TheMixColumnTransformation)：这一层的目的与移动行变换相同。(4)轮密钥加密变换(AddRoundKey)：轮密钥与上一层的结果进行异或操作。2.3.3AES算法描述(续)每一轮由四个基本1092.3.3AES算法描述(续)一轮的过程ByteSub(BS)ShiftRow(SR)MixColumn(MC)AddRoundKey(ARK)Rijndael加密(1)使用第0轮密钥执行ARK操作。(2)依次使用第1轮到9轮密钥按顺序执行BS，SR，MC，和ARK操作。(3)使用第10轮密钥按顺序执行BS，SR，和ARK操作。注意最后一轮忽略了混合列变换(MC)层。2.3.3AES算法描述(续)一轮的过程ByteSubS1102.3.3AES算法描述(续)层2.3.3AES算法描述(续)层1112.3.3AES算法描述(续)(1)字节转换2.3.3AES算法描述(续)(1)字节转换1122.3.3AES算法描述(续)2.3.3AES算法描述(续)1132.3.3AES算法描述(续)(2)移动行变换2.3.3AES算法描述(续)(2)移动行变换1142.3.3AES算法描述(续)(3)混合列变换2.3.3AES算法描述(续)(3)混合列变换1152.3.3AES算法描述(续)(4)轮密钥加密变换2.3.3AES算法描述(续)(4)轮密钥加密变换1162.3.3AES算法描述(续)轮密钥产生方法2.3.3AES算法描述(续)轮密钥产生方法1172.3.3AES算法描述(续)

解密字节转换、移动行变换、混合列变换、轮密钥加密变换都存在相应的逆变换：(1)字节转换的逆变换可以通过查另一个表来完成，我们称之为逆字节转换(IBS)。(2)移动行变换的逆变换可以通过字节右移来实现，我们称之为逆移动行变换(ISR)。(3)逆混合列变换(IMC)通过乘上另一个矩阵实现。

(4)轮密钥加密变换实际上是自身的逆。2.3.3AES算法描述(续)解密1182.3.3AES算法描述(续)S-盒原理2.3.3AES算法描述(续)S-盒原理1192.3.3AES算法描述(续)2.3.3AES算法描述(续)1202.3.3AES算法描述(续)解密变换2.3.3AES算法描述(续)解密变换1212.3.3AES算法描述(续)Rijndael解密(1)使用第10轮密钥执行ARK操作。(2)依次使用第9轮到1轮密钥按顺序执行IBS，ISR，IMC，和IARK操作。(3)使用第0轮密钥按顺序执行IBS，ISR，和ARK操作。#为了保持结构的一致性，在最后一轮加密中忽略了MC操作。2.3.3AES算法描述(续)Rijndael解密(1)1222.3.4AES的安全与执行

设计思考(1)由于加密和解密过程不一致，相比DES(全1密钥，加密两次恢复为本身)，相信AES不存在任何弱密钥。(2)不同于Feistel系统，AES对输入所有比特的处理相同，这使得输入的扩展速度很快。实践表明两轮计算就能得到充分扩展，也就是说，所有的128比特输出完全依赖于所有128比特输入。(3)AES的S-盒的建立有明晰而简单的代数意义，这样可以避免任何建立在算法上的门陷，较好避免存在于DES的S-盒上的神秘色彩。AES的S-盒具有良好的非线性特性，它可以很好地用来阻止差分和线性分析。2.3.4AES的安全与执行设计思考1232.3.4AES的安全与执行(续)(4)移动行这一层可以很好地阻止新发现的截断攻击和平方攻击。(5)混合列可以达到字节扩散的目的。这步1个输入字节的改变导致所有4个输出字节改变。(6)轮密钥产生方法使用了密钥位的非线性组合，因为它使用了S-盒，这种非线性组合用来对付当解密者知道了部分密钥并以此推测余下部分的攻击。循环常量(10)(i-4)/4是用来消除在循环过程中生成每个循环差别的对称性。2.3.4AES的安全与执行(续)(4)移动行1242.3.4AES的安全与执行(续)(7)轮次之所以选择10，是因为在6轮情况下存在比强力搜索攻击更好的算法。到2004年，公布的密码分析结果在7轮以上还没有比强力搜索攻击更好的办法。多出4轮能够让人更有安全感。当然，轮次还可以根据需要增加。2.3.4AES的安全与执行(续)(7)轮次之所1252.3.4AES的安全与执行(续)

执行思考我们已经看到Rijndael内部的层是非常简单的，它在很小的代数空间上即可完成。因此，可以高效完成这些层。从前面对Rijndael的内部层描述可以看到，仅有SB/ISB和MC/IMC值得考虑它们的快速实现问题。(1)对于SB/ISB，我们建议使用S-盒查表方法：可以一次建立一个有28=256个字节的小表，长期使用(就是说，这个表可以“固化”在硬件或者是软件中实现)。“查表法”不仅非常有效，还能阻止定时分析攻击，这种攻击根据不同数据的运算时间差异，来推断运算是在比特0还是在比特1上运行。2.3.4AES的安全与执行(续)执行思考1262.3.4AES的安全与执行(续)(2)在MC操作中，有限域GF(28)上的两个元的乘法操作也可以用“查表法”来实现：z=x

y(有限域乘法)，这里x

{01，10，11}和y

GF(28)。我们进一步注意到字节01为有限域乘法单位元，也就是，01

y=y。因而无论用软件还是硬件执行“查表法”时只需要存储2

256=512项，这个表是非常小的。这样实现不仅速度很快，而且还能够减少定时分析攻击的危险。(3)执行IMC操作就不像执行MC操作那么快。这是因为IMC操作的4

4矩阵比MC操作的复杂得多，一般执行IMC操作比MC操作需要多花费30%的处理时间。然而，幸运的是在一些应用中解密是不需要的。2.3.4AES的安全与执行(续)(2)在MC1272.3.5对称密码的应用(1)加密模式通常大多数消息的长度大于分组密码的消息分组长度，长的消息被分成一系列连续排列的消息分组，密码一次处理一个分组。在分组密码的上层，不同的加密模式被开发出来，这些加密模式可以为整体消息加密提供一些希望得到的性质。如：分组密码的不确定性(随机性)，将明文消息添加到任意长度(使得密文长度不必与相应的明文长度相关)，错误传播控制，流密码的密钥流生成。等等。2.3.5对称密码的应用(1)加密模式1282.3.5对称密码的应用(续)密码分组链接(CBC)模式C0P1EKC1P2EKC2…图2.17CBC模式加密2.3.5对称密码的应用(续)密码分组链接(CBC)模式1292.3.5对称密码的应用(续)2.3.5对称密码的应用(续)1302.3.5对称密码的应用(续)(2)修改发现码(MDC)实例-使用DES的MDC-2

在分组密码基础上建立Hash函数的主要动机是：如果系统已经拥有了非常有效的分组密码，那么以分组密码作为实现Hash函数的主要部件，将既可以提供Hash函数的功能，又能使额外开销最小。2.3.5对称密码的应用(续)(2)修改发现码1312.3.5对称密码的应用(续)2.3.5对称密码的应用(续)1322.3.5对称密码的应用(续)2.3.5对称密码的应用(续)1332.3.5对称密码的应用(续)Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iCR'iCLiCR'iCL'iCRiHiH'i图2.18MDC-2原理图2.3.5对称密码的应用(续)Eg(Hi-1)Eg'(H1342.3.5对称密码的应用(续)

(3)

基于CBC的消息认证码(MAC)定义26消息认证码(MAC)算法是带有密钥k的函数族hk，其具有如下性质：1)易于计算：对于任何已知函数hk，给定值k和输入x，值hk(x)容易计算出来。这个值被称做MAC-值或MAC。2)压缩：函数hk可以将任意有限比特长度的输入x影射为固定n比特长度的位串。进一步，给出函数族h的算法描述，对于任何一个固定符合要求的密钥值k(攻击者不知其值)，需要满足如下性质：3)计算抵抗：给定0个或多个消息-MAC值对(xi，hk(xi))，找到任意消息-MAC值对(x，hk(x))满足x

xi在计算上不可能(当然也包括某些i满足hk(x)=hk(xi)的可能性)。2.3.5对称密码的应用(续)(3)基于CBC的1352.3.5对称密码的应用(续)2.3.5对称密码的应用(续)1362.3.5对称密码的应用(续)M10EkH1M2EkH2…Ht-1MtEkHtEkDk'Ht可选图2.19基于CBC的MAC原理图2.3.5对称密码的应用(续)M10EkH1M2EkH21372.4公钥密码体制：RSA和ElGamal体制

2.4.1RSA体制Diffie和Hellman提出了建立公钥密码系统的可能性。但是，他们并没有提出公钥密码算法。接下来的几年，一些公钥密码算法相继被提出。其中最为成功的依赖大整数分解困难性的公钥密码算法，于1977年由Rivest，Shamir，和Adleman提出。这也就是我们熟知的RSA算法。虽然经过长期的密码分析并不能证明也不能否定RSA的安全，但是这也无疑给了算法的安全性一定承诺。2.4公钥密码体制：RSA和ElGamal体制2.1382.4.1RSA体制(续)

注意这里讲到的公钥密码算法，都是假定发送消息者已经得到接受者一份真实的公开密钥拷贝。现实中，有许多技术保障真实公开密钥分配，包括：在可信信道上交换密钥，使用可信公开文件，使用在线可信服务器或使用离线服务器和证书。2.4.1RSA体制(续)注意这里讲到的公钥密码算法1392.4.1RSA体制(续)RSA加密2.4.1RSA体制(续)RSA加密1402.4.1RSA体制(续)2.4.1RSA体制(续)141