（控制理论与控制工程专业论文）数据加密算法的研究与实现.pdf

东北大学硕士学位论文摘要 数据加密算法的研究与实现 摘要 随着集成电路制造技术进入深亚微米阶段，芯片集成度呈指数级增长，使得片上系 统( s y s t e mo n a c h i p ，s o c ) 成为可能，并成为当今集成电路设计的发展趋势。基于知 识产权( i n t e l l e c t u a lp r o p e r t y ，i p ) 复用的s o c 设计方法已成为当今集成电路设计的主 要方法，同时，随着网络信息技术的飞速发展，对作为信息安全基础的信息安全芯片的 设计与开发也提出了高速、高可靠性、高安全性等要求。信息安全芯片的设计开发既要 与当今s o c 设计方法相适应，又要兼容国内外流行的密码标准体系，保证芯片设计的 自主知识产权。 本文首先研究了高级加密标准( a d v a n c e de n e r y p t i o ns t a n d a r d ，a e s ) 算法、公钥 密码算法( r s a ) ，并针对两种算法各自的优缺点，采用将两种算法结合在一起来实现 对数据进行加解密的混合加解密算法。在a e s 算法实现中，在对比了流水线结构、内 部流水线结构和循环展开结构的速度和特点之后，选择了基本结构来实现算法。在a e s 算法密钥扩展方面，采用了加密同步扩展，并将各扩展密钥存入存储器中，在解密时从 存储器中读取密钥的方法。在r s a 算法实现中，采用了以低位乘法器单元连乘、连加 的方式来实现高位乘法器，以查找表来实现试商等方法，大大减少了所需的芯片资源。 本文按照自顶向下的设计方法，采用可综合的代码风格，在q u a r t u s 4 2 软件中分别 设计了a e s 算法、r s a 算法各个功能模块的v e f i l o g h d l 代码，并进行了仿真，验证了 设计的正确性，并以a l t e r a 公司的c y c l o n e 系列e p l c 6 q 2 4 0 c 8 型f p g a 为载体进行了 映射和实现，其a e s 算法加密正常工作的时钟频率为3 3 3 3 m h z ，解密为2 8 5 7 m h z ， r s a 算法中的模乘单元的正常工作速率为6 5 0 次秒。 在设计出了a e s 、r s a 两种算法的i p 核设计之后，研究了a l t e m 公司开发的3 2 位n i o s i i 嵌入式软核的特点，给出了一个基于可编程片上系统( s y s t e mo n a p r o g r a m m a b l ec h i p ，s o p c ) 的嵌入式混合加解密系统的设计，本设计充分利用前面设 计的a e s 、r s a 两种算法的p 核，结合s o p c 的设计方法，分别定制了a e s 、r s a 两 种算法的自定义指令，通过在n i o si 嵌入式软核上编写c 语言算法代码来实现对数据 的加解密功能，大大提高了算法实现的灵活性。 关键词：数据加密，高级加密标准算法，公开密钥算法，可编程片上系统，知识产权 一 东北大学硕士学位论文 a b s 打a c t r e s e a r c ha n dr e a l i z a t i o no f e n c r y p t i o n a r i t h m e t i cf o rt h ed a t a a b s t r a c t w i t ht h et e c h n i q u eo ft h ei cm a n u f a c t u r ee n t e r i n gi n t ot h ev e r yd e 印s u b - m i c r o n ，t h e i n t e g r a t i o no f i ct a k e so ne x p o n e n t i a li n c r e m e n t ，w h i c hm a k e st h es y s t e mo nf lc h i p ( s o c ) p o s s i b l ea n dt u r n si n t ot h ed e v e l o p m e n tt r e n do f i cd e s i g nn o w t h em e t h o do fs o cd e s i g n b a s e do nt h er e u s e f u li pc o r eh a sb e e nt h ec h i e fm e t h o di ni cd e s i g n a tt h es a m et i m e ，w i t h t h er a p i dd e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n i q u e ，t h ec h i p so fi n f o r m a t i o n a ls e c u r i t yn e e d 1 l i 曲s p e e da n dh i g hr e l i a b i l i t y t h ed e i s g no ft h ei n f o r m a t i o n a ls e c u r i t y sc h i p sn e e d st h e a p p l i c a t i o no ft h en e wm e t h o do fs o cd e s i g n a c c o r d s 、i mt h eo v e r s e a sc r y p t o g r a g h ya n d a s s u r e st h ei n t e l l e c t u a lp r o p e r t yr i g h to f t h ec h i p s t h i st h e s i sf i r s ts t u d i e st h ea r i t h m e t i co fa d v a n c e de n c r y p t i o ns t a n d a r d ( a e s ) ，t h e a r i t h m e t i co f p u b l i ck e ya r i t h m e t i c ( r s a ) ，a n dp u t sf o r w o r dam e t h o do f e n c r y o p t i n gd a t ab y c o m b i n i n gt w oa r i t h m e t i c s i ni m p l e m e n t i n gt h e a r i t h m e t i co fa e s ，a f t e ra n a l y z i n ga n d c o n t r a s t i n gt h ec h a r a c t e r i s t i c so fp i p e l i n ea r c h i t e c t u r e ，s u b , p i p e l i n ea r c h i t e c t u r ea n dl o o p u n r o l l i n ga r c h i t e c t u r e t h et h e s i sc h o o s e st h eb a s i ca r c h i t e c t u r et oc o m et r u e i nt h ea s p e c to f k e ye x p a n s i o n , s y n c h r o n o u se x p a n s i o ni sa d o p t e di ne n c r y p f i o n , w h i c hh o l d st h ee x p a n d e d k e yi nt h em e m o r y , a n dr e a d st h ek e yi nd e c r y p f i o n i ni m p l e m e n t i n gt h ea r i t h m e t i co fr s a ， t h i st h e s i sc o m e st r u et h el a r g ed a t am u l t i p l i c a t i o nb ya d o p t i n gt h ec o n t i n u o u sm u l t i p l ya n d a d dw i t ht h es m a l ld a t am u l t i p l i c a t i o n ，a n dc o m e st r u ec o m p u t i n ga r i t h m e t i c a lc o m p l i m e n t r e m a i n d e rb yt h el o o k u pt a b l e ，w h i c hh u g e l yd e c r e a s e st h ea r e ao ft h ec h i p t h et h e s i sa d o p t sa t o p - d o w n ”d e s i g nm e t h o da n dd e s c r i b e st h ea r i t h m e t i co fa e sa n d r s aw i n lv e r i l o gh d la tt h ef u l ls y n t h e s i z a b l er t ll e v e lo nq u a r t u s 4 2 a n dc o m p l e t e st h e s i m u l a t i o no ft h er t lt os h o wt h ec o r r e c tr e s u l to ft h ed e s i g n a n dt h e nt h ei m p l e m e n to ft h e d e s i g ni sp e r f o r m e db a s e do nt h ea l t e r a sc y c l o n ee p l c 6 q 2 4 0 c 8f p g aw i 廿lt h er e s u l t s s h o w i n gt h a tt h ef r e q u e n c y3 3 3 3 m h zi na e se n c r y p t i o na n d2 8 5 7 m h zi na e sd e c r y p f i o n a n dc o m p l e t i n g6 5 0t i m e so fm u l t i p l ya n dc o m p u t i n ga r i t h m e t i c a lc o m p l i m e n tr e m a i n d e rp e r s e c t i o ni nr s a a f t e rt h ed e s i g no f t h ei pc o r eo f t h et w oa r i t h m e t i c s ，p u t t i n gf o r w o r dam e t h o do f m i x e d e n c r y p t - d e c r y p tm e t h o db a s e do ns o p c ，w h i c hm a k e sf u l ln s eo ft h ec h a r a c t e r i s t i c so ft h e i i i 东北大学硕士学位论文 a b s t r a c t n i o si i ss o f t - c o r ei na l t e r a t h i sd e s i g nm a k e sf u l lu s eo ft h ei pc o r eo ft h ea e sa n dr s a ， i n t e g r a t i n gt h ed e s i g nm e t h o do fs o p c ，t h ei m t h o rm a k e ss e p e r a f l yc u s t o mi n s t r u c t i o no f t w oa r i t h m e t i c s ，a n dp r o g r a m st h ecc o d eo fa r i t h m e t i ct oi m p l e m e n tt h ef u n c t i o no f e n c r y p t d e c r y p td a t ao i lt h es o f t c o r e o fn i o s1 1 ，w h i c hh u g e l yi n c r e a s e st h ea g i l i t yi n i m p l e m e n t i n gt h ea r i t h m e t i c k e yw o r d s ：d a t ae n c r y p t ，a d v a n c e de n c r y p t i o ns d a n d a r d ，p u b l i ck e y a r i t h m e t i c ， s y s t e mo nap r o g r a m m a b l ec h i p ，i n t e l l c t u a lp r o p e r t y i v 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名：名彬 签字日期：妒 一i 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：导师签名： 签字日期：签字日期： 东北大学硕士学位论文第一章绪论 第一章绪论 1 1 研究背景及意义 随着信息化与网络化的飞速发展，网络己极大的改变了人们的生活，人们可以通过 网络实现网上购物、网上办公、共享资源等活动【”。与此同时，由于计算机网络所具有 的开放性与共享性，其安全性也成为人们日益关切的问题。特别是有关国家安全的政治、 经济和军事情况以及一些企业和私人的机密与敏感信息的安全性问题，已成为威协国 家、企业、个人的主要问题。我国的信息化、网络化建设在技术与装备上对别国的极大 依赖性，使得信息安全问题尤为突出。我国的信息网络安全研究起步较晚，安全防护能 力处于发展的初级阶段，与发达国家有较大差距。数据加密技术是解决信息安全问题的 重要手段，密码技术是网络安全与保密的核心和关键。因此，加快研究与开发带有加解 密功能的电子产品、开发具有自主知识产权的信息安全芯片已成为我国电予技术开发人 员的当务之急。 加密技术按照密码使用方法分为对称密钥算法和非对称密钥算法。对称密钥算法 中，加密、解密都使用相同的密钥。非对称密钥算法又称为公钥密码算法，即加密、解 密使用两个不同的密钥。公钥密码算法能够有效地解决密钥分发和不可否认服务等问 题，而这些问题正是对称密钥算法难以有效解决的。目前，公钥密码算法已经广泛应用 于信息源的身份认证、数字签名和密钥分发。特别是公钥密码技术r s a 算法的芯片级 实现，代表着一个国家在信息安全领域的水平。对称密钥算法虽不利于密钥管理，但加 解密速度较高。公钥密钥算法便于密钥管理和数字签名，但加解密速度较低。因此，采 用混合加解密算法，综合了对称密钥算法和公钥密码算法的优点，有效的得到了一种新 的加解密方案，即采用对称密钥算法实现大量信息的安全存储与传输，采用公钥密码算 法实现对称密钥算法的密钥的存储与传榭2 】。 信息的加解密运算，既可以通过软件来实现，也可以采用硬件来完成。与传统的软 件加解密相比，硬件加解密具有速度快、安全性高的优点。随着集成电路设计技术的不 断发展，基于i p 复用的s o c 设计技术已成为当今集成电路设计的主要技术。因此，研 究与开发具有自主知识产权的对称密钥算法和公钥密码算法的i p 核，加快信息安全芯 片国产化，无论是对我国集成电路设计产业的发展还是对缩短我国在信息安全领域与外 国的差距，有着重要的战略意义。在对称密钥算法中，a e s 算法汇聚了高安全、高性能、 易用和灵活等优点。它是一个迭代分组密码算法，其分组长度和密钥长度都是可变的， 一1 一 东北大学硕士学位论文第一章绪论 分组长为1 2 8 位，密钥长度为1 2 8 1 9 2 2 5 6 位，相应的轮数为1 0 1 1 2 1 4 。a e s 算法采用 代替置换网络，每轮由3 层组成：线性混合层，确保多层之上的高度扩散；非线性混合 层，由1 6 个s 盒( 替换盒) 并置而成，起到混淆的作用：密钥加层，子密钥简单地异 或到中间状态上去。s 盒选取的是有限域g f f 2 8l 中的乘法逆运算，它的差分均匀性和 线性偏差都达到了最佳。对称密钥算法的个薄弱环节是密钥的传递。在公钥密码算法 中，1 9 7 8 年由r i v e s t ，s h a m i r 和a d l e m a n 在美国m i t 提出的r s a 算法被公认为是目前 理论与实际应用中最为成熟的一种公钥密码体制口1 1 4 】，可以用来进行数字签名和身份认 证f 5 i 。该算法的安全性依赖于大整数的素数因子分解的困难性，其最基本最核心的算术 操作是模乘运算，再由一系列的模乘来完成模幂运算。将a e s 的密钥经r s a 算法加解 密，大大提高了a e s 算法密钥的安全性。用硬件描述语言来描述a e s 算法和r s a 算法， 分别实现a e s 算法和r s a 算法的i p 核，再将二者结合在一起，从而形成一个新的加解 密i p 核。结合a e s 算法和r s a 算法的p 核可以很方便的通过基于口复用的s o c 设 计方法集成到当前的系统芯片中，必将大大提高系统的安全性和保密性嘲【刀。 1 2 国内外研究发展状况及趋势 a e s 已于2 0 0 2 年生效，当前正处在a e s 算法应用的蓬勃发展阶段，尽管它在软 件中得到了较多的应用，但是相应的硬件产品却不是很多。就硬件实现而言，国外许多 公司都相继推出了自己的商用a e si p 核，如h e l i o n 技术有限公司、d 、c r y p t p t e 技术有 限公司及o c e a nl o g i c p t y 技术有限公司等。对国内来说，虽然有关a e s 算法的硬件产 品还很少，但越来越多的国内公司和研究机构已经把目光投入到a e s 的硬件实现当中， 相关的研究项目也如雨后春笋般出现。 对于r s a 算法的研究，目前，主要是对m o n t g o m e r y 模乘算法的研究。一种是采 用高基的结构，另一种是采用脉动阵列的方法实现。相对于国外对于r s a 硬件实现研 究的成熟，国内在这方面起步比较晚，能最终流片成功，做成r s a 芯片的公司很少。 深圳中兴集成电路设计有限公司已经成功的设计出了模幂乘密码算法协处理器芯 片一s s x 0 4 f s ，支持的最高时钟频率为1 0 0 m h z ，模长和幂长都为1 0 2 4 位时的模幂运算 速度为6 6 次秒。 北京天一集成科技有限公司的r s a 密码算法芯片及核，是国内首个运算速度为 2 0 0 0 次秒的1 0 2 4 位公钥密码算法芯片。 针对国内外对密码算法的不断深入研究，将各种算法结合在一起已成为一个发展趋 2 东北大学硕士学位论文第一章绪论 势。本设计正是将基于两种不同体制的加解密算法结合在一起来实现对数据的加解密功 能，并将其应用在a l t e r a 公司的s o p c 系统中，从而充分利用s o p c 系统设计的灵活性， 大大提高了系统的应用范围 9 】 1 0 1 。 1 3 片上系统的设计方法与流程 集成电路( i c ) 加工工艺的发展使得片上系统( s o c ) 成为电子设计领域发展的新 趋势【l ，s o c 是一个复杂的系统，它一般将一个完整产品的各个功能集成在一个芯片上 或者芯片组上。一般意义上，s o c 设计包括一个可编程的处理器、片上存储器、硬件加 速单元( 如图像声音处理单元、d s p 、浮点协处理器等) 、与外围设备的接口、a d d a 转换以及射频部分。一个典型的s o c 结构如图1 1 所示。s o c 涉及软硬件的协同设计， 硬件中包括模数混合单元，甚至包括微机电或者微光电单元，对于如此复杂的系统，现 有的i c 设计方法已经不再适用。历史上每一次i c 加工工艺的巨大进步必然带来i c 设 计领域设计方法的革命，以满足市场的需要，例如在2 0 世纪8 0 年代出现的以单元库为 基础的a s i c 设计方法极大的促进了集成电路的发展。现在s o c 设计所要求的新的设计 方法必须满足以下的条件：缩短设计时间，降低设计的复杂度，保证设计性能的可预测 性，减少s o c 系统设计和实现的风险。s o c 的设计采用t o p - d o w n 和结构化的方法【1 2 1 ， 以各种可复用的i p 为基础，以软硬件协同设计为主要方法来开发s o c t 6 i 。i p 是具有知 识产权的、已经设计好并经过验证的可重复利用的集成电路模块。比如存储器核、a r m 微处理器核、s p a r c 微处理器核等等。这里的p 主要包括虚拟部件v c ，设计和重用 相关的接口标准。国外的许多i c 设计公司多年来积累了大量的口核，包括软核、固核 和硬核，显然利用现有的口进行设计可以改善和提高系统性能，减少设计瓶颈，大大 缩短了产品的上市时间【13 】。 图1 1s o c 典型结构 f 追1 1 t h et y p i c a la r c h i t e c t u r eo f s o c 3 东北大学硕士学位论文第一章绪论 目前，s o c 设计技术主要采用基于平台的s o c 设计技术，主要是以现有的微处理 器核及片上总线为开发平台，如a r m 公司的a r m 核以及a m b a 总线、i b m 的 p o w e r p c 核及c o r e c o n n e c t 总线等等。平台的应用就是在口核的基础上进行软件和硬 件的协同设计。图1 2 显示了一个典型的s o c 的设计流程【1 1 1 。首先根据用户的要求提出 整个系统的设计规范以及系统的整体描述，包括系统的行为描述和结构描述。行为描述 就是对系统划分出具有不同功能的各个子模块，然后根据这个行为级的功能划分进行结 构描述，也就是把手中掌握的i p 核( 包括已有的或者自己设计的或从第三方购买的口 核) 对应到各个功能模块。之后，通过系统仿真与系统行为描述交互修正，确定系统结 构描述和软硬件划分。s o c 中所使用的i p 核来自不同的供应商，有些还可能是用户自 己设计的。所以i c 设计工程师必须对它们进行必要的修改和描述，以解决不同模块在 s o c 设计中验证的一致性问题【l4 j 。 物理设计 面积功耗时 钟要求 优化面积硬件设计软件设计 速度功耗 时钟频率 i o 要求 任务分配 算法开发 软件要求 用例分析 版图设计 i 1 模块时序i 1 划分子块1 1 代码开发 纛：积i h i 模块级综合l h | 模块级蛳h 原型开发功耗版图+ + i 模块级综合f + i 模块级验证h i 原型开发 布局布线l l _ j 顶级综合l l _ 一顶级验证l l _ j 软件测试 图1 2s o c 设计流程图 f i g 1 2 t h ed e s i g nf l o wo f s o c 由此可以看出，现代s o c 设计的基础是各种i p 核的设计。开发高性能的i p 核，建 立i p 核库对我国的集成电路设计业的发展，缩短与国外集成电路设计水平有着十分重 要的战略意义。i p 核的设计应遵循一定的规范与标准，以获得最好的可重用性、可扩充 4 东北大学硕士学位论文第一章绪论 性等品质。目前，虚拟插座接口联盟( v i s a ) 制定了一系列的口核设计规范和标准 1 5 】 1 6 1 。 目前，i p 核的设计流程如下： 制定设计规范，抽象地描述所设计的电路功能、接口和整体结构； 进行功能级的描述和r t l 级的描述； 利用e d a 工具进行功能级的仿真与验证； 结合具体工艺进行逻辑综合，将r t l 的h i ) l 代码映射到具体的工艺上加以实现； 门级仿真，逻辑综合工具将r t l 描述转换成门级网表，并将网表中的延时存成标 准延时文件，以用于门级仿真时将综合出来的电路中的延时信息随测试代码一起送入仿 真器中。 根据不同需求可将m 核设计成硬核、固核、软核的形式。硬核是指将r t l 代码经 综合、布局布线、d r c 、l v s 等工具处理后所得到的，通常以g d s 的形式交付。软核 是指经过验证的r t l 代码，并且是可综合的。通常以r t l 形式提供。固核是介于软核 和固核之间的一种形式，可提供部分版图信息。 这一点非常重要，把设计过程分为几个独立的阶段，但并不是指那种严格的自顶向 下的设计方法。通常为了确保设计能够实现，必须在制定设计规范之前，做一些详细的 设计工作。 严格的自顶向下设计方法是指如果上一阶段没有完成，下一阶段就不能开始。目前 各大公司大多采用的是一种混合的方法，就是将自顶向下的设计方法与自底向上的设计 方法结合在一起来完成设计。 1 4 本课题研究的主要内容 本课题深入研究了当今比较流行的两种数据加密算法，结合硬件描述语言 v e r i l o g h d l 实现电路结构的特点，以尽量小的芯片资源来实现算法为目的，分别对a e s 算法、r s a 算法进行了比较合理的模块划分，设计了相应模块的寄存器传输级( r t l ) 代码描述，并使用a l t e r a 公司的q u a r t u s 4 2 软件进行了功能仿真。研究了a l t e r a 公司的 s o p c 系统的设计方法，充分利用其用户自定义指令灵活性的特点，进一步对两种数据 加密算法进行了分析，通过在n i o s 软核处理器上定制几条加密算法专用指令，采用c 语言对这些指令进行调用来完成加密算法的编程。 论文组成如下： 第一章介绍了本论文的研究背景和意义、目前国内外在数据加密算法方面的研究现 东北大学硕士学位论文第一章绪论 性等品质。目前，虚拟插座接口联盟( v i s a ) 制定了一系列的i p 核设计规范和标准【1 6 】。 日前，p 核的设计流程如下： 制定设计规范，抽象地描述所设计的电路功能、接口和整体结构； 进行功能级的描述和r t l 级的描述； 利用e d a 工具进行功能级的仿真与验证； 结合具体工艺进行逻辑综合，将r t l 的h d l 代码映射到具体的工艺上加以实现； 门级仿真，逻辑综合工具将r t l 描述转换成门级网表，并将网表中的延时存成标 准延时文件，以用于门级仿真时将综合出来的电路中的延时信息随测试代码一起送入仿 真器中。 根据不同需求可将i p 核设计成硬核、固核、软核的形式。硬核是指将r t l 代码经 综合、布局布线、d r c 、l v s 等工具处理后所得到的，通常以( m s 的形式交付。软核 是指经过验证的r t l 代码，并且是可综合的。通常以r t l 形式提供。固核是介于软核 和固核之间的一种形式，可提供部分版图信息。 这一点非常重要，把设计过程分为几个独立的阶段，但并不是指那种严格的自顶向 下的设计方法。通常为了确保设计能够实现，必须在制定设计规范之前，做一些详细的 设计工作。 严格的自项向下设计方法是指如果上一阶段没有完成，下一阶段就不能开始。目前 各大公司大多采用的是一种混合的方法，就是将自顶向下的设计方法与自底向上的设计 方法结合在一起来完成设计。 1 4 本课题研究的主要内容 本课题深入研究了当今比较流行的两种数据加密算法，结合硬件描述语言 v e f i l o g h d l 实现电路结构的特点，以尽量小的芯片资源来实现算法为目的，分别对a e s 算法、r s a 算法进行了比较合理的模块划分，设计了相应模块的寄存器传输级( r t l ) 代码描述，并使用a l t o r a 公司的q u a r t u s 4 2 软件进行了功能仿真。研究了a l t e r a 公司的 s o p c 系统的设计方法，充分利用其用户自定义指令灵活性的特点，进一步对两种数据 加密算法进行了分析，通过在n i o s 软核处理器上定制几条加密算法专用指令，采用c 语言对这些指令进行调用来完成加密算法的编程。 论文组成如下： 第一章介绍了本论文的研究背景和意义、目前园内外在数据加密算法方面的研究现 第一章介绍了本论文的研究背景和意义、目前国内外在数据加密算法方面的研究现 东北大学硕士学位论文第一章绪论 状、当今s o c 设计的典型流程和本课题的研究内容。第二章详细介绍了a e s 算法、r s a 算法的数学基础及算法描述。第三章以减少芯片资源为目的，分别对a e s 算法、r s a 算法的结构和算法进行了分析、研究，用v e r i l o gh d l 语言设计了具有可综合风格的代 码，并在a l t e r a 公司的q u a r t u s 4 2 软件上进行了各个模块的仿真、验证，给出了仿真结 果的波形图，其结果表明了设计功能的正确性。第四章在深入研究了a l t e r a 公司的s o p c 系统设计方法、特点之后，设计了用于实现数据加密算法的用户自定义指令。第五章给 出了全文工作的结论与展望。 东北大学硕士学位论文 第二章数据加密算法原理 第二章数据加密算法原理 2 1a e s 算法数学基础 2 】1 字节运算 字节运算是a e s 的基本运算，一个字节可以被看作g f ( 2 8 1 的元素1 7 1 。有限域 g f ( 2 8 1 可定义为三元组：( f ，+ ，+ ) ，其中： f = ( b , b ：, b a b a b o ) l b , = o ，1 ；f = 0 , 1 7 。 ( 1 ) f 中的加法“+ ”定义为： ( 嘶魄吩吼吗呸q 嘞) + ( 6 7 玩如良6 3 如臣6 0 ) = ( c ，c 6 c 5 c 4 c 3 c ：c i c 0 ) ， c = q o 缸，i = o 1 7 ，而。是按位异或。 事实上，加法就是字节的按位异或运算，例如： l 10 00ll0 + 】0 】01101 0l l0lul l 所以：1 1 0 0 0 1 1 0 + 1 0 1 0 1 1 0 1 = 0 1 1 0 1 0 1 1 。 ( 2 ) f 中的乘法“+ ”定义为： ( a 7 a 6 a s a 4 a 3 a 2 a l a o ) ( 6 7 玩6 5 6 4 岛6 26 1 6 0 ) = ( c 7 c 6 c 5 c 4 c 3 c 2 c 1 c 0 ) ，其中： 口( x ) = a t x 7 + a 6 x 6 + a s x 5 + a 4 x 4 + a 3 x 3 + a 2 x 2 + a l x + a o b ( x ) = b 7 x 7 + 玩+ 岛x 5 + 6 4 x 4 + 6 3 + 如x 2 + b , x + b o c ( x ) = 白z 7 + 吒+ c 5 x 5 + c 4 x 4 + c 3 x 3 + c 2 x 2 + g x + c o 历( x ) = x 8 + x 4 + x 3 + x + 1 。 则： c ( x ) = a ( x ) b ( x ) m o d m ( x ) ， 其中口( x ) 6 ( x ) 是普通多项式乘法，但系数运算看作比特的乘法和异或运算，即看作最小 域e = o ，1 ) 上的运算。可见乘法运算不如加法运算那么简单，这也是a e s 运算费时的地 方。 ( 3 ) z 乘运算定义为： 工乘是乘法运算的特例，即用工乘以一个多项式再模棚( x ) ，记为6 = x t i m e ( a ) 。 一，一 东北大学硕士学位论文第二章数据加密算法原理 j 乘可用字节内左移和其后的一个与m ( x 1 的条件比特异或来实现。可以证明在所定义 的加法及乘法运算下构成一有限域且同构于g f ( 2 8 1 。 例：根据对g f f 2 8 ) 的表示方法，1 6 进制5 7 和8 3 所表示的元素之间的乘积等于1 5 进制数c l 所表示的元素，计算如下： ( x 6 + 工4 + 工2 + x + 1 ) ( 工7 + 工+ 1 ) = x 1 3 + x 1 1 + x 9 + x 6 + x 5 + x 4 + x 3 + 1 ( 一3 + z 1 1 + z 9 + + + x 4 + x 3 + 1 ) = ( x 7 + x 6 + 1 ) m o d ( p + x 4 + x 3 + x + 1 ) 。 2 1 2 字运算 在a e s 算法中每个字由四个字节构成，因此，字运算也就是四字节运算。四字节向 量可以用g f ( 2 8 1 上的次数小于4 的多项式来表示。 ( 1 ) 加法运算：同字节的加法运算相类似，仅是简单的异或。 ( 2 ) 乘法运算： m 0 ) = x 4 + 1 ，乘法运算定义为两个多项式模m o ) 相乘。 ( 3 ) x 乘运算：x 乘对应向量内字节的一个左循环移位。 2 2a e s 算法 2 2 1a e s 算法结构 a e s 算法是一个迭代分组密码算法，分组长度和密钥长度可以独立的指定为1 2 8 ， 1 9 2 或2 5 6 比特。 数据块要经过多次数据转换操作，每一次转换操作产生一个中间结果，这个中间结 果叫做状态。状态可表示为二维字节数组即状态矩阵，它有四行，n b 列，且n b 等于数 据块长除以3 2 ，在标准a e s 里n b = 4 。密钥也可类似地表示为二维字节数组，它有四行， n k 列，且n k 等于密钥块长除以3 2 。算法转换的轮数n r 与n b 和n k 关系见表2 1 。 表2 1n b 和n k 下的n r 值 t a b l e2 1t h ev a l n eu n d e r n ba n dn k a e s 采用的是替代置换( s p ) 网络结构，每一轮由3 层组成： ( 1 ) 非线性层：进行s u b b y t e 变换( 即s 盒替换) ，起到混淆的作用； 东北大学硕士学位论文第二章数据加密算法原理 ( 2 ) 线性混合层：进行s h i t l r o w 行变换运算和m i x c o l u m n 列变换运算以确保多轮 之上的高度扩散； ( 3 ) 密钥加层：子密钥简单的异或到中间状态上。 a e s 算法加密( 解密) 算法流程如图2 1 所示： 1 次循环 环 图2 1a e s 算法加密与解密流程图 f i g 2 1 t h ea e sa r i t h m e t i cf l o wc h a r to f e n c r y p ta n dd e c r y p t 2 2 2 轮变换 轮变换由4 个不同的变换组成( s 盒变换，行变换，列变换和轮密钥加) ，c 表示为 r o u n d ( s t a t e ，r o u n d k e y ) s u b b y t e s ( s t a t e ) ； s h i f f r o w s ( s t a t e ) ； m i x c o l u m n s ( s t a t e ) ； a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) ； ) 最后一轮稍有不同为： f i n a l r o u n d ( s t a t e ，r o u n d k e ：y ) 9 东北大学硕士学位论文第二章数据加密算法原理 s u b b y t e s ( s t a t e ) ； s h i f t r o w s ( s t a t e ) ； a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) ； ) ( 1 ) s u b b y t e 变换 s u b b y t e 变换即s 盒运算，将每个字节通过s 盒做非线性运算。这个替换表( 或说 是s 盒) 是可逆的，并且它是由两个变换复合而成，这两个变换是： ( a ) 所有的子字节在有限域g f ( 2 8 ) 中求其乘法逆，且规定o o 的逆为0 0 ， 0 l 的为0 1 ； ( b ) 经( a ) 处理后的字节值进行如下定义的仿射转换； 五 恐 而 以 岛 +( 2 1 ) 这两个变换构造出s 盒。s 盒在状态的所有字节上运算的变换用s u b b y t e ( s t a t e ) 来记。 在这个变换中通过查s 盒表找到这个字节对应的多项式，然后对这个字节进行替换。关 于逆s 变换的计算是通过查逆s 盒表进行字节替换，即首先进行逆仿射变换运算，然后 利用前面的方法求得输入的字节乘法逆【1 9 1 。 ( 2 ) s h i f l r o w 变换 在行左平移变换中，状态的行以不同的位移向左循环平移，第0 行不动，第l 行移 动c 1 个字节，第2 行移动c 2 个字节，第3 行移动c 3 个字节。与n b 关系如表2 2 示。 表2 2 行移位表 m l b l e2 2t h et a b l eo f t h es h i f tn u m b e r ( 3 ) m i x c o l u m n 变换和i n v m i x c o l u m n 变换 在列混淆变换中，我们把状态的每一列看作是在系属域g f ( 2 8 ) 上的多项式，然后 一1 0 一 n叭m l 1 o o o 1 1 1 1 o o o 1 1 1 1 0 o 0 1 1 1 l l 0 0 1 l l 1 1 o o 1 1 1 1 o o 1 1 1 1 o o o m咒乃m儿m 东北大学硕士学位论文第二章数据加密算法原理 在模x 4 + 1 下与固定多项式c ( x ) = 0 3 p + o l x 2 + o l x + 0 2 相乘。这种运算可用矩阵乘 法表示，记6 ( x ) = c ( x ) o 口0 ) ，则： 6 0 岛 6 2 6 3 0 2 0 30 10 1 0 10 2 0 30 1 0 1 0 10 2 0 3 0 30 l 0 10 2 q 啦 吒 ( 2 2 ) 对所有的列进行这一运算就用m i x c o l u n m ( s t a t e ) 表示。由于c ( x ) 与x 4 + 1 互素， 故c ( 并) 可逆，且c - 1 ( 工) = d ) = 0 b x 3 + 0 d x 2 + 。0 9 x + 0 e 。列混淆变换的逆类似于 列混淆变换，只需将c ( x ) 换成d ( z ) 即可【刎。矩阵如下： q 吃 码 0 e0 bo d0 9 0 90 eo 丑0 d o d0 9o eo 召 o b0 d0 90 e 玩 6 l 6 2 6 3 ( 2 3 ) ( 4 ) 轮密钥加 在这一运算中，将状态矩阵和轮密钥进行简单的异或。轮密钥通过运用密钥扩展方 案，由种子密钥生成，生成的轮密钥长度等于数据分组长度n b 。这一变换用 a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) 表示。 2 2 3 密钥扩展方案 轮密钥的生成是由密钥扩展和轮密钥选择两部分构成，其基本原则是： ( 1 ) 轮密钥的总位数等于分组长乘( 1 + n r ) 。 ( 2 ) 种子密钥扩展为扩展密钥，种子密钥长度为4 * n k 字节： ( 3 ) 轮密钥由以下方法从扩展密钥获得：对第一轮密钥由前n b 个字构成；第二轮 由扩展密钥的第二组n b 字构成，以此类推。 密钥扩展 扩展密钥用数组w w o + ( n r + 1 ) 】表示，前n k 个字是种子密钥，其它的密钥通过 递归定义生成。由于密钥扩展函数取决于n k 值，分为n k 小于6 和大于6 两种。 小于6 ： k e y e x p a n s i o n ( b y t ek e y 4 + n k , w o r dw n 铲( n r + 1 ) 】) ( f o r ( i = o ；i 心m ；i + + ) 一1 1 东北大学硕士学位论文第二章数据加密算法原理 w i 】= ( k e y 4 + i ，k e y 4 + i + 1