基于非平衡Feistel結(jié)構(gòu)的加密算法

甘攀攀

摘 要：對經(jīng)典的二維Henon映射的混沌和密碼學(xué)特性進(jìn)行了詳細(xì)的分析，并與傳統(tǒng)密碼學(xué)中廣泛使用的Feistel結(jié)構(gòu)進(jìn)行了比較研究.在此基礎(chǔ)上，提出一種新的不平衡的Feistel結(jié)構(gòu)，并設(shè)計出一種基于該結(jié)構(gòu)和Henon映射的混沌加密算法。

關(guān)鍵詞：Feistel結(jié)構(gòu);加密算法

1.Feistel結(jié)構(gòu)概述

在傳統(tǒng)的對稱密碼學(xué)中，許多分組密碼都采用了一種叫做Feistel的結(jié)構(gòu)，如DES、RC5、FEAL、GOST、LOKI等。Feistel結(jié)構(gòu)把任何函數(shù)都轉(zhuǎn)化為一種轉(zhuǎn)換，是一種典型的迭代結(jié)構(gòu)，也是一種乘積形式的密碼變換.它能夠充分實現(xiàn)擴散與混亂，構(gòu)成強度很高的密碼系統(tǒng)。用數(shù)學(xué)式來表達(dá)，其第i輪的加密變換為：

其中，+表示按位異或，F(xiàn)是輪函數(shù)，Ki是第i輪的子密鑰，式（1）所描述的是左右長度相同的“平衡Feistel結(jié)構(gòu)”，在加密時，算法將長度為2n比特的明文分組m分為2個長為n比特的部分Lo和R，即nz=Lo Ro，每輪只對Ro進(jìn)行加密，如DES就是采用的這種結(jié)構(gòu)，考慮加密過程中的擴展置換，DES中需同時處理的長度是48 bit。采用的是左右長度不同的“非平衡Feistel結(jié)構(gòu)”，分組長度同樣為64 bit，但需同時處理的長度卻是64 bit.大家知道明文分組長度越大，敵手破譯的難度也越大，但計算機能夠處理的字的長度卻是有限的，又迫使分組的長度不能太長，可見，F(xiàn)eistel結(jié)構(gòu)是影響分組密碼算法中分組長度的一個重要因素，制約著分組密碼算法的安全性和運行速度，因此，在實踐中總是通過仔細(xì)設(shè)計Feistel結(jié)構(gòu)，使同時處理的字的長度較小，而分組長度卻較大。筆者這里設(shè)計出一種不平衡的Feistel結(jié)構(gòu)，實現(xiàn)對較大的明文分組進(jìn)行加密。

2.混沌系統(tǒng)及其特性分析

人類對混沌現(xiàn)象的認(rèn)識，是非線性科學(xué)最重要的成就之一。經(jīng)過比較深入的研究，人們發(fā)現(xiàn)一個混沌動力學(xué)系統(tǒng)的演化具有對初值高度敏感性、偽隨機的軌道具有不可預(yù)測性、在信息傳輸過程中呈現(xiàn)連續(xù)寬帶功率譜的特點.這些特性與密碼學(xué)中對輪函數(shù)、偽隨機序列發(fā)生器、長周期密鑰等的要求非常近似，也正是由于二者有如此多的相似之處，近十年來，混沌動力學(xué)系統(tǒng)在通信、密碼學(xué)中的應(yīng)用才引起了人們廣泛的注意，已發(fā)展成為一個非?；钴S的研究領(lǐng)域。將混沌理論中非常經(jīng)典的Henon映射作為加密變換的輪函數(shù)，主要是基于2個方面的原因：一是理論上對其混沌行為的研究比較深入，二是它具有很好的密碼學(xué)特性一。

關(guān)于混沌特性，在非線性研究領(lǐng)域，對Henon映射的混沌特性的研究比較深入，對Henon映射：

它是一個二維的非線性混沌系統(tǒng)，具有很多優(yōu)良特性。

3.基于Henon映射的Feistel結(jié)構(gòu)設(shè)計

在Henon映射中，隱含了密碼學(xué)中應(yīng)用非常廣泛的Feistel結(jié)構(gòu)。通過比較式（1）和式（2），發(fā)現(xiàn)離散形式的Henon映射具有與Feistel結(jié)構(gòu)非常相似的結(jié)構(gòu)。

為便于Feistel結(jié)構(gòu)的設(shè)計及軟件實現(xiàn)，將Henon映射寫為：

由此，筆者設(shè)計加密變換的Feistel結(jié)構(gòu)如下圖。

4.加密算法設(shè)計

加密算法中采取如下的分組密碼模式：設(shè)B0為長為64位的分組，xi，o，xi，1，…，xi，7為一個分組Bi的8個字節(jié)，即Bi=xi，o，xi，1，…，xi，7。加密變換過程為對明文分組Bo進(jìn)行r輪的相同變換，即：

（3）

其中，i=1，2，…，rk=1，2，…，8，f0=zi，o，X8=XO，第i輪的子密鑰zi=zi，o，zi，1，…，zi，7控制第f輪的加密變換fo，fi，…Z是加密的輪函數(shù)，其形式為：

其中fo =zi，f1=f（xo，x1，z1），j=2，3，…，7，f：M→M，M={0，1，...，255}是從混沌映射導(dǎo)出的一個一對一映射函數(shù)，此算法中的混沌系統(tǒng)采用Henon映射。每輪的輸出分組Bi=xi，o，x1，1，…，xi，7為下一輪的輸入（最后一輪除外），因此，第r輪的輸出Br=xr，o，xr，1，…，xr，7即為明文Bo的64位密文分組。

解密過程將加密變換逆運算，從密文Br，計算出明文Bo，注意在運用密鑰時要與加密變換所使用的次序相反，解密變換為：

其中，i=1，2，…，r，k=1，2，...，8，f0=zi，o，X8=XO，f0，f1…f7是加密的輪函數(shù)。

5.加密算法安全分析

從理論上講，一個安全的算法肯定具有“隨機性增加”和“計算上不可預(yù)測”兩個特性有關(guān)對“隨機性增加”和“計算上不可預(yù)測”的嚴(yán)格定義超出了筆者所討論的范圍，且基于混沌的密碼算法的安全性指標(biāo)目前還沒有建立，有待進(jìn)一步研究。對所設(shè)計的算法而言，通過分析S-盒的非線性性和差分均勻性來證明。

從實踐上講，只有能夠抵抗目前所有的密碼分析攻擊的算法才能說是安全的。從目前來看，差分密碼分析和線性密碼分析是最基本和最有效的兩種攻擊方式，估計一個分組密碼抵抗差分密碼分析和線性密碼分析的能力也就成為評估這個密碼算法安全強度的重要指標(biāo)。

5.1 S-盒的差分均勻性

差分分析的過程就是尋找、暴露非線性變換中輪函數(shù)的差分不一致性，因此，差分密碼分析最困難的步驟就是搜索r-1輪中具有最大或接近最大概率的差分。這樣，就可以通過計算一個密碼算法的差分逼近概率來評估其輪函數(shù)的差分一致性，定義差分逼近概率DPf為：

其中，X為滿足要求的所有輸入值的集合，2n為輸入集合的元素個數(shù)事實上，DPf就是當(dāng)輸入差分為Ax，輸出差分為Ay時的最大概率，減少Dpf的值就增加了差分密碼分析的難度。根據(jù)計算，筆者所提算法的Dpf14/256 -2-4.4。

5.2 抗差分和線性攻擊的評估

對分組密碼抵抗差分密碼分析和線性密碼分析的能力評估，現(xiàn)有的做法主要有下面3種：（1）給出加密算法的最大差分概率平均值和線性概率平均值的一個上界;（2）給出密碼算法的最大差分特征和線性逼近概率;（3）給出加密算法的最大差分特征和線性逼近概率的一個上界。

證明中采取在計算輪函數(shù)的差分逼近概率和線性逼近概率的基礎(chǔ)上，通過估計差分活動輪函數(shù)的最小個數(shù)，給出算法的差分特征和線性逼近概率的一個上界，即通過估計算法式（3）的差分活動輪函數(shù)的最小個數(shù)，給出8輪差分密碼分析的最大差分特征概率的上界。

參考文獻(xiàn)

[1]斯托林斯（WilliamStallings），密碼編碼學(xué)與網(wǎng)絡(luò)安全，電子工業(yè)出版社，2011.1.1.

[2]Bruce Schneier[美]，《應(yīng)用密碼學(xué)–協(xié)議算法與C源程序》，機械工業(yè)出版社，2000.1.1.

[3]結(jié)城浩[日]，《圖解密碼技術(shù)》，人民郵電出版社，2016.7.1.