（计算机应用技术专业论文）rijndael算法的实现研究及应用.pdf

摘要 摘要 信息产业的发展使信息安全越来越受到重视，而密码算法又是信息安全的 基础与核心。自从高级加密标准a e s ( a d v a c e de n c r y p t i o ns t a n d a r d ) 取代了数据 加密标准d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 成为新一代的加密标准以后，a e s 的核 心算法r i j n d a e l 的研究一直倍受国内外学者的关注。 本文针对耻j n d a e l 算法的快速实现和应用做了研究。主要分为以下三个部 分： 首先，对r i j n d a e l 算法原理，设计原则进行了介绍，并详细地描述了该算 法的结构。 第二，对r i j n d a e l 算法进行了详细的分析，提出了快速有效的软件实现优 化方法。该优化方法根据r i j n d a e l 算法的代换表s - b o x 和轮函数的特点，在加 密方面，对四个轮函数变换进行合并，并用4 个2 5 6 * 2 5 6 的表实现了轮函数的 查表方法；在解密方面，实现了等价解密算法。由于轮函数是r i j n d a e l 算法的 核心，整个算法的实现就可以转换为用查表、异或和移位操作来完成。并用c 语言实现了优化后的r i j n d a e l 算法，验证了其高效性及正确性。 最后，介绍了图像的基本知识，分析了数字图像加密的特点，针对图像的 数据量大，不适合直接加密，且数字图像都以压缩的形式出现等特点，提出了 把小波变换与r i j n d a e l 算法相结合的图像加密方法。 关键词a e s ；r i j n d a e l 算法；优化；图像加密 北京t 、i k 人学t 学硕l ：学位论文 a b s tr a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o ni n d u s t r y , m o r ea t t e n t i o ni s p a i d t o i n f o r m a t i o ns e c u r i t y a n dc r y p t o g r a p h i ca l g o r i t h mi st h eb a s ea n dc o r e w h e nt h e d a t ae n c r y p t i o ns t a n d a r d ( d e s ) w a sr e p l a c e db ya 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 ew h o l ew o r l di sp u t t i n gl i g h to nr i j n d a e la l g o r i t h m ，w h i c hi st h ec o r e a l g o r i t h mo f a e s t h er e s e a r c ha n da p p l i c a t i o no fr i j n d a e la l g o r i t h mi nt h i sp a p e rc o n t a i n st h r e e p a r t s f i r s t l y , t h ek e y s t o n ea n dd e s i g np r i n c i p l eo fr i jn d a e la l g o r i t h ma r ep r e s e n t e d ， t h es t r u c t u r eo fi ti sp i c t u r e dc a r e f u l l y s e c o n d l y , w i t hm o r e d e t a i l e d a n a l y s i s o n r i j n d a e la l g o r i t h m r o u n d t r a n s f o m a t i o n s ，i tp u t sf o r w a r dt h ep r o p o s a lo fah i g h s p e e di m p l e m e n t a t i o no f r i j n d a e l f o re n c r y p t i o n ，t h ei n n e rp r o c e s s e sa r ec o m b i n e d a n ds i m p l i f i e d ，a n d r i j n d a e la l g o r i t h m i si m p l e m e n t e dw i t ho n l yf o u r2 5 6 宰2 5 6t a b l el o o k u p s ；f o r d e c r y p t i o n ，e q u i v a l e n td e c r y p t i o ni si m p l e m e n t e d s ot h a t ，t h er i j n d a e la l g o r i t h m c a nb ei m p l e m e n t e do n l y b yl o o k i n gu pt a b l e s ，x o ra n ds h i f t i n g i na d d i t i o n ，r i j n d a e l a l g o r i t h mi so p e r a t e do ns o f t w a r eu s i n gc ，a n dw i t hc o r r e c to u t p u t f i n a l l y , d i g i t a li m a g ei si n t r o d u c e da n da n a l y z e d b a s e d o ni t sh u g ei n f o r m a t i o n ， d i r e c te n c r y p t i o ni sn o ts u i t a b l e i m a g eu s u a l l ya p p e a r sa sc o n s t r i n g e n t ，w a v e t r a n s f o r ma n dr i j n d a e la r ei n t e g r a t e dt oe n c r y p td i g i t a li m a g e k e y w o r d sa e s ；r i j n d a e l ；o p t i m i z a t i o n ；i m a g ee n c r y p t i o n l l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：固啦一日期：坐啤 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：! 虱堕童 导师签名： 日期： 第1 章绪论 第1 章绪论 1 1 课题的研究背景和意义 1 1 1 a e s 及r i j n d a e l 算法的概述 分组密码是实际运行产品和系统中最常使用的对称密码，从1 9 7 6 年美国数 据加密标准算法( d e s ) 【2 】公布以来，到2 0 世纪末，d e s 算法基本主宰了分组密码 的研究和开发过程，一直是分组密码设计的标准参照物。但是d e s 历经2 0 年的 时间检验，现在已经不是一个可靠的算法。1 9 9 6 年1 月2 同美国国家标准技术 和研究所( n i s t ) 发布了高级加密标准的( a e s ) 【3 】研发来代替d e s ，作为保护敏感 信息的新的，公开的，免费的通用算法。算法必须是私钥体制的分组密码，支持 1 2 8 位分组长度和1 2 8 、19 2 、2 5 6 b i t s 密钥长度。 经过三轮遴选，r i j n d a e l 最终胜出，r i j n d a e l 是从它的两个开发者v i n c e n t r i j m e n 和j o a nd a e m e n 的名字得来，他们都是公认的国际密码界顶尖高手。 黜i n d a e l 算法是一种可变分组长度和密钥长度的迭代型分组密码，它的分组长度 和密钥长度均可独立地指定为1 2 8 b i t s 、1 9 2 b i t s 、2 5 6 b i t s ，它以其安全性强和算法 易于实现，灵活性强等各种优良性能成为a e s 的最佳选择方案。 1 1 2 研究意义 随着计算机和通信技术的发展，网上交易电子商务得以实现，信息的安全存 储，安全处理和安全传输问题越来越受到人们的重视。信息安全的研究包括密码 理论与技术、安全协议与技术，安全体系结构理论，信息对抗理论与技术、网络 安全与安全产品等领域，其中密码算法的理论与实现研究是信息安全研究的核 心。第一代数据加密标准d e s 经历了2 0 的辉煌，已经逐渐走向衰弱，其安全性 已经受到威胁，不再是一个可靠的算法。1 9 9 7 年9 月，美国国家标准和技术研 究所( n i s t ) 开始在全世界范围内征集高级加密标准( a e s ) 候选算法。经过三轮评 选，来自比利时的密码学家j o a nd a e m e n 和v i n c e n tr i j n m e n 设计的r i j n d a e l 算法 因其优越的安全性、性能和效率以及执行的简单性和灵活性获胜，成为新的加密 标准。r i j n d a e l 作为加密标准将在未来的2 0 年内用来保护联邦政府的敏感非机 密信息，也将被政府部分以及商业机构所采用。所以现在对r i j n d a e l 算法的任何 北京丁业人学t 学顾f 学化论文 研究都是具有巨大的理论意义的。 另一方面，随着网络和多媒体技术的迅速发展，多媒体通信已经成为人们之 间交换信息的主要方式，多媒体信息的安全性也越发显得重要。对于多媒体信息， 如常用的图像信息，传统的加密技术只是将其作为数据流加密，而忽略了图像数 据的特点。因为数字图像数据量一般都很大，如果直接加密，需要很长时间，而 且a e s 等算法是针对数据流的，所以使用之前还要进行预处理，即要先将2 d 的图像数据转化为1 d 的数据流，而在接收端还要将1 d 的数据流转化为2 d 的 图像数据存储格式，这无疑影响了加密操作的效率。由于大多数的数字媒体信息， 尤其是图像或者视频流都是以某种压缩方式出现的，所以对压缩图像的加密和安 全技术的研究具有重要的现实意义。 1 2 课题的研究现状 a e s 标准虽然已经生效，它在作为密码标准为全球所接受需要一段时间，人 们正在对它进行系统的科学的研究。研究的方向主要集中在以下几个方面：算法 设计原理【6 】，安全性分析7 】【8 】，统计性能分析及软、硬件实现技巧上【9 】【10 1 。 对于算法的设计原理，主要研究算法的设计，遵循的原则和整体结构。a e s 算法所遵循的是安全性和实现性原则，在整体结构上采用的是s p 网络结构。 算法安全性分析主要包括差分密码分析和线性密码分析。差分密码分析是通 过分析明文对的差分值对密文对的差分的影响来恢复某些密钥比特。线性密码分 析本质是已知明文攻击方法，找出包含明文、密文和密钥在内的统计成立的线性 式，然后用已知明文技术得出密钥信息。还有强力攻击，s q u a r e 攻击和插值攻击 等。由于p a j n d a e l 算法是个在众多的分组密码分析技术发现后才出现的，而a e s 的要求就是它能抵抗现有的任何方法的攻击，因此对r i j n d a e l 算法的密码分析还 没有重大突破。 对于统计性能，主要研究算法随即化数据能力，目前国内外的研究都比较少。 a e s 算法的实现主要分为软件和硬件两个方面。软件p c 实现主要是用高级 语言实现算法，并测试不同工作模式下的性能，还没有真正的商用的软件加密产 品。对于硬件实现，美国的g m u 和n s a 等大学和机构提供了有关a e s 的i p 核。它们都支持三种密钥长度，具有较快的加密解密速度。 2 第1 章绪论 图像方面，考虑图像信息的特征，近几年发展的图像加密系统按照加密时有 无数据压缩可分为加密的同时有数据压缩以及只有加密而无数据压缩；按照加密 对象可分为直接对图像数据进行加密以及对图像编码的辅助信息进行加密；按照 加密手段可分先对图像进行编码，再对编码信息进行加密和建立完全新式的密码 体质来达到对图像数据加密的目的。 1 3 课题的研究内容和来源 本课题的研究受到北京工业大学和日本s o r u n 公司关于“基于高级加密标 准( a e s ) 算法的加密解密的研究”合作项目的支持。数据加密标准( d e s ) 算法因 为其时效方面的优势在日本s o r u n 公司的电子商务中有着广泛的应用，但是随 着芯片处理能力和计算水平的不断进步，d e s 的5 6 比特密钥长度已经显得太短， 难以抵御穷尽密钥搜索攻击，所以d e s 的破译已经成为可能。日本s o r u n 公 司迫切需要将a e s 替换d e s 在其安全系统中运行。 a e s 与d e s 相比，虽然加密强度提高了很多，但是由于a e s 的密钥至少是 1 2 8 比特，软件实现速度远远不及d e s 。s o r l r n 公司提出了对a e s 的核心算法 r i j n d a e l 的软件实现速度的要求：对算法本身不能做任何修改，算法必须是基于 高级加密标准a e s ；在软件实现方面，算法的实现速度必须比s o r u n 公司提供 的开放源码【4 4 l 夹一倍以上。 本课题的主要出发点就是为了使r i j n d a e l 算法能更快速有效的应用到实际系 统中，针对其时效方面的不足，提出了一些改进策略。并根据图像信息的特点和 图像加密的性质，把改进r i j n d a e l 算法直接应用到图像加密中去，实现其实际应 用的意义。 1 4 本章小结 本章首先介绍了全文的研究背景，说明了研究的目的和意义，以及课题的研 究内容和来源，介绍了r i j n d a e l 算法的概念，为后面的r i j n d a e l 算法的介绍和改 进打了基础，同时概况介绍了图像加密的意义和r i j n d a e l 算法和图像加密的关 系。 第2 章r i j n d a e l 铮法 第2 章r i j n d a e l 算法 2 1 算法的数学基础 2 1 1 有限域与域上多项式 有限域是有有限个元素的域，元素个数称为域的阶。q 阶域存在当且仅当 q = p ”，p 为素数并称为有限域的特征，有限域记为g f ( p ”) 【3 3 1 。 a e s 算法中涉及两类如下形式的特征2 域上的多项式 b ( x ) = b 7 x 7 + b 6 x 6 + b s x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b l x + b o ，b i g f ( 2 ) ( 2 1 ) a ( x ) = a 3 x 3 + a 2 x 2 + a l x + a o ，a ，o f ( 2 8 ) ( 2 2 ) 其中b ( x ) 表示a e s 算法中的单字节( b y t e ) 数据，a ( x ) 表示a e s 算法中的4 字节 ( 4b y t e s ) 或字( w o r d ) 数据。单字节也可以用数据向量 b y , b 6 ，b 5 ，b 。，b 3 ，b 2 ，b l ，b o ) 或十六进制数 m ) 表示。 2 1 2 多项式运算 1 单字节( b y t e ) 运算 单字节运算是两个形如( 2 1 ) 的多项式f 3 4 1 的运算。 ( 1 ) 单字节加法：两多项式相同指数项系数的模2 加，用符号。表示。 ( 2 ) 单字节乘法：两多项式模m ( x ) 乘，用符号表示。m ( x ) 为8 次既约多项 式x 8 + x 4 + x 3 + x + 1 ，模m + ( x ) 能保证相乘后的多项式始终在g f ( 2 8 ) 上。 2 字( w o r d ) 运算 字运算为两个形如( 2 2 ) 的多项式的运算。 ( 1 ) 字加法：两多项式的相同指数项系数的对应比特的模2 加。 例： a ( x ) = a 3 x3 + a 2 x2 + a l x + a o ，b ( x ) = b 3 x 3 + b 2 x 2 + b l x + b o 贝0 a ( x ) + b ( x ) = ( a 3o b 3 ) x 3 + ( a 2o b 2 ) x 2 + ( a lo b l ) x + ( a oo b o ) ( 2 ) 字乘法：两多项式模m 。 ) 乘，用符号。表示。m ( x ) 是可约多项式x 4 + 1 ， 北京t 、i k 大学t 学硕l ：r - 6 l 论文 模m ( x ) 可以保证字乘之后的结果仍为一个字。 由于所 ) 不是g f ( 2 8 ) 上的不可约多项式，故并非所有多项式在模历7 ( x ) 下均有 乘法逆元。 3 多项式与列向量 在r i j n d a e l 中，将四字节的列向量看作g f ( 2 8 ) 上次数小于4 的多项式。为了 定义乘法运算，使用以下约化多项式： l ( x ) = z 4 + 1( 2 3 ) 在r i j n d a e l 的定义中，乘法运算的一个输入是常量多项式。因为，( x ) 在 g f ( 2 8 ) 上可约，故并非所有多项式在模，( x ) 均有乘法逆元。如果多项式x + l 不 能整除b ( x ) ，贝q b ( x ) 有乘法逆元。 以下将更详细地介绍在r i j n d a e l 中所采用的与给定多项式相乘的运算。 设6 ( x ) = b 3 x 3 + 6 2 x 2 + b l x + 钆是一个给定的3 次多项式，并设c ( x ) 和d ( x ) 是两个 系数分别为c ；和d ，的多变量多项式( 0 m ，2 d p i ) 后l左移c l 位、 ) j y d口 左移c 2 位 bp y wx y z寿移c 3 位wx j ， 图2 - 2s h i f l r o w s 变换 f i g u r e2 - 2s h i f t r o w st r a n s f o r m a t i o n 图2 3m i x c o l u m n s 变换 f i g u r e2 - 3m i x c o l u m n st r a n s f o r m a t i o n 由于c ( x ) 是可逆的，并且d ( x ) = 。0 x 3 + 0 d x 2 + 0 9 。x + 0 e ，所以这个变换的 逆也可以用一个矩阵乘法来表示： 0 e 0 9 0 d 0 b 0 曰 o e 0 9 o d 0 d 0 b 0 e 0 9 矗( x ) 的系数为如、d j 、0 9 、o e ，与加密过程比较，解密的系数较大， 1 0 m 矾如仍 丌i j i i i j i i 儿 踟讲m 以 9 d 8 e凹凹呈耋晒 ，。，l1， 巩魏现现 。，。，l 所以就需要花费更多的时间和资源。 4 轮密钥加a d d r o u n d k e y a d d r o u n d k e y 是唯一的一个有密钥参与运算的变换，在这个变换中，将状态 与轮密钥进行简单的按位异或运算，轮密钥是由初始密钥进行密钥扩展后得到 的。轮密钥的长度和分组长度相同。 图2 4 说明了a d d r o u n d k e y 的变换过程。 o k o 。l k o , 2k o 3k o 5 图2 4a d d r o u n d k e y 变换 f i g u r e2 - 4a d d r o u n d k e yt r a n s f o r m a t i o n 因为轮密钥加仅包括一个异或运算，所以这个变换的逆变换即为本身。 2 2 2 密钥调度 轮密的生成包括两部分，即密钥扩展和轮密钥选择。且遵循下面的原则。 ( 1 ) 轮密钥的总长度等于分组长度与轮数( ，) 加1 的积。如分组长度为 1 2 8 b i t ，轮数为1 0 ，则轮密钥的总长度为1 2 8 木( 1 0 + 1 ) = 1 4 0 8 b i t ； ( 2 ) 种子密钥扩展为扩展密钥，种子密钥长度为4 木。个字节； ( 3 ) 轮密钥通过如下方法求得：第一个轮密钥由前面的。个字节组成，第二 个轮密钥由接下来的m 个字节组成，以此类推。 1 密钥扩展 扩展密钥是一组线性4 字节的数组，记为w 【。木( ，+ 1 ) 】，密钥包含在丌始 的帆个字节中，轮密钥扩展以字为单位进行处理进行递归定义。若将原始密钥 看作有n 个字一块，记为：形 o 】，w i n 一1 ，则随后的【- j 1 块轮密 4 水( 尺+ 1 ) i， 钥字w i n ，w 4 ，c ( r + 1 ) 一1 】按如下方法生产：块首字由前一字左循环一个字 节，进行字节替换，结果与前一块的首字，轮常数异或而成；若密钥长度为2 5 6 比特，则块中的第5 字由前一个字进行字节替换的结果与前一块相同位置上的字 异或而成。其他的字由前面的字经过处理后得到。密钥扩展依赖于m 的值，有 r 6 和m 6 两种密钥编制体制。 ( 1 ) 当n k 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 b 水( n r + 1 ) 】) f o r ( i = o ；i n k ；i + + ) w i 】= ( k e y 4 半i ，k e y 4 宰i + 1 】，k e y 4 幸i + 2 ，k e y 4 宰i + 3 】) ； f o r ( i = n k ；i ) 在上面的c 语言函数中，s u b b y t e s ( w ) ：是- - 个返回4 个字节的函数，每个字节都 是通过作用在它上面的s b o x 后的结果。而函数r o t b y t e s ( w ) 返回是4 个字节经过循 环替换后的字，比如输入的字为a ，b ，c ，d ) ，输出为( 6 ，c ，d ，口) 。 可以看出，密n c n n f i ；i m 个字是由种子密钥构成的。接下来的每个字形 司 1 2 第2 幸r i n d a c l 算法 都等于它f j 面的w i 一1 】经过一些变换得到的。 ( 2 ) 当。) 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 b 枣( n r + 1 ) 】) f o r ( i = 0 ；i n k ；i + + ) w i 】2 ( k e y 4 木i 】，k e y 4 宰i + l 】，k e y 4 卡i + 2 】，k e y 4 丰i + 3 】) ； f o r ( i = n k ；i n b 奉州r + 1 ) ；i + + ) t e m p = w i - 1 ； i f ( i n k = = 0 、 t e m p = s u b b y t e ( r o t b y t e ( t e m p ) ) r c o n i n k 】； e l s ei f ( i n k = = 4 ) t e m p 2 s u b b y t e ( t e m p ) ； w i 】= w i n k 】 t e m p ； ) ) 。) 6 时密钥编制与n k 6 的区别在于对于满足i - 4 是女的整数倍的字， s u b b y t e s 在异或前只对w i 一1 进行字节操作。 轮常数r c o n 与。无关，且轮常数r c o n 是这样定义的： r c o n i 】= ( 火c 吐0 0 ，0 0 ，0 0 ) r c 1 】= 1 ( i e 。o1 。) r c i - x ( i e0 2 ) ( r c i l 】) = x 卜1 卜r o u n d k e y 0 专4 - - r o u n d k e y l _ 图2 5 轮密钥选择 f i g u r e2 - 5s e l e c t i o no f r o u n dk e y 2 轮密钥的选择 轮密钥i 是由轮密钥缓冲字w n b 宰z 到w n b ，一c ( z + 1 ) 组成。图2 - 5 说明 北京t 业人学t 学硕i j 学化论丈 了m = 6 ，n 。= 4 时轮密钥的选择过程。 2 2 3 加密算法 r i j n d a e l 算法的加密过程包括三个部分：一个初始轮密钥加；n ，一1 轮轮数 迭代；一个最终轮。 用c 语言表示为： r i j n d a e l ( s t a t e ，c i p h e r k e y ) k e y e x p a n s i o n ( c i p h e r k e y ，e x p a n d e d k e y ) ； a d d r o u n d k e y ( s t a t e ，e x p a n d e d k e y ) ； f o r ( i = l ；i n r ；i + + ) r o u n d ( s t a t e ，e x p a n d e d k e y + n b 宰i ) ； f i n a l r o u n d ( s t a t e ，e x p a n d e d k e y + n b 幸n r ) ； ) 密钥扩展可以在最初进行，如果预先执行了密钥扩展，贝l j r i j n d a e l 算法的加 密过程可用这一扩展密钥来描述： r i j n d a e l ( s t a t e ，e x p a n d e d k e y ) a d d r o u n d k e y ( s t a t e ，e x p a n d e d k e y ) ； f o r ( i = l ；i 0 ；i 一) i _ r o u n d ( s t a t e ，i _ e x p a n d e d k e y + n b 木i ) ； i f i n a l r o u n d ( s t a t e ，i e x p a n d e d k e y ) ； ) r i j n d a e l 密码的解密算法为顺序完成以下操作：初始的密钥加；( n r - 1 ) 轮迭 代；一个结尾轮。 逆密钥扩展的伪c 代码描述如下： i _ k e y e x p a n s i o n ( c i p h e r k e y , i _ e x p a n d e d k e y ) k e y e x p a n s i o n ( c i p h e r k e y , i _ e x p a n d e d k e y ) ； f o r ( i _ 1 ；i n r ；i + + ) i n v m i x c o l u m n ( i _ e x p a n d e d k e y + n b 母i ) ； ) 设加密算法的初始密钥加、第一轮、第二轮、第n r 轮的字密钥依次为： k ( 0 ) ，k ( 1 ) ，k ( 2 ) ，k ( n r - 1 ) ，k ( n r ) 则解密算法的初始密钥加、第一轮、第二轮、第n r 轮的字密钥依次为： k ( n r ) ，i n v m i x c o l u m n ( k ( n r - i ) ) ，i n v m i x c o l u m n ( k ( n r - 2 ) ) ， i n v m i x c o l u m n ( k ( 1 ) ) ，k ( 0 ) 逆密钥扩展中除第一轮和最后一轮之外，所有轮密钥都要进行 2 l 北京t 、i k 人学t 学硕i j 学f 节论文 i n v m i x c o l u m n 变换。因此解密算法的密钥扩展i ：l , d r l 密算法的密钥扩展要慢。 经过如上的转换，等价解密算法就跟加密有同样的轮变换顺序，即为： i n v s u b b y t e s ，i n v s h i f t r o w s ，i n v m i x c o l u m n s ，a d d r o u n d k e y ，此时，我们利用 3 2 2 的方法，把解密算法合并为一个查表操作。 设密文输入为a ，解密时经过四个轮函数变换后的状态为b ，c ，d ，e 解密的四 个轮函数可以用的公式分别来表示： i n v s u b b y t e s 变换，用i s 表示逆替换表i n v s b o x 岛，= 胚k 。，_ ，j ( 3 - 1 0 ) i n v s h i f t r o w s 变换： i n v m i x c o l u m n s 变换： d q i d l d 2 d 3 ， c o c l ，_ ， c 2 ， c 3 ， 6 0 ，_ ， b l ，一l b 2 、j + 2 岛+ 3 0 e0 bo d0 9 0 90 eo 曰 o d 0 d0 90 e0 d o b0 d0 9o e 力1 ：i 解密的a d d r o u n d k e y 变换相同： e q 0 p l ， p 2 ，_ ， e 3 ，j d o ，j d l ， d 2 。j d 3 j o k o 。j k 1 j 七2 ， 七3 ， ( 3 1 1 ) ( 3 - 1 2 ) ( 3 - 1 3 ) 综合上面四个公式，可以将四个轮函数合并到一个矩阵乘法运算中进行，如 式( 3 1 4 ) 所示： p o p l ，j p 2 ， p 3 ， o e 0 9 0 d 0 b 0 b 0 e 0 9 o d o d o b o e 0 9 o k o ，j k l ， k 2 k 3 ， ( 3 1 4 ) 吖 列 c c c c 丁jiiiiii业 门d d ， ” 托 r 仉 - 三 厶 扎 口 口 口 口 胳俗俗俗 。，l 1j 9 d b e0 吼n 仉 第3 章r i j n d a e l 算法的优化实现 再化为列向量的线性组合，用公式( 3 1 5 ) 表示： p 0 ，j p i ，j p 2 ，j p 3 ，j 0 e i 俗叫舄 j f0 b i - o ； 。毗+ ，o 芋 i 10 d o d 。嚣k ：雠 9 l r 0 9 i r 0 d 。厣+ 3 o b 0 e o k q j k l k 2 k 3 ，j ( 3 一1 5 ) 解密时需要定义四个表，分别存储与0 9 ，0 b ，0 d ，0 e 相乘后的结果。 需要指出的是，等价解密算法的密钥扩展与加密不同，等价解密算法的密钥 扩展分为两步：加密算法的密钥扩展方法k e y s c h e d u l e ，以及除了第一个和最后 一个轮密钥以外，在所有的轮密钥上使用i n v m i x c o l u m n s 。虽然k e y s c h e d u l e 变换 比直接解密多一个操作，k e y s c h e d u l e 的速度会相对变慢，在一般应用中， k e y s c h e d u l e 所占的执行时间比例很小，绝大部分是加密解密。而且当加密的轮 数增多时，k e y s c h e d u l e 消耗的时间所占比例更小，所以算法解密的总体速度将 会有明显提高。 3 2 4 针对加密自身特点的快速实现原则 对于加密算法用不同的方法来实现，并不会对算法的d n 解密强度产生影响， 但是，算法的加解密速度在不同的实现中，却可能有很大的不同。加解密速度 在根本上是由算法本身的设计决定的，但是在实现中可以使用各种优化技术进而 最大限度的发挥算法速度的潜力。本小节根据加密算法本身的特点，提出一些有 效的快速实现原则l 2 5 1 。 r i j n d a e l 算法包括两个部分，轮函数和密钥扩展。密钥扩展是将初始密钥扩 展为供每轮力l ：i 解密使用的轮密钥，密钥扩展所占的执行时间远远小于轮函数的 执行时间。轮函数是加密循环，包括异或、移位、查表等操作。所以，展开加密 循环和轮函数能提高算法的实现速度。展开加密循环就是将循环变为多个循环体 程序模块，同时也将加密循环中调用的子函数展开，这样不仅减少了循环生成跳 转指令和计算指令以及函数调用的开销，而且也将许多变量变为常量，能够有效 提高算法速度，但是缺点是增加程序的长度。 当代的c p u 都采用了许多巨型的计算机技术，包括指令流水线、超标量等等。 在定条件下，一个时钟周期内可以同时执行两条整数运算指令，从而提高速度。 2 3 北京t , l k 人学t 学硕l j 学化沦文 如果把变量长度与c p u 内部寄存器定义为长度相同，对于p e n t i u m 等3 2 位c p u 上的算法c 语言的实现，无论算法描述中的密钥和状态等变量是1 6 位还是8 位， 在程序中都应定义为3 2 位，因为若变量与c p u 内部寄存器长度不同，将使得变 量的存取都要附加其他指令，因而增加程序长度和指令周期数。 另外限制变量的数量也能有效提高算法的实现速度。在p e n t i u mc p u 中只有 7 个通用寄存器，如果内部有太多的变量，它们就不会被存入寄存器中，而是被 存入内存中，因为内存操作与寄存器操作相比是很浪费时间的，所以应该削减变 量的数量以减少内存操作。另外，算法中可定义为常量的数据不要定义为变量。 3 3 c 语言的实现 加密时，m i x c o l u m n s 变换的系数为0 1 ，0 2 ，0 3 ，与0 1 相乘即为查替换表 s - b o x 。与0 2 ，0 3 相成需要定义两个替换表： m u l _ s 0 2 1 2 5 6 = o x c 6 ，o x f 8 ，o x e e ，o x f 6 ，o x i f , o x d 6 ，o x d e ，o x 9 1 ，o x 6 0 ，o x 0 2 ，o x c e ，0 x 5 6 ，o x e 7 ，o x b 5 ，o x 4 d ，o x e c ， o x 8 c o x lc 0 x 8 9 ，o x f a ，o x e e o x b 2 ，o x 8 e ，o x f b ，o x 41 ，o x b 3 ，o x 5 e o x 4 5 ，0 x 2 3 ，0 x 5 3 ，o x e 4 ，o x 9 b ， 0 x 7 5 ，o x el ，o x 3 d ，0 x 4 c ，o x 6 c ，o x 7 e ，o x f 5 ，0 x 8 3 ，0 x 6 8 ，o x 51 ，o x d1 ，o x f 9 ，o x e 2 ，o x a b ，0 x 6 2 ，o x 2 a ， o x 0 8 ，0 x 9 5 ，0 x 4 6 ，o x 9 d ，o x 3 0 ，0 x 3 7 ，o x o a 0 x 2 e o x o e ，0 x 2 4 ，o x l b ，o x d o x c d ，o x 4 e ，o x 7 c o x e a ， o x l 2 ，o x l d ，0 x 5 8 ，0 x 3 4 ，0 x 3 6 ，o x d c ，o x b 4 ，o x 5 b ，o x a 4 ，0 x 7 6 ，o x b 7 ，o x 7 d ，0 x 5 2 ，o x d d ，o x 5 e ，o x l 3 ， 0 x a 6 ，o x b 9 ，o x 0 0 ，o x cl ，o x 4 0 ，o x e 3 ，0 x 7 9 ，o x b 6 ，o x d 4 ，o x s d ，0 x 6 7 ，0 x 7 2 ，0 x 9 4 ，0 x 9 8 ，o x b o ，0 x 8 5 ， o x b b ，o x c 5 ，o x 4 f , o x e d ，0 x 8 6 ，o x 9 a ，o x 6 6 ，o x l1 ，o x 8 a ，o x e 9 ，o x 0 4 ，o x f e ，o x a o ，0 x 7 8 ，0 x 2 5 ，o x 4 b ， o x a 2 ，o x 5 d ，o x 8 0 ，o x 0 5 ，o x 3 f , o x 21 ，o x 7 0 ，o x f l ，0 x 6 3 ，0 x 7 7 ，o x a c o x 4 2 ，o x 2 0 ，o x e 5 ，o x f d ，o x b e o x 8 1 ，o x l8 , 0 x 2 6 ，o x c 3 ，o x b e ，0 x 3 5 ，0 x 8 8 ，o x 2 e ，0 x 9 3 ，0 x 5 5 ，o x f c ，o x 7 a ，o x c 8 ，o x b a ，0 x 3 2 ，o x e 6 ， o x c o ，o x l 9 ，o x 9 e ，o x a 3 ，0 x 4 4 ，0 x 5 4 ，o x 3 b ，o x o b ，o x 8 c ，o x c 7 ，o x 6 b ，0 x 2 8 ，o x a 7 ，o x b c ，o x l 6 ，o x a d ， o x d b ，0 x 6 4 ，0 x 7 4 ，0 x 14 ，0 x 9 2 ，o x o c ，0 x 4 8 ，o x b 8 ，o x 9 c o x b d ，0 x 4 3 ，o x e 4 ，0 x 3 9 ，o x 31 , o x d 3 ，o x f 2 ， o x d 5 ，o x 8 b ，o x 6 e ，o x d a ，o x 0 1 ，o x b l ，o x 9 c ，0 x 4 9 ，o x d 8 ，o x a c ，o x f 3 ，o x c f , o x c a ，o x f 4 ，0 x 4 7 ，o x l o ， o x 6 o x f o ，o x 4 a ，o x 5 c ，0 x 3 8 ，0 x 5 7 ，0 x 7 3 ，0 x 9 7 ，o x c b ，o x a l ，o x e 8 ，o x 3 e ，0 x 9 6 ，o x 6 1 ，o x o d ，0 x 0 o x e o ，o x 7 c ，o x 7 1 ，o x c c ，o x 9 0 ，o x 0 6 ，o x f 7 ，o x l c ，o x c 2 ，o x 6 a ，o x a e ，0 x 6 9 ，o x l 7 ，0 x 9 9 ，o x 3 a ，0 x 2 7 ， o x d 9 ，o x e b ，o x 2 b ，0 x 2 2 ，o x d 2 ，o x a 9 ，o x 0 7 ，0 x 3 3 ，o x 2 d ，o x 3 c ，o x l5 ，o x c 9 ，0 x 8 7 ，o x a a ，o x 5 0 ，o x a 5 ， o x 0 3 ，0 x 5 9 ，o x 0 9 ，o x i a , o x 6 5 ，o x d 7 ，0 x 8 4 ，o x d o ，0 x 8 2 ，0 x 2 9 ，o x 5 a o x l e ，o x 7 b ，o x a 8 ，o x 6 d ，o x 2 c 2 4 第3 章r i j n d a e l 算法的优化实现 m u l _ s 0 3 1 2 5 6 = o x a 5 ，0 x 8 4 ，0 x 9 9 ，0 x 8 d ，o x o d ，o x b d ，0 x b l ，0 x 5 4 ，0 x 5 0 ，o x 0 3 ，0 x a 9 ，0 x 7 d ，0 x l9 ，0 x 6 2 ，0 x e 6 ，o x 9 a 0 x 4 5 ，0 x 9 d ，0 x 4 0 ，0 x 8 7 ，o xl5 , 0 x e b ，0 x c 9 ，0 x o b ，0 x e c ，0 x 6 7 ，0 x f d ，0 x e a , 0 x b f , 0 x f 7 ，0 x 9 6 ，0 x 5 b ， 0 x c 2 ，0 x l c ，0 x a e ，o x 6 a ，0 x 5 a ，0 x 4 1 ，0 x 0 2 ，0 x 4 l 0 x 5 c ，o x f 4 ，0 x 3 4 ，0 x 0 8 ，0 x 9 3 ，0 x 7 3 ，0 x 5 3 ，0 x 3 f , 0 x o c ，0 x 5 2 ，0 x 6 5 ，0 x 5 e ，0 x 2 8 ，0 x a l ，0 x 0 c 0 x b 5 ，o x 0 9 ，0 x 3 6 ，0 x 9 b ，0 x 3 d ，0 x 2 6 ，0 x 6 9 ，0 x c d ，0 x 9 f ， 0 xlb ，0 x 9 e ，0 x 7 4 ，o x 2 e ，0 x 2 d ，0 x b 2 ，0 x e