面向一类序列密码算法的可重构数据分配网络设计与实现

陈 羽 淏

(中标软件有限公司 上海 200436)

0 引 言

序列密码[1]以其生成算法简洁、加解密速度快、没有或有限错误传播等优势，使得它在实际应用中，特别是在实时通信中具有得天独厚的优势，成为在无线通信、军事、外交通信等诸多领域中的主流加密算法。序列密码算法的实现方式通常有两种[2]：采用专用集成电路方式实现，或者采用通用微处理器方式实现。前者实现速度快而灵活性差，后者恰恰相反，灵活性高但速度慢。因此，基于可重构计算的思想设计序列密码协处理器是一个重要的发展趋势，利用可编程器件多次重新配置逻辑单元的功能和互连的特性，使系统兼具灵活性、高性能、高可靠、低能耗、低成本、易于升级等多种优良特性。

前馈模型是序列密码算法的一个基本模型，主要由初始乱源发生器和非线性变换两部分组成。初始乱源发生器一般都是线性反馈移位寄存器或者非线性反馈移位寄存器等，非线性变换的输入向量来自于初始乱源发生器的输出。因此，在初始乱源发生器与非线性变换单元之间实现高效、灵活的数据分配，对于面向序列密码算法的可重构设计具有重要意义。

1 序列密码算法中数据分配特征分析

初始乱源发生器的输出，可以是一个移位寄存器的若干个状态位，也可以是几个移位寄存器的若干个状态位。非线性变换，可以是反馈函数运算单元，用于计算移位寄存器的更新值，也可以是前馈函数运算单元，用于计算最终的密钥流。本质上，反馈函数与前馈函数都可归结为非线性布尔函数。布尔函数在硬件实现上，往往能够显示出很高的设计效率，所以，这里的数据分配可以理解为布尔变量的分配，应能够支持以下两种操作：

抽取：将参与运算的一个或多个移位寄存器的若干个状态位抽取出来。

可重复置换：经抽取出来的参与运算的状态位可置换到非线性变换运算单元的任意输入端，该置换是一对多的映射，即可重复置换。

其中，抽取操作描述如图1所示，根据预先产生的Rc(控制数据序列)中的控制位的值对Rs(源数据序列)中的对应数据位进行抽取，Rc中的控制位“1”对应的Rs中的数据按照原有的先后顺序依次排在Rd(目的数据序列)的右侧，Rd中其余各位均置为0。例如，从Rs中的8个布尔变量X0，X1，…，X7抽取出5个到Rd中。

图1 抽取操作

可重复置换操作描述如图2所示，Rc中控制位用16进制的值表示布尔变量Xi的位置，其对应的Rd中的数据与其位置值所对应的Rs中的数据进行置换。例如，Rc中第1位的值为“4”，表示其对应的Rd中第1位的数据来自于变量位置“4”对应的Rs的数据，即X7，并且，Rs与Rd可以存在一对多的映射关系，如布尔变量X0和X5。

图2 可重复置换操作

通过对NESSIE工程[3]、ECRYPT工程[4]所征集到的以及在实际应用中普遍使用的A5[5]、E0[6]、W7[7]等共40余种序列密码算法进行分析后发现，有近20余种算法用到反馈函数运算单元或前馈函数运算单元，其输入变量一般来自于一个或几个移位寄存器，移位寄存器的级数、抽头个数及位置都各不相同。并且，抽取操作对应的源数据变量一般在128个以内，经过抽取用于前馈函数或反馈函数的输入变量的个数大多都在10个以内。

基于上述事实，我们设计的用于布尔函数的逻辑运算模块BCB(Boolean Calculation Block)具有10个输入端，而输入变量较多、与项次数较高的复杂的布尔函数计算，则可以通过将多个BCB进行可重构级联来实现(具体不再赘述)。对于每一个BCB实现数据分配的可重构设计，为了提高适用性，可考虑源数据变量在256个以内，因此，需要满足从256个源布尔变量到BCB的10个输入端的任意分配，即包括256 bit源数据位宽到10 bit目的数据位宽的抽取操作，以及10 bit数据位宽的任意可重复置换操作。

2 数据抽取可重构设计

数据抽取网络由两部分组成：基于Inverse Butterfly网络的抽取主体电路和Inverse Butterfly网络每级的控制信息生成电路，如图3所示。其中，进入抽取网络之前，Rs和Rc的数据先进行与操作，使Rs中不需要参与抽取的布尔变量数据置为0。

图3 数据抽取网络

2.1 基于Inverse Butterfly网络主体电路

N输入的Inverse Butterfly网络具有相当优良的特性：存在Euler回路、简单的递归结构、第1级与第log2N级之间存在唯一的长为log2N的路等。它能够很好地实现抽取操作，其证明在此不再赘述。图4所示为N=8 bit的Inverse Butterfly网络，通过递归扩展即可得到N=2nbit的Inverse Butterfly网络。

图4 N=8 bit Inverse Butterfly网络

基于Inverse Butterfly网络的抽取主体电路为N=256 bit的log2N=8级Inverse Butterfly网络，每级由N/2=128个2×2开关元件组成。如图5所示，每一级中输入端总是两两一组，与两个输出端之间由一个2×2开关元件相连。每个开关元件需要1 bit的控制信息，8级抽取主体电路共需要log2N×N/2=1 024 bit控制信息。通过控制信息生成电路产生每一级、每一个开关元件的控制信息，得到每一个开关元件的状态(直通或者交叉)，从而为每一个需要抽取的输入布尔变量建立到输出端的路由，实现抽取操作。

图5 开关元件状态

2.2 Inverse Butterfly网络控制信息生成

对于每个2×2开关元件，定义其控制信息为ai,j(其中，i表示第几级，1≤i≤log2N；j表示第几个开关，0≤j≤N/2-1)，当ai,j=0时，表示开关元件状态为直通，当ai,j=1时，表示开关元件状态为交叉。

Inverse Butterfly网络控制信息生成算法具体描述如下：

1) 根据BCB的资源适配信息(注：该适配信息的如何获取不在本文讨论范畴)，可以得到需要抽取的布尔变量，从而生成本次抽取操作需要的Rc(控制数据序列)。例如，假设N=16，则输入变量为(X15，X14，…，X0)，通过资源适配信息得到需要抽取到BCB的输出变量为(X13，X10，X9，X6，X4，X3，X1，X0)，如表1所示。

表1 生成控制数据序列

2) 假定由比特位0或者1组成的比特序列称为比特位串。x‖y表示比特位串x与比特位串y进行连接，如x=0010，y=0111，则x‖y=00100111。Rc_Mask(v：u)表示Rc中从第u位到第v位之间的比特位串。Rc_Count(str)表示比特位串str中“1”的个数。LROTCMP(allstr，rot)表示对全“1”的比特位串allstr进行顺次逐位左移操作，操作次数为rot，每次操作，最左边的一位移出，并取反补偿进来作为最右边的位。例如，allstr=1111，rot=2时，有1111→1110→1100，如图6所示。另外，对于全“1”的比特位串allstr，假如其“1”的个数为k，则allstr可表示成1k，如allstr=1111=14。

图6 LROTCMP操作示意图

下面，从Inverse Butterfly网络的第log2N级到第1级，计算每一级的控制信息ai,j(1≤i≤log2N，0≤j≤N/2-1)。

1) 计算v从0到N-2时，比特位串Rc_Mask(v：0)中“1”的个数，并分别存入数组PC[v]中。

2) 计算Inverse Butterfly网络每一级控制信息的比特位串Ctr_Str(i)。首先计算网络每一级的局部右半部分的比特位个数IB[i]。所谓局部是指Inverse Butterfly网络每一级彼此之间有连接的部分。如图7所示，若N=8，则第2级有两个局部，即(7654)和(3210)，则IB[2]=LR的比特位个数=RR的比特位个数=2，即IB[i]=N/2i。在每一个局部右半部分中，计算出其最左边的比特位位置Pos，如若N=8，则第2级的两个局部右半部分LR中Pos=5，RR中Pos=1，即对于第i级，Pos=j×IB[i]-1，其中，j=1，3，…，2i-1。对于每一个局部右半部分的LROTCMP操作，其顺次逐位左移操作次数rot等于该局部右半部分的最左边比特位到第0比特位构成的比特位串中“1”的个数，即rot=PC[Pos]=Rc_Count(Rc_Mask(Pos：0))，全“1”的比特位串allstr中“1”的个数k等于每一级的局部右半部分的比特位个数IB[i]。

图7 Inverse Butterfly网络N=8各级局部

3) 得到Inverse Butterfly网络控制信息矩阵。假设Get(str，s)表示从比特位串str中取出第s比特位。以第1步中给出的Rs，Rd为例，N=16，Inverse Butterfly网络共4级，控制信息求解如下：

• 第4级

LROTCMP(18，Rc_Count(“01011011”))= LROTCMP(11111111，5)= 11100000

Ctr_Str(4)= 11100000

• 第3级

LROTCMP(14，Rc_Count(“1011”))= LROTCMP(1111，3)= 1000

LROTCMP(14，Rc_Count(“011001011011”))= LROTCMP(1111，7)= 0111

Ctr_Str(3)=(0111)||(1000)= 01111000

• 第2级

LROTCMP(12，Rc_Count(“11”))= LROTCMP(11，2)= 00

LROTCMP(12，Rc_Count(“011011”))= LROTCMP(11，4)= 11

LROTCMP(12，Rc_Count(“1001011011”))= LROTCMP(11，6)= 00

LROTCMP(12，Rc_Count(“10011001011011”))= LROTCMP(11，8)= 11

Ctr_Str(2)=(11)||(00)||(11)||(00)= 11001100

• 第1级

LROTCMP(11，Rc_Count(“1”))= LROTCMP(1，1)= 0

LROTCMP(11，Rc_Count(“011”))= LROTCMP(1，2)= 1

LROTCMP(11，Rc_Count(“11011”))= LROTCMP(1，4)= 1

LROTCMP(11，Rc_Count(“1011011”))= LROTCMP(1，5)= 0

LROTCMP(11，Rc_Count(“001011011”))= LROTCMP(1，5)= 0

LROTCMP(11，Rc_Count(“11001011011”))= LROTCMP(1，7)= 0

LROTCMP(11，Rc_Count(“0011001011011”))= LROTCMP(1，7)= 0

LROTCMP(11，Rc_Count(“010011001011011”))= LROTCMP(1，8)= 1

Ctr_Str(2)=(1)‖(0)‖(0)‖(0)‖(0)‖(1)‖(1)‖(0)= 10000110

图8所示，为通过上述算法生成Inverse Butterfly网络控制信息，实现抽取操作。

图8 生成Inverse Butterfly网络控制信息实现抽取操作

3 数据可重复置换可重构设计

数据可重复置换网络由两部分组成：基于Crossbar网络的置换主体电路和Crossbar网络每级的控制信息生成电路，如图9所示。该可重复置换网络输入端与输出端具有相同的数据位宽。

图9 数据可重复置换网络

3.1 基于Crossbar网络主体电路

Crossbar网络由N×N交叉矩阵构成，是一种严格无阻塞的交换结构，随着N的增大，Crossbar会导致指数级增长的硬件开销。因为，我们设计的针对每一个BCB的可重复置换操作数据位宽为10 bit，即N=10，所以，基于10×10 Crossbar网络的置换主体电路，如图10所示，其硬件规模能够得到很好的控制。

图10 10×10Crossbar可重复置换网络

Crossbar网络的10个输入端从右到左分别为Y0-Y9，10个输出端从上到下分别为Z0-Z9，并分别对应着BCB的10个输入端。

Crossbar网络共10级，从第1级到第10级分别对应着输出端Z0-Z9，并可以和10个输入端的任意一个相连接，每级由9个2×1开关元件(即图10中“×”处，为2选1数据选择器)组成，每个开关元件需要1 bit的控制信息，共需要9×10=90 bit控制信息。通过控制信息生成电路产生每一级中每一个开关元件的控制信息，从而控制每一级在某一时刻只有10个输入端中的某一个与该级的输出端保持连接状态，从而选择由抽取操作获取的相应的布尔变量，实现可重复置换操作。

3.2 Crossbar网络控制信息生成

假设每一个开关元件为bi,j，i表示第几级，从上到下依次为1，2，…，10；j表示某一级中第几个开关元件，从右到左依次为0，1，…，8。bi,j=1，表示该开关元件选择输入端Yj(这里，j= 0，1，…，9)的值作为输出。

bi,j=0，表示该开关元件选择输入端Yj+1的值作为输出，如图11所示。Sub(Zk)表示Zk(这里，k= 0，1，…，9)对应的布尔变量的下标。Order(Zk)表示每个输出端Zk以所对应布尔变量下标排序后的顺序大小，Order(Yj)表示每个输入端Yj以所对应布尔变量下标排序后的顺序大小。

图11 开关元件状态

Crossbar网络控制信息生成算法具体描述如下：

1) 根据BCB的资源适配信息，得到每级输出端所对应的布尔变量。例如，由2.2节中的表1得到每级输出端与抽取的布尔变量之间的对应关系，其中，输出端Z1无输入变量，输出端Z2和Z5有相同的输入变量。如表2所示。

表2 各级输出端与对应的布尔变量

2) 根据布尔变量的下标，对每一个输出端进行排序。因为输入端、输出端个数最多都为10，由抽取操作的性质可知，如果某输出端无输入变量，则意味着有输入端肯定无抽取布尔变量，且被置为0，并位于有抽取变量的输入端的左边。所以，在此种情况下，可以将无输入变量的输出端的排序大小置为9，表示该输出端与最左边的输入端进行置换。如表3所示。

3) 计算Crossbar网络每一级控制信息的比特位串Ctr_Str(i)。经过抽取操作得到的布尔变量在可重复置换网络的输入端是以原有的从小到大的顺序排列的，显然有Order(Yj+1)=Order(Yj)+1。若Order(Ym)= Order(Zn)，则Ym=Zn。由Order(Zk)的值来确定Crossbar网络每一级的控制信息，因此有：若j=Order(Zi-1)，则ai,j=1；若j≠Order(Zi-1)，则ai,j=0。Ctr_Str(i)的第Order(Zi-1)位为1，其余各位为0。

根据表2所列输出端与对应的布尔变量例子，通过上述算法得到Crossbar网络控制信息，如图12所示。图最右边一列显示的是每一级的控制信息。

图12 生成Crossbar网络控制信息实现可重复置换操作

4 性能分析与比较

对于序列密码算法中数据分配网络能够实现抽取和可重复置换的特性要求，可以按照文献[8]的设计，用M个N选1的数据选择器来实现，N表示输入端布尔变量个数，M表示输出端布尔变量个数。一个N选1的多路选择器的功能可以由log2N级共N-1个2选1的选择器实现，M个N选1的数据选择器就相当于M×(N-1)个2选1数据选择器。根据第2节的分析，这里，M=10，N=256，所以按照文献[8]设计实现，共需要10×255=2 550个2选1数据选择器。

可重排无阻塞互连网络，如Benes、Omega-flip、LPS等可以实现N×N的任意置换，但不能满足可重复的要求，如果以互连开关网络实现，其中，每个2×2开关相当于2个2选1数据选择器，则需要基本步骤如下：① 基于Inverse Butterfly网络实现256 bit-10 bit抽取，共需要N×log2N=256×8=2 048个2选1的选择器；② 10 bit-20 bit扩展置换网络，共需要10个2选1的数据选择器；③ 实现20 bit-10 bit抽取，因为互连网络只能是2nbit的数据位宽，所以该抽取网络实际上是32 bit-16 bit抽取网络，共需要N×log2N=32×5=160个2选1的选择器；④ 最后实现10 bit-10 bit的任意置换，如选择Benes网络，实际是16 bit-16 bit的Benes网络，共需要(2Nlog2N)-N=2×16×4-16=112个2选1数据选择器。而且，因为实际设计中BCB输入端的布尔变量可以重复4次，这样，步骤②和③需要重复一次。所以，以互连开关网络实现，共需要2 048+10×2+160×2+112=2 500个2选1数据选择器。另外，该种方式实现，所需的级数是文献[8]实现方式的近4倍。

我们选用ALTERA公司Cyclone系列的EP1C12Q240C8芯片作为目标器件，采用Verilog语言对各种设计进行了描述，使用Altera公司的QuartusII6.0软件对设计进行了综合。本文提出的数据分配网络设计，共需要2 048+90=2 138个2选1数据选择器，1 024+90=1 114 bit控制信息。比较结果见表4。

表4 各种方式实现256 bit-10 bit数据分配所需硬件资源

在实际设计中，由多个BCB进行级联来满足布尔函数运算的需要，本文的设计较其他实现方式可以节省大量的硬件资源。

5 结 语

本文在分析一类序列密码算法中数据分配网络的特征基础上，提出了基于Inverse Butterfly网络和基于Crossbar网络的数据分配网络主体电路设计，并给出了控制信息生成算法。通过Inverse Butterfly网络在大量、任意的数据中抽取出需要参加逻辑运算的布尔变量，再经Crossbar网络将抽取出来的数量较少的布尔变量与BCB的输入端之间进行任意可重复置换，从而实现灵活、高效的数据分配。相较于文献[8]和其他多级互连开关网络实现，本文的设计能够节省16%的硬件资源。

参 考 文 献

[1] 徐远泽,张文科,尹一桦,等.基于FPGA的eStream序列密码实现分析[J].通信技术,2015(7):850-854.

[2] Elbirt A J,The O,Orr P J,et al.Reconfigurable Computing For Symmetric-Key Algorithms[DB].oai:CiteSeerX.psu:10.1.1.11.7408,2002.

[3] 冯登国.NESSIE工程简介[J].信息安全与通信保密,2001(3):36-39.

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

[5] Briceno M,Goldberg I,Wagner D.A Pedagogical Implementation of A5/I[OL].1999-5.http://www.scard.org.

[6] Bluetooth Specification version 1.1[OL].http://www.bluetooth.org/spec/.

[7] Thomas S,Anthony D,Berson T,et al.The W7 Stream Cipher Algorithm[EB].Internet Draft,2002.

[8] 曲英杰.可重组密码逻辑的研究与设计[D].北京:北京科技大学,2004.

[9] 张游杰,马俊明,卫艳艳.基于分组加密同步信息的自同步序列密码算法[J].计算机应用,2016,36(S1):42-45.

[10] Tutsch D,Hendler M,Hommel G.Multicast Performance of Multistage Interconnection Networks with Shared Buffering[C]//International Conference on NETWORKING.Springer-Verlag,2001:478-487.

[11] Feldmann R,Unger W.The cube-connected cycles network is a subgraph of the butterfly network[J].Parallel Processing Letters,1992,2(1):13-19.

[12] Luo Q B,Zhang J.Status Quo and Development of Stream Cipher[J].Information & Electronic Engineering,2007,4(1).