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

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

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

　在圖1明文重組的第二步中，實際上絕大多數情況下需要對數據分組進行補位處理，對于格式化的明文文件，其明文統計學特性能得到部分的隱藏。實際上，在進行明文重組時，也可以將第一次分組所得到的明文分組按照特定順序將其重新排列，則明文數據分組更無規則可尋。
與IDEA算法中的各明文分組單獨加密的方式不同的是，在X_IDEA算法中，將通過隨機數發生器隨機產生一個明文分組作為加密的首個明文分組，且后續加密過程中前后明文之間關系密切，算法的混淆性也進一步加強，具體詳見X_IDEA的加、解密過程。
2.2 密鑰生成
　X_IDEA算法中不再強調密鑰為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 
//計算出初始密鑰長度的逆元數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不互素，補位處理其長度
        KEY=KEY+”0”
        Else
        KEY=KEY+”1”
End If
EXT_DO：
Loop
　在IDEA_KEY算法中，初始密鑰的長度可能≤832 bit或>832 bit。對于≤832 bit的初始密鑰，每次都要經過移位后才將其逐位賦值給子密鑰，而移位方向以及位數與初始密鑰的首位及長度都有關系且每輪循環都在變化，密鑰的首位決定移位的方向，密鑰長度的逆元決定移位的位數；對于長度>832 bit的初始密鑰，雖然有可能存在前832 bit相同的初始密鑰，但只要其不完全相同也會生成不同的子密鑰。
2.3 加密過程
　加密過程是對重組后的明文進行分組處理，每組64 bit。在所有重組好的明文分組中由隨機數產生器隨機產生數據X，作為加密的初始數據，X為64 bit，運用IDEA數據加密算法對數據X以及除最后一個明文分組之外的所有明文分組進行加密，產生密文C0和密文分組D1，D2，D3…Dn-1，對密文C0再次進行加密操作，將產生的密文C0′與明文P1進行“異或”操作C1=C0’⊕P1產生密文C1，再將密文D1與明文P2進行“異或”操作產生密文C2，密文D2與明文P3進行“異或”操作產生密文C3，依此方式進行運算產生直到所有的密文C=C1C2C3…Cn。最后將密文C0置于密文C頭部形成總的密文C=C0C1C2…Cn。加密規則公式表示如下：
　
X_IDEA算法中嵌套了IDEA算法進行加密，也未對IDEA算法的加密原理及加密過程進行改變，所以X_IDEA算法的混淆性與擴散性肯定不低于IDEA算法。實際上，在X_IDEA算法的加密過程中，首個隨機加密數據分組的引入以及前一密文與后一明文“異或”再產生密文的方式進一步增強了算法的混淆性。
2.4 解密過程
　解密過程是對密文進行分組處理，分為C0，C1，C2，C3，…Cn共(n+1)個組，每組也是64 bit。對密文的第一個分組C0使用IDEA數據加密算法進行加密，產生密文C0′，并將產生的密文C0′與密文C1進行“異或”操作，產生明文P1，對明文P1進行加密操作，將產生的密文與密文C2進行“異或”操作，產生明文P2，對明文P2進行加密操作，將產生的密文與C3進行“異或”操作，產生明文P3，依此方式進行運算，直到產生所有的明文P=P1P2P3…Pn。解密規則公式表示如下：

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