第三章-分组密码

第三章分组密码3.1分组密码概述3.2DES3.3分组密码运行模式3.4AES一、分组密码概述分组密码概述分组密码是许多系统安全的一个重要组成部分。可用于构造伪随机数生成器流密码消息认证码(MAC)和杂凑函数消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。应用中对于分组密码的要求安全性运行速度存储量(程序的长度、数据分组长度、高速缓存大小)实现平台(硬、软件、芯片)运行模式分组密码概述明文序列x1,x2,…,xi,…加密函数E:Vn×KVm这种密码实质上是字长为n的数字序列的代换密码。解密算法加密算法密钥k=(k0,k1,…,kt-1)密钥k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xn-1)明文x=(x0,x1,…,xn-1)密文x=(y0,y1,…,ym-1)分组密码概述通常取n=m。若nm，则为有数据扩展的分组密码。若nm，则为有数据压缩的分组密码。分组密码设计问题分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。分组密码设计准则混淆：人们所设计的密码应使用使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐藏明文数字统计特性。分组密码算法应满足的要求分组长度n要足够大：防止明文穷举攻击法奏效。密钥量要足够大：尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。分组密码算法应满足的要求加密和解密运算简单：易于软件和硬件高速实现。数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。差错传播尽可能地小。分组密码的实现原则软件实现的原则：使用子块和简单的运算。如将分组n化分为子段，每段长为8、16或32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。硬件实现的原则：加密解密可用同样的器件来实现。代换网络代换是输入集A到输出A’上的双射变换：fk：AA＇k是控制输入变量，在密码学中则为密钥。实现代换fk的网络称作代换网络。双射条件保证在给定k下可从密文惟一地恢复出原明文。代换网络代换fk的集合：S={fkkK}K是密钥空间。如果网络可以实现所有可能的2n!个代换，则称其为全代换网络。代换结构代换网络密码设计中需要先定义代换集S，而后还需定义解密变换集，即逆代换网络S-1，它以密文y作为输入矢量，其输出为恢复的明文矢量x。要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密码体制的集合S中的元素个数都远小于2n!。代换盒(S盒)在密码设计中，可选n=rn0，其中r和n0都为正整数，将设计n个变量的代换网络化为设计r个较小的子代换网络，而每个子代换网络只有n0个输入变量，称每个子代换网络为代换盒(SubstitutionBox)S盒x5x4x3x2x1x0y3y2y1y0DES的S盒DES的S1-盒的输入和输出关系x5x0x5x4x3x2x1x010101100列号0123456789101112131415行号01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613(y3,y2,y1,y0)=(0,0,1,0)S盒的设计准则迄今为止，有关方面未曾完全公开有关DES的S盒的设计准则。Branstead等曾披露过下述准则：P1S盒的输出都不是其输入的线性或仿射函数。P2改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。P3当S盒的任一输入位保持不变，其它5位输入变化时(共有25=32种情况)，输出数字中的0和1的总数近于相等。这三点使DES的S盒能够实现较好的混淆。Feistel密码结构乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果.Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。Feistel网络示意图输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。第i轮迭代的输入为前一轮输出的函数：其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。111,iiiiiiLRRLFRKFeistel密码结构Feistel密码结构Feistel网络的实现与以下参数和特性有关：①分组大小:分组越大则安全性越高，但加密速度就越慢。②密钥大小：密钥越长则安全性越高，但加密速度就越慢。③轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。④子密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。⑤轮函数：轮函数的复杂性越大，密码分析的困难性也越大。在设计Feistel网络时，还有以下两个方面需要考虑：①快速的软件实现：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。②算法容易分析：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。Feistel密码结构Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，……，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。Feistel解密结构Feistel加解密过程在加密过程中：在解密过程中161516151516,LERERELEFREK10161510016161516151516151615,,,,LDRDLERERDLDFRDKREFREKLEFREKFREKLEFeistel密码结构所以解密过程第1轮的输出为LE15‖RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第i轮有因此111,iiiiiiLERERELEFREK111,,iiiiiiiiiRELELEREFREKREFLEKFeistel密码结构3.2美国数据加密标准—DES（DataEncryptionStandard）美国制定数据加密标准简况目的通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于90年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。美国制定数据加密标准简况美国NBS（NationalBureauofStandards）在1973年5月15公布了征求建议。1974年8月27日NBS再次出公告征求建议，对建议方案提出如下要求：(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的美国制定数据加密标准简况IBM公司在1971年完成的LUCIFER密码(64bit分组，代换-置换，128bit密钥)的基础上，改进成为建议的DES体制1975年3月17日NBS公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。1977年1月15日建议被批准为联邦标准[FIPSPUB46]，并设计推出DES芯片。1981年美国ANSI（AmericanNationalStandardsInstitute）将其作为标准，称之为DEA[ANSIX3.92]1983年国际标准化组织(ISO，InternationalOrganizationforStandardization)采用它作为标准，称作DEA-1美国制定数据加密标准简况NSA（NationalSecurityAgency）宣布每隔5年重新审议DES是否继续作为联邦标准，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批准DES为联邦标准。虽然DES已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。1993年4月，Clinton政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准EES(EscrowedEncryptionStandard)。算法属美国政府SECRET密级。美国制定数据加密标准简况DES发展史确定了发展公用标准算法模式，而EES(EscrowedEncryptionStandard)的制定路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。1995年5月AT&TBellLab的M.Blaze博士在PC机上用45分钟时间使SKIPJACK的LEAF协议失败，伪造ID码获得成功。1995年7月美国政府宣布放弃用EES来加密数据，只将它用于语音通信。1997年1月美国NIST着手进行AES（AdvancedEncryptionStandard）的研究，成立了标准工作室。2001年Rijndael被批准为AES标准。DES（DataEncryptionStandard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。DES是第一代公开的、完全说明细节的商业级现代算法，并被世界公认。美国制定数据加密标准简况DES算法分组长度为64bits(8bytes)密文分组长度也是64bits。密钥长度为64bits，有8bits奇偶校验，有效密钥长度为56bits。算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。DES算法框图初始置换IP将64bit明文的位置进行置换，得到一个乱序的64bit明文组，而后分成左右两段，每段为32bit，以L0和R0表示。逆初始置换IP-1。将16轮迭代后给出的64bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系。DES算法（续）1初值置换IP1.初始置换M1M2M3M4M5M6M7M8M9M10M11M12M13M14M15M16M17M18M19M20M21M22M23M24M25M26M27M28M29M30M31M32M33M34M35M36M37M38M39M40M41M42M43M44M45M46M47M48M49M50M51M52M53M54M55M56M57M58M59M60M61M62M63M64DES算法（续）其中Mi是二元数字。由下表得X=IP(M)为：M58M50M42M34M26M18M10M2M60M52M44M36M28M20M12M4M62M54M46M38M30M22M14M6M64M56M48M40M32M24M16M8M57M49M41M33M25M17M9M1M59M51M43M35M27M19M11M3M61M53M45M37M29M21M13M5M63M55M47M39