第2章 分组密码

主讲人：侯红霞通信与信息工程学院第2章分组密码2.1分组密码的设计准则•分组密码也叫做块密码（BlockCipher），是指对固定长度的一组明文进行加密的一种加密算法，这一固定长度称之为分组长度。•在分组密码中，必须处理一个问题——填充。–在分组加密中，要求填充是可逆的•假定块长度为8字节，要加密的明文数据长度为9字节。那么消息被切成两个块，第二块只有1个字节，需要填充7个字节。如果把9字节的明文数据记为：•F1F2F3F4F5F6F7F8F9•（1）Zeros填充算法：需要填充的7个字节全部填充为0，分组结果为：•第一个消息分组：•F1F2F3F4F5F6F7F8•第二个消息分组：•F900000000000000–Zeros填充算法无法区分第二个消息分组中F9后的0序列是否是明文中的原始序列，因此该填充算法不可逆。•（2）X923填充算法：需要填充的7个字节中前6个字节填充0，最后一个字节记录填充的总字节数，分组结果为：•第一个消息分组：•F1F2F3F4F5F6F7F8•第二个消息分组：•F900000000000007•（3）PKCS7填充算法：需要填充的7个字节中的每一个字节填充需要填充的总字节数，分组结果为：•第一个消息分组：•F1F2F3F4F5F6F7F8•第二个消息分组：•F907070707070707•（4）ISO10126填充算法：需要填充的7个字节中前6个字节填充随机字节序列，最后一个字节记录填充的总字节数，分组结果为：•第一个消息分组：•F1F2F3F4F5F6F7F8•第二个消息分组：•F97D2A75EFF8EF072.1.1Feistel分组密码的基本结构Feistel密码结构是基于1949年Shannon提出的交替使用代换和置换方式构造密码体制的设想提出的。–在设计密码体制的过程中，Shannon提出了能够破坏对密码系统进行各种统计分析攻击的两个基本操作：扩散(diffusion)和混淆(confusion)。明文(2L)密文(2L)R0(L)R1(L)Rn(L)L0(L)L1(L)Ln(L)ff++…K1KnLn-1(L)Rn-1(L)+f…Kn-1•Feistel分组密码的一个加密阶段示意图•其中S操作通过密钥为每一个阶段生成一个子密钥，T为每一轮加密过程中的核心操作，要求为非线性运算，保证加密算法的安全性。明文LRL’R’TS替换置换密钥•Feistel型的分组密码的安全性取决于以下几个方面：•（1）明文消息和密文消息的分组大小•（2）子密钥的大小•（3）循环次数•（4）子密钥产生算法•（5）轮函数在其它条件相同的情况下，每一轮加密的分组长度越大，加密算法的安全性就越高，而相应的加密速度也越慢，效率越低。目前常用的分组加密算法的分组长度取64位。算法的安全性随着子密钥长度的增加而提高，但是相应的加密速度会降低，所以设计分组密码时需要在安全性和加密效率之间进行平衡。在实际应用中，一般认为，要保证分组加密算法满足计算安全性，子密钥的长度至少要大于128位。循环越多安全性越高，相应的加密效率也就越低。在初始密钥给定的情况下，产生子密钥的算法越复杂，加密算法的安全性越高。对于轮函数的讨论相对较复杂，一般认为，轮函数越复杂，对应的加密算法的安全性越高。Feistel分组密码的解密过程与加密过程是相同的。解密过程将密文作为算法的输入，同时按照与加密过程相反的次序使用子密钥对密文序列进行加密，即第1轮使用nK，第2轮使用1nK，依此类推，最后一轮使用1K，进行相同次数加密，“加密”的结果就得到相应的明文序列。2.1.2函数的设计准则•Feistel分组密码的核心是轮函数(非线性)。•设计的函数应该满足–严格的雪崩准则SAC（StrictAvalancheCriterion）–位独立准则BIG（BitIndependenceCriterion）–保证的雪崩准则GAC（GuaranteedAvalancheCriterion）2.2数据加密标准----DES•DES是DataEncryptionStandard（数据加密标准）的缩写。它是由IBM公司研制的一种加密算法，二十年来，它一直活跃在国际保密通信的舞台上，扮演了十分重要的角色。DES算法的历史过程•20世纪70年代中期，美国政府认为需要一个强大的标准加密系统，美国国家标准局提出了开发这种加密算法的请求，最终IBM的Lucifer加密系统胜出。•1972年美国商业部所属的美国国家标准局NBS(NationalBureauofStandards)开始实施计算机数据保护标准的开发计划。•1973年5月13日，美国国家标准局NBS发布文告征集在传输和存贮数据中保护计算机数据的密码算法。•1975年3月17日，首次公布DES算法描述，认真地进行公开讨论。•1977年1月15日，正式批准为无密级应用的加密标准(FIPS—46)，当年7月1日正式生效。以后每隔5年美国国家安全局对其安全性进行一次评估，以便确定是否继续使用它作为加密标准。在1994年1月的评估后决定1998年12月以后不再将DES作为数据加密标准。•DES是一个分组加密算法，它以64位为分组对数据加密。同时DES也是一个对称算法：加密和解密用的是同一个算法。它的密钥长度是56位（因为每个第8位都用作奇偶校验），密钥可以是任意的56位的数，其中极少量的56位数被认为是弱密钥，为了保证加密的安全性，在加密过程中应该尽量避开使用这些弱密钥。2.2.1DES的描述•DES是一个包含16个阶段的“替换--置换”的分组加密算法，64位的分组明文序列作为加密算法的输入，经过16轮加密得到64位的密文序列。•尽管DES密钥的长度有64位，但用户只提供56位，其余的8位由算法提供，分别放在8、16、24、32、40、48、56、64位上，结果是每8位的密钥包含了用户提供的7位和DES算法确定的1位。添加的位是有选择的，使得每个8位的块都含有奇数个奇偶校验位（即1的个数为奇数）。明文（64bits）IP置换（64bits）L0(32bits)R0(32bits)L1=R0R1=L0f(R0,k1)fki+16轮同样运算…L16+R16=L15f(R15,ki)+IP-1置换（64bits）DES算法结构密文（64bits）图2-3一轮DES加密过程Li-1Ri-1密钥Li密钥Ri扩展变换S盒替代P盒置换移位移位压缩变换++111(,)iiiiiiLRRLfRKDES：f的结构(即黑盒变换)R（32bit）EE(R)（48bit）K（48bit）B1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P+（48bit）（32bit）•DES加密过程中包含的基本操作：•初始置换•初始置换（InitialPermutation，简称置换）在第一轮运算之前执行。IPIPIP置换表58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157(1)58表示：结果中位于第1个位置的值，等于原文中第58个位置的值(2)图中的一格代表1bit，共有64bit，即8字节DES：IP置换•扩展变换：扩展变换（ExpansionPermutation，也被称为E－盒）将64位输入序列的右半部分从32位扩展到48位。3212345456789891011121312131415161716171819202120212223242524252627282928293031321扩展变换•E－盒的真正作用是确保最终的密文与所有的明文位都有关。•初始10000000000000000000000000000000•第1阶段01000000000000000000000000000001•第2阶段10100000000000000000000000000010•第3阶段01010000000000000000000000000101•第4阶段10101000000000000000000000000101•第5阶段01010100000000000000000000010101•第6阶段10101111010000000000000010101010•第7阶段01010101111000100101010101010101•第8阶段10101010101111111010111010101010第二次E－盒作用于该单词，初始的影响延伸到了位置1、3和31。第8次该单词通过E－盒后，E－盒对每个位都有影响。第一个E－盒操作将位复制，并将它放在位置2和位置32；•S－盒替换（S－boxesSubstitution）48比特输入32比特输出S－盒1S－盒2S－盒3S－盒4S－盒5S－盒6S－盒7S－盒8S－盒11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S－盒21518146113497213120510313471528141201106911501441110413158126932151381013154211671205149S－盒31009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S－盒47131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S－盒52124171011685315130149141121247131501510398642111101378159125630141181271142136150910453S－盒61211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S－盒74112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S－盒81328461511110931450127115138103741256110149271141912142061013153582114741081315129035611S－盒11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S—盒的输出表示设对应S－盒1的输入序列为：行号：11即3列号：0111即70123012345689101112131415结果为7即01117•P－盒置换（P-boxesPermutation）1672021291228171152326518311028241432273919133062211425•逆初始置换（InverseInitialPermutation）40818165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725•初始置换和对应的逆初始置换操作并不会增强DES算法的安全性，它的主要目的是为了更容易地将明文和密文数据以字节大小放入DES芯片中。轮子密钥的生成初始密钥（64比特）D0(28比特)循环移位循环移位密钥置换C0(28比特)压缩置换循环移位循环移位子密钥K1…………57494133251