第7讲 分组加密算法

第7讲分组密码它将明文划分成固定的n比特的数据组，然后以组为单位，在密钥的控制下进行一系列的线性或非线性的变化而得到密文。这就是分组密码。分组密码一次变换一组数据。分组密码算法的一个重要特点就是：当给定一个密钥后，若明文分组相同，那么所变换出密文分组也相同。分组密码的一个重要优点是不需要同步分组密码体制输入输出加密算法密钥明文输入输出解密算法密钥明文nbitnbitnbitnbit密文密文分组密码的一般设计原理分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。加密算法解密算法明文密文原来的明文（x0，…,xn-1）（k0，…,kn-1）密钥k=（k0，…,kn-1）密钥k=（x0，…,xn-1）（y0，…,yn-1）分组密码的一般设计原理设计目标在密钥控制下，从一个足够大、足够好的置换子集中简单迅速地选出一个置换，对当前输入的明文数字组进行加密变换；要求：1分组长度足够大，防止穷举攻击；2密钥空间足够大，但不能太长，以便于密钥的管理；3算法要足够复杂，充分实现明文和密钥的扩散；没有简单的关系可寻DES对称加密技术DES(DataEncryptionStandard)算法是一种用56位密钥来加密64位数据的方法。发明人：IBM公司W.Tuchman和C.Meyer.基础：1967年美国HorstFeistel提出的理论；产生：美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告，最终选定DES。DES采用分组密码体制；用56bit密钥来加密64bit数据的方法；DES要达到的目标有：提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；具有复杂性，使得破译的开销超过可能获得的利益；DES的安全性不依赖于算法的保密，安全性仅以加密密钥的保密为基础；在实现上可行、经济；DES算法的原理DES算法的入口参数有三个：Key、Data、Mode。其中：Key为8个字节共64位，是DES算法的工作密钥；Data也为8个字节64位，是要被加密或被解密的数据；Mode为DES的工作方式有两种：加密或解密。DES算法原理DES算法的工作原理：如Mode为加密，则用Key去把数据Data进行加密，生成Data的密码形式（64位）作为DES的输出结果；如Mode为解密，则用Key去把密码形式的数据Data解密，还原为Data的明码形式（64位）作为DES的输出结果。DES算法的实现步骤第一步：变换明文。对给定的64位比特的明文x，首先通过一个置换IP表来重新排列x，从而构造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。第二步：按照规则迭代。规则为Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)（i=1,2,3…16）经过第一步变换已经得到L0和R0的值，其中符号⊕表示的数学运算是异或，f表示一种置换，由S盒置换构成，Ki是一些由密钥编排函数产生的比特块。f和Ki将在后面介绍。第三步：对L16R16进行交换得到R16L16对R16L16利用IP-1作逆置换，就得到了密文y。DES加密过程输入64位比特明文在密钥控制下16轮迭代初始置换IP置换表交换左右32bitIP逆置换表输出64位比特密文DES算法的实现步骤可以看出，DES加密需要四个关键点：(1)IP置换表和IP-1逆置换表;(2)函数f;(3)子密钥Ki。(4)S盒的工作原理。（1）IP置换表和IP-1逆置换表5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输入的第58位作为第1位输入的第50位作为第1位输入的第42位作为第1位输入的第40位作为第1位输入的第8位作为第1位输入的第42位作为第1位IP与IP-1互逆M=(m1,m2,…..)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455561234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556IP(M)=(m58,m50)=(m11,m12,…..)5850423426181026052443628201246254463830221466456484032241685749413325179161584537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602834242105018582633141949175725IPIP-1DES的一轮迭代Li-1（32bit）Ri-1（32bit）选择扩展运算E盒48bit寄存器48bit寄存器选择压缩运算S盒32bit寄存器置换运算PRi=Li-1⊕f(Ri-1,ki)（32bit）（32bit）⊕⊕Li=Ri-1轮开始：64bit分成左右两半子密钥Ki（48bit）扩展置换E盒(ExpandBox)将输入的32bit块扩展到48bit的输出块；48bit的输出块再分成8个6bit块；0102030405060708091011121314151617181920212223242526272829303132010203040506070809101112131415161718192021222324252627282930313232040812162024280509131721252901扩展置换函数E扩展位扩展位固定位压缩替代S盒(SubstitutionBox)48bit块通过S盒压缩成32bit块48bit寄存器32bit寄存器S1S2S3S4S5S6S7S86bit4bit共8个S盒S盒S1盒1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S2盒1518146113497213120510313471528141201106911501471110413158126932151381013154211671205149作用：将6个输入位映射为4个输出位；方法：若定义a1a2a3a4a5a6，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。输入为101011的输出是？？？S盒S3盒1009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S4盒7131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S5盒2124171011685315130149141121247131501510398642111101378159125630141181271142136150910453S盒S6盒1211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S7盒4112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S8盒1328461511110931450127115138103741256110149271141912142061013153582114741081315129035611S盒DES中其它算法都是线性的，而S盒运算则是非线性的，S盒不易于分析，它提供了更好的安全性；所以S盒是算法的关键所在；提供了密码算法所必需的混乱作用；改变S盒的一个输入位至少要引起两位的输出改变；置换函数P（Permutaion）P置换的目的是：提供雪崩效应；明文或密钥的一点小的变动都引起密文的较大变化；1607202129122817011523260518311002082414322703091913300622110425DES中子密钥的生成64bit密钥置换选择1C0（28bit）D0（28bit）循环左移循环左移C（28bit）C（28bit）循环左移循环左移置换选择2置换选择2循环左移1234567811222222091011121314151612222221密钥表的计算逻辑：Ci（28bit）Di（28bit）(56bit)(56bit)KiK1(48bit)(48bit)(56bit)置换选择-1置换选择-2574941332517915850423426181025951432527191136052443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374755304051453348444939563453464250362932置换选择1置换选择2多重DES—双重DES加密加密K1K2PC加密加密K2K1CP双重DES加密逻辑双重DES解密逻辑多重DES—三重DES加密解密K1PC三重DES加密逻辑三重DES解密逻辑K2解密K1BA解密加密K1CPK2解密K1BADES算法的安全性DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。而56位长的密钥的穷举空间为256，如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近228.5年的时间。f函数（S盒）的设计原理未知；DES算法的程序实现根据DES算法的原理，可以方便的利用C语言实现其加密和解密算法。在VC++6.0中新建基于控制台的Win32应用程序，算法如程序DES1.cpp所示。数据加密标准DES数据加密标准DES属于常规密钥密码体制，是一种分组密码。在加密前，先对整个明文进行分组。每一个组长为64bit。然后对每一个64bit二进制数据进行加密处理，产生一组64bit密文数据。最后将各组密文串接起来，即得出整个的密文。使用的密钥为64bit（实际密钥长度为56bit，有8bit用于奇偶校验)。DES加密标准L0R0L1=R0IPL2=R1L15=R14R1=L0f(R0,K1)R2=L1f(R1,K2)R15=L14f(R14,K15)L16=R15R16=L15f(R15,K16)IP1fff输出密文Y(64bit)明文X(64bit)输入K16(48bit)K2(48bit)K1(48b