一种新型序列密码的设计与实现

赵 培，赵景琰，金鹰翰，赵 颖，王进祥

(哈尔滨工业大学微电子中心，哈尔滨150001)

1 引言

序列密码实现简单、加密速度快、没有或只有有限的传播错误，在网络安全等领域有着重要的应用。LFSR能产生具有良好统计特性的m序列，但其线性复杂度低，直接使用不能抵御已知的明文攻击，所以LFSF不能用作密钥发生器而通常作为密钥发生器的驱动部分。由于LFSR的理论已经成熟，驱动部分的设计相对容易，故非线性组合部分的设计便成为了密钥流生成器的重点和难点，因此LFSR与FCSR、FCSR与钟控发生器等相结合的组合生成器成为了目前的研究热点。

设计提出一种将LFSR、NFSR和FCSR相结合的序列生成器结构，该结构包含了 LFSR、FCSR和NFSR的良好代数特性，能够获得更大的混淆，因此更加难以被分析和破解。采用Verilog HDL建模，并在FPGA实现与验证，结果表明该算法消耗资源少、加密速度快，可以应用于网络安全等领域。

2 常见组合发生器的结构与特点

［2，3－4］中所提出的算法。文献［3］提出了基于FCSR和LFSR相结合的密钥流生成算法，其特点是结合了FCSR和LFSR的良好代数特性，产生的序列具有较好的伪随机性，在此将其简称为FL算法;参考文献［4］提出的算法基于LFSR并借鉴了DES等分组密码的设计思想，其特点是能产生较好的非线性伪随机序列，简称其为LS算法。文献［2］提出的Grain－128属于应用了NFSR的非线性前馈发生器。

FL算法的基本结构如图1(a)所示。该生成器的左半部分由4个LFSR进行带进位加后输出序列，并以钟控方式驱动右半部分4个FCSR。当左半部分输出1时，各个FCSR进行移位操作，否则各半部分保持上一次的输出。最后将左右两个部分的输出结构进行异或运算。由于利用了带进位加打破了LFSR的代数特性，而用异或运算搅乱了FCSR的代数特性，因此该密钥发生器具有良好的混淆特性和伪随机性。但是该算法中的LFSR级数分别为13，17，19，23，经查证23不是梅森素数，因此易造成周期较小;另外由于密钥长度较短，易于被分析和破解。

LS算法的基本结构如图1(b)所示。该算法为了增强密钥的非线性，使用了:①依赖数据的循环移位;②S盒;③循环结构;因此该算法具有较高的非线性。另外该算法借鉴了分组密码的设计思想，可以实现双字的加密，因此具有较高的加密速度。但是DES算法里面的S盒子已经不够强壮，加密强度不高;以及该设计方案在K1的低五位全为零时，存在循环失效的危险。

Grain算法的基本结构如图1(c)所示。该算法的显著特点是硬件实现占用资源少、功耗较低、加密速度快。该经典算法的不足之处在于密钥流仅有84bit，随着计算机的发展，可以通过足够长度的密文分析出密钥，因此算法的保密密钥长度需要加长，以提高序列的保密性。

图1 三种参考算法的基本结构

3 新型序列密码算法

针对目前序列密码发生器大多基于线性反馈移位寄存器以及上述参考组合序列密码的缺点，提出了一种通过将短移位寄存器级联在一起成为较长移位寄存器，通过引入控制信号控制多选器，配合各个移位寄存器的非线性组合函数，实现不同的加密算法。不但可以实现上述的三种参考算法，并且可以实现三种参考算法的混合加密，大大提高了传输数据的混淆度和数据的保密性。

3.1 对参考算法的改进

针对FL算法、FS算法和Grain－128算法的不足，在保留原算法细想的基础上对其做如下修改:

(1)将 FL算法的四个 LFSR级数从13，17，19和23 改为17，19，31 和61

(2)将FL算法的四个FCSR级数从17，18，19和20增加为22，23，25和26

(3)LS算法的的四个LFSR可直接采用FL算法的LFSR，最后增加一个13级的LFSR即可，因此LFSR 的级数为 13，17，19，31，61

(4)增加一个19级的移位寄存器与其余5个LFSR级联，构成Grain－128算法的128级LFSR

(5)将DES算法的S盒替换为SNOW2.0的S盒，并同时将密钥K2生成模块也对应的替换为32bits，并去掉扩展函数模块

(6)将k1循环左移mod32位，并将结果赋值给密钥K2生成模块的输入和k1，若k1mod32为0，将结果或32’h0000001f后再赋值给密钥K2生成模块的输入和k1

(7)Grain－128的初始密钥由84位增加为128位

其中改进(1)(2)(7)的目的是增大序列的周期，以提高数据的保密性;改进(3)(4)的目的是实现资源的重复利用，以减少硬件消耗;改进(5)的目的采用保密性更强的SNOW2.0盒子，提高序列的非线性;改进(6)的目的是克服了在特定情况下的加密失效。如此设计的目的不但可以增大序列的周期而且也可以实现硬件资源的复用。

3.2 短移位寄存器级联的基本原理

短移位寄存器级联的基本原理如图2所示。

当ctrl为低电平时，移位寄存器1和移位寄存器2由其各自的反馈函数f1(x)和f2(x)决定其性质。2个移位寄存器最右边的状态s10和s20输出经非线性组合A输出z1，z=z1。此时完成的是一种非线性组合序列发生器算法。

当ctrl为高电平时，移位寄存器1和2级联成为一个新的较长移位寄存器，由馈函数f3(x)确定其性质，从移位寄存器3上引出相应的多个抽头经非线性组合B输出，此时完成的是前馈发生器功 能。

图2 短移位寄存器级联示意图

FL算法和LS算法可以直接使用上述短移位寄存器实现，而Grain－128算法需要将移位寄存器级联才能实现。Grain－128算法需要128级NFSR以及128级的LFSR，其中128级的NFSR直接由FL算法和LS算法共同使用的4个LFSR级联构成;128级的LFSR由FL算法的4个FCSR以及FL算法的第5个LFSR和新增的19级移位寄存器级联而成，这样有利用减少硬件资源的消耗。

3.3 动态反馈

为进一步加强数据的加密强度，对线性反馈移位寄存器引入动态反馈多项式(DFP)，同样由控制密钥控制其反馈多项式的选择。其简易原理如图3所示。

图3 DFP简易原理图

在本设计中，Grain－128的LFSR采用其自定义的本原多项式;FL算法和LS算法共同使用的4个LFSR采用动态反馈的本原多项式，其中17级的LFSR具有三个本原反馈多项式、19级的LFSR具有2个本原反馈多项式、31级的LFSR具有6个本原反馈多项式、61级的LFSR具有2个本原反馈多项式。采用控制信号，控制反馈多项式的选择，使得该设计可以实现三种73类不同的加密算法。

采用短移位寄存器级联的结构，实现寄存器资源的复用，不但有利用减小寄存器资源的消耗，而且可使设计变的更加灵活。使得设计不但可以实现特定的加密算法，而且在混合加密时，由于动态反馈多项式的存在使得序列的伪随机性、混淆度和保密性都增大了，更加难以被分析和破解。

4 硬件实现与结果分析

4.1 硬件实现的基本结构

三种参考算法生成的密钥流的数据类型不同，其中FL和Grain－128实现的是比特加密，LS算法实现的是双字加密。因此硬件实现的结构图如图4所示。

其中KeyIV_REG模块主要完成密钥和初始变量的注入;KSG是设计的主体部分，其主要功能是接收通过KeyIV_REG注入的密钥和初始变量，按设计的算法产生相应的密钥流，并控制其他两个模块正常工作;EncryFun模块负责进行具体的加密解密运算。

4.2 系统工作流程

在设计时引入强制控制信号，在该信号的控制下，通过配置移位寄存器可以实现三种参考算法中的任意一种。

FL和Grain－128算法实现的是bit加密，而LS算法实现的是双字加密，因此易知在混合加密时，该设计并没有一直在读取外部数据。

下面简述混合加密的基本工作过程:在上电复位后KeyIV_REG开始接收外部32bits的数据，并开始密钥和初始变量的注入，控制信号也完成初始化;KSG模块接收到密钥和初始化变量，初始化内部所有的移位寄存器，并按照控制信号的要求(加密算法以及何种动态反馈)，配置出密钥流的数据通路，产生相应的密钥流，并根据当前的加密算法和运行状态，输出信号标志何时可以重新读入下一组加密数据;EncryFun利用KSG模块产生的密钥流来加密KeyIV_REG接收的数据。由分析可知FL和Grain－128算法产生的密钥流是bit形式的，而LS算法产生的密钥流为32bits，因此EncryFun要根据控制信号的要求决定是否对接收到的密钥流进行串并转换，之后再对数据进行加密。当前数据加密结束时，在KSG模块将控制信号与内部寄存器进行异或运算，对控制信号进行更新;利用更新后的控制信号，确定下一组数据的加密算法，开始下一组数据的加密，使得整个数据的加密过程中各种加密算法“乱序”的对数据进行加密，以使加密序列难以被分析和破解。

图4 序列密码的结构图

4.3 FPGA实现与结果分析

本设计采用Verilog HDL进行建模，在经过功能仿真之后按照修改后的设计参数，在Altera Cyxlone II系列的EP2C35F672C6 FPGA芯片上进行了硬件实现，实现结果表明算法功能具有较快的加密解密速度(时钟频率最高可达109.52MHz)，达到了设计要求。在相同约束条件下几种算法性能的比较如表1所示。

表1 几种参考算法的比较

通过分析可知，该算法具有较高的运算速度(100MHz以上)，LE资源消耗与三种参考算法消耗资源的总和相当，这是因为Grain－128算法资源消耗少(主要是FL和LS算法资源消耗大)，在将移位寄存器级联时在设计中加入较多的选择器，因此造成了资源消耗相当的结果。由于设计考虑了寄存器资源的重复利用，因此寄存器资源减小的较为明显。虽然该设计并没有显著减小资源消耗，但该设计可产生3类(73种)不同的加密算法，而且在混合加密时可大大降低数据被分析和破解的几率。若单独实现三种算法不但不会节省资源而且对加密数据的安全性没有任何改进。

5 结论

在参考三种具有代表性的序列密码基础上，设计实现了一种可控的，将短移位寄存器级联成长移位寄存器，通过控制密钥选择反馈以改变加密方式的新型序列密码发生器。该序列密码发生器可以产生多种加密算法，加密速度较快、资源消耗相对较少，在混合加密时可产生伪随机性很强的序列。该算法具有多种变形，可以应用于网络安全等领域。

参考文献:

［1］C E Shannon.Communication Theory of Secret System［M］.Bell Syst.Tech.J.1949，28:656 －715.

［2］M Hell，T Johansson，A Maximov.A Stream Cipher Proposal:Grain－128.IEEE International Symposium on Information Theory［R］.Seattle，2006:1614 －1618.

［3］郑宇，何大可，唐小虎，等.基于FCSR和LSFR相结合的密钥流生成器［J］.计算机工程，2007，33(5):32－35.

［4］李昌刚，张昕，朱芳来，等.一种新的密钥流发生器设计算法［J］.计算机工程，2007，33(10):138 －140.

［5］王相生.序列密码设计与实现的研究［D］.北京:中国科学院，2001:28－55.