（电子科学与技术专业论文）soc芯片中aes加密模块的设计与实现.pdf

a b s t r a c t a b s t r a c t w i t ht h ep o p u l a r i z a t i o no f 也ec o m p u t e ra n dt h ed e v e l o p m e n to fi n t e m e t i n f o r m a t i o n s e c u r i t yi sb e c o m i n gm o r ca n dm o r ei m p o r t a n tt h a nb e f o r e s i n c en o v e m b e r2 6 ，2 0 0 1 ，w h e n n a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g yc l a i m e dr i j n d a e la l g o r i t h ma sa d v a n c e e n c r y p t i o ns t a n d a r d ( a e s ) ，t h er e s e a r c ho ne n c r y p t i o nc h i pw i t ha e sa l g o r i t h mh a sb e c a m et h e f o c u si nt h ew o r l d s o c ( s y s t e mo nac h i p ) i sb e c o m i n ga ni n e v i t a b l et r e n di nc h i pd e s i g nb e c a u s e o fl o wd e s i g nc o s ta n dh i g hr e l i a b i l i t y t h i st h e s i si sd e d i c a t e dt ot h er e a l i z a t i o no fa e sm o d u l ei n s o c 弧ea e sm o d u l ei nt h i sp a p e ri sr e q u i r e dt os u p p o r tt h r e es i z e so fk e yl e n g t h , i n c l u d i n g 12 8 ，19 2 ，2 5 6 b i t ，t os u p p o r tf i v em o d e si n c l u d i n ge c b ，c b c ，c f b ，o f b ，c t r , a n dt oa c h i e v ea t h r o u g h p u to f1 g b p sw i t ht h ef r e q u e n c yo f1 0 0 m h z i nt h i sp a p e r , t h eb a s i ck n o w l e d g eo fa e s a l g o r i t h mi si n t r o d u c e d ，a n dt h eh a r d w a r er e a l i z a t i o na n dw o r k i n gf l o wo ft h ea e sm o d u l ei ns o c i sd i s c u s s e d n o n - p i p e l i n i n gs t r u c t u r ew h i c hs u p p o r t i n gb o t hf e e d b a c ka n dn o n - f e e d b a c km o d ei s u s e di nt h i sa e sm o d u l e a n dc o n f i g u r a b l ek e yl e n g t hi n p u ti sa l s ou s e d t h ef r a m e w o r ko fe a c h s u b - m o d u l ed e s i g ni sd e s c r i b e d , a n ds e v e r a lk e ym o d u l e ss u c ha sk e ye x p a n s i o n ，e n c r y p t i o na n d d e c r y p t i o na r ea n a l y z e di nd e t a i l a tl a s t ，t h ea e s m o d u l ei si m p l e m e n t e dw i t hv c r i l o gh d l a f t e rs i m u l a t i o na n ds y n t h e s i s ，t h ea e sm o d u l ei si m p l e m e n t e do i lf p g af o rv e r i f i c a t i o n 1 1 1 et e s tr e s u l ts h o w st h a tt h ea e sm o d u l em e e t st h ed e s i g nt a r g e t a l s o t h ea e sm o d u l ei nt h i s p a p e ri sc o m p a r e d 、撕也o t h e rs i m i l a rd e s i g n t og e tac o n c l u s i o no fi t s s u p e r i o ro ri n a d e q u a t e k e y w o r d s ：s o c ( s y s t e mo i l ac h i p ) ，v e r i l o gh d l ，t h r o u g h p u t , n o b - p i p e l i n i n g ，r o u n d f u l n o t i o n i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生 院办理。 第一章绪论 第一章绪论 本章主要介绍课题的背景，包括信息安全、a e s 标准的产生以及s o c 的发展。在本章末， 阐述了本课题的任务及主要工作，概述了论文的结构框架。 1 1 课题背景 1 1 1 信息技术和信息安全 信息和信息技术正在改变传统的生产方式、经营方式和生活方式，信息产业已经成为国 民经济新的增长点，是当今时代发展的核心和灵魂。随着计算机与通信技术的迅猛发展，由 于计算机网络所具有的开放性和共享性，大量敏感信息通过公用通信设施和计算机网络进行 交换，信息的安全、高效的传输成为当前的迫切需要。信息的传递和获取倍受重视，信息的 实效性决定着信息的价值，更快速更准确的传递信息成为各国科研人员的不断追求的目标。 我国信息网络安全起步较晚，信息化、网络化建设在技术与设备上对别国有很大的依赖性， 安全防护能力尚处于初级阶段，与发达国家有较大的差距，信息安全问题格外突出。加密是 保障信息安全最核心的技术措施和理论基础，它用小的代价为信息提供大的安全保护，是保 证信息机密的唯一方法。国家关键基础设施中无法直接引进或采用别国的关键技术，只能自 主开发，而我国的密码技术的应用水平与国外还有一定的差距，特别是加入w t o 后，国外 的密码技术对我们的冲击力有增无减，因此，只有自主开发我们的加密芯片，才能切实保障 自己的信息安全。信息加密研究的主要内容是密码学川。 1 1 2a e s 的产生背景和当前研究动态 1 9 4 9 年c e s h a n n o n 发表了保密系统的通信理论1 2 j ，开创了现在密码学的研究。1 9 7 6 年w d i f f e r 与m e h e l l m a n 发表的密码学的新方向口】和1 9 7 7 年美国公布实施的数据加密 保准( d e s ) 【4 】- 【5 】标志着现代密码学的诞生。此后使用的密码体制的研究基本沿两个方向进 行，以r s a 【6 j 为代表的公开密钥体制和d e s ( 以及由d e s 衍生的三重d e s ) 为代表的秘密密 钥体制。随着密码分析水平、芯片处理能力和计算技术的不断进步，d e s 的安全强度已经难 以适应新的安全需要，其实现速度、代码大小和跨平台性均难以继续满足应用需求。1 9 9 7 年1 月美国国家标准和技术研究所( n i s t ) 正式宣布了n i s t 计划，该计划公开征集和评估新 的数据加密标准，其目标是确定一种保护敏感( 无密级的) 信息的、公开的、免费的并且全球 通用的算法作为高级加密标准( a 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 ) ，作为保护2 l 世纪敏感 政府信息的新型加密标准，以弥： i d e s 退出后数据加密标准留下的空缺【5 】，并于同年9 月1 2 日正式发出征集算法的公告。a e s 的基本要求是：算法必须是对称分组密码，必须至少支持 1 2 8b i t 分组加密和1 2 8 1 9 2 2 5 6b i t 密钥，密钥要比三重d e s 快，而且至少与三重d e s 一样安全。 n i s t 计划的评判规则大体分为安全性、代价、算法实现特性三大部分，其中安全性是评判 算法最重要的因素，包括算法的抗分析能力、稳固的数字基础、算法输出的随机性以及与其 他算法的对比特性：代价是指授权合法使用的代价，如在多种平台上计算的效率速度和占用 存储器的数量；而算法实现特性则是指灵活性软硬件兼容性和简单性。 2 0 0 1 年1 1 月2 6 日，n i s t 正式宣布r i j n d a e l 算法为a e s ，其编号为f i p sp u b s1 9 7 l j 。新标 准a e s 能够提供抗线性密码分析和差分密码分析能力，将会取代d e s 和三重d e s ，在商业领 域被广泛采用。 东南大学硕士学位论文 1 1 3 s o c 和加密芯片的发展 2 0 世纪9 0 年代末，随着深亚微米集成电路工艺技术的成熟，人们已经能够将包含模拟 电路、射频电路、微处理器、数字信号处理、存储器和微机械等模块的完整系统集成到一个 芯片上，集成电路迈入了s o c ( s y s t e m0 1 1ac h i p ) 时代【8 】。s o c 即系统级芯片，也称s l i ( s y s t e ml e v e li n t e g r a t i o n ) 1 9 1 ，指的是在单个芯片上集成一个完整的系统，对所有或部分必 要的电子电路进行包分组的技术。s o c 是与其它技术并行发展的，如绝缘硅( s o d ，它可 以提供增强的时钟频率，从而降低微芯片的功耗。由于s o c 高效的集成性能，片上系统是 替代集成电路的主要解决方案。s o c 已经成为当前微电子芯片发展的必然趋势。一般说来， s o c 有如下特征 1 0 l ： 实现复杂系统功能的v l s i 采用超深亚微米工艺技术 使用一个以上嵌入式c p u 数字信号处理器( d s p ) 外部可以对芯片进行编程 s o c 技术通常应用于小型的、日益复杂的客户电子设备。例如，声音检测设备的片上系 统是在单个芯片上为所有用户提供包括音频接收端、模数转换器( a d c ) 、微处理器、必 要的存储器以及输入输出逻辑控制等设备。此外系统芯片还应用于单芯片无线产品，诸如蓝 牙设备，支持单芯片w l a n 和蜂窝电话解决方案。由于s o c 可以有效地降低电子信息系 统产品的开发成本，缩短开发周期，提高产品的竞争力，是未来工业界将采用的最主要的产 品开发方式。 国外许多公司都很早就开始开发加密芯片，如1 9 8 1 年a m d 公司就推出了加密芯片 a m 9 5 18 1 1 2 1 。a e s 作为当前最流行加密标准之一，在许多场合如智能卡、i p s e e 等领域己被 广泛使用【1 3 】。旧，应用a e s 标准的加密专用芯片是实现信息安全与保密的基础核心产品，已 成为目前的研究热点【l8 】- 【2 2 j ，很多知名公司推出了i p ( i n t e l l e c t u a lp r o p e r t y ) 核，如：h e l i o n 技术有限公司( 如图1 1 所示) 和o c e a n l o g i c p t y 技术有限公司等。在国内，尽管越来越多 的公司和研究机构已经把目光投入到a e s 的硬件实现当中，但和国际先进水平还有不小的 差距 2 3 】【2 5 1 。本文即是设计一个可嵌于s o c 芯片中的、以a e s 标准实现的加密模块。 图1 1h e l i o n 公司的a e s 商用i p 核 2 第章绪论 1 2 论文的内容和结构框架 绪论部分介绍了课题的研究背景和意义，概述了本论文的主要内容和工作安排。第二 章介绍了密码学的背景知识和a e s 标准的算法原理。第三章介绍了s o c 芯片上a e s 加密模 块的系统架构，并具体分析了a e s 模块硬件实现的几种结构，根据本次设计的要求，确定 了非流水线的工作方式以同时支持反馈和非反馈下不同的工作模式。第四章是测试验证部 分，利用软硬件协同验证的平台，先进行仿真验证，然后进行片上测试，两方面验证a e s 模块的正确性。结束语部分总结了论文各项的研究工作，并提出进一步的展望。 3 东南大学硕士学位论文 第二章密码学和a e s 算法原理 本章主要介绍密码学的基础知识，重点分析了分组密码的工作模式，接着介绍了a e s 的相关背景知识，包括数学基础和算法原理。 2 1 密码学 2 1 1 密码学基础知识 密码学技术是信息安全技术的核心，包括密码编码技术和密码分析技术。密码学广泛应 用于通信安全保密和存储加密等领域，它能够很好的解决数据机密性的保护和身份证认证等 方面的难题。 一个密码系统通常简称为密码体制有五部分构成【2 6 】： 1 明文空间m ：它是全体明文的集合。 2 密文空间c ：它是全体密文的集合。 3 密钥空间k ：它是全体密钥的集合。其中每一个密钥k 均由加密密钥k 和解密密钥 组成，即k - 磁+ 。 4 加密算法e ：它是一族由m 到c 的加密变换。对于每一个具体的k ，n e 便确定出一 个具体的加密函数f 。 5 解密算法d ：它是一族由c 到m 的解密变换，对于每一个确定的，贝j d 便确定一个 具体的函数f 1 ，使得m = f 1 ( c ，) ，对于每一个确定的密钥k = k + i h ，密文c = e ( m ， i g ) ，有明文m = d ( c ，i g ) = d ( e ( m ，k ) ，) 。 如果一个密码体制的= 磁，或由其中一个容易推出另一个，则称为单钥密码体制或对 称密码体制，否则，如果在计算机上磁不能由k 推出，这样将k 公开也不会损害的安 全，于是便可以将k 公开，这种密码体制称为公钥密码体制或非对称密码体制，反之，则称 为私钥密码体制或对称密码体制：前者是基于双密钥的，后者是基于单密钥的。私钥和公钥 作为两种不同的加密思想，解决不同的问题。对称加密适合加密大量数据，它具有较快的速 度，并且对选择密文攻击不敏感；非对称加密通常比对称加密速度慢很多，但它有其特殊的 应用场合，例如进行密钥的分配和管理，数字签名等等【2 7 】。 目前将密码理论与技术分为两大类1 2 8 】，一是基于非数学的密码理论与技术，包括信息 隐藏、量子密码、基于生物特征的识别理论和技术等等；其二是基于数学的密码理论和技术， 包括分组密码、序列码、公钥密码、认证码、数字签名、h a s h 函数、身份识别、密钥管理、 p k i 技术等等。根据加密方式的不同，密码可以分为分组密码和流密码。流密码就是对数据 流一次加密一个比特或一个字节。分组密码则是先把要加密的明文划分成相同比特的数据 块，称为明文分组。一个明文分组被当作一个整体来产生一个等长的密文分组，分组的大小 通常是6 4 位或1 2 8 位。分组密码可以通过工作方式取得和流密码同样的效果。人们在分析分 组密码方面下的功夫要比在流密码方面多得多，般而言，分组密码比流密码的应用更加广 泛。绝大部分的基于网络的常规加密应用都使用分组密码，当前使用的几乎所有的对称加密 算法都是分组密码。 根据一次加密数据的长度的不同，对称加密算法又可以分为两类。一类是只对明文的单 个比特运算，其使用短的密钥比特串生成长的密钥比特串，然后再与明文按位进行模2 相加 产生密文，它的安全性基于密钥的随机性，这种加密算法称为序列算法或是序列码；另一类 是对明文的一组比特进行运算，这些比特组称为分组，相应的算法称为分组加密算法或分组 4 第二章密码学和a e s 算法原理 密码。分组密码通常由加、解密算法和密钥扩展两部分组成。密钥扩展算法用于生成m 个 子密钥。加密算法由一个密码学上的函数f 对数据进行一系列变换之后，每次与一个子密钥 迭代，对一个数据分组的加密总共需完成r 次迭代。分组加密多应用于网络通信中。 2 1 2 分组密码的工作模式 以往的加密算法中，d e s 是应用最为广泛的，d e s 、三重d e s 和许多商业分组密码都 采用“位的明文分组长度，所以以往的工作模式讨论均是基于6 4 位的分组讨论。本次课题 是采用a e s 加密算法，采用的是1 2 8 位的分组，与6 4 位分组的工作模式讨论一样，所以我 们在讨论本次加密算法的工作模式时，定明文分组长度为1 2 8 位。 为了将d e s 应用于实际，人们定义了五种工作模式。这五种模式可以用于包括三重d e s 和高级加密标准( a e s ) 在内的任何分组密码。表2 1 对这些模式作了一个总纠2 9 1 。 表2 1a e s 的工作模式 模式描述典型应用 电码本 用相同的密钥分别对明文组加密单个数据的安全传输 密码分组链加密算法的输入是上一个密文组和下一个普通目的的面向分组的传输 接明文组的异或 认证 一次处理s 位。上一个分组密文作为产生一个伪随机 普通目的的面向分组的传输 密码反馈数列的加密算法的输入，该输出与明文异或，作为下 一个分组的输出 认证 与c f b 基本相同，只是加密算法的输入是上一次 输出反馈噪声通道上的数据流的传输 a e s 的输出 每个明文分组是加密的计数器的异或。对每个以后普通目的的面向分组的传输 计数器 的分组，计数器是累加的用于高速需求 1 电码本模式 最简单的模式是电码本模式( e c b ) ，如图2 1 所示，它一次处理1 2 8 位明文，每次使 用相同的密钥加密。使用电码本这个词是因为对于给定的密钥，任何1 2 8 位明文组只有唯一 的密文与之对应，所以，可以想象存在一个很厚的密码本，根据任意1 2 8 位明文都可以得到 相应的密文。 明文若长于1 2 8 位，则可以简单的将其分为1 2 8 位分组，必要时可对最后一个分组进行 填充。解密也是一次执行个分组，且使用相同的密钥。明文由一串1 2 8 位的分组组成，记 做p l ，p 2 ，p 3 ，p 。，相应的密文分组依次是c l ，c 2 ，c 3 ，c n 。 e c b 模式特别适合于数据较少的情况，比如加密密钥。因此，若想安全的传输一个a e s 密钥，选择这种模式是合适的。对于很长的消息，e c b 模式可能不安全。 时间= 1 时间= 2时间= n k k k k 图2 - 1e c b 模式 5 k k ( a ) 加密 ( b ) 解密 东南大学硕士学位论文 2 密码分组链接模式 为了克服e c b 的这些弱点，我们需要将重复的明文组加密成不同的密文组。密码分组 链接( c b c ) 模式能满足这个要求，见图2 2 。这种模式下加密算法的输入是当前的明文组 加上一个密文组的异或，而使用的密钥是相同的。这就相当于将所有的明文组链接起来了。 加密算法的每次输入与本明文组没有固定的关系。因此，若有重复的1 2 8 位明文组，加密以 后就看不出来了。 解密时，每个密码组分别进行解密，再与上一块密文异或就可以恢复出明文。下面对这 个过程的正确性给出证明。 c j - - e k q _ , op j 】 ( 2 1 ) 则d k c j - - d k e k ( q lo p p 】 ( 2 2 ) d k t c j - - c 1op j ( 2 3 ) c j 1o d k c j 】= c j 1o c j 1 审p j = p j ( 2 4 ) 第一块明文可以和一个初始矢量( i v ) 异或后再加密。解密时将第一块密文解密的结果 与i v 异或而恢复出第一块明文。 时间= 1 时间= 2 时间= n 图2 - 2c b c 模式 c n 1o 士p n ( a ) 加密 ( b ) 解密 3 密码反馈模式 a e s 本质上是一个1 2 8 位的分组密码，但是利用密码反馈模式( c f b ) 或输出反馈模式 ( o f b ) ，亦可作为流密码使用。流密码不需要明文长度是分组长度的整数倍，且可以实时 操作。所以，待发送的字符流中任何一个字符都可以用面向字符的流密码加密后立即发送。 图2 3 描述了c f b 模式。假设传输单元是s 位，s 通常是8 。如果用c b c 模式，明文的 各个单元要链接起来，所以任意个明文单元的密文都是前面所有明文的函数。在这种情况下， 明文被分成s 位的片断而不是1 2 8 位的单元。 首先来考虑加密。加密函数的输出是1 2 8 位的移位寄存器，它的值是初始矢量i v 。加 密函数输出最左边的s 位与明文p 1 异或得到第一个密文单元c 1 ，然后将c l 发送出去；接着， 移位寄存器左移s 位，c l 填入移位寄存器的最右边s 位。就这样，直到所有明文单元被加密 完成。 解密使用相同的办法，只是有一点不同：将收到的密文单元与加密函数的输出异或得到 明文单元。注意，这里使用的是加密函数而非解密函数，这一点很容易解释。设s 。( x ) 表示 x 的最左边s 位，则有： c l = p ios s ( e k ( i v ) ( 2 5 ) 从而有： 6 第二章密码学和a e s 算法原理 p i - - - c ios 。( e k ( i ) 对后续单元亦同理可得。 移位寄存器 移s 位i s 位12 8 一s 位i s 位 叫加密j_ 志1 0 选择s 位l 选择s 位l 丢弃1 2 8 一s 位 丢弃1 2 8 一s 位 束 束。 加密 选择s 位i 丢弃1 2 8 一s 位 p c t v 移位寄存器 1 2 8 s 位i s 位 鉴- 厂巧斋 选择s 位l 丢弃1 2 8 一s 位 p c 图2 - 3c f b 模式 k 移位寄存器 12 8 s 位i s 位 加密 选择s 4 , - k i 丢弃1 2 8 一s 位 p 2 移位寄存器 12 8 s 位l s 位 鉴- 厂五蒿 选择s 位l 丢弁1 2 8 一s 位 q 严c 2 p 2 图2 - 4o f b 模式 ( 2 6 ) a ) 加密 k ( b ) 解密 ( a ) 加密 ( b ) 解密 4 输出反馈模式 如图2 4 所示，输出反馈模式( o f b ) 的结构和c f b 很相似。正如我们所见的那样， 7 东南大学硕士学位论文 它用加密函数的输出填充o f b 中的移位寄存器，而在c f b 中，则用密文单元来填充移位寄 存器。 o f b 的一个优点是传输过程中在某位上发生的错误不会影响其他位的数据。比如，c l 中有l 位发生了错误，只会影响到p l 的恢复，后续的明文单元不受影响。而在c f b 中c l 还作为了移位寄存器的输入，所以影响了后续的所有消息。 5 计数器模式 尽管随着计数器模式( c t r ) 在a t m 网络安全与i p s e c 中的应用使得人们最近才对它 产生了浓厚的兴趣，但这种模式在很早以前就已经提出来了。 图2 5 描述了c t r 模式。计数器使用与明文分组相同的长度，唯一要求是加密不同的 明文组计数器对应的值必须是不同的。典型地，计数器首先被初始化为某一值，然后随着消 息块的增加计数器的值加1 。计数器加1 后与明文组异或得到密文组。解密使用具有相同值 得计数器序列，用加密后的计数器的值与密文组异或来恢复明文组。 图2 - 5c t r 模式 2 2a e s 算法的背景知识 ( a ) 加密 ( b 解密 2 2 1 有限域g f ( 2 5 ) 上的运算 有限域是具有有限个元素的划3 1 1 ，集合中元素的个数称为域的阶，m 阶域存在当且仅当 m 是某素数的幂，即存在某个整数n 和素数p 使得m - _ p ”，称为有限域的特征。在a e s 的描 述中均使用以2 为特征的有限域。对于每个素数幂恰好存在一个有限域，我们用g f ( p ”) 表 示。 素数p 阶域g f ( p ) ，其元素可以用整数1 ，2 ，p l 来表示。该域的两种运算则是“模 口的整数加法”和“模p 的整数乘法”。 一个有限域中的元素可以用多种不同的方式表示。对于任意素数的方幕p ，只有唯一一 个有限域g f ( p ) ，因此，g f ( 2 8 ) 的所有表示是同构的。尽管有这一等价性，但不同的表 示方法对g f ( 2 8 ) 上的运算复杂度是有影响的。此处采用传统的多项式表示法。 由b t b 6 b s b 4 b 3 b 2 b l b o 构成的一个字节，b 看成系数在 o ，i ) 中的多项式： 8 第二章密码学和a e s 算法原理 b 7 x 7 + b 6 x 6 + 6 5 工5 + 钆x 4 + 如工3 + b 2 x 2 + b i x + b o 例如；十六进制数“5 7 ”对应的二进制数为0 1 0 1 0 111 ；看作一个字节，对应的多项式为： x 6 + 工4 + x 2 + x + 1 。 1 有限域上的加法 在a e s 算法中，字节被看作诗有限域上的元素，可以进行加减乘除，但这些运算不同于 一般的数学运算。 有限域中的加法运算相当于执行异或操作，即模2 加法，表示为0 。两个字节的相加可 以表示成多项式形式、二进制形式和十六进制形式。多项式之和等于先对具有相同x 次幂的 系数求和，然后各项再相加。而各系数求和是在域f 中进行的，如式2 7 ： c ( x ) = 口( x ) + 6 ( 工) 亨c ( i ) = a ( i ) + 6 ( f ) ，0 f 刀( 2 7 ) 加法的零元素0 是一个所有系数都等于0 的多项式，一个多项式的逆元素可以通过将其每 一个系数替换为域f 上的逆元素而得到。c ( x ) 的系数最多为a ( x ) 和b ( x ) 的次数的最大 值，因此该加法运算是封闭的。 以下为一个加法的例子：g f ( 2 8 ) 域中，1 6 迸制数5 7 和8 3 所表示的多项式的和可以用 16 进制数d 4 来表示，如式2 8 所示： ( x 6 + x 4 + x 2 + 工+ 1 ) o ( 工7 + x + 1 ) = x 7 + 工6 + + x 2 ( 2 8 ) 采用2 进制符号所以有0 1 0 1 0 1 1 lo1 0 0 0 0 0 1 l = 1 1 0 1 0 1 0 0 ，显然，这个加法可以用逐位异或来 实现。 2 有限域上的乘法 要计算g f ( 2 8 ) 域的乘法，必须先确立一个g f ( 2 ) 上的8 次不可约多项式，g f ( 2 8 ) 域上的两个元素的乘积就是这两个多项式模此8 次不可约多项式的积。对于r i j n d a e l 算法，这 个8 次不可约多项式确定为： m ( x ) = x 8 + x 4 + x 3 + z + l( 2 9 ) 这个8 次不可约多项式的十六进制表示为l i b ，二进制表示为9 比特1 0 0 0 1 1 0 1 1 。 多项式a ( x ) 和b ( x ) 的乘积定义为模多项式1 1 1 ( x ) 的多项式的代数乘积，如式2 1 0 ： c ( x ) = a ( x ) e t , ( x ) 甘c ( x ) = ( a ( x ) x b ( x ) ) m o d m ( x ) ( 2 1 0 ) 由前所述，一个字节可以看作一个系数在域g f ( 2 ) 上的多项式： b v x 7 + b 6 x 6 + b s x 5 + b a x 4 + b 3 x 3 + b 2 x 2 + b i x + b o 所有可能的字节的集合对应于次数小于8 的全体多项式。字节的加法可以定义为相应的 多项式的加法。为了定义字节乘法，我们称z n ( x ) 为约化多项式。 由于约化多项式本身是既约多项式，这样就构造了域g f ( 2 8 ) 的一种表示。因此，可 以作如下约定：在e d j n d a e l 的描述中，将字节看作域g f ( 2 8 ) 中的元素运算。下例根据对域 g f ( 2 8 ) 的表示方法，十六进制数5 7 和8 3 所表示的元素之间的乘积等于十六进制数c 1 所表示 的元素，如式2 1 l 、2 1 2 所示： 9 东南大学硕士学位论文 ( 石6 + x 4 + x 2 + x + 1 ) ( x 7 + x + 1 ) = ( z 1 3 + 工+ x 9 + z 8 + 工7 ) 0 ( 工7 + x 5 + 工3 + x 2 + 石) 0 ( 工6 + x 4 + x 2 + x + 1 ) 2x 1 3 + z 1 1 + x 9 + z 8 + x 6 + x 5 + z 4 + x 3 + 工+ 1 ( 2 1 1 ) ( x 1 3 + z 1 1 + 石9 + 工8 + 工6 + 工5 + x 4 + z 3 + 工+ 1 ) m o d ( 工8 + 工4 + x 3 + z + 1 ) = 工7 + x 6 + 1 ( 2 1 2 ) 与加法不同的是，没有简单的指令可以直接实现此功能。 最后，我们讨论x 乘运算，假设b ( x ) 是g f ( 2 8 ) 上的多项式，我们需要计算x b ( 】or o o d r e ( x ) ，我们可以寻找它的快速实现方法，因为： x b ( x ) = b 7 x 8 + b e x 7 + b s x 6 + 钆石5 + b 3 x 4 + b z x 3 + 岛x 2 + b o x ( 2 1 3 ) 如果玩= 0 ，那么上面的多项式的次数小于8 ，就是结果。如果良= l ，那么将上述多项 式对m ( x ) 求余，就是将上述多项式的十六进制表示形式对 1 b ) 进行异或运算，也就是说x b ( x ) r o o dm ( x ) 就是将b ( x ) 先进行一次左移位运算，再根据条件( b 7 - - 17 ) 决定是否对 1 b ) 进行异 或运算，把这个过程表示成一个函数x t i m e 0 。那么g f ( 2 8 ) 域上面的乘法就可以表示成一 系列上述过程的集合，例如： 5 7 ) 1 3 = f e ) 因为： 5 7 ) 0 2 = x t i m e ( 5 7 ) = a e ) 5 7 ) 0 4 ) = x t i m e ( a e ) = 4 7 ) 5 7 0 8 ) = x t i m e ( 4 7 ) = 8 e ) 5 7 。 1 0 ) = x t i m e ( 8 e ) = 0 7 ) 所以： 5 7 1 3 ) = 5 7 ( 0 1 ) o 0 2 ) o 1 0 ) ) = 5 7 o a e ) 国 0 7 ) = f e ) 。 2 2 2a e s 算法的输入输出 a e s 与r i j n d a e l 之间的唯一差别在于各自所支持的分组长度和密钥长度不同。r i j n d a e l 是有可变分组长度和可变密钥长度的分组密码算法，其分组长度只是规定为3 2 比特的任意 倍数，最小值为1 2 8 比特，最大值为2 5 6 比特。a e s 标准取的是r i j n d a e l 算法中一个范畴， a e s 将分组长度固定为1 2 8 比特，而且仅支持1 2 8 、1 9 2 、2 5 6 比特长度的密钥。 a e s 密码算法的输入输出是固定的1 2 8 比特流，密钥的长度可以选择为1 2 8 比特1 9 2 比特 和2 5 6 比特，a e s 算法处理数据的基本单元是字节，a e s 算法的输入输出可以看作是一维的 字节数组。若用n 表示数据字节数，即： b l o c kl e n g t h = 1 2 8 b i t s ，0 n 1 6 ： 当k e yl e n g m = 1 2 8 b i t s ，0 疗 1 6 ： 当k e yl e n g t h = 1 9 2 b i t s ，0 万 2 4 ； 当k e yl e n g t h = 2 5 6 b i t s ，0 n 3 2 ； 1 0 第二章密码学和a e s 算法原理 b l o c k1 e n 啦可简单比表示为：a o a a 2 a 1 5 ， 具体为比特串即：i n p u t o i n p u h i n p u h i n p u t l 2 7 ，即： a o i n p u t o i n p u t z i n p u t 2 i n p u t 7 ； a l - - i n p u t s i n p u t g i n p u h o i n p u t l s ) ； a l s = i n p u t l 2 0 i n p u t l 2 i n p u t l 2 2 i n p u h 2 7 即：2 l n = i n p u t s n 卸u t 8 n + l 卸u t b 口+ 2 i n p u t 8 n + 7 ) 。 同理可得出k e yl e n g t h 的表示。 如图2 6 所示为输入比特流和字节的对应转换关系。 i n p u tb i t o12 34 5 67891 0 1 11 2 1 31 41 5 1 61 71 8 1 92 02 l 2 22 3 s e q u e n c e b y t en t m a b e r 0 l 2 b i tn u m b e r si n 765432lo76543210 7 65 4 32io b y t e 图2 6 输入比特流和字节的转换关系 对加密来说，其输入是一个明文分组和一个密钥，输出是一个密文分组；对解密来说， 输入是一个密文分组和一个密钥，而输出的则是一个明文分组。a e s 算法中需要迭代运算， 每一次迭代称为轮变换，每一次轮变换又有四个步骤。设加密或解密一个数据分组共需要的 轮次为n r ，则当密钥的长度分别为1 2 8 、1 9 2 和2 5 6 时，n ，分别为1 0 、1 2 和1 4 。a e s 的轮变换 及其每一步均作用在中间结果上，中间结果可以形象地表示为一个矩形的二维字节数组。我 们将该中间结果称为状态数组：t h es t a t e 。对于每个状态数组行数固定为4 行，其列数记为 n b ，它等于分组长度除以3 2 ，在a e s 中n b = 4 。s o - i 由横坐标r ，纵坐标c 来界定，给定了r 、c 的值，即可对应到二维数组s t a t e 中的某一个元素( 即8 位比特的字节) ，这个字节可表示为 s r ，c 】，其中0 ， 4 ，0 c 4 。 在加密或解密开始时，输入的数据先被复制到状态数组s 中。在迭代过程中，每轮变换 的结果都保存在中间数组( 也即状态数组) 中，在加密或解密完成时，状态数组中的每个字 节就被复制到输出数组中去。a e s 算法中输入输出及状态数组的数据组织形式如图2 7 所示。 i n p u tb y t e s s t a t ea r r a yo u t p u tb y t e s i n oi n i n 8i n l 2 i n l i n 5i n 8i n l 3 l n 2 i n e1 1 1 1 0 l n l 4 i n 31 1 1 71 1 1 1 1 1 1 1 1 5 s o os o ， s 0 2s 0 3 s 1 0s l ls 1 2s 1 3 s 翘s 2 1s z 2s $ 3 0s s ls s 2s 3 3 o u t o 0 u t 4 o u ho u t l 2 o u t l o u t so u t o o u h 3 o u t 2o u t 6o u t o o l l h 4 o u t 3o u t 7 o u t l lo u h 5 图2 7a e s 的状态数组 其中，s i r ，c = i n r + 4 c ，0 厂 4 ，0 c 4 ：o u t r + 4 c = s r ，c 】，0 ， 4 ，0 c 4 。 与数据分组同理，密钥分组也被复制到一个两维数组中，该数组有4 行，列数记为n k ， 东南大学碰士学位论文 它等于密钥的长度除以3 2 ，所以当密钥的长度分别为1 2 8 、1 9 2 和2 5 6 时，n k 分别为4 、6 和8 ， 密钥数据的组织形式如图二8 所示( 鳜色的深浅以示密钥长度不同的区别) - 3 3a e s 算法流程 ：竺豳 图2 8 密钥字节数组 2 3 1a e $ 算法的加密流程 无论是加密运算还是解密运算晕基本的都是对状卷数组中敷据的重复运算选代运 算，也即轮变换。 由上节所述，对于a e s 算法，n b 、n ，的差系可用表2 - 2 表示a e $ 加密的基本 流程如图2 - 9 所示。在加密运算中，每一轮选代由4 种变换即4 个步骤组成包括： a d d r o l m k e y ( 轮密钥加) 、s u b b y 慨( 字节替换) 、s h i 腿。婀( 行变换) 和m i x c o l m ：o n s ( 列 混台) 。首先，加密开始时。输入数据被复制到状志数维中，状态数组中的数据与初始密钥 相加记作a d d p , o u n i 铆。其次，a e $ 根据密钥长度执行n r l 次的迭代运算。每一次的迭 代变换均以状态教组和一个轮密钥相加的结果作为输 然后依次进行s u b b y k s 、s h i 蛐, o w s 和m i x c o l u m m 的变授。最后一轮的选代运算与前面n ，i 轮不同最后一轮的迭代运算，没 有m i x c o l u m 皿的运算。 表2 - 2 数据分组、密钥、迭代轮数的关系 加密流程由圈2 - 9 所示 第二章密码学和a e s 算法原理 图2 - 9a e s 加密流程图 1 s u b b y t e 卜- 孚节替换 s u b b y t e s 是一种非线性置换。假设a ( x ) 为状态数组中的一个字节，采用上一章节给出 的多项式表示将o f ( 2 8 ) 中的元素用多项式的形式表示，且系数是g f ( 2 ) 中的元素。在约化多 项式m ( x ) = x 8 + x 4 + ，+ x + 1 模乘运算下，定义y a ( x ) 的乘法逆元，元素 o o ) 的乘法逆元为 其本身。在s u b b y t e s 变换中，先求出a ( x ) 的乘法逆元b ( x ) ，然后进行仿射变换，仿射变换也 可描述为：先进行多项式乘法，然后再与一个常量异或。这种变换可以用式2 1 4 、2 1 5 表示： b ( x ) = o - 1 ( x )( 2 1 4 ) b i b i o b ( i + 4 ) 仃i o d bo f + 5 ) 啪d 8e b , f + 6 ) i n o d 8o 纹f + 7 ) i i l o d 8o c ( 耽0 i 8 ( 2 1 5 ) 以矩阵形式完全展开即为： + ( 2 1 6 ) b i 是a ( x ) 乘法逆元素的第i 个比特。为了表示方便，域g f ( 2 8 ) 上的一个元素可以用两个 1 6 进制字符表示，如 5 3 ) 经置换后变为 e d 。在a e s 算法中，由于执行乘法求逆运算和仿射 变换需要大量的有限域运算，所以，在实际的a e s 硬件实现中，通常把运算的结果做成一个 表，称为s b o x ，用查表的方式实现s u b b y t e s 变换如图2 - 1 0 所示。 1 3 钆既坟6，钆玩饥坊 1 1 1 1 o o 0 l l 1 l o 0 o l 1 1 1 o 0 o 1 1 1 1 o 0 0 1 1 l 1 o o o 1 1 1 1 l 0 0 1 1 1 1 1 o o 1 1 1 1 1 o o 1 1 1 1 1 o o o 良阢良n加良良西 东南大学硕士学位论文