基于FPGA的eStream序列密碼實(shí)現(xiàn)分析*

徐遠(yuǎn)澤，張文科，尹一樺，羅　影

(衛(wèi)士通信息產(chǎn)業(yè)股份有限公司，四川 成都 610041)

?

基于FPGA的eStream序列密碼實(shí)現(xiàn)分析*

徐遠(yuǎn)澤，張文科，尹一樺，羅影

(衛(wèi)士通信息產(chǎn)業(yè)股份有限公司，四川 成都 610041)

修回日期：2015-06-16Received date:2015-03-11；Revised date：2015-06-16

摘要：歐洲eStream序列密碼計(jì)劃推動(dòng)了現(xiàn)代序列密碼的發(fā)展，序列密碼研究開(kāi)始關(guān)注于易于硬件實(shí)現(xiàn)的輕量化序列密碼設(shè)計(jì)。主要研究了eStream序列密碼推薦的三種面向硬件實(shí)現(xiàn)的密碼算法：Grain-128、MICKEY2.0和TRIVIUM。首先分別介紹了三種算法的基本原理，然后針對(duì)每種算法進(jìn)行FPGA下的電路結(jié)構(gòu)設(shè)計(jì)，最后采用Verilog HDL語(yǔ)言，在Xilinx Virtex-5 FPGA平臺(tái)上進(jìn)行了綜合實(shí)現(xiàn)。實(shí)現(xiàn)結(jié)果表明，在三種算法中，TRIVIUM算法占用FPGA邏輯資源最少，其吞吐量最高，而MICKEY2.0算法占用FPGA邏輯資源最多，同時(shí)吞吐量最低。

關(guān)鍵詞：eStream序列密碼; Grain-128；MICKEY2.0；TRIVIUM；FPGA

0引言

eStream序列密碼計(jì)劃最終選出了7個(gè)相對(duì)較強(qiáng)的密碼算法，其中偏向硬件實(shí)現(xiàn)的算法包括Grain、MICKEY和TRIVIUM三種算法，這幾種算法均是基于非線性反饋移位寄存器的設(shè)計(jì)，在一定程度上提高了系統(tǒng)的非線性，增強(qiáng)了系統(tǒng)的安全性。然而，隨著計(jì)算機(jī)和密碼分析技術(shù)的發(fā)展，這些算法的安全性逐漸受到威脅，因此算法設(shè)計(jì)者對(duì)算法又進(jìn)行了改進(jìn)。目前eStream序列密碼推薦使用面向硬件實(shí)現(xiàn)的算法為Grain-128、MICKEY2.0和TRIVIUM[1-3]。從eStream序列密碼計(jì)劃的發(fā)展過(guò)程可以看出，現(xiàn)代序列密碼設(shè)計(jì)越來(lái)越關(guān)注資源受限環(huán)境下的使用，特別是在現(xiàn)代移動(dòng)通信和RFID等應(yīng)用領(lǐng)域，對(duì)算法實(shí)現(xiàn)的硬件資源損耗有著苛刻的限制，輕量化的序列密碼設(shè)計(jì)成為了當(dāng)前序列密碼研究的一大主流方向。

文中主要研究了Grain-128、MICKEY2.0和TRIVIUM這三種序列密碼算法在FPGA上的實(shí)現(xiàn)，并進(jìn)一步分析其在FPGA上的硬件資源消耗、速度性能等情況，以求在同一平臺(tái)下評(píng)估三種算法的硬件性能優(yōu)劣。

1算法簡(jiǎn)介

1.1Grain-128算法

Grain算法是由Martin Hell、Thomas Jonhan-sson和Willi Meier共同設(shè)計(jì)的，存在兩個(gè)版本，版本一所用密鑰長(zhǎng)度為80比特，因易遭受“時(shí)間-存儲(chǔ)-數(shù)據(jù)”攻擊，因此算法的設(shè)計(jì)者設(shè)計(jì)了另一個(gè)版本—Grain-128[4-7]。Grain-128算法密鑰Key為128比特，初始向量IV為96比特，主要由一個(gè)128比特的線性移位寄存器S、一個(gè)128比特的非線性移位寄存器b以及一個(gè)非線性濾波函數(shù)h(x)組成，算法的整體結(jié)構(gòu)如圖1所示。

圖1　Grain-128算法結(jié)構(gòu)

Grain-128算法流程可分為初始化階段和密鑰輸出階段。在初始化階段，首先需要對(duì)寄存器進(jìn)行初始化填充，填充過(guò)程如下：將96比特初始向量IV填入寄存器s的低96位，寄存器S的高32位填充1；將128比特密鑰填入寄存器b。此外，整個(gè)算法不產(chǎn)生密鑰輸出，而是將密鑰輸出結(jié)果直接反饋回寄存器s和寄存器b(如圖1虛線所示)，如此運(yùn)行256個(gè)時(shí)鐘周期。在密鑰輸出階段，算法的輸出不再反饋回寄存器，而是直接作為密鑰輸出。

在Grain-128算法中，線性反饋移位寄存器s的反饋函數(shù)多項(xiàng)式為：

f(x)=1+x32+x47+x58+x90+x121+x128

(1)

其對(duì)應(yīng)的遞推公式為：

si+128=si+si+7+si+38+si+70+si+81+si+96

(2)

非線性移位寄存器b的反饋函數(shù)多項(xiàng)式為：

g(x)=1+x32+x37+x72+x102+x128+x44x60+x61x125+

x63x67+x69x101+x80x88+x80x88+x110x111x115x117

(3)

其對(duì)應(yīng)的遞推公式為：

bi+128=si+bi+bi+26+bi+56+bi+91+bi+96+

bi+3bi+67+bi+11bi+13+bi+17bi+18+

bi+27bi+59+bi+40bi+48+bi+61bi+65+

bi+68bi+84

(4)

非線性濾波函數(shù)為：

h(x)=x0x1+x2x3+x4x5+x6x7+x0x4x8

(5)

其對(duì)應(yīng)的遞推公式為：

c=bi+12si+8+si+13si+20+bi+95si+42+si+60si+79+bi+12bi+95si+95

(6)

最后，密鑰輸出的遞推公式為：

z=bi+2+bi+15+bi+36+bi+45+bi+64+bi+73+bi+89+c+si+93

(7)

1.2MICKEY 2.0算法

MICKEY 2.0是由Steve Babbage和Matthew Dodd在其原版MICKEY算法基礎(chǔ)上改進(jìn)而來(lái)的，設(shè)計(jì)者通過(guò)增加內(nèi)部寄存器數(shù)量和改變寄存器反饋抽頭的位置進(jìn)一步提升了算法的安全性[8]。MICK-EY 2.0算法密鑰Key長(zhǎng)度為80比特，初始向量IV為0-80比特的可變長(zhǎng)度，主要由一個(gè)100比特的線性移位寄存器R和一個(gè)100比特的非線性移位寄存器S組成，并且寄存器的反饋采用的是一種非規(guī)則鐘控反饋型式，算法結(jié)構(gòu)如圖2所示。

圖2　MICKEY 2.0算法結(jié)構(gòu)

MICKEY 2.0算法流程分為初始化階段和密鑰輸出階段。在初始化階段，首先，寄存器R與寄存器S填充全0，然后，按如下流程進(jìn)行初始化處理：

(1)加載IV

for (0≤i≤IVLENGTH-1){

CLOCK_KG(R,S,MIXING=TRUE,

INPUT_BIT=ivi)}

(8)

(2)加載K

for (0≤i≤79){

CLOCK_KG(R,S,MIXING=TRUE,

INPUT_BIT=ki)}

(9)

(3)前鐘控

for(0≤i≤99) {

CLOCK_KG(R,S,MIXING=TRUE,

INPUT_BIT=0) }

(10)

(4)密鑰輸出

在密鑰輸出階段，其按以下流程生成密鑰輸出：

for (0≤i≤L-1) {

zi=r0⊕s0;

CLOCK_KG(R,S,MIXING=FALSE,

INPUT_BIT=0) }

(11)

其中CLOCK_KG(R,S,MIXING,INPUT_BIT)為鐘控函數(shù)，其定義如下：{

CONTROL_BIT_R=s34⊕r67

CONTROL_BIT_S=s37⊕r33

If(MIXING=TRUE)

INPUT_BIT_R=INPUT_BIT⊕s50

elseINPUT_BIT_R=INPUT_BIT;

INPUT_BIT_S=INPUT_BIT

CLOCK_R(R,INPUT_BIT_R,CONTROL_BIT_R)CLOCK_S(S,INPUT_BIT_S,CONTROL_BIT_S)

}

(12)

上述表達(dá)式中，CLOCK_R(*)和CLOCK_S(*)分別代表寄存器R和寄存器S的鐘控變化。兩個(gè)寄存器的鐘控變化定義如下：

FEEDBACK_BIT=r99⊕INPUT_BIT_R

for(0≤i≤99){

if(i∈RTAPS)

if(CONTROL_BIT_R=1){

}

(13)

其中RTAPS為定義的抽頭位置。

FEEDBACK_BIT=s99⊕INPUT_BIT_S;

for(1≤i≤98){

ifCONTROL_BIT_S=0{

for0≤i≤99，

if(CONTROL_BIT_S=1){

for(0≤i≤99){

}

(14)

其中COMP0,COMP1,FB0,FB1為四個(gè)預(yù)先定義好的序列。

1.3TRIVIUM算法

TRIVIUM算法是由密碼學(xué)家ChristopheDeCanniere和BartPreneel在2005年向eStream計(jì)劃提交的一種面向硬件的同步序列密碼，設(shè)計(jì)目的在于構(gòu)建一種安全性、速度以及硬件復(fù)雜度均衡的密碼算法[9]。TRIVIUM算法密鑰Key長(zhǎng)度為80比特，初始向量IV為80比特，主要由一個(gè)288比特長(zhǎng)的非線性移位寄存器和一些抽頭反饋組成，其算法結(jié)構(gòu)如圖3所示。

圖3　TRIVIUM算法結(jié)構(gòu)

TRIVIUM算法流程分為初始化階段和密鑰輸出階段。在初始化階段，首先按如下方式加載密鑰和初始向量：{

(s1,s2,…,s93)←(K1,…,K80,0,…,0)

(s94,s95,…,s177)←(IV1,…,IV80,0,…,0)

(s178,s279,…,s288)←(0,…,0,1,1,1)}

(15)

然后按以下流程開(kāi)始初始化處理：

for(1≤i≤1152){

t1←s66+s91s92+s93+s171

t2←s162+s175s176+s177+s264

t3←s243+s286s287+s288+s69

(s1,s2,…,s93)←(t3,s1,…,s92)

(s94,s95,…,s177)←(t1,s94,…,s176)

(s178,s279,…,s288)←(t2,s178,…,s287)}

(16)

而在密鑰輸出階段，算法流程如下：

for(1≤i≤N) {

t1←s66+s93

t2←s162+s177

t3←s243+s288

zi←t1+t2+t3

t1←t1+s91s92+s171

t2←t2+s175s176+s264

t3←t3+s286s287+s69

(s1,s2,…,s93)←(t3,s1,…,s92)

(s94,s95,…,s177)←(t1,s94,…,s176)

(s178,s279,…,s288)←(t2,s178,…,s287)} (17)

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

2.1Grain-128電路結(jié)構(gòu)設(shè)計(jì)

Grain-128算法的電路控制是通過(guò)一個(gè)狀態(tài)機(jī)來(lái)實(shí)現(xiàn)的。如圖4所示，整個(gè)算法電路由三個(gè)狀態(tài)組成：S0、S1和S2，其中S0為算法電路初始化中的密鑰和初始向量加載階段，S1為電路初始化運(yùn)行階段，S2為密鑰產(chǎn)生輸出階段。當(dāng)電路復(fù)位以后的第一個(gè)時(shí)鐘周期，電路進(jìn)入S0狀態(tài)，開(kāi)始從外部讀入128比特密鑰和96比特初始向量并存儲(chǔ)于相應(yīng)的寄存器中；然后控制電路產(chǎn)生初始化控制信號(hào)，電路進(jìn)入S1狀態(tài)，計(jì)數(shù)器Counter開(kāi)始初始化控制計(jì)數(shù)；當(dāng)計(jì)數(shù)器計(jì)數(shù)周期達(dá)到256個(gè)時(shí)鐘周期時(shí)，電路進(jìn)入S2狀態(tài)，開(kāi)始產(chǎn)生密鑰輸出。

圖4　Grain-128狀態(tài)轉(zhuǎn)移圖

在Grain-128電路設(shè)計(jì)中，除了兩個(gè)128比特的移位寄存器外，還需要一個(gè)8比特的寄存器用于電路初始化計(jì)數(shù)控制。同時(shí)兩個(gè)反饋函數(shù)f(x)、g(x)，以及濾波函數(shù)h(x)均通過(guò)組合邏輯實(shí)現(xiàn)，因此，每個(gè)時(shí)鐘周期，整個(gè)電路寄存器狀態(tài)更新一次，在密鑰輸出階段，每個(gè)時(shí)鐘周期產(chǎn)生1比特的密鑰輸出。

2.2MICKEY2.0電路結(jié)構(gòu)設(shè)計(jì)

MICKEY2.0算法的電路控制同樣使用一個(gè)狀態(tài)機(jī)來(lái)實(shí)現(xiàn)。如圖5所示，MICKEY2.0的電路主要由四個(gè)狀態(tài)組成：S0、S1、S2和S3，其中S0為算法電路初始化過(guò)程中的初始向量加載階段，S1為初始化過(guò)程中的密鑰加載階段，S2為初始化過(guò)程中的前鐘控運(yùn)行階段，S3為密鑰產(chǎn)生輸出階段。

當(dāng)電路復(fù)位后的第一個(gè)時(shí)鐘，電路進(jìn)入S0狀態(tài)，開(kāi)始從外部讀入初始向量進(jìn)行初始化處理，同時(shí)計(jì)數(shù)器Counter開(kāi)始計(jì)數(shù)；當(dāng)Counter計(jì)數(shù)周期達(dá)到初始化向量長(zhǎng)度時(shí)，控制電路產(chǎn)生密鑰加載控制信號(hào)，電路進(jìn)入S1狀態(tài)，開(kāi)始從外表讀入密鑰進(jìn)行初始化處理，此時(shí)，Counter計(jì)數(shù)器開(kāi)始重新計(jì)數(shù)；當(dāng)Counter計(jì)數(shù)器數(shù)值達(dá)到79時(shí)，電路進(jìn)入S2狀態(tài)，開(kāi)始前鐘控運(yùn)行處理，此時(shí)，counter計(jì)數(shù)器又重新開(kāi)始計(jì)數(shù)；當(dāng)counter計(jì)數(shù)器計(jì)滿100個(gè)時(shí)鐘周期時(shí)，電路進(jìn)入S3狀態(tài)，開(kāi)始產(chǎn)生密鑰輸出。

圖5　MICKEY2.0狀態(tài)轉(zhuǎn)移圖

在MICKEY2.0電路設(shè)計(jì)中，需要讀入初始化向量的輸入長(zhǎng)度，以控制初始化向量的讀入控制。MICKEY2.0算法電路除了需要兩個(gè)100比特的移位寄存器外，還需要一個(gè)7比特的計(jì)數(shù)器用于電路初始化過(guò)程中各個(gè)階段的計(jì)數(shù)控制。電路中，兩個(gè)移位寄存器的狀態(tài)更新均在一個(gè)時(shí)鐘周期內(nèi)完成，因此，寄存器中間反饋運(yùn)算均是由組合電路組成。同樣，在密鑰輸出階段每個(gè)時(shí)鐘周期產(chǎn)生1比特的密鑰輸出。

2.3TRIVIUM電路結(jié)構(gòu)設(shè)計(jì)

TRIVIUM的控制電路由一個(gè)三態(tài)的狀態(tài)機(jī)控制。如圖6所示，整個(gè)算法電路狀態(tài)分為S0、S1和S2，其中S0為算法電路初始化過(guò)程中的密鑰和初始向量加載階段，S1為電路初始化運(yùn)行階段，S3為密鑰產(chǎn)生輸出階段。當(dāng)電路復(fù)位后的第一個(gè)時(shí)鐘周期，電路進(jìn)入S0狀態(tài)，開(kāi)始從外部讀入80比特密鑰和80比特初始向量并存儲(chǔ)于對(duì)應(yīng)的寄存器中；然后控制電路產(chǎn)生初始化控制信號(hào)，電路進(jìn)入S1狀態(tài)，計(jì)數(shù)器Counter開(kāi)始初始化控制計(jì)數(shù)；當(dāng)計(jì)數(shù)器計(jì)數(shù)周期達(dá)到1 152個(gè)時(shí)鐘時(shí)，電路進(jìn)入S2狀態(tài)，開(kāi)始產(chǎn)生密鑰輸出。

圖6TRVIUM狀態(tài)轉(zhuǎn)移圖

在TRIVIUM電路設(shè)計(jì)中，使用了1個(gè)288比特的移位寄存器，此外還需要一個(gè)11比特的計(jì)數(shù)器用于電路初始化階段的計(jì)數(shù)控制。算法電路中，寄存器之間的反饋運(yùn)算均是由組合電路組成，因此，移位寄存器的狀態(tài)更新均在一個(gè)時(shí)鐘周期內(nèi)完成。同樣，在電路密鑰輸出階段每個(gè)時(shí)鐘周期產(chǎn)生1比特的密鑰輸出。

3實(shí)現(xiàn)比較

利用XilinxISE9.2i軟件，選用xilinx公司型號(hào)為xc5vlx110t的FPGA作為統(tǒng)一平臺(tái)庫(kù)，對(duì)Grain-128算法、MICKEY2.0算法、TRIVIUM算法的VerilogHDL代碼進(jìn)行綜合分析，以評(píng)估算法在FPGA上的實(shí)現(xiàn)情況。實(shí)現(xiàn)結(jié)果如表1所示。

表1　三種算法FPGA的實(shí)現(xiàn)結(jié)果

從表1可以看出，三種序列密碼算法在FPGA實(shí)現(xiàn)上TRIVIUM算法雖然FFs數(shù)最多，但其總體占用硬件資源最少，為94Slices，并且具有最大的吞吐量；而MICKEY2.0具有最大的硬件復(fù)雜度，因此其硬件資源占用最多，同時(shí)，其吞吐量也最小。總體來(lái)說(shuō)，在FPGA實(shí)現(xiàn)上，三種序列密碼算法硬件性能優(yōu)劣排序?yàn)門(mén)RIVIUM優(yōu)于Grain-128、Grain-128優(yōu)于MICKEY2.0。

4結(jié)語(yǔ)

歐洲eStream序列密碼計(jì)劃在一定程度上推動(dòng)了現(xiàn)代序列密碼的發(fā)展，使得現(xiàn)代序列密碼更加關(guān)注于非線性和低資源損耗、高吞吐量等方面的研究。當(dāng)前eStream序列密碼所推薦使用的面向硬件實(shí)現(xiàn)的Grain-128、MICKEY2.0以及TRIVIUM具有輕量化特點(diǎn)。通過(guò)研究三種密碼算法在FPGA上的實(shí)現(xiàn)，進(jìn)一步分析三種算法的硬件性能，從而在同一FPGA平臺(tái)層面評(píng)估出三種序列密碼的優(yōu)劣性。

參考文獻(xiàn)：

[1]劉依依.eSTREAM和流密碼分析現(xiàn)狀[J].信息安全和通信保密，2009(12)：47-49.

LIU Yi-yi. eSTREAM and the Present State of Stream-Cipher Analysis[J]. Information Security and Communication Privacy, 2009(12)：47-49.

[2]The eSTREAM Portfolio in2012[EB/OL].http://www.ecrypt.eu.org/stream/portfolio.pdf.

[3]趙偉.HC-128 的內(nèi)部狀態(tài)表[J].通信技術(shù)，2014(11)：1328-1332.

ZHAO Wei.Inner State Table of HC-128[J]. Communications Technology,2014(11):1328-1332.

[4]宋海欣.eSTREAM序列密碼算法的分析[D].北京:中國(guó)科學(xué)院研究生院，2012.

SONG Hai-xin. Cryptanalysis of the Stream Ciphers of eSTREAM Project[D]. Beijing：University of Chinese Academy of Sciences,2012.

[5]楊昌盛，于敬超，嚴(yán)迎建.Grain-128同步流密碼的選擇初始向量相關(guān)性能量攻擊[J].2014,34(5):1318-1321.

YANG Chang-sheng, YU Jing-chao, YAN Ying-jian. Chosen Initial Vector Correlation Power Attack on Synchronous Stream Cipher Grain-128[J]. 2014, 34(5): 1318-1321.

[6]趙蓮清，陳元?jiǎng)?，段曉?基于Grain-128a算法的RFID安全機(jī)制[J].電子技術(shù)應(yīng)用，2013，39(4)：126-129.

ZHAO Lian-qing, CHEN Yuan-xun, DUAN Xiao-meng. RFID Security Mechanism based on Grain-128a[J].Application of Electronic Technique，2013，39(4)：126-129.

[7]Martin Hell, Thomas Johansson, and Alexander Maximov. A Stream Cipher Proposal: Grain-128[EB/OL].http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain128_p3.pdf.

[8]Steve Babbage, Matthew Dodd. The Stream Cipher MICKEY 2.0. ECRYPT Stream Cipher Project Report[EB/OL].http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey_p3.pdf.

[9]Christophe De Canniereand Bart Preneel. TriviumSpecifications [EB/OL].http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf.

徐遠(yuǎn)澤(1985—)，男，碩士，工程師，主要研究方向?yàn)槊艽a研究與信息安全技術(shù)；

張文科(1973—)，男，碩士，高級(jí)工程師，主要研究方向?yàn)槊艽a理論和密碼實(shí)現(xiàn)；

尹一樺(1979—)，男，碩士，工程師，主要研究方向?yàn)樾畔踩c技術(shù)；

羅影(1980—)，男，碩士，工程師，主要研究方向?yàn)槊艽a算法研究與實(shí)現(xiàn)。

Implementation of FPGA-based eStream Sequential Cipher

XU Yuan-ze，ZHANG Wen-ke，YIN Yi-hua，LUO Ying

(Westone Information Industry Company Limited, Chengdu Sichuan 610041, China)

Abstract：The project of Europe eStream sequential cipher promotes the development of modern stream cipher, and the researchers of sequential cipher turn their attention to the design of light-weight stream cipher liable to hardware implementation. Grain-128, MICKEY2.0 and TRIVIUM, these three stream ciphers oriented to hardware implementation recommended by eStream sequential cipher are studied. Firstly, the basic principles of these three stream ciphers are presented, then their circuit configurations designed on FPGA,and finally,their comprehensive implementations are done on Xilinx Virtex-5 of FPGA platform with Verilog HDL language.Implementation result indicates that，of the three algorithms，TRIVIUM occupies the least FPGA logic resources while enjoying the highest throughput,and MICKEY2.0 occupies the highest logic resources while enjoying the lowest throughput.

Key words：eStream sequential cipher；Grain-128；MICKEY2.0；TRIVIUM；FPGA

作者簡(jiǎn)介：

中圖分類號(hào)：TN918.4

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1002-0802(2015)07-0850-05

收稿日期：*2015-03-11；

doi:10.3969/j.issn.1002-0802.2015.07.020