基于FPGA的高速加密芯片的设计与实现

摘要：以非线性组合函数和线性反馈移位寄存器(LFSR:Linear Feedback Shift Registers)为基础，利用可编程逻辑门阵列(FPGA:Field-Programmable Gate Array)设计了一个高速加密芯片。该芯片既能满足密码学领域对密钥序列的高质量要求，又能满足保密通信领域高速度要求。介绍了加密芯片的设计理论、设计过程、加密芯片安全性分析和硬件实现，最后对密钥流进行了随机性统计测试。

关键词：非线性组合函数；加密芯片；伪随机序列；可编程逻辑门阵列

引言

密码技术是信息安全技术的核心，密码算法又是密码的核心。为此，世界各国对密码算法的研制都高度重视。根据明文消息加密形式的不同，密码体制可分为分组密码和序列密码。分组密码多用于商业领域，而序列密码主要用于政府、军方等国家重要部门。美国早在1977年就制定了自己的数据加密标准———DES(Data Encryption Standard)。随着DES的出现，人们对分组密码展开了深入的研究和讨论，现已有大量的分组密码，如IDEA(International Data Encryption Algorithm)算法、SAFER(Secure And Fast Encryption Routine)系列算法、AES(Advanced Encryption Standard)算法、FEAL(日本NTT(日本电报电话公司)的清水和宫口设计)系列算法、LOKI(DES的一种潜在替代算法)系列算法、CAST(Carlisle Adams/Stafford Tavares)系列算法等。2001年11月26日， NIST (National Institute for Standards Technology)公布了新一代数据加密标准AES(高级加密标准)，这是比利时学者Vincent Rijmen和Joan Daemen发明的“Rijndae算法”。与分组密码相比，序列密码具有加解密速度快、安全性较高等优点，但一般要设计专用的硬件加密芯片。讨论的高速加密芯片就是基于序列密码算法。序列密码算法的设计方法可归纳为4种：系统论方法、复杂性理论方法、信息论方法和随机化方法。笔者将密钥流生成器分解成驱动部分和非线性组合部分分开设计，不仅结构简单，而且便于从理论上分析。对于密钥流生成器的驱动部分，采用线性反馈移位寄存器(LFSR:Linear Feedback Shift Registers)；对于密钥流生成器的非线性部分，采用最典型、也是最常用的方法———非线性组合函数。当然，非线性部分还可采用其他方法，如非线性滤波生成器和钟控序列法等。笔者采用基于LFSR和非线性组合函数的方法设计密钥流生成器，不仅便于从理论上分析其安全性，而且易于硬件实现。经严格测试表明，该加密芯片能产生高质量、高速的伪随机密钥流，它在保密学领域有广泛的应用。

高速密钥序列生成器的设计

高速加密芯片的核心是密钥序列生成器，实质是一个伪随机序列生成器。笔者讨论的随机序列生成器的结构图见图1，由N个多级LFSR和一个非线性组合函数组成。LFSR产生M序列，为提高密钥流的复杂度，再将多路M序列进行非线性组合。伪随机序列生成器的设计主要有：LFSR的级数和反馈函数的设计；非线性组合函数的设计。

图1　伪随机序列生成器结构图

图2　线性反馈移位寄存器的结构图

LFSR的设计
一个N级反馈移位寄存器由两部分组成：移位寄存器和反馈函数。移位寄存器是一个位序列，每生成一位时，移位寄存器中所有的位都向右移一位，移出的位就是输出结果，左边空出的位由反馈函数对其他位进行运算后的结果填充。当反馈函数是线性函数时，该反馈移位寄存器就叫线性反馈移位寄存器，一般的线性反馈移位寄存器如图2所示。按图2的连线关系，该LFSR可用式(1)表达

式(1)称为递推方程，c_i∈(0,1)，它的取值决定了反馈函数的结构。LFSR还可表示为

式(2)称为特征多项式。式中xⁱ的取值只表明系数c_i的取值(0或1)，其本身并无实际意义。

经严格的证明：如果一个n级LFSR的特征多项式为本原多项式，则该LFSR生成的随机序列具有最大的周期为2ⁿ-1。因此，只要找到LFSR的本原多项式，并以此为反馈函数，序列发生器就能产生M序列。

LFSR的级数选取
LFSR级数的选取应满足以下准则：，N为密钥长度，取N=256；m_i为LFSR的级数，要求m_i为整数且两两互素，且m_i>2；n为LFSR的数量，要求n≥4，在此取n=7。基于采用的设计系统，先搜索到一部分满足以上条件的n个整数m_i，然后再计算其最大序列周期，结果如表1所示。由表1的结果，取序列周期最大的一组m_i为LFSR的级数，它们分别为31、32、33、35、37、41和47。

表1　LFSR的级数及对应的最大周期

构造LFSR的反馈函数
一个n位长的LFSR最多有2ⁿ种状态，除全0状态外，其最大周期为2ⁿ-1。理论已证明：在用n级LFSR产生伪随机序列时，为了获得最大周期2ⁿ-1，需要寻找n阶的GF(2)本原多项式。有很多方法可寻找本原多项式，如循环队列法、筛选法、利用纠错码原理法和利用CA(Cellular Automata)原理法等，其中最常用的是筛选法。为了寻找本原多项式，要用到以下定理和定义。

定义1　若一个n次多项式满足以下条件：f(x)为既约多项式；f(x)可以整除(x^m-1)，m=2ⁿ-1；f(x)除不尽(x^q-1)，q>m，则称f(x)为本原多项式。

定理1　f(x)为GF(p)上的m次既约多项式，且f(x)可以整除(x^p^^m-1-1)，而当rm-1时，则f(x)不能整除(x^p^^m-1-1)，那么f(x)为GF(p)上的m次本原多项式。

依据以上定理和定义，采用设计系统在计算机上找到了部分本原多项式，结果见表2。

表2　LFSR的部分本原多项式

为了简化实现函数所需的硬件，选定的一组简单的LFSR的线性反馈函数，其形式如下：

构造非线性组合函数
非线性组合函数f(x)是定义在GF(2)ⁿ→GF(2)上的函数，一般又把函数f(x)称为布尔函数f(x)。理论和实际的研究都指出非线性组合函数f(x)的设计应满足一定的准则，通常认为f(x)应满足以下4条设计准则。
准则1　平衡性准则，要求组合函数f(x)的输出值中0与1的数目各占一半。
准则2　相关免疫性准则，要求非线性组合函数f(x)与每个输入变量统计独立。
准则3　严格雪崩准则(SAC:Strict Avalanche Criterion)，要求组合函数中某个变量取补的话，那么函数f(x)输出值中将有一半改变。
准则4　要求非线性函数f(x)的代数标准式中乘积项次数尽量高。因为在同样的输入情况下，函数次数越高，线性复杂度越大，从而能对抗B-M算法攻击。

为了构造高次布尔函数f(x₁,x₂,x₃,.,x_n):GF(2)ⁿ→GF(2)，可以先利用穷举搜索法搜索全部满足上述4个准则的低次布尔函数，然后再利用组合法构造高次布尔函数。

穷举搜索法
穷举搜索法，即遍历函数f(x₁,x₂,x₃,.,x_n)的所有可能形式，对每个具体的f(x)，根据上述4个准则进行筛选。对有n(n≥4)个输入变量的f(x₁,x₂,x₃,.,x_n)，其所有可能形式为N=2^{(2^n)}，因此，总的搜索次数也为N=2^{(2^n)}。准则1和准则4比较容易判断，为了判断f(x)的相关免疫性准则与严格雪崩准则，要引入序列的Walsh(沃尔什)频谱理论和一些定理。由于GF(2)在加法运算下构成一个阿贝尔群，故它的特征函数系一定存在。事实上，函数系 构成了GF(2)ⁿ上的特征函数系，对任何一个布尔函数f(x₁,x₂,x₃,.,x_n):GF(2)ⁿ→GF(2)都可用Walsh函数系展开为

定义2　n元布尔函数f(x₁,x₂,x₃,.,x_n)是m阶相关免疫的(1≤m≤n-1)，当且仅当对任意1≤i₁2<.m≤n和a₁,a₂,a₃,.,a_n，下式成立：

定理2　n元布尔函数f(x₁,x₂,x₃,.,x_n)是m阶相关免疫性的(1≤m≤n-1)，当且下式仅当对任意w=(w₁,w₂,w₃,.,w_n)，1≤W(w)≤m都成立：S_f(w)=0。这里W(w)指向量w的重量，是函数f(x)的Walsh频谱。如果组合函数f(x)满足相关免疫性准则，那么它的Walsh频谱S_f(w)=0，对w∈GF(2)ⁿ，W(w)=1。严格雪崩准则与Walsh频谱有如下定理。

定理3　对布尔函数f(x):GF(2⁾ⁿ→GF(2)，满足严格雪崩准则，当且仅当 成立。依据定理2和定理3对f(x)进行判定。基于以上理论，通过设计系统，可以找到n=5的满足要求的部分非线性组合函数。

组合构造方法
以穷举搜索法得到n=5的非线性组合函数为基函数，采用组合构造方法可构造出次数更高的非线性组合函数。组合构造方法的原理如下：设m，n是两个不同的整数，且m>n，I_m,n={I_0...0,I_0...1,^_...,I_1...1}，I_m,n中包含2^m-n个函数，其中每个函数都满足上述4个准则。令x=(x₁,x₂,x₃,...,x_n)，y=(y₁,y₂,y₃,...,y_n)，那么构造的函数为 其中

对于该方法，有以下引理和定理。

在函数集I_m,n中。
引理1　如果每个函数都满足平衡性，那么新构造的函数也满足平衡性；
引理2　如果每个函数都满足相关免疫性，那么新构造的函数也满足相关免疫性；
引理3　如果每个函数都满足SAC(严格雪崩准则)且∑I_i(x).I_j(x)=0，i不恒等于j，那么新构造的函数也满足SAC；
定理4　如果至少有一个最大代数式次数的同一项在I_m,n中出现的数目为奇数，那么新构造的函数可达到最高代数式次数。

伪随机序列的测试

穷举搜索法
采用美国国防部在测试序列随机性方面的一些标准方法，对生成的密钥流进行测试，测试的标准如下。

1)平衡特性。如果样本中的0和1的比特总数被这个样本长度除，得数都是0.5，则平衡特性得到满足。
2)第1_Δ特性。如果样本中重叠00和11模式的总数被这个样本长度除，得数是0.5，则第1_Δ特性得到满足。
3)第2_Δ特性。如果样本中重叠0x0和1x1模式的总数被这个样本长度除，结果是0.5，则第2_Δ特性得到满足。
4)第3_Δ特性。如果样本中重叠0xx0和1xx1模式的总数被这个样本长度除，结果是0.5，则第3_Δ特性得到满足。

测试方案与步骤
根据测试密钥的不同分以几类进行统计测试。
1)随机密钥测试。随机生成256位密钥，统计分析输出密钥序列的4种特性。
2)全“1”密钥测试。密钥置全1，统计分析输出密钥序列的4种特性。
3)全“0”密钥测试。密钥置全1，统计分析输出密钥序列的4种特性。
4)将测试1)中的密钥随机地改变一位，观察生成的密钥序列与原密钥序列不同的位数，以判别加密的扩散性。
5)将测试1)中的密钥取补后再进行测试，观察现在生成的密钥序列与原密钥序列不同的位数，以判别加密的严格雪崩特性。

测试结果分析
对序列进行随机密钥测试、全“1”、全“0”密钥测试。测试结果如表3所示，测试密钥流长度为6000bit。表3中E(k)表示输出密文序列中1的平均个数；E(k′)表示平衡特性的均值， 表示平衡特性的均方差值：E(Δi′)，δ(Δi′)，i=1,2,3,表示第i_Δ特性的均值、均方差值。由表3可知，对随机密钥和特殊密钥(全1密钥和全0密钥，为节省版面，特殊密钥的测试结果未给出)，该算法所生成的密钥序列都有良好的伪随机特性，并且对密钥的变化具有良好的扩散性和严格的雪崩特性。

表3　随机密钥测试结果

加密芯片的硬件实现

整个设计采用Altera公司的FPGA实现。系统由图3所示5个功能区组成：加密控制器；初始密钥存贮区；初始密钥寄存区；会话密钥寄存区；伪随机序列生成区。

图3　加密芯片的系统框图

图3反映了整个伪随机序列生成器的结构和各功能模块的连线。当加密功能选中时，加密芯片首先从初始密钥存贮区中将初始密钥读至初始密钥寄存器。实际加密数据前，加密控制器会发出加密控制信号，并产生一随机数作为本次加密的会话密钥。该随机数经与基本密钥一起去控制密钥发生器的初态，用于产生加密数据的伪随机序列流。在本次设计中，采用Altera的FPGA开发系统Quartus II作为FPGA开发工具，并以VHDL语言作为输入工具，与传统的电路原理图输入法相比，VHDL输入法具有设计周期短，容易移植，容易修改和与工艺无关等特点。

结语

笔者设计了一个高速加密芯片，该芯片能够满足密码学安全领域对随机序列的高质量、高速度的需求，具有一定的现实意义。设计以LFSR为基础，为提高序列的复杂性，又将多个LFSR生成的序列进行非线性组合，以提高序列的安全性。对生成的序列进行了统计测试，随机测试结果表明，该伪随机序列具有一定的安全性，也便于高速硬件实现，满足保密通信领域的适时性要求。