張 毅，肖四友，張文祥

(浙江萬(wàn)里學(xué)院 智能控制研究所，浙江 寧波 315100)

1 IDEA算法簡(jiǎn)述

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

IDEA也被認(rèn)為是目前世界上最好最安全的分組密碼算法，且對(duì)計(jì)算機(jī)功能要求不高。IDEA的128 bit密鑰長(zhǎng)度，相對(duì)較長(zhǎng)，但加密強(qiáng)度高。在窮舉攻擊的情況下，IDEA需要經(jīng)過2128次加密才能恢復(fù)出密鑰，假設(shè)芯片每秒能檢測(cè)100億個(gè)密鑰，需要10年。IEDA被認(rèn)為僅循環(huán)4次即可抵制差分密碼分析，對(duì)IDEA算法也不起作用，隨機(jī)選擇密鑰基本沒有危險(xiǎn)，故其安全性較高。IDEA算法基于一些可靠的基礎(chǔ)理論，軟件實(shí)現(xiàn)的IDEA比DES快2倍。

IDEA算法是由八個(gè)相似圈外加一個(gè)輸出變換組成的循環(huán)密碼。圈函數(shù)的模塊是模216+1乘法。模216加法和按位XOR。IDEA有一個(gè)128 bit的總密鑰和以64 bit為塊的加密數(shù)據(jù)。

除密鑰調(diào)度之外，IDEA解密過程與加密過程相同。加密圈密鑰是總密鑰的16 bit子串，如表1所示。解密圈密鑰能從加密圈密鑰中導(dǎo)出。

1.1 IDEA明文長(zhǎng)度

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

表1 IDEA算法密鑰生成表

1.2 IDEA的弱密鑰

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

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

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

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

2 X_IDEA算法設(shè)計(jì)

2.1 明文處理

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

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

圖1 明文重組

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

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

2.2 密鑰生成

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

IDEA_KEY算法：

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

2.3 加密過程

加密過程是對(duì)重組后的明文進(jìn)行分組處理，每組64 bit。在所有重組好的明文分組中由隨機(jī)數(shù)產(chǎn)生器隨機(jī)產(chǎn)生數(shù)據(jù) X，作為加密的初始數(shù)據(jù)，X為 64 bit，運(yùn)用IDEA數(shù)據(jù)加密算法對(duì)數(shù)據(jù)X以及除最后一個(gè)明文分組之外的所有明文分組進(jìn)行加密，產(chǎn)生密文C0和密文分組 D1，D2，D3…Dn-1，對(duì)密文 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)行加密，也未對(duì)IDEA算法的加密原理及加密過程進(jìn)行改變，所以X_IDEA算法的混淆性與擴(kuò)散性肯定不低于IDEA算法。實(shí)際上，在X_IDEA算法的加密過程中，首個(gè)隨機(jī)加密數(shù)據(jù)分組的引入以及前一密文與后一明文“異或”再產(chǎn)生密文的方式進(jìn)一步增強(qiáng)了算法的混淆性。

2.4 解密過程

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

由于加密前的明文進(jìn)行過重組，所以解密完成后同樣要對(duì)產(chǎn)生的明文進(jìn)行重組工作。如果產(chǎn)生的明文分組后存在加密前明文重組時(shí)所補(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子密鑰，子密鑰的生成過程無(wú)法找出固定的分析方法，因?yàn)槊荑€的移位及補(bǔ)位操作都與初始密鑰KEY的長(zhǎng)度和具體的值有關(guān)，無(wú)法進(jìn)行分析。由此可見，算法IDEA_KEY產(chǎn)生的832 bit子密鑰沒有固定的位置生成表1，從而使IDEA算法的弱密鑰問題得到有效地解決。

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

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

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

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

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

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

(4)安全性有所提高

由于分組密碼可以作為序列密碼使用，X_IDEA算法的加密過程中，加密的首個(gè)數(shù)據(jù)塊以及各明文塊都充當(dāng)了加密密鑰，根據(jù)X_IDEA算法的加密方程，在X_IDEA算法中，一次一密亂碼本是由加密明文提供的，密鑰是C0和 P1P2P3……Pi序列的函數(shù)具有很強(qiáng)的隨機(jī)性；而“異或”運(yùn)算是非線性算法，而且在整個(gè)加密過程中相當(dāng)于嵌套了IDEA算法，因而其安全性高于IDEA。

X_IDEA算法在密鑰的選擇上給用戶帶來(lái)更大的靈活性，增強(qiáng)了算法的適應(yīng)性，同時(shí)也消除了IDEA算法中的弱密鑰，抗攻擊能力進(jìn)一步增強(qiáng)。加密前的明文重組以及初始向量的設(shè)置可以使用相同的明文加密成不同的密文，密文的明文依賴性更強(qiáng)。而且X_IDEA算法并沒有改變IDEA算法的加密原理，只是在加密過程中嵌套了IDEA算法，所以計(jì)算量也不會(huì)增加。

參考文獻(xiàn)

[1]吳偉彬，黃元石.IDEA算法的改進(jìn)及其應(yīng)用[J].福州大學(xué)學(xué)報(bào)，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.應(yīng)用密碼學(xué)[M].吳世忠譯.北京：機(jī)械工業(yè)出版社，2000.