基于FPGA的改进DES算法的实现

为了解决数据在网络通信中的安全传输问题，通常采用分组加密技术对数据信息进行加密保护，其中最具有代表性的是数据加密标准DES。DES加密算法已成为应用非常广泛的一种分组对称加密算法,该算法具有极高的安全性。到目前为止，除了穷举搜索法对DES算法进行攻击外，还没有发现更有效的方法。目前，DES算法广泛应用于卫星通信、网关服务器、网络通信设备、智能卡（IC卡）等领域[1]。其实现方法通常分为软件实现和硬件实现两种，由于软件实现时速度较慢，最快速度不到150 Mb/s[2]，且利用软件实现DES算法在安全性方面也存在隐患，而应用硬件实现则可以克服以上的问题。现场可编程门阵列(FPGA)在算法实现方面具有灵活性、物理安全性，相对于软件实现，在速度和性能上具有明显的优势。
    DES算法是以多轮的密钥变换轮函数、子密钥和数据异或运算的轮函数为特征，相应的硬件实现方法有两种：一种是通过轮函数的16份硬件拷贝，达到深度细化的流水线处理，实现性能最优；另一种是通过时分复用，重复调用1份轮函数的硬件拷贝，以时间换空间，从而得到硬件资源占用的最小化。通过对系统的性能和资源占用进行综合考虑，本文采用资源优先方案。
    采用此方案系统消耗的资源较少，但运行速度受限。改进的方法是采取在轮函数内部设置流水线结构来提高整体处理的速度，同时子密钥变换轮函数提供子密钥，应与迭代轮函数保持同步工作状态，以减少迭代运算带来的等待延迟。通过设置迭代轮计数器产生的算法状态执行指示位，控制轮函数的输入和反馈，实现轮函数的复用。
1 DES算法概述与原理
　　DES是一种分组加密算法,将64 bit的明文模块输入用64 bit密钥加密得到64 bit密文输出。其64 bit密钥中有效密钥只有56 bit，其余8 bit为奇偶校验位，不参与运算。同时，它也是对称加密算法，其加密和解密运算过程是一样的，区别仅仅在于迭代时子密钥的使用顺序，算法本身并没有任何变化。DES算法的处理流程如图1所示。

    图1(a)是整个算法的实现处理流程，64 bit的明文输入模块经过初始置换IP后，改变了分组中每个bit的顺序,并把置换输出分为L0、R0两部分；进入16轮迭代运算,每一轮迭代都要用到轮函数f,第16轮迭代两输出左右互换的结果R16、L16作为逆初始置换IP-1的输入；64 bit的R16、L16经过逆初始置换得到64 bit的密文输出,IP·IP-1=I。
    图1(b)是单轮迭代运算过程，也是一非线性变换的作用过程。第i轮迭代过程的具体描述可表示为[3]：
  
其中,㈩表示2 bit串的“异或”(按位模2加)。
    轮函数f是迭代运算的核心部分，正是在密钥控制下多次利用论函数进行加密变换，才达到实现扩散和混淆的效果。轮函数f的功能由四个部分按顺序完成:(1)将32 bit Ri-1输入通过扩展E变换扩展为48 bit的数据； (2)将扩展后的48 bit数据与对应的48 bit子密钥Ki“异或”； (3)将异或结果分成8个6 bit分组，8个分组在8个不同的非线性S盒的作用下被转变为8个4  bit分组,其中每个S盒都将6 bit输入映射为4 bit输出;(4)将S盒的输出结果经过P盒的换位置换,得到f(Ri-1,Ki)的32 bit输出。
    DES实际有效的密钥长度为56 bit，对于56 bit的密码信息，每7 bit扩充1 bit奇偶校验位,从而得到64 bit外部密钥。外部密钥输入后，首先经过重排PC-1表(剔除奇偶校验位，打乱密码信息顺序)得到56 bit原始密钥，并分成两部分28 bit的输出。每部分按循环移位次数表[4]移位，并按重排PC-2表置换得到每轮迭代所需的48位子密钥。
2 DES算法的FPGA实现
    本设计选用资源优先方案,即仅用硬件实现单轮密钥变换和密钥加数据运算的轮函数,通过重复16次调用这一功能模块来实现一次DES加/解密运算。该设计方案原理图如图2所示。当数据装载信号置为高电平时，待加/解密数据通过数据选择器送到轮函数的入口。同时在轮计数器的控制下，算法状态执行位置1。在第一个时钟到来时,将数据(B1、B2)通过轮函数实现第一轮变换，经过第一轮变换后的数据被寄存器锁存。在下一个时钟到来时，与相应轮的子密钥一起再次被送到轮函数的输入端，这样循环16轮后，算法状态执行位置0，输出最终数据。

    本文在对DES算法进行建模时，将整个算法分为子密钥生成模块、S盒非线性变换模块、单轮迭代运算模块和顶层模块四个部分。其中，单轮迭代运算模块调用子密钥生成模块和S盒模块实现了一轮迭代运算功能。
2.1子密钥的生成
    DES算法每一轮次迭代都需要一个子密钥参与“异或”运算。传统的硬件实现时，通过对外部密钥的换位重组，以及每次迭代对应的不同次数的循环移位，预先生成子密钥。这样不仅语言描述复杂，占用的硬件资源较多，而且每轮密钥移位次数也不同，需要的运算时间不同，会给算法的迭代运算带来更大的等待延迟。
    外部密钥先后经过置换重排1、第n轮的循环移位和置换重排2这三个步骤得到第n轮的子密钥。通过分析可知这一系列处理都只是位的置换，每轮迭代需要每一位子密钥，相对于外部密钥的每一位存在一定固定的对应关系。为了降低资源消耗，提高算法执行速度，设计中可将三个步骤合并成一次位的置换。采用硬件描述语言Verilog HDL对子密钥生成模块进行组合逻辑设计,其仿真结果如图3所示。图中，mode为工作方式（=0时,加密；=1时,解密);外部密钥为十六进制数133457799bbcdff1时，prekey为外部密钥被剔除奇偶校验位生成的56 bit有效密钥重排PC-1得到的原始密钥，newkey为经过重排PC-2置换的48 bit子密钥。只要改变迭代轮数ki，就会预先生成子密钥。迭代轮数的变化是通过轮计数器来控制。

    此设计方案消除了子密钥之间的相关性，便于子密钥在迭代过程中动态分发。同时，简化了子密钥的产生，有效地节约了硬件资源。
2.2 单轮迭代运算模块
    DES算法是典型的迭代分组密码算法，实现过程的核心是16轮次迭代运算。16轮迭代运算过程完全相同，只是轮迭代的输入参数不同。迭代运算中的轮函数f是非线性的，它是每轮实现扩散和混淆的关键。其中，E盒扩展置换和P盒置换都是线性变换，而S盒代换部件是一个十分复杂的非线性函数，正是经过它的非线性变换才使明文实现了较好的混乱，达到加解密的效果，从而具有较强的安全性。因此，S盒设计在整个DES算法中是非常关键的。
    S盒的功能描述：如果用a1a2a3a4a5a6表示6 bit输入，那么4 bit的输出值可以通过查表得到,行的a1a6索引的表示与列的a2a3a4a5索引表示均为二进制数。因此，建立S盒模型时，一般采用case语句来实现。用case多分支选择语句实现S盒有两种方法：(1)直接使用输入为6变量,输出为4变量的case语句对S盒描述,形成一个4 bit 64个存储空间的表。此方法可读性强，但8个S盒需要8×64个存储空间，占用大量资源，综合效率低，速度慢，不利于整个系统设计实现; (2)由于S盒是一个4×16的二维数组，使用双重case语句，外层使用2个变量，对应S盒输入的第1、6位。内层使用4个变量，对应S盒输入的第2、3、4、5 位。采用双重case语句可以直接定位输出结果。该方案可充分利用FPGA的内部资源，提高综合效率，加快算法执行速度。经过综合后，单个S盒的实现仅占用24个逻辑单元，相对于直接使用6个变量的case语句的实现,占用资源约减少50%。
     本文对单轮迭代运算进行功能模块设计，实现过程调用了密钥生成模块和S盒模块。由于该设计的子密钥是独立产生的，彼此不相关，因此在一轮运算中，不需把子密钥输出作为下轮运算用来产生密钥的输入。子密钥通过控制信号直接控制子密钥生成模块产生分发，在一轮运算中只参与与E扩展后的数据进行“异或”运算,既节省了器件的管脚资源,又提高了算法的执行效率。同样,S盒在具体实例调用时，亦采用了此方法。单轮迭代变换仿真结果如图4所示。图中，ki_i为控制子密钥动态分发的控制信号；L_i和R_i是第i轮非线性变换的输入；R_i是经过轮函数一系列运算生成的数据与输入L_i“异或”，产生的结果作为输出R_o；把R_i直接赋值给输出L_o。

2.3 顶层模块的设计与实现
    顶层模块的功能就是调用单轮迭代运算模块，实现16轮次循环迭代，完成DES算法的总体设计。采用组合逻辑设计实现了数据的初始置换IP、轮函数f、子密钥的产生以及最后的逆初始置换IP-1。图5所示为DES算法的最终设计工程文件生成的原理图。

    顶层模块仅在数据装载控制信号load为高电平时,接收外部数据din;发送控制信号ready为高电平时,输出dout为有效数据。由于16轮迭代的每一轮运算都要用到上一轮的最后计算结果，并且每轮迭代都是调用单轮迭代运算模块。因此，设计了算法执行状态指示位dt，用来协调控制整个DES算法的各轮迭代运算结果的反馈赋值。采用Altera公司的CycloneII系列的EP2C8Q208C8器件作为平台，在Quartus II 8.0下对Verilog HDL代码进行综合，然后布局布线对其进行时序仿真，仿真结果完全符合时序要求，达到了设计目的。由表1给出的DES算法硬件实现性能对比结果表明，在资源使用和实现速度方面，本文算法实现方案都比较理想。DES系统的实现所占用的逻辑单元数仅为468,小于整个硬件资源的6%，可见设计资源得到了极大的优化利用。
    本文的创新点：在传统硬件实现资源优先方案的基础上，采取在轮函数内部设置流水线结构来提高系统的整体运行速度，既节省了硬件资源，又提高了系统的性能;简化了子密钥与外部密钥的生成关系，消除了各个子密钥之间的相关性，保证了在子密钥和数据异或运算的轮函数实现时，子密钥的动态分发。
    通过对整个DES算法的详细分析，提出了合理的分模块设计思想，并采用Verilog硬件描述语言对算法进行了验证仿真。设计文件最终生成的原理图可以完成DES算法的功能，对其进行适当改进，可以作为功能模块嵌入到实际系统中，实现通信数据的实时、可靠传输，具有一定的实际应用价值。
参考文献
[1] 王简瑜, 张鲁国. 基于FPGA实现DES算法的性能分析 [J]. 微计算机信息, 2007, 23(3-2): 217-218.
[2] MCLOONE M, MCCANNY J V. High-performance FPGA implementation of DES using a novel method for implementing the key schedule [J]. IEEE, Circuits Devices System. 2003, 150(5): 373-378.
[3] 郑东, 李祥学, 黄征. 密码学—密码算法与协议[M]. 北京: 电子工业出版社, 2009.
[4] STALLINGS W. Cryptography and network security principles and practices[M]. Prentice Hall,1996.
[5] 姚霁, 刘建华, 范九伦. 一种密钥可配置的DES加密算法的FPGA实现[J].电子技术应用,2009,35(7):145-148.
[6] 张峰, 郑春来, 耶晓东. DES加密算法的FPGA实现[J].现代电子技术, 2008, 31(7):80-82.