第4章-分组密码

第4章分组密码本节主要内容分组密码概述数据加密标准DES二重和三重DES分组密码的工作模式概述分组密码就是将明文消息序列,,,,21kmmm分成等长的消息组12122(,,,)(,,,)nnnnmmmmmm在密钥控制下，按固定的算法kE一组一组进行加密。加密后输出等长密文组12122(,,,)(,,,)mmmmyyyyyy可用如下框图来表示:其解密过程是逆过程。n称为分组长度,当nm时称为有数据压缩的分组密码；当nm时称为有数据扩展的分组密码。通常取nm。研究分组密码就是研究从明文组1(,,)nxx到密文组1(,,)myy的变换规则。由于我们只研究二元情况,1(,,)nxx，1(,,)myy都是二元组，于是研究分组密码就是研究(2)nGF到(2)mGF的映射。一般我们只考虑nm的情况。70年代,美国数据加密标准DES的出台,标志着现代分组密码学的开始。从此揭开了商用民用密码研究的序幕。这是信息化社会发展的产物越来越多的敏感信息通过网络传输和存贮，迫切需要具有高强度、高速率，便于软硬实现、易于标准化的加密体制；由于非相关团体之间频繁交换加密信息,为了实现同一水平的安全性和兼容性,数据加密标准化也势在必行。分组密码由于其固有的特点而成为标准化进程的首选体制。DES就是首先成为数据加密标准的分组密码的典型代表。作为数据加密标准,DES算法完全公开,任何个人和团体都可以使用,其信息的安全性取决于各自密钥的安全性。这正是现代分组密码的特征。定义一个(私钥)分组密码是一种映射:222ntmFFF记为(,)EXK或22(),,,ntkEXXFKF2nF称为明文空间,2mF称为密文空间,2tF为密钥空间。n为明文分组长度,当nm时,称为有数据压缩的分组密码;当nm时,称为有数据扩展的分组密码,当nm且映射一一时,)(xEk就是(2)nGF到(2)nGF的置换,研究分组密码就是研究这种置换的。分组密码的安全性现代分组密码算法完全公开，安全性仅依赖于密钥。成功的密码分析是指密码分析者可以恢复明文或密钥。安全性的相关因素：（假设）攻击者可以截获在不安全信道上传输的全部密文实际中往往攻击者可能还会获得一些其它信息安全性也与攻击者拥有的计算能力密切相关因此，在攻击者拥有的信息越多，拥有的计算能力越强的前提下，一个系统是安全的，则说这个系统具有较高的安全性。相关概念之一：攻击类型相关概念之二：绝对安全性和相对安全性一个密码系统的安全性依赖于攻击者的计算能力。如果一个密码体制对于一个拥有无限计算机资源的攻击者是安全的，则该体制就是绝对安全的。也称无条件安全性或理论上安全的（即完善保密系统）。一个体制是绝对安全的，说明破译该密码是不可能的。如果一个体制对于拥有有限计算资源的攻击者是安全的，则称该密码是计算上安全的。也称为实际上安全的，或相对安全的。计算上安全的密码说明破译该密码是困难的。破译信息所花的代价超出信息本身的价值。破译信息所需时间超出信息的有效期。事实上，经典密码中已知的无条件安全体制都是不实用的，比如一次一密体制。因此，人们通常只是追求计算上的安全性，而不是理论上的安全性。计算安全性只是一个相对概念，它依赖于攻击者的计算能力和所采用的攻击方式。一般地,计算上安全是指对该密码的最佳攻击方法的困难性超过了攻击者的计算能力。人们为了定量描述这种“困难性”，通常使用“复杂度”的概念：一种攻击的复杂度是指为了实施该攻击所需的平均运算次数。一个密码的安全性的评估，依据已知的关于该密码的最佳攻击方法的复杂度。由于假定分组密码算法是公开的，在密钥不知道的情况下，对已知密文总可采用穷搜索进行攻击。如果一个分组密码，它的所有攻击方法均不比穷搜索方法更好的话，就说它是安全的。对分组密码实施穷尽搜索的唯密文攻击，每一个可能的密钥必须试一次，其复杂度可理解为试解密钥的次数。若密钥空间为2tF，则它的试解次数平均值为12t。穷搜索是一种蛮力(或称暴力)攻击,可用于任何密码。因而，要使一个分组密码是安全的，它的密钥空间必须充分大，若用2tF表示，则t要足够大，以使对其实施穷搜索是计算上不可行的。相关概念之三：一种特定攻击的复杂度对于一种特殊攻击而言，其复杂度可分为数据复杂度和处理复杂度。数据复杂度是指实施该攻击所需的数据量；处理复杂度是指处理这些数据所需的计算量。通常以两者中主要部分来刻画该攻击的复杂度。如在对密钥的穷搜索攻击中，所需数据量(即截获的密文组或明密对)与实施该攻击所需的运算次数相比是很小的。因此,这种穷搜索攻击所需的复杂度实际是处理复杂度。又如Biham和shamir的差分密码分析是一种选择明文攻击，其复杂度主要由进行该攻击所需的明密对来决定。因此，差分密码分析的复杂度实际上是数据复杂度。对于明文空间为2nF，密钥空间为2tF的分组密码而言，穷搜索攻击的复杂度以2t为上界。而已知明文，或选择明文攻击的数据复杂度以2n为上界。如果一个密码的所有攻击方法中没有一种方法的数据复杂度远远小于2n，而处理复杂度远远小于2t,则该密码就是计算上安全的。而一种攻击能否成功则取决于其复杂度是否远远小于2n和2t。事实上，并没有一个真正实用的密码被证明是计算上安全的。一般地人们只能证明某个密码是不安全的，因为这只要找到一种方法，其复杂度远小于2n和2t。分组密码的设计原则一个好的分组密码应是既难破译又易于实现的。安全性原则分组长度n足够大。从而破解2n次加密在计算上不可能，防止明文穷搜索攻击凑效。密钥量足够大。防止对密钥的穷搜索攻击。混乱和扩散。这是shannon提出的两个一般设计原则。混乱（Confusion）的目的在于使明文和密文的统计特性之间的关系复杂化。如后面将要讨论的“非线性”因素。扩散（Diffusion）就是将每一位明文数字的影响迅速地散布到较多个输出的密文数字中，以便隐蔽明文数字的统计特性。将密钥的每位数字尽可能扩散到更多个密文数字中去，以防止对密钥进行逐段破译。易实现性：分组密码可用软件和硬件实现。用硬件实现可以获得高速率软件实现则有灵活性,代价低的优势迭代密码就是为了克服这一对矛盾而产生的一种分组密码。现代分组密码中最典型的就是迭代密码。典型迭代密码的定义设K是一个确定长度的随机二元密钥，用K来生成rN个轮密钥（也叫子密钥）1,,rNKK。轮密钥的列表1,,rNKK就是密钥编排方案。密钥编排方案由K经一个固定的、公开的算法生成。轮函数g以轮密钥rK和当前状态1rw作为它的两个输入。第r状态定义为:1,rrrwgwK初态0w被定义成明文x，密文y定义为经过所有rN轮后的状态。整个加密操作过程如下：0wx101,wgwK212,wgwK211,rrrNNNwgwK1,rrrNNNwgwKrNyw典型迭代密码的定义为了能够解密，轮函数g在其第二个自变量固定的条件下必须是单射函数，这等价于存在函数1g，对所有的w和y，有1,,ggwyyw。解密过程如下：rNwy11,rrrNNNwgwK1122,wgwK0111,wgwK0xw典型迭代密码的定义典型的分组密码分析方法对分组密码的分析方法主要有以下几种类型：穷尽密钥搜索（蛮力攻击）线性分析法差分分析法相关密钥密码分析中间相遇攻击DES是一种Feistel型密码体制在一个Feistel型密码中，每一个状态iu被分成相同长度的两半iL和iR。轮函数g具有以下形式：11,,,iiiiigLRKLR，其中，1iiLR11,iiiiRLfRK函数f并不需要满足任何单射条件，因为一个Feistel型轮函数肯定是可逆的。给定轮密钥，就有：1,iiiiLRfLK1iiRLFeistel结构FeistelCipherStructure第i轮操作+fLi-1Ri-1kiLiRiFeistel结构分析Blocksize(64→128)Keysize(56→128~256)Numberofrounds(16)SubkeygenerationRoundfunction(F)Fastsoftwareencryption/decryptionEasyhardwareimplementationSimplestructureEaseofanalysis数据加密标准（DES）1973年5月15日,美国国家标准局NBS(NationalBureauofStandards)开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性;(2)算法必须有详细的说明,并易于理解;(3)算法的安全性取决于密钥,不依赖于算法;(4)算法适用于所有用户;(5)算法适用于不同应用场合;(6)算法必须高效、经济;(7)算法必须能被证实有效;(8)算法必须是可出口的.1974年8月27日,NBS开始第二次征集加密算法.美国IBM公司提交了算法LUCIFER，该算法由IBM的工程师在1971~1972年研制.1975年3月17日,NBS公开了全部细节.1976年,NBS指派了两个小组进行评价.1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构.1977年1月15日公开发布“数据加密标准DES”(FIPSPUB46).DES的应用1979年，美国银行协会批准使用1980年，美国国家标准协会ANSI（AmericanNationalStandardsInstitute)赞同DES作为私人使用的标准,称之为DEA（ANSIX.392）1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1该标准规定每五年审查一次，计划十年后采用新标准最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。在当时，DES的替代物，高级加密标准，已经开始发展了（1997年4月开始征集AES，02年正式使用）DES结构图DES结构DES是一个16轮的Feistel型密码，它的分组长度为64，用一个56比特的密钥来加密一个64比特的明文串，并获得一个64比特的密文串。在进行16轮加密之前，先对明文做一个固定的初始置换IP，写作00IPxLR。在16轮加密之后，对比特串1616RL做逆置换-1IP来给出密文y，即-11616=IPyRL，注意在使用-1IP之前，要交换16L和16R。IP和-1IP的使用并没任何密码学意义，所以在讨论DES的安全性时常常忽略它们。DES的一轮加密与下页图（Feistel轮操作）相同。DES结构DES第i轮的操作+fkiLiRiLi-1Ri-1每一个iL和iR都是32比特长，函数324832:0,10,10,1f的输入是一个32比特的串(当前状态的右半部)和轮密钥。密钥编排方案1216,,,KKK由16个48比特的轮密钥组成，这些轮密钥由56比特的种子密钥K导出。每一个iK都是由K置换选择而来。函数f主要包含一个应用S-盒的代换以及其后跟随的一个固定置换P。设f的第一个自变量是A，第二个自变量是J，计算,fAJ的过程如下：DES算法AE(A)JB1B2B3B4B5B6B7B8C1C2C3C4C5C6C7C8f(A,J)DES算法的fExpansion:32→48S-box:6→4Permutation:1.根据一个固定的扩展函数E，将A扩展成一个长度为48比特的串。EA包含经过适当置换后的A的32比特，其中有16比特出现两次。2.计算EAJ，并且将结果写作8个6比特串的并联12345678BBBBBBBBB。3.用8个S-盒18,,SS，其中64:0,10,1iS把6比特映射到4比特，一般用一个416的矩阵iS来描述。给定一个长度为6的比特串123456jBbbbbbb，可如下计算