BeeCipher： 一種32bit分組長度的輕量級(jí)密碼算法

羅宜元，　林智偉，　陳煒家，　徐祿豐

(上海電機(jī)學(xué)院 電子信息學(xué)院, 上海 201306)

?

BeeCipher： 一種32bit分組長度的輕量級(jí)密碼算法

羅宜元，林智偉，陳煒家，徐祿豐

(上海電機(jī)學(xué)院 電子信息學(xué)院, 上海 201306)

摘要設(shè)計(jì)了一個(gè)32bit分組長度、64bit密鑰長度的分組密碼BeeCipher。該算法基于國際數(shù)據(jù)加密算法(IDEA)和Lai-Massey結(jié)構(gòu)，對(duì)IDEA算法的32bit版本的輪函數(shù)進(jìn)行了改進(jìn)，添加了正交置換，使得其具有可證明安全性；修改了密鑰調(diào)度過程，使得目前已有的對(duì)IDEA算法的攻擊都對(duì)BeeCipher無效。BeeCipher的軟件和硬件實(shí)現(xiàn)都很簡(jiǎn)單，其速度較目前已有的大多數(shù) 32bit 分組長度算法要快很多，是32bit分組長度輕量級(jí)分組密碼中有力的候選算法。

關(guān)鍵詞計(jì)算機(jī)安全; 密碼學(xué); 分組密碼; 輕量級(jí)

BeeCipher: A 32 bit Block Length Lightweight Block Cipher

LUOYiyuan，LINZhiwei，CHENWeijia，XULufeng

(School of Electronics Information Engineering, Shanghai Dianji University，Shanghai 201306, China)

AbstractThis paper proposes a 32 bit block length, 64 bit key length block cipher BeeCipher. It is based on the structure of IDEA and Lai-Massey. The round function of IDEA-32 version is revised, and an orthomorphism added to the round function to achieve provable security. The key schedule is also updated such that all known attacks on IDEA cannot be applied to BeeCipher. Software and hardware implementation of BeeCipher is simple, and faster than most of other 32 bit block ciphers. BeeCipher can be a candidate for 32 bit block ciphers in lightweight applications.

Keywordscomputer security; cryptology; block cipher; lightweight

隨著信息技術(shù)的發(fā)展，信息的安全性問題愈來愈顯得突出，保證信息安全的一個(gè)重要技術(shù)就是密碼學(xué)。密碼學(xué)在信息安全技術(shù)中扮演著基礎(chǔ)的角色，是攻擊者最難攻破的模塊。而分組密碼又是密碼學(xué)中最常用的算法，是信息安全中的主力，通常被稱為信息安全中的驛馬。目前，學(xué)術(shù)界對(duì)分組密碼的設(shè)計(jì)和研究已經(jīng)相當(dāng)成熟，每年都有很多新的加密算法推出。由于物聯(lián)網(wǎng)等相關(guān)技術(shù)的進(jìn)步，人們發(fā)現(xiàn)傳統(tǒng)的加密算法已經(jīng)在資源受限的環(huán)境中無法得到廣泛應(yīng)用，因此，對(duì)資源消耗較少、實(shí)現(xiàn)效率較高的輕量級(jí)密碼算法的設(shè)計(jì)已經(jīng)成了學(xué)術(shù)界關(guān)注的熱點(diǎn)。

對(duì)于輕量級(jí)密碼算法的設(shè)計(jì)，目前常用的算法的長度都是64bit長度的，如PRESENT[1]、LED[2]、PRINTCipher[3]、Twine[5]，LBlock等[6-7]。而在某些特殊應(yīng)用下，用戶會(huì)需要32bit分組長度的分組密碼，如：

(1) 一個(gè)網(wǎng)站系統(tǒng)的數(shù)據(jù)庫用戶ID在數(shù)據(jù)表中是用32bit整型數(shù)字來表示的，網(wǎng)站系統(tǒng)希望在用戶訪問的統(tǒng)一資源定位符(Uniform Resource Locator, URL)中標(biāo)明這些ID，但同時(shí)不想讓其他用戶知道這些ID的數(shù)量。因此就使用一個(gè)32bit分組長度的加密算法對(duì)這些ID進(jìn)行加密，然后將加密后的URL發(fā)給用戶，使得用戶無法查看ID的數(shù)量。同時(shí)，當(dāng)用戶使用相應(yīng)的URL訪問網(wǎng)站時(shí)，系統(tǒng)會(huì)進(jìn)行相應(yīng)的解密，并調(diào)出相應(yīng)的用戶ID。

(2) 需要將一組按序排列的32bit整數(shù)加密成另外一組無序排列的32bit的整數(shù)，同時(shí)具備一定的安全性。

對(duì)于64bit的密鑰長度，窮舉攻擊需要264次加密過程，對(duì)于非政府或非軍事組織而言，還是很難破譯的。因此，目前64bit密鑰的算法對(duì)于抵抗個(gè)人和小型組織的攻擊還是具有一定的安全性。

目前，已有的輕量級(jí)算法主要采用Feistel結(jié)構(gòu)及其擴(kuò)展和代換置換網(wǎng)絡(luò)(Substitution Permutation Network, SPN)結(jié)構(gòu)，如PRESENT采用SPN結(jié)構(gòu)，LBlock主要采用的是Feistel擴(kuò)展結(jié)構(gòu)等。除Feistel和SPN結(jié)構(gòu)外，還有一類比較成熟的分組密碼設(shè)計(jì)結(jié)構(gòu)，即Lai-Massey結(jié)構(gòu)[8]，以國際數(shù)據(jù)加密算法(International Data Encryption Algorithm, IDEA)、FOX算法為代表[9-10]。其中，IDEA在經(jīng)過20多年的密碼分析后，提出了Biclique攻擊方法[11]。該方法將攻擊復(fù)雜度降低到窮舉攻擊復(fù)雜度的1/4，且對(duì)于Biclique攻擊，AES算法也不能幸免。因此，IDEA算法還是一個(gè)很安全的算法。其安全性建立在3個(gè)不相合的代數(shù)群運(yùn)算上。其主要運(yùn)算是對(duì)16bit的數(shù)據(jù)塊進(jìn)行異或、模216加法、模216+1乘法運(yùn)算。由于這3個(gè)運(yùn)算各自在不同的代數(shù)群上，結(jié)合律、分配律均不適用，從而使得IDEA算法的混淆速度非常快，在經(jīng)過4.5輪迭代后，就能抵抗差分分析攻擊。IDEA算法的缺陷是其密鑰調(diào)度過于簡(jiǎn)化，只有簡(jiǎn)單的線性移位，故目前所有針對(duì)IDEA的攻擊都是利用其密鑰調(diào)度的缺陷。

原始的IDEA算法的上層結(jié)構(gòu)并不具有理論意義上的偽隨機(jī)性，故文獻(xiàn)[8]中對(duì)IDEA算法的結(jié)構(gòu)進(jìn)行了微小的改動(dòng)，添加了一個(gè)正交置換，從而使其具有理論意義上的偽隨機(jī)性，而且將該結(jié)構(gòu)稱為Lai-Massey結(jié)構(gòu)。Lai-Massey結(jié)構(gòu)被證明經(jīng)過3輪后具有偽隨機(jī)性，4輪后具有強(qiáng)偽隨機(jī)性。

本文基于IDEA和Lai-Massey結(jié)構(gòu)設(shè)計(jì)了一種32bit分組長度、64bit密鑰長度的分組密碼BeeCipher。該算法不僅對(duì)IDEA算法的32bit版本，且對(duì)其輪函數(shù)進(jìn)行了修改，添加了正交置換，并修改了密鑰調(diào)度過程，從而使得目前已有的針對(duì)IDEA算法的攻擊均對(duì)BeeCipher無效。BeeCipher的軟件實(shí)現(xiàn)也非常簡(jiǎn)單，其速度較目前已有的大多數(shù)32bit分組長度算法要快很多。

1BeeCipher算法的描述

圖1　BeeCipher加密過程Fig.1　Encryption of BeeCipher

圖中，有3種運(yùn)算方式：

(2) 字節(jié)加法運(yùn)算，即模28下加法運(yùn)算，用符號(hào)表示；

1.1BeeCipher加密過程

1.2BeeCipher解密過程

1.3BeeCipher的密鑰調(diào)度過程

密鑰調(diào)度將64bit的主密鑰分為8個(gè)ByteK1，K2，…，K8。BeeCipher加密時(shí)一共需要68個(gè)Byte的子密鑰，則第一輪子密鑰為

(1) 令第r+1輪子密鑰中

其中，Primes是小于整數(shù)256的54個(gè)素?cái)?shù)集合，即Primes[54]={2，3，5，7，…，251}，由i=0開始，以后每運(yùn)行一次乘法操作后將i遞增，即i=i+1；

(3) 重復(fù)步驟(1)和(2)直到i=8，然后將r+1輪子密鑰循環(huán)左移13bit。

(4) 一直到生成了68個(gè)子密鑰為止。

2BeeCipher算法的設(shè)計(jì)原則與安全性

2.1Lai-Massey結(jié)構(gòu)與IDEA結(jié)構(gòu)

BeeCipher算法是基于Lai-Massey結(jié)構(gòu)設(shè)計(jì)的。Lai-Massey結(jié)構(gòu)與IDEA結(jié)構(gòu)不同，圖2給出了Lai-Massey結(jié)構(gòu)與IDEA結(jié)構(gòu)的對(duì)比。

圖2　Lai-Massey結(jié)構(gòu)與IDEA上層結(jié)構(gòu)對(duì)比圖Fig.2　Lai-Massey scheme and IDEA high-level

由圖可見，在Lai-Massey結(jié)構(gòu)中，每輪左邊的值都增加了一個(gè)正交置換；而IDEA的上層結(jié)構(gòu)只是將左邊數(shù)據(jù)塊的右半部分與右邊數(shù)據(jù)塊的左邊部分進(jìn)行了對(duì)稱交換。

對(duì)于Lai-Massey結(jié)構(gòu)，Vaudenay等[6]已經(jīng)證明了以下定理。

定理1在輪函數(shù)F為獨(dú)立隨機(jī)函數(shù)時(shí)，3輪Lai-Massey結(jié)構(gòu)構(gòu)成一個(gè)偽隨機(jī)置換，4輪Lai-Massey結(jié)構(gòu)構(gòu)成一個(gè)強(qiáng)偽隨機(jī)置換。

對(duì)于如圖2(b)所示的IDEA上層結(jié)構(gòu)，由于采用了以下的攻擊方法，故無論迭代多少輪都無法達(dá)到偽隨機(jī)性。

攻擊對(duì)于一輪IDEA上層結(jié)構(gòu)，若輸入為

輸出為

若F的輸出為(f1‖f2)，則有

故可見無論經(jīng)過多少輪迭代，攻擊者都可以使用上面的攻擊方法將其與一個(gè)偽隨機(jī)置換區(qū)分開來。

值得注意的是，由于IDEA算法使用了不相容群上的運(yùn)算，具有很強(qiáng)的混淆性，因此此處的攻擊并不表示IDEA具體算法不能達(dá)到偽隨機(jī)性，而是指其上層結(jié)構(gòu)無法達(dá)到偽隨機(jī)性。若IDEA算法輪函數(shù)的輸入與密鑰的運(yùn)算都在一個(gè)群上進(jìn)行攻擊，如將IDEA輪函數(shù)中最上面的明文與密鑰的運(yùn)算改為異或運(yùn)算，則IDEA算法將無法達(dá)到偽隨機(jī)性。

BeeCipher對(duì)IDEA算法做了相應(yīng)修改，在 IDEA 算法的基礎(chǔ)上增加了正交置換，并在理論上證明BeeCipher的結(jié)構(gòu)具有強(qiáng)偽隨機(jī)性，且其同時(shí)具有IDEA算法的在不同群上運(yùn)算的強(qiáng)混淆性，因此BeeCipher的安全性要強(qiáng)于32bit版本的IDEA算法。

2.2安全性分析

2.2.1弱密鑰分析目前對(duì)IDEA的所有攻擊都利用了IDEA密鑰調(diào)度過于簡(jiǎn)單的弱點(diǎn)。在BeeCipher的密鑰調(diào)度中，使用了類似非線性移位寄存器的方法，每一個(gè)新生成的字節(jié)密鑰都由之前的密鑰經(jīng)過不同群上的模乘和異或運(yùn)算得出。由于在28+1上的模乘與GF(28)上的異或運(yùn)算不兼容，使得兩者混合起來具有很高的非線性，故BeeCipher不存在類似于IDEA的弱密鑰。

2.2.2差分分析與線性分析BeeCipher是IDEA的32bit版本的改進(jìn)版。文獻(xiàn)[10]中使用了馬爾科夫鏈理論證明了8bit和16bit版本的 IDEA 算法在經(jīng)過4輪后就能抵抗差分分析，并猜想32bit與64bit也是如此。就目前已有的對(duì) IDEA 的攻擊結(jié)果來看，IDEA對(duì)差分分析的抵抗能力的確很好。

對(duì)于線性分析，由于BeeCipher采用了群上的不兼容運(yùn)算，其非線性度非常高；文獻(xiàn)[10]中證實(shí)了MA結(jié)構(gòu)，也就是圖1中輪函數(shù)中最中間的結(jié)構(gòu)是具有完美的混淆性，因此，BeeCipher對(duì)線性分析具有很強(qiáng)的抵抗能力。

2.2.3Biclique攻擊Biclique攻擊是目前最成功的攻擊，能夠成功地應(yīng)用在IDEA和AES上，這是由于利用的IDEA和AES算法的密鑰調(diào)度的混淆速度都不是很快，而BeeCipher的密鑰調(diào)度混淆速度卻相當(dāng)快，使得Biclique攻擊無法奏效。

綜上分析可知，BeeCipher較32bit的IDEA算法更安全，且能達(dá)到最優(yōu)的安全性，即對(duì)BeeCipher的最好攻擊是窮舉攻擊。64bit的安全性能夠滿足對(duì)手是非政府組織和非軍事組織，安全性需求不太高，但又具有一定安全性，特別的，其可以應(yīng)用在超市、購物商場(chǎng)上。

3BeeCipher算法的實(shí)現(xiàn)效率

由于BeeCipher所有的運(yùn)算都是字節(jié)運(yùn)算，故無論是軟件實(shí)現(xiàn)，還是硬件實(shí)現(xiàn)，都很簡(jiǎn)單。本文將其實(shí)現(xiàn)效率與其他算法進(jìn)行了比較。為了實(shí)現(xiàn)算法的公平對(duì)比，故在同一個(gè)運(yùn)算平臺(tái)上實(shí)現(xiàn)，所用平臺(tái)為HP個(gè)人PC，CPU為Intel i5-5200U 2.20GHz。表2給出了運(yùn)行加密算法100萬次所耗時(shí)間對(duì)比，同時(shí)給出了各算法的特征。其中，除AES128算法外，其他均為32bit分組長度的算法；Skip32算法由Greg Rose[12]基于Skipjack設(shè)計(jì)，KATAN算法由Canniere等[13]設(shè)計(jì)，SIMON和SPECK算法等由美國國家安全局[14]設(shè)計(jì)。

由表可見，KATAN32與KATANTA32算法的軟件實(shí)現(xiàn)速度很慢，這主要是因?yàn)樗鼈兪怯布脚_(tái)實(shí)現(xiàn)的算法；BeeCipher算法的軟件實(shí)現(xiàn)速度較Skip32算法快了3倍多，較AES128算法快了25倍多；雖然較美國國家安全局(NSA)最新設(shè)計(jì)的SPECK32和SIMON32算法慢了約40%，但SIMON32和SPECK32算法正受到大量攻擊，且公眾對(duì)NSA不夠信任，其安全性受到很大威脅。由于BeeCipher算法所有的運(yùn)算都是字節(jié)運(yùn)算，且硬件實(shí)現(xiàn)也很方便，故認(rèn)為BeeCipher在32bit長度分組密碼中是很有競(jìng)爭(zhēng)力的候選算法。

表1　不同算法的特征及運(yùn)行耗時(shí)對(duì)比

4結(jié)語

本文主要設(shè)計(jì)了一個(gè)32bit分組長度，64bit密鑰長度的分組密碼算法BeeCipher，并且對(duì)BeeCipher的安全性做出了分析。BeeCipher是對(duì)32bit IDEA算法版本的改進(jìn)，在輪函數(shù)中增加了正交置換，從而使得結(jié)構(gòu)具有可證明安全性；同時(shí)，采用了IDEA算法中良好的乘法、加法混淆模塊，增加了算法混淆性，并且修改了密鑰生成算法，避免了線性密鑰調(diào)度過程，從而使得最新的Biclique攻擊對(duì)BeeCipher不成立。在軟件實(shí)現(xiàn)上，BeeCipher算法比其他大多數(shù)32bit分組算法要快很多，只比美國國家安全局最新設(shè)計(jì)的SIMON和SPECK慢了40%左右。在硬件實(shí)現(xiàn)上，BeeCipher也非常容易?？紤]到美國國家安全局設(shè)計(jì)的算法目前還未被驗(yàn)證具有良好的安全性，因此，BeeCipher是一個(gè)有力32bit分組長度的候選分組密碼算法。

參考文獻(xiàn)

[1]BOGDANOV A，KNUDSEN L R，LEANDER G，et al.PRESENT：An ultra-lightweight block cipher[C]∥Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems.Berlin，Heidelberg：Springer-Verlag，2007： 450-466.

[2]GUO Jian，PEYRIN T，POSCHMANN A，et al.The LED Block Cipher[C]∥Cryptographic Hardware and Embedded Systems-CHES 2011：Proceedings of the 13th International Workshop.Berlin，Heidelberg：Springer-Verlag，2011： 326-341.

[3]KNUDSEN LR，LEANDER G，POSCHMANN A，et al.PRINTcipher：A block cipher for IC-Printing[C]∥Proceedings of the 12th International Conference on Cryptographic Hardware and Embedded Systems.Berlin，Heidelberg： Springer-Verlag，2010： 16-32.

[4]LEANDER G，PAAR C，POSCHMACNN A，et al.New lightweight DES variants[C]∥Fast Software Encryption：Proceedings of the 14th International Workshop.Berlin Heidelberg: Springer，2007： 196-210.

[5]SUZAKI T，MINEMATSU K，MORIOKA S，et al.TWINE： A lightweight block cipher for multiple platforms[C]∥Proceedings of SAC 2012.Berlin，Heidelberg： Springer-Verlag，2012： 339-354.

[6]WU Wenling，ZHANG Lei.LBlock： A Lightweight block cipher[C]∥Proceedings of the 9th International Conference.Berlin，Heidelberg：Springer，2011： 327-344.

[7]郭建勝，羅偉，張磊，等.LBlock碼的不可能差分密碼性能分析[J].電子與信息學(xué)報(bào)，2013，35(6)： 1516-1519.

[8]VAUDENAY S.On the Lai-Massey scheme[C]∥International Conference on the Theory and Application of Cryptology and Information Security.Berlin，Heidelberg：Springer，1999： 8-19.

[9]JUNOD P，VAUDENAY S.FOX：A new family of block ciphers[C]∥11th International Workshop，Heidelberg：Springer Berlin，2004： 114-129.

[10]LAI Xuejia，MASSEY J L，MURPHY S.Markov ciphers and differential cryptanalysis[C]∥Advances in Cryptology-EUROCRYPT’91：Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques.Berlin，Heidelberg：Springer，1991： 17-38.

[11]BOGDANOV A，KHOVRATOVICH D，RECHBERGER C.Biclique cryptanalysis of the full AES[C]∥Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security.Berlin，Heidelberg：Springer，2011： 344-371.

[12]ROSE G.Skip32：A 32-bit block cipher based on Skipjack[EB/OL].[2015-08-12].http：∥www.qualcomm.com.au/PublicationsDocs/skip32.c.

[13]CANNIERE C，DUNKELMAN O，KNEZEVIC M.KATAN and KTANTAN-A family of small and efficient hardware-oriented block ciphers[C]∥Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems.Berlin，Heidelberg：Springer-Verlag，2009，272-288.

[14]BEAULIEU R，SHORS D，SMITH J，et al.The SIMON and SPECK families of lightweight block ciphers[EB/OL].(2013-06-19)[2014-05-18].http：∥eprint.iacr.org/2013/404.pdf.

[15]DAEMEN J，RIJMEN V.The Design of Rijndael：AES-The advanced encryption standard[M].Berlin，Heidelberg：Springer-Verlag，2002： 25.

文獻(xiàn)標(biāo)識(shí)碼A

中圖分類號(hào)TP 309.7

文章編號(hào)2095 - 0020(2016)01 -0038 - 05

作者簡(jiǎn)介：羅宜元(1986-)，男，講師，博士，主要研究方向?yàn)槊艽a學(xué)，E-mail： luoyy@sdju.edu.cn

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目資助(61402280)；上海電機(jī)學(xué)院重點(diǎn)學(xué)科資助(13XKJ01)；上海市大學(xué)生創(chuàng)新活動(dòng)計(jì)劃項(xiàng)目資助(A157011501201062)

收稿日期：2015 - 07 - 27