（计算机应用技术专业论文）基于二维logistic与chebyshev映射的aes混沌加密算法.pdf

太原理工大学硕士研究生学位论文 基于二维l o g i s t i c 与c h e b y s h e v 映射的a e s 混沌加密算法 摘要 混沌系统具有良好的密码学特性，混沌序列具有对初始条件和系统参数 的极端敏感性，以及混沌序列长期演化结果的不可预测性的特性。混沌系 统还有很好的保密通信特性，例如内在随机性、对初值和参数的极端敏感 性等等。因此混沌密码学成为现代密码学的一个重要研究前沿，具有广阔 的发展前景。 目前，对于公开加密算法结构的加密算法( d e s ，a e s ，r s a ，e c c 等) 来说，加密算法的可靠性绝大部分取决于密钥。在数学家香农( c l a u d e e s h a n n o n ) 仓l jx f _ 的信息论中，用严格的数学方法证明了这么一个结论：一切 密码算法，除了一次一密以外，在理论上都是可以破解的。因此基于传统 a e s 力n 密算法在安全性的缺点，我们想提出一种可以实现动态变换密钥的 a e s d h 密算法来达到加密算法的最大安全性。 本文介绍一下a e s 方i 密算法的理论基础，概述混沌密码学的研究现状， 和几种混沌密码学中常用的混沌映射。介绍了混沌学的一些基本概念和相 关原理，其中尤其重点介绍了决定序列密码安全性方面的几个重要因素。 我们主要针对混沌理论和a e s 算法开展了研究工作，并提出了基于混沌理论 的可以实现密钥动态变换的a e s 算法。我们提出了基于二维l o g i s t i c 混沌映 射和c h e b y s h e v ； 沌映射的a e s d n 密算法思想，两种混沌映射采用一主一副 的设计思想，其中一个混沌映射起干扰作用，然后复合这两个混沌序列产 生新的混沌加密序列。 论文主要成果及特色如下： 1 提出了一种新的混沌密钥产生方法，并将这种方法与传统a e s 加密算 法结合起来，这种方法可实现动态变换密钥的a e s 加密算法以及多密钥控制 加密。 2 分析了这混沌密钥产生方法的密钥与初值敏感性，并对改进后的a e s 算法与传统a e s 算法进行了对比。 3 对基于l o g i s t i c 和c h e b y s h e v 混沌映射的a e s 算法进行了混沌密钥分 太原理工大学硕士研究生学位论文 析、算法安全性分析、密钥空间分析及混乱性和扩散性分析。 4 给出了一种基于基于l o g i s t i c s h c h e b y s h e v 混沌映射的a e s 算法的数据 文件的实现方法。 通过分析和试验结果，证明了改进算法在序列的随机性和安全性方面较 之传统算法有了明显的改善，达到了改进的预期效果。最后我将改进算法 应用到了数字文件的加密中，设计了以改进算法为基础的数据文件加密算 法。 关键词： a e s 算法，混沌，二维l o g i s t i c 映射，二维c h e b y s h e v 映射 太原理工大学硕士研究生学位论文 d l e s i g no fa e sa l g o 砒t h mb a s e do nt w o d i m e n s i o n a ll o g i s t i ca n dc h e b y s h e v c h a o t i cm a p p i n g a b s t r a c t c h a o t i cs y s t e mh a sf i n ec r y p t o l o g yc h a r a c t e r i s t i cp r o p e r t y t h ec h a o t i c a r r a yh a se x c e e d i n gs e n s i b i l i t yi n i t i a lc o n d i t i o na n ds y s t e mp a r a m e t e r , a sw e l la s t h ec h a o t i ca r r a yl o n gr a n g ee v o l v e sb e a r i n gf r u i tb en o ta l l o w e dt of o r e c a s tt h e c h a r a c t e r i s t i cp r o p e r t y m e a n w h i l e ，t h ec h a o t i cs y s t e mh a sn i c ec h a r a c t e r i s t i co f s e c u r ec o m m u n i c a t i o ns u c ha s r a n d o m n e s s ，t h ee x t r e m es e n s i t i v i t yt ot h e p a r a m e t e ra n dt h ei n i t i a lv a l u e c h a o t i cc r y p t o l o g yb e c o m e sa ni m p o r t a n t r e s e a r c ho fm o d e mc r y p t o l o g yf o r w a r dp o s i t i o n ，a n di th a sv a s t l yd e v e l o p i n ga p r o s p e c t n o w a d a y s ，f o rt h ep u b l i cc r y p t o g r a p h ya l g o r i t h m ( d e s ，a e s ，r s a ，e c c e t c ) ，t h es e c u r i t yo fc r y p t o g r a p h ym o s t l yd e p e n d so nt h e s e c u r i t y a n d r a n d o m n e s so ft h ec i p h e rk e y i nt h ei n f o r m a t i o nt h e o r yw h i c hw a sf o u n d e d b y c l a u d ee s h a n n o n ，h eu s e ds t r i c tm a t h e m a t i cm e t h o d st o p r o v et h a t ：a n y c r y p t o g r a p h y , e x c e p td y n a m i ck e yc h a n g i n gs y s t e m ，c a nb ec r a c k e di nt h e o r y s oib r i n gf o r w a r dk i n do fn e wa e sc h a o t i ce n c r y p t i o na l g o r i t h m w h i c hc a n s c h a n g i n gt h ek e y , b e c a u s eo ft h et r a d i t i o n a la e sa l g o r i t h mh a v ed i s a d v a n t a g e o nt h es e c u r i t y f i r s tt h i sa r t i c l ei n t r o d u c e saf e wb a s i ct h e o r i e sa b o u ta e sa l g o r i t h m ， s u m m a r i z e sc h a o t i cc r y p t o l o g yr e s e a r c hc u r r e n ts i t u a t i o n ，c h a o t i cm a p p i n gi n c o m m o nu s ea n dt h et h e o r ya n dp r i n c i p l eo fc h a o s e s p e c i a l l yi m p o r t a n t l yi t i n t r o d u c e ds o m em a i nf a c t o r st h a tr e g a r d e dw i t ht h es e c u r i t yo ft h es e q u e n c e c r y p t o g r a p h w ef o c u so nt h ec h a o t i ct h e o r ya n da e sa l g o r i t h m ，a n dd e v e l o pa n i i i 太原理工大学硕士研究生学位论文 a e sd y n a m i ck e yc h a n g i n gs y s t e mb a s e do nc h a o t i ct h e o r y an o v e la e s a l g o r i t h mb a s e do n t w od i m e n s i o n a ll o g i s t i cm a p p i n ga n dc h e b y s h e v m a p p i n g h ei sp r e s e n t e d t h eo n ec h a o t i cm a p p i n gi st h ep r i m a r ym a p p i n g ；t h eo t h e ro n e i st h e s e c o n d a r ym a p p i n gw h i c hh a st h ei n t e r f e r e n t i a l f u n c t i o n w eb r i n g f o r w a r do n ek i n do fn e wc h a o t i ce n c r y p t i o na l g o r i t h mw h i c hc o m b i n e st h et w o d i m e n s i o n a ll o g i s t i cm a p p i n ga n dc h e b y s h e vm a p p i n g o u re f f o r t sa sf o l l o w ： 1 w em o d i f yan e wc h a o t i ck e ym e t h o da n dc o m b i n et h i sm e t h o da n da e s a l g o r i t h m t h ea e sa l g o r i t h mc a nc h a n g et h ed y n a m i ck e ya n db ec o n t r o l l e db y s o m ek e y s 2 w ea n a l y s e st h ee x t r e m es e n s i t i v i t yt ot h ep a r a m e t e ra n dt h ei n i t i a lv a l u e ， c o n t r a s tt h et r a d i t i o n a la e sa l g o r i t h ma n dt h ei m p r o v e da e sa l g o r i t h m 3 w ea n a l y s e st h ec h a o t i ck e y , s e c u r i t yo ft h ea l g o r i t h m ，s p a c eo fk e y ；t h e c o n f u s i o nc h a r a c t e ra n dt h ed i f f u s ec h a r a c t e r 4 w ei m p l e m e n tam e t h o db a s e do nt h ei m p r o v e da l g o r i t h mw h i c hc a n e n c r y p t t h ed a t ai n f o r m a t i o n t h r o u g ht h et h e o r ya n a l y s i s a n de x p e r i m e n t sm e t h o d ，w i t ht h et h e o r y a n a l y s i sa n de x p e r i m e n tw a y ip r o v et h ei m p r o v e m e n ta l g o r i t h mh a dd i s t i n c t i m p r o v e m e n t i nc h a o t i ck e yr a n d o m n e s sa n dt h es e c u r i t ya s p e c tc o m p a r e dw i t h t h et r a d i t i o n a la l g o r i t h m a c h i e v e sa n t i c i p a t e de f f e c t f i n a l l yii m p r o v et h e a l g o r i t h mt oa p p l yi nt h ed i g i t a ld o c u m e n te n c r y p t i o n d e s i g n e dt a k ei m p r o v e d t h ea l g o r i t h ma st h ef o u n d a t i o n ，t h eu n i o nd i g i t a li m a g es e t sa tc h a o t i ct e c h n i c a l d i g i t a ld o c u m e n te n c r y p t i o na l g o r i t h m k e yw o r d s ：a e sa l g o r i t h m ，c h a o s ，t h et w od i m e n s i o n a ll o g i s t i cm a p p i n g ， t h et w od i m e n s i o n a lc h e b y s h e vm a p p i n g i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：互x 菡 日期：沙。黾ls 、2 9 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；。学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：垫煎日期： 导师躲2 ，么嗍导师签名：毛笔堑王l 日期： 矽孓z 太原理工大学硕士研究生学位论文 1 1 引言 第一章绪论 随着计算机技术、信息技术以及网络技术的迅速发展，信息已经成为当今社会的一 种重要财富。但是当人们享受信息技术带来的巨大变革的同时，也承受着信息被篡改、 泄漏、伪造的威胁，以及计算机病毒与黑客入侵等安全问题。全世界由于信息系统安全 的脆弱性而导致的经济损失逐年上升，安全问题日益严重。信息安全的风险制约着信息 的有效使用，并对经济、国防乃至国家的安全带来了威胁。也就是说信息安全对现代社 会健康有序地发展，保障国家安全和社会稳定有着重要作用，对信息革命的成败有着关 键的影响。随着互联网和无线通信业务的迅猛发展，为了满足不断增长的种类繁多的业 务需求，数字信息在互联网和无线通信网络中的安全通信成为日益重要的竞争领域。目 前，信息安全领域的技术主要有：密码技术、防火墙技术、虚拟专用网络技术、病毒与 反病毒技术、数据库安全技术、操作系统安全技术、物理安全与保密技术以及信息伪装、 数字水印、电子现金、入侵检测、安全智能卡、p k i 、网络安全协议等。密码技术是信 息安全技术的核心，它是实现保密性、完整性、不可否认性的关键。 1 9 4 9 年香农( s h a n n o n ) 发表了“c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m ( 保密系统 的信息理论) 【l 】一文，为现代密码学奠定了理论基础，从此密码成为一门科学。同时 他也提出设计密码的观点，它们构成“私钥密码学”的理论基础。1 9 7 5 年n b s ( 美国 国家标准局) 公布了由i b m 公司的h f e i s t e l 设计的d e s ( d a t a e n c r y p t i o ns t a n d a r d ) 2 h 密 算法，并于1 9 7 5 年将它批准为数据加密的联邦标准。d e s 的公布和采用为标准是密码 学发展史上的一个里程碑。密码学的另一个重大事件发生在1 9 7 6 年，d i f f i e e 和h e l l m a n 发表了题为“n e wd i r e c t i o ni nc r y p t o g r a p h y ”馇码学的新方向) 1 2 1 一文，导致了密码学 的一场革命，开创了公钥密码的新体制。它使得从发送端到接收端进行保密通信不再需 要密钥传送，从而公钥密码学不仅可以用于保密，还可以用于认证。1 9 7 8 年出现第一个 r s a 公钥加密和签名方案，它基于大整数素因子分解难解问题。1 9 8 5 年又出现一个基 于离散对数问题的e 1 g a m a l 公钥加密方案。 但是随着密码分析学的不断发展，攻击方案的不断改进和计算机技术的日益更新， 许多传统的加密方法已显得容易被攻破。如美国的加密标准d e s ( 5 6 比特) 已经于1 9 9 7 年6 月1 7 日被攻破；2 0 0 5 又报道在商业应用中及其广泛的h a s h 散列算法m d s 和s h a l 太原理工大学硕士研究生学位论文 已被成功的攻击；另据报道1 0 2 4 比特的r s a 也可能在2 0 1 0 年被攻破。由此可见，网 络信息安全领域急切希望拥有更安全、实现方便、有效的信息保护手段。随着基础理论 和科学技术的不断发展，目前一些新兴非传统的方法进行信息加密与隐藏的方向在国外 得到充分的重视和大量的研发投入，其中混沌密码学理论就是被采纳和得到广泛研究的 方法之一。 而混沌理论是研究特殊的复杂动力学系统的理论，混沌和密码学之间所具有的天然 联系和结构上的某种相似性，启示人们把混沌理论应用于密码学领域。自从混沌理论与 密码学的紧密联系被揭示出来后，混沌这一极具潜在密码学应用价值的理论逐渐得到了 国内外众多研究者的重视。混沌系统的动力学行为非常复杂，难以重构和预测。一般的 混沌系统都具有如下基本特性：确定性、对初始条件的敏感性、混合性、快速衰减的自 相关性、长期不可预见性和伪随机性。而混沌系统所具有的这些基本特性恰好同密码学 的基本要求相一致。密码学的两个两条基本原则混淆( c o n f u s i o n ) 和扩散( d i f f u s i o n ) 在混沌 系统中都可以找到相应的基本特性：遍历性( e r g o d i c i t y ) ，混合性( m i x i n g ) ，以及对初值和 参数的敏感性等混沌系统的的确定性则保证了通信双方加密和解密的一致性；只要对混 沌映射的基本特性加以正确的利用，通过易于实现的简单方法就能获得具有很高安全性 的加密系统。另外，近几十年非线性系统的研究成果为加密变换的密码学分析提供了坚 实的理论依据，使得混沌加密系统的方案设计和安全分析能从理论上得到保证。混沌和 密码学之间所具有的天然联系和结构上的某种相似性，启示人们把混沌理论应用于密码 学领域。 虽然这些年混沌密码学的研究取得了许多可喜的进展，但仍存在一些重要的基本问 题尚待解决。设计具有自主知识产权的新型高性能的混沌密码体制是当前亟待解决的重 要问题。 而a e s ( a d v a n c e de n c r y p t i o ns y s t e m ) = c i h 密算法是由美国政府于2 0 0 1 年1 1 月2 6 日正 式颁布为美国国家标准，以弥补d e s 退出后，数据加密标准留下的空缺【3 ，4 】。由于美国 在信息技术领域的领先地位，可以预见a e s 将与它的前身d e s 样具有广阔的应用前 景。同其他对称密码系统的算法一样，a e s 具有简便高效，密钥简短，破译极其困难， 加密解密速度极快的优点。但是在使用对a e s 加密算法存在密钥空间不足、密钥单一 以及由密钥单一产生的算法安全性低等问题。 本论文主要致力于混沌加密算法的研究。对基于混沌理论的对称分块加密算法进行 深入的密码学分析研究和算法改进。本论文的研究工作有助于丰富现代密码学的内容， 促进信息安全技术的发展。在理论方面，我们对离散化的混沌映射的特殊性质做了深入 2 太原理工大学硕士研究生学位论文 研究，有助于揭示在有限域上混沌现象的量化分析问题；同时促进混沌加密系统的设计 和分析方法的不断深入，为密码学的安全分析提供新的攻击方法。在应用方面，为数字 产品安全系统的设计提供更多的思路和基本工具。 1 2 本论文选题意义 随着信息技术的不断发展，人们的生活越来越离不开信息技术的帮助，而信息安全 也随之变得越来越重要，作为信息安全的核心技术，密码学也需要不断改进革新，以适 应变化多端的应用环境。 为达到此目的，人们提出了将对称加密算法和公钥加密算法相结合的混合算法，并 己出现了多种应用。但目前的混合算法多以d e s ，3 d e s 为主，少量的新算法使用了较 为先进的i d e a 算法。d e s 是上世纪7 0 年代提出的，经过3 0 年硬件技术的发展，现状 的超级计算机能够很容易地破解d e s 算法。3 d e s 虽然对d e s 进行改进增加了安全性， 但其运算速度却很不理想。 ；2 0 0 2 年生效的a e s 加密算法是新一代的对称密钥加密算法，它比d e s 或i d e a 算 法更为安全、快捷、灵活，它加密速度快，效率高，很适合加密数据量大的信息，但同 时也带有对称加密算法的缺点：密钥空间不足和算法安全性不足等问题。 。，混沌( c h a o s ) 是非线性系统特有的一种运动形式。它是由确定性系统产生且敏感性 依赖于初始条件的往复稳态非周期运动，类似于随机震动而具有长期不可预测性，具有 很强的密码特性。本论文根据a e s 加密算法的特点和混沌理论的特点，设计了基于混 沌系统的a e s 加密算法。该算法用混沌理论与a e s 加密算法进行结合创新，相比于a e s 加密算法，有更大的密钥空间和算法安全性。然后用改进后的算法实现对数据文件的加 密系统，使其在现实中有更大的作用。 1 3 本文研究内容 论文针对a e s 加密算法的安全性进行深入研究，并结合混沌理论，使a e s 加密算 法与混沌理论结合产生出种基于混沌理论的加密算法，论文具体内容如下： 第一章：简单介绍了本论文的研究背景、课题意义和主要的研究内容及成果。 第二章：详细介绍了a e s 加密算法和其他加密算法，并从密码学角度指出a e s 加 密算法在安全性方面的不足。 3 太原理工大学硕士研究生学位论文 第三章：详细分析了当前混沌理论的发展情况以及混沌与加密算法相结合的优点。 第四章：本章是论文的主要内容，提出基于双混沌系统的a e s 加密算法。理论分 析和仿真实验结果表明，改进后的算法除了具备可靠的安全性，还具有其它的优良性质。 第五章：本章是对论文提出的算法进行了算法性能分析，并得出相应的结论，来证 明算法的可行性，并用改进后的算法实现以数据文件的加密系统。 第六章：本章是对全文的一个总结，并得出结论。 4 太原理工大学硕士研究生学位论文 第二章a e s 算法原理分析 1 9 9 7 年4 月，美国国家标准和技术研究所( n i s t ) 开始征集先进加密标准( a e s ) 算法 来替代己不安全的d e s 算法。1 9 9 8 年5 月，n i s t 宣布接收1 5 个新的候选算法并提请 全世界密码研究界协助分析这些候选算法，包括对算法的安全性和效率特性进行初步检 验。之后，n i s t 考察了这些初步的研究成果，并选定m a r s ，r c 6 ，r i j n d a e l ，s e r p e n t 和t w o f i s h 这5 个算法作为参加决赛的算法。经公众对决赛算法进行更进一步的分析评 论后，n i s t 于2 0 0 0 年l o 月宣布r i j n d a e l 作为高级加密标准( a e s ) 【5 j 。 a e s 加密算法是一种分组加密算法，分组长分别为：1 2 8 位、1 9 2 位和2 5 6 位，其 密钥长度也分别为1 2 8 位、1 9 2 位和2 5 6 位。但在高级加密标准规范中分组长度只能是 1 2 8 位。该算法可以抵抗现有的、已知的攻击方法，具有良好的代数结构，其加密过程 可以用简洁的代数方程表示。该算法具有很强的灵活性，对软件和硬件的计算环境适应 性强、易于实现，该算法性能稳定，即使在受限环境下( 如智能卡) 也具备良好的性能。 2 1 数学预备知识 2 1 1 有限域 定义l ：代数系统钮+ ， 满足下列条件： ( 1 ) f 在“+ 运算下是一个阿贝尔群，且0 是单位元； ( 2 ) f 中的非零元素在“，运算下是一个阿贝尔群； ( 3 ) v a ，b ，c f ，q o * ( b + c ) = a , , b + a e c 。 称这一个代数系统为域。 在密码研究中，我们遇到的大多为元素个数有限的代数系统。若集合f 中的元素个 数有限，则如上定义的代数系统为有限域或g a l o i s 域常用g f 表示，其中p 表示域中 元素个数。 由于有限域f 在“+ 运算下是一个阿贝尔群，即，中的元素具有有限性和封闭性， 因此必存在一个整数刀使 一。上 l + 1 + + l = 0 成立。使上式成立的最小次数p ，我们称为有限域f 的特征。 5 太原理工大学硕士研究生学位论文 2 1 2 域上的多项式 域f 上的多项式形如： 6 ( x ) = 一l x 疗一1 十6 n - 2 x 刀- 2 + 6 2 x 2 + 6 l x l + 6 0 z 称为多项式的变元，6 je f 是多项式的系数。 我们将域上的多项式看作为抽象的实体而不参加计算。由于不对多项式中的各项之 和进行计算，因此即使多项式定义在特征域上，我们仍然使用符号“+ 。 称一个多项式的次数为1 ，如果对于v j l ，均有bj = 0 ，并且1 是具有此性质的最小 数。域f 上的多项式的集合用f i x 来表示，而域，上次数小于l 的多项式的集合用删 l 来表示。在计算机内存中，f x l l 中的多项式可以通过将其1 个系数作为一个字符串来 实现有效存储。 例2 1 ：设域f 为g f ( 2 ) ，并令1 = 8 ，可以很方便地用8 个比特值( 即一个字节) 来存储一个多项式。 例2 2 - g f ( 2 ) l8 中的多项式 夕+ + + + l 等价于比特串0 1 0 1 0 1 1 1 ，也就是用1 6 进制表示的5 7 ( 比特串通常用1 6 进制的符号来缩 写) 。 2 1 3 加法 有限域中两个元素的加法定义为其多项式表示的相应系数的“加法”。此处加法是异 或运算( 记为o ) ，即模2 加，1o1 = 0 ，l00 = 1 ，0 00 = 0 。因此，多项式减法与多项 式加法的规则相同。 有限域元素的加法也可以表示成字节中相应比特的模2 加。对于两个字节 a 7 a 6 口；口4 a 3 a 2 & l a o 和 b 7 b 6 6 5 b 4 b 3 b 2 b l b o ，其和为 c 7 c 6 c 5 占4 c 3 c 2 c i c o ) ， c f = a fo6 f ( 即 c 7 = a 7ob 7 ，c 6 = a 60 6 6 ，c o = a o0 6 0 ) 。 例如，下述表达式彼此相等： ( a + ，+ x + 1 ) + g 7 + 卅1 ) = ，乜6 + 十x 2( 多项式记法) ； 0 1 0 1 0 1 1 1 ) o 1 0 0 0 0 0 1 1 ) = 1 1 0 1 0 1 0 0 )( 二进制记法) ； 5 7 o 8 3 = d 4 )( 十六进制记法) 。 6 太原理工大学硕士研究生学位论文 2 1 4 乘法 在多项式表示中，有限域g f ( 2 8 ) 上的乘法( 记为) 定义为多项式的乘积模一个次 数为8 的不可约多项式： r e ( x ) = x 8 + x 4 + x 3 + x + 1 用十六进制表示该多项式为 0 1 ) 1 6 ) 。 例如， 5 7 ) 8 3 ) = c 1 ，因为 g 6 + + ，+ x + 1 ) ( x 7 + x + 1 ) ：x 1 3 + x 1 1 + ，+ ，+ x 7 + 工7 + x 5 + ，+ ，十x + x 6 + x 4 + ，+ x + l = x 1 3 + 0 l + 2 + x s + x x x 4 + x 3 + 1 而x ，3 + x 7 7 + ，+ ，+ x 6 + ，+ x 4 + ，+ 1r o o d ( x s + x 4 + x 3 + x + 1 ) = x t + x 6 + l 模r e ( x ) 确保了所得结果是次数小于8 的二元多项式，因此可以用一个字节表示。不像加 法，乘法在相应的字节级别并没有简单运算。 上述定义的乘法具有结合性，元素 0 1 ) 是乘法单位元。对任意次数小于8 的非零二 元多项式6 ，其乘法逆元记为扩7 ) ，可通过下述方法找到：使用扩展欧几里德算法计 算多项式口和c 使得 6 口+ m g ) c = l 因此口6 m o d m ( x ) = 1 意味着 ( 力= 口( 功m o dr e ( x ) 而且，对该域上的任意口，b ( x ) 和c g ) 均有下式成立 口( 6 + c ) = 口o ) 6 + 口o ) c 由此可见，由所有2 5 6 个可能的字节值组成的集合，使用异或作为加法以及上述定义的 乘法运算，构成有限域g f ( 2 8 ) 。 2 2a e s 算法设计原则 2 2 1 设计考虑 设计者在设计r i j n d a e l 算法时主要考虑了以下三点【6 】， ( 1 ) 要抵抗现有已知的密码攻击方法； ( 2 ) 在各平台上都应具有良好的性能如较快的速度、编码要紧凑等； 7 太原理工大学硕士研究生学位论文 则。 ( 3 ) 设计要简单。 由第一点可以看出a e s 算法在设计时遵循了安全性原则，后二点则遵循了实现原 2 2 2 针对安全性的设计原则 针对某一特定的分组密码算法，其攻击方法可以分为通用攻击方法和专用攻击方法。 所谓通用攻击方法就是对所有的分组加密算法攻击都有效的方法，比如强力攻击和线性 差分密码攻击。而专用攻击方法只对该特定算法有效，一般与具体密码算法某种特定的 结构有关，对r i j n d a e l 算法而言，s q u a r e 攻击就是这种。 影响安全性的因素很多，诸如分组长度和密钥长度等，但为了有效的抵抗通用攻击， 一般都遵循香农【7 1 ( s h a n n o n ) 所提出的混乱原则和扩散原则。所谓混乱原则就是所设计的 密码应使得密文对密钥和明文的的依赖关系相当复杂以至于这种依赖性对密码分析者 来说是无法利用的；扩散原则指的是所设计的密码应使得密钥的每位数字影响密文的 许多位数字以防止对密钥进行逐段破译，同时明文的每一位数字也应影响密文的许多位 数字以便隐蔽明文数字的统计特性。为了有效的抵抗密码算法的专用攻击方法，则要对 算法的自身结构进行分析，消除其中的不安全因素。 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 2 3 针对实现的设计原则 一个密码算法若要用软件实现，则尽量使密码运算针对某一长度的子块进行，子 块的长度应尽可能的适应软件编程，如采用8 位、1 6 位、3 2 位的子块，这是因为在软 件实现中，单个比特之间的置换是难于实现的；除了使用子块外，密码算法应采用一些 易于软件实现的运算，如标准处理器能直接处理的加法、乘法、移位运算等。密码算法 若是要用硬件实现，那么就要求密码算法的结构尽可能紧凑，轮变换尽可能一致，这样 就便于用a s i c 或是f p g a 来实现；同时在设计时，使加密过程和解密过程尽可能相似， 这样便于用一个功能模块同时实现加密和解密过程。 r i j n d a e l 算法的运算是针对字节进行的，密码运算也非常简单，并且结构紧凑，每 轮变换也基本一致，所以易于用软件或是硬件实现，因此具有良好的实现性。 8 太原理工大学硕士研究生学位论文 2 3 高级加密标准算法描述 m j n d a e l 算法是一个可变数据块长和可变密钥长的分组迭代加密算法，数据块长和 密钥长可分别为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 算法在整体结构上采用的是代替置换网络构成 圈函数，多圈迭代。每一圈由3 层组成： 非线性层：进行s 盒变换b y t e s u b ，由1 6 个s 盒并置而成，起到混淆的作用。 线性混合层：进行行移位变换s h i t t r o w 和列混淆变换m i x c o l u n m ，以确保多圈 之上的高度扩散。 密钥加层：进行轮密钥加变换a d d r o u n d k e y ，将轮密钥异或到中间状态上。 a e s 的输入输出可以看作8 位字节的一维数组。对加密来说，其输入是一个明文和 一个密钥，输出是一个密文分组。对解密而言，输入是一个密文分组和一个密钥，而输 出是一个明文分组。a e s 的轮变换及其每一步均作用在中间结果上，我们将中间结果称 为状态。状态可以形象地表示为一个矩形的字节数组，该数组共有4 行。状态中的列数 记为n b ，它等于分组长度除以3 2 。 a e s 算法加密的基本流程( 解密流程同加密流程大同小异) 如下图2 - l 所示： 图2 - 1a i s 加解密结构图 f i g u r e2 - 1a e se n c r y p ta n dd e e r y p t 9 太原理工大学硕士研究生学位论文 2 3 i 状态、密钥种子和轮数 a e s 算法的明文分组以及每次变换的中间结果分组叫做状态，用阵列表示如图2 - 2 所示，其中母。为个单字节( 以后简称字节) ，该阵列有4 行肋列( 肋= 4 ) ，其中，表 示行号，c 表示列号，0 r 2 3 3 非线性混合层与s - 盒 在轮变换中，s 盒用于对状态矩阵进行非线性混合，以起到混淆的作用【9 】。这个非 线性混合的过程就是一个可逆的字节替换运算( s u b s t i t u t eb y t e ) ，利用一张字节替换表， 分别对状态矩阵中的每个字节进行查表替换，这张字节替换表就称为s 盒。s 盒用于加 密过程，在解密过程中则需要生成逆s 盒。 在a e s 加密算法中，s - b o x 的作用是进行s u b b y t e s ( ) 变换，如下图2 4 ： ，一s _ b o x 。 、 s o os 0 1 s 0 2 ，s 0 3s o 夺 j - s 位 s 0 3 ， s 忘 3 s l o s l l s 鸥 s l o s l o s 2 0 s 2 ls 2 2 s 2 3s2 0s fi ： s 2 3 s 3 0s 3 l s 3 2s 3 3 s3 0 s a ls 3 2s 3 3 图2 - 4s u b b y t e s ( ) 变换 f i g u r e2 - 4s u b b y t e s ( ) t r a n s f o r m 1 2 太原理工大学硕士研究生学位论文 s 盒是由在g f ( 2 8 ) 域上乘法求逆运算和在g f ( 2 ) 域上的一个仿射运算对字节运算 后得到的。其中，乘法取逆运算为： - - a ( x ) r o o d 嬲 其中m ( 力= 工3 + + 工3 + 工十1 ，当a ( x ) = 0 。时，其逆元素也为0 。而在g f ( 2 ) 域上的 仿射运算则可以利用下面的仿射变换矩阵进行。 l 0 o 1 o o ( 2 4 ) 将从0 0 到f f 的十六进制数经过上述运算就可以得到一个1 6 1 6 的字节替换表，也 就是用于加密的s 盒。对于用于解密逆s 盒的，需要通过在g f ( 2 ) 域上的逆仿射运 算生成，下面是进行逆仿射运算的仿射变换矩阵。 10 ll ll ll ll 0t o o o 0 o0 l0 ll 1l l1 l o 1ll o1l 00l 000 1o0 ll0 0 ( 2 5 ) 经过简化后，只需对s 一盒进行循环移位和异或运算就可以实现该逆仿射变换，生成 逆s 盒。利用非线性变换可以提高算法对差分攻击和线性攻击的抵抗强度。 2 3 4 线性混合层的行移位和列混合 轮变换在利用s 一盒完成字节替换后得到新的状态矩阵，接着就要利用纯属混合层对 新状态矩阵进行线性混合，这个变换层包含行移位和列混合两个子变换层。 行移位根据不同的分组长度做相应的循环移位运算，加密算法的行移位过程如图2 5 所示【l o 】。在加密过程中，状态矩阵中的后三行要按字节进行左移位。在解密过程中，则 1 3 砌新庇乃缸私新 o 0 l o l 0 0 l o l o l o 0 l o 弗儿儿几儿儿所 知耽知知乃新乃儿乃几儿儿n 要进行逆行移位，即将状态矩阵中的后三行按字节进行右移位。表2 2 给出了在分级不 同的情况下移位的次数。即在后三行的第l 行要移位c l 字节，第2 行要移位c ：字节， 第3 行要移位c 3 字节。 表2 吃行移位次数 t a b l e2 - 2s h i f l r o w sn u m b e r n bc l s 0 0 s o ls 0 2s s l os 1 1s 1 2s 1 3 $ 2 0s 2 ls 2 2$ 2 3 $ 3 0s 3 ls 3 2$ 3 3 s o os 0 1s 0 2s 0 3 s l ls 1 2s 1 3s l o s 2 2s 2 3s 2 0s 2 l s 3 3s 3 0s 3 ls 3 2 图2 - 5 加密算法中行移位过程 f i g u r e2 - 5t h es h i f l r o w sp r o c e s si nm g o r i t h m 图2 - 6 加密算法中列混合变化过程 f i g u r e2 - 6t h em i x c o l u m n sp r o c e s si nm g o d t h m 1 4 太原理工大学硕士研究生学位论文 行移位后所得的状态矩阵还要进行列混合，加密算法的列混合过程如图2 - 6 所示。 在列混合变换时，把状态矩阵的一列看作在上的多项式，与一个常数多项式c ( x ) 相乘并 模工+ 1 后得到的结果。其中， c ( 功= 3 x 3 + + x + 2( 2 6 ) 设6 g ) x ) o 口o ) ，则可以把上述运算转变成如下的一个矩阵运算。 i0 20 3 0 10 1 i0 10 20 30 1 l0 1 0 10 2 0 3 l0 3o l o l0 2 i i i ( 2 - 7 ) i i l 利用列混合可以使第一列的第一个字节与该列中的其他任一字节相互作用，而行移 位则可以使第一轮中的其他字节互相混合，由此经过多轮运算可以达到相当强的扩散作 用。 在解密过程中，要做逆列混合的运算。逆列混合运算可转变成如下的一个矩阵运算。 2 3 5 密钥加层及密钥扩展 q a 3 , y f 0 e i lq 8 = i l0 d l l0 9 l 0 90 do bl 0 e0 90 d 4 0 b0 匠0 9l i 0 d0 b0 el l k l 弘8 ， 1 j 在进行轮变换前，一般要进行密钥扩展，来产生轮密钥( r o u n d k e y ) 。如不算初始密 钥，在这一过程中需扩展出m 个轮密钥，用于每轮变换的最后的密钥加层运算 ( a d d r o u n d k e y ) ，即把状态矩阵和轮密钥进行异或，实现对状态矩阵的次性掩盖。由 于每轮使用的轮密钥相关，在有些算法中也把产生轮密钥的