（微电子学与固体电子学专业论文）面向aes加密的可配置处理器设计及实现.pdf

摘要 随着计算机技术和网络技术的快速发展和广泛应用，信息安全逐渐成为人们 普遍关注的课题。高级加密标准( a e s ) 是美国国家标准与技术研究局宣布采用 的数据加密标准，在安全性、简洁性、实现成本等方面与原有的对称加密算法相 比具有一定的优势，具有广泛的应用前景。a e s 的传统实现方式是采用d s p 或 a s i c 方法，本文阐述一种基于传输触发架构( 1 r a ) 的可配置处理器实现a e s 的方法，该方法在一定程度上达到性能与灵活性的折衷。 本文首先介绍n = a 架构可配置处理器的结构、硬件、指令集系统的特点，然 后分析并用c 语言实现a e s 算法，根据在c 幸c o r ec 3 1 0 上的统计结果，分析出关键 路径，将字节乘法转化为查表运算。其次，重点论述了基于传输触发架构和超长 指令字( v l r ) 指令结构的a e s 算法并行优化方法：将密钥扩展与轮变换并行 实现，综合轮变换整个过程简化数据流，并根据特殊运算定制功能单元、指令集。 设计自动化是可配置处理器设计的一大难点，也是可配置处理器能够被广泛使用 的必要条件。本文还重点讨论基于，兀= a 架构处理器的r 1 l 代码及可配置汇编器自 动生成的方法。通过采用本设计实现的r 1 r l 代码自动生成软件及汇编器，自动生 成了用于a e s 加密的可配置处理器的i 汛代码及特殊指令集汇编器。最后在仿真 软件和f p g a 上完成验证，结果表明进行1 2 8 - b i t 明文，1 2 8 b “密钥的a e s 加密， 吞吐率为1 8 m b p s ，其性能优于一般通用处理器和d s p 。由于自动生成技术，其设 计周期比a s i c 短，设计难度比a s i c 低，而且由于采用特殊的1 r a 架构实现加密 算法，具有抗攻击特点。但与a s i c 设计相比，在速度上还存在一定差距。因此， 此领域存在广阔的研究空间。 关键词：高级加密标准传输触发架构可配置处理器超长指令字并 行优化抗攻击 a b s t r a c t w 油t h er ：叩i dd e v e l o p m 锄ta n dw i d e 叩p l i c a t i o no fc o m p u t c r t e c i l n 0 j o g i e s 锄d n e t 、o d ( t e c h n o l o g y ，i n f o m a t i o ns e c 谢t ) ，铲a d u a l l yb e c o m e s 锄i i l t c r e s t i n g 鲫b j e c t n a t i o n a li n s t i t u t eo fs 切n d a r d s 柚dt e c h n o l o g y 锄。咖c e da d v a n c e de n c d 忧i o n s t a n d a r d ( a e s ) 嬲d a 诅e n c r y p t i o ns t a n d a r d ，w h i c hh a l s c e r c a i l la d v 柚t a g e s0 v e r o r i g i n a ls y i l l i t l e t r i c 朗c i p h e 加ta l g o r i t h mms e c u r i 吼c o n c i s e n e s s ，c o s t ，锄dh a v e w i d e s p r e a da p p l i c a t i o np r o s p e c t t r a d i t i o n a l l y ，a e s 、嬲i l i l p l e m e n t c db a s e d0 n 舭 d s p0 ra s i c t h i sp a p e rs t a t e sam c 1 0 do fi m p l e m e n t a t i o nb a s e d0 nt i l et r 舭驴r t 嘣g g c ra r c h i t e c t u ( t t a ) c o i l f i g u r a b l ep r o c e s s o r t 0s o m ee x t i 雕t ，m i sm e t h o d m a k e st h ec o m p r o m i s eb e t 、e 朗p e 响r n l 锄c ea n df l e x i b i l i 够 f i r s t l y ，t l l i sp a p e rd e s c n b e st h ea r c h i t e c u r e ，h a r d w a r e 锄d 洫s t r i 】c t i o ns e ts y s t 锄 o f1 1 阪c o n n g u r a b l ep r o c e s s o r a 舭刑a r d s ，a e sa l g o r i t h mi s 锄a l y z e d 觚d h p l e m e n t e db ycl 锄罂l a g e a c c o r d i n g t os 协t i s t i co nc 幸c o r cc 3lo ， b y t c m u l t i p l i c a t i o ni st r a n s f 0 1 c dt ol o o k i n gu pt a b l e s e c o n d l y ，p a 豫1 l e lo p t h 娩a t i o n m e t h o d so fa e s a l g o r i t i l n lb a s e d 0 nr r r a 锄dv e r yl o n gw o r di sd i s c u s s e d ，w h i c ha r e p 啪l l e li m p l 锄e n t a t i o no fk e ye x p a n s i o n 粕dr o u i l d ，s i i i l p l i 匆m gd a t a f l o wo fr 0 u i l d ， c u s t o m i z i n g 向n c t i o nu n i ta n d i i l s 臼1 l c t i o ns e tc o r d i i 唱 t 0 s p l e c i a lo p e r a t i o n a u t o m a t i o ni so n eo ft h em o s td i 伍c u l t i e so fc o n f i g u r a b l ep r o c e s s o rd e s i g n ，粕d n e c e s s a r yc o n d i t i o no fw i d e s p r e a du s eo fc o 而g u r a b l ep r o c e s s o r ，n l i sp a p c rl a y s s 雠s so n 舢t o g e m t i o nm e t h o do fr ，几c o d e 锄dc o n f i g u r a b l ea s s 锄b l e rb a s e d0 n 1 r a r t lc o d e 锄d 私s e m b l e ro fs p c c i a lm 鼬r u c t i o ns c tf o ra e se n 刚i o nw 嬲 a i i t o g 蛐e r a _ t c db yk 兀。叫_ t 0 - g e n e r a t i o ns o 如a 他a l l da s s e m b l e r f i l l a l l y r e s u l t sf i r o m s o f t w a r e 锄df p g av e r i f i c a t i o ns h o wt l l a tf o r12 8 - b i tp l a m t e x t l2 8 - b i tc i p h e rk e y a e s 锄c 聊p t i o n ，t i l et h r o u g h p u ti sl8 m b p s ，w h i c hi sb e 批r 廿l 彻g c n e m lp c e s s o 璐 a n dd s p b e c a u s eo f 卸t o g c n e r a t i o nt c c l l l l i q u e ，i ti ss h o n e r 觚de 鼬i c r 廿l 锄t h a ti i l a s i c b e c a u s e 锄c 州i o na l g o r i t h i ni si n l p l e m e n t e db ys 0 腑a r e ，i tc 锄a g a i n s ta 位a c l 【， b u t 廿l e r ci sc e r t a i l lg 印w i ms p l c e dt h a ti i la s i c t h e r e b yr c s e a r c hs p a c ei ss om u c hi i l m i s 剐呜a k e y w 6 r d s ：a d v 粕c e de n c 聊p t i o ns t 锄d a r d ，t r 锄驴r t 野g g e r 心c h i t e c u r e ， c o n f i g u r a b l ep r o c e s s o r ，v e 哆l o n gw 6 r d ，p a r a l l e lo p t i m i z a t i o n ，a g a i n s ta t 眦k 第一章绪论 1 1 课题研究背景、意义 第一章绪论 随着3 g 、无线智能终端、物联网的迅猛的发展，人类生活正在发生日新月 异的变化，然而在电子支付、智能交通、身份识别、可信计算、消费电子等诸 多领域正在遭受诸如黑客攻击、系统崩溃等信息安全问题的侵扰，严重损害着 用户的安全与利益，威胁着国家安全、社会稳定与经济发展。因而，保障信息 的安全，保护信息的机密性、完整性不可抵赖性和可用性已成为信息社会亟须 解决的重要问题之一i i j 。 密码技术是保证信息的机密性、完整性以及可用性等安全要求的基本手段。 密码算法属于计算密集型应用，传统实现方式是专用集成电路( a p p l i c a t i o n s p e c i f i ci l l t e 野l t e dc i r c u i t ，a s i c ) 【2 。、f p g a l 副或数据信号处理器( d i g i t a ls i 朗a l p r o c e s s o r ，d s p ) i 引。采用a s i c ，是针对具体应用提供定制数据通路和控制通路， 最大限度发挥算法的并行性，特点是速度快、功耗低，没有多余的操作，但是 设计较复杂，开发周期较长，成本较高，而且无法满足环境中灵活实现密码算 法的要求，而且这种方式下功率消耗的大小与所处理的数据量的大小和数据的 类型直接相关，容易被攻击。采用f p g a ，可以根据算法设计硬件逻辑，理论 上在容量允许情况下可实现任何算法。由于f p g a 具有可重复编程性，灵活性 较强。但是由于其逻辑和布线资源都是通过数量、位置固定的基本单元实现， 在速度、面积、功耗都会造成一定程度的浪费，而且在大批量应用时存在高成 本等缺点。采用d s p ，根据通用结构，通过编程实现特定算法，优点是灵活性 高，抗攻击性能好，但其通用性一方面限制了特定领域的并行处理性，一方面 造成逻辑和连线资源较大程度的冗余，所以这种方法速度慢，功耗高【5 】。 本文提出一种基于传输触发架构的可配置处理器实现a e s 算法。这种处理 器是一种专用指令集( a p p l i c a t i o n s p e c i f i ci i l s t r l l c t i o np r o c e s s o r ，a s 口) 处理器， 用户可以根据可根据具体算法的共性和需要的性能定义总线宽度，根据算法并 行度定义特殊功能单元、总线数目、通用寄存器数量，根据算法涉及的操作定 义功能单元的种类，最终定义出指令集。同时采用超长指令字( v e 珂l o n g i i l s t r u c t i o nw 6 r d ，v l i w ) 的指令格式，充分发挥数据并行处理的能力。因此， 这种架构对于数据处理具有高效性的特点。这种架构处理器由功能单元 第一章绪论 ( f u n c t i o nu n i t ，f u ) ，寄存器堆和一些互联逻辑组成，结构简单，灵活，模块 化1 6 】，便于自动生成。通过自动生成，用户可以通过简单设定配置信息，快速 生成处理器硬件架构和软件汇编器、汇编器，减小设计难度，极大缩短了设计 周期、降低设计难度i _ 7 1 ，同时整个算法通过软件编程实现，硬件、软件设计都 具有灵活性、可扩展性，而且在一定程度上还具有防止差分能量攻击的特点。 a e s 可配置处理器的设计结合了a s i c 设计的高性能和d s p 设计的高灵活性、设 计难度低的优点，具有很强的研究意义。 1 2 数据加密算法 在需要加解密大量的数据时一般采用对称加解密算法。对称加密算法中， 加密和解密使用同一个密钥，安全性取决于算法和密钥长度【8 】。上个世纪7 0 年 代，数据加密标准( d a t ae n c 帅t i o ns t a n d a r d ，d e s ) 广泛用于商业系统中，但 其密钥只有5 6b i t s ，对于穷尽搜索攻击来说太小了，很容易被破解，例如1 9 9 8 年电子开拓基金会耗资2 3 万美元，制造出一台特殊的计算机，可在5 6 小时内破 解d e s 加密信息，经改进后7 小时就可破解d e s 【9 】。三重d e s ( t d e s ) ，使用3 倍d e s 的密钥长度的密钥，执行3 次d e s 算法，在安全性方面高于d e s ，但是传 输带宽是d e s 的三倍，实际应用中极大影响网络传输的性能。从保密性和高效 性两个方面考虑，采用d e s 进行数据加密并不是一个十分理想的方案【1 0 】。2 0 0 1 年，美国国家标准与技术研究局( n a t i o n a li i l s t i t u t eo f s t 锄d a r d s 锄dt e c l l l l o l o g y ， n i s t ) 出于安全性、速度和存储需求、算法与实现特性这三方面考虑，从m a r s 、 r c 6 、r i j n d a e l 、s e 印e m 、t 、f i s h 这五个后选算法中选出由比利时密码学研究 员者j o 锄d a e m e n 和n c e n t 砌j m e n 提出的r i j n d a e l 算法作为高级加密标准 a e s ( a d v 锄c e de n c 巧p t i o ns t a n d a 坩) ，代替了传统的d e s ，作为联合信息处理 标准( f e d e r a li n f o 朐a t i o np r o c e s s i n gs t 锄d a r d s 。f 口s ) 【11 】【1 2 1 。 a e s 算法目前可应用于很多方面，无论是i p s e c 、p p l l p ，构建虚拟专用网 ( ) n ) 的协议族，还是p g p 、p e m ，保护电子邮件安全的协议族；无论是 s s 价s l 、s s h ，保护w 曲安全的协议，还是s e t ( 安全电子事务) ，用于安全 电子支付的协议；无论是无线局域网( w l 蝌) 技术，还是自动存取款机( a 1 m ) ， 都离不开a e s 数据加密技术【3 】【1 3 】【1 4 】。随着人们信息安全意识的不断提高，在未 来一定时间内，a e s 将发挥不可替代作用。未来实现a e s 应该考虑以下几个方 面1 1 5 】： 安全性。使用密码算法就是为了保证信息的安全，其实现的安全性尤其重 2 第一章绪论 要。目前对a e s 最有威胁的攻击方式是差分功耗攻击( d p a ) 【1 6 】。进行差分功 耗攻击时，功率消耗的大小与所处理的数据量的大小和数据的类型直接相关， 攻击者正是利用这种数据与功耗的相关性进行敏感数据的破译。由于处理器本 身并不仅仅执行单一的加密操作，并且在指令执行过程中采用了流水线的操作 方式，这样，密钥与处理器的功耗之间的相关性趋近于o ，打破了数据与功耗的 相关关系，使得处理器具有较高的抗功耗攻击防护能力。所以从这个角度讲， 用处理器和d s p 实现具有天然的抗攻击的优势。 实时性。数据加解密后，利用安全信道传输到客户端，用户不会感到延时， 这是对其应用时的最基本要求。随着网速的提高，实时性对a e s 算法实现速度 的要求不断提高。从这一点来讲，采用a s i c 实现具有一定的优势。 灵活性。安全标准、安全协议以及密码算法本身都是发展的。在同一时间 内，往往是多个标准并存的，一个设备需要同时满足多个应用要求，设计也应 该能够满足多个标准。这要求软件、硬件都要有可扩展性。 面积小。面积代表成本，面积越小，芯片厂商才会从中获取越大的利润。 低功耗。越来越多的数据处理系统应用于小型设备，当安全加解密系统用 于嵌入式系统中，功耗问题会限制整体的性能，是设计者不可避免的关键问题。 因此，a e s 处理器的设计要兼顾以上要求，达到此五条要求的最佳折衷。 1 3 可配置处理器 1 3 1 工业界可配置处理器 处理器的发展经过四个时代。大约在上个世纪七十年代，出现了第一代处 理器从4 位处理器到早期的1 6 位和3 2 位微处理器，它们的出现为八十年 代第二代个人计算机和大型工作站技术的发展、数量的增长奠定了基础。第三 个时代发生在九十年代，以精简指令集砌s c 处理器为代表。这三代处理器中 的硬件模块是固定的，因此存在灵活性差的缺点。可配置处理器出现及发展标 志着第四代微处理器设计的开始。 从上世纪9 0 年代至今，可配置处理器作为通用处理器的补充和延伸，得到 了飞速的发展，并迅速实现了产业化。其中较为知名的可配置处理器公司及产 品有：t e n s i l i c ax t e n s a i j ，a r ca r c t 锄g e n t 【”】。 t c n s i l i c a 的x t c n s a 系列处理器( 包括x t c n 鼢7 、x t e n s al ) ( i 2 、d i 枷o n d 、 第一章绪论 x t e n s ad s p 等) 是目前技术最成熟、最主流的可配置可扩展处理器【1 9 】。它采用 可裁减扩充指令集的参数可配置的s c 体系结构，具有约8 0 条的基本指令。 t e n s i l i c a 提供有一个自动化工具集合，包括c 编译器、汇编器、连接器和调试 器。设计人员能够使用一种称为t i e 的语言来定义新增指令和功能部件【2 0 】，全 球逾1 2 5 家公司获得t e n s i l i c a 公司处理器核许可，其中包括a m d 、b r o a d c o m 、 c i s c o 、 c y p r e s ss e m i c o n d u c t o r 、 d e l l 、 e p s o n 、f u j i t s u 、i n t e l 、c 、l e n o v o 、 l ge l e c n o n i c s 、m a n r e l l 、m e d i 印h y 、m i t s u b i s m 、m o t o r o l a 、n e ce l e c t r o n i c s 、 n t t e l e c n o n i c s 、n v i d l 、o l y m p u “ p 柚a s o n i c 、 s 锄s u n g 、和s o n y 等国 际型大公司。x t e n s a 处理器的应用领域很广，如a m d 的i m a g e o n 系列媒体处 理器( h n a g e o n 系列被用于c i n g u l a r 、m o t o r o l a 、p 粕a s o n i c 和s a m s u n g 手机中) 。 e p s o n 、h p 最新打印机，m a r v e l l 、e m c 的网络设备，s 锄s u n g 的h d 无线通 信芯片，l ge l e c r o n i c s 的最新手机等领域均存在t e n s i l i c a 的解决方案，可见可 配置处理器具有广泛的市场和应用前景【2 1 1 。 1 3 2 传输触发架构可配置处理器 传输触发架构( t r a n s p o r tt r i g g e r a r c h i t e c t i l r e ，”r a ) 是由荷兰t ud e l r 计 算机工程系的d r h e n kc o 印o r 姚l 提出并设计的【2 2 1 ，典型的，兀a 处理器由各类 功能单元( f u ) 、寄存器堆附s ) 以及互连网络组成，如架构图所示2 5 。互连 网络分为总线( b u s ) 和s o c k e t 两部分，所有的f u 和r f s 通过s o c k e t 与总线 连接，彼此交换数据【2 3 1 。t t a 架构处理器的基本结构图如图1 1 所示，这里， 以四总线为例，图中a l u ( 舢i t i l i l l e t i cl o g i c a lu n i t ) 为算术逻辑单元，l s u ( l o a d s t o r cu n i t ) 完成核与数据存储器的数据交互功能。 4 第一章绪论 图卜11 v r a 架构处理器基本架构 不同于其他以r j s c 架构为基础的0 1 a ( 0 p e r a t i o nt r i g g e r e da r c h i t e c t l l r e ， 操作触发体系结构) 可配置处理器，1 1 r a 处理器的指令中没有操作码，而只 有源地址和目的地址码，数据从一个功能单元被发送到另一个功能单元，数据 发送过程本身即触发对应的功能操作。概括地说，t t a 处理器只有一类指令， 即数据传输指令：m o v e 洲，与其它处理器操作触发传输的机制不同，任何操作 都是通过传输来触发，可以说操作是传输的边际效应。为了实现指令集并行 ( i i l s t m c t i o nl e v e lp a r a l l e l i s m ，i l p ) ，最大限度限度并行处理数据，传输触发 架构处理器一般采用v l i w 的指令格式【2 5 1 ，每个指令槽只有源( s o u r c e ) ( 表示 数据来自何处) 和目的( d e s t i n a t i o n ) ( 表示数据去往何处) 两部分组成，以四 总线为例，指令示意图见图1 2 。1 r a 架构的f u 中有三种寄存器：操作寄存 器( o p e r 雅dr e g i s t e 船) ，触发寄存器( t r i g g e rr e g i s t c r s ) 和结果寄存器( r e s u l t r e g i s t e r s ) ，对于与每个功能单元，触发寄存器是必须的。指令中的源部分用来 编码结果寄存器和立即数，目的部分用来编码操作寄存器和触发寄存器。和超 标量( s u p e r s c a l a r ) 处理器的指令调度由硬件完成不同，v l i w 结构的处理器 将代码的调配分配工作交给编译器来完成【2 6 】。 匿 第一章绪论 基于t t a 架构中的f u 独立于互联逻辑，每个s o c k e t 相当于一个交叉开关， 每个时钟周期可以将总线上的一个数据传输到相应的f u 或r f ，也可将f u 、 r f 中的数据传输到一条或多条总线之上，通过s o c k e t ，总线与f u 、r f 构成了 松耦合的连接模式。总线、s o c k e t 、f u 、i 珂具有模块化( m o d u l a r 时) 的特点， 对应的硬件代码结构规整，规律性强，便于自动生成。 t 1 队架构采用混合流水线，包括两个的阶段：第一段包括：p c ( 预取指令) ， i f ( 取指令) ，d c ( 解码) ，o f ( 取操作数) 这四个阶段，对于任何指令，这四个阶 段都是固定不变的，一般为1 个周期。第二段包括：e x ( 执行) ，不同的指令， e x 所耗费的指令周期可能不同，例如普通的加减法和逻辑运算需要1 个周期， 而l o a d ，m a c ( 乘累加) 需要2 个周期，因此硬件f u 的设计具有灵活 ( f l e x i b i l i 哆) 的特点。 设计者可以根据具体应用和需求的性能，只需在遵循与s o c k e t 的标准接口 的基础上，设计特殊功能f u ，调整i 心数目，连接到总线上。因此t t a 架构 处理器具有可扩展( s c a l a b i l i 哆) 的特点。 1 4 论文主要工作和结构 1 4 1 本文的主要工作 1 分析并用c 语言实现a e s 算法，结合a e s 算法和”隗架构的特点，提 出优化a e s 的方法：将密钥扩展与轮变换并行实现，综合轮变换整个过程简化 数据流，并根据特殊运算定制功能单元，并在此基础上定制处理器总线宽度、 数目，寄存器数目，f u 种类及数量，从而定义出指令集。 2 基于t t a 架构的特点，总结出”队架构处理器硬件、汇编器自动生成 的方法，并自动生成面向a e s 加密的”r a 架构处理器。 3 验证并分析此处理器的性能，与通用处理器、d s p 、a s i c 实现进行比较， 并得出结论。 1 4 2 论文结构 本文共分五章，论文结构如下所示： 第一章，介绍了本文的课题研究背景、目的和意义。分析传统实现a e s 的 6 第一章绪论 方法存在的一些问题，提出基于n a 架构可配置处理器的a e s 的实现方法。 介绍目前业界主流的可配置处理器的市场和应用前景，分析传输触发架构处理 器的特点。 第二章，简单介绍传统实现a e s 的算法，提出基于n a 架构处理器的优 化方法，总结出面向a e s 加密n a 架构处理器的架构配置信息、编码信息和 f u 的种类。 第三章，介绍n a 架构处理器自动生成的方法：根据f u 的功能及时序信 息定制f u ，根据架构配制信息自动生成硬件架构、根据编码文件自动生成汇 编器，以a e s 应用为例，介绍a e s 可配置处理器的自动生成流程。 第四章，用m o d e l s i m 6 2 b 进行软件仿真验证，用x i l i n ) 【v i n c x 一 x c 4 v l x l 0 0 - f f l l 4 8 1 0 cf p g a 进行硬件原型验证，给出仿真结果。并给出处 理器在s 蹦c0 1 8 啪聊i c a l 工艺下d c 的综合结果和在f p g a 中所占硬件资 源。并与通用处理器：国芯公司的c c o r e 处理器c 3 1 0 ，a r m 7 ，a i 洲9 ，t i 公司的t m s 3 2 0 v c 5 4 1 0 e d s p 和a s i c ：i pc o r e ，v 队p a d l o c k 进行性能对 比，分析其优势和劣势。 第五章，总结全文，提出以后改进的目标。 7 第二章基于传输触发架构a e s 算法优化 第二章基于传输触发架构的a e s 算法优化 2 1 传统a e s 算法分析 r i i n d a e l 算法是基于块的对称加密算法，f e d e r a li n f o 咖a t i o l lp r o c e s s 访g s t 锄d a r d sp u b l i c a t i o n 中定义数据块大小为1 2 8b 砥，密钥长度为1 2 8 、1 9 2 、2 5 6b i t s 。 主要由密钥扩展和轮变换组成，轮变换主要由字节替换( s u b b v t e s ) 、行移位 ( s h i m t o w s ) 、列混合( m i ) 【c o l u m n s ) 、密钥和( a d d r o u n d k e y ) 组成。密钥 长度不同导致计算复杂度和加密安全性不同，密钥越长，密钥扩展需要的产生的 密钥越多，轮变换需要计算的轮数越多，计算时间越长，安全性能越高。密钥长 度、密钥扩展次数和加密轮数关系如表2 1 【2 7 1 。 表2 1 密钥长度与密钥扩展次数、加密轮数关系表 下面以1 2 8b i t s 明文，1 2 8b i t s 密钥为例详细介绍a e s 加密流程，流程如图2 1 所示。 第二章基丁传输触发架构a e s 算法优化 加 密： 图2 一la e s 加解密流程 首先，a e s 加解密过程中，数据基本运算都是建立在有限域g f ( 2 8 ) 的基础 之上。计算过程中涉及到有限域g - f ( 2 8 ) 的加法和乘法，这与实数域的加法和乘法 规则不同。 其次，定义一个名词，将加密计算过程中的中间结果叫状态，操作是以字节 为单位的，每个明文数据块( 1 2 8b i t s ) 可以对应的状态为一个4 宰4 的矩阵，如图 2 2 、 9 轮变换 最后轮 第二章基于传输触发架构a e s 算法优化 s 0 s 1s 2 s 3 s 4s 5s 6s 7 s 8s 9s 1 0s l1 s 1 2s 1 3 s 1 4s 1 5 图2 - 2 明文状态矩阵 但这里需要注意的是：a e s 明文数据输入对应到这里是s 0 ，s 4 ，s 8 ，s 1 2 ，s l ， s 5 ，s 9 s 3 ，s 7 ，s l l ，s 1 5 。 1 2 8b i t s 密钥的密钥矩阵如图2 3 ： k 0 k 1 l 【2 k 3 k 4k 5k 6k 7 k 8 k 9k 1 0k 11 k 1 2k 1 3k 1 4k 15 图2 3 密钥矩阵 同样需要注意的是：a e s 密钥数据输入对应到这里是k o ，k 4 ，k 8 ，k 1 2 ，k l ， k 5 ，k 9 l c 3 ，k 7 ，k 1 1 ，k 1 5 。 2 1 1 轮变换 普通轮变换包括：字节替换、行移位、列混合、密钥和；最后轮变换包括 字节替换、行移位、列混合、密钥和。伪代码如下： r d i u l d o s u b b y t e s o ； s h i f 淑o w s o ； m i x c o l u m n s o ； a d d r o u n d k e y ( r o u n d ) ； ) 1 0 第二章基于传输触发架构a e s 算法优化 f i n a l r d u n d o s u b b y t e s o ； s h i f 哌o w s o ； a d d r o u n d k e y ( n j t o l r n d - 1 ) ；n - j 之o l 7 n d = l 1 ) 2 1 1 1 字节替换 字节替换属于a e s 加密计算中的非线性部分，相比异或操作等线性部分，字 节盒替换具有难攻破的特点。实现时，本质上是根据明文数据的一个字节查表 s b o x ，利用明文中每一个字节的高四位作为行索引，低四位作为列索引，进行查 表，故s b o x 是1 6 1 6 数据表，查表的结果也是一个字节，即完成b y t e - b y t c 的转换， 而且字节与字节之间是独立的，其过程示意图如图2 4 。字节替换也是可逆的， 因此解密时，只需查i i l v s b o x 数据表( 注此数据表与s b o x 不是取逆的关系) 。 s 5 = 图2 - 4 字节替换示意图 1 6 ，l c l 6 _ s b o x 数据表 s 5 = 7 8 第二章基于传输触发架构a e s 算法优化 2 1 1 2 行移位 行移位是以状态矩阵中的每一行为单位进行操作的，4 木4 的状态表中的数据 第一行顺序不变，第二行循环左移一个b y t e ，第三行循环左移二个b y t e ，第四行 循环左移三个b ) r t c 。在解密时，逆行移位的每行移位的b y t e 数与加密数时相同， 只是将“循环右移”代替加密时的“循环左移 。行移位、逆行移位分别见图2 5 、 图2 6 ： s os 1s 2s 3 蕙习h 、 s 5s 6s 7s 4 蕙| 7 弱 k 、s 1os 1 1 s 8s 9 酽 霭卜 js l5s 1 2 s 1 3s 1 4 厂t ，； 图2 5 行移位示意图 s os 1s 2s 3 s 4s 5s 6s 7 刊 ；锡一 隆：翻 s 8s 9s 1 0s 11 刊习一 s 1 2 s 1 3s 1 4s 15、- h j 7 湖 一 一翎 2 1 1 3 列混合 图2 - 6 逆行移位示意图 列混合是以状态矩阵中的每列为单位进行操作的，每一列作为有限域 g f ( 2 8 ) 上的一个多项式乘以一个固定的多项式a ( x ) = 0 3 ) x 3 + 0 l x 2 + 0 1 ) x + 0 2 ) 。这里涉及到有限域g f ( 2 8 ) 的乘法，包括四字节的乘法和字节乘法。 对于域中的四字节乘法，如果相乘的结果发生溢出，再与多项式x 4 + l 取模， 设在列混合之前，状态矩阵为s ( x ) ，经过列混合之后，状态矩阵为s ( x ) = a ( x ) s ( x ) ，矩阵表示为： 1 2 第二章基于传输触发架构a e s 算法优化 j 0 s l s 2 s 3 0 20 30 10 1 0 10 20 30 l 0 10 10 20 3 0 30 10 10 2 s o s l s 2 j 3 ( 2 - 1 ) 列混合也是可逆过程，在解密时，反列混合之前状态s 和之后状态s 的关系为 s ( x ) = a 1 ( x ) s ( x ) ，矩阵表示为： s 0 s 1 s 2 s 3 o p0 60 d0 9 0 9o p0 6o d 0 d0 90 p0 6 0 60 d0 90 p j 0 s l s 2 s 3 ( 2 - 2 ) 其中，矩阵对应元素的乘法为字节乘法，在g f ( 2 8 ) 域中，一个字节与最高项 小于等于x 7 的多项式系数一一对应，例如h ( x ) = a 7 木x 7 + a 6 宰x 6 + a 5 奎x 5 + a 4 幸x 4 + a 3 母x 3 + a 2 x 2 + a l x 1 + a o 枣x 0 与a 7 a 6 a 5 a 4 a 3 a 2 a l a o 这一个字节数据是一一对应的，字节乘 法可以转化为八组一个字节数据与1 b i t 数据的乘法，再把这8 个结果相加( 有限域 g f ( 2 8 ) 的加法就是异或运算) 。下面以x 宰h ( x ) 为例，介绍乘法规则 椭_ = = ：。篆； ， 、7 l 粕邪a 4 a 3 a 2 a l a o o0o x l b i fa 7 ：1l 叼 由以上关系可推出x 1 幸h ( x ) ( i = o 7 ) 的结果，从而得出字节乘法的结果。 可见，对于列混合计算，结果的状态矩阵中的每一个元素需要进行数据宽度 8b i t s 的乘法四次，异或运算三次。因此，进行一次列混合共需要字节乘法6 4 次， 异或运算4 8 次。 2 1 1 4 密钥和 在有限域g f ( 2 8 ) 中，“和”运算相当于异或运算。“密钥和”本质上就是状 态矩阵和密钥矩阵对应元素的异或运算。密钥和计算的示意图如图2 7 所示 第二章基丁传输触发架构a e s 算法优化 s os 4s 8s 12 s 1s 5s 9 s 1 3 s 2s 6s 1os 14 s 3s 7s 11s 15 k ok 1l 也l ( 3 k 4 k 5 k 6k 7 k 8 k 9k 1 0k l1 k 1 2k 1 3k 1 4k l5 图2 7 密钥和过程 其中s t i = s iol 【i i = 0 ，1 1 5 。 2 1 2 密钥扩展 s os 1s 2 s 3 s 4s 5s 6s 7 s 8s 9s l os 1 1 s 1 2s 1 3s 1 4s 15 对于1 2 8b h 明文、1 2 8b i t s 密钥的a e s 加密，输入为初始1 2 8b i t s 密钥，经过 密钥扩展，扩展出1 0 组1 2 8b 砥密钥，初始密钥与明文进行初始密钥和 ( a d d r d 啪d k e y o ) ，产生的这1 0 组密钥分别按顺序与9 轮轮变换( r d u n d ) 和最 后轮变换( f i n a l r o u i l d ) 的明文进行异或运算。 扩展算法如图2 8 所示，l ( o ，k 1 k 1 5 为初始密钥，1 6 个字节可以组成4 个字， 每个字3 2 位，则k e y ( o ) = 【w 0 ，w 1 ，w 2 ，w 3 】，任意密钥可表示为k e y ( i ) = 【w 4 i ，w ( 4 i + 1 ) ，w ( 4 i + 2 ) ，w ( 4 i + 3 ) 】，i 表示加密轮数，任意字w j 的值取决于j 、w ( j 一4 ) 与w ( j 1 ) 的值。如璃不是4 的倍数，w j = w ( j 一4 ) + w ( j 一1 ) ，如果j 是4 的倍数， 需要对w ( j 一1 ) 作一定转换。例如j = 4 ，w 3 = k 。：k 。k 。k 。，需要首先对w 3 作循环左移 一个字节：m 3 = k 。k 。k ，。k 。：；其次，利用s 盒变换对每个字节进行字节替换，v 3 = k t 。k 、，t k 。s k 、1 2 最后再与轮常数r c o n i 】异或，轮常数这个字只有最高字节存在 有效值，较低的三个字节总是“0 ，即r c o n 【i 】= 限c 【i 】，o ，0 ，o 】，i 与r c 【i 】的 关系见表2 2 ( 表中r c 【i 】为1 6 进制) 。 表2 2r c 【i 】 1 4 第二章基于传输触发架构a e s 算法优化 k o k l l ( 2 l 【3 2 2a e s 性能的优化 2 2 1 性能优化理论分析 图2 8 密钥扩展原理图 性能优化一般体现在以下几个方面： l 算法层面，例如d c t ( 离散余弦变换) ，其功能是完成时域到频域的转 换，对于n 木n 点二维d c t ，本质上是乘累加，需要n 2 次乘法，n m 1 ) 次加法， 存在一些d c t 快速算法，例如w h c h 算法【2 引、l o e f f l e r 算法f 2 9 】f 捌；又如d f t ( 傅立叶变换) ，现在存在基2 、基4 、高基、混合基f f t ，这些快速本质思想 是利用三角函数性质进行等价变形，以达到减小计算次数的目的；无论用软件 实现还是硬件实现，算法的优化都会带来性能的提高，可以说算法的优化对性 能的提高是“革命性的”。 2 架构层面，在算法固定的前提下，架构的定义对性能至关重要，一般公 司里的架构工程师都是比较有经验的工程师。例如3 音频解码器一般采用 m c u + d s p 的实现方式，只采用m c u 是无法达到性能要求，又如视频处理芯 片一般采用m c u 十a s i c 的解决方案，m c u + d s p 或单纯m c u 也无法完成实 第二章基于传输触发架构a e s 算法优化 时处理的任务。 3 硬件单元层面，对于传统a s i c 的实现方法，主要是在算法固定的前提 下，优化数据流路径和控制方式以实现性能的提高，例如对于带有循环的算法， 是采用复用单元，循环方式实现，还是采用流水线实现；对于传统d s p 而言， 硬件单元是固定的，用户不可修改；而对于可配置处理器，用户可以根据算法 的特点，把大量重复计算模式硬件化，使其在较短的时钟周期完成。 4 软件层面，对于代码编写也存在一定技巧，尤其对于编译器不太成熟的 时候，代码编写时更需要程序员了解硬件底层细节，寄存器分配、指令调度基 本原理，代码执行时间的关键路径等等。 对于任意应用，这几个方面的优化是按照顺序进行的。一般来讲，越高层 次优化对于性能的影响越大，算法或架构层面的优化效果要好于软件或硬件优 化。 本文性能的优化主要涉及算法的优化，结合a e s 算法和传输触发架构特点 对软件汇编代码的优化，最后根据特殊操作对特殊功能功能单元进行定制。 2 2 2 将g f ( 2 8 ) 域中的字节乘法转化为查表 按照上述a e s 算法用c 语言实现，在国芯公司的3 2 位c 木c o 刚c 3 1 0 处理器上利用四组数据统计加密( c i p h e r o ) ，解密( i n v c i p h e r o ) 的时钟周期数，统 计结果见表2 3 。 表2 3a e s 加解密在c c o i 冱t mc 3l o 上的时钟统计 详细统计加密中最重要部分轮变换所占的周期数，统计结果见表2 4 ， 相比与字节替换、行移位、密钥和，列混合是算法中最大的瓶颈，占到整个轮 变换的9 5 以上，究其原因：一方面是一次列混合共需要字节乘法6 4 次，异 或运算4 8 次，这是算法决定的，无法修改，另一方面字节乘法比较复杂，每次 字节乘法大约耗费3 1 0 0 个周期，所有字节乘法占到整个列混合的9 5 以上， 可见减小字节乘法的时间是提高系统性能的关键。 1 6 第二章基于传输触发架构a e s 算法优化 0 20 30 l0 1 加密时字节乘法涉及的固定数组l 三：署芝芝 0 30 10