X_IDEA算法設計＊

張 毅，肖四友，張文祥

(浙江萬里學院 智能控制研究所，浙江 寧波 315100)

1 IDEA算法簡述

IDEA(Internation Data Encryption Algorithm)數(shù)據(jù)加密算法是由中國學者來學嘉博士和著名的密碼專家James L.Massey于1990年聯(lián)合提出的。IDEA是對64 bit大小的數(shù)據(jù)塊加密的分組加密算法，密鑰長度為128 bit，是基于“相異代數(shù)群上的混合運算”的設計思想，其算法用硬件和軟件實現(xiàn)都很容易，而且比DES實現(xiàn)快。IDEA算法既可用于加密，又可用于解密。

IDEA也被認為是目前世界上最好最安全的分組密碼算法，且對計算機功能要求不高。IDEA的128 bit密鑰長度，相對較長，但加密強度高。在窮舉攻擊的情況下，IDEA需要經(jīng)過2128次加密才能恢復出密鑰，假設芯片每秒能檢測100億個密鑰，需要10年。IEDA被認為僅循環(huán)4次即可抵制差分密碼分析，對IDEA算法也不起作用，隨機選擇密鑰基本沒有危險，故其安全性較高。IDEA算法基于一些可靠的基礎理論，軟件實現(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所示。解密圈密鑰能從加密圈密鑰中導出。

1.1 IDEA明文長度

在IDEA算法中，加密前對明文的處理方法是：依次將明文分解成64 bit的數(shù)據(jù)塊，最后一個數(shù)據(jù)塊如果不足64 bit則進行補位處理。明文的長度固定且比較短只有64 bit，因此，在對格式化數(shù)據(jù)進行明文分組時必然存在較多的相似明文分組，并且這些相似的明文分組往往是連續(xù)排列的。IDEA算法在進行加密時當前被加密明文分組與其他明文分組沒有任何關系，加密密鑰和加密流程也完全相同，所以在對格式化數(shù)據(jù)進行加密時，明文中相同的部分會被加密成相同的密文，明文的數(shù)據(jù)格式及某些統(tǒng)計學特性也將暴露無遺，降低了明文的保密性[1]。

表1 IDEA算法密鑰生成表

1.2 IDEA的弱密鑰

IDEA算法一次完整的加密運算需要52個 (832 bit)子密鑰。這52個16 bit的子密鑰都是由一個128 bit的加密密鑰產(chǎn)生的。生成的過程如下：

將 128 bit分成 8份，每份 16 bit，相當于 Z1～Z8的子密鑰。Z1的16 bit對應加密密鑰中的最高階的16 bit。而Z8的16 bit對應加密密鑰中的最低階的16 bit。將加密密鑰循環(huán)左移25 bit之后，同樣可得到另外8個子密鑰Z9～Z16。重復同樣的步驟，依次循環(huán)即可得到52個子密鑰(詳見表1)。

[2]中指出了IDEA算法中存在弱密鑰的問題。在標準IDEA算法產(chǎn)生的密鑰中，其中的一類(223個)密鑰存在一個線性因子；另一類(235個)具有一個概率為1的環(huán)形階；還有一類(251個)，可以解一組含有 12個變量的16個非線性布爾等式測試出所使用的密鑰是否屬于這一類，若使用的密鑰屬于這一類，則就有高效破譯這一密鑰的方法。

在參考文獻[3]中，作者就是通過這些不斷重復出現(xiàn)的128 bit原始密鑰，通過這些特別選定的密文可以測試和觀察出密鑰所含的線性因子，通過8輪的迭代，密鑰中的線性因子也逐漸增多，可推算出 26～40 bit，72～83 bit和99～122 bit密鑰的值。按照IDEA算法設計者的思路其密鑰空間應該為2128，但現(xiàn)有251個為弱密鑰，所以其真實密鑰空間應該為277。

2 X_IDEA算法設計

2.1 明文處理

在X-IDEA算法中，不再按IDEA算法中那樣依次將明文分解成64 bit的數(shù)據(jù)分組。加密前先對明文進行重組，加大明文的初始分組長度，進行第一次等長分組后判斷各分組的長度是不是64的整數(shù)倍，如果不是則對明文進行補位(特殊字符)，使明文的長度達到64的整數(shù)倍；如果明文的長度是64的整數(shù)倍，則不做補位處理。最后加密前再將每一組明文分解成若干64 bit的明文分組，此為第二次分組，所以加密的明文分組仍為64 bit。

明文重組過程如圖1所示。

圖1 明文重組

在圖1明文重組的第二步中，實際上絕大多數(shù)情況下需要對數(shù)據(jù)分組進行補位處理，對于格式化的明文文件，其明文統(tǒng)計學特性能得到部分的隱藏。實際上，在進行明文重組時，也可以將第一次分組所得到的明文分組按照特定順序?qū)⑵渲匦屡帕?，則明文數(shù)據(jù)分組更無規(guī)則可尋。

與IDEA算法中的各明文分組單獨加密的方式不同的是，在X_IDEA算法中，將通過隨機數(shù)發(fā)生器隨機產(chǎn)生一個明文分組作為加密的首個明文分組，且后續(xù)加密過程中前后明文之間關系密切，算法的混淆性也進一步加強，具體詳見X_IDEA的加、解密過程。

2.2 密鑰生成

X_IDEA算法中不再強調(diào)密鑰為128 bit，而是通過用戶輸入的長度不定的初始密鑰，通過密鑰生成算法IDEA_KEY生成832 bit(52組×16 bit)子密鑰。密鑰生成算法IDEA_KEY所生成的832 bit子密鑰中不能分析出弱密鑰，下面介紹并分析該算法。IDEA_KEY算法如下：

IDEA_KEY算法：

在IDEA_KEY算法中，初始密鑰的長度可能≤832 bit或>832 bit。對于≤832 bit的初始密鑰，每次都要經(jīng)過移位后才將其逐位賦值給子密鑰，而移位方向以及位數(shù)與初始密鑰的首位及長度都有關系且每輪循環(huán)都在變化，密鑰的首位決定移位的方向，密鑰長度的逆元決定移位的位數(shù)；對于長度>832 bit的初始密鑰，雖然有可能存在前832 bit相同的初始密鑰，但只要其不完全相同也會生成不同的子密鑰。

2.3 加密過程

加密過程是對重組后的明文進行分組處理，每組64 bit。在所有重組好的明文分組中由隨機數(shù)產(chǎn)生器隨機產(chǎn)生數(shù)據(jù) X，作為加密的初始數(shù)據(jù)，X為 64 bit，運用IDEA數(shù)據(jù)加密算法對數(shù)據(jù)X以及除最后一個明文分組之外的所有明文分組進行加密，產(chǎn)生密文C0和密文分組 D1，D2，D3…Dn-1，對密文 C0再次進行加密操作，將產(chǎn)生的密文 C0′與明文 P1進行 “異或”操作C1=C0’⊕P1產(chǎn)生密文C1，再將密文D1與明文 P2進行“異或”操作產(chǎn)生密文 C2，密文 D2與明文 P3進行“異或”操作產(chǎn)生密文C3，依此方式進行運算產(chǎn)生直到所有的密文C=C1C2C3…Cn。最后將密文C0置于密文C頭部形成總的密文C=C0C1C2…Cn。加密規(guī)則公式表示如下：

X_IDEA算法中嵌套了IDEA算法進行加密，也未對IDEA算法的加密原理及加密過程進行改變，所以X_IDEA算法的混淆性與擴散性肯定不低于IDEA算法。實際上，在X_IDEA算法的加密過程中，首個隨機加密數(shù)據(jù)分組的引入以及前一密文與后一明文“異或”再產(chǎn)生密文的方式進一步增強了算法的混淆性。

2.4 解密過程

解密過程是對密文進行分組處理，分為C0，C1，C2，C3，…Cn共(n+1)個組，每組也是 64 bit。對密文的第一個分組C0使用IDEA數(shù)據(jù)加密算法進行加密，產(chǎn)生密文 C0′， 并將產(chǎn)生的密文 C0′與密文 C1進行 “異或”操作，產(chǎn)生明文P1，對明文 P1進行加密操作，將產(chǎn)生的密文與密文 C2進行“異或”操作，產(chǎn)生明文P2，對明文P2進行加密操作，將產(chǎn)生的密文與C3進行“異或”操作，產(chǎn)生明文P3，依此方式進行運算，直到產(chǎn)生所有的明文P=P1P2P3…Pn。解密規(guī)則公式表示如下：

由于加密前的明文進行過重組，所以解密完成后同樣要對產(chǎn)生的明文進行重組工作。如果產(chǎn)生的明文分組后存在加密前明文重組時所補得的特殊字符，要將其去除后再進行重組。其重組過程就是加密前明文重組的逆過程。

3 X_IDEA加密性能分析

(1)IDEA算法弱密鑰問題得到有效解決

在IDEA算法中，根據(jù)128 bit的密鑰就可以得出表1，且參考文獻[2]和參考文獻[3]都證明了其弱密鑰的存在。X_IDEA算法通過密鑰生成算法IDEA_KEY生成832 bit子密鑰，子密鑰的生成過程無法找出固定的分析方法，因為密鑰的移位及補位操作都與初始密鑰KEY的長度和具體的值有關，無法進行分析。由此可見，算法IDEA_KEY產(chǎn)生的832 bit子密鑰沒有固定的位置生成表1，從而使IDEA算法的弱密鑰問題得到有效地解決。

X_IDEA算法沒有改變IDEA算法的加密原理，而是在用戶密鑰與子密鑰的生成上給予了加強。用戶可以隨意輸入密鑰，通過該算法可以生成較強的子密鑰；同時也可以滿足對密鑰強度要求較高的用戶，做到密鑰空間為 832 bit(而不是128 bit)，因而安全性不會低于標準的IDEA算法。

(2)密文的明文依賴性有所提高

在X_IDEA算法中，明文加密前先要進行重組，先后要進行兩次明文分組，最后得到一個個64 bit的明文塊。首個加密的明文塊是通過隨機數(shù)發(fā)生器確定的，并且在X_IDEA算法的加密過程中前一數(shù)據(jù)塊加密后得到的密文還將數(shù)據(jù)參與后一數(shù)據(jù)塊的加密。這樣，加密后的密文的長度會加長。同時，如果明文發(fā)生了改變，除了會改變同部分、同組數(shù)據(jù)加密后的結果外，也會導致不同組、不同部分數(shù)據(jù)的加密結果發(fā)生改變，從而增加了數(shù)據(jù)的依賴性，使密文與明文的統(tǒng)計特性之間的關系更加復雜。

(3)抗攻擊能力較IDEA算法更強

算法設計者已證明IDEA算法在加密循環(huán)過程中的第4次循環(huán)之后不再受差分密碼分析的影響，因而目前也尚未出現(xiàn)對IDEA算法較為有效的分析方法。所以，對IDEA的攻擊到目前為止仍只能采用強攻擊方式。

對稱密鑰密碼體制要求算法是公開的，其安全性依賴于密鑰的安全性，密鑰長度應足夠長，以防止窮舉式搜索方法的攻擊[4]。密鑰長度為1時攻擊次數(shù)為 21，密鑰長度為2時攻擊次數(shù)為22，所以算法的抗攻擊能力隨密鑰的長度加大而增強。X_IDEA算法的密鑰長度實際可達 832 bit，則它的攻擊次數(shù)為 2832，而 IDEA標準算法的攻擊次數(shù)為2128次。

(4)安全性有所提高

由于分組密碼可以作為序列密碼使用，X_IDEA算法的加密過程中，加密的首個數(shù)據(jù)塊以及各明文塊都充當了加密密鑰，根據(jù)X_IDEA算法的加密方程，在X_IDEA算法中，一次一密亂碼本是由加密明文提供的，密鑰是C0和 P1P2P3……Pi序列的函數(shù)具有很強的隨機性；而“異或”運算是非線性算法，而且在整個加密過程中相當于嵌套了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.GOVAERTSR.VANDEWALLE J.Weak keys for IDEA.Crypto， 1993：224-231.

[4]SCHNEIER B.應用密碼學[M].吳世忠譯.北京：機械工業(yè)出版社，2000.