Profile - CN158

CN158

基于Petri网的分组密码算法的硬件加速实现

Project

Name of Project:	基于Petri网的分组密码算法的硬件加速实现

Contact Information

Name:	沈国新
E-Mail:	strongwind7@sina.com
Telephone:	0532-86057775转858
Mobile Phone:	13730925842
Mailing Address:	山东省青岛市经济技术开发区前湾港路579号山东科技大学信息学院J13-132实验室

Contest Advisor

Name:	张德学
E-Mail:	dxzhang@ustc.edu
Telephone:	15866890384

Members

No.	Name	E-Mail	English Name
1	沈国新	strongwind7@sina.com	Shen Guoxin
2	焦汉明	jiaohan_901@163.com	Jiao Hanming
3	罗虎	rophihoo_hn_cn@163.com	Luo Hu

Project Paper - view as Preliminary(2009/06/15), Final(2009/09/14), Draft, Latest

1. 设计概述 (Preliminary Paper)

设计意图

       随着通信技术和网络技术的发展，信息安全问题日益突出。目前虽然流行的加密算法本身对公众是公开的，但仍受知识产权保护。因此，拥有自主知识产权的加密算法是很重要的。

       山东科技大学吴哲辉教授发布的基于petri网的分组加密算法，设计思路不同于现有加密算法，加密过程可以做到一次一密，且分组长度可调，可有效对抗现有的密码分析手段，有着更好的安全性。置换表计算完成后，加密过程只需简单的置换操作，加解密速度快。但该算法目前尚处于理论阶段，急需应用到现实系统中进行检验。

 

 

图1 基于Petri网的加密算法框架

        基于Petri网的加密算法框架如图1所示。Petri网分组加密算法中，存在着大量的矩阵运算、乘法运算和排序运算。在取分组长度为9的情况下，加密算法大致需要60万次整数的加法、乘法和比较运算。这是现代通用计算机在1秒内的计算量。而经过测试，在2.40GHz的双核CPU台式机上，Petri网的关联矩阵为4×6矩阵，l₁为1，l₂为7，计算置换表一次所花的时间为10ms，而在使用低速CPU的嵌入式设备上速度将更慢，这是没法忍受的，也限制了该算法的在嵌入式系统中的实际应用。但是本加密算法在理论上已经成熟，其功能、算法日趋稳定，软件本身运行带来的性能损耗已很难再依赖改进算法本身来降低。因此，通过重新划分软硬件功能，将加密算法中公用的、耗时、运算量大的相关操作用硬件实现，是解决问题的关键所在。

       本题目针对该加密算法，分析其各个过程的执行时间，找出性能瓶颈，并对计算量大的部分作硬件化处理，大幅降低算法本身运行的时间。在Altera的FPGA器件上，利用SoPC技术，搭建以Nios II为核心，以加解密模块为从设备，可以进行网络通信的系统，在uClinux操作系统下，整体上使软硬件协调工作，将文件加密后通过网络传输到PC端，实现加密传输。

适用范围及用户群

       本设计所使用的的加解密算法，算法破解难度大，密钥公开传送部分传输量小，适用于文件加密、数据流加密、各种商业的保密传输系统。同时为理论算法的硬件化提供借鉴。该算法硬件化的开发及推广和使用，必然会推动我国信息安全领域的发展，进而带来很大的经济效益。

本设计采用本款Altera器件设计的原因

1. 该加解密算法硬件加速需要进行大量的运算与逻辑资源，结合实验室购买了40套DE2-70开发板，所以该设计选择的FPGA芯片为Cyclone II EP2C70。该芯片逻辑资源丰富，拥有高达70,000个逻辑单元，250个M4K RAM块，150个乘法器等。DE2-70开发板上具有大容量的内存组件（64MB的SDRAM，8MB的FLASH），丰富的多媒体、通信、网络及存储器等应用接口，可以进行深入的功能开发。
2. 开发工具齐全。Altera除了提供基本的综合、布局布线工具，还提供了与其他优秀EDA软件的接口，方便调用。
   
3. Altera公司的SoPC工具提供性能优良的CPU NIos II，且开发环境界面友好，可通过简单的操作搭建性能优良、复杂、稳定的系统。这给开发者更多的精力用于专注于加密算法的硬件研究。
4. Altera公司提供大量IP（知识产权）可供使用，且可使用GUI和配置文件配置各类IP，给设计带来方便。
5. 文档、教程丰富，且有良好的解答技术问题的渠道。
   

(Revision: 7 / 2009-06-15 09:02:05)

2. 功能描述 (Final Project Paper)

2.1 基本功能

        基于petri网的分组密码加密算法是最近提出的一种新型的算法，通过软件建模仿真，发现其在嵌入式系统中运行速度非常慢，对该算法进行硬件化就有了必要，并可以推广在实际中应用。

        本设计搭建SoPC+uClinux测试平台，实现计算置换表、对文件加密和解密等功能。由Nios II 送初始数据到自定义的IP核，完全由硬件计算置换表；移植uClinux并实现网络功能，配置网络后使用NFS服务传输文件；对文件实现加密和解密，并将密钥中可以公开传送的部分加在加密文件头中。

2.2 功能实现的模块

（1）加解密置换表生成模块

        通过输入初始矩阵A、初始向量M0，运行Petri网，得到可达标识集Mx  用户可以输入一个数（L1）来确定进行排序的Mx并根据生成顺序进行编号 ，然后对可达标识集Mx进行排序，由排序前后可达标识Mx的序号生成置换表，即为算法的加解密置换表。由于每次输入的L1，M₀是变化的，所以参与排序的Mx也是每次都不一样，因此该算法是一次一密的。

（2）文件加解密模块

        通过网络读入需要加解密的文件到SDRAM中，DMA主读端从SDRAM中读取数据，根据加解密置换表对数据进行加密或解密，DMA主写端把数据写回SDRAM。

（3）终端显示模块

        本系统基于Linux主机和DE2-70客户机进行系统设计。通过UART串口以及串口终端完成对系统的操作以及系统处理信息的显示。

 

(Revision: 2 / 2009-09-13 22:13:40)

3. 性能参数 (Final Project Paper)

3.1 系统资源利用情况

3.1.1系统整体资源利用情况如图3.1所示

 

图3.1 系统整体资源利用情况

 

3.1.2 自定义petri网加解密模块资源利用情况

 P&R后资源利用情况如图3.2所示

图3.2 petri网加解密模块资源利用情况

3.2 分组密码算法硬件加速前后的性能参数

3.2.1 算法各部分的执行时间

由上表可知：在Nios II + uClinux上纯软件实现时最耗时的操作是Petri网运行时生成可达标示集Mx，大约占83.87%，最后生成加解密置换表的时间是18352ms。在对关键模块进行硬件加速后，在同样的Nios II平台上仅需要41.90ms。大大提高了加解密置换表的生成时间，提高了加解密模块的性能。

表3-1 不同平台下算法各部分执行时间

Module	PC （Intel(R) Xeon(R) CPU E5405@ 2.00GHz  4核4G内存		NiosII+uClinux （SW） 100MHz，4Kb 指令cache，2Kb数据cache		NiosII+uClinux（HW+SW） 100MHz，4Kb 指令cache，2Kb数据cache
	Time（ms）	Rate	Time（ms）	Rate	Time(ms)
sum_next_ mtvs time	1.692	83.87%	15524	84.77%	41.90
sort_Mx time	0.121	5.98%	1224	6.66%
Index Mx time	0.000084	0.004%	1.12	0.006%
Sum mtvs time	0.007	0.35%	73	0.40%
calc_subs_table  Total time	2.017		18352

3.2 .2 对文件加解密操作的性能参数

表3-2 加密不同大小文件所需时间及计算置换表所占比重

Module	PC（Intel(R) Xeon(R) CPU E5405  @ 2.00GHz  4核4G内存）		NiosII+uClinux （SW） 100MHz，4Kb 指令cache，2Kb数据cache		NiosII+uClinux （HW+SW） 100MHz，4Kb 指令cache，2Kb数据cache
	Time (ms)	Rate (%)	Time (ms)	Rate (%)	Time (ms)	Rate (%)
20K	10.95	18.42	22472	81.67	160	11.47
40K	11.45	17.62	25938	70.75	179	10.25
60K	12.00	16.80	29431	62.36	201	9.13
80K	12.60	16.01	33128	55.40	221	8.30
90K	13.05	15.46	35235	52.08	230	7.98
2M	72.25	2.79	378380	4.85	1982	0.93

 

表3-3 解密不同大小文件所需时间及计算置换表所占比重

 

Module	PC（Intel(R) Xeon(R) CPU E5405  @ 2.00GHz  4核4G内存）		NiosII+uClinux （SW） 100MHz，4Kb 指令cache，2Kb数据cache		NiosII+uClinux（HW+SW） 100MHz，4Kb 指令cache，2Kb数据cache
	Time(ms)	Rate (%)	Time(ms)	Rate (%)	Time (ms)	Rate (%)
20K	11.05	18.25	22761	80.63	161	11.40
40K	12.00	16.80	28847	63.56	180	10.20
60K	12.05	16.74	32487	56.49	201	9.13
80K	13.00	15.52	35849	51.19	220	8.34
90K	13.10	15.40	37491	48.95	232	7.91
2M	74.10	2.72	381340	4.81	1900	0.97

 

 

          通过上表可知：在加密和解密中，随着文件的增大，计算置换表占对文件加解密操作的比例越小。这是因为置换关系只在加解密算法开始时计算一次，随后对数据的加解密操作最终简化为置换操作，因此可以得出，本分组密码算法对大数据量加解密时时效率更高。

 

3.2.3 不同大小文件加解密的性能参数

本设计最后对比密码算法在硬件加速前后的性能，对不同大小文件操作20次所需时间参数如图3.3和图3.4所示：

 

 图3.3  20次软件加解密时间

图3.4 使用硬件和DMA后，20次加解密文件时间

由图可知：在Nios II + uClinux上纯软件对20K的数据加密20次需要449.44秒，约为0.89KB/s，而同样的平台上，硬件加速后仅需要3.21秒，约为124.61KB/s，性能提高140倍。当加密文件达到2M，加密20次时所需时间分别为7626秒、38秒，速度分别为5.37KB/s、1078KB/s。性能提高200余倍。因此可以得出：一是硬件加速后性能得到很大的提高，在140倍以上；二是文件越大，性能提高的倍数越大，这也再次说明了本分组密码算法对大数据量操作效率更高。

(Revision: 2 / 2009-09-13 21:53:02)

4. 设计结构 (Preliminary Paper)

       本系统的总体设计如图2所示。本设计将建立以Nios II为核心的基本的嵌入式开发平台，并移植uClinux操作系统。设计基于Petri网的分组加密算法专用硬件，通过SoPC提供的定制指令功能对该硬件进行操作。为便于开发和增强可移植性，将开发该硬件在uClinux上的软件驱动，设计接口函数供应用程序调用。

图2 系统总体设计图

       硬件设计框图如图3所示。其中Timer用于测试程序执行时间，可评价自定义加密模块的性能。为降低CPU在读取大文件时的负担，设计了输入输出buffer用于提高加密的速度。

图3 SoPC硬件结构

       该加解密算法的输入部分包括Petri网的关联矩阵、初始标示M₀、素数向量P_m和分组长度k。算法首先对输入部分进行初始化，确定分组长度k。然后计算（level+1）级的M_x ，这是关键函数，用于计算指定level级的下一级M_x 。算法要求选择两个level之间的M_x 来排序，且此两个level之间的M_x 个数个满足：2^k<=|R(M₀)|_[l1,l2]|<=2^k+1 ，从而确定l₁与l₂。根据M_x 计算V向量，它是T向量中t_i的个数组成的向量。将每一个MTV结构中T域中的t_i出现的次数数出来。随后计算 M向量对应的A_SM值，按值得从小到大排序并对其进行二进制编号。同时对V向量按对角线序排序并进行二进制编号。从而得到M与V向量编号的一一对应关系。根据序号对应关系，对明文分组置换，完成加密算法。加密流程如图4所示。

图4 加密流程

 

       解密过程类似加密过程，区别是：

1. 解密时，M₀不是初始给定，而是通过A_SM₀与P_m计算得到，P_m已知，P_m是从加密后的数据流中得到的。
2. 解密时，最大计算的级数就是l₂，也是在加密后的数据流中得到的。
   
3. 解密时，需要计算V向量与M向量的对应关系，得到V向量与M向量置换值表。
   

       解密过程中的其他操作，如Petri网运行、M向量排序等操作均同加密过程，在此从略。

       经过软件测试，在加密过程中，计算Mx所耗的时间最长，占到全部的98%，也就是说这部分运算是加密算法的性能瓶颈。对这部分运算进行硬件化，就有了必要。

       考虑到后面的运算多为排序和置换操作，硬件设计难度不大，为减轻程序设计的复杂度，故将后面的操作也做了硬件化处理。

     图5为对文件加密的过程：

 

 

图5 对文件加密流程

       如果对明文只是简单做置换操作，体现不出该算法一次一密的特点。所以在加密文件的过程中，加密一定长度的明文后，要更换密钥一次，增加加密强度。

       最后通过网络验证该算法在实际应用中的可行性。过程如图6所示。

 

图6 使用网络传输密文

       将经过加密后的文件，通过网络传输到PC机上。在PC机上，使用C++语言编写解密程序，读入密文并解密，实现密文传输。
       该过程也可反方向运行，由PC机加密，开发板端解密。

(Revision: 7 / 2009-06-15 09:04:46)

5. 设计方法 (Final Project Paper)

5.1 最终搭建的SoPC平台

   如图5.1所示：

                                       图5.1 SoPC平台 

    其中nios II使用fast类型，指令cache为4kB，数据cache为2kB。两个timer，一个用于普通的定时器，另外一个用于测量软硬件的运行时间。使用DM9000A，在uClinux上要使用网络来传输文件。

5.2 硬件设计

5.2.1 Petri网加解密的总体设计

    对文件加密或解密之前首先要得出置换表，这个工作主要有自定义的模块完成。

    该模块的运行过程如图5.2所示：

 

 

 

图 5.2 加解密基本流程

 

    假定初始标识M₀ 为[1 0 1 0 0 0]^T，通过petri网的运行，得到一个唯一可达标识图。如图5.3所示：M0~M16组成可达标识集。

图 5.3 计算可达标识集

5.2.2 硬件加速设计的难点

   （1）中间数据量大。

    在本硬件中，排序前需要存储16×512 + 16 × 512 × 3位数据。其中前半部分为可达标识，后半部分为用于排序的序号。这么多数据，如果使用寄存器将浪费太多的资源。这里使用RAM，将每次计算得出的数据作为一组存入RAM。

   （2）时序复杂

        

        在计算过程中需要不断的比较。在计算可达标识时，需要比较是否已经有相同的可达向量已经计算出来；后面还要大量的向量比较。这么大量的运算，使用并行逻辑将占用太多的LUT资源，而且过程控制不容易，并且会出现过长的最差路径，使最差时间变长。

本设计中，使用状态机控制各个流程，虽然状态比较多，但控制容易，运行的最高频率也可提高。

5.2.3 加解密模块的IP核设计

 计算出置换表后，可以使用DMA方式进行加密。加密模块整体框图如图5.4所示：

图5.4 加密模块的整体框图

 

 该图中首先通过avalon总线输入初始信息生成置换表，然后送被加密文件的起始地址、长度、加密后文件的起始地址等控制信息到DMA Control（DMA控制器），DMA Control将控制DMA Read Master从相应的地址内读取数据，通过置换模块加密后送到DMA Write Master中的FIFO，在由DMA Control控制DMA Write Master将加密后的数据写到相应的位置。

5.3 文件加解密操作

    对文件加密的流程如图5.5：

                                       图 5.5文件加密流程

 

解密流程如图5.6：

 

                     

                       图5.6 解密流程

 

(Revision: 3 / 2009-09-13 22:22:42)

6. 设计特点 (Preliminary Paper)

设计特点

1.  将纯理论的基于petri网的加解密算法根据硬件特点进行再设计，提高加解密速度；
2. 使用Nios II自定义指令来运行该加解密模块，并编写其在uClinux下的驱动，可对文件或其他数据流进行加密；
   
3. 利用该算法可一次一密的特点设计程序，对单个文件进行分段单独加密，增加破解难度；
   
4.  密文、密钥公开传送部分单独传送，提高加密强度。
   

(Revision: 5 / 2009-06-14 22:23:50)

7. 总结 (Final Project Paper)

在科研中，由算法到实际应用是有很大的距离的。我们希望能够在短时间内，搭建稳定可靠的测试和试验平台，集中精力完成核心算法部分，Altera公司的SoPC builder软件提供了这样一种平台。其提供的丰富的IP模块可灵活方便的搭建各种平台，我们只需要按照avalon接口协议完成自定义模块，就可以方便的调试以及测试性能。在这个过程中，也逐渐认识到对FPGA、CPU架构、软件编译了解的不够。

    我们也体验到了团队合作的重要性，由专攻方向不同的同学组成的小组，可以高效并且比较全面的完成任务。我们一起讨论、一起进步，完成我们共同的目标，并为以后的团队合作提供宝贵的经验。

        FPGA器件高度灵活的特点，可以让我们的各种想法快速实现，并很快的加入系统中。FPGA是个很有趣的领域，我相信我们以后会继续关注和使用它。

 

 

(Revision: 2 / 2009-09-13 21:45:33)