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

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

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

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

IDEA能抗差分分析和相關分析；

IDEA似乎沒有DES意義下的弱密鑰；

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

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

全0作為處理外，其余都作為16位無符號整數(shù)處理。9例如這是因為216×215mod(216+1)=215+1。IDEA設計原理10

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

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

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

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

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

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

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

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

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

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

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

(1)第i(i=1,2,…,9)輪解密的前4個子密鑰是由加密過程第(10-i)輪的前4個子密鑰得出。其中第1個和第4個解密子密鑰取為相應的第一個和第四個加密子密鑰模乘法逆元。第二和第三個子密鑰的取法為：當輪數(shù)為i=2,..,8時取為相應的第三個和第二個加密子密鑰的模加法逆元，當i=1和9時，取為相應的第二個和第三個加密子密鑰的模加法逆元。IDEA的解密過程31(2)第i(i=1,…,8)輪解密的后兩個子密鑰等于加密過程的第(9-i)輪的后兩個子密鑰。IDEA的解密過程32加密過程變換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輪…………..解密過程34

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

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

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

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

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

將解密子密鑰由加密子密鑰表達并將Y1，Y2，Y3,，Y4代入以下關系，有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的解密過程39

可見解密過程第1輪第1步的輸出等于加密過程最后一步輸入中第2個子段和第3個子段交換后的值。從圖4.16，可得以下關系：W81=I81MAR(I81I83，I82I84)W82=I83MAR(I81I83，I82I84)W83=I82MAL(I81I83，I82I84)W84=I84MAL(I81I83，I82I84)IDEA的解密過程40其中MAR(X,Y)是MA結構輸入為X和Y時的右邊輸出，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