面向序列密码的高效能分层式比特抽取网络设计研究

金 羽 戴紫彬 李 伟,2 马 超

1(信息工程大学电子技术学院 河南 郑州 450000) 2(复旦大学专用集成电路与系统国家实验室 上海 201203)

面向序列密码的高效能分层式比特抽取网络设计研究

金 羽1戴紫彬1李 伟1,2马 超1

1(信息工程大学电子技术学院 河南 郑州 450000)2(复旦大学专用集成电路与系统国家实验室 上海 201203)

针对序列密码算法中抽取操作的可重构硬件实现资源消耗大的问题，通过研究序列密码中非线性布尔函数的变量需求，基于Inverse Butterfly网络提出一种高效能分层式比特抽取网络-HHBN(High-efficiency hierarchical bit-extraction network)。与其他网络进行对比，该网络可一次抽取出含有重复变量的多组数据，且不仅其实际性能与灵活度优于其他大多网络，面积消耗也远小于同灵活度的Crossbar网络。在Synopsys公司的Design Compiler进行了综合，实验结果表明与Crossbar网络在不同位宽实现相比，其面积减少约20%～50%，这就减少了实现不同序列密码算法抽取操作的可重构硬件资源消耗，从而提高了效能。

序列密码 比特抽取 高效能 分层式 Inverse Butterfly

0 引 言

序列密码具有实现简单、加密速度快、密文传输中有限的错误扩散性等优点，因此在各种应用中越来越广泛[1]。序列密码算法主要由移位寄存器、反馈函数运算单元和密钥流生成函数运算单元组成，其中反馈函数用于计算反馈移位寄存器的更新值，密钥流生成函数用于计算最终的密钥流[2]。

无论算法中反馈函数的计算和密钥流的生成，都需要通过反馈抽头将反馈移位寄存器的状态位并行地抽取出来参与后续运算，而反馈抽头根据算法的不同，不仅位置灵活多变且个数也各不相同[3]。如何将参与运算的一个或几个反馈移位寄存器的若干状态位高效、并行地抽取出来完成后续运算，成为制约序列密码算法运算性能的关键因素之一。

而若使用灵活度高的Crossbar全互联网络[4]实现抽取操作，势必会造成巨大的资源开销。文献[5]使用Inverse Butterfly网络的抽取操作虽减少了所需资源但抽取结果顺序固定且比特位的抽取不能重复，导致在含有重复变量的非线性布尔函数应用时并不够灵活，Omega-flip[6]、Benes[7]与文献[8]也存在同样的问题。针对上述问题，本文通过对序列密码抽取需求进行分析，在保证灵活度下，基于Inverse Butterfly网络设计了高效率低资源的比特抽取网络HHBN，对节约序列密码算法硬件资源并提高效率具有重要现实意义。

1 序列密码抽取操作需求分析

序列密码算法中对密钥流要求较高，要求其满足相应的密码学特征。一般，安全性能越高，其设计越复杂，在具体实现时越困难。算法中通常采用的方法是由多个线性移位寄存器和一个非线性组合函数即非线性布尔函数组成。因此大多数的序列密码算法中，都包含非线性布尔函数，而其数据来源于移位寄存器数据的抽取，如图1所示。

图1 序列密码算法中的抽取操作与非线性布尔函数

序列密码算法中的非线性反馈函数、前馈函数以及钟控函数的实现都可以归属于非线性布尔函数的实现，具体的实现为任意的多输入布尔函数。本文对序列密码算法中的非线性布尔函数进行了分析，如表1所示[9-11]，分别对非线性布尔函数的数据来源的位宽、变量个数、最高次数进行了总结归纳。

表1 各序列密码算法中非线性布尔函数统计

可以看出，序列密码非线性布尔函数中存在着大量抽取操作，但大多数序列密码的变量个数在32个以内，而通过文献[12]所设计的基于查找表的可重构非线性布尔函数NBF(Non_Line Boolean Function)单元为6变量实现形式，且6个变量均不相同。在所进行运算的变量个数大于6时可以通过多个NBF单元级联实现。所以在进行状态位抽取时，只需将所需数据抽取后，以6个变量为一组分别输入至NBF单元。

2 比特级抽取操作研究

要实现抽取操作，考虑到面积资源消耗的问题，采用Inverse Butterfly网络为基本网络进行设计。图2为一个8 bit位宽的Inverse Butterfly网络，它可以通过改变各级switch开关状态实现不同结点之间的连接，使系统具有自重构能力，从而灵活地完成数据的重新排列[13]。

图2 Inverse Butterfly网络

比特抽取操作即为从给定的控制序列Control中为“1”的控制位对应的输入数据抽取出来并依次排在输出序列的右侧，控制序列为“0”的控制位所对应的数据逆序排在输出序列的左侧。位宽为N的Inverse Butterfly网络，根据控制序列生成控制信息的算法[14]如下：

Input: Control //控制序列

Output: Control_bits //网络的各级控制信息

(1) for (i = 1; i<=N-2; i++)

Sum[i]=Popcnt(Control{i:0})

//Popcnt为统计控制序列Control中[i:0]位的“1”

//个数

(2) RLTR(1k,M)

M= M mod 2i

C=11…1100…00 //K个1与K个零

RLTR_tmp=C <<< k //循环移位

RLTR = RLTR_tmp[2k-1:k]

(3) for (i=1 ; i<=lg(N); i++)

k=2i-1 //第i级的每个子蝶网络的控制序列长度

for (j=1,j<= N/2i-1-1,j=j+2) {

q=j × k - 1

Control_bits(i)= RLTR(1k, Sum[q])

//依次输出第 i 级中每个子蝶网络的控制信息

}

其中，(1)为对控制序列的连加求和，将其从最低位到每一位为止的“1”的个数求出；(2)RLTR单元为左移反填充，可以视为11…1100…00(K个“1”与K个“0”)的左循环移位；通过执行(3)中的循环即可求出Inverse Butterfly网络各级各子蝶网络所需要的控制信息。这样通过上述算法所给出的控制信息即可将所需要的对应比特位数据通过网络抽取出来。

3 分层抽取网络设计技术研究

3.1 分层式抽取网络设计

通过第1节分析可以看出，大多数序列密码算法所需变量在32个以内，单个变量可能会被多个NBF单元使用，而每个NBF单元需要至多6个的变量输入，且这6个变量每个都不相同。

针对算法中非线性布尔函数的结构特点，对于应有的抽取网络应满足如下要求：

(1) 因非线性运算函数表达式差异较大且位宽不同，因此必须能实现多种位宽操作。

(2) 因同一运算因子可能会被多个NBF多次使用，因此必须支持单比特多次重复抽取。

(3) 因抽取位置不固定，必须支持任意位置的抽取。

本文以128 bit位宽的移位寄存器为例，若使用Crossbar网络[4]，即128个128选1数据选择器，虽然可以非常灵活地实现抽取操作，但对于资源的消耗很大。每一位均为128选1选择器，即7级2选1数据选择器组成，每一位就需要127个数据选择器，则128 bit抽取N位就需要数量为127N的2选1数据选择器。且因单个NBF单元所需变量各不相同，但该网络的每一位的输出均可能彼此相同，其硬件资源相对于功能需求而言会形成一种较大的浪费。

若直接使用Inverse Butterfly网络实现抽取操作，虽然资源消耗较小，但其每位数据之间不会相同且输出结果的顺序固定，当使用多个NBF单元且有重复变量时其抽取结果无法直接提供给其进行运算。如图3所示，要抽取出6、5、3、1、0的数据，其抽取结果顺序必定为24765310，在实际使用时就需要使用多个该网络或进行多次抽取才能实现，显然在位宽较大时其灵活度并不适应非线性布尔函数单元具体的需求。而其他类似网络如Benes网络等也存在相同问题。

图3 Inverse Butterfly网络抽取

因此，本文通过研究非线性布尔函数的数据特点，基于Inverse Butterfly网络提出一种高效能分层式比特抽取网络-HHBN，如图4其两层结构主要分为两层：

(1) 第一层从输入128 bit数据中抽取32 bit，包含非线性布尔函数所需的全部变量，且变量之间不重复；

(2) 第二层子网络从第一层抽取的32 bit中分别抽取出6 bit共6Nbit以供NBF单元使用，6 bit数本身不重复，但每个32-6 bit子网络的输入可以重复。

图4 分层式抽取网络

这样对于不同非线性布尔函数时，都可保证一次抽取出所有NBF单元所需要的数据，这就在其灵活度满足需求的前提下，大大减少抽取网络所占用的资源。

3.2 分层式抽取子网络设计

因为使用的Inverse Butterfly子网络仅需完成128-32 bit与32-6 bit操作，为节约资源，可以对其结构进行优化。若以16-3 bit为例，如图5所示，最后一级仅需要3 bit数据输出，则最后一级原本8个switch即16个数据选择器中仅需保留3个数据选择器即可。3个数据选择器需6个数据输入，对应第二级保留6个数据器。16-3 bit的Inverse Butterfly网络需要3+6+12+16=37个数据选择器，而原本16-16 bit的网络需要16×4=64个数据选择器。

图5 简化后的16-3 bit Inverse Butterfly

总结规律得，位宽为m的Inverse Butterfly网络，当仅输出nbit(n

x=m×(log2m-a)+n×2a-1+n×2a-2+…+n×20=

m×(log2m-a)+n×(2a-1)

同理可得，128-32 bit的Inverse Butterfly网络需要128×5+96=736个数据选择器，32-6 bit的Inverse Butterfly需要32×2+42=106个数据选择器。

据上述分析可知，若网络第一层使用的128-32 bit的Inverse Butterfly网络，第二层若使用5个32-6 bit网络，则共使用736+5×106=1 266个数据选择器。数据网络相比于等效的128-30 bit的Crossbar网络使用的127×30=3 810个数据选择器个数减少约67%，而灵活度相应于非线性布尔函数的要求而言并无下降。

4 性能评估

下面将本文设计的网络与其他文献进行对比，位宽均为128-128 bit，因NBF设计原因，本文网络采取位宽相近的128-126 bit，其结果如表2所示。

表2 不同方法的抽取资源占用

表2中第二列为实现所需要的2选1数据选择器数量，第三列为网络的级数，第四列则为是否支持重复的比特位抽取，第五列为抽取出21组含有公共变量的6 bit数据所需要通过网络的次数。可以看出，Omega-flip、Inverse Butterfly、Benes与文献[8]所提出的网络虽面积小但均不支持重复的比特位抽取，在实际运用时需使用多个网络并行放置或单个网络进行多次抽取，这就变相增加了其资源消耗并降低了实际性能。而对比HHBN网络与同样支持重复比特位抽取的Crossbar网络，虽级数增加，但理论面积减小约80%。

为更加客观地评价本文所设计的网络，在Synopsys公司的Design Compiler软件上基于SMIC 65-nm工艺进行了逻辑综合。综合时环境参数设置为：最慢工艺角(ss)、最高温度(125℃)、和最低电压(1.08 V)。采用flatten优化策略，因Crossbar与本文网络灵活度相近，且结构较为简单，这里同时对其进行了编码并综合以进行比较，结果如表3所示。

表3 抽取网络面积、延迟对比

表3中第一行为128-30bit的全置换Crossbar网络，在SIMC 65 nm工艺下的约束为0.96 ns时，其面积为9 496.4 μm2；第二行为本文的HHBN网络，在SMIC 65 nm工艺下其延迟为0.96 ns，面积为7 482.6 μm2。

若将抽取结果位宽扩展至6×21=126 bit，即HHBN第二层使用21个子网络进行抽取，如表3中第三行所示，HHBN网络在128-126 bit情况下，其延迟为1 ns，面积为20 495.5 μm2；表3中第四行为128-126 bit的Crossbar网络在1 ns约束下面积为40 697.2 μm2。如图6所示。

图6 综合后网络面积对比

经上述分析可知，HHBN网络不仅实际实现的效率上强于Omega-flip、Benes等网络，且与Crossbar网络相比面积大大减少，抽取30 bit时实际面积资源消耗减少约20%，抽取126 bit时实际面积减少约50%。虽在延迟上不如Crossbar网络，但因选择器本身延迟较低，对算法整体的影响并不会很大，这就有效减少了抽取网络所占用的资源，提高了抽取网络的效能。

5 结 语

本文通过分析序列密码算法中状态位抽取后进行的非线性布尔函数及非线性布尔函数硬件单元的实际需求，基于Inverse Butterfly网络提出了一种高效能的分层式抽取网络(HHBN)。并针对实际的数据需求对网络中各子网络进行了优化，使其在可以灵活高效地抽取非线性布尔函数所需求的数据的同时，大大减少了抽取操作所需的面积资源，对提高序列密码可重构实现的效率与节约其硬件资源消耗具有重要意义。

[1] Seward B R,Aaron R,Shiffman A.Localized bioimpedance analysis in the evaluation of neuromuscular disease[J].Muscle & Nerve,2002,25(3):390-397.

[2] 陈涛,马超,罗兴国,等.面向序列密码的比特级抽取指令研究与设计[J].信息工程大学学报,2015(1):123-128.

[3] 徐建博,戴紫彬,李伟,等.面向序列密码的抽取与插入单元可重构设计研究[J].电子技术应用,2011,37(7):65-67.

[4] 曲英杰.可重组密码逻辑的设计原理[D].北京:北京科技大学,2003.

[5] Yang X,Lee R B.Fast Subword Permutation Instructions Using Omega and Flip Network Stages[C]//IEEE International Conference on Computer Design:Vlsi in Computers & Processors.IEEE Computer Society,2000:15-22.

[6] Shi Z J.Bit permutation instructions:architecture,implementation,and cryptographic properties[M].Princeton University,2004.

[7] Shan W W,Chen X,Yinchao L U,et al.A Novel Combinatorics-Based Reconfigurable Bit Permutation Network and Its Circuit Implementation[J].Chinese Journal of Electronics,2015,24(3):513-523.

[8] Hilewitz Y,Lee R B.A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations[J].IEEE Transactions on Computers,2009,58(8):1035-1048.

[9] 张玉安,冯登国.欧洲流密码加密标准的竞评[J].信息安全与通信保密,2003(3):38-41.

[10] 刘运毅,覃团发,倪皖荪,等.简评ECRYPT的候选流密码算法(中)[J].信息安全与通信保密,2006(8):26-28.

[11] Robshaw M J B.Stream Ciphers[R].RSA Laboratories Technical Report,1995.

[12] 纪祥君,陈迅,戴紫彬,等.一种改进的非线性布尔函数硬件设计与实现[J].计算机应用与软件,2014,31(7):283-285,302.

[13] Nassimi D,Sahni S.A Self-Routing Benes Network and Parallel Permutation Algorithms[J].IEEE Transactions on Computers,1981,C-30(5):332-340.

[14] 马超,戴紫彬,常忠祥,等.高速可重构插入与抽取单元设计[J].计算机应用与软件,2013,30(10):326-330.

DESIGNANDRESEARCHOFHIGH-EFFICIENCYHIERARCHICALBIT-EXTRACTIONNETWORKFORSTREAMCIPHER

Jin Yu1Dai Zibin1Li Wei1,2Ma Chao1

1(InstitutionofElectronicTechnology,InformationEngineeringUniversity,Zhengzhou450000,Henan,China)2(StateKeyLabofASICandSystem,FudanUniversity,Shanghai201203,China)

Aiming at the problems in stream cipher algorithm that the high areas of the reconfigurable hardware implementation of bit-extraction, we propose a high-efficiency hierarchical bit-extraction network based on the Inverse Butterfly network named HHBN(High-efficiency hierarchical bit-extraction network), through the studying of the non-lineal boolean function in stream cipher algorithm. Compared with other networks, the proposed network can extract multiple sets data with common variables. The actual performance and flexibility of HHBN are better than most other networks, and area is far less than the Crossbar network that has same flexibility with HHBN. We integrated the design compiler software at Synopsys company. The results show that compared with the Crossbar network in different width, HHBN reduce the area about 20%～50%, which reduces the resources consumption of extraction operation for different stream cipher algorithm, so as to improve the efficiency of it.

Stream cipher Bit-extraction High-efficiency Hierarchical Inverse Butterfly

2017-03-14。国家自然科学基金项目(61404175)。金羽，硕士生，主研领域：安全专用芯片设计。戴紫彬，教授。李伟，副教授。马超，博士生。

TP3

A

10.3969/j.issn.1000-386x.2017.12.032