第二部分密码学.ppt

第二部分 密码学,2014-11-30,本部分要点,现代密码学框架 现代密码学的理论基础 对称密码技术 公钥密码技术,2.1 现代密码学框架,2.1.1 什么是密码学 定义1 密码学是研究与信息安全各方面有关的(比如机密性、数据完整性、实体认证及数据源认证)数学技术的一门学科。,2.1.1 什么是密码学(续),图 2.1 Shannon保密系统,2.1.1 什么是密码学(续) 通信中的参与者 (1) 发送者(Alice)： 在双方交互中合法的信息发送实体。 (2) 接收者(Bob)：在双方交互中合法的信息接收实体。 (3) 分析者(Eve)：破坏通信接收和发送双方正常安全通信的其他实体。可以采取被动攻击和主动攻击的手段。 信道 (1) 信道：从一个实体向另一个实体传递信息的通路。 (2) 安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道。 (3) 公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道。,2.1.2 对称与非对称密码思想,# 对称密码加密密钥与解密密钥同：K1=K2 代表系统：DES和AES,2.1.2 对称与非对称密码思想(续),若互联网上有n个用户，则需要,个密钥，若n=1000，则NK500 000。 # 如此众多的密钥如何建立，如何保存？,2.1.2 对称与非对称密码思想(续),# 非对称密码加密密钥与解密密钥不同：K1K2 代表系统：RSA和ElGamal,2.1.3 密码学的演进及目前的状态,# 公钥密码体制以其强大的功能使得私钥密码体制显得已经过时，但是强大的功能不是无代价获得的，公钥密码的计算量远大于相同情况下的私钥密码。因此，不适合加密大量数据，只适合于完成少量数据加密，如传送私钥密码的密钥、签名等等。,2.1.4 现代密码学主要技术,2.1.4 现代密码学主要技术(续),(1) 加密 加密基本术语 明文消息空间M: 某个字母表集 密文消息空间C: 可能的密文消息集 加/解密密钥空间K: 可能的加/解密密钥集 加/解密函数EeK (mM) / DdK (cC) : 一个 从M到C/C到M的有效变换,2.1.4 现代密码学主要技术(续),加密方案 加密方案是由一个加密函数集Ee: eK和解密函数集Dd: dK构成，并且满足任意一个加密密钥eK存在唯一一个解密密钥dK使 Dd=Ee-1，也就是对于所有明文消息mM ，存在Dd(Ee(m)=m，(e, d)称为密钥对。设计加密方案就是确定M、 C、 K、Ee: eK、Dd:dK的过程。 定义2 一个加密方案可以被破译是指，第三方在没有事先得到密钥对(e, d)的情况下，可以在适当的时间里系统地从密文恢复出相对应的明文。 # 适当的时间由被保护数据生命周期来确定。,2.1.4 现代密码学主要技术(续),私钥加密 定义3 一个由加密函数集Ee: eK和解密函数集Dd: dK组成加密方案，每一个相关联的密钥对(e, d)，如果知道了e在计算上很容易确定d，知道了d在计算上很容易确定e，那么，就是私钥加密方案。 # 私钥加密需要一条安全信道来建立密钥对。 主要技术：分组密码与流密码 定义4(分组密码) 将明文消息在编码集按照固定长度t进行分组，再一组一组地加解密明密文消息。 #著名的DES、AES都是这类密码。,2.1.4 现代密码学主要技术(续),定义5 K 是加密变换集的密钥空间，序列e1e2eiK称为密钥流。 定义6 (流密码) 消息m以串的形式(m1m2mi)给出，密钥e1e2ei是K上的密钥流。流密码通过ci=Eei(mi)给出密文消息(c1c2ci)；如果di为ei的逆，解密则通过mi=Ddi(ci)完成。,2.1.4 现代密码学主要技术(续),公钥加密 定义7 一个由加密函数集Ee: eK和解密函数集Dd: dK组成加密方案，每一个相关联的加/解密密钥对(e, d)，加密密钥e公开，称为公开密钥，而解密密钥d保密，称为秘密密钥。 # 显然安全公钥密码系统要求从e计算d为不可能。,2.1.4 现代密码学主要技术(续),公钥加密实例,# 因为存在替代攻击问题，公钥系统中公开密钥e 必须认证，一般是建立PKI。,2.1.4 现代密码学主要技术(续),(2) 数字签名技术 基本术语 明文消息空间M:某个字母表中串的集合 签名空间S:可能的签名集合 签名密钥空间K:用于生成签名的可能密钥集，具体取值k需要保密 验证密钥空间K:用于验证签名的可能密钥集，具体取值k需要公开 签名函数SK(mM):从M到S的有效变换 验证函数VK(mM, s):一个从MS到输出True, False的有效变换,2.1.4 现代密码学主要技术(续),签名过程 签名(签名者完成) 1) 对一条需要签名的消息mM计算签名s=Sk(m)。 2) 将对消息m 的签名(m, s)发送出去。 验证 (验证者完成) 1) 得到对应签名者的验证算法Vk ，计算u=Vk (m, s)。 2) 如果u=True，接受签名；如果u=False，拒绝签名。,2.1.4 现代密码学主要技术(续),签名和认证函数必须满足的性质 1) 当且仅当Vk (m, s)=True时，s是消息m的合法签名。 2) 对于任何签名者以外的实体在计算上不可能得到任意的一组mf和sf满足Vk (mf , sf)=True。 数字签名的争议解决(不可否认) 如果签名者和验证者对签名发生争议，可由验证者带着签名(m, s)提交给可信任第三方(TTP)，由TTP验证该签名，最后进行仲裁。,2.1.4 现代密码学主要技术(续),数字签名技术在公钥基础设施(PKI)中的应用 除非对密钥产生的认证性和合法性有足够的信任，否则公钥密码的优势就十分有限。公钥基础设施或简称PKI是一个框架。这个框架主要由一组策略组成。策略确切定义了关于密码系统运行和密钥产生和发布与证书的规则。 X.509是设计用来在大型计算机网络中提供目录认证服务的国际标准。由于它本身是ISO/ITU 的一个标准，很多实用产品都基于它开发出来。例如，X.509被用在Visa和Mastercard的安全电子交易标准中。,2.1.4 现代密码学主要技术(续),图 2.3 X.509的结构原理,2.1.4 现代密码学主要技术(续),2.1.4 现代密码学主要技术(续),图 2.4 证书认证过程,# 证书权威负荷小(离线、非交互、存储证书)，权限低,2.1.4 现代密码学主要技术(续),公钥证书的产生 情况1 可信方产生密钥对。可信方为实体产生公钥算法的密钥对，并将公开密钥和绑定身份的公钥证书通过公共信道发给该实体。实体在证明了自己的身份(例如，出示身份证或个人可信照片)后，将通过安全信道得到对应的秘密密钥。 情况2 实体产生自己的密钥对。实体产生自己的公钥算法的密钥对，并安全地将公开密钥传送给可信方(例如，通过可信通道或派人送达)，这里主要是保证公开密钥的真实性。在验证了公开密钥来源的真实性后，可信方为公开密钥生成证书。,2.1.4 现代密码学主要技术(续),证书链和证书路径,图 2.5 证书链,2.1.4 现代密码学主要技术(续),(3) 认证与鉴别技术 鉴别或实体认证 定义9 鉴别或实体认证是一个过程。在这个过程中一方通过获得一些确定的证据来确认参加实体认证的另一方的身份，而具有相应身份的实体也确实就是正在参与这一认证过程的另一方。 例子1 实体A与B通电话，如果A与B认识就可以通过声音来确定对方的真实性。 例子2 实体A通过信用卡在银行ATM机上取钱。 # 特点：时实性。,2.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 现代密码学主要技术(续),数据源认证 定义10 数据源认证或消息认证技术，提供一方通过一些附加的证据，确定消息的产生一方的真实身份。 例子3 实体A向实体B发送电子邮件，电子邮件通过网络传输并存储，在某个时间由B接收到，由于没有直接通信，B这时可能要求认证邮件确实来自A。,2.1.4 现代密码学主要技术(续),(4) 密码Hash函数技术 定义11 Hash函数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 现代密码学主要技术(续),消息认证码(MACs) 消息认证码的目的，通俗讲就是不附加任何其他机制，确保消息来源的真实性的Hash函数。消息认证码有两个不同功能的参数，即消息和秘密密钥。,图 2.6 密码Hash函数的简单分类,2.1.4 现代密码学主要技术(续),(5) 随机数与随机序列 密码中以伪随机序列发生器代替随机序列发生器。伪随机序列发生器以短的随机数做种子，以固定方式产生伪随机序列。 # 伪随机序列与真随机序列不可区分假设，与安全数字签名、公钥密码的存在性等价。,2.1.5 评价现代密码算法的标准,Kerckhoffs准则 在评估一个密码系统安全性时，应该总是假定我们的敌人了解实际使用的各种方法。 # 落实到现代密码算法中就是攻击者知道密码算法的所有执行细节，算法的安全不应该依赖于对算法的保密。,2.1.5 评价现代密码算法的标准(续),Shannon提出的“优质”密码算法特征 (1) 加解密的工作量由所要求的安全程度决定。 (2) 密钥集合和加密算法不应该过于复杂。 (3) 执行过程应该尽量简单。 (4) 密码中的差错不应该具有传播性。 (5) 加密后的文本大小不应该比原始报文更大。,2.1.5 评价现代密码算法的标准(续),“可信赖的”加密体制的特点 (1) 有可靠的数学基础。 (2) 经过专家的严格分析，证实是可靠的。 (3) 经得起时间的检验。,2.1.5 评价现代密码算法的标准(续),(1) 无条件安全(信息论意义下安全) a 无论攻击者具有何种计算能力，都无法破解 密码。 b Shannon证明无条件安全需要私钥加密中密 钥的长度与加密信息的长度相等。 c 私钥加密中有一次一密乱码本(one-time pad) 是无条件安全的密码。 d 公钥密码中没有。,安全评估模型,2.1.5 评价现代密码算法的标准(续),(2) 计算复杂理论下安全 限定攻击者的计算能力为多项式能力(P)，证明破译密码需要指数能力(NP)。,2.1.5 评价现代密码算法的标准(续),(3) 规约安全 规约破解密码的能力为一个数论(通常是)中的著名困难问题，如RSA问题或Diffie-Hellman问题。步骤通常如下： a 刻画安全模型。 b 在安全模型下，定义密码算法需要达到的安全目标。 c 描述密码算法。 d 规约密码算法可以达到设定的安全目标。 # 可以看作放宽条件的计算复杂理论下安全或下面所说的计算安全的特殊子类，这一方法是目前比较实用的公钥密码分析技术。,2.1.5 评价现代密码算法的标准(续),(4) 计算安全 在已知的攻击方法和攻击者的计算能力下，攻击密码成功的可能性是可以忽略的。 特点：依赖困难问题，但不存在等价证明，大多数私钥密码属于这一类安全，也称为实践安全。,2.1.5 评价现代密码算法的标准(续),(5) 启发式安全 根据列出的著名攻击方法，结合使用的困难问题对密码进行逐条启发示分析，得出安全结论。很多高层复杂的密码协议通常采用这种方法，但经过这种分析方法的协议只能得到一定程度的计算复杂安全。 缺点：攻击的具体手段和方法可能无法穷尽，而且，设计者即使知道某一个攻击方法未必就可以设计出一个真正能抵抗这一攻击的密码，因此，设计的密码常常仍然存在漏洞。,2.2 现代密码学的理论基础,现代密码学要求很高的数学基础，包括：数论、抽象代数与有限域、计算复杂理论、信息论、概率论等。 但是掌握基础的密码算法并不需要精通过多的底层数学理论。这里我们仅讲述掌握基本的密码算法所需要的计算复杂理论、数论等的基础知识。,2.2.1 计算复杂理论,如果加密算法建立在一个已知非常难解决的问题或者可能解的数目巨大的问题之上，那么攻击者要破译算法就注定要完成一个即便不是不可能，也是另人沮丧的任务。即使有计算机的支持，一个穷尽的暴力解答也是不可行的。NP完全问题就是这样一类具有计算复杂特点的问题。我们用非形式化的方式来描述NP完全问题。,2.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 计算复杂理论(续),例子5 背包问题,2.2.1 计算复杂理论(续),例子6 团 给定一个图G和一个整数n，是否存在一个包含n个顶点的子图，使得子图中的每个顶点与其他顶点之间都有一条边每个顶点都与其他所有顶点相连的图被称为团(clique)? 例如，图2.7有4顶点的团，但无5顶点的团。,图 2.7 图的团子图,2.2.1 计算复杂理论(续),NP完全问题的特征 (1) 每个问题都有解法，且总有一个相对简单的解法(尽管该解法也许十分耗时)。 (2) 如果要列举所有可能性，就需要考虑2n中情况(n与问题有关) (3) 这些问题是无关的，分别来自逻辑学、数论和图论。 (4) 如果能完全猜中，则可以在相对较少的时间内求解每一个问题。,2.2.1 计算复杂理论(续),P类和NP类 P类问题是一类问题的集合，这个集合中的问题都可以在一个与问题大小相关的多项式函数时间内完成。 NP类问题是所有这样一类问题的集合，假设能够完全猜中，这些问题可以在一个多项式函数时间内得到解决(猜测函数被称为是预言机或非确定性图灵机)。这种猜测是非确定性的。 EXP类，它由所有存在指数时间cn内的确定性解法的问题组成，其中，c是一个常数。 它们有如下关系，PNP EXP。,2.2.1 计算复杂理论(续),NP完全的含义 Cook证明了：如果可满足问题有一个确定性的、多项式时间的算法(不带猜测)，那么对NP中的每个问题都会有一个确定性、多项式时间的算法，即NP=P。Karp证明了背包问题和团问题具有和可满足问题一样的性质。这一问题的逆否命题是：如果可以证明这些问题中的某个问题没有在多项式时间内完成的确定性算法，那么它们中所有问题都不存在确定性多项式时间算法。这里对一个问题的解决是要求找到一个通用算法来解决它的每个实例。,2.2.1 计算复杂理论(续),图 2.8 复杂性的层次结构,# P=NP或PNP,2.2.1 计算复杂理论(续),已经有很多人对NP完全问题进行了长期研究，如果对确实存在多项式时间算法，那么我们有理由认为已经有人找到了解法。目前，已经有数以百计的问题被证明是NP完全问题。我们列举的这类问题越多，就越有理由确信不存在一个能解决所有问题的简单方法。,2.2.1 计算复杂理论(续),NP完全性与密码学 (1) 一个NP完全问题不能保证不存在一种比指数时间更容易的算法，它仅表示我们不大可能找到这一算法。 (2) 每个NP完全问题都有一个确定性的指数时间算法，即可以与2n成比例的时间运行完成。 (3) 硬件的不断进步，越来越大规模的问题都能计算了。 (4) 即使一个加密算法是基于难解问题的，但攻击者未必总是去解这个难解问题才能破译加密算法。,2.2.1 计算复杂理论(续),其他固有的难解问题 数论中存在大量难解问题，但大多数数论中的难解问题都是NP问题，不是NP完全问题。公钥密码体制主要依赖数论中的两个难解问题：大整数分解问题和离散对数问题。,2.2.2 数论知识,(1) 基本概念 整除性,2.2.2 数论知识(续),2.2.2 数论知识(续),素数,2.2.2 数论知识(续),200以内的素数： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.2 数论知识(续),整数唯一分解定理,2.2.2 数论知识(续),2.2.2 数论知识(续),一次不定方程,2.2.2 数论知识(续),(2) 同余 同余定义与概念,2.2.2 数论知识(续),2.2.2 数论知识(续),剩余类和完全剩余类,2.2.2 数论知识(续),缩系,2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.2 数论知识(续),一次同余式,2.2.2 数论知识(续),2.2.2 数论知识(续),(3) 原根,2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.2 数论知识(续),2.2.3 群环域的概念,(1) 群,2.2.3 群环域的概念(续),2.2.3 群环域的概念(续),(2) 环,2.2.3 群环域的概念(续),2.2.3 群环域的概念(续),(3) 域,2.3 对称密码技术,对称密钥体制的问题 (1) 在安全加密体制中，密钥是需要经常变更的，使得已丢失的密钥只能泄露数量有限的信息。 (2) 密钥的分发必须保证安全。一种方式就是对密钥分解分发，如图2.9。 (3) 密钥数目的增长与交换信息的人数的平方成正比，在人数多的时候，可以考虑使用信任中心，如图2.10 。,2.3 对称密码技术(续),图 2.9 密钥的分块分发,图 2.10 加密信息分发中心,2.3.1 DES算法描述 1974年，IBM向国家标准局(NBS)提交了一个名为 LUCIFER的加密算法。NBS将其转给了国家安全局 (NSA) 进行审定，之后就得到了一个名为数据加密标准DES的算法。1977年，NBS 正式将其用于无限制级的政府通信。其间NBS和NSA可能存在某些误会。NSA原本打算DES仅用于硬件执行，但是NBS却公布了过多的技术细节以致于人们可以根据其写出DES加密软件。如果NSA预料到后续的情况发展变化，他们或许不会同意公布DES。,2.3.1 DES算法描述(续),DES是分组密码，每个分组为64比特数据。 64比特明文通过加密最后成为64比特密文。 DES的密钥通常写为64比特，但每8比特有一位奇偶效验位，可以忽略。因此，实际只有56比特。算法只使用不超过64位的标准算术操作和逻辑操作，所以在70年代仅使用硬件就可以容易地实现算法。算法的重复特性非常适合专用芯片执行。起初采用软件执行的DES显得笨拙，但目前的软件执行效果也相当不错。 DES 的核心是一个被称为Feistel系统的部件。,2.3.1 DES算法描述(续),图 2.11 DES算法总体流程,2.3.1 DES算法描述(续),2.3.1 DES算法描述(续),初始计算,2.3.1 DES算法描述(续),函数 f(Ri-1, Ki),图 2.12 f函数计算结构,2.3.1 DES算法描述(续),2.3.1 DES算法描述(续),图 2.13 DES的S盒,2.3.1 DES算法描述(续),2.3.1 DES算法描述(续),密钥变换,2.3.1 DES算法描述(续),2.3.2 DES的安全,DES存在关于密钥长度、叠代次数、S-盒设计准则的问题。特别是S-盒以常量形式给出，但并未明确说明这些常量为何以这种形式出现。虽然IBM声称这些是经过17年大量密码分析得出的结果，但是人们还是十分担心NSA的介入可能为算法安装陷门以利于其解密。,2.3.2 DES的安全(续),(1) 弱密钥与半弱密钥,图 2.14 4个DES弱密钥即EKEK(x)=x,图 2.15 6对DES半弱密钥即EK1EK2(x)=x,2.3.2 DES的安全(续),(2) 关于S盒 NSA曾公布了一些关于S盒选择的信息： 1) 没有一个S盒的输出是输入的线性或仿射函数； 2) 改变S盒的一位输入将至少引起2个输出位的变化； 3) 固定输入的某一位为0或1后，改变它周围的位不应导致输出的0或1的个数不成比例的变化。,2.3.2 DES的安全(续),(3) 加密轮数与差分分析攻击 差分分析通过微小差异的明文对，研究这些差异对所得密文的影响。如果同时更改输入位的某些组合，输出结果中的某些位也会以很高的概率、以特定方式变化。实践表明，DES在小于16轮的情况下，差分攻击的效率将明显快于搜索全部密钥空间的强力攻击。,2.3.2 DES的安全(续),(4) 密钥长度问题 密钥长度偏小一直是DES的一个安全问题。 1) 1977年，Diffie和Hellman估计如果花费2千万美元建造一台机器，大约仅需一天就可以破译DES。 2) 1993年，Wiener利用开关技术设计了更加有效的破译DES设备。 3) 到1996年逐渐形成了3种破译DES的基本方法。一种方法是利用分布计算；一种是设计专用攻击芯片；折中的方法是使用可编程逻辑门阵列。,2.3.2 DES的安全(续),4) 分布计算方法破译DES变得十分流行，特别是在Internet兴起和壮大的情况下。1997年，RSA数据安全公司开展了破译DES密钥和其加密消息的竞赛。仅仅5个月，Rocke Verser 就在搜索了25%的密钥空间后发现密钥。接下来，RSA数据安全公司又开展了第二次竞赛。结果用时39天搜索了密钥空间的85%发现了对应密钥。 5) 1998年，电子领域基金会(EFF)展开了一项名为DES破译的计划。计划的基本思想是：一般使用的计算机对于完成破译DES的任务来说不是最优的。计划使用的结构是，硬件用来判定排除大量不可能的密钥并返回那些可能的密钥；软件则用来处理每一个可能的密钥，判定这些密钥是否确实为密码系统使用的密钥。结果是计划使用1500个芯片平均在大约在4.5天可以完成对DES 的破译。,2.3.2 DES的安全(续),6) 有传言说根据预先处理的不同，NSA可以在3到5分钟成功破译DES。而在机器方面的开销仅有5万美元。 #上述结果说明对于90年代晚期的计算技术而言，加密系统使用56比特的密钥已经显得过短，不能提供强有力的安全保护。,2.3.2 DES的安全(续),(5) 增加安全性的DES变化,2.3.2 DES的安全(续),2.3.3 AES算法描述,1997年1月2日，国家标准与技术研究所(NIST)宣布，启动设计新的对称分组加密算法，作为新一代加密标准替代DES。新的加密标准将被命名为高级加密标准(AES)。不同于暗箱设计过程的DES，AES的设计方案于1997年9月12向全世界公开征集。,2.3.3 AES算法描述(续),AES需要满足下列要求： (1) 必须详细和公开说明对称加密算法的设计原理。 (2) 算法必须支持最小128比特的消息分组，密钥长度可以为128，192，256比特，而安全强度至少与三重DES相当但效率应该高于三重DES。 (3) 算法适合于在各种硬件设备上执行。 (4) 如果算法被选种，不应该存在专利问题并可以在世界范围内使用。,2.3.3 AES算法描述(续),1998年8月20日，NIST公布了15个AES侯选算法，这些算法由遍布世界的密码团体的成员提交。公众对这15个算法的评论被当作初始评论(公众的初始评论也被称为第一轮)。第一轮于1999年4月15日截止。根据收到的分析和评论，NIST从15个算法中选出5个算法。,2.3.3 AES算法描述(续),5个参加决赛的AES侯选算法是：MARS(来自IBM，在大型机上的实现进行了优化，个人计算机上就不那么有效了)；RC6(来自RSA实验室，它是RC5的延续，设计非常简单，甚至可以靠记忆记住它)；Serpent(来自Ross Anderson， Eli Biham，和Lars Knudsen，该算法硬件实现很稳定，以4位子处理器的并行操作为基础)； Twofish(来自Bruce Schneier，John Kelsey，Doug Whiting，David Wagner，Chris Hall，和Niels Ferguson，开发者设计了一个替换表的设计方案，该方案依赖于加密密钥而不是依赖固定的替换表) ；Rijndael(来自Joan Daemen和Vincent Rijmen) 。这些参加决赛的算法在又一次更深入的评论期(第二轮)得到进一步的分析。,2.3.3 AES算法描述(续),在第二轮中，要征询对候选算法的各方面的评论和分析，这些方面包括但不限于下面的内容：密码分析、知识产权、所有AES决赛侯选算法的剖析、综合评价以及有关实现问题。在2000年5月15日第二轮公众分析结束后，NIST汇集和研究了所有得到的信息，为最终选择提供依据。2000年10月2日，NIST宣布它选中了Rijndael作为AES。NIST指出，之所以选择Rijndael的原因是因为它是安全性、性能、效率、实现方便性和灵活性的最佳组合。,2.3.3 AES算法描述(续),有限域GF(pn)的知识,2.3.3 AES算法描述(续),2.3.3 AES算法描述(续),2.3.3 AES算法描述(续),2.3.3 AES算法描述(续),算法架构 为使论述简单，我们以使用128比特密钥加密128比特消息为例说明，并且先对算法的整体架构予以说明。算法由10轮组成。每一轮使用一个由原始密钥产生的密钥。第0轮使用原始的128比特密钥。每一轮都是128比特输入128比特输出。AES的结构如图2.16。,2.3.3 AES算法描述(续),图 2.16 AES的结构,2.3.3 AES算法描述(续),每一轮由四个基本步骤称为层(layers)组成： (1)字节转换(The Byte Sub Transformation)： 这是一个非线性层主要用于防止差分和线性分析攻击。 (2) 移动行变换(The Shift Row Transformation)：这是一个线性组合，可以导致多轮之间各个比特位间的扩散。 (3) 混合列变换(The Mix Column Transformation)： 这一层的目的与移动行变换相同。 (4) 轮密钥加密变换(Add Round Key)：轮密钥与上一层的结果进行异或操作。,2.3.3 AES算法描述(续),一轮的过程,注意最后一轮忽略了混合列变换(MC)层。,2.3.3 AES算法描述(续),层,2.3.3 AES算法描述(续),(1) 字节转换,2.3.3 AES算法描述(续),2.3.3 AES算法描述(续),(2) 移动行变换,2.3.3 AES算法描述(续),(3) 混合列变换,2.3.3 AES算法描述(续),(4) 轮密钥加密变换,2.3.3 AES算法描述(续),轮密钥产生方法,2.3.3 AES算法描述(续),解密 字节转换、移动行变换、混合列变换、轮密钥加密变换都存在相应的逆变换： (1)字节转换的逆变换可以通过查另一个表来完成，我们称之为逆字节转换(IBS)。 (2) 移动行变换的逆变换可以通过字节右移来实现，我们称之为逆移动行变换(ISR) 。 (3) 逆混合列变换 (IMC) 通过乘上另一个矩阵实现。 (4) 轮密钥加密变换实际上是自身的逆。,2.3.3 AES算法描述(续),S-盒原理,2.3.3 AES算法描述(续),2.3.3 AES算法描述(续),解密变换,2.3.3 AES算法描述(续),# 为了保持结构的一致性，在最后一轮加密中忽略了 MC操作。,2.3.4 AES的安全与执行,设计思考 (1) 由于加密和解密过程不一致，相比DES(全1密钥，加密两次恢复为本身)，相信AES不存在任何弱密钥。 (2) 不同于Feistel系统，AES对输入所有比特的处理相同，这使得输入的扩展速度很快。实践表明两轮计算就能得到充分扩展，也就是说，所有的128比特输出完全依赖于所有128比特输入。 (3) AES的S-盒的建立有明晰而简单的代数意义，这样可以避免任何建立在算法上的门陷，较好避免存在于DES的S-盒上的神秘色彩。AES的S-盒具有良好的非线性特性，它可以很好地用来阻止差分和线性分析。,2.3.4 AES的安全与执行(续),(4) 移动行这一层可以很好地阻止新发现的截断攻击和平方攻击。 (5) 混合列可以达到字节扩散的目的。这步1个输入字节的改变导致所有4个输出字节改变。 (6) 轮密钥产生方法使用了密钥位的非线性组合，因为它使用了S-盒，这种非线性组合用来对付当解密者知道了部分密钥并以此推测余下部分的攻击。循环常量(10)(i-4)/4是用来消除在循环过程中生成每个循环差别的对称性。,2.3.4 AES的安全与执行(续),(7) 轮次之所以选择10，是因为在6轮情况下存在比强力搜索攻击更好的算法。到2004年，公布的密码分析结果在7轮以上还没有比强力搜索攻击更好的办法。多出4轮能够让人更有安全感。当然，轮次还可以根据需要增加。,2.3.4 AES的安全与执行(续),执行思考 我们已经看到Rijndael内部的层是非常简单的，它在很小的代数空间上即可完成。因此，可以高效完成这些层。从前面对Rijndael的内部层描述可以看到，仅有SB/ISB和MC/IMC值得考虑它们的快速实现问题。 (1) 对于SB/ISB，我们建议使用S-盒查表方法：可以一次建立一个有28=256个字节的小表，长期使用(就是说，这个表可以“固化”在硬件或者是软件中实现)。“查表法”不仅非常有效，还能阻止定时分析攻击，这种攻击根据不同数据的运算时间差异，来推断运算是在比特0还是在比特1上运行。,2.3.4 AES的安全与执行(续),(2) 在MC操作中，有限域GF(28)上的两个元的乘法操作也可以用“查表法”来实现：z = xy(有限域乘法)，这里x01，10，11和yGF(28)。我们进一步注意到字节01为有限域乘法单位元，也就是，01y=y。因而无论用软件还是硬件执行“查表法”时只需要存储2256=512项，这个表是非常小的。这样实现不仅速度很快，而且还能够减少定时分析攻击的危险。 (3) 执行IMC操作就不像执行MC操作那么快。这是因为IMC操作的44矩阵比MC操作的复杂得多，一般执行IMC操作比MC操作需要多花费30%的处理时间。然而，幸运的是在一些应用中解密是不需要的。,2.3.5 对称密码的应用,(1) 加密模式 通常大多数消息的长度大于分组密码的消息分组长度，长的消息被分成一系列连续排列的消息分组，密码一次处理一个分组。在分组密码的上层，不同的加密模式被开发出来，这些加密模式可以为整体消息加密提供一些希望得到的性质。如：分组密码的不确定性(随机性)，将明文消息添加到任意长度(使得密文长度不必与相应的明文长度相关)，错误传播控制，流密码的密钥流生成，等等。,2.3.5 对称密码的应用(续),密码分组链接(CBC)模式,图 2.17 CBC模式加密,2.3.5 对称密码的应用(续),2.3.5 对称密码的应用(续),(2) 修改发现码(MDC)实例-使用DES的MDC-2 在分组密码基础上建立Hash函数的主要动机是：如果系统已经拥有了非常有效的分组密码，那么以分组密码作为实现Hash函数的主要部件，将既可以提供Hash函数的功能，又能使额外开销最小。,2.3.5 对称密码的应用(续),2.3.5 对称密码的应用(续),2.3.5 对称密码的应用(续),图 2.18 MDC-2原理图,2.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)满足xxi在计算上不可能(当然也包括某些i满足hk(x)=hk(xi)的可能性) 。,2.3.5 对称密码的应用(续),2.3.5 对称密码的应用(续),图 2.19 基于CBC的MAC原理图,2.3.6 安全Hash算法SHA-1,安全Hash算法(SHA)是美国国家标准技术研究所(NIST)设计，并于1993年作为联邦信息处理标准(FIPS180)发布。后做修改，于1995年再次公布修订后的SHA，通常称为SHA-1。,2.3.6 安全Hash算法SHA-1(续),SHA-1算法的输入为小于264比特长的任意消息，输出为160比特的消息摘要，算法处理过程如图。,2.3.6 安全Hash算法SHA-1(续),SHA-1消息处理过程： (1) 消息填充。填充使得消息的比特长度为512比特的某个倍数减64，即使原始消息已满足要求，仍要填充。这样填充的比特数在1到512。填充方式是第一位为1其他位是0。最后64比特位用来填充消息被填充前的长度。这形成了长度为512比特的一系列分组Y0， Y1， ，YL-1。,2.3.6 安全Hash算法SHA-1(续),(2) 初始化。 SHA-1使用160比特的缓冲区存储中间和最终Hash值，可用5个32比特寄存器A，B，C，D，E表示，初始值为A=67452301，B=efcdab89，C=98badcfe，D=10325476，E=c3d2e1f0。,2.3.6 安全Hash算法SHA-1(续),(3) 处理。每个分组Yq经过压缩函数处理，压缩函数由4轮处理过程构成，如图2.22所示。每一轮又由20步迭代组成。4轮处理结构一样，但基本逻辑函数不同，分别为f1，f2，f3，f4 。每轮处理消息分组Yq和缓冲区A、B、C、D、E的当前值，输出仍放在对应缓冲区。每一轮处理有一个加法常量Ki，其中t表示迭代步数，0t79。第4轮的输出与第1轮的输入CVq依5个缓冲区对应进行模232相加得到CVq+1。消息的L个分组都按上述计算处理完成后最后一个分组的输出就是160比特消息摘要。,2.3.6 安全Hash算法SHA-1(续),2.3.6 安全Hash算法SHA-1(续),SHA-1的压缩函数 各个20步迭代运算的每一步运算可以