（通信与信息系统专业论文）高级加密标准的简洁紧凑型硬件实现.pdf

武汉理工大学硕士学位论文 摘要 高效、可靠、简洁紧凑型的高级加密标准( a l e s ：a d v a n c e de n c r y p t i o n s t a n d a r d ) 算法实现系统，是非常适用于未来低端小型的嵌入式应用的。本文设 计和实现了一套完整的紧凑型a e s 算法加密和解密系统。 基于0 1 8 岫c m o s 技术，研究了各种类型的紧凑型a e s 系统结构。首先， 探索了一种新的a e ss - b o x 的硬件数字实现方案。这种新的实现方法正是基于 a e s 算法中s - b o x 输出的布尔函数具有线性冗余性的新发现。虽然新的电路系统 的面积非常小，但同时系统的速度也减慢了。 在s - b o x 研究结果的基础上，完成了一套完整的a e s 加密解密系统。实现 了不带密钥扩展的循环结构的加密系统，并且分别将三种不同的简洁紧凑型 s - b o x 运用到这个结构中。在比较了六种实现方案的结果后，发现利用四个基于 g f ( 2 4 ) 域算术运算的s - b o x 的实现方案在速度和面积的平衡方面做得最好。因 此，基于这样四个g f ( 2 4 ) 域算术运算的s - b o x 的实现方案下完成了一套完整 的，带有密钥扩展的、简洁紧凑型的、a e s 加密解密系统。 最后实现的a e s 加密解密系统电路面积最小只需要7 5 k 电路门，数据通道 延迟为1 9 2 6 n s ，系统的最高时钟频率为5 1 9m h z ，数据输出率为1 3 2 9 2m b p s 。 关键词：高级加密算法，硬件实现，加密，解密，嵌入式应用 武汉理工大学硕士学位论文 a b s t r a c t ac o m p a c t ，e f f i c i e n ta n dh i g h i yr e l i a b l ei m p l e m e n t a t i o no ft h ea d v a n c c x i e n c r y p t i o ns t a n d a r d ( a e s ) i st h ed e s i r a b l ee n e r y p t i o nc o r ef o ra n yp r a c t i c a ll o w - a n d e m b e d d e da p p l i c a t i o n i nt h i st h e s i sw ed e s i g na n di m p l e m e n tac o m p a c th a r d w i l r e a e s e n c r y p t i o na n dd e c r y p t i o ns y s t e m w ei n v e s t i g a t ev a r i o u sa r c h i t e c t u r e s f o rc o m p a c ta e si m p l e m e n t a t i o n si no 1 8 i l mc m o st e c h n o l o g y w e f i r s t e x p l o r ean 洲c o m p a c td i g i t a l h a r d w a r e i m p l e m e n t a t i o no ft h ea e ss - b o x e sa p p l y m gt h ed i s c o v e r yo fl i n e a rr e d u n d a n c yi n t h ea e ss - b o x e s a l t h o u g ht h en e wc i r c u i th a sas m a l ls i z e ，t h es p e e do ft h i s i m p l e m e n t a t i o ni sa l s or e d u c e d e n c r y p t i o na r c h i t e c t u r e sw i t h o u tk c ys c h e d u l i n gt h a te m p l o yf o u rs - b o x e sa n d o n l yo r es - b o xa r ei m p l e m e n t e au s i n gt h en e wa e ss - b o x e s ，a sw e l la sb a s e do n o t h e rc o m p a c ts - b o xs t r u c t u r e s t h ec o m p a r i s o no ft h ei m p l e m e n t a t i o n sb a s e do i l d i f f e r e n ta r c h i t e c t u r e sa n ds - b o xs t r u c t u r e si n d i c a t e st h a tt h ei m p l e m e n t a t i o nu s i n g f o u rs - b o x e sb a s e d0 1 1a r i t h m e t i co p e r a t i o n si ng f ( 2 4 ) h a st h eb e s tt r a d e - o f fo fa r e a a n d s p e e d t h e r e f o r e ，u s i n g t h i ss - b o x i m p l e m e n t a t i o n , a c o m p l e t e e n e r y p t i o n - d c c r y p t i o na r c h i t e c t u r ew i t hk e ys c h e d u l i n ge m p l o y i n gt h ef o u rs - b o x s t n m m r ei si m p l e m e n t e d t h ec o m p l e t ec o m p a c te n e r y p f i o n - d e c r y p f i o ns y s t e mh a sas m a l ls i z er e q u i r i n g a b o u t7 5 kg a t e sa n dt h et h r o u g h p mo f t h ec i r c u i ti s1 3 2 9 2m b p s k e y w o r d k ：a d v a n c e de n e r y p t i o ns t a n d a r d ，h a r d w a r ei m p l e m e n t a t i o n , e n c r y p t i o n , d e e r y p t i o n , e m b e d d c da p p l i c a t i o n 武汉理工大学硕士学位论文 第1 章绪论 我们生活在迅速发展的信息时代。从最早的现代电讯发明电报，到当 前的高速网络，信息时代带来了经济的飞速成长和科技的不断革新。而科技发 展促成整个世界的社会变革。电报使得远距离的文本信息传递成为现实；而电 话让远距离语音通讯成为可能；广播和卫星电视让我们的娱乐生活变得丰富多 彩；无线通信，比如移动电话，让我们可以随心所欲的和远在万里的人通话； 因特网的出现带给人类全新的生活方式。人们通过遍及世界的计算机网络传递 声音，视频和文本消息，甚至库存清单，财务报表和其他商业数据。当然人们 也通过网络来查找他们需要的信息。大众越来越习惯用方便快速的电子邮件代 替传统纸质邮件来互相联系。而所有的信息都被转为更利于传输和储存的电子 数据。通信服务的形式越来越多，甚至每天都有新的服务方式出现；而与此同 时人们对通信服务的要求也越来越高，越来越多。 随着现代通信服务越来越深入到人们的日常生活中，信息安全也变得越来 越重要。当人们使用因特网传递私人信息的时候，他们不想让其他人获得这些 数据。尤其是在商业公司，军事部门和政府机关中，必须确保机密文件和敏感 数据的安全和保密。信息安全正是研究这一领域的学科。 在现代电子通讯应用中，嵌入式系统应用越来越受到市场和业界的欢迎。 据估计，信息技术市场对嵌入式c p u 的需求大概是通用c p u 的l o 倍。所谓嵌 入式系统就是封装在由他控制的电子器件中，以应用为导向的特殊系统。随着 集成电路设计和制造技术的迅速发展，许多如p d a ，移动电话等消费类通讯电子 产品都开始成为嵌入式系统应用。绝大部分的嵌入式系统都应用在面积要求严， 速度要求一般的系统中，从而达到降低整个系统成本的目的。因此，对低端的 嵌入式系统的应用中最重要的就是减小面积，降低成本。和其他通讯电子技术 一样，通讯安全也是嵌入式应用的一个重要方向。因此，本文主要论述的就是 如何设计和实现一个既能满足客户对芯片面积和成本要求，又能提供信息安全 保障的紧凑型加密解密硬件电路。 本章将概要介绍一些和本研究相关的信息安全，密码和硬件应用实现的背 景知识，以及研究的初衷和目标。 武汉理工大学硕士学位论文 1 1 信息安全 最早关于信息安全的纪录大概可以追溯到四个世纪前。古人利用不同的方 法来隐藏秘密信息。例如，人们用柠檬汁和洋葱汁制成看不见的墨水写信。这 种墨水对热非常敏感，于是当信纸被加热以后新的内容立刻就显现出来t i l l 。 还有用针在被选中的字符上打出小孔办法，从而使得只有把信笺对着光才能看 到信的真实内容。同样也被记录在案的还有例如用整封信的每个单词或每一行 的首字母来隐藏秘密信息。直到今天我们仍有利用这些古老技术的现代加密产 品。 密码加密术被用来确保秘密信息的安全已经有很长的时间了。英美军队在 第一次世界大战中就已经广泛使用从古老的凯撒密码到p l a y f a i r 密码了，以及德 军在第二次世界大战中使用赫赫有名的三转子e n i g m a 密码机，过去密码加密术 主要应用在军事情报方面【l 】。而现今，在现代通讯技术中，我们利用密码加密术 给需要传递的信息加密以确保信息的安全。与试图隐藏信息存在性的古老隐写 术【l 】不同的是，密码加密术应用不同的数学算法将需要加密的信息转换成密码文 本。即使被对手获得加密文本，他们也不能计算出有用信息，因而确保信息传 送的安全。 密码加密技术可以为通信网络确保数据的保密性，完整性，可验证性和不 可否认性【1 1 。保密性是到防止传输的数据遭到偷听和控制。并且防止流量分析， 这要求攻击者不能观察到信息的源和宿、频率、长度或通信设旌上的其他流量 特征。数据的完整性保证收到的消极和发出的消息的一致性，没有复制、插入、 修改、更改顺序或重放。可验证性是在消息发出后，接收方能证明消息时由声 称的发送方发出的。同样，当消息接收后，发送方能证明消息事实上却是由声 称的接收方收到了。不可否认性可以防止发送方或接收方否认传输或接收过某 条消息。各种加密机制和算法交叉应用，从而提供了各种各样的安全服务。 1 1 1 对称密钥加密系统 对称密钥加密是接收方和发送方在传输中用一个相同的密钥的加密系统。 发送方和接收方必须通过某种安全渠道获得和交换密钥或者由第三方来分配密 钥来保证密钥的安全。发送方使用这个密钥来加密消息而接收方也使用同样密 钥来解密它。我们也必须保证在没有密钥的情况下，即使敌人已知密文和加密 解密的算法，他也无法破译消息。 如图1 1 所示i l j ，在发送方把消息从信息通道传输之前，他应用加密算法e 和密钥k 将原文p 加密成密文c 。这个变换过程是c = e k ( p ) 。接收到密文后， 2 武汉理工大学硕士学位论文 接收方利用相对应的解密算法d 和相同的密钥k 将密文转换为原文p 。这个过 程是p = d k ( c ) 。即使敌方捕捉到传输中的密文c ，并且知道这个安全系统所用 的加密算法，他依然无法在不知道密钥k 的情况下破译消息。因此，这种安全 系统的安全性依赖于加密算法的鲁棒性。 图1 1 对称钥匙加密系统 对称加密技术通常是基于最基本的加密变换：替代和置换。代替和置换的 应用使信息混淆和扩散 2 1 。按照s h a n n o n 最初的定义，混淆是指使密钥和密文的 信息混淆在一起，越乱越好。扩散是指将原文中信息的冗余概率完全分布到密 文信息的概率中去。 1 1 1 1 分组密码 分组密码是一种每次只处理一组原文的对称密钥加密系统。一组原文当作 一个整体来产生一段相同长度的密文。解密过程与加密过程相似，只是使用了 相应的解密算法。分组密码的过程如图1 2 所示。 s 删l 锄 图1 2 分组密码 3 j 瞄又理工大学硕士学位论文 1 1 1 2 流密码 流密码是以元素为单位通常是一位一位的) 连续地对原文进行加密，并 且也是一位一位的产生密克通常流密码需要一组随机产生的密钥流来与原文 一位一位地进行异或。这些童机的密钥流可以完全破坏消息中的任何概率统计 规律。对于流密码来说，解畜过程和加密过程是完全一样的。流密码系统如图 1 3 所示： , s e a mk e y j 图1 3 流密码 v e m a m 密码旧和r c 4 密玛眦是二种众所周知的流密码算法。r c 4 算法被广 泛地使用在s s l t l s ( 安全葺层，传送层安全) 标准中。这两种标准在网页浏览 器和服务器通信中有定义。誓4 算法也被用在w e p ( 电线等价保密) 协议中， 这个协议是i e e e 8 0 2 1l 无盹局域网标准【1 】的一部分。 ， 1 1 2 公钥加密系统 公钥加密系统的发明在骞码学上是一个重大的突破，因它与以前传统的对 称密钥密码有着很大的不同在公钥加密系统中，传输双方每一个人拥有一对 密钥。这一对密钥是完全不嗣的，但它们又是相互联系的。其中一个被称为公 共密钥，另一个被称为私人塞钥。双方分别将自己的私人密钥秘密保存，并且 把自己的公共密钥发给所有与他通信的人。这就意味着私人密钥是只有拥有者 知道的密钥，而公共密钥是新有在网络上通信的人都可以知道的。这一对密钥 有一个很特殊的特点，那就鼍被其中任一个密钥加密的消息都可以通过另一个 密钥解密。所以在通信的过翟中，接收方和发送方使用不同的密钥进行加密盒 解密。接收方和发送方谁用蠢人密钥，谁用公共密钥，这些都是由通信系统中 甲 武汉理工大学硕士学位论文 的安全目标所决定的。 假如通信系统中的信息是按照图1 4 中所示的方式来保密的【1 1 ，发送方必须 在发送消息之前用接收方的公共密钥k u r 进行加密。因为只有接收方知道自己 的私人密码k r r ，并且只有用这个私人密码才能把密文解密成有用的信息，从而 实现了整个机密系统保密的功能。而当通信系统以验证作为安全的目标是，如 图1 5 所示i l j ，发送方得用自己的私人密钥k r r 加密，而当接收方用发送方的公 共密钥k u r 去解密成功的话，接受方就可以确定这条消息确实是经过验证的发 送方所传送过来的，因为只有用发送方的私人密钥加密的密文才能用与其相对 应的公共密钥解密开。在这两种情况下，敌方即使获取了密文并且知道了加密 和解密算法，甚至知道了公共密钥，也无法计算出或推理出私人密钥。 图1 4 公钥加密系统 公钥加密系统比传统的对称密钥加密系统有着非常大的优势。公钥加密系 统中不存在对称密钥加密系统中交换密钥的问题。由于在公钥加密系统中接收 方和发送方使用完全不同密钥，并且公共密钥是陪外界已知的，而私人密钥又 是由用户自己秘密保存的，所以根本不需要密钥的交换和配置。通常情况下， 我们一般使用公共密钥加密系统来实现对称密钥加密系统所使用的密钥的交 换。因此，公共密钥加密技术对于密钥交换、系统验证和数据的保密都起着非 常重要的意义。可是，一种高强度的公共密钥密码加密从计算量上来说比传统 的对称密钥加密要大得多。一般情况下，公共密钥加密算法比与其相当的对称 密钥加密算法运行的时间要慢l o o o 倍【“。 5 武汉理工大学硕士学位论文 图1 5 公共密钥验证系统 与对称密钥加密算法基于代替和置换不同的是，公共密钥加密算法主要是 基于数论的数学特性。举个例子，最重要的一个公共密钥加密算法r s a i s ，就 是基于这样一个理论：要将一个很大的数n 因数分解成两个较大的质数p 和q 是无法实际完成的。另一个非常重要的公共密钥加密算法，椭圆曲线加密算法 ( e c c ) 【9 】，基于的理论是：己知椭圆极点g ，我们很难计算出正整数k 来满足 己知乘积k g 。这在数学上称为椭圆曲线对数问题。 1 2 软件实现v s 硬件实现 对于加密算法软件实现比硬件实现更容易也更加灵活。软件实现是将加密 程序在一般通用计算机上运行，因此软件程序不会消耗大量资源，开发和实现 周期也比较短。然而，一般通用计算机或处理器对于很多的加密计算都不是很 适合。大多数计算机硬件是一种通用的计算工具，比如个人电脑( p c ) 或商用 大型计算机。软件实现计算在高速应用和大量数据时速度会比较慢。对称密钥 加密的软件实现输出约为几百兆位每秒( m b p s ) 。一台6 0 0 兆赫兹的处理器无 法及时完成t 3 通信电缆的3 d e s 加密数据【l o 】。对于现在的无线带宽和嵌入式系 统的要求，掌上电脑p a l mi i i 则需要3 4 分钟才能完成一个5 1 2 位的r s a 密钥 的产生，需要7 秒钟才能完成一个数字签名。而且它只能以1 3 k b p s 的速度实现 d e s 算法【l l 】。 硬件实现通常需要比较长的开发时间，并且需要更为专业的硬件设计和实 现的技能。除这以外，硬件实现对于不同的应用需求缺少了灵活性。可是，硬 件实现有一个最大的优点，那就是所有的硬件模块可以同时工作这样就可以得 6 武汉理工大学硕士学位论文 到非常好的系统性能，有的可以达到g b p s 级，这样就非常适合现代的高速网络 应用，例如虚拟个人网( v p n ) ，安全i p ( i p s e c ) 。举个例子，在参考文献【1 2 】 中，一个大型集成电路系统( v l s i ) 的f p g a 实现3 d e s 算法利用流水线的体系结 构达到了6 9 g b p s 的速度。另一个高性能的单片f p g aa e s 算法实现方案【i3 l 的 1 2 8 位加密核达到了7 g b p s 。在参考文献【l q 中，作者甚至展示了一个用0 1 8 啪 c m o s 技术实现的a e s 处理器，速度达到了3 0 7 0 g b p s 。除了速度，对于特别 高速的处理器，加密硬件芯片比软件加密实现还有另外一些潜在的优势，比如 说更小的体积，消耗的电能更少。而且，由于加密硬件在物理位置上是于系统 的其他模块分开放是的，学术上广泛认为硬件实现在实际中比相应的软件实现 更加安全。 一般，硬件实现包括专用集成电路( a s i c ) 实现和现场可编程门阵列( f p g a ) 实现。它们各有各的优势。采用a s i c 方法可以得到更高的性能和更好的集成性， 并且可以实现比f p g a 技术更快、更小、能耗更少的设计【1 5 l 。但是f p g a 则可 以给设计带来更来的灵活性和可配置性，这些又正好是a s i c 设计所欠缺的。 考虑到软件和硬件实现的优缺点，一些软硬件混合加密实现方案被提出来 了。比如，在参考文献【7 j 中，作者给我们展示了一套软件和硬件共同实现的加密 处理器，这个处理器有非常好的性能，同时又保持了在现场支持多种算法的灵 活性。 本文由于主要考虑了低端应用上面积和费用的限制，加上嵌入式处理器有 限的性能，我们选择研究和探索一种针对此类应用的a e s 加密算法专用的精简 紧凑型硬件设计和实现方案。 1 3 硬件设计和实现方法理论 随着数字系统大小和复杂度的增加，人们越来越多的在硬件设计和实现过 程中采用计算机辅助设计( c a d ) 。这些c a d 工具可以完成复杂的硬件设计， 仿真，综合，验证和实现的功能。现今，硬件描写语言( h o e ) 被广泛的应用于硬 件设计和实现。v h d l 和v c t i l o g 是二种目前非常普遍被使用的h d l 语言。它 们使用于数字系统模型设计的各个抽象阶段，从算法级到门级。v h d l 是超高 速集成电路( v h s l c ) 硬件描述语言。在我们的研究和整个数字系统的设计，建模， 测试和文档过程中，我们使用的是v h d l 语言和s y n o p s y s 计算机辅助工具。 既然硬件系统的设计和实现是一个复杂的过程，它是不可能一下子完成整 个大系统的实现，所以我们在硬件设计时采用了一种分解攻克的策略，被 称为t o p - d o w n 的方法，而在硬件实现时采用的b o r o m u p 的方法。t o p d o w n 的 7 武汉理工大学硕士学位论文 设计方法其实是将一个大的系统分解成子模块，子模块再分解成更小的模块， 直到所有的子模块都可以对应到已知的目标库，并且可以通过使用已有的工具 和技术来实现这些子模块。这个过程在图1 6 中显示为一个树形结构【1 6 1 。在 t o p - d o w n 的设计后，我们开始实现树形结构中的末端模块，然后再把这些末端 模块按照整个系统的结构体系连接起来。每一个末端模块在它们被连接到上一 层模块之前必须已经通过了测试和验证。 图1 6t o p - d o w n 的设计和b o t t o m - u p 的实现 在数字系统设计的过程中，我们完全按照图1 7 种所示的数字i c 设计流程 ( d i g i t a li cd e s i g nf l o w ) 【l ”。最初的设计构想在成为真正的硬件芯片之前要 经过好几个步骤。首先，最初的设计构想要用v h d l 语言写成r t l 代码，其中 采用t o p d o w n 设计和b o t t o m - u p 的实现方法。r t l 代码的功能要依靠仿真进行 验证。接下来，我们使用s y n o p s y sd e s i g na n a l y z e r 来综合和优化r t l 代码，生 成基于目标库的门级网表，同时我们也会对设计加上一定的约束来满足设计的 性能要求。在这之后，我们使用t e s tc o m p i l e r 来插s c a n 链，使用d e s i g nf o r t e s t a b i l i t y ( d f t ) 技术来保证设计的可测试性。然后我们会验证门级网表的功能， 其中我们会将时序信息加入网表中来保证在实际情况下门级网表的电路的功能 是正确的。这四个步骤都使用s y n o p s y sc a d 工具，被统称为前端设计。在前端 设计后，我们将会作物理层的一些设计。f l o o r p l a n n i n g 使用了p h y s i c a ld e s i g n p l a n n e r 是为了系统布局布线产生一个规划，并且给所有的单元电路定义了位置 布置。这之后利用前置的时序信息来完成核心模块的布局布线。时钟树是为了 8 武汉理工大学硕士学位论文 满足综合时所设定的参数而加入一些时钟b u f f e r ，来生成一个平衡的时钟树。 r o m m g 和时序验证是为了验证在真正的布局布线后设计还能够满足时钟的一些 约束。最后物理级的验证时为了保证最后出来的电路的正确性，并修改一些小 的d e s i g nr u l ec h e c k ( d r c ) 错误。在物理层的设计阶段，我们通常使用c a d e n c e c a d 工具和v e r i l o g 语言。在这篇论文中，我们主要侧重于前端的设计和研究。 r t l s i m 一- 。0 l s y n t h e l l $ l s 。“i “n 。t i 。” l s g 。a 。t e 。- 。l e u v 。e 。l l 9 ”“t “。r i g l p l 。n t l l 。c 1 0 。c 。k ，。t 。r e 。e 。 l l “u 。t 。l n 。g 。& t 。i m 9 l ，p h y b i c a l、 v e r i f l c , a u o n 1 4 研究动机和目标 d l g na n a l y z e r 图1 7 数字芯片设计流程 自从美国国家标准技术局( n i s t ) 在2 0 0 1 年1 1 月宣布将r i l m d a e l 算法选 为高级加密标准( a e s ) ，a e s 已经广泛地用于加密敏感的商业和政府机密数据。 在n i s t 评估高级加密标准候选算法过程中，r i j n d a e l 算法以其在软件和硬件实 现中高效的计算效率和执行速度，强大的安全性和在各种计算环境下的灵活性 和自适应性从众多候选算法中脱颖而出。今天，随着日益增长的安全数据交换 的需求，多种a e s 算法的硬件实现结构被提出来，但通常这些高速的实现方案 9 武汉理工大学硕士学位论文 会占用非常复杂的硬件资源。超大的面积带来高硬件费用不适合实际生活中低 端嵌入式应用，例如s m a r tc a r d ，手上电脑( p d a ) ，手机及其他的无线设备。 这些小型的嵌入式应用不需要很高的通讯速度，但对面积有苛刻的要求。因此， 缩减硬件资源从而实现一个紧凑简洁并有效的实现电路是一种越来越重要的研 究方向。 我们研究的目标就是要用硬件设计和实现一套节约紧凑型a e s 加密系统， 包括加密，解密和密钥的扩展，并努力地为嵌入式应用在系统性能和成本之间 寻找到最好的平衡。 本文由以下五个章节组成： 第二章主要介绍了与a e s 算法硬件实现相关的研究背景。我们首先介绍了 a e s 算法理论基础和内容，然后对各种不同的a e s 算法的硬件实现方法做了调 研。面对不同的应用，需要满足不同的系统性能和成本的平衡。 第三章提出了一种新的a e ss - b o x 的实现方案，这个方案是基于关于s - b o x 线性冗余研究的新发现。因为s - b o x 是整个a e s 算法中成本最大的模块，我们 首先探究了紧凑型s - b o x 的实现方法。在调研了已知的紧凑型s b o x 的硬件实现 方案后，我们利用了a e ss b o x 线性冗余的新发现提出了一种基于这个理论的 新紧凑型s - b o x 的硬件实现方法。我们也将这种新的实现与其它已知的实现方案 进行了比较。 第四章在s - b o x 研究结果的基础上完成了一套完整的a e s 加密解密系统。 我们首先实现了不带密钥扩展的循环结构的加密系统，并且分别将三种不同的 简洁紧凑型s b o x 运用到这个结构中。在比较了六种实现方案的结果后，我们发 现利用四个基于g f ( 2 4 ) 域算术运算的s - b o x 的实现方案在速度和面积的平衡 方面做得最好。因此，我们基于这样四个g f ( 2 4 ) 域算术运算的s - b o x 的实现 方案下完成了一套完整的，带有密钥扩展的，简洁紧凑型的，a e s 加密解密系 统。 第五章对所做的研究工作做了一个总结，并对今后的工作方向提出了几点 建议和展望。 1 0 i 汉理工大学硕士学位论文 第2 章a e s 加密算法硬件实现 在这一章里，我们研究了实现a e s 算法的各种硬件实现方略和技术。我们 将在这里针对不同的实际a e s 应用讨论各式各样可能的实现方案，设计方法， 结构构造和算法优化方法。 在a e s 算法之前，d e s 是最广泛使用的加密算法。随着计算机硬件速度的 不断增加和硬件价格的不断低，d e s 在1 9 9 8 年7 月被最终证明是不可靠不安 全的。美国国家标准技术局f n i s t ) 在1 9 9 7 年宣布需要用一种新的高级加密标 准取代d e s 在各种应用中自抛位。在经过了三年彻底深入的评比之后，r i h n d a e l 算法最终从众多候选算法中颖而出，在2 0 0 1 年1 1 月宣布正式当选为a e s 算 法标准【2 l j 。这次的评比涵盖了现代对称分组密码在现实应用中的所有性能，包 括安全性，成本和各种实现制生。r i h n d a e l 算法优于其它候选算法在于其在软件 和硬件实现中高效的计算效事和执行速度，强大的安全性和在各种计算环境和 模式下的灵活性和自适应性如今，a e s 已经被广泛地应用于加密敏感的商业 和政府机密数据。 a e s 是一种对称密钥的分组加密算法，它的支持1 2 8 位，1 9 2 位或2 5 6 位的 密钥长度。该算法主要是基f 以字节为单位的代换和线性变换作用于1 2 8 位的 分组长度。对应于1 2 8 ，1 9 6 和2 5 6 位不同的密钥长度，运算的循环分别为1 0 轮，1 2 轮和1 4 轮。 a e s 算法可以用来对数曙进行加密和解密。对于加密操作来说，该算法共 有4 个主要变换阶段，分别口撇字节代换( b y t es u b s t i t u t i o n ) 行移位( s h i f tr o w ) ， 列混淆( m i xc o l u m n ) 和轮骞钥加( a d dr o u n dk e y ) 。另一个非常重要的变换 是密钥扩展( k e ye x p a m i o t d 。这些交换使信息统计规律得以分散和混淆。分 散可以保证两个只有一位t , e 的两组数据经过变换后成了两组完全不同的输出 数据。而混淆可以使密钥和誊出数据的数学关系非常复杂。 武汉理工大学硕士学位论文 扣e n 叫p - n姊嘶叫- 口- n 图2 1a e s 加密和解密流程图 ( 1 ) 节代换 字节代换变换是一个简单的查表操作。因为字节代换是以每一个字节为单 位进行操作的，输入的1 2 8 位数据被分为1 6 个字节。所有的字节排列成4 乘4 的矩阵，其中每个字节通过按a e s 算法中定义s _ b o x 中相对应的字节映射为一 个新的字节。比如说，对于某一个字节确，我们通过s - b o x 查表找到其对应位置 上的元素为字节b 日所以我们就可以将b i j 替换到曲在矩阵中所在的位置上。 a e s 算法中所定义的s - b o x 是一个8 输入8 输出的模块。它包含了2 5 6 个由8 位数组成所有可能的值。s - b o x 的设计是整个算法中最重要的部分，因为s - b o x 是整个加密系统中唯一的一个非线性的部分。 ( 2 ) 行移位 行移动是一种简单的调换操作。第一行的数据不需要任何移动。第二行的 数据依次向左移动1 个字节。第三行的数据依次向左移动2 个字节最后一行 的数据依次向左移动3 个字节。 ( 3 ) 列混淆 在这一步操作中，一个固定的矩阵c ( ) ( ) = 0 3 ) x 3 + 0 1 ) c 2 + 0 1 ) x + 0 2 ) 被当作乘数，在g f ( 2 8 ) 域上与数据的每一列，进行以“+ l 为模的乘法运算。 列混淆操作在数据处理的每一轮( 除了最后一轮) 都会进行。 ( 4 ) 加入轮密钥 轮密钥的加入操作实际上是将整组数据和轮密钥进行按位的异或( x o r ) 武汉理工大学硕士学位论文 运算。并且在第一轮运算之前再增加一次密钥加的操作。 ( 5 ) 密钥扩展 密钥扩展的算法可以用于1 2 8 位，1 9 2 位或1 5 6 位不同长度的初始密码。对 于1 2 8 位的密钥，密钥扩展算法会将1 2 8 位的初始密码当作4 个字长( 1 6 个字 节) 的输入，然后生成4 0 个字长的密码，在加密过程l o 轮中的每一轮使用其 中的4 个字长作为轮密钥。每一轮的轮密钥是基于上一轮的轮密钥而产生的。 与数据加密标准( d e s ) 不同的是，a e s 的解密操作与加密操作是运用的 不同的结构。然而，如果我们在操作的顺序进行一些改变，并且能在密钥扩展 的过程中进行一些变换，那么我们就可以在解密的过程中利用一个和加密相同 的结构进行处理，只是使用字节代换，行移位，列混淆的反运算。 2 2a e s 硬件实现方案 a e s 算法的结构比较简单，它可以非常有效的在大量通用微处理器和嵌入 式处理器中实现。与其它分组密码算法相比，a e s 算法在软件实现中有着更高 效的计算效率和执行速度。即使a e s 算法在软件实现的性能上比其他算法有优 势，像专用的加密处理器之类的硬件系统仍然是很多现实应用中所需要的。 高速应用希望使用a e s 硬件系统来实现较高的数据流量。比如互联网物理 层加密中使用网络加密协处理器就是一个很好的例子。在此类的应用中，高速 是最重要的考虑因素。在通用处理器中使用软件来实现a e s 算法只能得到约几 百兆缈的数据流量。这个速度对于高端互联网路由器来说太慢了。虽然近期有 一些被高度优化的软件实现程序跑在高速微处理器上，可以获得快到1 5t 3 b p s 的速度 2 2 1 。但是高速的微处理器的成本更大，需要大的空间，消耗更多的能量， 这些与a e s 硬件实现系统相比需要更大的成本。 对于低端嵌入式移动应用，例如手上电脑( p d a ) ，手机及其他的无线设 备，a e s 算法在通用计算机上实现的的软件系统会比硬件实现系统消耗更大的 能量。s m a r t c a r d 是另一种非常适用于硬件实现系统的例子。在这些应用中，虽 然速度也是很重要的，但更多考虑的是如何得到最小的面积和如何消耗最少的 能量。 2 2 1 高速a e s 硬件实现方案 高速a e s 硬件实现系统适用于速度需求很高的应用，比如互联网服务器， 虚拟私人网( v p n ) 或异步传送模式( a t m ) 。这类需要较高数据流量的a e s 系统通 常会为了得到最高的速度而采用一些结构上的优化，如流水线结构，亚流水线 武汉理工大学硕士学位论文 结构和循环展开结构【2 3 】。这样的结构可以在每一轮中利用重复冗余的硬件设各 进行加速运算。 对于a e s 算法的f p g a 和a s i c 的硬件实现这个方向，已经有很多相关的 研究结果。所以我们将在这里从两个方面把这些相关的研究做一个详细的介绍。 2 2 1 1 高速a s i c 实现方案 a s i c 实现系统比f p g a 实现系统更适合于产生高速的数据流。大多数a s i c 的a e s 系统可以达到几个o b p s 的输出率。 在n i s t 对a l e s 算法的挑选过程中，美国国家安全局( n s a ) 对参加评选 的所有候选算法的硬件性能基于o 5 mc m o s 技术做了充分的仿真和比较凹。 r i j n d a e l 算法作为其中的一个候选者，也从各种角度分析了硬件的各项性能，如 速度，面积和输出率。对于高速实现系统，他们对算法中数据处理和密钥扩展 都使用了一种流水线的设计结构。这种流水线结构的密钥扩展在加密开始后与 数据的加密同时进行，不需要专门等待密钥的初始化。密钥按照每轮4 个3 2 位 字长的速度生成。一组寄存器专门用来存放密钥并且把密钥加入到数据中。这 种流水线的数据通道只执行每一个操作的一轮，并对加密和解密采用相同的流 水线。在参考文献 2 5 1 q 3 ，t i c h i k a w a 和他的同事们利用m i t s u b i s h ie l e c t r i c 的 0 3 5 岬c m o s 技术a s i c 的库对a e s 评选中最后一轮的几个候选算法进行了 研究。在这篇文献主要侧重于反馈模式下的高速加密系统，没有用流水线结构 而是采用了一种完全展开循环的结构，是因为流水线结构无法在反馈模式下进 行运算。因此他们的设计是极力获取高速而没有考虑任何减小硬件尺寸的方面。 在文献【1 4 】中介绍了一种采用完全流水线结构的a e s 系统，这个系统的输 出数据量可以超过3 0o b p s 。将所有操作的循环全部展开，每一轮之间采用轮外 流水线，s - b o x 采用在复合域两级亚流水线的方法，利用0 1 8 岬1c m o s 技术 a e s 硬件系统可以达到3 0g b p s 到7 0o b p s 的速度。由于流水线的结构需要消耗 大量的硬件资源，这个实现方案使用了复合域代数方法实现s b o x 来减小电路面 积，同时使用了非实时的密钥产生方案。在参考文献 2 6 1 中，还有一些没有考虑 任何减小硬件面积的相关研究，三种都是采用流水线结构设计却不尽相同的 a e s 算法实现方案从面积和速度的平衡和折中方面做了详尽的比较。 另一组快速的a e s 硬件实现是通过采用各种各样的硬件设计技巧来同时达 到提高性能又减小电路尺寸的目的。这些设计方案都是想尽力在性能和成本之 间建立一种桥梁。因此这些实现方案都是采用一种循环的结构来提供中等的数 据处理速度，但却只需要相对少的面积和硬件数量。循环的结构是指只需要用 硬件实现一轮的操作，而整组数据需要在这一轮硬件操作的数据通道中循环n 1 4 武汉理工大学硕士学位论文 次才能完成一次完整的加密，解密。有一套此类有效的a e s 硬件实现系统在参考 文献 2 7 1 中展示出来。这个系统没有使用简单的s b o x 查表实现方法，而是利用 复合域g f ( 2 4 ) 的代数运算来实现的s - b o x ，这样可以减小电路的面积。这个芯片 的数据通道采用了4 级的流水线结构，而只用硬件实现了一轮的加密解密操作。 前三级的流水线实现的是字节代换的操作，而所有其他的操作都是在最后一级 中完成的。这个系统采用t s m co 2 5 岬c m o s 技术，获得了1 2 8 位密钥的a e s 系统，速度达到了2 9 7 7g b p s ，最高时钟频率为2 5 0m h z ，所用硬件大小为 6 3 4 0 k 门。类似的系统还在参考文献 2 8 1 ，【2 9 1 ，【3 0 中有所介绍。在 2 8 1 q b 所描 述的实现方案也在数据通道中采用了加快操作频率并且提高硬件利用效率的流 水线方法，所不同的是它在每一个操作的结束处加了2 5 6 位的寄存器。并且， 它将s - b o x 储存在r o m 中，直接用查表的方法完成字节代换的操作，事先生成 轮密钥并且把它们储存在s r a m 中。这个硬件系统采用了t s m co 1 8 岫c m o s 技术，输出数据率为2 3g b p s ，最高工作频率为4 6 5m h z ，所消耗的硬件电路大 小为2 8 6 k 门并加上1 2 8 k 的r o m 和4 k 的s r a m 。与刚才介绍的两个实现方 案一样，参考文献【2 9 】和【3 0 】也采用了循环结构，在一个时钟周期内完成一轮数 量处理。这个系统都支持三种不同的密钥长度和三种不同的数据分组大小。利 用查表s - b o x 和实时密钥扩展，这个a e s 芯片基于o 1 8p mc m o s 技术得到的 最大数据输出率为2 2 9g b p s ，电路大小为1 7 3 k 门。 另一个速度超过了1 0g b p s 的a e s 硬件实现系统在参考文献 3 h 中介绍出 来，这个系统采用循环结构，数据通道为3 2 位。这样的一个循环结构通常用在 简洁紧凑型的实现方案中，但是这个系统却采用了循环的结构，而没有采用流 水线或循环展开的结构，却也达到了这么高的速度。它利用了一种特殊的扭转 二进制决定表( b d d ) 来实现s - b o x 。这样的方法比传统方法实现的s b o x 要快 1 5 2 倍。t - b o x 算法在参考文献 2 3 1 中也与b d d 方法结合，被称为b d dt b o x 结构，这种结构可以使数据处理的延迟更小些从而增加速度。实际上t - b o x 是一 种在软件实现中常常使用的加速方法。这种方法将字节代换和列混淆两个操作 融合成了一个功能模块。密钥是事先生成好的并储存在外部的寄存器里。同时 这个系统采用了更先进的半导体工艺，这个也使得系统的速度增大不少。最后 这个电路在使用了o 1 3i t mc m o s 标准单元库后面积为1 6 7 6 k 门电路，即使在 反馈模式下在时钟周期为8 8 0m h z 时输出数据率也高达1 lg b p s 。 对于1 2 8 位密钥的r i j n d a e l 算法所有这些系统实现的硬件综合结果都列在表 2 1 中。 武汉理工大学硕士学位论文 表2 11 2 8 位密钥a e s 算法的高速a s i c 硬件实现系统 c l o c k c r i t i c a l t h r o u g h - l m p l e m e n t a t e c h n o l oa r e a f r e q u e n k b p s p r o c e s sa r c h i t e c t u r ep a l h p u t - t i o n g y ( g a t e s ) c yg a t e ( n s ) ( g b p s ) m 删 t i e h i k a w ae n c l o o p 0 3 5m6 1 2 k 6 5 6 41 5 2 3 1 ”3 1 s c t a l 嘲 d e c u n r o l l i n g c m o s 4 - s t a g e 0 1 8 i n n 4 7 3 k1 6 56 0 6 7 7 61 6 4 1 s u b - p i p e l i n i n g c m o s h o d j e t f u l l y 0 1 8m d m 嗍 e r i c 3 7 2 k2 6 53 7 7 4 8 2 1 2 争6 p i p e l i n i n g c m o s 2 - r o u n d0 1 8 i n n 2 2 5 k2 7 6 3 6 22 3 1l 舵7 p i p e l i n i n g c m o s c s ue 耐 i t e r a f i v e0 2 5 t u n 6 3 4 0 k4 0 02