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

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

(上海電機學院 電子信息學院, 上海 201306)

?

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

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

(上海電機學院 電子信息學院, 上海 201306)

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

關鍵詞計算機安全; 密碼學; 分組密碼; 輕量級

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

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

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

(1) 一個網站系統的數據庫用戶ID在數據表中是用32bit整型數字來表示的，網站系統希望在用戶訪問的統一資源定位符(Uniform Resource Locator, URL)中標明這些ID，但同時不想讓其他用戶知道這些ID的數量。因此就使用一個32bit分組長度的加密算法對這些ID進行加密，然后將加密后的URL發給用戶，使得用戶無法查看ID的數量。同時，當用戶使用相應的URL訪問網站時，系統會進行相應的解密，并調出相應的用戶ID。

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

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

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

原始的IDEA算法的上層結構并不具有理論意義上的偽隨機性，故文獻[8]中對IDEA算法的結構進行了微小的改動，添加了一個正交置換，從而使其具有理論意義上的偽隨機性，而且將該結構稱為Lai-Massey結構。Lai-Massey結構被證明經過3輪后具有偽隨機性，4輪后具有強偽隨機性。

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

1BeeCipher算法的描述

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

圖中，有3種運算方式：

(2) 字節加法運算，即模28下加法運算，用符號表示；

1.1BeeCipher加密過程

1.2BeeCipher解密過程

1.3BeeCipher的密鑰調度過程

密鑰調度將64bit的主密鑰分為8個ByteK1，K2，…，K8。BeeCipher加密時一共需要68個Byte的子密鑰，則第一輪子密鑰為

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

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

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

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

2BeeCipher算法的設計原則與安全性

2.1Lai-Massey結構與IDEA結構

BeeCipher算法是基于Lai-Massey結構設計的。Lai-Massey結構與IDEA結構不同，圖2給出了Lai-Massey結構與IDEA結構的對比。

圖2　Lai-Massey結構與IDEA上層結構對比圖Fig.2　Lai-Massey scheme and IDEA high-level

由圖可見，在Lai-Massey結構中，每輪左邊的值都增加了一個正交置換；而IDEA的上層結構只是將左邊數據塊的右半部分與右邊數據塊的左邊部分進行了對稱交換。

對于Lai-Massey結構，Vaudenay等[6]已經證明了以下定理。

定理1在輪函數F為獨立隨機函數時，3輪Lai-Massey結構構成一個偽隨機置換，4輪Lai-Massey結構構成一個強偽隨機置換。

對于如圖2(b)所示的IDEA上層結構，由于采用了以下的攻擊方法，故無論迭代多少輪都無法達到偽隨機性。

攻擊對于一輪IDEA上層結構，若輸入為

輸出為

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

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

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

BeeCipher對IDEA算法做了相應修改，在 IDEA 算法的基礎上增加了正交置換，并在理論上證明BeeCipher的結構具有強偽隨機性，且其同時具有IDEA算法的在不同群上運算的強混淆性，因此BeeCipher的安全性要強于32bit版本的IDEA算法。

2.2安全性分析

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

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

對于線性分析，由于BeeCipher采用了群上的不兼容運算，其非線性度非常高；文獻[10]中證實了MA結構，也就是圖1中輪函數中最中間的結構是具有完美的混淆性，因此，BeeCipher對線性分析具有很強的抵抗能力。

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

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

3BeeCipher算法的實現效率

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

由表可見，KATAN32與KATANTA32算法的軟件實現速度很慢，這主要是因為它們是硬件平臺實現的算法；BeeCipher算法的軟件實現速度較Skip32算法快了3倍多，較AES128算法快了25倍多；雖然較美國國家安全局(NSA)最新設計的SPECK32和SIMON32算法慢了約40%，但SIMON32和SPECK32算法正受到大量攻擊，且公眾對NSA不夠信任，其安全性受到很大威脅。由于BeeCipher算法所有的運算都是字節運算，且硬件實現也很方便，故認為BeeCipher在32bit長度分組密碼中是很有競爭力的候選算法。

表1　不同算法的特征及運行耗時對比

4結語

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

參考文獻

[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].電子與信息學報，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.

文獻標識碼A

中圖分類號TP 309.7

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

作者簡介：羅宜元(1986-)，男，講師，博士，主要研究方向為密碼學，E-mail： luoyy@sdju.edu.cn

基金項目：國家自然科學基金項目資助(61402280)；上海電機學院重點學科資助(13XKJ01)；上海市大學生創新活動計劃項目資助(A157011501201062)

收稿日期：2015 - 07 - 27