基于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