一种改进的序列密码可重构处理结构设计

 

　　可重构计算（Reconfigurable Computing,RC），FPGA的可重构运算分为动态系统重构和静态系统重构。FPGA（现场可编程门阵列）动态重构技术，是指基于SRAM编程和专门结构的FPGA,在一定条件下，不仅具有在系统重新配置电路功能的特性，同时还具有在系统动态重构电路逻辑的能力。换言之，FPGA动态可重构技术就是对FPGA的全部或者部分逻辑资源实现在系统的动态的功能变换，动态可重构FPGA则是基于动态重构技术的一种可在系统实现动态配置的新型FPGA芯片。相对于静态系统重构，动态部分重构缩短了重构的时间，而且在重构时，非重构部分依然运行，其寄存器中的数据不会丢失，从而减少了重构系统的开销，提高了系统运行的效率。可重构计算的概念早在20世纪60年代就已提出。在通用微处理器上也运用了这一思想，如组件就是利用多路选择器来实现功能的变化，而这些组件一般与计算结构不发生直接联系。目前，可重构计算已有较大发展，主要目标是希望通过硬件可编程，来自适应计算任务的需求，以期达到性能；而且这种硬件结构的变化，能实时地适应计算任务要求的变化。

　　序列密码也称为流密码（Stream Cipher），它是对称密码算法的一种。序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点，因此在实际应用中，特别是专用或机密机构中保持着优势，典型的应用领域包括无线通信、外交通信。 1949年Shannon证明了只有一密的密码体制是安全的，这给序列密码技术的研究以强大的支持，序列密码方案的发展是模仿一密系统的尝试，或者说"一密"的密码方案是序列密码的雏形。如果序列密码所使用的是真正随机方式的、与消息流长度相同的密钥流，则此时的序列密码就是一密的密码体制。若能以一种方式产生一随机序列（密钥流），这一序列由密钥所确定，则利用这样的序列就可以进行加密，即将密钥、明文表示成连续的符号或二进制，对应地进行加密。序列密码涉及到大量的理论知识，提出了众多的设计原理，也得到了广泛的分析，但许多研究成果并没有完全公开，这也许是因为序列密码目前主要应用于军事和外交等机密部门的缘故。目前，公开的序列密码算法主要有RC4、SEAL等。

　　根据序列密码设计所采用的理论不同，可将序列密码分为4类：基于信息论设计、基于系统论设计、基于复杂度理论设计和基于随机化理论设计的序列密码[4].其中第1、3、4类序列密码涉及的数学理论多样，适于用软件的方法实现，不适于专用硬件或可重构硬件来实现。而第2类基于系统论设计的序列密码是目前为实用的序列密码，这类序列密码的密钥流生成器大多由1个或多个线性或非线性反馈移位寄存器LFSR/NLFSR（Linear/Non-linear Feedback Shift Register）和1个非线性函数NLF（Non-linear Function）构成，本文把符合该特点的序列密码简称为FSR+NLF类序列密码。这类密码由于具有相似的运算单元，很适合采用可重构硬件实现。FSR+NLF类序列密码又分为2个子类： （1）若序列密码中1个或多个FSR状态位参与NLF运算，则称为非线性滤波型序列密码，相应的NLF称为非线性滤波函数，其结构如图1所示，Grain[5]就属于这类序列密码；（2）若序列密码中只有各个FSR的状态位参与NLF运算，则称为非线性组合型序列密码，相应的NLF称为非线性组合函数，其结构如图2所示，Achterbahn[6]就属于这类序列密码。根据FSR运算域的不同，FSR+NLF类序列密码又有GF（2）域上和GF（2n）域上之分，本文将详细讨论GF（2）域上该类序列密码的可重构处理结构设计，非线性滤波型和非线性组合型序列密码均可以在该可重构处理结构上实现。

　　1 总体结构设计

　　对现有的GF（2）域上FSR+NLF类序列密码分析发现，绝大多数此类密码的FSR个数不超过8个，长度不超过256 bit,因此其可重构处理总体结构设计如图3所示。从图中可以看出，此类密码的可重构处理结构主要由8个可重构FSR和1个可重构NLF通过互连网络连接而成。其中，8个可重构FSR分成完全相同的两组，每组中的4个可重构FSR的长度分别为32 bit、64 bit、128 bit和256 bit,以满足不同算法的需要，又可以减少互连资源。该可重构处理结构采用了特殊的互连网络结构，外部送入的配置指令经译码电路译码后存入配置寄存器组，再由配置寄存器组对各可重构FSR、可重构NLF和互连网络进行配置，从而构成相应的序列密码算法处理结构。

　　2 可重构FSR结构设计

   

 

　　基于以上基本理论，1个长级数为n的可重构FSR结构设计如图4所示。其结构总体上分为3部分：中间是1个级数为n的移位寄存器SR,其移动方向为从n-1级到0级；SR以上的部分为反馈函数部分；SR以下部分为前馈函数部分，因为有的序列密码的FSR带有前馈输出（例如Achterbahn）。

　　对现有的FSR+NLF类序列密码反馈函数分析发现：反馈函数F中二次及二次以上项的总数不超过20项。为此，该结构中为项设计了1个配置寄存器CR1;为二次及二次以上项设计了30个配置寄存器CR2~CR31,共计31个配置寄存器。这31个配置寄存器的位数均与SR的级数相同，为n bit.

　　该结构中反馈函数部分工作原理：假设反馈函数F=x0+x3+xn-2+x1x2+x5xn-1+x6x9x12+x1x3x7x10xn-3xn-2,配置时，将CR1的第0、3、n-2位配置为"1",其余位配置为"0";将CR2的第1、2位配置为"0",其余位配置为"1";将CR3的第5、n-1位配置为"0",其余位配置为"1";将CR4的第6、9、12位配置为"0",其余位配置为"1";将CR5的第1、3、7、10、n-3、n-2位配置为"0",其余位配置为"1";其余的配置寄存器各位均配置为"1".配置完成后，SR的各级状态与CR1的对应位相"与",得到的各位结果相"异或"即得到F的所有项模2加的和，即x0+x3+xn-2的结果；SR的各级状态与CR2的对应位相"或",得到的各位结果再一起相"与"即得到x1x2的结果；CR3、CR4、CR5进行与CR2相同的运算后可分别得到x5xn-1、x6x9x12、x1x3x7x10xn-3xn-2的结果，其余各配置寄存器运算与CR21也相同，得到的结果为"1".然后，通过1个32 bit的组合配置寄存器CRcom将各项结果组合运算后即得到F,F反馈给SR的，CRcom的配置方式和运算过程与CR1相同。CRcom在进行组合运算时，还有1个外部反馈值FV_ext参与了运算，这是因为一些序列密码中，有外部数据参与了FSR的反馈（例如Grain）。

　　该可重构FSR结构中，SR以下是1个前馈函数部分，因为在有些序列密码中，FSR带有前馈输出（例如Achterbahn）。前馈函数F′ 是FSR某些级状态的1个线形函数，其中必定包含FSR的状态。该结构设计中，采用1个n bit的前馈函数配置寄存器CRff和SR的各级状态进行组合运算即得到前馈输出FF_out,CRff的配置方式和运算过程与CR11相同。当CRff中只有某一位被配置为"1"时，则FF_out输出即为FSR对应的状态，特别是这样可以得到FSR的状态输出，用于另一个FSR的FV_ext输入或NLF的输入。

　　该可重构FSR的长级数为n,通过对其各个寄存器的配置，可以将其配置为级数小于等于n的任意FSR.例如，当n=32时，要得到一个级数为30的FSR,则将配置寄存器CR1的第0位和第1位都配置为"0",将CR2~CR31的第0位和第1位都配置为"1",则SR的第0级和第1级没有参与反馈运算，相应的FSR退化为30级，其有效级为第2~31级。

　　n位输出信号线Data_out 输出FSR的n级状态，当NLF为滤波函数时作为其输入。外部输入信号线有配置使能信号线Cfg_en、运行使能信号线Run _en、时钟Clk以及32 bit宽的配置数据线Cfg_data.配置使能信号Cfg_en有效后，外部配置寄存器组通过Cfg_data对FSR内部各寄存器进行配置，配置完成后运行使能信号Run_en变为有效，FSR在时钟控制下开始运行。

　　3 可重构NLF结构

　　FSR+NLF 类序列密码中的NLF单元对输入的信号进行非线性变换后输出密钥，其定义与（1）式相同，故可重构NLF 的结构与可重构FSR结构中的反馈函数部分相似。与可重构FSR结构不同的是，在可重构NLF中设计了32个配置寄存器NCR1~NCR32,而且由于输入数据线Data_in宽度固定为32 bit,因此32个配置寄存器NCR1~NCR32均为32 bit.输入数据Data_in分别与各配置寄存器进行组合运算后得到NLF各项结果，各项结果通过NCRcom组合运算后输出NLF值，即密钥Key.

　　4 互连网络结构

　　本文讨论的序列密码可重构处理结构可以实现滤波型和非线性组合型两类序列密码，因此，其互连网络结构应能满足这两类序列密码的连接需要，基于此要求设计的互连网络结构如图5所示。

　　该互连网络结构总的设计思路：当实现非线性组合型序列密码时，可重构FSR1~FSR8的前馈输出信号FF_out与可重构NLF单元的数据输入信号Data_in（0~7） 分别相连；当实现滤波型序列密码时，由于此类密码中FSR一般为1个，个别为2个，因此选择组1中级数长的2个可重构FSR3和FSR4参与互连，组2中的4个和组1中的其他2个可重构FSR这种情况下不参与互连。

　　具体连接规则是：可重构FSR3的128 bit状态输出信号Data_out分别与可重构FSR1~FSR8的前馈输出信号FF_out通过8个129选1选路器MUX0~MUX7与可重构NLF的数据输入信号Data_in（0~7）相连；可重构FSR3的128 bit状态输出信号Data_out再通过8个128选1选路器MUX8~MUX15与可重构NLF的数据输入信号Data_in（8~15）相连；可重构FSR4的128 bit状态输出信号Data_out通过16个128选1选路器MUX16~MUX31与可重构NLF的数据输入信号Data_in（16~31）相连；同时，为了满足有些序列密码算法中某一个FSR的输出要参与另一个FSR的反馈的情况，将可重构FSR3、FSR4的FF_out分别与对方的FV_ext相连。

　　本文论述的FSR+NLF类序列密码可重构处理结构的配置寄存器都是32  bit的整数倍，故规定其重构粒度为32  bit,配置数据线Cfg_data宽度为32  bit.从功能上来看，该可重构处理结构除可以满足FSR+NLF类序列密码的处理需求外，还可以和自收缩式发生器、有限状态机等单元结合使用来处理一些该类衍生的序列密码。

　　此外，该可重构处理结构具有可扩展性，可重构FSR的个数、各可重构FSR的长度、各可重构FSR的反馈函数部分与可重构NLF中二次以上项的项数都可以根据需要进行扩展。

　　本文论述的FSR+NLF类序列密码可重构处理结构的原型已经在Altera公司生产的EP2S60F1020C5型 FPGA上实现，所需资源约为2.2万门，工作频率为200 MHz.由此可见，该可重构处理结构简单，实现时占用资源较少，运行速度较高。