現(xiàn)代密碼學(xué)章節(jié)IDEA算法

現(xiàn)代密碼學(xué)章節(jié)IDEA算法2本節(jié)主要內(nèi)容1、IDEA基本概念2、IDEA設(shè)計(jì)原理3、IDEA加密過(guò)程4、IDEA3IDEA(InternationalDataEncryptionAlgorithm)是瑞士的JamesMassey，XuejiaLai等人提出的加密算法，在密碼學(xué)中屬于數(shù)據(jù)塊加密算法(BlockCipher)類。

IDEA使用長(zhǎng)度為128bit的密鑰，數(shù)據(jù)塊大小為64bit。從理論上講，IDEA屬于“強(qiáng)”加密算法，至今還沒(méi)有出現(xiàn)對(duì)該算法的有效攻擊算法。1.IDEA基本概念4

早在1990年，XuejiaLai等人在EuroCrypt’90年會(huì)上提出了分組密碼建議PES(ProposedEncryptionStandard)。在EuroCrypt’91年會(huì)上,XuejiaLai等人又提出了PES的修正版IPES(ImprovedPES)。目前IPES已經(jīng)商品化，并改名為IDEA。IDEA已由瑞士的Ascom公司注冊(cè)專利，以商業(yè)目的使用IDEA算法必須向該公司申請(qǐng)?jiān)S可。IDEA基本概念5IDEA是一個(gè)分組長(zhǎng)度為64位的分組密碼算法，密鑰長(zhǎng)度為128位（抗強(qiáng)力攻擊能力比DES強(qiáng)），同一算法既可加密也可解密。

IDEA能抗差分分析和相關(guān)分析；

IDEA似乎沒(méi)有DES意義下的弱密鑰；

IDEA的“混淆”和“擴(kuò)散”設(shè)計(jì)原則來(lái)自三種運(yùn)算，它們易于軟、硬件實(shí)現(xiàn)（加密速度快）IDEA基本概念6異或運(yùn)算（）整數(shù)模216加（+）整數(shù)模216+1乘（）(IDEA的S盒）擴(kuò)散由稱為MA結(jié)構(gòu)的算法基本構(gòu)件提供。Z6F2F1Z5G1G2IDEA運(yùn)算7實(shí)現(xiàn)上的考慮使用子分組：16bit的子分組；使用簡(jiǎn)單操作（易于加法、移位等操作實(shí)現(xiàn)）加密解密過(guò)程類似；規(guī)則的結(jié)構(gòu)（便于VLSI實(shí)現(xiàn)）。IDEA運(yùn)算82.IDEA設(shè)計(jì)原理1密碼的強(qiáng)度：主要是通過(guò)混淆和擴(kuò)散來(lái)實(shí)現(xiàn)?；煜龑?shí)現(xiàn)的方法：(1)逐比特異或。表示為(2)模整數(shù)加法，表示為，其輸入和輸出作為

16位無(wú)符號(hào)整數(shù)處理。模整數(shù)乘法，表示為，其輸入和輸出中除16

全0作為處理外，其余都作為16位無(wú)符號(hào)整數(shù)處理。9例如這是因?yàn)?16×215mod(216+1)=215+1。IDEA設(shè)計(jì)原理10

表3.6給出了操作數(shù)為2比特長(zhǎng)時(shí)3種運(yùn)算的運(yùn)算表。在以下意義下，3種運(yùn)算是不兼容的：①3種運(yùn)算中任意兩種都不滿足分配律，例如a+（b⊙c）≠(a+b)⊙(a+c)②3種運(yùn)算中任意兩種都不滿足結(jié)合律，例如a+（bc）≠(a+b)c+

IDEA設(shè)計(jì)原理113種運(yùn)算結(jié)合起來(lái)使用可對(duì)算法的輸入提供復(fù)雜的變換，從而使得對(duì)IDEA的密碼分析比對(duì)僅使用異或運(yùn)算的DES更為困難。算法中擴(kuò)散是由稱為乘加（multiplication/addition,MA）結(jié)構(gòu)（見(jiàn)圖4.14）的基本單元實(shí)現(xiàn)的。該結(jié)構(gòu)的輸入是兩個(gè)16比特的子段和兩個(gè)16比特的子密鑰，輸出也為兩個(gè)16比特的子段。這一結(jié)構(gòu)在算法中重復(fù)使用了8次，獲得了非常有效的擴(kuò)散效果。IDEA設(shè)計(jì)原理12IDEA算法的擴(kuò)散主要是由乘加結(jié)構(gòu)的基本單元實(shí)現(xiàn)的。IDEA的MA結(jié)構(gòu)13

IDEA加密的總體方案循環(huán)2循環(huán)8循環(huán)1輸出變換64位密文64位明文Z1Z6Z7Z12Z43Z48Z49Z52子密鑰生成器128位密鑰Z1Z521614

IDEA加密的總體方案圖15IDEA加密過(guò)程第1輪64比特明文X1X2X3X4第2輪W11W12W13W14第8輪W71W72W73W74W21W22W23W24W81W82W83W84輸出變換Y1Y2Y3Y4密文…Z1Z6…Z7Z12…Z43Z48…Z49Z52字密鑰生成器128比特密鑰Z1Z5216

加密過(guò)程（如圖4.15所示）由連續(xù)的8輪迭代和一個(gè)輸出變換組成，算法將64比特的明文分組分成4個(gè)16比特的子段，每輪迭代以4個(gè)16比特的子段作為輸入，輸出也為4個(gè)16比特的子段。最后的輸出變換也產(chǎn)生4個(gè)16比特的子段，鏈接起來(lái)后形成64比特的密文分組。每輪迭代還需使用6個(gè)16比特的子密鑰，最后的輸出變換需使用4個(gè)16比特的子密鑰，所以子密鑰總數(shù)為52。圖4.15的右半部分表示由初始的128比特密鑰產(chǎn)生52個(gè)子密鑰的子密鑰產(chǎn)生器。3.IDEA加密過(guò)程17

圖4.16是IDEA第1輪的結(jié)構(gòu)示意圖，以后各輪也都是這種結(jié)構(gòu)，但所用的子密鑰和輪輸入不同。從結(jié)構(gòu)圖可見(jiàn)，IDEA不是傳統(tǒng)的Feistel密碼結(jié)構(gòu)。每輪開(kāi)始時(shí)有一個(gè)變換，該變換的輸入是4個(gè)子段和4個(gè)子密鑰，變換中的運(yùn)算是兩個(gè)乘法和兩個(gè)加法，輸出的4個(gè)子段經(jīng)過(guò)異或運(yùn)算形成了兩個(gè)16比特的子段作為MA結(jié)構(gòu)的輸入。MA結(jié)構(gòu)也有兩個(gè)輸入的子密鑰，輸出是兩個(gè)16比特的子段。IDEA的輪結(jié)構(gòu)18IDEA第1輪的輪結(jié)構(gòu)19Y1Y2Y3Y41輪結(jié)構(gòu)20

最后，變換的4個(gè)輸出子段和MA結(jié)構(gòu)的兩個(gè)輸出子段經(jīng)過(guò)異或運(yùn)算產(chǎn)生這一輪的4個(gè)輸出子段。注意，由X2產(chǎn)生的輸出子段和由X3產(chǎn)生的輸出子段交換位置后形成W12和W13，目的在于進(jìn)一步增加混淆效果，使得算法更易抵抗差分密碼分析。IDEA加密過(guò)程21在每一輪中，執(zhí)行的順序如下：1.X1和第一個(gè)子密鑰相乘。2.X2和第二個(gè)子密鑰相加。3.X3和第三個(gè)子密鑰相加。4.X4和第四個(gè)子密鑰相乘。5.將第1步和第3步的結(jié)果相異或。6.將第2步和第4步的結(jié)果相異或。IDEA每一輪的加密順序227.將第5步的結(jié)果與第五個(gè)子密鑰相乘。8.將第6步和第7步的結(jié)果相加。9.將第8步的結(jié)果與第六個(gè)子密鑰相乘。10.將第7步和第9步的結(jié)果相加。11.將第1步和第9步的結(jié)果相異或。12.將第3步和第9步的結(jié)果相異或。13.將第2步和第10步的結(jié)果相異或。14.將第4步和第10步的結(jié)果相異或。IDEA每一輪的加密順序23

算法的第9步是一個(gè)輸出變換，如圖4.17所示。它的結(jié)構(gòu)和每一輪開(kāi)始的變換結(jié)構(gòu)一樣，不同之處在于輸出變換的第2個(gè)和第3個(gè)輸入首先交換了位置，目的在于撤銷第8輪輸出中兩個(gè)子段的交換。還需注意，第9步僅需4個(gè)子密鑰，而前面8輪中每輪需要6個(gè)子密鑰。IDEA每一輪的加密順序24IDEA的輸出變換25

加密過(guò)程中52個(gè)16比特的子密鑰是由128比特的加密密鑰按如下方式產(chǎn)生的：前8個(gè)子密鑰Z1，Z2，…，Z8直接從加密密鑰中取，即Z1取前16比特（最高有效位），Z2取下面的16比特，依次類推。然后加密密鑰循環(huán)左移25位，再取下面8個(gè)子密鑰Z9，Z10，…，Z16，取法與Z1，Z2，…，Z8的取法相同。這一過(guò)程重復(fù)下去，直到52子密鑰都被產(chǎn)生為止。IDEA子密鑰的產(chǎn)生26IDEA子密鑰的產(chǎn)生

產(chǎn)生子密鑰的方法。這個(gè)算法用了52個(gè)子密鑰（8輪中的每一輪需要6個(gè)，其他4個(gè)用于輸出變換）。首先，將128-位密鑰分成8個(gè)16-位子密鑰。這些是算法的第一批8個(gè)子密鑰（第一輪6個(gè)，第二輪的頭2個(gè)）。然后，密鑰向左環(huán)移動(dòng)25位產(chǎn)生另外8個(gè)子密鑰，如此進(jìn)行直到算法結(jié)束。2728294.IDEA的解密過(guò)程加密解密實(shí)質(zhì)相同，但使用不同的密鑰；解密密鑰以如下方法從加密子密鑰中導(dǎo)出：解密循環(huán)I的頭4個(gè)子密鑰從加密循環(huán)10－I的頭4個(gè)子密鑰中導(dǎo)出；解密密鑰第1、4個(gè)子密鑰對(duì)應(yīng)于1、4加密子密鑰的乘法逆元；2、3對(duì)應(yīng)2、3的加法逆元；對(duì)前8個(gè)循環(huán)來(lái)說(shuō)，循環(huán)I的最后兩個(gè)子密鑰等于加密循環(huán)9－I的最后兩個(gè)子密鑰；30

解密與加密過(guò)程基本相同，但使用的密鑰不同，解密密鑰按下面的方式生成。

(1)第i(i=1,2,…,9)輪解密的前4個(gè)子密鑰是由加密過(guò)程第(10-i)輪的前4個(gè)子密鑰得出。其中第1個(gè)和第4個(gè)解密子密鑰取為相應(yīng)的第一個(gè)和第四個(gè)加密子密鑰模乘法逆元。第二和第三個(gè)子密鑰的取法為：當(dāng)輪數(shù)為i=2,..,8時(shí)取為相應(yīng)的第三個(gè)和第二個(gè)加密子密鑰的模加法逆元，當(dāng)i=1和9時(shí)，取為相應(yīng)的第二個(gè)和第三個(gè)加密子密鑰的模加法逆元。IDEA的解密過(guò)程31(2)第i(i=1,…,8)輪解密的后兩個(gè)子密鑰等于加密過(guò)程的第(9-i)輪的后兩個(gè)子密鑰。IDEA的解密過(guò)程32加密過(guò)程變換X1X2X3X4Z1..Z4子加密I11I12I13I14Z5Z6變換W11W12W13W14Z7..Z10子加密I21I22I23I24Z11Z612W21W22W23W24變換W71W72W73W74Z43..Z46子加密I81I82I83I84Z47Z48變換W81W82W83W84Z49..Z52Y1Y2Y3Y4第1輪第2輪第8輪…………..33變換X1X2X3X4U49..U52子加密V81V82V83V84U47U48變換J81J82J83J84U43…U46子加密V71V72V73V74U11U12V21V22V23V24變換J21J22J23J24U7…U10子加密V11V12V13V14U5U6變換J11J12J13J14U1…U4Y1Y2Y3Y4第8輪第2輪第1輪解密第9輪…………..解密過(guò)程34

表3.7是對(duì)以上關(guān)系的總結(jié)。其中Zj的模216+1乘法逆元為Z-1j，滿足（見(jiàn)58頁(yè)表3.7）Zj⊙Z-1j=1mod(216+1)

因216+1是一素?cái)?shù)，所以每一個(gè)不大于216的非0整數(shù)都有一個(gè)惟一的模216+1乘法逆元。Zj的模216加法逆元為-Zj，滿足：

-Zj+Zj=0mod(216)IDEA的解密過(guò)程35

下面驗(yàn)證解密過(guò)程的確可以得到正確的結(jié)果。圖4.18中左邊為加密過(guò)程，由上至下，右邊為解密過(guò)程，由下至上。將每一輪進(jìn)一步分為兩步，第1步是變換，其余部分作為第2步，稱為子加密。IDEA的解密過(guò)程36IDEA加密和解密框圖37

現(xiàn)在從下往上考慮。對(duì)加密過(guò)程的最后一個(gè)輸出變換，以下關(guān)系成立：Y1=W81⊙Z49Y2=W83+Z50Y3=W82+Z51Y4=W84⊙Z52解密過(guò)程中第1輪的第1步產(chǎn)生以下關(guān)系：J11=Y1⊙U1J12=Y2+U2J13=Y3+U3J14=Y4⊙U4IDEA的解密過(guò)程38

將解密子密鑰由加密子密鑰表達(dá)并將Y1，Y2，Y3,，Y4代入以下關(guān)系，有J11=Y1⊙Z-149=W81⊙Z49⊙Z-149=W81J12=Y2+

-Z50=W83+

Z50+

-Z50=W83J13=Y3+

-Z51=W82+

Z51+

-Z51=W82J14=Y4⊙Z-152=W84⊙Z52⊙Z-152=W84IDEA的解密過(guò)程39

可見(jiàn)解密過(guò)程第1輪第1步的輸出等于加密過(guò)程最后一步輸入中第2個(gè)子段和第3個(gè)子段交換后的值。從圖4.16，可得以下關(guān)系：W81=I81MAR(I81I83，I82I84)W82=I83MAR(I81I83，I82I84)W83=I82MAL(I81I83，I82I84)W84=I84MAL(I81I83，I82I84)IDEA的解密過(guò)程40其中MAR(X,Y)是MA結(jié)構(gòu)輸入為X和Y時(shí)的右邊輸出，MAL(X,Y)是左邊輸出。則V11=J11MAR(J11J13,J12J14)=W81MAR(W81W82,W83W84)=I81MAR(I81I83,I82I84)MAR[I81MAR(I81I83,I82I84)I83MAR(I81I83,I82I84),I82MAL(I81I83,I82I84)I84

MAL(I81I83,I82I84)]=I81MAR(I81I83,I82I84)MAR(I8