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

甘攀攀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

加密算法中采取如下的分組密碼模式：設(shè)B0為長(zhǎng)為64位的分組，xi，o，xi，1，…，xi，7為一個(gè)分組Bi的8個(gè)字節(jié)，即Bi=xi，o，xi，1，…，xi，7。加密變換過(guò)程為對(duì)明文分組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)出的一個(gè)一對(duì)一映射函數(shù)，此算法中的混沌系統(tǒng)采用Henon映射。每輪的輸出分組Bi=xi，o，x1，1，…，xi，7為下一輪的輸入（最后一輪除外），因此，第r輪的輸出Br=xr，o，xr，1，…，xr，7即為明文Bo的64位密文分組。

解密過(guò)程將加密變換逆運(yùn)算，從密文Br，計(jì)算出明文Bo，注意在運(yùn)用密鑰時(shí)要與加密變換所使用的次序相反，解密變換為：

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

5.加密算法安全分析

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

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

5.1 S-盒的差分均勻性

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

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

5.2 抗差分和線性攻擊的評(píng)估

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

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

參考文獻(xiàn)

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

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

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