基于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，就会预先生成子密钥。迭代轮数的变化是通过轮计数器来控制。