【安全课件】第11讲--idea算法

IDEA分组密码算法王滨2005年3月23IDEA分组密码算法概述XuejiaLai和JamesMassey于1990年提出了PES（ProposedEncryptionStandard，推荐加密标准）分组密码算法。为了抗击差分密码分析，设计者于1991年对PES作了改进，并将改进后的算法称为IPES（ImprovedProposedEncryptionStandard，改进型推荐加密标准）。IPES于1992年改名为IDEA（InternationalDataEncryptionAlgorithm，国际数据加密标准）。算法的描述分组长度：64比特密钥长度：128比特迭代圈数：8圈（每圈6个子密钥），附加一个输出变换（4个子密钥）。子密钥长度：16比特。52个子密钥由128比特初始密钥通过密钥生成算法生成。使用的三种基本运算：按位模2加；模216加法，模216+1乘法。整个运算过程全部在16位子分组上进行，因此该算法对16位处理器尤其有效。将待加密的64比特明文数据X分成4个16位子块，作为算法第一圈的输入，每圈有6个16比特圈子密钥参与变换，经过8圈迭代后得4个16比特子块，再通过一个输出变换得算法的输出，级连起来即为密文Y。4321,,,xxxx4321,,,yyyy（一）加密算法所用符号的含义：xi（i=1,2,3,4）是16比特明文子分组；yi（i=1,2,3,4）是16比特密文子分组；zi（i=1,…,52）16比特圈子密钥；wi,j(i=1,2,...,8;j=1,2,3,4）是16比特中间结果；⊕表示16比特的逐位异或运算；表示16比特整数的模216加法运算；表示16比特整数的模216+1乘法运算，其中全零子块用216代替。64bit明文X11w12w13w14w循环27z12z输出变换81w82w83w84w49z52z21w22w23w24w循环843z48z71w72w73w74w循环11z6z1x2x3x4x1y2y3y4y64bit密文Y子密钥生成算法1z52z128bit密钥ZIDEA加密总体方案流程图1k2k1,21234(,,,)kkfmmmmIDEA第一圈的细节5z6z3x1x4x1z2x2z3z4z11w12w14w13wFz5,z683w81w84w49z82w50z51z52z2y1y3y4yIDEA的输出变换（二）子密钥生成算法首先将128比特初始密钥从左到右分成8个16比特子块，并将所得的8个子块直接作为加密算法中最前面的8个子密钥，然后将上述128比特密钥循环左移25位，将其从左到右分成8个16比特子块，得到随后的8个子密钥，重复这个过程，直到产生52个16比特子密钥为止。（三）脱密算法这里z-1表示z的模216+1乘法逆，-z表示z的模216加法逆。脱密密钥与加密密钥的对应关系为：)(rik)(riz),,,(),,,(11)10(4)10(2)10(3)10(1)(4)(3)(2)(1rrrrrrrrzzzzkkkk8,,2r),,,(),,,(11)10(4)10(3)10(2)10(1)(4)(3)(2)(1rrrrrrrrzzzzkkkk9,1r；),(),()9(6)9(5)(6)(5rrrrzzkk8,,1r。脱密算法与加密算法是相同的，只是在脱密过程中使用脱密密钥。圈数加密子密钥脱密子密钥12345678输出变换)1(6)1(5)1(4)1(3)1(2)1(1ZZZZZZ)2(6)2(5)2(4)2(3)2(2)2(1ZZZZZZ)3(6)3(5)3(4)3(3)3(2)3(1ZZZZZZ)4(6)4(5)4(4)4(3)4(2)4(1ZZZZZZ)5(6)5(5)5(4)5(3)5(2)5(1ZZZZZZ)6(6)6(5)6(4)6(3)6(2)6(1ZZZZZZ)7(6)7(5)7(4)7(3)7(2)7(1ZZZZZZ)8(6)8(5)8(4)8(3)8(2)8(1ZZZZZZ)9(4)9(3)9(2)9(1ZZZZ)8(6)8(5)9(4)9(3)9(2)9(111ZZZZZZ)7(6)7(5)8(4)8(2)8(3)8(111ZZZZZZ)6(6)6(5)7(4)7(2)7(3)7(111ZZZZZZ)5(6)5(5)6(4)6(2)6(3)6(111ZZZZZZ)4(6)4(5)5(4)5(2)5(3)5(111ZZZZZZ)3(6)3(5)4(4)4(2)4(3)4(111ZZZZZZ)2(6)2(5)3(4)3(2)3(3)3(111ZZZZZZ)1(6)1(5)2(4)2(2)2(3)2(111ZZZZZZ11)1(4)1(3)1(2)1(1ZZZZIDEA加、脱密子密钥的关系64bit明文X11I12I13I14I子加密过程5z6z输出变换81w82w83w84w49z52z11w12w13w14w循环843z48z71w72w73w74w变换1z4z1x2x3x4x1y2y3y4y64bit密文Y循环111V12V13V14V5u6u1u4u循环11y2y3y4y子加密过程变换循环881w82w83w84w49z52z43z48z输出变换71w72w73w74w11j12j13j14j81I82I83I84I子加密过程47z48z变换81w82w83w84w43z46z输出变换49z52z1y2y3y4y64bit密文Y11V12V13V14V5u6u1u4u循环11y2y3y4y子加密过程变换11j12j13j14j64bit密文Y循环85z6z3x1x4x1z2x2z3z4z11w12w14w13w（四）IDEA加、脱密变换的相似性图示的变换是IDEA的圈变换中的一部分，称为共处理变换。1y2y3y4y1x2x3x4xzz设该变换的输入为：4321,,,xxxx输出为：4321,,,yyyy要证明IDEA加、脱密算法的相似性，只需证明共处理变换的4个输入子块经过两次共处理变换后的输出仍然是它本身即可。若记乘加结构输出的左16比特为LMA，右16比特为RMA，则有下面4个式子：),,,(423111zzxxxxRMAxy),,,(423122zzxxxxLMAxy),,,(423133zzxxxxRMAxy),,,(423144zzxxxxLMAxy由于3131xxyy，4242xxyy),,,(423111zzyyyyRMAyx),,,(423122zzyyyyLMAyx),,,(423133zzyyyyRMAyx),,,(423144zzyyyyLMAyx则：这说明当共处理变换以作为输入，而子密钥不变时，其输出为。至此证明了IDEA分组密码加、脱密变换的相似性。zz,4321,,,yyyy4321,,,xxxx二、IDEA算法的设计原理IDEA是一种使用128比特密钥以64比特分组为单位加密数据的分组密码，其设计目标可以归结为两方面：一方面与密码强度有关，另一方面与使用的方便性有关。（一）密码强度IDEA的下列特性与其密码强度有关：分组长度：分组长度应足够大，以抵抗统计分析。使用64比特的分组大小通常认为已经足够强，另外使用密码反馈操作方式可以进一步加强算法这方面的强度。密钥长度：密钥长度应足够长，以抵抗密钥穷尽攻击，通过使用128比特的长度，在将来的很长时间里IDEA似乎在这方面都是安全的。关于混乱：密文应以一种复杂的方式依赖于明文和密钥，这样做的目的是使确定密文的统计特性和明文的统计特性的依赖关系非常复杂。IDEA通过使用三种不同的操作达到该目的，而DES主要靠异或运算及小的非线性S盒代替来实现。关于扩散：每个明文比特都应该影响每个密文比特，并且，每个密钥比特都应该影响每个密文比特。单个明文比特应扩散到许多密文比特才能隐藏明文的统计特性。在IDEA中，扩散是由乘加结构（MA）实现的。MA的输入有两部分，一部分是由明文导出的两个16比特数值，另一部分是两个16比特子密钥。计算机进行的彻底检查证明，第一圈输出的每一比特依赖于输入（明文部分和密钥部分）的每一比特。经8圈循环之后，可提供非常有效的扩散。（二）实现方面的考虑IDEA的设计考虑到了方便硬件和软件实现。通常由超大规模集成电路进行的硬件实现的设计目标是取得高速度，而软件实现则有灵活和低价的优点。使用子分组：密码操作应该在对于软件来说很自然的子分组上进行，具有这种特性的子分组包括8，16或32比特，IDEA使用16比特子分组。使用简单操作：密码操作应该容易使用加法、移位等基本操作编程实现。IDEA的三种操作符合该要求，其中最困难的模乘法也可以容易地用简单的基本操作构成。1、便于软件实现的原则：模216+1乘法的具体运算过程如下：(1)如果a=0，则bab12)12mod(1616(2)若a、b为两个非零整数，则有)12mod(16ab)2()2(mod12)2()2(mod)2()2(mod)2()2(mod161616161616161616divababdivababdivababdivabab若若其中表示ab除以216所得的商。)2(16divab我们不妨用(ab)h表示32比特数ab的高16位，(ab)l表示32比特数ab的低16位，则有hlhlhabababababab)()()12()()(2)(1616hlababab)()()12mod(16则)2(mod)(16ababl)2()(16divababh其中加密和解密过程类似：加密和解密应该只在使用密钥的方式上有所不同，以便于同一个设备既可用于加密又可用于解密。和DES一样，IDEA具有满足该要求的结构。规则的结构：为便于VLSI（verylargescaleintegration，超大规模集成）实现，密码应该具有一种模块化结构。IDEA是由重复使用两种基本的模块化（变换子块和加密子块）构件而构成的。2、便于硬件实现的设计原则：下节内容分组密码小结