（通信与信息系统专业论文）高级数据加密标准aes的代数性质研究.pdf

摘要 随着计算机和通信技术的发展，用户对信息的安全存储、安全处理和安全传 输的需求越来越迫切。随着攻击手段的日益提高和计算机计算速度的增长，原有 的d e s 密码体制由于密钥长度太短，无法满足需要的安全强度。最新的密码体制 a e s 具有简洁、实现速度快、安全性高等优点，是分组密码加密体制的一个相当 好的标准。 本文主要对美国高级加密标准r i j n d a e l 算法进行了比较深入的研究，包括算 法的代数性质和有效的攻击方法。主要成果有： 1 、 对r i j n d a e l 算法进行了详细的介绍，包括算法的设计原理、设计原则， 并对国内外的研究现状进行了总结 2 、针对a e s s 盒的设计特性，详细的分析了其代数性质，给出了s 盒的 一个性质，并发现了其8 个布尔函数之间的等价性，为进一步分析 a e s 提供了理论基础。 3 、 介绍了目前针对a e s 的有效的一种攻击方法：差分容错攻击，并给出 了完整的攻击实例来加以说明。 关键词： a e s 、r i j n d a e l 算法、s 盒、分组密码 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t e ra n dc o m m u n i c a t i o nt e c h n o l o g y , t h eu s e r s r e q u i r e m e n t s f o rt h ei n f o r m a t i o n s s a f e t y s t o r a g e ，s a f e t yp r o c e s s a n d s a f e t y t r a n s m i s s i o ni t r e g e t t i n gm o r ea n dm o r ee x i g e n t w i t ht h ei m p r o v e m e n to fa t t a c k m e t h o da n dc o m p u t i n g ，d e si sn o ts e c u r ef o ri t st o os h o r tk e yi nl e n g t h t h ea d v a n c e d e n c r y p t i o ns t a n d a r d i sa g o o dc r y p t o s y s t e m f o ri t ss i m p l i c i t y , h i g hr a t ea n d s e c u r i t y t h i sp a p e rh a sad e t a i li n v e s t i g a t i o no n r i j n d a e l ，i n c l u d i n gi t sa l g e b r a i cp r o p e r a n d e f f i c i e n ta t t a c k i n gm e t h o d t h ec e n t r a lc o n t r i b u t i o ni sa sf o l l o w s ： 1 ad e t a i li n t r o d u c t i o no fr i j n d a e li s p r e s e n t e d ，i n c l u d i n g t h e d e s i g n p r i n c i p l ea n d t h ec u r r e n tr e s e a r c hr e s u l t 2 k e y w o r d s ： t h eo n l yn o n l i n e a rp a r ts - b o xi s a n a l y z e da n da ni m p o r t a n ta l g e b r a i c p r o p e r t yi s i n t r o d u c e d t h ee q u i v a l e n c eo fe i g h tb o o l e a nf u n c t i o n si s f o u n d ，a n di ti sah e l pt oa n a l y z ea e s i nd e t a i l a ne f f i c i e n ta t t a c km e t h o d a g a i n s ta e s i sp r e s e n t e dw i t had e t a i le x a m p l e w h i c hi sc a l l e dd i f f e r e n t i a lf a u l t a n a l y s i s a e s ；r i j n d a e l ；s - b o x ；b l o c kc i p h e r 创新性声明 y5 9 5 2 7 3 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确地说明并表示了谢意。 本人签名：j 、盖一日期，、午旧、。厂本人签名：! ：l 璺二日期：) ： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电予科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名：i 塾! ；：日期 导师签名 日期丝 兰：2 箍= 童缝迨! 第一章绪论 随着计算机网络和通信技术的迅猛发展，人类进入了信息社会。利用互联网 获得信息和交换信息的需求越来越迫切，与此同时，信息安全问题也e t 趋突出， 网络入侵、信息泄密及网络犯罪等案件也日益上升，因此，如何堵住网络的安全 漏洞和消除安全隐患已成为人们十分关心和重视的问题，而解决这一问题的有效 手段之一是使用现代密码技术。信息安全已成为信息科学领域的热点课题，对此 方向的研究不但具有理论价值，而且具有广泛的实际应用价值。 2 0 世纪末蓬勃发展起来的互联网已成为全球范围内最大的信息传播媒体。 从技术上讲，这主要归功于互联网的开放性。在它带给人们无限惊喜的同时，也 导致了互联网的不安全性和不稳定性。开放性使全球范围内的网络互连成为现实， 同时又使得网络具有天生的脆弱性。一般来说，计算机中的大量数据由于传输的 公共信道和存储的计算机系统非常脆弱，容易受到攻击：一种是从传输信道上截 取信息，或从存储的载体上偷盗或拷贝信息，这称之为被动攻击，其结果是导致 数据的泄漏和对隐私权的侵犯；另一种是在传输过程中对存储的数据进行非法删 除、更改或插入等操作，这称之为主动攻击，其结果可能引起数据或文件的混乱， 严重时可能导致信息处理系统的完全失控。加密技术是保证信息安全的一个必不 可少的手段，加密技术的核心是密码技术。 1 1 密码学的基本概念 密码学包括密码编码学和密码分析学两部分，密码编码学是密码体制的设 计学，而密码分析学则是在未知密钥的情况下从密文推演出名文或密钥的技术。 密码学是对信息进行编码实现隐蔽信息的一门学问，而密码分析学是研究分析破 译密码的学问，两者相互对立，而又相互促进的向前发展。 采用密码方法可以隐蔽和保护需要保密的消息，使未受授权者不能提取信 息。被隐蔽消息称作明文消息( n a i n t e x t ) 。密码可将明文变成另- - ；f e e 隐蔽的形式， 称作密文( c i p h e r t e x t ) 。这种变换过程称作加密( e n c r y p t i o n ) 。其逆过程，即由密文 。阪复出原明文的过程成为解密( d e c r y p t i o n ) 。对明文进行加密操作的人员称作加密 员或密码员( c r y p t o g r a p h e r ) 。密码员对明文进行加密时所采用的一组规则称作加密 算法( e n c r y p t i o n a l g o r i t h m ) 。传统密码体制所用的加密密钥和解密密钥相同，也成 为对称算法，其代表是d e s 1 ( d a t a e n c r y p t i o ns t a n d a r d ) ，新一代加密算法是 r i j n d a e l ；非对称算法在加密和解密的过程中使用不同的密钥( 公钥和私钥) ，其中 公钥公开，私钥保密，是一种由已知的加密密钥推演出解密钥在计算上是不可行 的密码体制。这类算法的主要应用是身份验证和数字签名，代表算法是r s a 公 西安也予科技人学硕士论文：高级数据加密标准a e s 的代数性质研究 司的r s a 算法。 1 2 对称密钥加密算法 对称密钥加密是指加密密钥与解密密钥相同，通信双方必须都拥有同一个密 钥并保持其机密性。发送信息时，发送方用自己的密钥进行加密，而在接收方收 到数据后，又用对方所给密钥进行解密。对称密钥算法应用较多的是d e s 2 捌算法。 d e s 输入6 4 位密钥，实际使用密钥长度为5 6 位( 有8 位用于校验) 。加密是把明文以 6 4b i t 为单位分成块，而后用密钥进行块加密，把明文转换为密文。d e s 算法对6 4 位的输入数据块进行1 6 轮的编码。在每轮编码时，都要从5 6 位的主密钥中得出一 个唯一的轮次密钥，经验证采用的1 6 次迭代扩散己能满足安全要求。在加密过程 中输入的6 4 位原始数据被转换成6 4 位被置换完全打乱了的输出数据，在解密是可 以用解密算法将其转换为原来的状态。d e s 的整个体制是公开的，系统的安全性全 靠密钥的保密性。算法在每次迭代时都要有一个子密钥提供加密用，如果随机地 选取密钥，则在总数2 ”个密钥中，弱密钥所占比例极小，因此，弱密钥的存在不 会危及d e s 的安全性。但随着应用的发展，d e s 亦已经不能抵抗现有的日益强大的 计算能力的进攻。目前，攻击d e s 的最有效的办法是密钥穷举攻击。结合差分密码 分析和线性密码分析的穷搜索攻击将是经济可行的破译d e s 的有效手段。 d e s c h a l l d x 组经过近四个月的努力，通过i n t e m e t 搜索了3 + 1 0 ”个密钥，找出了 d e s 的密钥，恢复出了明文【4 2 】。1 9 9 8 年5 月，美国e f f ( e l e c t r o n i cf r o n t i e rf o u n d a t i o n ) 宣布，他们以一台价值2 0 万美元的计算机改装成的专用解密机，用了5 6 d 时破译 了5 6 b i t 的d e s i “。随着d e s 弊端的暴露，1 9 9 7 年美国国家标准技术研究所( n i s n 发起征集a e s f 4 1 ( 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 s e 作组。1 9 9 9 年n i s t 召开a e s 候选会议，公布了满足要求的1 5 个a e s 候选算法，并 公布了他们的分析测试结果。2 0 0 0 年1 0 月2 日美国商务部宣布高级加密标准最终评 估结果：比利时密码专家推荐的r i j n d a e l 算法最终获胜。r i j n d a e l 是由比利时的j o a n d a e m e n 并n v i n c e n tr i j m e n 提交的一个候选算法， r i j n d a e l 算法是一个迭代分组加 密算法。其密钥空间l k d e s 大得多， 相应的转换操作轮数为1 0 1 2 1 4 。r i j n d a e l 的算法原型是s q u a r e 算法，设计策略是宽轨迹策略( w i d et r a i ls t r a t e g y ) 【5 】0r i j n d a e l 算法在整体结构上采用的是代替置换网络，多轮迭代，每一轮由三层组成：非线 性层、线性混合层以及密钥加层n 线性混合层： 进j t s u b b y t e ( 字节替换) 转换，即在状态中每个字节进行非线性字节转换，确 保多轮之上的高度扩散： 非线性层： 进行s h i f t r o w ( 行移位) 运算和m i x c o l u m n ( y l j 混合) 运算，它是由1 6 个s 盒并置而 成，起到混淆作用。s - 盒选取的是有限域g f ( 2 8 ) 中的乘此逆运算，它的差分均 匀性和线性偏差都达到了最佳【5 1 ； 密钥加层： 进行a d d r o u n k e y ( 密钥加) 运算，子密钥与状态对应字节异或。 r i j n d a e l 算法的解密结构与加密结构相同，其变换为加密算法的逆变换。算法分析 结果显示，7 轮以上的r i j n d a e l 对s q u a r e 攻击是免疫的。r i j n d a e l 的4 轮、8 轮最佳差 分特征的概率及最佳下线性逼近的偏差均较低。至今还没有发现r i j n d a e l 算法的明 显缺点，也没有发现明显的安全漏洞，算法具有良好的安全系数【4 3 】。 1 3 非对称密钥加密算法 1 9 7 6 年d i f f i e 和h e l l m a n 的文章引入了公钥密码学的概念，它给出一种新的有 创新性的密钥交换的方法。这种方法的安全性基于离散对数问题的难解性。虽然 当时他们并没有具体实现这种公钥加密方案，但是想法非常清晰，引起了密码学 界的广泛兴趣。1 9 7 8 年出现第一个r s a 公钥加密和签名方案，它基于大整数分解 难解问题。虽然2 0 世纪8 0 年代关于大整数素因子分解方法有很大的进展，但是人 们仍然认为r s a 是安全的。1 9 8 5 年又出现一个基于离散对数问题的e l g a m a l 公钥加 密方案。目前，国际上流行的非对称密码主要有两种，一种是建立在大整数因子 分解问题基础之上，其中最典型的是r s a 公钥密码；另一种是基于离散对数问题， 其中影响最大的是椭圆曲线公钥密码。r s a 公开密钥密码是由r r i v e s t ，a s h a m i r 和l a d l e m a n 于1 9 7 7 年提出的。它的取名来自三位发明者的姓的首字母。r s a 的基 础是数论的欧拉定理，它的安全性依赖于大数的因数分解的困难性。 r s a 公开密钥密码体制所根据的原理是【4 3 】：根据数论，寻求两个大素数比较 简单，而分解它们的乘积则极其困难。在这一体制中，每个用户有两个密钥：加 密密钥p k = ( e , n ) 和解密密钥s k = ( d ，n ) 。用户把加密密钥公开，使得系统中的任何 其他用户都可以使用，而对解密密钥中的d 贝, l j 保密。对于r s a 体制的安全，必须仔 细选择每个参数。由于大整数因子的分解的能力同益增强，对r s a 公钥密码的安 全带来了威胁。 l i s a 和a e s 的性能比较【4 3 】 a e s 与r s a 两种算法各自有其优缺点，以下从几个方面进行论述。 ( 1 ) 在加密、解密的处理效率方面，a e s 算法优于r s a 算法。因为a e s 密钥的长度 为1 2 8 ，1 9 2 和2 5 6 = l 特，可以利用软件和硬件的方法来实现高速处t 望；r s a 算法需要 进行大整数的乘幂和求模等多倍字长的处理，处理速度明显慢于a e s 算法。 ( 2 ) 在密钥管理方面，r s a l l a e s 更加优越。因为r s a 算法可以采用公开形式分配 4 西安电予科技大学硕士论文：高级数据加密标准a l e s 的代数性质研究 加密密钥，对加密密钥的更新也很方便、简单，并且对不同的通信对象，只需对 自己的解密密钥保密即可；a e s 算法要求通信前对密钥进行密钥分配，密钥的更换 困难，对不同的通信对象a e s 需要产生和保管不同的密钥。 ( 3 ) 在安全性方面，两者都较好，还没有在短时间内破译它们的有效方法。r s a 的 安全性依赖于大整数分解的困难性，而a e s 依赖于密钥的保密性。 ( 4 ) 在签名和认证方面，a e s 从原理上不可能实现数字签名和身份认证，但r s a 很 容易实现。 ( 5 ) 在改进方面看，a e s 和r s a 均为基于密钥的分组加密算法，都可以通过增加密 钥的比特长度来增加安全性。 网络安全已经成为一个跨多门学科的综合性学科，是在攻击和防护这一对矛盾 的斗争发展起来的，新的攻击必然导致研究新的防护措施，新的防护措拖又招致 新的攻击，循环反复。 1 4 本论文的主要工作及章节安排 目前，在a e s 领域中还有许多理论和实际问题有待继续研究和完善，是密码理 论研究中国内外学者研究的热点课题之一j 这些问题包括如何设计算法的硬件结 构使其加解密过程对称，从而共享硬件逻辑单元；如何设计有效的方法来求解有 限域中的元素的逆，从而加快实现效率和硬件实现的简单性：如何提高对a e s 的攻 击能力，例如提高攻击的简化轮数；如何从密码算法的设计入手，分析算法的代 数结构；如何从密码算法的实现入手，探索算法在实现上的一些弱点。a e s 算法要 获得真正意义上的破译，还需要很长一段时间，需要密码分析者的不懈努力。本 文的安排如下： 第二章介绍了a e s 的设计原理和设计原则，并对a e s 的研究现状进行了详细的 介绍。 第三章针对a e ss 盒的设计特性，详细的分析了其代数性质，给出了s 盒的 一个性质，并发现了其8 个布尔函数之间的等价性，为进一步分析a e s 提供了理 论基础。 第四章给出了a e s 的性能分析，介绍了目前针对a e s 的有效的一种攻击方 法：差分容错攻击，并给出完整的攻击实例加以说明。 第二章r i j n d a e l 算法设计原则 a e s 选择进程是由n i s t 宣告一项开发a e s 计划而开始的，随后于1 9 9 7 年正式 征集加密算法。征集要求规定a e s 必 须是一种非保密的、可以向公众公开的加密算 法，在世界范围内不用交专利权税就可以得到，而且a e s 要实现分组密码，具有1 2 8 比特的分组长度，支持三种密钥大小即1 2 8 、1 9 2 和2 5 6 h 特。r i j n d a e l 算法因其优 越的安全性、性能和效率以及执行的简易l 生和灵活性成为美国新的高级加密标准 a e s ，在未来2 0 3 0 年内保护联邦政府敏感的非机密信息。政府部门之外的许多商 业组织、研究机构和个人都期望采用这一高级加密标准本章描述刚n d a e l 算法的 基本原理，对其设计原则进行了研究。 表。 2 1a e s 的评选过程 最早考虑用a e s 代替d e s 是在9 0 年代初期，表1 t 7 1 给出a e s 产生的详细时间 表2 1a e s 评选时间表 时闻括碴详牲 1 9 9 0 。早船考虑a e s f 每疆 】蝣 指h a 匹代替d b 髓在1 9 鸲年嬲评估击上 1 9 9 7 1 2发布蟠班p s 研发计划 1 9 9 6 年已开始礁钎 1 9 9 丑乳1 2 征集蜈选算祛 ! 帮界的广泛响应( 共2 1 1 9 9 8 。8 - 2 0 i ! ：擎a 器安议召开c a 盟- c a t l -釜变誉十候选算法，第一 1 9 9 9 6 篆三欢a e s 击议召开( 艘， 分析1 5 个懒算法 1 9 9 9 8 逃出5 十进行第二袍详怙第二轮开嫱 2 a 4 j 臻扶a 醛鲁设召开( a 瞄， 矗哲对5 个惯逃算姥进行努析 j o o n l m 2 宣布n l m 的评选站粜硒赫获胜 2 d 1 l a 基发布脯草秉 豪珊瞄草案进行公众评 n i s t 仅仅宣布此算法被列为f i p s 的一个新草案，用以征集公众的评论，之后 还要进行标准的修订，如果合适，才会被采纳为正式的政府标准来维护商业的安 全。a e s 以后的发展有以下两个阶段：2 0 0 1 年2 月，评述期结束；2 0 0 1 年4 6 月， a e s f i p s 正式使用，并通过规范测试。以后n i s t 每5 年对其进行一次评估。 西安电子科技大学硕士论文：高级数据加密标准a e s 的代数性质研究 2 1 15 个a e s 候选算法 第三次a e s 7 】会议于2 0 0 0 年4 月在纽约召开，接受了提交的3 7 篇论文及报告以 及1 3 6 组公众评论意见【8 ，9 ，1 0 ，1 1 。这次会议按照1 9 9 7 年制定的基本评估标准，从安 全性、成本、算法实现特性等方面对5 个最后候选算法 l 习( m a r s ，r c 6 ， s e r p e n t t w o f i s hr i j n d a e l ) 进行了进一步地分析与评估。 m a r s 算法是i b m 公司提供的一个候选算法，它的特点是充分使用非平衡的 f e i s t e l 网络。为了保证加密和解密的强度相当，m a r s 由结构类似的2 部分组成。m a r s 的加密算法由6 部分组成：密钥加；不受密钥控制的8 轮前期混合运算；密 钥控制下的8 轮前期加密变换；密钥控制下的8 轮后期加密变换；不受密钥控 制的8 轮后期混合运算；密钥减。从现有的分析结果来看，m a r s 对现有的密码分 析方法是免疫的，其缺陷是有弱密钥，且速度相对较慢。 r c 6 算法是在r c 5 算法的基础上设计的。众所周知，r c 5 是一个非常简洁的算 法，它的特点是大量使用数据依赖循环。r c 6 继承了这些优点。为了满足n i s t 的 要求，即分组长度为1 2 8 b i t ，r c 6 使用了4 个寄存器，并加进3 2 b i t 的整数乘法， 即二次函数b ( 2 b + 1 ) ( 相应为d ( 2 d + 1 ) ) ，用于加强扩散特性。关于r c 6 的分 析结果可归纳如下： f 1 ) 对r c 6 的最好攻击似乎是穷举搜索用户的密钥。 ( 2 ) 对r c 6 进行差分和线性密码分析，所需的数据超过现有的数据。值得注意 的是，由于使用了3 2 b i t 的整数乘法，r c 6 的速度可能受到影响。 s e r p e n t 算法是a n d e r s o n ，b i h a r n 和k u n d s e n 提交的一个候选算法。它采用的是代 替置换网络。在s e r p e n t 的最初版本中，使用了d e s 的s 盒，目的是使公众相信设计 者没有设置任何陷门。对于s e r p e n t 有类似的保证，这是因为s 2 盒以简单的、确定 的方式生成。s e r p e n t 的加密算法由3 部分组成：初始置换；3 2 轮的加密操作， 每一轮包含密钥混合运算、s 2 盒及线性变换：末尾置换。 t w o f i s h 算法是美国的b r u c es c h n e i e r 等人提交的一个候选算法。它的总体结构 是一个1 6 轮的f e i s t e l 结构，主要特点是s 2 盒由密钥控制。t w o f i s h 的加密分3 部分： 第1 部分是初始变换；第2 部分是1 6 轮的加密；第3 部分是末尾变换。关于t w o f i s h 的分 析结果，公丌的最佳攻击是用2 2 2 5 个选择明文和2 5 l 的计算量攻破5 轮t w o f i s h 。 在第三次a e s 会议上，尽管并未完全达成一致，但与会者认为，鼬i n d a e l 按时 间测试原理设计简单，在各种测试环境下总体性能良好。而且，其安全强度指标 经过各种算法分析与密码攻击证实可以说是相当高的，惟一不足的是加密轮数还 需提高，以保证更好的安全性f 注：算法在不同的密钥长度下采用不同的加密轮 数) 。在这次会议上一般都认为r i j n d a e l 会最终胜出。 表2 25 种候选算法的比较 加船算法提交单位h - 人) 主要日争睦宴现复杂性 碰安垒飘窿尚 蓉藉牛成懊 骼端a 宴验蜜安垒强度低 赫鐾蔑一般 j o d i - m m t 辫瑟激良葵赣歪装一般 瑙口女吐 j a 啤t & 删 慧眷工她，粼计与 慧件性能差 密卓日毕虚船 玉陆b 剿岫警强g 鸸与鹱珈睦 毖赣睾狲 2 1 2 a e s - r i j n d a e l 算法思想与特点评述 n i s t 于2 0 0 0 年1 0 月2 日宣布选择剐n d a e l 作为a e s 的惟一算法r q n d a e l 算法是比 利时p r o t o nw o r l di n t e r n a t i o n a l 的j o a n d a e m e n 博士和天主教大学电子工程系的 v i n c e n t r i j m e n 博士后提交的一种候选算法。鼬i n d a e l 汇聚了高安全、高性能、高 效率、易用和灵活等优点。它是一个迭代分组密码算法，其分组长度和密钥长度 都是可变的，但为了满足a e s 的要求分组长度为1 2 8 b i t ，密钥长度为1 2 8 1 9 2 2 5 6 b i t ，相应的轮数为1 0 1 2 1 4 。相比较而言，a e s 的1 2 8 b i t 密钥l e d e s 的5 6 b i t 密钥多1 02 1 倍。该算法的原形是s q u a r e 算法，它的设计策略是宽轨迹策略( w i d et r a i l s t r a t e g y ) 。宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给 出算法的最佳差分特征的概率以及最佳线性逼近的偏差的界。由此，可以分析算 法抗击差分密码分析及线性密码分析的能力。r i j n d a e l 采用的是代替置换网络。 每一轮由3 层组成：线性混合层，确保多轮之上的高度扩散；非线性层，由1 6 个s 盒并置而成，起到混淆的作用；密钥加层，子密钥简单地异或到中间状态上。 s 盒选取的是有限域g f ( 2 8 ) 中的乘法逆运算，它的差分均匀性和线性偏差都达到了 最佳。 2 2 r i j n d a e l 算法原理 r d n d a e l 是一个迭代分组密码，其分组长度可以为1 2 8 、1 9 6 、2 5 6 比特，密 钥长度也可以独立的指定为1 2 8 、1 9 6 、2 5 6 比特。当分组和密钥取不同长度时， 算法迭代的圈数也有所不同。r j j n d a e l 算法的中间结果被称作状态，各个不同的 变换都是在状态上进行运算的。本论文以1 2 8 比特分组、1 2 8 比特密钥为例进行 详细介绍，状态和密钥都是以一个4 x 4 的字节矩阵表示的，如图2 1 ： 两安电予科技大学预上论文：高级数据加密标准a e s 的代数性质研究 a o o 口0 1日0 2 口0 3 【 口i o a i li 口1 2 d 1 3 i l 口。la 2 。 a ：! 啦，i ja 3 0 呜l1a 3 2 | a 3 3 分组矩阵 。七0 2， k l ok l lk 1 2k l3 七2 。如2k 2 3 屯。k也， 密钥矩阵 图2 11 6 、2 4 和3 2 字节的分组矩阵和密钥矩阵 算法迭代次数由分组长度和密钥长度共同决定，如表2 1 所示。每一轮包括4 个基本操作：非线性的字节替换b y t e s u b ，行移位s h i f l r o w ，列混合m i x c o l u m n 和轮密钥加r o u n d k e y a d d i t i o n 。 表2 3r i j n d a e l 算法迭代次数 迭代次数1 2 8 比特分组1 9 2 比特分组2 5 6 比特分组 1 2 8 比特密钥l o1 21 4 1 9 2 比特密钥1 21 21 4 2 5 6 比特密钥 1 41 41 4 我们下面针对1 2 8 比特分组、1 2 8 比特密钥的情况详细介绍这四个操作。 图2 2 给出第一个基本操作示意图：字节替换b y t e s u b 是对状态字节逐一进 行可逆的、具有高度非线性的s 盒运算。s 盒运算由两个独立操作组成：取逆运 算和仿射运算。其中的逆运算是将字节看作域g f ( 2 8 ) 的元素，取其在既约多项式 m ( x ) = x 8 + x 4 + x 3 + x + 1 下的逆；而仿射运算是取逆结果与g f ( 2 ) 上的矩阵m 相 乘然后与向量，相加。 m = 1 = ( 0 1 10 ，0 0 1 1 ) 。 图2 2 是行移位s h i f t r o w 在状态行上的运算：状态的最后3 行循环移位不同 的位移量。第2 行循环移位c l 字节，第3 行循环移位c 2 字节，第4 行循环移位 c 3 字节。位移量c 1 、c 2 和c 3 由分组长度决定，如表2 2 所示。 o o 0 l l l 1 l 0 0 1 1 1，1 o o l 1 l 1 1 0 o l l 1 1 1 o o 0 1 1 l l o o o 1 1 1 l o o o i 1 1 1 o o o l l 1 1 o o o l l l l 厂厂。厂t i 1 ，1 j j ，厂广r t b i l 上j | “ o _ 二正 日 l ! 套蔓! 晕_ _ 图2 2 行移位s h i f l r o w 6 1 0 0g 0 1a 0 2g 0 3 i a i ig 1 2a 1 36 1 0 “d 拦”嘞”哟r“口盯” g 3 3q oa 3 1g 3 2 表2 4 不同分组长度对应的位移量 分组长度 c 1 c 2 4 c 3 1 2 8 比特l23 1 9 2 比特123 2 5 6 比特134 在图2 3 的列混合m i x c o l u m n 中，将状态的列看作g f ( 2 8 ) 域上的多项式， 与固定的多项式c ( x ) = 3 x3 + z 2 + x + 2 进行模x 4 + 1 乘：等效于图中的矩阵乘法。 这个过程实际上是基于纠错码理论的列中字节的线性组合，形成列内高度的扩散 性。 i 瓦 l l 鱼 一墅 a 3 0 。垒l 垒一 d o i 球“ a 2 i d 3 i b o ob o ib 0 26 0 3 - - - b l 。b l 。b x 26 1 ， l 也! k 6 2 ：6 2 3 f b 3 06 3 ，6 3 ：岛。 图2 3 列混合m i x c o l u m n 在行移位s h i f l r o w 和列混合m i x c o l u m n 的共同作用下，在轮之间形成了高 度扩散性。 轮密钥加r o u n d k e y a d d i t i o n 是将轮密钥矩阵与状态进行字节间的简单异或 图2 4 轮密钥加r o u n d k e y a d d i t j o n 图2 5 中的轮密钥是通过轮密钥扩展过程从密码密钥中获得的。轮密钥扩展 叽m 吃 眦m 仑j 吼仑i 昭饥吃m 叭 -。，。l = 广_=_=_=_u 舶加既如 西安电子科技大学硕士论文：高级数据加密标准a e s 的代数性质研究 以字为单位进行处理a 若将原始密钥看作有n 个字一块，记为w o ，w i n 一1 则 随后的 二! 坐】1 块轮密钥字w 时 ，w 4 + ( i h l ) 1 】按如下方法生成：块 v 的首字由前一字左循环一个字节，进行字节替换，结果与前一块的首字、轮常数 异或而成：若密钥长度为2 5 6 比特，则块中的第5 字由其前一个字进行字节替换 的结果与前一块第5 字异或而成；其余所有字均由前一个字与前一块相同位置上 的字异或而成，如图2 5 所示。 卜_ j 共斗毒毒吣- i ： _ 县骑韩呐- 1 + 唇窑钥4 _ + 冒密钳 + |0 + l 叶o r c0 蛔聱s ( r 10 ) _ l 一一一。吉j i 。；+ 0 jl + o b s 1 图2 5 轮密钥扩展过程 其中，b s ( w ) 是将字w 中的4 个字节逐一进行字节替换变换，r 1 ( w ) 是将字 w 中的4 个字节左循环移位1 个字节，轮常数r c o n ( i ) = x ，0 ，0 ， 0 l 。 完整的算法中，第一轮之前有一个初始轮密钥加，最后一轮省去列混合操作， 伪c 语言代码如下： n b = b i t s o f b l o c k 3 2 ； r i j n d a e l e n c r y p t i o n ( 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 ) ； r o u n d k e y a d d i t i o n ( s t a t e ，e x p a n d e d k e y ) ； f o r ( i = 1 ；i n u m b e r o f r o u n d s ；i + + ) b y t e s u b ( s t a t e ) ； s h i f t r o w ( s t a t e ) ； m i x c o l u m n ( s t a t e ) r o u n d k e y a d d i t i o n ( s t a t e ，e x p a n d e d k e y + n b + i ) ； ) b y t e s u b ( s t a t e ) ； s h i f t r o w ( s t a t e ) ； r o u n d k e y a d d i t i o n ( s t a t e ，e x p a n d e d k e y + n b + n u m b e r o f r o u n d s ) ； 筮三童垦i j b 4 坐簋擅堡盐基盟一 旦 ) r i j n d a e l _ d e c r y p t i o n ( 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 ) ； r o u n d k e y a d d i t i o n ( s t a t e ，e x p a n d e d k e y + n b + n u m b e r o f r o u n d s ) f o r ( i = n u m b e r o f r o u n d s 一1 ；o ；i 一) i n v _ s h i f l r o w ( s t a t e ) ； i n v _ b y t e s u b ( s t a t e ) ； i n v _ r o u n d k e y a d d i t i o n ( s t a t e ，e x p a n d e d k e y + n b + i ) = i n v _ m i x c o l u m n ( s t a t e ) i n v _ s h i f l r o w ( s t a t e ) ； i n v b y t e s u b ( s t a t e ) ； i n v r o u n d k e y a d d i t i o n ( s t a t e ，e x p a n d e d k e y ) ； 2 3 r i j n d a e l 算法设计原则 r i j n d a e t 算法的的主要设计思想是宽轨迹策略( w i d e t r a i ls t r a t e g y ) ，是针对差 分分析和线性分析提出的，其最大优势是可以给出算法最佳差分特征的概率及最 佳线性逼近偏差的界。本节研究r i j n d a e l 算法内部结构的设计原则和各种参数的 选取方法 4 , 1 4 , 1 5 】。 2 3 1密钥参数 我们都清楚地看到d e s 的5 6 比特密钥太短了，以今天的计算能力已经能够 对其进行密钥穷尽搜索。因此，随后设计的分组密码一般都使用更长的密钥长度， 这也是a e s 为什么使用1 2 8 、1 9 2 和2 5 6 比特密钥的缘故。实际上，大多数密码 分析者相信8 0 比特密钥长度的分组密码在未来几年内还是足够安全的。表2 3 1 1 3 ，1 5 汇总了n 1 s t 目前认可和计划设置的算法安全强度的估测。 表2 , 5 各类等价强度密码算法的密钥长度 2 两安屯了科技大学颂士论文高级数据加密标准a e s 的代数性质研究 离散对数( 公钥，私钥) 。 r s a 椭例曲线2 8 0s k l p j a c ks h a - 11 0 2 4 1 6 01 0 2 41 6 0 t i l 2t d e s2 0 4 8 2 4 42 0 4 82 2 4 1 2 8a e s 1 2 8s h a - 2 5 63 0 7 2 2 5 63 0 7 22 5 6 1 9 2a e s 1 9 2s h a 3 8 47 6 8 0 3 8 47 6 8 03 8 4 2 5 6a e s 2 5 65 1 21 5 3 6 0 5 1 21 5 3 6 05 1 2 1 包括教牛签名算法d s a 和d i f f i e - h e l l m a n 密钥协商算法； 2 包括椭圆曲线数字签名算法e c - d s a 和椭圆曲线d i f f i e h e l l m a n 密钥协商算法。 如果摩尔定律继续有效，并且传统的密钥穷举方法仍是最佳攻击的话，以现 今8 0 比特的安全度来衡量，1 2 8 比特密钥的a e s 直到2 0 6 6 年都是安全的，而2 5 6 比特密钥的a e s 则会安全好几个世纪。 对r i j n d a e l 算法使用的密钥，r o s sa n d e r s o n 的意见是：原则上应该使用2 5 6 比特长密钥，特别情况下1 9 2 和1 2 8 比特长的密钥应谨慎使用。而r i c h a r d s c h r o e p p e l 认为：只有花销增加不是很大的情况下才使用2 5 6 比特长的密钥。 其理由为：1 ) 出于硬件资源的限制，运行圈数越多( 即存储越多的圈密钥) 则越趋 向于使用尽可能短的密钥：2 ) 一些算法的密钥越长，其运行速度越慢：3 1 对应 于分组密码2 5 6 比特密钥的安全强度，公钥密码的密钥产生时间太长，从而( 利用 公钥密码) 进行密钥交换的时间过长( 如要达到1 2 8 比特安全强度，d i f f i e h e l l m a n 密钥交换算法需要一个3 0 7 2 比特的素数模数，而要对应2 5 6 比特安全强度，则需 要1 5 3 6 0 比特的模数，密钥交换时间将是前者的5 倍。当然，使用椭圆衄线密码， 所需密钥长度只是2 5 6 或5 1 2 比特，但后者仍比前者慢2 倍11 。 许多人习惯性地认为2 5 6 比特密钥的算法比1 2 8 比特算法更安全、更难破译。 然而，如果基于以下假设，我们会发现相反的情况。这个假设是：任何攻击复杂 度小于2 ”1 的攻击，就算是以今天的计算能力未能实施，都可以认为是对密码算 法的一种破译。从这个角度看，由于允许更多的复杂度，破译2 5 6 比特密钥的密 码比破译1 2 8 比特的密码更为容易。例如，有一种方法攻击2 5 6 比特密钥的密码 复杂度为2 ”o ，而攻击1 2 8 比特密钥的密码复杂度为2 ”o 。在这种情况下，虽然攻 击2 5 6 比特密钥的密码比攻击1 2 8 比特密钥的密码更为不现实，并且2 5 6 比特密 钥的密码安全性仍旧更强，但前者可以认为是被破译了，而后者却不能认为是被 破译t t l3 1 。 对轮密钥的产生，密码设计者认为其方案具有如下特点 1 4 j 5 】： 1 能够抵抗已知部分密钥的攻击，即从部分轮密钥比特无法计算出太多 其它轮密钥比特。 2 能够抵抗己知密钥或可选择密钥的攻击( 如密码被用作杂凑算法) 。 3 能够抵抗相关密钥攻击。将密钥差异扩散到轮密钥中去，保证没有两 莹三童型也4 瞳篁鎏塑盐厘型旦 个主密钥产生的轮密钥具有大的重合。 4 使用轮常数消除轮变换内外的对称性。 5 变换可逆：知道一块。个字的子密钥可以产生髂个密钥。 6 能够在多种处理器上快速实现，因为选择的是重量轻、面向字节的方 案。 7 使用中字节替换保证密钥方案足够的非线性性，防止只从密钥的差分 就能完全决定所有的轮密钥差分 8 描述的简单性。 我们认为，由扩展的轮密钥密钥可以导出主密钥；甚至可以由部分扩展密钥 求出另外的一些扩展密钥，这一点是r i j n d a e l 密钥生成方案一个潜在的危险；此 外，其扩散性能并没有象提案中声称的那么好。 此外，在用户输入长度小于算法密钥长度的情况下，还需考虑密钥的填充方 案。通常的做法有：不足部分全部补零；拷贝已输入密钥的一部分或全部；选有 重叠的两部分的异或结果：使用杂凑算法如s h a 进行h a s h 扩展。r i c h a r d s c h r o e p p e l 认为第一种方案的攻击复杂度保持不变，其它方案复杂度有所改变。 我们认为，在知道密钥实际长度和填充方法情况下，四种方案的攻击复杂度都一 样1