（电路与系统专业论文）aes和md5混合加密算法的硬件实现.pdf

i i i ii iii i i iii ii i ii ii il y 17 6 18 3 4 h a r d w a r e i m p l e m e n t i o no f a e s a n dm d 5 h y b r i d e n c r y p t i o n a l g o r i t h m at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y l u of e n g s u p e r v i s e db y p r o f z h a n gm e n g s c h o o lo fe l e c t r o n i cs c i e n c ea n de n g i n e e r i n g s o u t h e a s tu n i v e r s i t y m a r c h2 0 l o 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南人学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 牛眦珥删 东南大学学位论文使用授权声明 东南人学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大 学研究生院办理。 躲普新躲蜥 摘要 摘要 随着手机理财与支付等手机新业务不断扩张，新一代智能手机大多采用具有硬什加密功能的 s o c 芯片作为主处理芯片；新一代硬盘和移动硬盘，很多都采用硬加密技术对数据信息进行加密； 有些无线传感网络的基带处理芯片内也集成了硬件加密模块。硬件加密技术已广泛应用丁日常生活 中，并具有十分重要的作用。 论文首先在技术调研基础上确定了基- j = a e s 和m d 5 算法加密加速器的基本结构。然后，采用 非流水线结构完成支持e c b 、c b c 、c f b 、o f b 、c t r 五种工作模式的a e s 模块r t l 级设计；采 用非流水线结构完成m d 5 模块的r t l 级设计；采用b b s 算法完成硬件随机数生成器的r t l 级设计， b b s 算法的“平方”和“模”运算使用等效算法由加法和移位实现。最后，为了将加密加速器集成 到自主研发的s o c 芯片中，还完成了a h b 总线主设备接口和a h b 总线从设备接口的r t l 级设计。 在完成r t l 级设计后，采用m o d e l s i m 对加密加速器进行模块级仿真，采用v c s 对其进行系统 级仿真；采用s y n p l i f y 对设计进行综合；采用q u a r t u s l i 对设计进行布局布线和时序分析；使用 q u a r t u s l l 通过u s b 下载线将镜像文件烧录到f p g a 开发板上，配合a r m 公司的r v d s 调试工具完 成f p g a 验证。实验结果表明a e s 模块数据吞吐率达到1 9 5 g b i t s ，m d 5 模块数据吞吐率达到 1 0 8 g b i 佻，已满足s o c 芯片商业应用需求。 关键词：加密加速器，a e s 加密算法，m d 5 加密算法，b b s 算法，系统芯片 a b s t r a c t a b s t r a c t w i t ht h ee x p a n s i o no fm o b i l ep h o n es e r v i c e ss u c ha sm o b i l ep h o n eb a n k i n g ，m o b i l ep h o n ep a y m e n t e t c m o s to ft h en e wg e n e r a t e ds m a r tp h o n e sa d o p tt h es o cc h i pw h i c hi n t e r g r a t e st h eh a r d w a r ee n c r y p t i o n a c c e l e r a t o ra st h em a i np r o c e s s o r t h eh a r d w a r e e n c r y p t e dm o d u l e sa r ea l s oa p p l i e do nh a r dd i s ka n d w i r e l e s ss e n s o rn e t w o r k s s ot h eh a r d w a r ee n c r y p t i o nt e c h n o l o g yh a sb e e nw i d e l yu s e di nd a i l yl i f e f i r s t ，t h i st h e s i sd e t e r m i n e st h es t r u c t u r eo ft h ee n c r y p t i o na c c e l e r a t o rb a s e do na e sa n dm d 5 e n c r y p t i o na l g o r i t h m st h r o u g ht e c h n o l o g yr e s e a r c h t h e n t h ea e sm o d u l ei sd e s i g n e dw i t hn o n p i p e l i n e s t r u c t u r ew h i c hs u p p o r t sf i v e o p e r a t i n gm o d e sa sf o l l o w s ：e c b ，c b c ，c f b 。o f ba n dc t r t h em d 5 m o d u l ei s d e s i g n e dw i t hn o n p i p e l i n es t r u c t u r e t h e b u i l t - i nh a r d w a r er a n d o mn u m b e rg e n e r a t o ri s d e s i g n e db ya l g o r i t h mn a m e db b s t h es q u a r ea n dm o do p e r a t i o n so ft h eb b sa l g o r i t h ma r ea c h i e v e d t h r o u g ht h ea d d i t i o na n ds h i f to p e r a t i o n f i n a l l y , i no r d e rt oi n t e r g r a t et h ee n c r y p t i o na c c e l e r a t o ri n t ot h e s e l f - d e v e l o p e ds o cc h i p 。t h ea h bb u sm a s t e rd e v i c ea n da h bb u ss l a v ed e v i c ea r ea l s od e s i g n e d a t i e rt h er t ll e v e l d e s i g n i n g 。t h em o d u l el e v e l o ft h ee n c r y p t i o na c c e l e r a t o ri ss i m u l a t e db y m o d e l s i m ，a n dt h es y s t e ml e v e io f t h ee n c r y p t i o na c c e l e r a t o ri sv e r i f i e di nt h ev c ss i m u l a t i o ne n v i r o m e n t 。i 。h ee n c r y p t i o na c c e l e r a t o rd e s i g ni ss y n t h e s i z e db yt h et o o ls y n p l i f ya n ds e n tt h eq u a r t u s i it oc o m p l e t e p & ra n dt i m i n ga n a l y s i s t h ei m a g ef i l eo u t p u tb yo u a r t u s l ii sd o w n l o a d e di n t ot h ef p g av i at h eu s b c a b l e t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ed a t a t h r o u g h p u to ft h ea e se n c r y p t i o nc o r ei s1 9 5 g b i t s a n dt h ed a t a t h r o u g h p u to ft h em d 5 e n c r y p t i o nc o r ea c h i e v e s1 0 8 g b i 眺w h i c hh a sm e tt h en e e d so fs o c c h i pc o m m e r c i a la p p l i c a t i o n s k e yw o r d s ：e n c r y p t i o na c c e l e r a t o r , a e se n c r y p t i o na l g o r i t h m ，m d 5e n c r y p t i o na l g o r i t h m ，b b sa l g o r i t h m ， s y s t e mo nac h i p 同录 摘要 a b s t r a c t 目录 目录 第一章绪论。 1 1 背j 景1 1 2 国内外研究现状1 1 3 论文的主要工作和结构框架3 第二章a e s 和m d 5 算法分析 2 1a e s 算法的数学基础4 2 2a e s 算法流程分析6 2 3 分组加密算法五种工作模式1 4 2 4m d 5 算法流程分析18 2 5 随机数生成方法2 0 2 6 月、结2 1 第三章加密加速器的硬件设计 3 1 整体结构设计2 2 3 2a e s 模块设计。2 2 3 3m d 5 模块设计2 9 3 4 硬件随机数生成器设计3 4 3 5 数据缓冲池设计3 6 3 6a h b 总线主从设备接口设计3 9 3 7d 、结z 1 3 第四章加密加速器的仿真验证 4 4 4 1 加密加速器模块级仿真4 4 4 2 加密加速器系统级仿真4 8 4 3 加密加速器f p g a 验证5 0 4 4 j 、结5 3 第五章总结与展望 致谢 5 4 5 5 5 6 参考文献 研究生期间发表论文 i i i 第一章绪论 第一章绪论 本章介绍课题背景和国内外研究现状，简要阐述目前在商业领域最为流行的分组加密算法和哈 希加密算法；阐述本课题的任务及主要工作，概述论文结构框架。 1 1 背景 随着网络技术、数据存储技术以及数据处理技术的飞速发展，信息卒十会中的信息安全问题受到 越米越多的关注。有关网络通讯中个人信息保密以及便携存储设备的数据信息保密已经成为研究热 点。新型加密技术和加密措施的出现正在酝酿着一场数字领域新的技术革命。 加密芯片在信息安全领域发挥着重要作用，特别是随着手机理财、手机支付、手机电子商务、 手机炒股等新型手机业务不断扩张，信息安全问题成为智能手机必须关注并予以解决的问题。所以 新一代智能手机大多都采用具有硬件加密功能的s o c ( s y s t e mo nac h i p ，系统芯片) 作为主处理芯 片【lj 。在数据存储领域，数据加密技术亦得剑广泛关注，新一代硬盘和移动硬盘，很多都采用硬加 密技术对数据信息进行加密。所有数据在存储的同时进行加密，如果需要读取硬盘上的数据则需要 解密。相对丁软件加密方式，硬件加密方式在系统运行时对硬盘进行读写操作，不会由于加解密操 作而对系统的运行速度造成影响。对于近年米很热的无线传感网络，信息的安全性和完整性无疑是 首要问题，而对称密码加密是确保无线传感器网络机密的标准解决方案1 2 j 。加密芯片的核心是加密 算法。目前在商业领域应用较多的有：分组加密算法d e s 3 d e s ( d a t ae n c r y p t i o ns t a n d a r d ，数据加 密标准) a l la e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ，高级加密标准) ，哈希加密算法m d 5 ( m e s s a g e d i g e s t a l g o r i t h m5 ，信息摘要算法) 和s h a 1 ( s e c u r eh a s ha l g o r i t h m 1 ，安全散列算法) 。 分组密码体制是目前商业领域比较重要且流行的一种加密体制，广泛应用于数据保密传输、加 密存储等应用场合。d e s 是1 9 7 7 年提出的密钥长度为5 6 位的加密算法，由于其密钥长度太短，随 着计算机运算能力不断提高，对其破解已经不再凼难，作为d e s 的加强3 d e s 被广泛采用，顾名思 义3 d e s 就是对一块数据用三个不同密钥进行三次d e s 运算，所以强度更高。a e s 是2 0 0 0 年1 0 月，由美国国家标准和技术协会从1 5 种候选算法中选出的一种新密钥加密标准【3 j ，有1 2 8 b i t 、1 9 6 b i t 和2 5 6 b i t 三种密钥长度，但目前采用最多的是1 2 8 b i t 密钥长度，冈为1 2 8 b i t 密钥长度已有足够的抗 攻击能力，完全可以满足目前商业领域对信息安全的需求。相对于3 d e s ，a e s 1 2 8 强度更高、运 算速度更快且消耗资源更少，所以在新一代加密产品中更多的采用a e s 而不是3 d e s l 4 j 。 哈希函数是一种单向密码体制，是一个从明文到密文的不可逆函数，也就是说，是无法解密的。 哈希函数通常用于只需要加密、不需要解密的特殊应用场合，例如，为保证数据完整性( 即保证信 息不被非法篡改) 可以使用哈希函数计算数据的哈希值，并将其保存。每当用户使， j 数据时，重新 使用哈希函数计算数据的哈希值，并与保存的数值进行比较，如果相等，说明数据完整未被篡改； 否则，数据已被非法篡改。哈希函数还可以应片j 于诸如口令表加密等场合，这时系统中保存的是口 令的哈希值，当用户进入系统时输入口令，系统重新计算用户输入口令的哈希值并与系统中保存的 值相比较，若两者相等，则用户输入的口令正确，允许用户进入系统，反之拒绝p j 。 m d 5 和s h a 1 都是哈希函数的典型代表，广泛应用于信息确认和数字签名等各个领域。m d 5 和s h a 1 均从m d 4 发展而来，他们的结构和强度等特性有很多相似之处，s h a 1 与m d 5 的最大 区别在于其摘要比m d 5 摘要长3 2 比特。对于强行攻击，产生任何一个报文使之摘要等于给定报文 摘要的难度：m d 5 是2 1 2 8 数量级的操作，s h a 1 是2 1 6 0 数量级的操作。产生具有相同摘要的两 个报文的难度：m d 5 是2 6 4 数量级的操作，s h a 1 是2 8 0 数量级的操作。因而s h a 1 对抗强行攻 击的强度更大。但由于s h a 1 循环步骤比m d 5 多，s h a 1 需8 0 次循环m d 5 需6 4 次循环，且要 处理的缓存大，s h a 1 要处理1 6 0 比特m d 5 要处理1 2 8 比特，所以s h a 1 运行速度比m d 5 慢1 6 j 。 1 2 国内外研究现状 作为信息安全技术核心的密码技术一直以来都备受关注，对密码技术的研究主要由密码编码和 东南大学硕士学位论文 密码分析两个分支组成，密码编码致力于寻求安全性高的有效密码算法和协议，而密码分析则是寻 求对已有密码算法和协议的破译方法。对于这两个研究分支任何一个包含范围都十分广泛，这里只 阐述与本课题密切相关，隶属丁密码编码技术的密码芯片的研究发展现状。 目前国内外有很多公司在做基于分组加密算法的商用加密芯片或i p ( i n t e l l e c t u a lp r o p e r t y ，知识 产权) 核，如西安希河公司的a e s 多模式加密i p 核和加密芯片、a l m a 公司的a e s 3 2 e 加密芯片、 h e l i o n 公司的a e s 加密i p 核17 j 1 8 j 1 9 1 1 1 0 j 。这些专片j 芯片或l p 核人致具有如下特点： 实现了基丁n i s tf i p sp u b1 9 7 的a e s r i j n d a e l 算法； 支持1 2 8 、1 9 2 、2 5 6 位a e s 密钥长度； 支持多种a e s 操作模式：如：e c b 、c b c 、o f b 、c f b 、c t r 、c c m 。 在数据存储领域，很多公司都采用a e s 加密算法进行数据加密，如日立5 k 2 5 0 加密硬盘、富 士通7 2 0 0 r p m 加密硬盘和明基d p 3 6 1 加密移动硬盘等。另外，目前国外主流s o c 设计公司设计的 新一代面向手持终端设备的高端s o c 芯片中，大多都集成了加密加速器。图1 1 是f r e e s c a l e 的 m c i m x 2 7 芯片内所集成的加密加速器结构框刚1 、图1 2 是s a m s u n g 的$ 3 c 6 4 1 0 内所集成的加密 加速器结构框图t 1 2 】。在这些芯片中，加密加速器大致具有如f 特点： 支持1 2 8 位密钥的a e s 加密算法； 支持5 6 位密钥的d e s 和1 1 2 位门6 8 位密钥的3 d e s 加密算法： 支持哈希( h a s h ) 加密算法m d 5 或s h a 1 ； 内置硬件随机数生成器r n g ( r a n d o mn u m b e rg e n e r a t o r ) ； 支持a h b 主、从设备总线接口。 s y m m e t r i c a s y m m e t r i ch a s h i n ga n dr a n d o ma c c e l e r a t o r ?二? s e c u r i t y c o r e ： 一 a e s 。 二 m d 5笼l f l f o ix d e sa r c 4r n g嬲 龌咧 d m a c ： 3 d e s ? s h a 一i 一 7 ： 一 = e e 阪赢竺篡= _ 黥基竺篓2 _ 图1 1f r e e s c a l em c i m x 2 7 内集成的加密加速器结构框图 s e c u r i t ys u b - s y s t e m s 劳。“磁 继r = 疆鍪篡焉翠烛画 n 矿矿 孥踟 s d m a - i 强， a翰敝。厶。翼曼”：盛豳b 爿氏 。? 渤譬尘二 ： f xb u s s y sb u s 劣 瑟三= = 二= 圈八 矿 图1 - 2s a m s u n g $ 3 c 6 4 1 0 内集成的加密加速器结构框图 2 第一章绪论 近年来本实验室一直致力y - s o c 芯片研发，经过多年努力，现己初具规模，目前正在研发一款 面向手持终端设备的高端s o c 芯片，该芯片拟应用于智能手机和掌上电脑等场合，所以要求芯片支 持硬件加密功能，顺虑这一需求，本文将设计实现一个可嵌入到自主研发s o c 芯片中的加密加速器， 该加密加速器支持分组加密算法a e s 和哈希加密算法m d 5 。 1 3 论文的主要工作和结构框架 本论文在分析a e s 和m d 5 加密算法基础上，完成加密加速器设计，并将其集成到自主研发的 s o c 芯片s e p 0 7 1 8 中完成功能前仿真和f p g a 验证。本文设计的加密加速器具有如下特点： 支持1 2 8 位密钥的a e s 加密算法并支持e c b 、c b c 、c f b 、o f b 、c t r 五种工作模式 支持哈希( h a s h ) 加密算法m d 5 内置便什随机数生成器r n g ( r a n d o mn u m b e rg e n e r a t o r ) 支持a h b 主、从设备总线接口 a e s 模块数据吞吐率可达到1 2 g b i 低 m d 5 模块数据吞吐率可达到1 o g b i f f s 根据需要论文架构拟定为： 第一章简单介绍分组加密算法a e s 和哈希加密算法m d 5 的背景及应用场合，并简要介绍目前市 面上已有的加密芯片，说明课题的研究背景、国内外研究现状和本文的主要工作。 第二章深入分析分组加密算法a e s 的背景知识及工作流程和哈希加密算法m d 5 的工作流程，详 细分析分组加密算法的五种丁作模式和随机数生成方法。 第三章是本文的主要内容，详细阐述本文设计的加密加速器，包括a e s 算法密钥扩展模块的设 计、a e s 算法加解密模块的设计、m d 5 算法模块的设计、硬件随机数生成器的设计和a h b 总线主从 设备的设计。 第四章首先对本文设计的加密加速器进行模块级仿真，然后将其集成到s e p 0 7 1 8 中完成系统级仿 真和f p g a 验证，并对验证结果进行分析。 第五章对本文上作进行总结并对尚要进一步开展的工作予以展望。 3 东南大学硕上学位论文 第二章a e s 和m d 5 算法分析 本章主要对a e s 和m d 5 算法进行分析，首先介绍a e s 相关背景知识，包括数学基础和算法流 程，然后讨论分组加密算法的五种上作模式，给出m d 5 算法流程，最后阐述随机数生成方法。 2 1 a e s 算法的数学基础 2 1 1 g f ( 2 8 ) 有限域 有限域是含有限个元素的域，它在密码学中有着重要作用，人们已经利用有限域定义出多种公 钥密码体制。a e s 把一个字节看成是在有5 艮域g f ( 2 8 ) 上的一个元素，并采用多项式表示域中的元 素。对于一个字节b ，其二进制表示为b 7 b 6 b s b 4 b 3 b 2 b l b o ，可以把b 看成是系数在 0 ，1 ) 中的多项式： b 7 x 7 + 6 6 x 6 + b s x 5 + 钆x 4 + 6 3 x 3 + b 2 x 2 + b , x + b o 。例如十六进制数 5 7 ) ( 二进制表示为“0 1 0 1 0 11 1 ) 这一字节对应的多项式为：矿+ x 4 + x 2 + x + 1 。 在g f ( 2 8 ) 域上定义了两种运算1 1 4 】：“+ ”和“牛”，下面分别予以说明： 1 ) 加法 有限域中的加法运算相当于执行异或操作，即模2 加，表示为o 。两个字节相加可以表示成多 项式形式、二进制形式和十六进制形式。多项式之和等于先对具有相同次幂的系数求和，然后再各 项相加，如式( 2 1 ) ： c ( x ) = a ( x ) + 6 ( x ) c c ( f ) = 口( f ) + 6 ( f ) ，0 f 胛( 2 1 ) 加法的零元素“0 ”是一个所有系数都等于0 的多项式，一个多项式的逆元素可以通过将其每一 个系数替换为域f 上的逆元素而得剑。c ( x ) 的最高次幂为a ( x ) 和b ( x ) 最高次幂的最大值，因此该加法运 算是封闭的。 例如： 5 7 和 8 3 ) 的和为 5 7 ) o 8 3 ) = d 4 ) ，采用多项式记法如式( 2 2 ) ： ( x 6 + x 4 + x 2 + x + 1 ) o ( x 7 + x + 1 ) = x 7 + x 6 + x 4 + x 2 ( 2 2 ) 采用二进制记法为0 1 0 1 0 1l lo1 0 0 0 0 0 1l = 11 0 1 0 1 0 0 。显然，该加法与按字节逐位异或一致。 2 ) 乘法 在多项式表示的域中，删g f ( 2 8 ) 中的乘法就是两个多项式模一个特定的次数为8 的不可约多 项式的乘积。对于a e s ，这个不可约多项式被称为m ( x ) ，由式( 2 3 ) 给出： m ( x ) = x 8 + x 4 + x 3 + x + 1( 2 3 ) 或用十六进制表示为 l1 b ，用二进制表示为9 比特 1 0 0 0 11 0 11 ) 。 则多项式a ( x ) 和b ( x ) 在有限域g f ( 2 8 ) 上的乘积可由式( 2 4 ) 表示： c ( x ) = 口( x ) 幸b ( x ) c ，c ( 石) = ( 口( x ) 6 ( x ) ) m o dm ( x ) ( 2 4 ) 例如： 5 7 木 8 3 = e l ，因为： ( x 6 + x 4 + x 2 + x + 1 ) ( x 7 + x + 1 ) = x 1 3 + x + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x + l ( x 1 3 + x 1 1 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x + 1 ) m o d m ( x ) ：( x 1 3 + x 1 1 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x + 1 ) m o d ( x 8 + x 4 + x 3 + x + 1 ) = x 7 + x 6 + 1 3 ) x 乘法 如果用多项式x 乘以6 0 ) = 岛z 7 + 6 6 x 6 + 6 5 x 5 + 6 4 x 4 + 岛x 3 + 如x 2 + b x + b o ，则有： 4 第- 二章a e s 和m d 5 算法分析 b 7 x 8 + b o x 7 + 6 5 x 6 + 6 4 x 5 + 6 3 x 4 + b 2 x 3 + 6 l x 2 + b o x ( 2 5 ) 将式( 2 5 ) 进行模m ( x ) 化简得到x 奉6 ( x ) 。如果6 7 = 0 ，则这一化简是恒等运算，乘积即为： 6 6 x 7 + b s x 6 + 么x 5 + 6 3 x 4 + 如x 3 + 6 i x 2 + b o x ；如果6 7 = 1 ，则必须减去m ( x ) 。由此得出x 乘法可以用 字节内左移操作和紧接着的一个与 i b 的有条件的逐位异或操作来实现，故x 乘法的实现效率非常 高。该运算表示成一个函数x t i m e ( b ) 。 可以利用x 乘法米加快g f ( 2 8 ) 域上任意两个元素的乘法。例如计算 5 7 ) 宰 1 3 ) 因为： 5 7 宰 1 3 = 5 7 謇( 0 1 ) o 0 2 o l o ) ) = 5 7 ) 宰 0 1 ) o 5 7 ) 宰 0 2 ) o 5 7 木 1 0 ) 5 7 ) 木 0 2 ) = x t i m e ( 5 7 ) = 彳毋 5 7 ) 木 10 ) = x t i m e ( x t i m e ( x t i m e ( x t i m e ( 5 7 ) ) ) ) = ( x t i m e ( x t i m e ( x t i m e ( a e ) ) ) = ( x t i m e ( x t i m e ( 4 7 ) ) = ( x t i m e ( s e ) = 0 7 ) 所以： 5 7 ) 母 1 3 = 5 7 木 0 1 o 5 7 ) 母 0 2 ) o 5 7 拳 1 0 ) = 5 7 o a e o 0 7 ) = 朋) 2 1 2 g f ( 2 8 ) 域上的多项式 一个字( 3 2 b i t ) 可以看作是g f ( 2 8 ) 域上的多项式1 14 1 ，每个字对应于一个次数小于4 的多项式。 多项式对应的系数简单相加可以实现多项式的相加。由于g f ( 2 8 ) 域上的加法为比特异或，因此两个 字的加法是一个简单地按位异或。 乘法则比较复杂。假设有g f ( 2 8 ) 域上的两个多项式，如式( 2 6 ) 和式( 2 7 ) ： 口( x ) = a 3 x + a 2 x 2 + 口l x + a o ( 2 6 ) b ( x ) = b 3 x 3 + 6 2 x 2 + 岛x + 6 0 ( 2 7 ) 它们的乘积c ( x ) = 口( x ) 木6 ( x ) 由式2 8 给出： c ( x ) = c 6 x 6 + c s x 5 + c 4 x 4 + c 3 x 3 + c 2 x 2 + c 1 x 4 - c o ( 2 8 ) 其中： c o 2 a o * t o q = q * t o o a o 木6 l c 2 = a 2 * b ooa l 木6 l0a o 水6 2 c 3 = a 3 * b ooa l 木6 20 口2 奎6 loa o 宰6 3 c 4 = a 3 木岛。呸幸6 20q 木6 3 岛= a 3 母6 2o 呸木岛 c 6 = a 3 木岛 显然，c ( x ) 无法由一个字表示，需要将c ( x ) 模上一个4 次多项式，将其化简为一个次数小于4 的多项 式。在a e s 算法中，这个模数多项式取为m ( x ) = x 4 + 1 。由于矿m o d ( x 4 + 1 ) = x 。4 0 d 4 。记 a ( x ) * b ( x ) m o d ( x 4 + 1 ) 的结果为j ( x ) = 口( x ) 圆6 ( x ) ，设d ( x ) = 以x 3 + 畋x 2 + a , x + a o ，则有式 ( 2 9 ) ： 5 东南大学硕士学位论文 d o = a o 幸6 0oq 幸岛a 2 木6 2oq 书包 d j = a i * b ooa o * b io q 6 2oa 2 6 3 吐= a 2 * b ooa l 宰6 loa o 6 2oa s 6 3 以= a 3 * b o o a 2 掌6 lo 口l , 6 20 宰6 3 其矩阵表示为式( 2 1 0 ) ： 以 名 吐 以 口。口3 q 呸q 口3吼 口2q 心口2 吼 口1 b l 如 良 ( 2 9 ) ( 2 1 0 ) 但需要注意的是，模式m ( x ) = x 4 + 1 不是g f ( 2 8 ) 域上的不可约多项式，这是因为 m ( x ) = x 4 + 1 = ( x + 1 ) ( x 3 + x 2 + x + 1 ) 。在a e s 中，选择了这样一个具有逆元的固定多项式进行 这样的乘法，保证了乘法的可逆性。 2 2a e s 算法流程分析 a e s 算法属于分组加密算法，其分组长度为1 2 8 位，有三种可选的密钥长度，即1 2 8 位、1 9 2 位和2 5 6 位。a e s 加解密过程是一个迭代过程，迭代的轮数n ，依赖于密钥长度14 1 。因为本文所选的 密钥长度是1 2 8 位，所以只对密钥长度为1 2 8 位的a e s 进行阐述。密钥长度是1 2 8 位的a e s ，迭代 轮数n r = 1 0 。以下各小节将详细介绍a e s 算法用到的四种基本变换、密钥扩展流程和加解密流程。 2 2 1 四种基本变换 为了提供安全性，a e s 加密算法采用四种基本变换：字节替换( s u b b y t e s ) 、行移位( s h i f t r o w s ) 、 列混合( m i x c o l u m n s ) 和轮密钥加( a d d r o u n d k e y ) 。 1 ) 字节替换( s u b b y t e s ) 变换 字节替换是一种非线性置换。假设“x ) 为状态矩阵中的一个字节，用g f ( 2 8 ) 域中的多项式形式表 示，且系数是 0 ，1 中的元素。在不可约多项式m ( x ) = x 8 + x 4 + x 3 + x + l 模乘运算下，定义了a ( x ) 的乘 法逆元，元素 0 0 的乘法逆元为其本身。字节替换，需先求出a ( x ) 的乘法逆元b ( x ) ，然后再进行仿射 变换【2 0 】。 对于a e s 算法，由于执行乘法求逆运算和仿射变换需要大量的有限域运算，所以在实际的硬件 实现中，通常把运算结果做成一个字节替换表( 也称s b o x ) ，通过查表的方式来实现字节替换，为 了替换一个字节，需要把这个字节转化为两位十六进制数，高位确定字节替换表的行，低位确定字 节替换表的列，在行列相交处的字节即为要替换的目标字节。在字节替换中，每次只对状态矩阵中 的一个字节进行替换，这一变换过程可用图2 1 表示。 a o ，0 a l 。o a o 啦 a 1 l i a 1 2 a o 3 a l ，3 a 2 ，oa 2 ，1a 2 ，2a 2 ，3 a 3 ，oa 3 ，1a 3 ，2a 3 ，3 图2 - 1通过查表实现字节替换 6 第二章a e s 和m d 5 算法分析 表2 1 为字节替换表，第一行为要替换字节的低四位，第一列为要替换字节的高四位。 表2 1 字节替换表 o123456 7 89abcdef o 6 3 7 c7 77 bf 26 b6 fc 53 00 16 72 bf ed 7a b7 6 1c a8 2c 97 df a5 94 7f 0a dd 4a 2蟠9 ca 47 2c 0 2b 7f d9 32 63 63 ff 7c c3 4a 5e 5f l7 ld 83 11 5 30 4c 72 3c 31 89 60 59 a0 71 28 0e 2e b 2 7 b 2 7 5 40 98 32 cl a1 b6 e5 aa 05 23 bd 6b 32 9e 32 f8 4 5 5 3 d l0 0e d 2 0f cb l 5 b6 a c bb e3 94 a4 c5 8c f 6d 0e fa af b4 34 d3 3 38 54 5f 90 27 f5 03 c9 fa 8 75 la 34 08 f9 29 d3 8f 5b cb 6d a2 11 0f ff 3d 2 8c do c1 3e c5 f9 74 41 7c 4a 7 7 e3 d 6 45 d1 9 7 3 96 08 14 fd c2 22 a9 08 84 6e eb 81 4d e5 e0 bd b ae 03 23 a0 a4 90 62 45 cc 2d 3a c6 29 l9 5e 47 9 be 7c b3 76 d8 dd 54 ea 96 c5 6f 4e a 6 5 7 aa e0 8 cb a7 82 52 e1 ca 6b 4c 6e 8d d7 41 f4 bb d8 b8 a d7 03 eb 56 64 8 0 3f 60 e6 l3 55 7b 98 6c 1l d9 e ee 1f 89 81 l6 9d 98 e9 49 b1 e8 7e 9c e5 52 8d f f8 ca l8 90 db fe 64 26 84 l9 92 do fb o5 4b b1 6 2 ) 行，眵位( s h i f t r o w s ) 变换 行移位是一种字节移位变换，它将状态矩阵中的行按照不同的偏移量进行循环左移，状态矩阵 的第一行保持不变，第二行向左循环移动1 个字节、第三行向左循环移动2 个字节、第四行向左循环 移动3 个字节，这一过程如图2 2 所示。 a o 。0a o ia o ，2a o 3 a l 。oa l ，1a l ，2a l ，3 a 2 ，oa 2 ，i a 2 。2 a 2 ，3 a 3 。oa 3 ，1a 3 ，2a 3 ，3 移位规则：第i 行循 环左移i 个字节 ( i - 0 3 ) a o ，0a o ，1a o ，2a o 。3 a 1 1 a l ，2a l ，3a l 。o a 2 2 a 2 。3a 2 ，oa 2 ，1 a 3 ，3a 3 。oa 3 ，1a 3 。2 图2 2 行移位变换 3 ) 列混合( m i x c o l u m n s ) 变换 列混合变换对状态矩阵中的每一列进行独立操作，它把每- - y u 都看成g f ( 2 8 ) 域上的一个四项多 项式x ) ，这个多项式与g f ( 2 8 ) 域上的i 矧定多项式c ( x ) = 0 3 x 3 + 0 1 x 2 + 0 1 x + 0 2 ) 进行模 x 4 + 1 的乘法运算。如对第j 列( 0 ，3 ) ，其对应的g f ( 2 8 ) 域上的多项式为 a a x ) = a o + q , j x + a 2 , i x 2 + 吩, i x 3 ，则列混合变换后的值为b a x ) = 巳( z ) 圆c ( x ) 。式( 2 1 1 ) 为列混 合运算矩阵表示。 针 0 20 3 0 10 2 0 l0 l 0 30 1 0 1o l 0 30 1 0 20 3 o l0 2 q n i q ，j a 2 j 吗 0 3 7 ( 2 1 1 ) 东南大学硕上学位论文 图2 3 为列混合变换图形表示。 a o ，1 a o 2 a 1 2 a 2 ，2 a 3 ，2 a o ，3 a 1 3 a 2 ，3 a 3 ，3 瀚数矩阵 鼍翳“ 9 0 20 3o lo l ? a o , i 上 ； j b 1 矗 0 10 20 3 0 l a 1 1 罗 ” l k l 0 1o l0 2 0 3 ： b o i b o ，1 鍪 b o 2 b o ，3 ： a 2 1 i j b 1 1 塑 b 1 2 b l ，3 巍 j 0 30 10 l 0 2 i 黝 b l 弘，“，旃a 缓 b 2 1 , 2 ，1 霆 b e 。2b e ，3 列混合 b 3 ，1 b 3 b 3 2 b 3 ，3 图2 3 列混合变换 4 ) 轮密钥加( a d d r o u n d k e y ) 变换 轮密钥加变换也是每次处理一列，这和列混合相似。列混合是使一个常数方阵分别和状态矩阵 的每一列相乘，轮密钥加是把一个轮密钥字和状态矩阵的一列相加。列混合操作是矩阵的乘法，轮 密钥加操作是矩阵的加法。冈为在g f ( 2 8 ) 域上加法和减法相同，所以轮密钥加变换是自身可逆的。 图2 4 为轮密钥加变换图形表示。 b o 2 b j ，2 b 2 2 b 3 ，2 b o ，3 b l 。3 b 2 ，3 b 3 ，3 图2 4 轮密钥加变换 因为在加密端使用了以上四种基本变换，所以在解密端也需要用到四种相应的基本变换，即逆 字节替换( i n v s u b b y t e s ) 、逆行移位( i n v s h i f t r o w s ) 、逆列混合( 1 n v m i x c o l u m n s ) 和轮密钥减 ( s u b r o