基于显式并行指令计算结构的密码算法设计

目前，在多数保密通信没备中，主要采用通用CPU和专用硬件电路控制密码专用芯片来实现两种方式的密码运算。采用前者控制密码专用芯片时，需要选用一种具有灵活性高、维护容易、升级方便等特点的性能优良的通用微处理器GPP(General Purpose Processor)，但由于通用微处理器指令的局限性，使密码专用芯片达不到其最佳性能，严重影晌了保密通信的速度；采用专用硬件电路直接控制密码专用芯片，虽然可使密码专用芯片的性能达到最高，但由于其功能只依赖于密码专用芯片及其外围器件，使得灵活性差、开发周期比较长。

    由此可见，无论采用上面哪种方式，由于密码专用芯片的运算处理与控制分离，限制了密码数据处理性能，制约了系统整体速度。针对上述问题，通过分析多种密码算法，本文提出一种基于处理器设计思想的显式并行指令计算结构(EPIC的可编程密码处理器架构，实现了速度与灵活性的折衷。  

1 密码算法分析  

1.1 典型的密码算法及其应用  

    现针对七种分组密码算法和两种杂凑函数即DES、IDEA、Rijndael、RC6、Serpent、Twofish、Mars、MD5和SHA进行分析。  

    分组密码算法是一个将比特明文映射成n比特密文的双射函数，n为其分组长度，它的加密与解密过程具有相同的密钥，因此又称为对称密码算法。而杂凑函数是一种将任意长度的消息压缩为某一固定长度的消息摘要的函数，它主要用十数字签名、消息的完整性检测和消息的起源认证检测等方面。  

    DES算法(数据加密标准)是第一代公开的完全说明实现细节的被世界公认的分组密码算法。其最初设计者是IBM公司，并取得了它的专利权。在随后的二十多年中，DES算法作为一种典型的分组密码算法，被广泛地应用于保护商业数据的安全(如银行系统等)。  

    IDEA算法(国际数据加密算法)公布于1992年，足IPES标准，因广泛应用于email加密认证软件(PGP)中而闻名。  

    Riindael是1998年公布的，并于2000年在由NIST(美国国家标准技术研究所)主持的AES评选中获胜，此后Rijndael算法也称为AES算法，成为逐渐代替DES的新的加密标准。  

    RC6、Serpent、Twofish和Mars算法是与Rijndael算法一起参评的AES候选算法，它们都不同程度地体现了分组密码算法的设计原则，对应用密码学的发展产生了相当大的影响。  

    MD5消息摘要函数是由RSA算法的设计者之一Rivest提出的一种单向散列函数，它不基于任何假设和密码体制，采用了直接构造的方法，处理速度非常快。  

    SHA是1993年公布的联邦信息处理标准(FIPS-180)的安全散列标准，由NIST提出并于1995年推出了其修订版，通称为SHA-1。  

1.2 密码算法中的基本操作  

    在分析上述算法的基础上，提取出各个算法的核心操作类型，并总结出它们的基本操作分别为以下六类：S盒操作、比特置换操作、算术运算、逻辑运算、移位操作和有限域乘法运算。其中算术运算包括模加／减和模乘运算，逻辑运算则由‘与 i、‘或 i、‘非 i和‘异或 i组成，表1详细列出了它们在各种算法中的具体应用，如DES算法中主要使用了S盒操作、比特置换、异或和移位操作。  

 

2 可编程密码处理器体系结构设计  

    在典型的可编程密码处理器结构(AFPC)中，EPIC结构开发的是标量操作之间的随机并发性，并且增加了功能部件的个数。不相关的指令由编译显式地编入到一个超长的机器指令字中，并发射到流水线，在各个功能部件中并发执行，指令级并行度为4～8。这种结构的硬件控制相对简单，在计算密集型应用时内在并行性很明显。且不需要很多转移预测。在这种结构上运行指令能够达到较高的实际指令级并行度。正是由于以上特点，EPIC结构在很大程度上符合了密码算法的需求，即计算密集且顺序执行。  

    可编程密码处理器体系结构的硬什结构如图1所示，整个处理器包括三部分：数据通路、控制单元和输入／输出接口电路。 

 

   

数据通路是处理器的关键部件之一，包含FUO～FU5共6个可并行执行的功能单元、32个32bit通用寄存器、4×32个32bit密钥寄存器和回写单元。  

    功能单元是处理器执行指令运算的核心，由若干个密码运算模块组成。其中，FUO～FU3内部运算模块的组成与结构完全相同，输入为3个32bit运算数据，其中2个来自通用寄存器堆、1个来自密钥寄存器堆，输出的运算结果亦为32bit。FUO～FU3内部分别设置了7个运算模块，分别为S盒运算模块、模加，减运算模块、模乘运算模块、32bit移位运算模块、有限域乘法运算模块、二输入逻辑运算模块、三输入逻辑运算模块。FU4内部设置了1个128bit，置换运算模块，输入为12个32bit运算数据，其中8个来自通用寄存器堆，4个来自密钥寄存器堆。FU5内部设置了1个128bit移位运算模块，输入也为12个32bit运算数据，其中8个来自通用寄存器堆，4个来自密钥寄存器堆。  

    上述这些运算模块功能不是单一的，而是可重构的。表2中给出了4个可重构运算模块所支持的模式。  

    除了上述运算模式可重构外，各运算模块根据具体情况还支持运算前增加‘异或 i操作、运算后增加‘异或 i操作或者运算前后都增加‘异或 i操作。由于‘异或 i操作延时很小，它的加入并不影响运算的关键路径，这就使得密码运算时减少了单一‘异或 i操作的时钟，从而减少了整个运算的时钟数，并且不影响整体性能。表3中给出了Rijndael算法轮运算流程，采用有限域乘法运算后加入‘异或 i操作，时钟周期数由4减为3，10轮运算将减少10个时钟周期。  

    控制单元完成指令存取、指令译码、指令存储器地址生成等工作，协调处理器内部指令与外部用户命令正确执行。  

    输入／输出接口电路包括16个32bit输入寄存器、16个32bit输出寄存器、4个数据 长度计数器、1个32bit命令寄存器等，完成指令、运算数据从32bit数据总线装载到指令存 储器和输人寄存器以及运算结果从内部通用寄存器写入输出寄存器等操作。  
3 指令系统设计

    指令系统是算法要素和密码处理器体系结构特性的集中体现，指令系统的设计必须支 持硬件的并行执行，即开发指令级并行性(ILP)，指令级并行性的开发程度对发挥密码微处理器的硬件特性，提高程序运行性能至为关键。ILP技术实际上是指一套完整的处理器设计和编译技术，这些技术通过并行地执行独立的机器操作(如存储器读写、逻辑运算、算术运算等)来加速程序的执行。ILP的大小可以采用每周期平均执行的指令数(IPC)朱衡量，或者采用整个程序的每条指令平均执行的周期数CPI(CPT=l／IPC)来衡量。在可编程密码处理器体系结构中采用了显式并行指令计算结构，指令级并行数达到5。   

 

 

3.1 指令分类  

    可编程密码处理器体系结构中的指令分为以下几类：  

(1)静态配置指令。它是在密钥生成及加／解密过程中保持不变或者改变次数很少的控制信息配置指令，算法确定后，其S盒查找表信息、有限域乘数矩阵和不可约多项式、若干个置换的控制信息等就确定了，它们不会因为操作模式不同而改变。在加／解密过程中采用将配置指令分离出来的方法，可以大大减少执行密码运算时指令的冗余编码，从而缩短了指令字的长度，增加了运算指令字中包含有效操作的个数，有效地提高了加／解密速度并减少了密码程序的代码量。  
(2)短指令。它执行除置换与128bit移位运算外的各种密码运算和内部寄存器问的数据传输操作。  
(3)长指令。它执行置换与128bit移位运算。  
(4)超长指令。它执行立即数操作和多分支判断操作。  
(5)控制指令。它执行程序跳转、子程序调用及返回、单分支判断等控制操作。  

3.2 指令形态  

   在硬件上，多个功能单元的设置为多条指令的并行执行提供了支持，而哪些指令可以并行执行，哪些指令不能并行执行以及如何将多条指令组装成一条指令的原则，即称为指令的拼装规则。在此设计中有以下几种指令形态：  

(1) 静态配置指令。  
(2) 超长指令。  
(3) 短指令Ⅱ短指令Ⅱ短指令Ⅱ短指令ll控制指令。  
(4) 长指令Ⅱ控制指令。  

     其中短指令长度为37bit，控制指令长度为32bit，长指令长度为148bit。无论上述哪种形态，最终的指令字长度都为192bit(包括指令拼装标识)，如四个短指令可以与控制指令拼装成一条指令，长指令也可以与控制指令拼装成一条指令，但静态配置指令与超长指令不能与其他指令拼装，自身组成一个192bit的指令字。  

4 性能分析  

    由于可编程密码处理器体系结构支持5条指令绑定并行执行，因此其数据路径定义为5CS(5Combining-Strands)，假设不采用绑定的数据路径定义为NCS(No-Combining-Strands)，将这两种情况与Alpha处理器、Cryp-toManiac密码处理器[9]路程进行比较，四种数据路径下加／解密所需时钟数如表4所示。分析比较表明可编程密码处理器执行时钟大量减少，尤其与通用处理器Al-pha相比，加／解时钟数DES算法减少83％，IDEA算法减少92％，Rijndael算法减少9l％，RC6算法减少69％，Twofish算法减少78％。   

  

   为了验证可编程密码处理器体系结构实现数据通路和控制通路的正确性，使用Altera StratixlIEP2S180F1508C4器件作为FPCA目标芯片，使用AlteraQuartusII 5.0工具进行综合，在综合前和综合后使用Mentor公司的ModelSim 5.8c分别进行功能仿真和时序仿真，结果均正确。其具体资源占用情况如表5所示。   

  

    密码处理的灵活性和高效性一直是密码算法使用中的制约因素，采用通用微处理器虽然能获得较好的灵活性，但却使一些算法的性能达不到要求；采用专用算法芯片，在获得很高性能的同时丧失了灵活性。本文针对这一矛盾以EPIC结构微处理器构架为出发点，系统地研究了通用的并行分组密码处理器模型、各种密码运算单元、指令集等关键技术，并最终得以实现，达到了实现性能与灵活性之间的良好折衷。