（计算机应用技术专业论文）aes密钥扩充算法改进与随机性测试研究.pdf

摘要 摘要 信息本身是用以消除不确定性的，而密码学的首要目是隐藏信息的涵义，并 不是隐藏信息的存在。那么，怎么样让信息变的看起来无意义呢? 随机性可以满 足要求。在现代信息安全系统中，随机数扮演着重要的角色。几乎每一个用到密 码技术的计算机安全系统都要用到随机数。比如：握手协议，会话密钥，r s a 公 开密钥加密算法中密钥的产生等。然而，真正的随机数的获得却非常困难。目前 密码学算法中使用的随机数，更多是使用算法技术产生的，用这种方法随机数称 作伪随机数。对伪随机数来说，要实现其严格数学意义上的随机性，在理论上是 不可能的，在实际应用中也没有这个必要。对大部分使用到随机数的系统，系统 的安全目标实现很大程度依赖于所用到的随机数的随机性，不同的应用领域对随 机数“质量”的要求是不一样的。实际调查表明，大量被强制破译的密钥，一个 最重要的原因就是密钥的随机性不够，从而使攻击者很容易“猜测一或“分析一 出密钥来。本文第一部分在对随机性基本概念进行阐述的基础上，讨论了对随机 性进行判定的一般方法，并以信息安全中广泛应用的随机序列的随机性判定为 例，对上述讨论进行了解释 作为下一代对称密码算法的标准， e s 以其突出的安全性、有效性受到人们 的重视。同时，由于其应用的广泛性和基础性，对其的研究和分析，不可避免的成 为一个熟点。在第二部分对a e s 基本原理的阐述中，重点分析了a e s 的密钥扩展， 以及对原密钥扩展算法的改进，并同采用直接h a s h 方法得到密钥扩展的思路进 行对比，从随机化的角度比较了每种方案的优劣以及产生这些差别的原因。 关键词：随机性；密钥；高级加密算法 a b s t r u e t a b s t r a c t t h ei n f o r m a t i o ni ss o m e t h i n gt h a tu s e dt oe l i m i n a t et h eu n c e r t a i n t y t h ep r i m a r y p u r p o s eo ft h ec r y p t o g r a p h yi st oh i d et h em e a n i n go fi n f o r m a t i o n , n o tt h ee x i s t e n c e o fi n f o r m a t i o n s o ，h o wt oc h a n g em e a n i n gt om e a n i n g l e s s ? r a n d o m n e s sm e e t st h e r e q u i r e m e n t s i nt h em o d e r ni n f o r m a t i o ns e o a i t ys y s t e m ，t h er a n d o mp l a y sa l l i m p o r t a n tr o l e a l m o s ta l ls e c u r i t ys y s t e mr e l a t e dt ot h ec r y p t o g r a p h yw i l lu s er a n d o m n u m b e r f o re x a m p l e ：h a n d s h a k ep r o t o c o l ，s e s s i o nk e y , t h ep r o d u c t i o no fk e yi nr s a a l g o r i t h m h o w e v e r , t h et r u er a n d o mn u m b e ri sv e r yh a r dt oo b t a i n m o s to ft h et h e r a n d o mn u m b e rt h a tu s e di nc r y p t o g r a p h i ca l g o r i t h m sc u r r e n t l yi sg e n e r a t e db y p r o g r a m m i n g t h i sk i n do fm e t h o dc 锄o n l yg a i nn u m b e r sc a l l e dp s e u d o - r a n d o m n u m b e r s o nt h ep s e u d o - r a n d o mn u m b e r s , i ti s i m p o s s i b l et o a c h i e v ei t ss t r i c t m a t h e m a t i c a lr a n d o m n e s si nt h e o r y , a n di t su n n e c e s s a r yi np r a c t i c a la p p l i c a t i o n f o r m o s to ft h er a n d o mn u m b e rs y s t e m ，t h es y s t e m ss e c u r i t yo b j e c t i v e si sd e p e n d e n to n t h er a n d o m n e s so ft h er a n d o mn u m b e r t h eq u a l i t yr e q u i r e m e n to ft h er a n d o m n u m b e ri nv a r i o u sa p p l i c a t i o na r e s si sd i f f e r e n t t h ei n v e s t i g a t i o ns h o w e dt h a ti na l a r g en u m b e ro f t h es e c u r i t ys y s t e m st h a th a sb e e na t t a c k e d , o n eo f t h em o s ti m p o r t a n t r e a s o n si st h a tt h e y 扣屯n o tr a n d o mk e y s , w h i c h 锄屯v e r ye a s yt ob e s p e c u l a t i o n o r 竹a n a l y s i s 计b ya t t a c k e r s o nt h eb a s i cc o n c e p to fr a n d o m n e s s , t h eg e n e r a lm e t h o dt o d e t e r m i n et h er a n d o m n e s si sd i s s c u s s e di nt h i sp a p e r , a n dt a k eo d tt h er a n d o m n e s so f r a n d o ms e q u e n c e si ns e c u r i t yf o re x a m p l e st oe x p l a i nt h ee s t i m a t eo fr a n d o n m e s s a st h en e x tg e n e r a t i o no fs y m m e t r i cc i p h e r a l g o f i t h r as t a n d a r d , a e sa t t r a c t p e o p l e sa t t e n t i o nf o ri t so u t s t a n d i n gs a f e t ya n de f f e c t i v e n e s s a n da tt h e 戤l n l et i m e , t h er e a s e a c ha n dt h ea t t a c k0 1 1a e si sa r o u s e db e c 戤o fi t sw i d e n e s sa n df o u n d a t i o n i np r a c t i a la p p l i c a t i o n i nt h es e c o n dp a r to ft h ea e s sb a s i ct e n e t s ，t h ef o c u si sp u to n i t sk e y e x p a n s i o na n di t si m p r o v e m e n t w i t ht h ec o m p a r i s o nt ot h eb a s hm e t h o dt h a t g e tt h ec i p h e rk e y , w ea n a l y s et h ep r o sa n dc o n so fe a c hp r o g r a m m ef r o mt h e p e r s p e c t i v eo fr a n d o r n n e s s k e yw o r d s ：r a n d o m n e s s ；k e y ；a e s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：秀沪 5 年阳多莎日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 l 、保密() ，在年解密后适用本授权书。 2 、不保密( v 3 ( 请在以上相应括号内打。 ) 作者签名：李刀y 导师签名： 日期：砂僻妇7 自 日期：吵馋妒啦 第一章引言 信息作为一种重要的资源，在社会生产生活中的作用日益显示电脑网络的 建立和延伸，打破了传统的行业地域和发展空问的概念。把地球上的人们罩在一 张密密麻麻的信息大网中，只要你愿意，一根电话线，一台电脑，加上一个小小 的调制解调器，你就可以与这张大网连在一起，既可以让你的信息传到世界的每 也可以坐在家中了解世界的各个角落。然而，事物都具有两重性，计算机同样存 在着安全隐患，它可能给你带来不便，甚至给社会、国家带来巨大的损失。随着 信息技术的发展，由于信息网络国际化、社会化、开放化、个人化特点使它在提 供人们技术共享信息共享的同时，也带来了不安全的阴影。信息社会并不安宁， 网上信息的被泄露、篡改和假冒，黑客入侵、计算机犯罪、计算机病毒传播等， 对网络信息形成重大威胁。信息社会，面临着政治、经济、外交、科技、教育和 意识形态等方面的总体网络斗争。如果信息安全不解决的话。信息社会就不能健 康有序地发展，电子商务、政府上网、网络银行等等，都将无法顺利开展起来。 另一方面，正因为信息是一种重要的战略资源，国际上围绕信息的获取、使 用和控制的斗争愈演愈烈。美国正在利用其信息技术优势，极力推行信息霸权主 义。一方面，向其他国家大肆倾销其信息产品夺取别国财富另一方面，在其出 口的信息系统中植入陷阱和后门，以控制、破坏和截取别国的信息。揭露出来的 奔腾中的序列号就是一例。 1 1 信息安全的概念 信息安全的概念经历了漫长的历史阶段，9 0 年代以来得到了深化，它包括： 1 信息的保密性 保证信息不泄漏给未经授权的人： 2 信息的完整性 防止信息被未经授权的篡改； 3 信息的可用性 保证信息和信息系统确实为授权者所用，防止由于计算机病毒或其它人为因 素造成系统的拒绝服务或者为非法者所用； 4 信息的可控性 a e s 密钥扩充算法改进与随机性测试研究 对信息和信息系统实施安全监控管理，防止非法利用信息和信息系统； 5 信息的不可否认性 保证信息行为人不能过后否认自己的行为； 信息安全涉及面很宽它包括着技术、管理、制度、人员和法律的诸多方面。 仅就技术而言，有防病毒、防电磁泄漏、物理安全防护、系统安全防护、密码保 护等，解决信息安全的基本策略是综合治理。信息安全决不是单靠某一项措施或 某一项技术所能奏效的。 1 2 密码学的研究内容 密码作为最初运用于军事和政治斗争的技术，有着悠久的历史。过去密码的 研制、生产、使用和管理都是在封闭的环境下进行的。七十年代以来，随着计算 机、通信和信息技术的发展。密码领域发生了新的变化，密码应用范围日益扩大， 社会对密码的需求更加迫切，密码研究领域不断拓宽，密码科研也从专用机构走 向社会和民间，密码技术得到了空前发展。 当前，密码学不仅在保护党政领导机关的秘密信息中具有重要的，不可代替 的作用，同时，在保护经济、金融、贸易等系统的信息安全，以及在保护商业领 域，如网上购物、数字银行、收费电视电子钱包的正常运行中也具有重要的应用。 有人以人体来比喻芯片是细胞，计算机是大脑，网络是神经系统，智能是营养， 信息是血液信息，安全是免疫系统。也有人把密码技术看作信息高速公路的保护 神，随着信息和信息技术的发展，电子数据交换逐步成为人们交换的主要形式 密码在信息安全中的应用将会不断拓宽，信息安全对密码的依赖会越来越大。 密码学是保密学的一部分。保密学是研究密码系统或通信安全的科学。密码 学的主要任务是解决信息的保密性和可认证性，即保证信息在生成、传递、处理、 保存的过程中不被未授权者非法提取、窜改、删除、重放和伪造。它包含两个分 支，既密码学( c r y p t o l o g y ) 和密码分析学( c r y p t a n a l y t i c ) 。密码学是对信息 进行编码实现隐蔽信息的一门学问，密码分析学是研究分析破译密码的学问，两 者相互对立，又相互促进。 密码学的使用与研究已经有几千年的历史，但是直到s h a n n o n 于1 9 4 9 年发 表了。保密通信的信息理论 之后，它才真正成为- f 科学。而搿密码学新方向圩 的发表和美国数据加密标准d e s 的颁布实施标志着现代密码学的诞生，并从此 2 第一章引言 揭开了商用、民用密码研究的序幕。此后实用密码体制的研究基本上沿着两个方 向进行，即以r s a 为代表的公开密钥密码体制和以d e s 为代表的秘密密钥分组密 码体制。分组密码具有速度快、易于标准化和和便于软硬件实现等特点，通常是 信息与网络安全中实现数据加密、数字签名、认证及密钥管理的核心体制，它在 计算机通信和信息系统安全领域有着最广泛的应用。 1 3 密码系统概述 一个密码系统的主角一般有三方，即发送方，接收方与攻击方( 密码分析者) ， 典型的密码系统如图卜1 所示。在发送方，首先将明文m 利用加密器e 及加密密 钥k e ，将明文加密成密文c = e ( g ，k e ) 接着将c 利用公开信道送给接收方，接 收方收到密文c 后，利用解密器d 及解密密钥k d ，将c 解密成明文m = d ( c ，k d ) 。 发送方接收方 i 。- ： 公开信道： i 秘文： i 图1 - 1 典型密码系统方框图 一般而言，密码系统依其应用可对信息提供下列功能： 1 秘密性：防止非法的接收者发现明文。 2 鉴别性t 确定信息来源的合法性，也即此信息确实是由发送方所传送， 而非别人伪造。 3 完整性：确定信息没有被有意或无意的更改，及被部分取代、加入或删 除等等。 4 不可否认性：发送方在事后不可否认其传送过的信息 现代密码学系统按密钥形式分为私钥密码系统和公钥密码系统。私钥密码系 3 a e s 密钥扩充算法改进与随机性测试研究 统是收发双方加解密的过程所使用的密钥都相同的密码系统，又叫作对称密码 系统，传统的密码系统都属此类公钥密码系统是指收发双方加解密的过程所 使用的密钥不相同的密码系统，又叫作非对称密码系统。 1 3 1 私钥密码系统概述 1 9 4 9 年s h a n n o n 发表的“保密系统的信息理论”为私钥密码系统建立了理论 基础，从此密码学成为一门科学。私钥密码系统的优点在于密码算法简便，加密 速度快，保密度高；它的最大问题是密钥的分发和管理非常复杂、代价高昂。比 如对于具有n 个用户的网络，需要刀( 刀一1 ) 2 个密钥，在用户群不是很大的情况下， 对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时，密钥 的分配和保存就成了大问题。另外，由于通信双方必须统一密钥，才能发送保密 的信息。如果发信者与收信人是素不相识的，就无法向对方发送秘密信息了 常用的私钥密码算法有以下几种： 1 d e s 算法 d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 是由i b m 公司研制的，美国国家标准局公 布的一种分组对称密码算法。自公布以来，它一直超越国界成为国际上商用保密 通信和计算机通信的最常用的加密算法。d e s 算法使用长度为5 6 比特的密钥加密 长度为6 4 比特的明文，获得长度为6 4 比特的密文。鉴于其密钥长度比较短，随 着硬件的发展，已经不再安全。 2 三重d e s 算法 三重d e s 算法用两个密钥对明文进行三次加密，假设两个密钥是k 1 和k 2 ，加 密步骤如下： 用密钥k l 进行d e s 加密。 用k 2 对步骤 的结果进行d e s 解密。 用步骤 的结果使用密钥k l 进行d e s 加密。 利用三重d e s 相当于密钥长度加倍，安全性增强了，但是带来的问题是，加 密时间是原来的三倍。考虑到加密速度的问题，人们需要一种新的算法。于是， a e s 算法产生。 3 a e s 算法 1 9 9 7 年美国国家标准技术研究所发起了征集a e s ( a d v a n c e de n c r y p t i o n 4 第一章引言 s t a n d a r d ) 算法的活动，目的是为了确立一个非保密的、全球免费使用的分组密 码算法。a e s 的基本要求是比三重d e s 快而且安全级别有所提高，分组长度为1 2 8 比特，密钥长度为1 2 8 1 9 2 2 5 6 比特。a e s 作为d e s 算法的替代者将成为未来数十 年最重要的对称密码算法。2 0 0 1 年夏天，美国国家标准技术协会已经将j o a n d a e m o n 和v i n c e n tr i j m e n 提出的密码算法r i j n d a e l ( 算法名称采用了他们两人姓 的组合) 作为下一代对称密码算法的标准。r i j n d a e l 算法在设计时就考虑到了3 个原则：抵抗已知的密码攻击方法；兼顾速度和代码大小以适应各种平台的需求； 设计思想简单。 1 3 2 公钥密码系统概述 1 9 7 6 年w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 发表了“n e wd i r e c t i o n si n c r y p t o g r a p h y ”这篇划时代的文章，奠定了公钥密码系统的基础。公钥密码系统 是收发双方使用不同密钥的密码系统；又叫作非对称密码系统。该体制的最大特 点就是采用两个密钥将加密和解密能力分开：一个公开作为加密密钥；一个为用 户专用，作为解密密钥，通信双方无需事先交换密钥就可进行保密通信，系统的 保密性完全依赖于用来解密的秘密密钥。而要从公开的公钥或密文分析出明文或 者秘密钥，在计算上是不可行的。从而很好的克服了对称密码体制在实际应用中 遇到的困难，公钥密码体制的概念本身己被公认为密码学上的里程碑，是现代密 码学诞生的标志之一。 二十多年来公钥系统密码发展很快，不断有新的或修改的公钥密码系统提 出，但同时也有很多系统被攻破比较成功的公钥密码系统主要有r s a ，背包， r a b i n ，e i g a m a l ，m c e l i e c e ，椭圆曲线密码体制。目前被认为既安全又实用的公 钥体制根据它们所依据的数学难题可分为五类： ( 1 ) 基于大整数因式分解问题( i f p ) 的公钥密码体制，如：著名的r s a 体制和 r a b i n w i11j a m s 体制； ( 2 ) 基于有限域上离散对数问题( d l p ) 的公钥密码体制，如：d s a 、 d i f f i e - h e l l m a n 密钥交换方案、e i g a m a l 类加密体制和签名方案等： ( 3 ) 基于椭圆曲线离散对数问题( e c d l p ) 的公钥密码体制，如e c c ； ( 4 ) 基于双线性对d i f f i e - h e l l m a n ( b d h p ) 问题。主要包括d b o h e n 和 k f r a n k l i n 的i b e 方案、h e s s 的签名方案等一系列采用双线性对构造的签名方案； 5 a e s 密钥扩充算法改进与随机性测试研究 ( 5 ) 基于g a p 群在此群中d d h p ( d e c i s i o no i f i e - h e l l m a np r o b l e m ) 问题可解， 而c d h p ( c o m p u t a t i o n a ld i f f i e - h e l l m a np r o b l e m ) 问题不可解。包括一系列用 双线性对构造的签名方案。 最后这两个问题是近年椭圆曲线公钥密码发展的结果，而且其快速实现、安 全性以及今后的进一步应用都与椭圆曲线上的运算息息相关。目前应用比较广泛 的公钥密码体制主要为前两类。然而，随着计算机运算速度的迅速提高和网络分 布式计算能力的日益强大，经典如r s a ，d i f f i e - h e l l m a n 等两类的公钥密码体制 在密钥长度为5 1 2 b i t 下己经越来越不安全；在不出现新的密码系统的前提下，唯 一的解决办法只有增加密钥长度，而增加密钥长度虽然能增强安全性，但加、解 密效率会越来越低，根本满足不了现代通信与网络的要求，同时密钥的增长对系 统的要求也越来越高。 1 4 随机性在密码系统中的应用 在目前的信息安全系统研究中，密钥的重要性不言而喻，如果密钥安全性不 能得到保证，整个安全系统就会功亏一篑。密钥是加密作业中最活跃的因素。因 此，从某种意义上说，保密的关键是密钥。它应考虑以下几个方面：密钥种子、 密钥的随机性、密钥的种类和层次、密钥长度、密钥生成算法的复杂度、密钥( 含 密钥生成算法及密钥自身) 保护、密钥的存储、传输、更换和废除以及密钥的管 理方式等。在这其中，密钥的随机性是个不容易测量，容易被忽视的一个因素。 而密钥的随机性，却是密钥安全的一个根本性的关键。随机性作为香农信息理论 的一个重要的思想，在密码学的很多部分得到了体现和应用，可以说是密码学安 全性的基础。实际调查表明，大量被强制破译的密钥，一个最重要的原因就是密 钥的随机性不够，从而使攻击者很容易。猜测 或“分析一出密钥来。 1 4 1 随机数得获取 真随机数数列是不可预计的，因而也不可能重复产生两个相同的真随机数数 列。真随机数只能用某些随机物理过程来产生。例如：放射性衰变、电子设备的 热噪音、宇宙射线的触发时间等等。如果采用随机物理过程来产生蒙特卡洛计算 用的随机数，理论上不存在什么问题。但在实际应用时，要做出速度很快( 例如 每秒产生上百个浮点数) ，而又准确的随机数物理过程产生器是非常困难的。 目前密码学算法中使用的随机数，更多是使用算法技术产生的，而一个确定 6 第一章引言 性的算法，是不可能产生不可预测的随机序列的，这些随机数只能称作伪随机数。 伪随机数有真随机数不具备的许多优点，比如：速度快、代价小、易获取，并且 在解决一些特殊问题时候，伪随机数具有真随机数所不具备的优点。 1 4 2 随机性的判定 然而实际使用的伪随机数产生程序还没有一个是十全十美的，不同的应用领 域对随机数。质量一的要求是不一样的。在使用这些随机数之前，根据具体应用 的安全级别对这些随机数的随机性进行判定是必不可少的。通常我们说一系列数 值是随机的，我们关心的是这些数值在某种明确的统计意义上是随机的。一致性 是指对指定的数值，每个数出现的频率应该近似相等。独立性是按先后顺序出现 的若干个随机数中，每一个数的出现都和它前后的各个数无关。有很多种方法可 以用于评价一个序列的随机性。随机性是一个概率属性，也就是说，随机性可以 用概率来描述。当一个随机测试被用于一些随机序列时，测试的结果不应该有显 著的差异。虽然测试一个随机序列的方法很多，但是每一个都只能评估随机性的 一个方面。 1 5 本文研究目标与内容 本文分为以下二个大的部分： 第一部分首先介绍了a e s 的设计原理，数学基础，整体结构，重点分析了a e s r 1 的密钥扩展及密钥扩展的一般规律，然后针对原密钥扩展算法的一些不足，提 出了一个基于f e s t i e l 结构新的密钥扩展的改进方案，并分析了该改进方案具有 的特点，并用实验数据，对比了改进前后性能方面的提高。 第二部分是对密钥随机性测试的研究。本部分在对随机性基本概念进行阐述 的基础上，首先讨论了对随机性进行判定的一般方法和指标，然后以信息安全中 随机序列中几个常用的随机性判定方法为例，对上述讨论进行了解释和实例分 析，并给出判定结果。最后，以几种通用的加密算法中的随机数产生的实现为例， 分析了其中随机密钥的产生机制和实用效果。并通过和其他密钥扩展方案特别是 直接用哈希函数进行密钥扩展的对比，分析了各自的安全及性能等特征最后通 过随机化一组主密钥后扩展得到一组随机化序列，然后用随机性测试对这些扩展 后的密钥序列进行了考察，给出并分析了一组基础数据，帮助我们从随机性的角 度认识和分析密钥生成。 7 第二章高级加密标准的设计原理及结构 2 1 高级加密标准的产生历史 1 9 7 3 年美国标准局征求国家密码标准方案，i b m 提出的方案是当时提出的最 好的算法，因而在当年被选为非保密数据( 与国家安全无关的信息) 加密，这个 算法在国际上得到了广泛的使用，一个最基本的例子就是它在银行现金安全传输 方面的使用。在1 9 9 9 年，n i s t 发行了它的标准的新版本( f i p sp u b4 6 - 3 ) ，并且 指出d e s 只在遗留系统中使用，三d e s 系统( 即对明文重复使用d e s 算法三次， 使用两个或者三个不同的密钥来产生密文) 将被使用。1 9 9 7 年1 月，n i s t 开始寻 找的替代算法，总体目标是开发新的f i p s ，指明在下个世纪用于保护敏感( 非保 密) 政府信息的加密算法，新算法将由美国政府使用，并且在自愿的基础上也可 以由私有部门使用。 征集要求规定必须明确为非保密的，公开的加密算法，并且在世界范围内通 用。另外，算法必须作为分组算法实现对称密钥密码，且至少支持1 2 8 比特的分组 大小和1 2 8 ，1 9 2 和2 5 6 比特长度的密钥大小。通过对1 5 个候选算法的评估，决定 选择r i j n d a e l 作为高级加密标准，在2 0 0 1 年1 1 月a e s 作为f i p s l 9 7 出版，今天 已经成为数字设施中至关重要的组成部分。 2 2 分组加密算法的实现原理 2 2 1分组加解密算法基本原理 分组加解密算法实际上就是利用密钥将明文做混淆( c o n f u s i o n ) 与打散 ( d i f f u s i o n ) 的动作而得到一组密文。对于这种算法，最简单的方式就是的建 立一个表格，对于不同的明文、不同的密钥列出相对应的密文，假设明文为p ， 密钥为k ，则我们可依据表格找出对应密文c 。若明文的长度为n 1 、密钥的长 度为n 2 ，则可知这个表格的长度为2 1 + 2 ，使用这种方法确实可以达到区块加 解密算法的要求，但是所需要储存的容量太大。我们希望尽可能设计一个区块加 解密算法用最短的密钥长度、最少的内存、最快的速度，却可得到相当的安全度 为了要达成上述目标，区块加解密算法设计的目的就是将安全性较弱的函数，重 复很多次，以达到较高的安全性，每一次称为一个轮( r o u n d ) 。在此，所谓的安 8 第二章高级加密标准的设计原理及结构 全性较弱是相对于上述例子的安全度，但仍然要对函数的输入做相当程度的混淆 与打散。以下，我们将介绍区块加解密算法设计的基本原理：混淆、打散、雪崩 效应与r o u n d 。 1 混淆 混淆的目的是在隐藏明文、密钥与密文之问的关系。由l i n e a ra t t a c k 与 d i f f e r e n t i a la t t a c k 我们知道无论函数中输入、密钥、密文之间的关系有多么 微乎其微，只要能找出其间的微小关系，就有破解的可能。所以一个良好的混淆 就是无论用多复杂的统计，都很难找出三者之间的一种转换关系。 很多区块加解密算法所用到的s - b o x 目的就是做混淆8 1 ，此外，例如r c 6 所采用的d a t ad e p e n d e n tr o t a t i o n 与c a s t 一2 5 6 所做的k e yd e p e n d e n t r o t a t i o n 也是一种混淆的动作。 2 打散 打散的目的是希望能让明文的某一位或密钥的某一位尽可能影响密文的其 它部分。最简单的打散就是做排列( p e r m u t a t i o n ) ，此外s a f e r + 所提出的 p h t ( p s e u d oh a d a m a r dt r a n s f o r m ) 也是一种更有效的打散方法，一个具有良好 打散的区块加解密算法将可以很容易达成f a s ta v a l a n c h ec r i t e r i a 的目标。 3 雪崩效应 每一个i n p u t 明文位必须要能够影响每一个o u t p u t 密文位，而且利用越少 的r o u n d 达到愈好。一般是利用p e r m u t a t i o n 将一个位的影响力扩大到每一个 b y t e ，再利用s - b o x 影响这个b y t e 内的每一个位。 4 r o u n d 由理论及实务上的一般攻击法可知，一个区块加解密算法r o u n d 的个数越 多将会越安全，但r o u n d 的个数将会影响到算法的速度，如何取得一个使得算 法安全却又适合的r o u n d 的个数必须由分析才可得知 2 2 2 分组加解密算法设计架构 区块算法的架构有 f e i s t e ln e t w o r k 及 s pn e t w o r k ( s u b s t i t u t i o n p e r m u a t i o nn e t w o r k ) 两种，分述如下。 1 f e is t e ln e t w o r k f e i s t e ln e t w o r k 的架构于1 9 7 3 年在h o r s tf e i s t e l 所设计的l u c i f e r 加 9 a e s 密钥扩充算法改进与随机性测试研究 解密算法中提出，至今已广泛的运用在大多数加解密算法的设计原则之中，包含 d e s 、f e a l 、g o s t 、l o k i 、c a s t - 1 2 8 等知名的加解密算法，都是采用这个架构。 在f e i s t e ln e t w o r k 最基本的架构中( 如下错误l 未找到引用源。) ，每一个输 入的区块( 长度n ) 被分为左右两个区块( 长度n 2 ) ，在每一个r o u n d 中，右 边的区块为下一个r o u n d 的左区块，而右边的区块经由一个由金钥值所控制且 非线性的函数f 运算后，其输出与左区块做e x c l u s i v e o r 所得到的值为下一 个r o u n d 的右边区块。也就是说 l i + i = r i r i + i = l io f ( r i ( b k i ) 其中 函数f 是任一个与k e y 相关的对应，通常为非线性的，其定义如下： f ： 0 ，i n 2 x 0 ，l n 专f 0 ，1 n 2 n 为区块的长度，n 为所输入k e y 的长度。 图2 1 f e i s t e ln e t w o r k 的基本架构 f e i s t e ln e t w o r k 的优点是不论函数f 是什么形式，每一个r o u n d 都是可 逆的( r e v e r s i b l e ) 。这是因为以下式子恒成立： l 10 f ( r 1 0 k i ) o f ( r 1 0 k i ) = l i 所以区块( 长度为n ) 经过一个r o u n d 所得到的两个区块( 长度为n 2 ) 左右 位置对调后，再重新做为r o u n d 的输入即可得到和原来相同的区块。这样的优 点使得采用f e i s t e ln e t w o r k 架构的加解密算法有着加密与解密可使用同一套 1 0 算法的好处，这种加解密相同性( “e n c r y p t i o n d e c r y p t i o ns i m i l a r i t y 一) 的 优点，使得一个加解密算法在硬件的实现上可以加密与解密使用同一个组件，此 便利性对于算法的推广是很有帮助的。 采用f e i s t e ln e t w o r k 的另一样优点是，设计者不需花费心思在函数的可逆 性( r e v e r s i b i l i t y ) 。因为不管f 函数如何设计，只要采用f e i s t e ln e t w o r k 的 架构，算法就具有可逆性。这个优点使得设计者可以专心在函数f 的设计之上。 函数f 是f e i s t e ln e t w o r k 加解密算法的核心，较安全的( 可以抵挡已知攻击 法) 的函数f 会使得加解密算法较安全。函数f 在算法中主要是扮演“混淆 ( c o n f u s i o n ) 的动作，目的是要把k e y 、函数输入、函数输出之间的关系隐藏。 此外还有一部份的“打散一( d i f f u s i o n ) 目的。 f e i s t e ln e t w o r k 也有相对应的缺点，由于每个r o u n d 只有一半的数据被 改变，所以打散( d i f f u s i o n ) 的速度较慢。在最传统的f e i s t e ln e t w o r k 中， 两个r o u n d 称为一个周期( c y c l e ) ，因为要经过两个r o u n d 之后所有的数据才 会被改变，在更多区块的f e i s t e ln e t w o r k 加解密算法，甚至要三个或四个 r o u n d 才能改变所有数据，所以f e i s t e ln e t w o r k 加解密算法需要较多的 r o u n d 个数才能达成相同的安全性，这种缺点也使得f e i s t e ln e t w o r k 的加解 密算法很难达到f a c ( f a s ta v a l a n c h ec r i t e r i a ) 2 s pn e t w o r k s pn e t w o r k 的架构如下图表2 - 2 所示，由s u b s t i t u t i o nl a y e r 达成混乱 ( c o n f u s i o n ) 的功能，由p e r m u t a t i o nl a y e r 达成打散( d i f f u s i o n ) 的功能。 s u b s t i t u t i o nl a y e r 隐藏k e y 、输入、输出之间的关系，与f e i s t e ln e t w o r k 的 函数f 不同的是，s u b s t i t u t i o nl a y e r 的函数必须具有可逆性( r e v e r s i b l e ) 这是因为s pn e t w o r k 的架构并没有f e i s t e ln e t w o r k 可逆的特性，所以函数 并不能任意选取。 p e r m u t a t i o nl a y e r 的功能是做打散( d i f f u s i o n ) ，也就是将算法明文的位 所能影响密文的范围尽可能的扩散。s a f e rf a m i l y 以线性转换函数( 1 i n e a r t r a n s f o r m a t i o nf u n c t i o n ) 取代原有的p e r m u t a t i o n ，使得打散( d i f f u s i o n ) 的程度更为快速，称为l i n e a r - t r a n s f o r m a t i o nn e t w o r k 。已知p e r m u t a t i o n 是li n e a rt r a n s f o r m a ti o n 的一种，所以li n e a r - t r a n s f o r m a ti o nn e t w o r k 可 以说是s pn e t w o r k 的衍生。 a e s 密钥扩充算法改进与随机性测试研究 以s pn e t w o r k 为基础的加解密算法使得设计者不用局限于f e i s t e l n e t w o r k 的一定架构，提供架构设计上较大的弹性。此外，s pn e t w o r k 加解密 算法所能达成的打散( d i f f u s i o n ) 速度较f e i s t e ln e t w o r k 加解密算法快，所 以所需要r o u n d 的个数较少，速度亦较快，再者，s pn e t w o r k 的安全度分析也 比较容易。 以s pn e t w o r k 为基础加解密算法的缺点已由前述可知，对于每一个加密所 用到的函数都必须去找到相对应的反函数以做为解密之用，这使得s pn e t w o r k 加解密算法在函数取得上无法如同f e i s t e ln e t w o r k 的函数f 般的自由。再者， 由于加密所用的函数与解密所用的函数不尽相同( 互为反函数) ，所以加密与解 密不能使用同一种算法，也就是说，并不具有加解密相同性 ( “e n c r y p t i o n d e c r y p t i o ns i m i l a r i t y 一) 的特性，在实际硬件的实作上需要 两种组件。 2 2 3 分组加解密算法中的核心函数 核心函数是加解密算法中提供安全性的部份，一个核心函数的强度关系到加 解密算法的强度。核心函数主要的工作是做混淆( c o n f u s i o n ) ，也就是在每一个 r o u n d 中，隐藏输入、密钥、输出的关系。所以，这个函数大多是非线性函数 ( n o n l i n e a rf u n c t i o n ) ，否则输入、密钥、输出之间最少会具有一定线性关系。 在f e i s t e ln e t w o r k 中，这个函数就是所谓的f 一函数，大多为不可逆，而在s p 1 2 第二章高级加密标准的设计原理及结构 n e t w o r k 中，由于架构上的考虑，这个函数必须是可逆的有些核心函数也做到 打散( d i f f u s i o n ) 的功能，例如在d e s 加解密算法f 一函数中的p - p e r m u t a t i o n 即是。 2 3 高级加密标准设计原理及结构 a e s 的具体实现分为信息加密部分和密钥扩展部分两个独立的模块羽在这 之前，我们首先介绍一下a e s 的数学基础。 2 3 1a e s 的数学基础 ，1r，o、，1z：，o、 a e s 的数学基础建立在w uj 之上，有多种构造u ru j 的方法，但应用最多 的是选用g f ( 2 ) 的一个n 次既约多项式p ( x ) 扩展一个g f ( 2 。、这个g f ( 2 。) 是模 p ( x ) 的全体余式的集合，即： g f ( 2 4 ) = 口卜i j 一+ a m _ 2 x 2 + + 口l x + a o ，其中口，g f ( 2 ) ) 基于多项式基的域运算定义如下：设任意的f ( x ) 和g ( x ) g f ( 2 “， 按照模加厂( 曲+ g ( 功= u ( 功+ g ( 砌烈，； 按照模乘( 曲g ( z ) = ( 厂( 曲。g ( 功) 烈j ； 具体地，设 厂( x ) = x 一+ 工柚+ + 口l x + a o ，g ( 力= 瓦一i 工一+ 一+ + t 、x + b o ， 则：厂( 力+ g ( 曲= 0 - - i + 屯一i h 一+ ( 口2 + 饥2 h “一2 + + 【口i + 包h + ( 口。+ ) 其 中的+ 号为g f ( 2 ) 上的加法，即模2 加o 则：，( 对g ( 砖= q l x 1 + c 一- 2 x 。- 2 + + c x + c o ，其中c ( x ) 是f ( x ) g ( x ) 被 p ( x ) 除所得的余式。 加法运算的单位元素是( 0 0 o ) ，f ( x ) 的加法逆元素是f ( x ) 本身，乘法运算 的单位元素是( 0 0 1 ) f ( x ) 的乘法逆元素为，u ( 工) ) 一，其中 f c x ) ( 厂( 功) 叫= 1 m o d p ( x ) 。其中，选用不同的模多项式p ( 】【) ，取模运算的效率 是不同的，p ( x ) 的项数越少，取模运算的效率越高。在a e s o p ( x ) = x 8 + x 4 + x 3 + x + 1 或x 4 + x + 1 1