摘  要： 讨论了FSR+NLF类序列密码的可重构处理结构设计，包括总体结构设计、可重构FSR结构设计、可重构NLF结构设计以及互连网络结构设计。采用该结构的密码运算单元可以根据需要实现多种此类序列密码，具有结构简单、可扩展、运行速度高等特点。
关键词： 序列密码;可重构计算;线性反馈移位寄存器;非线性反馈移位寄存器;非线性函数

    可重构计算的思想最早由加利福尼亚大学洛杉矶分校的Estrin教授[1]提出来的。可重构计算没有严格的定义，目前学术界普遍接受的定义是：使用集成了可编程硬件的系统进行计算，该可编程硬件的功能可由一系列定时变化的物理可控点来定义[2]。从这个定义可以看出，可重构计算是通过对结构可变的硬件进行软件配置，以适应不同算法的处理，故其既具有软件的灵活性，又具备了ASIC硬件的高速性，是解决资源受限类算法，如多媒体处理算法、DSP、加解密算法的一种理想选择。
    明文数据流与密钥流逐位地加密成密文数据流的密码体制称为序列密码(Sequence Cipher)。当密钥流满足离散无记忆二元均匀分布，即完全随机时，则该体制就是“一次一密”密码体制，香农证明该体制是不可破译的[3]。实际应用中,序列密码的密钥流是用确定的算法产生的，即密钥流是伪随机的，但可以通过数学的手段尽可能地提高密钥流的随机性,最大程度地逼近“一次一密”，因此序列密码的保密性较高。此外，由于序列密码具有容易实现、实时性好、错误传播有限等优点，被广泛应用于政府、军事等重要部门。
　 根据序列密码设计所采用的理论不同，可将序列密码分为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=x₀+x₃+x_n-2+x₁x₂+x₅x_n-1+x₆x₉x₁₂+x₁x₃x₇x₁₀x_n-3x_n-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加的和,即x₀+x₃+x_n-2的结果；SR的各级状态与CR2的对应位相“或”，得到的各位结果再一起相“与”即得到x1x2的结果；CR3、CR4、CR5进行与CR2相同的运算后可分别得到x₅x_n-1、x₆x₉x₁₂、x₁x₃x₇x₁₀x_n-3x_n-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。由此可见，该可重构处理结构简单，实现时占用资源较少，运行速度较高。
参考文献
[1]     ESTRIN G, BUSSEL B. Parallel processing in a restructurable computer system[J]. IEEE Trans. Elect comput, 1963. 747-755.
[2]     COMPTON K, HAUCK S. Reconfigurable computing: a  survey of systems and software[J]. ACM Computing Surveys.    2002, 34（2）：171-210.
[3]     SHANNON C E. Communication theory of secrecy systems     [EB/OL]. http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf. 2009-01.
[4]     冯登国，裴定一.密码学导引[M]. 北京：科学出版社，1999:486-100.
[5]     GAMMEL B, GOTTFERT R. The achterbahn stream cipher [EB/OL]. http://www.ecrypt.eu.org/stream/papers.html. 2009-02.
[6]     HELL M, JOHANSSON T, MEIER W. Grain-a stream cipher for constrained  environments[EB/OL].
    http://www.it.Ith.se/grain/grainV1.pdf. 2009.02.