对称密码体制课件.ppt

关于对称密码体制现在学习的是第1页，共61页概述v对称密码体制就是在加密和解密是用到的密钥相同，或者加密密钥和解密密钥之间存在着确定的转换关系。v对称密码体制又有两种不同的实现方式，即分组密码和序列密码（或称流密码）。现在学习的是第2页，共61页流密码与分组密码v流密码每次加密数据流中的一位或一个字节。v分组密码，就是先把明文划分为许多分组，每个明文分组被当作一个整体来产生一个等长（通常）的密文分组。通常使用的是64位或128位分组大小。v分组密码的实质，是设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。现在学习的是第3页，共61页分组密码v分组密码算法实际上就是在密钥的控制下，简单而迅速地找到一个置换，用来对明文分组进行加密变换，一般情况下对密码算法的要求是：分组长度m足够大（64128比特）密钥空间足够大（密钥长度64128比特）密码变换必须足够复杂（包括子密钥产生算法）现在学习的是第4页，共61页分组密码的设计思想分组密码的设计思想v扩散(diffusion)将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中。产生扩散的最简单方法是通过“置换(Permutation)”（比如：重新排列字符）。v混淆(confusion)其目的在于使作用于明文的密钥和密文之间的关系复杂化，是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。通常的方法是“代换（Substitution)”（回忆恺撒密码）。现在学习的是第5页，共61页分组密码的设计技术分组密码的设计技术v将大的明文分组再分成几个小段，分别完成各个小段的加密置换，最后进行并行操作。v采用乘积密码技术。现在学习的是第6页，共61页DES(Data Encryption Standard)v美国国家标准局NBS于1973年5月发出通告，公开征求一种标准算法用于对计算机数据在传输和存储期间实现加密保护的密码算法。v1975 年美国国家标准局接受了美国国际商业机器公司IBM 推荐的一种密码算法并向全国公布，征求对采用该算法作为美国信息加密标准的意见。v经过两年的激烈争论，美国国家标准局于1977年7月正式采用该算法作为美国数据加密标准。1980年12月美国国家标准协会正式采用这个算法作为美国的商用加密算法。现在学习的是第7页，共61页DES的实质vDES是一种对称密码体制，它所使用的加密和解密密钥是相同的，是一种典型的按分组方式工作的密码。其基本思想是将二进制序列的明文分成每64bit一组，用长为64bit(56bit)的密钥对其进行16轮代换和置换加密，最后形成密文。现在学习的是第8页，共61页DES的基本加密流程v加密前，先将明文分成64bit的分组，然后将64bit二进制码输入到密码器中，密码器对输入的64位码首先进行初始置换，然后在64bit主密钥产生的16个子密钥控制下进行16 轮乘积变换，接着再进行末置换就得到64位已加密的密文。现在学习的是第9页，共61页DES 算法的一般描述现在学习的是第10页，共61页0.子密钥产生器子密钥产生器 密钥（64bit）除去第8，16，64位，共8个校验位置换选择1（PC-1）Ci（28bit）Di（28bit）循环左移ti+1位循环左移ti+1位置换选择2（PC-2）Ki（48bit）现在学习的是第11页，共61页置换选择1现在学习的是第12页，共61页移位次数表 第i次迭代1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16循环左移次数1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1若 C1=c1c2c28，D1=d1d2d28 则 C2=c2c3c28 c1，D2=d2d3d28 d1。现在学习的是第13页，共61页置换选择2v置换选择PC-2将C中第9 18 22 25位和 D 中第7 9 15 26位删去，并将其余数字置换位置后送出48bit数字作为第i次迭代时所用的子密钥ki Ci Di=b1b2b56，则ki=b14 b17 b11 b24b36 b29 b32 现在学习的是第14页，共61页1.初始置换v将64个明文比特的位置进行置换，得到一个乱序的64bit明文组，然后分成左右两段，每段为32bit 以L和R表示。现在学习的是第15页，共61页2.乘积变换Li-1(32比特)Ri-1(32比特)选择扩展运算E48比特寄存器子密钥Ki(48比特)48比特寄存器选择压缩运算S32比特寄存器置换运算PLi(32比特)Ri(32比特)Li=Ri-1Ri=Li-1 F(Ri-1,Ki)现在学习的是第16页，共61页选择扩展运算Ev对原第 32 1 4 5 8 9 12 13 16 17 20 21 24 25 28 29 各位重复一次得到数据扩展。1，2，3232 1 2 3 4 54 5 6 7 8 98 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 11，2，48选择扩展运算结果(48bit)E的输入(32bit)现在学习的是第17页，共61页选择压缩运算Sv将前面送来的48bit 数据自左至右分成8组，每组6bit。然后并行送入8个S盒，每个S盒为一非线性代换网络，有4个输出。现在学习的是第18页，共61页S盒的内部结构现在学习的是第19页，共61页S盒的内部计算v若输入为b1b2b3b4b5b6其中b1b6两位二进制数表达了0至3之间的数。b2b3b4b5为四位二进制数，表达0至15之间的某个数。v在S1表中的b1b6行b2b3b4b5列找到一数m（0m15），若用二进制表示为m1m2m3m4，则m1m2m3m4便是它的4bit输出。v例如，输入为001111，b1b6=01=1，b2b3b4b5=0111=7，即在S1盒中的第1行第7列求得数1，所以它的4bit输出为0001。现在学习的是第20页，共61页关于S盒vS 盒是DES的核心，也是DES算法最敏感的部分，其设计原理至今仍讳莫如深，显得非常神秘。所有的替换都是固定的，但是又没有明显的理由说明为什么要这样，有许多密码学家担心美国国家安全局设计S盒时隐藏了某些陷门，使得只有他们才可以破译算法，但研究中并没有找到弱点。现在学习的是第21页，共61页置换运算Pv对S1至S8盒输出的32bit 数据进行坐标变换 v置换P输出的32bit数据与左边32bit即Ri-1诸位模2相加所得到的32bit作为下一轮迭代用的右边的数字段，并将Ri-1并行送到左边的寄存器作为下一轮迭代用的左边的数字段。现在学习的是第22页，共61页3.逆初始置换逆初始置换IP-1 v将16轮迭代后给出的64bit组进行置换得到输出的密文组 1，2，6440 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 251，2，64密文(64bit)置换码组(64bit)现在学习的是第23页，共61页现在学习的是第24页，共61页DES的解密v解密算法与加密算法相同，只是子密钥的使用次序相反。现在学习的是第25页，共61页DES的安全性vDES在20多年的应用实践中，没有发现严重的安全缺陷，在世界范围内得到了广泛的应用，为确保信息安全做出了不可磨灭的贡献。v存在的安全弱点：密钥较短：56位密钥空间约为7.2*1016。1997年6月Rocke Verser小组通过因特网利用数万台微机历时4个月破译了DES；1998年7月，EFF用一台25万美元的机器，历时56小时破译DES。存在弱密钥：有的密钥产生的16个子密钥中有重复者。互补对称性：C=DES(M,K),则C=DES(M,K)，其中，M,C,K是M,C,K的非。现在学习的是第26页，共61页DES具有良好的雪崩效应v雪崩效应：明文或密钥的微小改变将对密文产生很大的影响。特别地，明文或密钥的某一位发生变化，会导致密文的很多位发生变化。vDES显示了很强的雪崩效应两条仅有一位不同的明文，使用相同的密钥，仅经过3轮迭代，所得两段准密文就有21位不同。一条明文，使用两个仅一位不同的密钥加密，经过数轮变换之后，有半数的位都不相同。现在学习的是第27页，共61页多重DESvDES在穷举攻击下相对比较脆弱，因此需要用某种算法来替代它，有两种解决方法：设计全新的算法；用DES进行多次加密，且使用多个密钥，即多重DES。这种方法能够保护用于DES加密的已有软件和硬件继续使用。现在学习的是第28页，共61页二重DES(Double DES)v给定明文P和两个加秘密钥k1和k2，采用DES对P进行加密E，有 密文 C=EK2(EK1(P)对C进行解密D，有 明文 P=DK1(DK2(C)EEPXCK2K1加密图DDK2K1CXP解密图现在学习的是第29页，共61页v二重DES很难抵挡住中间相遇攻击法中间相遇攻击法（Meet-in-the-Middle Attack)C=EK2(EK1(P)从图中可见 X=EK1(P)=DK2(C)EEPCXK1K2DDCPXK2K1加密解密现在学习的是第30页，共61页 若给出一个已知的明密文对（P,C)做：对256个所有密钥K1做对明文P的加密，得到一张密钥对应于密文X的一张表；类似地对256个所有可能的密钥K2做对密文C的解密，得到相应的“明文”X。做成一张X与K2的对应表。比较两个表就会得到真正使用的密钥对K1,K2。现在学习的是第31页，共61页带有双密钥的三重DES（Triple DES with Two Keys)vTuchman给出双密钥的EDE模式（加密-解密-加密）：C=EK1(DK2(EK1(P)对P加密 P=DK1(EK2(DK1(C)对C解密 这种替代DES的加密较为流行并且已被采纳用于密钥管理标准（The Key Manager Standards ANSX9.17和ISO8732).现在学习的是第32页，共61页EDEDEDCBAPPAB CK1K2K1K1K2K1加密图解密图现在学习的是第33页，共61页v到目前为止，还没有人给出攻击三重DES的有效方法。对其密钥空间中密钥进行蛮干搜索，那么由于空间太大为2112=51033，这实际上是不可行的。注意：注意：v1*.Merkle和Hellman设法创造一个条件，想把中间相遇攻击（meet-in-the-middle attack）的方法用于三重DES，但目前也不太成功。v2*.虽然对上述带双密钥的三重DES到目前为止还没有好的实际攻击办法，但人们还是放心不下，又建议使用三密钥的三重DES，此时密钥总长为168bits.C=EK3(DK2(EK1(P)现在学习的是第34页，共61页高级加密标准高级加密标准AES v1997年年1月月，美美国国国国家家标标准准局局NIST向向全全世世界界密密码码学学界界发发出出征征集集21世世纪纪高高级级加加密密标标准准（AESAdvanced Encryption Standard）算算法法的的公公告告，并并成成立立了了AES标标准准工工作作研研究究室室，1997年年4月月15日日的的例例会会制制定了对定了对AES的评估标准。的评估标准。现在学习的是第35页，共61页AES的要求（1）AES是公开的；是公开的；（2）AES为单钥体制分组密码；为单钥体制分组密码；（3）AES的密钥长度可变，可按需要增大；的密钥长度可变，可按需要增大；（4）AES适于用软件和硬件实现；适于用软件和硬件实现；（5）AES可可以以自自由由地地使使用用，或或按按符符合合美美国国国国家家标标准准（ANST）策略的条件使用；）策略的条件使用；现在学习的是第36页，共61页算法衡量条件v满足以上要求的满足以上要求的AES算法，需按下述条件判算法，需按下述条件判断优劣断优劣a.安全性安全性b.计算效率计算效率c.内存要求内存要求d.使用简便性使用简便性e.灵活性。灵活性。现在学习的是第37页，共61页AES的评审的评审v 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。v这这些些算算法法设设计计思思想想新新颖颖，技技术术水水平平先先进进，算算法法的的强强度度都都超超过过3-DES，实现速度快于，实现速度快于3-DES。现在学习的是第38页，共61页AES的评审的评审v1999年年8月月9日日NIST宣布第二轮筛选出的宣布第二轮筛选出的5个个候选算法为：候选算法为：MARS(C.Burwick等等,IBM），），RC6TM（R.Rivest等等,RSA Lab.)，RIJNDEAL(J.Daemen,比比)，SERPENT(R.Anderson等，英、以、挪威等，英、以、挪威)，TWOFISH(B.Schiener)。v2000年年10月月2日，日，NIST宣布宣布Rijndael作为新作为新的的AES现在学习的是第39页，共61页AES加密数学基础 v群:是一个代数系统，它由一个非空集合组成，在集合上定义了一个二元运算，其满足：封闭性：对任意的 ，；结合律：对任何的 ，有 ；单位元：存在一个元素 (称为单位元)，对任意元素有：；逆元：对任意 ，存在一个元素 (称为逆元)，使得 。v记作：现在学习的是第40页，共61页交换群与有限群v若群还满足交换律，即对任何 ，有：，则称为交换群(或加法群，阿贝尔群等)。v若集合G中只含有有限多个元素，则我们称 为有限群，此时，把集合G中元素的个数称为有限群的阶。现在学习的是第41页，共61页群的性质v群中的单位元是惟一的；v消去律成立，即对任意的 ：如果 ，则 如果 ，则 v群中的每一元素的逆元是惟一的。现在学习的是第42页，共61页域 v域是一个代数系统，它由一个(至少包含两个元素的)非空集合F组成，在集合F上定义有两个二元运算：加法与乘法，并满足下面条件：F的元素关于加法成交换群，记其单位元为“0”(称为域的零元)F关于乘法成交换群，记其单位元为“1”(称其为域的单位元)乘法在加法上满足分配律，即 v记为 现在学习的是第43页，共61页有限域 v若集合F只包含有限个元素，则称这个域F为有限域。有限域中元素的个数称为该有限域的阶。v若有一任意的素数P和正整数 ，存在 阶有限域，这个有限域记为 。当 n=1时，有限域 称为素域。现在学习的是第44页，共61页GF(28)域上的多项式表示及运算 v一个字节的 元素的二进制展开成的多项式系数为：v例如，上的“37”(为十六进制)，其二进制为“00110111”，对应多项式为：现在学习的是第45页，共61页GF(28)4域上的多项式表示及运算 v一个四个字节的字(有32比特位)可以看作是域 上的多项式，每个字对应于一个次数小于4的多项式。v两个 域上的元素相加时，将这两个元素对应多项式系数相加即得到结果，相加时采用比特异或来实现。v两个 域上的元素相乘时，要将结果对一个特定的多项式取模，以使相乘后的结果还是一个4字节的向量。现在学习的是第46页，共61页AES加密算法的具体实现vAES每轮要经过四次变换，分别是 字节代换运算(SubByte()ShiftRows()(行移位)变换 MixColumns()（列混合）变换 AddRoundKey()(轮密钥的混合)变换 我们用的128bit的密钥（循环次数为10），那么每次加密的分组长为128bit，16个字节，每次从明文中按顺序取出16个字节假设为a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15，这16个字节在 进行变换前先放到一个44的矩阵中。如下页图所示：现在学习的是第47页，共61页a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15这个矩阵称为状态这个矩阵称为状态（statestate）以后所有的变换都是基于这个矩阵进行的，到此，以后所有的变换都是基于这个矩阵进行的，到此，准备工作已经完成。现在按照前面的顺序进行加密变换，准备工作已经完成。现在按照前面的顺序进行加密变换，首先开始第一次循环的第一个变换：字节代换首先开始第一次循环的第一个变换：字节代换(SubByte()。现在学习的是第48页，共61页字节代换(SubByte()a0a4a8a12a1a5a9a13a2a6a10a14a3a7a11a15s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33out0out4out8out12out1out5out9out13out2out6out10out14out3out7out11out15查表现在学习的是第49页，共61页字节代换-S盒变换(查表)S S12=53,则则X=5,Y=3,outX=5,Y=3,out9 9=ed现在学习的是第50页，共61页ShiftRows()(行移位)变换s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33s00s01s02s03s11s12s13s10s22s23s20s21s33s30s31s32行变换示意图行变换示意图S SS现在学习的是第51页，共61页MixColumns()（列混合）变换S0c0cS1c1cS2c2cS3c3cS0c0cS1c1cS2c2cS3c3c0202030301010101010102020303010101010101020203030303010101010202 S0c(02 S0c)(03 S1c)S2cS3c，但这个结果可能会超出一个字节的存储范围，所以实际上还要对结果进行处理。现在学习的是第52页，共61页3.4 序列密码(流密码)v“一次一密”密码在理论上是不可攻破的。流密码则由“一次一密”密码启发而来。v流密码目前的理论已经比较成熟，工程实现也比较容易，加密效率高，在许多重要领域得到应用。v“一次一密”密码使用的密钥是和明文一样长的随机序列，密钥越长越安全，但长密钥的存储、分配都很困难。现在学习的是第53页，共61页流密码的密钥流v流密码的关键就是产生密钥流的算法，该算法必须能够产生可变长的、随机的、不可预测的密钥流。v保持通信双方的精确同步是流密码实际应用中的关键技术。由于通信双方必须能够产生相同的密钥流，所以这种密钥流不可能是真随机序列，只能是伪随机流。明文流密文流密钥流现在学习的是第54页，共61页流密码的结构v典型的流密码每次加密一位或一个字节明文。v将初始密钥(种子)输入到发生器，输出一个随机数(密钥)。伪随机字节发生器(密钥流发生器)明文字节流M密文字节流C密钥Kk异或加密伪随机字节发生器(密钥流发生器)密钥Kk异或解密明文字节流M11001100 明文01101100 密钥流10100000 密文现在学习的是第55页，共61页设计流密码需要考虑的因素v密钥流的周期要长。伪随机数发生器产生的并非完全随机的序列，它是一个产生确定的比特流的函数，该比特流最终将产生重复。重复的周期越长，相当于密钥越长，密码分析也就越困难。v密钥流应尽可能地接近于一个真正的随机数流的特征。例如1和0的个数应大致相同。密钥流越随机，加密所得的密文也越随机，分析就越困难。v伪随机数发生器的输出取决于输入的密钥的值。现在学习的是第56页，共61页RC4流密码vRC4是Ron Rivest为RSA公司在1987年设计的一种流密码。v它是一种可变密钥长度、面向字节操作的流密码。vRC4可能是应用最广泛的流密码用于SSL/TLS(安全套接字/传输层安全协议)用于IEEE802.1无线局域网中的WEP协议。现在学习的是第57页，共61页RC4算法输入：一个256个字节的表示0-255的状态矢量S、密钥K(长度为kenlen)输出：密钥字节流*初始化*For i=0 to 255 doSi=i;Ti=Ki mod keylen;/临时矢量T(256字节)*置换*j=0;For i=0 to 255 doj=(j+Si+Ti)mod 256;Swap(Si,Sj);/S仍然包含所有值为0到255的元素现在学习的是第58页，共61页*密钥流的生成*i=0,j=0;While(true)i=(i+1)mod 256;j=(j+Si)mod 256;swap(Si,Sj);t=(Si+Sj)mod 256;k=St;加密中，将k的值与下一明文字节异或；解密中，将k的值与下一密文字节异或。现在学习的是第59页，共61页其他对称密码vIDEA由旅居瑞士的华人来学嘉和他的导师J.L.Massey共同开发的。IDEA使用128位密钥，明文和密文分组长度为64位。已被用在多种商业产品中。vCLIPPER密码采用SKIPJACK算法，明文和密文分组长度为64位，密钥长度为80位。vBlowfishBlowfish允许使用最长为448位的不同长度的密钥，并针对在32位处理器上的执行进行了优化。vTwofishTwofish使用128位分组，可以使用128、192或256位密钥。vCAST-128CAST-128使用128位密钥。它在更新版本的PGP中使用。vGOSTGOST是为了回应DES而开发的俄罗斯标准，它使用256位密钥。现在学习的是第60页，共61页感感谢谢大大家家观观看看现在学习的是第61页，共61页