摘  要： 在IDEA算法的基礎(chǔ)上，分析其存在的弱密鑰，其加密過程也決定了相同的明文必定加密成相同的密文，容易暴露明文的統(tǒng)計學(xué)特性。設(shè)計了基于IDEA 算法的加密算法X_IDEA，較好地解決了IDEA算法的弱密鑰問題。X_IDEA算法的加密過程中嵌套IDEA算法，特殊的加密過程設(shè)計使得其安全性和抗攻擊能力較IDEA算法更強(qiáng)。
關(guān)鍵詞： IDEA算法；X_IDEA 算法；IDEA_KEY算法；加密

1 IDEA算法簡述
　IDEA(Internation Data Encryption Algorithm)數(shù)據(jù)加密算法是由中國學(xué)者來學(xué)嘉博士和著名的密碼專家James L.Massey于1990年聯(lián)合提出的。IDEA是對64 bit大小的數(shù)據(jù)塊加密的分組加密算法，密鑰長度為128 bit，是基于“相異代數(shù)群上的混合運(yùn)算”的設(shè)計思想，其算法用硬件和軟件實(shí)現(xiàn)都很容易，而且比DES實(shí)現(xiàn)快。IDEA算法既可用于加密，又可用于解密。
　IDEA也被認(rèn)為是目前世界上最好最安全的分組密碼算法，且對計算機(jī)功能要求不高。IDEA的128 bit密鑰長度，相對較長，但加密強(qiáng)度高。在窮舉攻擊的情況下，IDEA需要經(jīng)過2128次加密才能恢復(fù)出密鑰，假設(shè)芯片每秒能檢測100億個密鑰，需要10年。IEDA被認(rèn)為僅循環(huán)4次即可抵制差分密碼分析，對IDEA算法也不起作用，隨機(jī)選擇密鑰基本沒有危險，故其安全性較高。IDEA算法基于一些可靠的基礎(chǔ)理論，軟件實(shí)現(xiàn)的IDEA比DES快2倍。
　IDEA算法是由八個相似圈外加一個輸出變換組成的循環(huán)密碼。圈函數(shù)的模塊是模216+1乘法。模216加法和按位XOR。IDEA有一個128 bit的總密鑰和以64 bit為塊的加密數(shù)據(jù)。  
除密鑰調(diào)度之外，IDEA解密過程與加密過程相同。加密圈密鑰是總密鑰的16 bit子串，如表1所示。解密圈密鑰能從加密圈密鑰中導(dǎo)出。
1.1 IDEA明文長度
　在IDEA算法中，加密前對明文的處理方法是：依次將明文分解成64 bit的數(shù)據(jù)塊，最后一個數(shù)據(jù)塊如果不足64 bit則進(jìn)行補(bǔ)位處理。明文的長度固定且比較短只有64 bit，因此，在對格式化數(shù)據(jù)進(jìn)行明文分組時必然存在較多的相似明文分組，并且這些相似的明文分組往往是連續(xù)排列的。IDEA算法在進(jìn)行加密時當(dāng)前被加密明文分組與其他明文分組沒有任何關(guān)系，加密密鑰和加密流程也完全相同，所以在對格式化數(shù)據(jù)進(jìn)行加密時，明文中相同的部分會被加密成相同的密文，明文的數(shù)據(jù)格式及某些統(tǒng)計學(xué)特性也將暴露無遺，降低了明文的保密性[1]。
1.2 IDEA的弱密鑰
　IDEA算法一次完整的加密運(yùn)算需要52個(832 bit)子密鑰。這52個16 bit的子密鑰都是由一個128 bit的加密密鑰產(chǎn)生的。生成的過程如下：
　將128 bit分成8份，每份16 bit，相當(dāng)于Z1~Z8的子密鑰。Z1的16 bit對應(yīng)加密密鑰中的最高階的16 bit。而Z8的16 bit對應(yīng)加密密鑰中的最低階的16 bit。將加密密鑰循環(huán)左移25 bit之后，同樣可得到另外8個子密鑰Z9~Z16。重復(fù)同樣的步驟，依次循環(huán)即可得到52個子密鑰(詳見表1)。

　參考文獻(xiàn)[2]中指出了IDEA算法中存在弱密鑰的問題。在標(biāo)準(zhǔn)IDEA算法產(chǎn)生的密鑰中，其中的一類(223個)密鑰存在一個線性因子；另一類(235個)具有一個概率為1的環(huán)形階；還有一類(251個)，可以解一組含有12個變量的16個非線性布爾等式測試出所使用的密鑰是否屬于這一類，若使用的密鑰屬于這一類，則就有高效破譯這一密鑰的方法。
　在參考文獻(xiàn)[3]中，作者就是通過這些不斷重復(fù)出現(xiàn)的128 bit原始密鑰，通過這些特別選定的密文可以測試和觀察出密鑰所含的線性因子，通過8輪的迭代，密鑰中的線性因子也逐漸增多，可推算出26~40 bit，72~83 bit和99~122 bit密鑰的值。按照IDEA算法設(shè)計者的思路其密鑰空間應(yīng)該為2128，但現(xiàn)有251個為弱密鑰，所以其真實(shí)密鑰空間應(yīng)該為277。
2 X_IDEA算法設(shè)計
2.1 明文處理
　在X-IDEA算法中，不再按IDEA算法中那樣依次將明文分解成64 bit的數(shù)據(jù)分組。加密前先對明文進(jìn)行重組，加大明文的初始分組長度，進(jìn)行第一次等長分組后判斷各分組的長度是不是64的整數(shù)倍，如果不是則對明文進(jìn)行補(bǔ)位(特殊字符)，使明文的長度達(dá)到64的整數(shù)倍；如果明文的長度是64的整數(shù)倍，則不做補(bǔ)位處理。最后加密前再將每一組明文分解成若干64 bit的明文分組，此為第二次分組，所以加密的明文分組仍為64 bit。
　明文重組過程如圖1所示。

　在圖1明文重組的第二步中，實(shí)際上絕大多數(shù)情況下需要對數(shù)據(jù)分組進(jìn)行補(bǔ)位處理，對于格式化的明文文件，其明文統(tǒng)計學(xué)特性能得到部分的隱藏。實(shí)際上，在進(jìn)行明文重組時，也可以將第一次分組所得到的明文分組按照特定順序?qū)⑵渲匦屡帕?，則明文數(shù)據(jù)分組更無規(guī)則可尋。
與IDEA算法中的各明文分組單獨(dú)加密的方式不同的是，在X_IDEA算法中，將通過隨機(jī)數(shù)發(fā)生器隨機(jī)產(chǎn)生一個明文分組作為加密的首個明文分組，且后續(xù)加密過程中前后明文之間關(guān)系密切，算法的混淆性也進(jìn)一步加強(qiáng)，具體詳見X_IDEA的加、解密過程。
2.2 密鑰生成
　X_IDEA算法中不再強(qiáng)調(diào)密鑰為128 bit，而是通過用戶輸入的長度不定的初始密鑰，通過密鑰生成算法IDEA_KEY生成832 bit(52組×16 bit)子密鑰。密鑰生成算法IDEA_KEY所生成的832 bit子密鑰中不能分析出弱密鑰，下面介紹并分析該算法。IDEA_KEY算法如下：
　IDEA_KEY算法：
　輸入：任意長度的密鑰
　輸出：832 bit(52組×16 bit)子密鑰
Inupt KEY  //輸入初始密鑰
SUBKEY=””
Do While Len(SUBKEY)<=832
　L=Len(KEY)
 If GCD(L，832)=1 Then
//初始密鑰的長度與832互素
        (L*T) Mod 832=1 
//計算出初始密鑰長度的逆元數(shù)T
If Left(KEY，1)=”0” Then KEY=KEY/2^T Else KEY=KEY*2^T  //密鑰移位
For I=1 TO L //將移位后的密鑰依次賦值給子密鑰
 SUBKEY=SUBKEY+Mid(KEY，I，1)
Next I
If Len(SUBKEY)=832 THEN
        Exit Do
Else
        GOTO EXT_DO
End If
Elseif L Mod 2=0 Then  
//初始密鑰長度與832不互素，補(bǔ)位處理其長度
        KEY=KEY+”0”
        Else
        KEY=KEY+”1”
End If
EXT_DO：
Loop
　在IDEA_KEY算法中，初始密鑰的長度可能≤832 bit或>832 bit。對于≤832 bit的初始密鑰，每次都要經(jīng)過移位后才將其逐位賦值給子密鑰，而移位方向以及位數(shù)與初始密鑰的首位及長度都有關(guān)系且每輪循環(huán)都在變化，密鑰的首位決定移位的方向，密鑰長度的逆元決定移位的位數(shù)；對于長度>832 bit的初始密鑰，雖然有可能存在前832 bit相同的初始密鑰，但只要其不完全相同也會生成不同的子密鑰。
2.3 加密過程
　加密過程是對重組后的明文進(jìn)行分組處理，每組64 bit。在所有重組好的明文分組中由隨機(jī)數(shù)產(chǎn)生器隨機(jī)產(chǎn)生數(shù)據(jù)X，作為加密的初始數(shù)據(jù)，X為64 bit，運(yùn)用IDEA數(shù)據(jù)加密算法對數(shù)據(jù)X以及除最后一個明文分組之外的所有明文分組進(jìn)行加密，產(chǎn)生密文C0和密文分組D1，D2，D3…Dn-1，對密文C0再次進(jìn)行加密操作，將產(chǎn)生的密文C0′與明文P1進(jìn)行“異或”操作C1=C0’⊕P1產(chǎn)生密文C1，再將密文D1與明文P2進(jìn)行“異或”操作產(chǎn)生密文C2，密文D2與明文P3進(jìn)行“異或”操作產(chǎn)生密文C3，依此方式進(jìn)行運(yùn)算產(chǎn)生直到所有的密文C=C1C2C3…Cn。最后將密文C0置于密文C頭部形成總的密文C=C0C1C2…Cn。加密規(guī)則公式表示如下：
　
X_IDEA算法中嵌套了IDEA算法進(jìn)行加密，也未對IDEA算法的加密原理及加密過程進(jìn)行改變，所以X_IDEA算法的混淆性與擴(kuò)散性肯定不低于IDEA算法。實(shí)際上，在X_IDEA算法的加密過程中，首個隨機(jī)加密數(shù)據(jù)分組的引入以及前一密文與后一明文“異或”再產(chǎn)生密文的方式進(jìn)一步增強(qiáng)了算法的混淆性。
2.4 解密過程
　解密過程是對密文進(jìn)行分組處理，分為C0，C1，C2，C3，…Cn共(n+1)個組，每組也是64 bit。對密文的第一個分組C0使用IDEA數(shù)據(jù)加密算法進(jìn)行加密，產(chǎn)生密文C0′，并將產(chǎn)生的密文C0′與密文C1進(jìn)行“異或”操作，產(chǎn)生明文P1，對明文P1進(jìn)行加密操作，將產(chǎn)生的密文與密文C2進(jìn)行“異或”操作，產(chǎn)生明文P2，對明文P2進(jìn)行加密操作，將產(chǎn)生的密文與C3進(jìn)行“異或”操作，產(chǎn)生明文P3，依此方式進(jìn)行運(yùn)算，直到產(chǎn)生所有的明文P=P1P2P3…Pn。解密規(guī)則公式表示如下：

　由于加密前的明文進(jìn)行過重組，所以解密完成后同樣要對產(chǎn)生的明文進(jìn)行重組工作。如果產(chǎn)生的明文分組后存在加密前明文重組時所補(bǔ)得的特殊字符，要將其去除后再進(jìn)行重組。其重組過程就是加密前明文重組的逆過程。
3 X_IDEA加密性能分析
　(1)IDEA算法弱密鑰問題得到有效解決
　在IDEA算法中，根據(jù)128 bit的密鑰就可以得出表1，且參考文獻(xiàn)[2]和參考文獻(xiàn)[3]都證明了其弱密鑰的存在。X_IDEA算法通過密鑰生成算法IDEA_KEY生成832 bit子密鑰，子密鑰的生成過程無法找出固定的分析方法，因為密鑰的移位及補(bǔ)位操作都與初始密鑰KEY的長度和具體的值有關(guān)，無法進(jìn)行分析。由此可見，算法IDEA_KEY產(chǎn)生的832 bit子密鑰沒有固定的位置生成表1，從而使IDEA算法的弱密鑰問題得到有效地解決。
X_IDEA算法沒有改變IDEA算法的加密原理，而是在用戶密鑰與子密鑰的生成上給予了加強(qiáng)。用戶可以隨意輸入密鑰，通過該算法可以生成較強(qiáng)的子密鑰；同時也可以滿足對密鑰強(qiáng)度要求較高的用戶，做到密鑰空間為832 bit(而不是128 bit)，因而安全性不會低于標(biāo)準(zhǔn)的 IDEA算法。
　(2)密文的明文依賴性有所提高
　在X_IDEA算法中，明文加密前先要進(jìn)行重組，先后要進(jìn)行兩次明文分組，最后得到一個個64 bit的明文塊。首個加密的明文塊是通過隨機(jī)數(shù)發(fā)生器確定的，并且在X_IDEA算法的加密過程中前一數(shù)據(jù)塊加密后得到的密文還將數(shù)據(jù)參與后一數(shù)據(jù)塊的加密。這樣，加密后的密文的長度會加長。同時，如果明文發(fā)生了改變，除了會改變同部分、同組數(shù)據(jù)加密后的結(jié)果外，也會導(dǎo)致不同組、不同部分?jǐn)?shù)據(jù)的加密結(jié)果發(fā)生改變，從而增加了數(shù)據(jù)的依賴性，使密文與明文的統(tǒng)計特性之間的關(guān)系更加復(fù)雜。
　(3)抗攻擊能力較IDEA算法更強(qiáng)
　算法設(shè)計者已證明IDEA算法在加密循環(huán)過程中的第4次循環(huán)之后不再受差分密碼分析的影響，因而目前也尚未出現(xiàn)對IDEA算法較為有效的分析方法。所以，對IDEA的攻擊到目前為止仍只能采用強(qiáng)攻擊方式。
對稱密鑰密碼體制要求算法是公開的，其安全性依賴于密鑰的安全性，密鑰長度應(yīng)足夠長，以防止窮舉式搜索方法的攻擊[4]。密鑰長度為1時攻擊次數(shù)為21，密鑰長度為2時攻擊次數(shù)為22，所以算法的抗攻擊能力隨密鑰的長度加大而增強(qiáng)。X_IDEA算法的密鑰長度實(shí)際可達(dá)832 bit，則它的攻擊次數(shù)為2832，而IDEA標(biāo)準(zhǔn)算法的攻擊次數(shù)為2128次。
　(4)安全性有所提高
　由于分組密碼可以作為序列密碼使用，X_IDEA算法的加密過程中，加密的首個數(shù)據(jù)塊以及各明文塊都充當(dāng)了加密密鑰，根據(jù)X_IDEA算法的加密方程，在X_IDEA算法中，一次一密亂碼本是由加密明文提供的，密鑰是C0和P1P2P3……Pi序列的函數(shù)具有很強(qiáng)的隨機(jī)性；而“異或”運(yùn)算是非線性算法，而且在整個加密過程中相當(dāng)于嵌套了IDEA算法，因而其安全性高于IDEA。
　X_IDEA算法在密鑰的選擇上給用戶帶來更大的靈活性，增強(qiáng)了算法的適應(yīng)性，同時也消除了IDEA算法中的弱密鑰，抗攻擊能力進(jìn)一步增強(qiáng)。加密前的明文重組以及初始向量的設(shè)置可以使用相同的明文加密成不同的密文，密文的明文依賴性更強(qiáng)。而且X_IDEA算法并沒有改變IDEA算法的加密原理，只是在加密過程中嵌套了IDEA算法，所以計算量也不會增加。
參考文獻(xiàn)
[1] 吳偉彬，黃元石.IDEA算法的改進(jìn)及其應(yīng)用[J].福州大學(xué)學(xué)報，2004，32(12)：28-31.
[2] 金茂順.IDEA弱密鑰[J].密碼與信息，1997，61(3)：9-14.
[3] JOAN D. GOVAERTS R. VANDEWALLE J. Weak keys for IDEA. Crypto， 1993：224-231.
[4] SCHNEIER B.應(yīng)用密碼學(xué)[M].吳世忠譯.北京：機(jī)械工業(yè)出版社，2000.