基于FPGA的eStream序列密碼實現分析*

徐遠澤，張文科，尹一樺，羅　影

(衛士通信息產業股份有限公司，四川 成都 610041)

?

基于FPGA的eStream序列密碼實現分析*

徐遠澤，張文科，尹一樺，羅影

(衛士通信息產業股份有限公司，四川 成都 610041)

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

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

關鍵詞：eStream序列密碼; Grain-128；MICKEY2.0；TRIVIUM；FPGA

0引言

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

文中主要研究了Grain-128、MICKEY2.0和TRIVIUM這三種序列密碼算法在FPGA上的實現，并進一步分析其在FPGA上的硬件資源消耗、速度性能等情況，以求在同一平臺下評估三種算法的硬件性能優劣。

1算法簡介

1.1Grain-128算法

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

圖1　Grain-128算法結構

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

在Grain-128算法中，線性反饋移位寄存器s的反饋函數多項式為：

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

(1)

其對應的遞推公式為：

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

(2)

非線性移位寄存器b的反饋函數多項式為：

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

x63x67+x69x101+x80x88+x80x88+x110x111x115x117

(3)

其對應的遞推公式為：

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)

非線性濾波函數為：

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

(5)

其對應的遞推公式為：

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算法基礎上改進而來的，設計者通過增加內部寄存器數量和改變寄存器反饋抽頭的位置進一步提升了算法的安全性[8]。MICK-EY 2.0算法密鑰Key長度為80比特，初始向量IV為0-80比特的可變長度，主要由一個100比特的線性移位寄存器R和一個100比特的非線性移位寄存器S組成，并且寄存器的反饋采用的是一種非規則鐘控反饋型式，算法結構如圖2所示。

圖2　MICKEY 2.0算法結構

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

(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)為鐘控函數，其定義如下：{

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)

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

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為四個預先定義好的序列。

1.3TRIVIUM算法

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

圖3　TRIVIUM算法結構

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

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

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

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

(15)

然后按以下流程開始初始化處理：

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設計

2.1Grain-128電路結構設計

Grain-128算法的電路控制是通過一個狀態機來實現的。如圖4所示，整個算法電路由三個狀態組成：S0、S1和S2，其中S0為算法電路初始化中的密鑰和初始向量加載階段，S1為電路初始化運行階段，S2為密鑰產生輸出階段。當電路復位以后的第一個時鐘周期，電路進入S0狀態，開始從外部讀入128比特密鑰和96比特初始向量并存儲于相應的寄存器中；然后控制電路產生初始化控制信號，電路進入S1狀態，計數器Counter開始初始化控制計數；當計數器計數周期達到256個時鐘周期時，電路進入S2狀態，開始產生密鑰輸出。

圖4　Grain-128狀態轉移圖

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

2.2MICKEY2.0電路結構設計

MICKEY2.0算法的電路控制同樣使用一個狀態機來實現。如圖5所示，MICKEY2.0的電路主要由四個狀態組成：S0、S1、S2和S3，其中S0為算法電路初始化過程中的初始向量加載階段，S1為初始化過程中的密鑰加載階段，S2為初始化過程中的前鐘控運行階段，S3為密鑰產生輸出階段。

當電路復位后的第一個時鐘，電路進入S0狀態，開始從外部讀入初始向量進行初始化處理，同時計數器Counter開始計數；當Counter計數周期達到初始化向量長度時，控制電路產生密鑰加載控制信號，電路進入S1狀態，開始從外表讀入密鑰進行初始化處理，此時，Counter計數器開始重新計數；當Counter計數器數值達到79時，電路進入S2狀態，開始前鐘控運行處理，此時，counter計數器又重新開始計數；當counter計數器計滿100個時鐘周期時，電路進入S3狀態，開始產生密鑰輸出。

圖5　MICKEY2.0狀態轉移圖

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

2.3TRIVIUM電路結構設計

TRIVIUM的控制電路由一個三態的狀態機控制。如圖6所示，整個算法電路狀態分為S0、S1和S2，其中S0為算法電路初始化過程中的密鑰和初始向量加載階段，S1為電路初始化運行階段，S3為密鑰產生輸出階段。當電路復位后的第一個時鐘周期，電路進入S0狀態，開始從外部讀入80比特密鑰和80比特初始向量并存儲于對應的寄存器中；然后控制電路產生初始化控制信號，電路進入S1狀態，計數器Counter開始初始化控制計數；當計數器計數周期達到1 152個時鐘時，電路進入S2狀態，開始產生密鑰輸出。

圖6TRVIUM狀態轉移圖

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

3實現比較

利用XilinxISE9.2i軟件，選用xilinx公司型號為xc5vlx110t的FPGA作為統一平臺庫，對Grain-128算法、MICKEY2.0算法、TRIVIUM算法的VerilogHDL代碼進行綜合分析，以評估算法在FPGA上的實現情況。實現結果如表1所示。

表1　三種算法FPGA的實現結果

從表1可以看出，三種序列密碼算法在FPGA實現上TRIVIUM算法雖然FFs數最多，但其總體占用硬件資源最少，為94Slices，并且具有最大的吞吐量；而MICKEY2.0具有最大的硬件復雜度，因此其硬件資源占用最多，同時，其吞吐量也最小。總體來說，在FPGA實現上，三種序列密碼算法硬件性能優劣排序為TRIVIUM優于Grain-128、Grain-128優于MICKEY2.0。

4結語

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

參考文獻：

[1]劉依依.eSTREAM和流密碼分析現狀[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 的內部狀態表[J].通信技術，2014(11)：1328-1332.

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

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

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

[5]楊昌盛，于敬超，嚴迎建.Grain-128同步流密碼的選擇初始向量相關性能量攻擊[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]趙蓮清，陳元勛，段曉萌.基于Grain-128a算法的RFID安全機制[J].電子技術應用，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.

徐遠澤(1985—)，男，碩士，工程師，主要研究方向為密碼研究與信息安全技術；

張文科(1973—)，男，碩士，高級工程師，主要研究方向為密碼理論和密碼實現；

尹一樺(1979—)，男，碩士，工程師，主要研究方向為信息安全與技術；

羅影(1980—)，男，碩士，工程師，主要研究方向為密碼算法研究與實現。

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

作者簡介：

中圖分類號：TN918.4

文獻標志碼：A

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

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

doi:10.3969/j.issn.1002-0802.2015.07.020