摘  要：一种基于FPGA的数据加密标准算法的实现。就资源优先和性能优先分别使用循环法和流水线法对DES加密算法进行了设计，并对其进行了比较。通过采用子密钥简单产生和ROM优化S盒的方法，对流水线法进行改进，达到了资源占用率低、加密速度快的效果。 

    关键词： DES； 流水线； 循环法； FPGA； 密码学

    付费节目是数字电视的重要新业务之一，建立付费频道，其中关键性的技术就是加密技术，数字电视条件接收系统CAS（Conditional Access System）是数字电视加密控制的核心技术的保证。典型的CAS由前端子系统、终端接收子系统等组成，前端子系统逻辑结构如图1所示。图1中加密器B采用数据加密标准DES（Data Encryption Standard）加密算法进行硬件实现，以达到对控制字CW进行快速加密。尽管目前DES算法已经出现很多变形的算法，但基础仍然是DES算法，可见，对DES算法的研究具有很大现实意义。 

    通过软件实现的安全系统从本质上来说很难做到真正的保密，而通过硬件来实现加密模块的内部运作，可实现硬件的自锁、自毁功能，能够实现真正意义上的保密。现场可编程门阵列FPGA在实现算法方面具有灵活性、物理安全性和比软件高的速度性能，已成为硬件实现DES算法最好的选择。本文就资源优先和性能优先上对DES算法进行了设计和比较，这两种设计方法和针对流水线改进后的方法都在Altera CycloneⅡ芯片上得到了实现。 

1 DES加密算法原理 

    本文采用电码本模式ECB(Electric Code Book)的DES加密算法，通过直接使用分组密码算法来进行消息加密。这一工作模式的优点就是分组密码的优点，其缺点是相同的密文对应相同的明文。DES是迭代型分组密码，明文分组长度为64bit，密钥的长度也为64bit，但实际上只有56bit有效，密钥中第8、16、24、…、64位被舍去，因为它们通常是奇偶校验位。DES加密算法从数据流的角度来看，可以分为两部分：明文的变换和密钥的变换。变换中引入了轮的概念，每一轮的算法都是重复的，一般要进行16轮。 

    在每轮密钥变换过程中，密钥扩展算法还需要用到循环左移变换。密钥变换的原则是：在第1、2、9、16轮变换时，密钥循环左移1位；当第3～8轮或者10～15轮变换时，密钥循环左移2位。每个循环左移变换的输入和输出都是28bit串。将移位所得的56bit密钥通过压缩变换变成48bit密钥，此密钥即为这轮变换所得的子密钥^[1]。 

    在一轮明文变换时，输入数据被分为左右对称的两部分。通过一个扩展置换将数据的右半部分扩展成48bit，将其与此轮生成的子密钥进行模二加运算，经过S盒代换将模二加生成的48bit密钥替代成32bit密钥，最后将其进行P盒置换。以上四个运算过程构成函数F。通过另一个模二加运算，函数F的输出与输入数据左半边模二加构成新的右半部分，原来的右半部分变成新的左半部分。以上过程即完成了DES算法的完整的一轮运算。DES加密算法一轮运算和总运算流程如图2所示。 

2 DES加密算法的FPGA实现 

2.1 资源优先设计方案 

    资源优先方案就是通过硬件设计出一个密钥变换轮函数和一个明文变换轮函数，通过16轮反复调用这一个硬件系统实现一次DES加密运算。由于16轮运算都只占用一轮运算所需的硬件资源，使硬件的开销大大减少。但是，一个时钟周期只能进行一轮加密运算，要完成整个加密过程要花费16个时钟周期，从而在速度性能上大打折扣。而采用循环法实现DES加密算法能达到减少资源占用的目的，具体实现方法如图3所示。 

2.2 性能优先设计方案 

    性能优先设计方案刚好与资源优先设计方案相反。传统方案是将循环全部打开配合流水线结构进行设计,即将16轮函数进行硬件级联构成一个16级的流水线结构，提前生成16个子密钥，随着流水线的进程发送给相对应的流水级，从而达到16个数据块同时加密的目的^[3-4]。这样，从第一个数据块开始加密起，每一个时钟周期延时都会有一个数据块进行加密，经16个时钟周期延时后，得到最终的密文。流水线结构设计通过一个时钟周期即可进行一个数据块的加密，通过占用资源换取速度性能的提高。

    本文通过子密钥的简化和S盒的优化来改进传统的流水线结构，实现一个占用资源少、加密速度快的加密系统。具体的设计框图如图4所示。 

    (1) 子密钥的简单生成 

    由DES加密算法原理可知，一个64bit的初始密钥输入后通过一次压缩变换、移位变换、二次压缩变换后得到第一轮子密钥，其密钥为48bit。第一轮子密钥变换结果如图5所示。由图5可知，第一轮子密钥的第1、2、3、…、46、47、48位分别为初始密钥的第10、51、34、…、62、55、31位。每一轮子密钥产生的方法是一样的，如果采用硬件描述语言按照其子密钥产生的原理一步步地推导出16次DES迭代的密钥，不仅语言表述繁琐，而且占用很多的硬件资源。同时，由于每一轮子密钥产生的时间并不相同，会给DES密码的迭代运算带来很多不必要的麻烦。 

    对密钥变换原理进行分析可以发现，每一轮子密钥的产生只是将初始密钥经过置换和不同次数的循环移位。每一轮循环移位的次数对原始密钥是固定的，其每一位相对于初始密钥的每一位存在着固定的关系，由此可以列出每一轮子密钥与初始密钥之间的关系表，通过关系表采用硬件描述语言可同时产生16轮子密钥。采用此方法大大简化了程序语言、节约了硬件的资源开销。 

    (2) S盒的优化 

    S盒的设计是DES算法的关键部分, S盒设计的优劣将影响整个算法的性能。S盒是DES加密算法中唯一的非线性函数，S盒的非线性变换使算法达到很好的“混乱”效果,从而具有较强的安全性。 

    S盒的原理是输入6bit的数据，其中第1位和第6 位确定行，中间4bit确定列，通过行、列查表确定对应的4 bit的输出。根据S盒的工作原理，可直接使用输入为6变量、输出为4变量的case语句进行描述，构成一个4bit 64个存储空间的表。然而这样的语句虽然可读性很强,但综合的效率往往不高，占用资源过多，速度也比较低，使S盒成为系统速度的瓶颈。 

    本文采用8个ROM来实现S盒。把输入的6bit作为地址，对应的地址空间里存放的就是待输出的4bit，这样可提高运算时间，解决S盒变换的时间瓶颈;利用FPGA内部自带的ROM，大大减少逻辑资源的占用。以第一个S盒设计为例，其设计实现电路如图6所示。输入为IN[6:1],经地址变换电路将输入的初始值转换为相应的查表地址{IN[6]、IN[1]、IN[5:2]}，即ADR[6:1],以此对64×4 ROM进行查表,ROM值按照S盒查找表进行初始化,由ADR[6:1]读取ROM中相对应的数据从而得到OUT[3:0]^[2，5]。采用同样的办法，通过ROM实现其他7个S盒，以达到优化的目的。 

3 综合仿真结果对比 

    利用ModelSim对三种不同方法实现的DES加密算法程序进行了仿真，得到的仿真波形初步验证了DES加密功能的正确性。选用Altera公司的QuartusⅡ6.0环境下成功编译、综合、适配、仿真，并下载到CycloneⅡ系列的FPGA中进行了验证，通过分析得到循环法、传统流水线法、改进流水线法在速度性能和资源占用上的差异如表1所示。 

    从表1可以看出，三种不同的方法，各自占用硬件资源、可以达到的最大时钟频率、加密速率上都存在各自的特点。循环法占用资源少、时钟频率低、加密速度相对较慢。传统流水线法通过改进后，大大减少了逻辑资源的占用量，同时在时钟频率和加密速率上都得到很大的提升。 

    本文按照资源优先和性能优先两种不同的设计方案，分别采取循环法和流水线法予以实现。同时，对性能优先方案提出了改进方法即：子密钥简单生成和S盒的优化。通过对这三种方法进行综合仿真验证，证实了改进流水线法的正确可行性。这两种方案可以用于不同要求的应用领域，具有较大的灵活性。 

参考文献 

[1] 胡予濮，张玉清，肖国镇.对称密码学[M].北京：机械工业出版社，2002：143-162. 

[2] HASKINS G M. Securing asynchronous transfer mode networks[D].Worcester Polytechnic Institute,Worcester,Massachusetts,USA,1997.  

[3] MCLOONE M, MCCANNY J V. High-performance FPGA implementation of DES using a novel method for implementing the key schedule[J]. Circuits, Devices and Systems, IEE Proceedings,2003,150(5):373-378. 

[4] LUBBE V D. Basic methods of cryptography[J].IEE Review, 1999,45(2):77-77. 

[5] 艾显峰,叶宇煌.高速通用DES加解密芯片设计与实现.宁德师专学报，2004，16（3）.