第8章对称密码体制课件

第第8章章 对称密码对称密码体制体制1 第八章第八章 对称密码体制对称密码体制8.1 8.1 对称密码概述对称密码概述8.2 DES8.2 DES8.3 AES8.3 AES2一、对称密码体制概述一、对称密码体制概述第第8章章 对称密码对称密码体制体制3对称密码体制简介对称密码体制简介n对于一个密码体制（M，C，K，E，D）中的K，若加密密钥Ke与解密密钥Kd相同或者二者之间很容易互相推出，由于加密密钥和解密密钥地位是对等的，因此称其为对称密码体制。n而在实际应用中，往往加密密钥和解密密钥都是相同的，即只有一个密钥，既作为加密密钥又作为解密密钥，因此又称为单钥体制。而且一般加密算法和解密算法也是一样的。第第8章章 对称密码对称密码体制体制4对称密码体制简介对称密码体制简介n对称密码体制是历史最为悠久的密码体制，古代和近代使用的都是这种体制。n根据对明文的加密方式不同，对称密码算法又分为分组加密算法（Block Cipher）和流密码算法。n分组加密算法将明文分为一组一组的固定长度进行加密。n流密码算法则将明文按字符逐位加密。n二者之间也不是有着不可逾越的鸿沟，很多时候，分组加密算法也可以用于构建流密码算法。第第8章章 对称密码对称密码体制体制5分组密码概述分组密码概述 明文序列明文序列 x1,x2,xi,将明文划分为m比特长的组 加密函数加密函数E:VmKVn各组分别在密钥K的控制下变换成等长的输出 这种密码实质上是字长为这种密码实质上是字长为m的数字序列的代换密码的数字序列的代换密码。解密算法加密算法密钥k=(k0,k1,kt-1)密钥k=(k0,k1,kt-1)明文明文x=(x0,x1,xm-1)明文明文x=(x0,x1,xm-1)密文密文x=(y0,y1,yn-1)第第8章章 对称密码对称密码体制体制6分组密码设计问题分组密码设计问题 分分组组密密码码的的设设计计问问题题在在于于找找到到一一种种算算法法，能能在在密密钥钥控控制制下下从从一一个个足足够够大大且且足足够够好好的的置置换换子子集集中中，简简单单而而迅迅速速地地选选出出一一个个置置换换，用用来对当前输入的明文的数字组进行加密变换。来对当前输入的明文的数字组进行加密变换。第第8章章 对称密码对称密码体制体制7分组密码设计准则n混混淆淆：尽可能使密文和加密密钥间的统计关系更加复杂，以阻止攻击者发现密钥。n扩扩散散：明文的统计特征消散在密文中，可以让每个明文数字尽可能地影响多个密文数字，等价于说每个密文数字被许多明文数字影响。第第8章章 对称密码对称密码体制体制8分组密码算法应满足的要求分组密码算法应满足的要求n分组长度分组长度n要足够大：要足够大：防止明文穷举攻击法奏效。防止明文穷举攻击法奏效。n密钥量要足够大：密钥量要足够大：尽尽可可能能消消除除弱弱密密钥钥并并使使所所有有密密钥钥同同等等地地位位，以以防防止止密密钥穷举攻击奏效钥穷举攻击奏效。n由密钥确定置换的算法要足够复杂：由密钥确定置换的算法要足够复杂：充充分分实实现现明明文文与与密密钥钥的的扩扩散散和和混混淆淆，没没有有简简单单的的关关系系可循可循，要能抗击各种已知的攻击。要能抗击各种已知的攻击。n加密和解密运算简单加密和解密运算简单：易于软件和硬件高速实现易于软件和硬件高速实现。98.2 美国数据加密标准美国数据加密标准DES（Data Encryption Standard）第第8章章 对称密码对称密码体制体制10美国制定数据加密标准简况美国制定数据加密标准简况n目的目的 通信与计算机相结合是人类步入信息社会的一个阶梯，通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于它始于六十年代末，完成于90年代初。计算机通信网的形年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。成与发展，要求信息作业标准化，安全保密亦不例外。只只有标准化，才能真正实现网的安全有标准化，才能真正实现网的安全，才能推广使用加密手，才能推广使用加密手段，以便于训练、生产和降低成本。段，以便于训练、生产和降低成本。第第8章章 对称密码对称密码体制体制11美国制定数据加密标准简况美国制定数据加密标准简况n美国美国NBS在在1973年年5月月15公布了征求建议。公布了征求建议。1974年年8月月27日日NBS再次出公告征求建议，对建议方案提出如下再次出公告征求建议，对建议方案提出如下要求：要求：(1)算法必须提供高度的安全性算法必须提供高度的安全性(2)算法必须有详细的说明算法必须有详细的说明,并易于理解并易于理解(3)算法的安全性取决于密钥算法的安全性取决于密钥,不依赖于算法不依赖于算法(4)算法适用于所有用户算法适用于所有用户(5)算法适用于不同应用场合算法适用于不同应用场合(6)算法必须高效、经济算法必须高效、经济(7)算法必须能被证实有效算法必须能被证实有效(8)算法必须是可出口的算法必须是可出口的第第8章章 对称密码对称密码体制体制12美国制定数据加密标准简况美国制定数据加密标准简况nIBM公公司司在在1971年年完完成成的的LUCIFER密密码码(64 bit分分组组，代代换换-置置换换，128 bit密密钥钥)的的基基础础上上，改改进进成成为为建建议议的的DES体制体制n1975年年3月月17日日NBS（美美国国国国家家标标准准局局）公公布布了了这这个个算算法法，并并说说明明要要以以它它作作为为联联邦邦信信息息处处理理标标准准，征征求求各各方方意意见。见。n1977年年1月月15日日建建议议被被批批准准为为联联邦邦标标准准FIPS PUB 46，并设计推出并设计推出DES芯片。芯片。n1981年年美美国国ANSI（美美国国国国家家标标准准协协会会）将将其其作作为为标标准准，称之为称之为DEAANSI X3.92n1983年年国国际际标标准准化化组组织织(ISO)采采用用它它作作为为标标准准，称称作作DEA-1 第第8章章 对称密码对称密码体制体制13美国制定数据加密标准简况美国制定数据加密标准简况nNSA（美美国国国国家家安安全全局局）宣宣布布每每隔隔5年年重重新新审审议议DES是是否否继继续续作作为为联联邦邦标标准准，1988年年（FIPS46-1）、1993年年（FIPS46-2），），1998年不再重新批准年不再重新批准DES为联邦标准。为联邦标准。n虽虽然然DES已已有有替替代代的的数数据据加加密密标标准准算算法法，但但它它仍仍是是迄迄今今为为止止得得到到最最广广泛泛应应用用的的一一种种算算法法，也也是是一一种种最最有有代代表表性性的的分分组组加加密体制。密体制。n1993年年4月月，Clinton政政府府公公布布了了一一项项建建议议的的加加密密技技术术标标准准，称称作作密密钥钥托托管管加加密密技技术术标标准准EES(Escrowed Encryption Standard)。算法属美国政府。算法属美国政府SECRET密级。密级。第第8章章 对称密码对称密码体制体制14美国制定数据加密标准简况美国制定数据加密标准简况nDES发发展展史史确确定定了了发发展展公公用用标标准准算算法法模模式式，而而EES的的制制定定路路线线与与DES的的背背道道而而驰驰。人人们们怀怀疑疑有有陷陷门门和和政政府府部部门门肆肆意意侵犯公民权利。此举遭到广为反对。侵犯公民权利。此举遭到广为反对。n1995年年5月月AT&T Bell Lab的的M.Blaze博博士士在在PC机机上上用用45分分钟钟时时间间使使SKIPJACK的的 LEAF协协议议失失败败，伪伪造造ID码码获获得得成成功功。1995年年7月月美美国国政政府府宣宣布布放放弃弃用用DES来来加加密密数数据据，只只将将它用于语音通信。它用于语音通信。n1997年年1月月美美国国NIST着着手手进进行行AES（Advanced Encryption Standard）的的研研究究，成成立立了了标标准准工工作作室室。2001年年Rijndael被被批准为批准为AES标准。标准。第第8章章 对称密码对称密码体制体制15nDES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。nDES是第一代公开的、完全说明细节的商业级现代算法，并被世界公认。美国制定数据加密标准简况美国制定数据加密标准简况第第8章章 对称密码对称密码体制体制16DES 算法算法n分组长度为分组长度为64 bits(8 bytes)n密文分组长度也是密文分组长度也是64 bits。n密密钥钥长长度度为为64 bits，有有8 bits奇奇偶偶校校验验，有有效效密密钥钥长长度为度为56 bits。n算算法法主主要要包包括括：初初始始置置换换IP、16轮轮迭迭代代的的乘乘积积变变换换、逆初始置换逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。第第8章章 对称密码对称密码体制体制17DES算法框图算法框图 输入 64 bit明文数据 初始置换IP 乘积变换 （16轮迭代）逆初始置换IP-1 64 bit密文数据 输出 标准数据加密算法第第8章章 对称密码对称密码体制体制18 Li-1(32bit)Ri-1(32bit)选择扩展运算 E 48 bit寄存器 按bit模2加密 48 bit寄存器 选择压缩运算 S 32 bit寄存器 置换运算 P 按bit模2和 Li(32bit)Ri(32bit)DES算法一轮迭代过程算法一轮迭代过程密钥产生器第第8章章 对称密码对称密码体制体制19Feistel网络示意图网络示意图第第8章章 对称密码对称密码体制体制20 FeistelFeistel加解密过程加解密过程第第8章章 对称密码对称密码体制体制21Feistel密码结构密码结构Feistel还还提提出出了了实实现现代代换换和和置置换换的的方方法法。代代换换作作用用在在数数据据的的左左半半部部分分。它它通通过过用用轮轮函函数数F F作作用用数数据据的的右右半半部部分分后后，与与左左半半部部分分进进行行异异或或来来完完成成。每每轮轮迭迭代代的的轮轮函函数数是是相相同同的的，但但是是输输入入的的子子密密钥钥KiKi不不同同。代代换换之之后后，交交换换数数据据的的左左右右两两部部分分完完成成置置换换。这这种种结结构构是是Shannon提提出出的的代代换换置置换换网网络络（SPNSPN，substitution-permutation networkssubstitution-permutation networks）的一种特别形式）的一种特别形式。第第8章章 对称密码对称密码体制体制22SPNnS-P networks are based on the two primitive cryptographic operations we have seen before:nsubstitution(S-box)npermutation(P-box)常见结构及代表算法nSPN网络（例如 AES、Serpent）nFeistel结构（例如DES、CAST、Skipjack）n其他结构（例如Frog和HPC）第第8章章 对称密码对称密码体制体制23DES的的安全性安全性S S盒设计盒设计。DES靠靠S盒实现非线性变换。盒实现非线性变换。密钥搜索机密钥搜索机。对对DES安安全全性性批批评评意意见见中中，较较为为一一致致的的看看法法是是DES的的密密钥钥短短了了些些。IBM最最初初向向NBS提提交交的的建建议议方方案案采采用用112 bits密密钥钥，但但公公布布的的DES标标准准采采用用64 bits密密钥钥。有有人人认认为为NSA故故意意限限制制DES的的密密钥钥长长度度。采采用用穷穷搜搜索索对对已已经经对对DES构成了威胁构成了威胁第第8章章 对称密码对称密码体制体制24DES算法的安全性 nDES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。第第8章章 对称密码对称密码体制体制25n1993年R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。可见这种机制是不安全的。第第8章章 对称密码对称密码体制体制26nDES的56位短密钥面临的另外一个严峻而现实的问题是：国际互联网Internet的超级计算能力。1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。第第8章章 对称密码对称密码体制体制27n一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成千上万的志愿者加入到计划中，在计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员Michael Sanders成功地找到了密钥，在计算机上显示了明文：“The unknown message is:Strong cryptography makes the world a safer place”。第第8章章 对称密码对称密码体制体制28n1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。n1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。n尽管DES有这样那样的不足，但是作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。298.3 高级加密标准高级加密标准 AES第第8章章 对称密码对称密码体制体制30 AES提出提出n1997年年1月月，美美国国NIST向向全全世世界界密密码码学学界界发发出出征征集集21世世纪纪高高级级加加密密标标准准（AESAdvanced Encryption Standard）算算法法的的公公告告，并并成成立立了了AES标标准准工工作作研研究究室室，1997年年4月月15日日的的例例会会制制定定了了对对AES的的评评估估标准。标准。第第8章章 对称密码对称密码体制体制31AES的要求（1）AES是公开的；是公开的；（2）AES为单钥体制分组密码；为单钥体制分组密码；（3）AES的密钥长度可变，可按需要增大；的密钥长度可变，可按需要增大；（4）AES适于用软件和硬件实现；适于用软件和硬件实现；（5）AES可可以以自自由由地地使使用用，或或按按符符合合美美国国国国家家标准（标准（ANST）策略的条件使用；）策略的条件使用；第第8章章 对称密码对称密码体制体制32算法衡量条件n满足以上要求的满足以上要求的AES算法，需按下述条算法，需按下述条件判断优劣件判断优劣na.安全性安全性nb.计算计算效率效率nc.内内存要求存要求nd.使用使用简便性简便性ne.灵活性。灵活性。第第8章章 对称密码对称密码体制体制33AES的评审的评审n 1998年年4月月15日日全全面面征征集集AES算算法法的的工工作作结结束束。1998年年8月月20日日举举行行了了首首届届AES讨讨论论会会，对对涉涉及及14个个国国家家的的密密码码学学家家所所提提出出的的候候选选AES算算法法进进行行了了评评估估和和测测试试，初初选选并并公公布布了了15个被选方案，供大家公开讨论。个被选方案，供大家公开讨论。CAST-256，RC-6，CRYPTON-128，DEAL-128，FROG，DFC，LOKI-97，MAGENTA，MARS，HPC,RIJNDAEL，SAFER+，SERPENT，E-2，TWOFISH。n这这些些算算法法设设计计思思想想新新颖颖，技技术术水水平平先先进进，算算法法的的强强度度都都超过超过3-DES，实现速度快于，实现速度快于3-DES。第第8章章 对称密码对称密码体制体制34AES的评审的评审n1999年年8月月9日日NIST宣布第二轮筛选出的宣布第二轮筛选出的5个个候选算法为：候选算法为：MARS(C.Burwick等等,IBM），RC6TM（R.Rivest等等,RSA Lab.)，RIJNDEAL(J.Daemen,比比)，SERPENT(R.Anderson等，等，英、以、挪威英、以、挪威)，TWOFISH(B.Schiener)。n2000年年10月月2日，日，NIST宣布宣布Rijndael作为新的作为新的AES第第8章章 对称密码对称密码体制体制35AES算法设计思想n抵抗所有已知的攻击；n在多个平台上速度快，编码紧凑；n设计简单。nRijndael没有采用Feistel结构，轮函数由3个不同的可逆均匀变换构成的，称为3个层n均匀变换是指state的每个bit都用类似的方法处理第第8章章 对称密码对称密码体制体制36算法说明算法说明n分组和密钥长度可变，各自可独立指定为分组和密钥长度可变，各自可独立指定为128、192、256比特。比特。nstaten算法中间的结果也需要分组，称之为算法中间的结果也需要分组，称之为state，state可以用以字节为元素的矩阵阵列表示，该阵列有可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数行，列数Nb为分组长度除为分组长度除32n种子密钥种子密钥n以字节为元素的矩阵阵列描述，阵列为以字节为元素的矩阵阵列描述，阵列为4行，列数行，列数Nk为密钥长度除为密钥长度除32第第8章章 对称密码对称密码体制体制37主要指标主要指标n速度 3DES,安全=3DES n块长 128 BitnKey 长 128，192，256 Bit 第第8章章 对称密码对称密码体制体制38第第8章章 对称密码对称密码体制体制39第第8章章 对称密码对称密码体制体制40第第8章章 对称密码对称密码体制体制41每轮由四个不同阶段组成每轮由四个不同阶段组成n字节代换字节代换n行移位行移位n列混合列混合n轮密钥加轮密钥加第第8章章 对称密码对称密码体制体制42字节代换字节代换n正向和逆向变换正向和逆向变换n简单的查表操作：定义了一个简单的查表操作：定义了一个S S盒，由盒，由16*1616*16字节组成的矩阵，包含了字节组成的矩阵，包含了8 8位所能表示的位所能表示的256256个数的一个置换。个数的一个置换。nStateState中每个字节按照如下方式映射为一个新中每个字节按照如下方式映射为一个新的字节：把该字节高四位作为行值，低四位的字节：把该字节高四位作为行值，低四位作为列值，从作为列值，从S S盒相应位置取出元素作为输出。盒相应位置取出元素作为输出。43图5.5 字节代换示意图第第8章章 对称密码对称密码体制体制44字节代换的一个例子第第8章章 对称密码对称密码体制体制45S盒的构造方法盒的构造方法(1)(1)按字节的升序逐行初始化按字节的升序逐行初始化S S盒，第一行盒，第一行0000，01010F0F，第二行，第二行1010，11111F1F，所以行，所以行y y列列x x的字节值为的字节值为yxyx(2)(2)将每个字节映射为它在将每个字节映射为它在GF(2GF(28 8)中的逆，中的逆，0000被映被映射为射为0000(3)(3)将每个字节做如下的将每个字节做如下的GF(2)GF(2)上变换上变换第第8章章 对称密码对称密码体制体制46字节代换字节代换第第8章章 对称密码对称密码体制体制47AES的的S盒盒y0123456789abcdefx0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c31896059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973960814fdc222a908846eeb814de5e0bdbae0323a0a4906245cc2d3ac629195e479be7c8376d8dd54ea96c56f4ea657aae08cba78252e1ca6b4c6e8dd741f4bbd8b8ad703eB5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fB054bb16第第8章章 对称密码对称密码体制体制48逆字节代换逆字节代换InvSubBytes()n逆字节替代变换是字节第替代变换的逆变换，在state的每个字节上应用逆S盒。这是通过应用字节替代变换中的仿射变换的逆变换，再对所得结果应用有限域的乘法逆运算得到的。第第8章章 对称密码对称密码体制体制49AES的逆的逆S盒盒y0123456789abcdefx052096ad53036a538bf40a39e81f3d7fb17ce339829b2fff87348e4344c4dee9cb2547b9432a6c2233dee4c950b42fac34e3082eA16628d924b2765ba2496d8bd125472f8f66486689816d4a45ccc5d65B69256c704850fdedb9da5e154657a78d9d84690d8ab008cbcd30af7e45805b8b345067d02c1e8fca3f0f02c1afbd0301138a6b83a9111414f67dcea97f2cfcef0b4e673996ac7422e7ad3585e2f937e81c75df6ea47f11a711d29c5896fb7620eaa18be1bbfc563e4bc6d279209adbc0fe78cd5af4c1fdda8338807c731b11210592780ec5fd60517fa919b54a0d2de57a9f93c99cefea0e03b4dae2af5b0c8ebbb3c83539961f172b047eba77d626e169146355210c7d第第8章章 对称密码对称密码体制体制50行移位行移位n将state阵列的各行进行循环移位，不同行的移位量不同n0行：不动n1行：循环左移C1字节n2行：循环左移C2字节n3行：循环左移C3字节n记为：ShiftRow(State)51图3.20 行移位示意图第第8章章 对称密码对称密码体制体制52逆行移位逆行移位InvShiftRows()n逆行移位变换是行移位变换的逆变换，它对state的每一行进行循环右移，其中第一行保持不变，第二行循环右移1个字节，第三行循环右移2个字节，第四行循环右移3个字节。第第8章章 对称密码对称密码体制体制53列混合列混合n乘积矩阵中的每个元素均是一行和一列中对应元素的乘积乘积矩阵中的每个元素均是一行和一列中对应元素的乘积之和。这里的乘法和加法都是定义在之和。这里的乘法和加法都是定义在GF（28）上的。）上的。n表示为表示为MixColumn(State)第第8章章 对称密码对称密码体制体制54列混合举例第第8章章 对称密码对称密码体制体制55逆列混合逆列混合InvMixColumns()n逆列混合逆列混合可以写成矩阵乘法形式 第第8章章 对称密码对称密码体制体制56证明证明 0E 0B 0D 09 09 0E 0B 0D 0D 09 0E 0B 0B 0D 09 0E 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1第第8章章 对称密码对称密码体制体制57轮密钥加轮密钥加n轮密钥与轮密钥与state进行逐比特异或。进行逐比特异或。n轮密钥由种子密钥通过密钥编排算法得轮密钥由种子密钥通过密钥编排算法得到到n轮密钥长度与分组密钥长度相同轮密钥长度与分组密钥长度相同n表示为表示为AddRoundKey(State,RoundKey)第第8章章 对称密码对称密码体制体制58轮密钥加轮密钥加第第8章章 对称密码对称密码体制体制59AES的密钥扩展的密钥扩展n输入值为4个字（16字节），输出值是一个由44个字组成的一维线性数组第第8章章 对称密码对称密码体制体制60第第8章章 对称密码对称密码体制体制61单钥密码体制概述第第8章章 对称密码对称密码体制体制62总结nDES算算法法描描述述分分组组长长度度为为64bits,密密钥钥长长度度为为64 bits，有有8 bits奇奇偶偶校校验验，有有效效密密钥钥长长度为度为56 bits。Feistel结构。结构。nAES算法描述分组和密钥长度可变，各自算法描述分组和密钥长度可变，各自可独立指定为可独立指定为128、192、256bits。SPN网络。每轮的步骤：字节代换、行移网络。每轮的步骤：字节代换、行移位、列混合、轮密钥加。位、列混合、轮密钥加。n扩散和混淆的概念扩散和混淆的概念