对称密钥密码算法研究

./河南科技大学毕业设计〔论文题目＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿姓名＿＿＿＿＿＿＿＿院〔系＿＿＿＿＿＿＿＿专业＿＿＿＿＿＿＿＿指导教师＿＿＿＿＿＿＿＿年月日毕业设计〔论文任务书填表时间：2008年12研究所〔教研室主任签字：年月日.对称密钥密码算法研究摘要对称密码是现代密码学中的一个重要分支,其诞生和发展有着广泛的使用背景和重要的理论价值。目前这一领域还有许多理论和实际问题有待继续研究和完善。这些问题包括：如何设计可证明安全的密码算法；如何加强现有算法及其工作模式的安全性；如何测试密码算法的安全性；如何设计安全的密码组件,例如S-盒、扩散层及密钥扩展算法等。目前分组密码所采用的整体结构可分为Feistel结构〔如CAST-256、DEAL、DFC、E2等、SP网络〔如Safer＋、Serpent等及其他密码结构〔例如Frog和HPC。Feistel结构最大的优点是容易保证加解密的相似性；SP网络则是扩散性能比较好。AES沿袭了SQUARE的特点采用了SP网络结构,并在加解密过程大量使用矩阵运算,这样做使得加密和解密过程略有不同,但大幅提高了算法实现的效率。虽然AES的设计在分组密码系统的发展上有了一个质的飞跃,然而目前仍有研究和改进的空间。AES在多种平台上实现的效率有待进一步提高,同时新的加解密工作模式也有待研究。本论文简单介绍了对称密码学的部分基本知识和AES算法的工作过程,根据AES算法大量矩阵运算的的特点,改进了传统的加解密速度,给出了其在时间上的优化：该算法的时间优化能够提高AES算法的加解密速度。关键词：对称加密算法,DES,Rijndael,有限域TheResearchOfSymmetricKeyCipherAlgorithmABSTRACTSymmetricalcryptosystemisanimportantbranchofmoderncryptography,withitsappearanceanddevelopmenttherearewideapplicantbackgroundandtheorialvalue.Therearelottheorialandapplicantproblemsneedtobestudiedandoptimized,suchas:howtodesignaprovablesafecryptosystem,howtostrengthenthesaftyofalgorithmsandworkingmoduleswhicharealreadyavailable,howtotestthesaftyofacipheralgorithm,howtodesignsafecomponentsofacryptosystem,asS-boxes,diffusinglayers,andkey-expandingprocesses,etc.ThegeneralarchitectureofsymmetricalcryptosystematpresentcanbesortedasFeistel<CAST-256,DEAL,DFCE2,etc.>,SPnetwork<Safer＋,Serpent,etc.>andotherarchitectures<Frog,HPC>.SymmetryisthemostdistinctcharacterofFeistel,whileSPnetworkhasagooddeffusecapability.AESinheritedSQUAREindesignation,andaddedinalotofmatrixoperations.Thiscausesabitdifferentbetweenencryptionanddecryption,butitoptimizestheefficiencyofthealgorism.AESisarapidprogressincryptosystemdevelopment,however,itneedstobeamelioratedyet.TheefficiencyofAESmaybeboosted,andnewworkingmoduleisalsonecessarytobedeveloped.ThispaperintrouducesthetheoryofsemmetricalcryptographyandtheworkingprocessofAESalgorithm,improvesaconventionalmeansofincreasingtheencryptingspeed,proposesitsoptimizedalgorism,whichcangreatelyincreasetheencryptingspeed。KEYWORDS:symmetricalcryptography,DES,Rijndael,finitefield目录TOC\o"1-4"\h\z\u摘要IABSTRACTII第1章引言1§1.1概述1§1.2课题的研究现状及发展趋势2§1.3分组密码的定义4第2章DES加密方法6§2.1DES算法基本原理7§2.2DES算法的f函数处理9§2.3子密钥的生成12§2.4DES安全性问题14§2.5IDEA分组密码15第3章AES加密算法16§3.1AES发展史16§高加密标准的制定过程16§3.1.2AES的评估及中选17§3.2AES算法的数学基础18§3.3AES算法的设计原理21§3.3.1安全性原则22§3.3.2实现性原则23§3.4AES算法的整体结构23§3.4.1迭代密码算法的结构分类24§Feistel网络结构24替换/置换<SP>网络结构25§AES算法的结构25§加、解密的输入输出26§3.4.3AES算法的步骤28§3.4.4AES算法描述30§字节代换〔SubBytes30§行移变换〔ShiftRows31§列混合变换〔MixColumns32§密钥扩展〔ExpandedKey34第4章AES的快速实现37§4.1Rijndael算法的实现方案37§4.1.1实现考虑37§4.1.2实现方案及其分析38§4.2各模块的算法描述及其分析39§4.2.1计算轮函数的T表39§4.2.2轮函数的C语言实现40§4.3加密性能测试42§4.3.1测试环境及开发平台42§4.3.2测试方法43§4.3.3测试结果44总结45参考文献46致50.引言§1.1概述密码学是学的一部分,学是研究密码系统或通信安全的科学。密码学的主要任务是解决信息的性和可认证性,即保证信息在生成、传递、处理和保存的过程中不被未授权者非法提取、篡改、删除、重放和伪造。它包含两个分支,即密码学<cryptology>和密码分析学<cryptanalytic>。密码学是对信息进行编码实现隐蔽信息的一门学问,密码分析学是研究分析破译密码的学问。两者相互对立又相互促进。密码学的使用与研究已经有几千年的历史,但是直到Shannon于1949年发表了"通信的信息理论"[1]之后,它才真正成为一门科学。而"密码学新方向"[2]的发表和美国数据加密标准DES的颁布实施标志着现代密码学的诞生,并从此揭开了商用民用密码研究的序幕。此后,实用密码体制的研究基本上沿着两个方向进行,即以RSA为代表的公开密钥密码体制和以DES为代表的秘密密钥分组密码体制。分组密码具有速度快、易于标准化和便于软硬件实现等特点,通常是信息与网络安全中实现数据加密、数字签名、认证及密钥管理的核心体制,它在计算机通信和信息系统安全领域有着最广泛的应用。对称算法<symmetricalgorithm>,有时又称传统密码算法,就是加密密钥能够从解密密钥中推算出来,同时解密密钥也可以从加密密钥中推算出来。而在大多数的对称算法中,加密密钥和解密密钥是相同的。所以也称这种加密算法为秘密密钥算法或单密钥算法。它要求发送方和接收方在安全通信之前,商定一个密钥。对称算法的安全性依赖于密钥,泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密,所以密钥的性对通信性至关重要。对称加密的优点在于算法实现的效率高、速度快。对称加密的缺点在于:第一,密钥量问题。在单钥密码系统中,每一对通信者就需要一对密钥,当用户增加时,必然会带来密钥量的成倍增长,因此在网络通信中,大量密钥的产生、存放和分配将是一个难以解决的问题。第二,密钥分发问题。单钥密码系统中,加密的安全性完全依赖于对密钥的保护,但是由于通信双方使用的是相同的密钥,人们又不得不相互交流密钥,所以为了保证安全,人们必须使用一些另外的安全信道来分发密钥,例如用专门的信使来传送密钥。这种做法的代价是相当大的,甚至可以说是非常不现实的,尤其在计算机网络环境下,人们使用网络传送加密的文件,却需要另外的安全信道来分发密钥,显而易见,这需要新的解决方法。§1.2课题的研究现状及发展趋势分组密码[3-12]的研究始于20世纪70年代中期,至今已有近30年的历史,这期间人们在这一研究领域已经取得了丰硕的成果。分组密码的研究大体上包括三个方面：分组密码的设计原理、分组密码的安全性分析和分组密码的统计性能测试。分组密码的设计与分析是两个既相互对立又相互依存的研究方向,正是由于这种对立促进了分组密码的飞速发展。早期的研究基本上围绕DES<DataEncryptionStandard>进行,进入20世纪90年代后,人们对DES类密码的研究更加深入,特别是差分密码分析[13-14]和线性密码分析[15-16]的提出,迫使人们不得不研究新的密码结构。IDEA密码的出现打破了DES类密码的垄断局面,IDEA密码的设计思想是混合使用来自不同代数群中的运算。随后出现的Sqare、Shark和Rijndael[17-18]都采用了结构非常清晰的代替-置换<SP>网络[19-24],每一轮由混淆层和扩散层组成。这种结构的最大优点是能够从理论上给出最大差分特征概率和最佳线性逼近优势的界,也就是说密码对差分密码分析和线性密码分析是可证明安全的。1997年4月,AES的征集掀起了分组密码研究的新高潮,15个AES候选算法[25-29]反映了当时分组密码的设计水平,可以说是近几年研究成果的一个汇总。目前分组密码所采用的整体结构可分为Feistel结构、SPN结构及其它密码结构。Feistel结构由于DES的公布而广为人知,已被许多分组密码所采用。Feistel结构的最大优点是容易保证加解密相似,这一点在实现中尤其重要。而SPN结构比较难做到这一点,但是SPN结构的扩散特性比较好。在现有的分组密码中,所用的基本运算有异或、加、减、查表、乘及数据依赖循环等。S盒是分组密码中唯一的非线性部件,由于S盒需要一些存储器,所以其规模不能太大。15个AES候选算法所采用的S盒规模有6种,分别是4×4、8×8、8×32、11×8、13×8及8×32。S盒又称黑盒子,它常给人们造成故意设置陷门的嫌疑,因此,Rijndeal、Safer+等选取公开的数学函数来避免嫌疑。S盒的设计与分析是分组密码设计中的重要环节,它的好坏直接影响密码体制的安全性。目前,对S盒的设计并没有一个完备的标准,但总的希望是增强S盒的非线性度、差分均匀度及其分量函数的代数次数和项数。2003年2月27日,欧洲签名、完整性和加密新标准计划NESSIE[30]<NewEuropeanSchemesforSignatures,IntegrityandEncryption>宣布了第二阶段的终选算法。自此,密码学界继AES之后又一场为期三年的旨在面向全球围进行公开征集,通过透明、公开的测试评估,制定一整套高效密码标准<包括分组密码、流密码、哈希函数、消息认证码函数、数据签名方案和公钥加密方案等>的具有深远意义的活动计划尘埃落定。NESSIE经过四次国际会议的热烈的讨论、分析和评估,最,从48个算法中选出了24个标准算法。其中,分组密码加密标准共有四个算法——MISTY1<64比特>、AES<128比特>、Camellia<128比特>[31]和SHACAL-2<256比特>算法。目前对分组密码安全性的讨论主要包括强力攻击、差分密码分析和线性密码分析等。从理论上讲,差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法,而实际上,强力攻击是攻击分组密码最可靠的方法。到目前为止,已有大量文献讨论各种分组密码的安全性,同时推出了譬如差分-非线性密码分析[32]、截断差分-线性分析[33]、高阶差分密码分析[34]及插值攻击[35]等多种分析方法。自从AES候选算法公布以后,国外许多专家学者都致力于候选算法的安全性分析,推出了一些新的攻击方法,这无疑将进一步推动分组密码的发展。目前在分组密码的设计与分析方面还有许多理论和实际问题亟待继续研究和完善,这些问题主要包括[10]：<1>算法部件方面,对多输出布尔函数的各种性质进行探索,如何对各种性质进行折衷而增强S盒的实质安全性等。<2>算法结构方面,设计出的算法如果能证明能抵抗某种攻击,算法则不会太复杂,有可能存在别的分析方法；但是算法过于复杂又不利于设计者本身分析其密码性质。如何折衷也是值得考虑的问题。<3>算法分析方面,除了从差分分析和线性分析发展起来的各种分析方法外,针对算法的整体结构,密钥扩展算法等方面的分析方法也不断出现,因此各个部分的设计准则也相应的在不断更新。§1.3分组密码的定义根据被加密明文的处理方式不同,单钥密码体制通常可分为秘密密钥分组密码体制<简称分组密码>和秘密密钥流密码体制<简称流密码>。分组密码<Blockcipher>是将明文消息编码表示后的数字序列划分成长为n的组x=<x0,x1,...,xn-1>,各组长为n的矢量分别在密钥k=<k0,k1,...,kn-1>的控制下变换成输出数字序列y=<y0,y1,...,ym-1><长为m的矢量>,如图1所示。图2.1-1分组密码简化框图通常的分组密码算法明文与密文的长度相等,这表明加密和解密的结构一样,便于简单的实现。若n>m,则为有数据扩展的分组密码,易增加密文解密的难度；若n<m,则为有数据压缩的分组密码；若n=m,则为无数据压缩和扩展的分组密码。密钥长度r在加密过程往往是一个变数,目的是为了增加混乱和扩展性。一般地,对应密钥长度r,则有密钥量为2r。考虑GF<2>上共有2n、个不同置换,必须保证2r2n！。当然,r还不能太大,否则密钥难管理；但也不能太小,因为难以抵抗穷举搜索的攻击。DES加密方法美国国家标准局年开始研究除国防部外的其它部门的计算机系统的数据加密标准,于1973年先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的,主要为以下四点:提供高质量的数据保护,防止数据未经授权的泄露和未被察觉的修改；具有相当高的复杂性,使得破译的开销超过可能获得的利益,同时又要便于理解和掌握；DES密码体制的安全性应该不依赖于算法的,其安全性仅以加密密钥的为基础；实现经济,运行有效,并且适用于多种完全不同的应用。1977年1月,美国政府颁布：采纳IBM公司设计的方案作为非数据的正式数据加密标准即<DES即DataEncryptionStandard>。它是由IBM公司研制的一种对称加密算法,属于分组加密算法。美国国家标准局于1977年公布把它作为非机要部门使用的数据加密标准,三十年来,它一直活跃在国际通信的舞台上,扮演了十分重要的角色。DES是一个分组加密算法<即将数据分块>,它用56位的密钥以64位分组对数据加密。同时DES也是一个对称加密算法,它的密匙长度是56位<添加个奇偶校验位后成64位,但有效位仍然是56位>,密匙可以是任意的56位的数,而且可以任意时候改变。其中有极少量的数被认为是弱密匙<即很容易破解>,但是很容易避开他们"所以性依赖于密钥。DES的寿命还不到20年时,就已被数次攻破而被认为不安全了,其中最著名的两个攻击是差分密码分析和线性密码分析。但DES的设计至今仍闪烁着人类设计思想的精华,其结构和部件仍在被后人效仿。DES的轮函数采用Feistel网络,8个s盒,扩充－压缩置换,块置换。其算法简洁快速且加解密相似,但一个明显的缺陷是s盒的设计原则一直没有公开,因此公众长久地抱怨并怀疑它设有陷门。早期的迭代分组密码设计主要围绕DES进行,后来在此基础上有很大发展,出现了众多的Feistel型密码,如:LOKI,FEAL,GOST,Lucifer等。§2.1DES算法基本原理DES是分组长度为64比特,密钥长56比特的分组密码算法。明文的长度与加密得出的密码的长度一样,没有数据压缩和扩展。DES的算法完全公开,完全依赖于密钥。图2.1-1[36]是DES算法的全部16轮结构图,输入<input>可以是明文也可以是密文,视使用者进行的是加密或是解密操作。加密和解密的唯一不同在于图右边的16个轮子密钥Ki,1i16的使用顺序正好相反,加密为K1,K2,...,K16,解密为K16,K15,...,K1。子密钥由密钥扩展算法生成。图2.1-1DES加密算法16轮迭代过程DES算法对输入的64位明文进行一个初始置换IP<INITIALPERMUTATION,如图2.1-2>,以打乱原来的比特次序。把置换后的数据分成各32位的左右两部分,左边记为L0,右边记为R0。对R0进行轮密钥控制下的变换f,其结果记为f<Ro,K1>,得到的结果再与L0进行逐位异或<XOR>运算,结果作为下一轮数据的右半部的32比特R1。而R0作为下一轮数据的左半部的32比特L1。对L1和R1实行同样的过程得L2和R2。这样一个过程称为轮加密,或轮迭代。如此进行16次轮迭代,最后得到L16和R16。最后再对<R16L16>实施初始置换的逆置换IP-1轮运算可以简洁地表示如下：Ri=Li-1⊕f<Ri-1,Kl>Li=Ri-1,i=1,2,...16初始置换及其逆置换是确定的,所以其在密码学上并没有意义。在DES之后的一些密码就改进了这一点。图2.1-2初始换位IP图2.1-2逆初始换位IP-1§2.2DES算法的f函数处理DES迭代过程的核心问题是非线性f函数的功能,它是每轮实现加密混乱和扩散的主要途径。其基本的思想如图2.2-1所示。图2.2-1第i次f函数处理示意图每一轮迭代过程的密码函数f<Ri-1,ki><1i16>都必须经过三个子过程<扩展置换、S盒替换<压缩>、P盒排列>处理得到。函数f是将32bit的输入转化为32bit的输出,中间参与运算的结果为48为,加密函数f的计算如图2.2-2所示。图2.2-2加密函数f的计算过程扩展置换扩展置换简称E函数<Expand>,功能是把32位扩展成48位,是一个与密钥无关的纯移位变换,结构示意图如图2.2-3所示。扩展置换按32bit输入,分8组,每组4位,经E函数扩展后变成每组6位输出。若令ai<l><1i4,18>为选择组对应的每位输入,bj<><1i4,18>为选择组扩展的每位输入,则有扩展公式为：其中组排列具有循环性,即当=1时,b1<1>=a4<8>；=8时,b6<8>=a1<1>。扩展置换的全部形式如表2.2-1所示。扩展结果与子密钥Ki<1i16>进行异或运算,结果作为S盒的输入。表2.2-1扩展置换E函数图2.2-3扩展置换示意图<2>压缩替换<S盒选择>压缩替换是通过8个S盒<替换盒SubstitutionBox>的正确选取将48位属入变换为32输出。第i个S盒是一个6比特输入4比特输出的变换,变换的规则是取{0,1,…,15}上的4个置换,即它的4个排列排成4行,得到4*16矩阵。设S盒的输入是b0b1b2b3b4b5,输出对应矩阵中b0b5行b1b2b3b4列中的元素。8个S盒的结构可由表2.2-2表示。表2.2-2S盒选择表0123456789101112131415S10123140415121511213714814821214134152691113218111731015510612116129312117145931095100035678013S201231530131131488471014711161510311241538134414129125117086211271310612126900935511214105159S301231013131076109041314990638634159156385100712114138115125214714123111251141110521514281712S401237131031386151411903506061210615111907131031381415927148235512141111151212102741482159414S501232144111211284211211211774101107131411137261813851565091531512015105913361009341480596143S6012312109411514310415215251297292128569121585310067111310143134141410714016711130531181181613S701234131611041121111131471381541210934817101310147314109123155956071281552014101552689316212S801231317221511181341448176109415312101171481421310120159561236109141113050153014351295672811P盒排列P盒排列也是一种置换<Permutation>,将压缩替换得到的32位结果重新按图2.2-4的顺序排列,得到变换后的32位,即为密码函数f<Ri-1,Ki>输出。图2.2-4P排列§2.3子密钥的生成在DES算法中,每一轮迭代运算都是用一个子密钥,子密钥本身是从用户输入的密钥来产生的,图2.3-1给出了子密钥产生的流程图。K是长度为64位的比特串,其中的56位是密钥,8位是奇偶校验位,分布在8,16,24,32,40,48,56,64,比特位置上,目的是用来检错,可在8位组中检查单个错误,实际上,在密钥编排的计算中用56位,不包括这8位。子密钥生成的大致过程分为：置换选择1<pc-1>、循环左移、置换选择2等变换,分别产生16个子密钥。置换选择1<pc-1>对56位密钥输入按表2.3-1进行重新编排。将前28位作为C,后28位作为D。即C0=K57K49K41...K52K44K36D0=K63K55K47...K20K12K4图2.3-1子密钥产生流程表2.3-1PC-157494133251791585042342618102595143252719113605244366355473931231576254463830221466153453719211352820124循环左移计算对16轮的计算模型描述如下：LSi表示循环左移一个或两个位置,它取决于i值变化的次数,当i=1,2,9,16时,则左移一个位置,其余左移两个位置,如表2.3-2所示。表5-3迭代次数12345678910111213141516左移位数1122222212222221比如,对应不同次数,左移变化情况如下：i=1,C1=c1c2...c27c28,D1=d1d2i=2,C2=c2c3...c28c1,D1=d2d3...d28i=3,C3=c4c5...c28c1c2c3,D1=d4d5...d28以此类推。<3>选择置换2<pc-2>其作用是删除每次移位后C中第9、18、22、25位和D中第7、9、15、26比特位,其余比特按表2.3-3置换后从出48位比特,作为第i次迭代的子密钥ki使用。表2.3-3PC-21417112415328156211023191242681672720132415231374755304051453348444939563453464250362932§2.4DES安全性问题DES的密钥空间为256,使用硬件解码速度相当快。在1997年,人们估计建成一台每秒钟检测一百万个密钥的专用机用于DES的解密要耗资两千万美元,而且需要12个小时的破解才能得到结果,所以当时被认为是一种十分强壮的加密方法。其问世年来,成为密码界研究的重点,经受住了许多科学家的研究和破译,是一种世界公认的较好的加密算法,在POS、ATM、磁卡及智能卡<IC卡>、加油站、高速公路收费站等民用密码领域有着广泛的应用。应用围包括：计算机网络通信中的数据保护、电子资金传送系统中的信息加密、保护用户文件、用户识别等,为全球贸易、金融等非官方部门提供了可靠的通信安全保障。但是,当今的计算机速度越来越快,1997年,制造一台用于DES解密的专用机的费用降到十万美元左右,破解时间为6小时。而在21世纪的今天破译成本更低,DES已经不再安全。因此,56位的密钥显然影响了它的强度。针对DES算法密钥短的问题,密码学家又研制了80位的密钥,以及在DES的基础上采用三重DES和双密钥加密的方法。双密钥方法用两个56位的密钥k1、k2对明文进行三次加密,发送方用k1加密,k2解密,再使用k1加密。接收方则使用k1解密,k2加密,再使用k1解密,其效果相当于将密钥长度加倍,缺点是要花费原来三倍时间[37]。目前,三重DES的112位密钥长度被认为是很"强壮"的加密方式。此外,由于DES算法完全公开,其安全性完全依赖于对密钥的保护,必须有可靠的信道来分发密钥<如采用信使递送密钥等>,不适合在网络环境下单独使用。§2.5IDEA分组密码对DES的成功破译迫使人们重新设计密码算法。IDEA[38]是第一个不采用Feistel网络的密码。IDEA的安全性设计思想是:采用同一明文空间上的三个不同的群运算,使掩蔽,混淆和扩散溶为一体。IDEA是分组密码的杰出代表,开创了新的一类设计风格。AES加密算法§3.1AES发展史§高加密标准的制定过程最初阶段,1997年1月,美国国家标准和技术研究所<NIST>发布公告征集新的加密标准,即AES。新的加密标准将取代旧的数据加密标准<DES>和三重DES而成为一个<美国>联邦信息处理标准<FIPS>。与DES、安全散列算法<SHA-1>和数字签名算法<DSA>的选择过程不同。NIST宣布AES的选择过程将是公开的,任何人都可以提交候选密码算法,任何符合要求的提案都将被仔细考虑,NIST本身不进行任何的安全或效率评估,而是邀请密码学界攻击候选算法并进行密码分析,并且任何感兴趣的人都可以评估候选算法的实现代价。所有的结果都可以作为公开评论发给NIST,并在NIST的AES发布,或者也可以提交AES会议进行述。NIST只是收集这些评沦。将其作为评选AES的依据,并在评估报告中促进它们被选择。FIPS标准的官方围非常有限,它只适用于美国联邦行政部门。然而新的AES将仅仅用于保护包含敏感但非的信息的文档,然而AES预期的影响将远远不止这些：由丁AES是DES的继承者,它自从被接纳为标准之日起就已经被银行业、行政部门和工业界作为事实上的密码标准。Rijndael被正式批准为政府标准的事实赋予了它一个官方的"质量证书"。目前,AES己经提交国际标准化组织<ISO>和因特网工程任务组<IETF>,同时电子和电气工程师协会<IEEE>也正在考虑接纳其作为标准。甚至在Rijndael成为AES之前,己经有多家组织和公司声明接纳Rijndael。欧洲电信标准协会<ETSI>在其MILENAGE算法集中集成了Rijndael模块,而且有多家密码库提供商也早已在它们的产品中包含了Rijndael。Rijndael被迅速接受的原因主要在于其可免费获得,而且能够在不明显降低带宽的前提下易于在大量的平台上实现。§3.1.2AES的评估及中选DES因其密钥仅有56位等原因而存在被破译的可能,后来出现了三重DES,但三重DES又因加密速度太慢而不能满足人们的需要,这就要求提出安全性更好、加密速度较快的新的数据加密标准。1997年1月2日,美国国家标准技术研究所<NIST>发起了征集AES<AdvancedEncryptionStandard>算法的活动,并专门成立了工作组。目的就是开发一个联邦信息处理标准<FIPS>来提出一个能保护下一世纪政府敏感信息的算法。1997年9月12日正式提出了征集AES的公告。并指出：AES候选算法必须是一个非保护的、公开的、全球免费使用的安全算法,并且也是一个能支持分组长为的对称密钥的分组算法,其密钥长可以是128/192/256bit。1998年8月20日,NIST召开第一次AES候选会议,宣布了满足候选要求的15个候选算法,并在会议上和出版的FederalRegister杂志上对这些算法进行公开的评论。1999年3月22日召开了第二次AES候选会议,公开了对第一阶段的15个候选算法的分析和测试结果,并从中选择5个候选算法,分别是IBM公司提出的MARS算法,RSA公司提出的RC6算法,JoanDaemen和VincentRinmen提出的Rijndael助算法,RossAnderson、EliBiham和LarsKnudsen提出的Serpent算法以及由BruceSchneier、JohnKelsey、DougWhiting、DavidWagner、ChrisHall和NielsFerguson提出的Twofish算法。20XX11月从中选取Rijndael算法作为下一代密码算法AES[39-40]在AES候选算法的评估过程中,AES工作组考虑所有的评论、论文、NIST研究和报告,提出了如下的评判准则[41].安全性。这是评估中最重要的因素,包括：算法抗密码分析的强度,稳定的数学基础,算法输出的随机性以及与其他候选算法比较的相对安全性。<2>代价。这是评估中的第二重要的因素[42],主要包括：应具有高执行效率和低存储需求的有点；而且各运算部件具有良好的统计特性,并行执行度高；加、解密速度快,不需要繁琐的乘法运算。<3>算法的实现特性[43]。它包括：灵活性,硬件和软件的适应性,算法的简单性。其中灵活性应包括：处理的密钥和分组长度必须超出最小支持围；在许多不同类型的环境中能够安全和有效地实现；可以作为序列密码、杂凑算法实现,并且提供附加的密码服务。2001年2月28日,NIST发布FIPS草案供公众讨论。2001年11月2日NIST发布正式文本FIPS1971,2002年3月26日FIPS197正式生效。至此,AES的征集工作结束,21世纪高级加密标准宣告诞生了。§3.2AES算法的数学基础在有限域[44]GF<28>上的元素可以用几种方法来表示,Rijndael算法中,为了方便的执行,选择传统的多项式表示法,而其中的许多运算都是按字节定义的,用字节表示有限域GF<28>中的元素,其他的运算是按4字节的方式定义的。有限域GF<28>假设一个字节b由b7b6b5b4b3b2b1b0组成,我们可以把这些bi想象成一个7次多项式的系数,而这些系数不是0就是1：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如,<57>16的二进制表示法为<01010111>2表示成多项式,则为：x6+x4+x2+x+1<1>加法运算两个多项式的加法,则定义为相同指数项的系数和再模余2,简单的说就是作异或运算。例如：<57>16+<83>16=<01010111>2+<10000011>2=<11010100>2=<D4>16如果以多项式表示,则为：<x6+x4＋x2+x+1>+<x7+x+1>=x7+x6＋x4+x2显而易见,在这种加法运算上的多项式集合组成一个交换群,它们满足封闭性,结合性,零元<00>,逆元<每一个元素逆元是其本身>和交换性,因为元素的逆元是其本身,因此加法和减法运算是相同的。<2>乘法运算在乘法里而,多项式相乘之后的结果很容易造成溢位的问题,解决溢位的方式是把相乘的结果,再模余一个可解的多项式m<x>。在Rijndael中,定义这样的多项式为：m<x>＝x8+x4+x3+x+1或是<11B>16例如：<57>16×<83>16=<x6+x4+x2+x+1>×<x7+x+1>=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=<x13+x11+x9+x8+x6+x5+x4+x3+x+1>mod<x8+x4+x3+x+1>=x7+x6+1=<C1>16显而易见,模的结果是一个低于8价的多项式,与加法不同的是,乘法并不是在字节上的简单运算。按照上述方式定义的乘法运算具有封闭性、结合性、零元<01>。另外,对于任何低于8阶的二进制多项式b<x><00除外>,存在多项式a<x>和c<x>,使得下式成立：B<x>a<x>+m<x>c<x>=1<3.2-1>由欧几里德扩展算法可计算得到a<x>和c<x>,因此有b<x>a<x>modm<x>=1<3.2-2>b-1<x>=a<x>modm<x><3.2-3>由此,我们可以获得b<x>的逆元。<3>乘数为x的相乘运算若把b<x>乘以x,得到：b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x相乘的结果再与m<x>相模后的结果有如下规律：若b7＝0,则<b<x>·x>modm<x>=b<x>·x若b7＝1,则<b<x>·x>modm<x>=<b<x>·x>⊕m<x>因此,<b<x>·x>modm<x>可以被认为是先进行字节的左移操作,根据移位结果对该字节与"1B"<m<x>>进行条件异或运算。这种类型的操作表示为：b=xtime<a>例如：'57'·'13'='FE''57'·'02'=xtime<57>='AE''57'·'04'=xtime<AE>='47''57'·'08'=xtime<47>='8E''57'·'10'=xtime<8E>='07''57'·'10''='57'·<'01'⊕'02'⊕'10'>='57'⊕'AE'⊕'07'='FE'这样,通过分解可将复杂的相乘操作转化为简单的移位和异或操作。2.域GF<28>上带有系数的多项式在域GF<28>上可以定义带有系数的多项式,在该方式的定义下,一个4字节的向量对应一个阶数小于4的多项式。<1>加法运算两个带有系数的多项式之和等于相应系数之和的多项式,在GF<28>上的和运算等于异或运算。<2>乘法运算带有系数的多项式相乘与不带系数的多项式相乘相比,稍为复杂一些,设在GF<28>上有两个多项式：a<x>=a3x3+a2x2+a1x+a0b<x>=b3x3+b2x2+b1x+b0c<x>=a<x>b<x>=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0将a<x>b<x>的结果展开,再与c<x>的多项式相对照,可得：c0=a0b0c1=a1b0⊕a0b1c2=a2b0⊕a1b1⊕a0b2c3=a3b0⊕a2b1⊕a1b2⊕a0b3<3.2-4>c4=a3b1⊕a2b2⊕a0b3c5=a3b2⊕a2b3c6=a3b3再将c<x>模上一个4阶多项式m<x>,得到了一个低于4阶的多项式,在Rijndael算法中,m<x>=x4+1,则d<x>=c<x>modm<x>=d3x3+d2x2+d1x+d0<3.2-5>由ximod<x4+1>和<3.2-5>式可得c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0c4x4mod<x4+1>=<a3b1⊕a2b2⊕a0b3>x4mod<x4+1>=a3b1⊕a2b2⊕a0b3c5x5mod<x4+1>=<a3b2⊕a2b3>x5mod<x4+1>=<a3b2⊕a2b3>xc6x6mod<x4+1>=a3b3x2<3.2-6>由<3.2-4>、<3.2-5>、<3.2-6>式得d0=a0b0⊕a3b1⊕a2b2⊕a1b3d1=a1b1⊕a0b1⊕a3b2⊕a2b3<3.2-7>d2=a2b0⊕a1b1⊕a0b2⊕a3b3d3=a3b0⊕a2b1⊕a1b2⊕a0b3用矩阵表示为：<3.2-8><3>乘数为x的相乘运算如果b<x>与x相乘,得：b3x4+b2x3+b1x2+b0x将结果与x4+1相乘后,得：c<x>=b2x3+b1x2+b0x+b3如果将c<x>再与x相乘后模上x4+1得d<x>=b1x3+b0x2+b3x+b2将b<x>、c<x>、d<x>的系数相比较,容易得到以下结论,即每乘上一次x的运算结果,相当于多项式系数的一次左移操作。§3.3AES算法的设计原理AES算法是当前密码算法设计最高水平的反映,设计者在进行算法设计时主要考虑了以下三点：<1>要能抵抗所有已知的攻击方式。<2>在各平台上具有良好的性能,如较快的速度、编码要紧凑等。<3>设计要简单。第一点强调的是安全性原则,而后两点强调的是实现性原则,这是AES算法所遵循的两个重要的原则。AES算法在整体结构上采用的是替代/置换<SP>网络的迭代结构方式,在安全性方面能抵抗各种攻击。下面就分别从这两个方面对AES算法的设计原理进行说明。§安全性原则针对某一特定的分组密码算法,其攻击的方法可分为通用攻击方法和专用攻击方法。所谓通用攻击方法就是对所有的分组加密算法攻击都有效的方法,而专用攻击方法只针对某特定的算法有效,一般与具体密码算法的某种特定的结构有关。设计现代实用密码算法时,为了能有效地抵抗通用攻击,一般遵循仙农<Shannon>提出的混淆<Confusion>原则和扩散<Diffusion>原则。同时,混淆和扩散也是分组密码算法的设计理论中保证明文能够可靠、隐蔽的最基本技术[45]。所谓混淆性原则是指所设计的密码应使密文对密钥和明文的依赖关系相当复杂,以至于这种依赖性对于密码分析者来说是无法利用的。混淆用于掩盖明文、密文和密钥之间的关系。这可以挫败通过研究密文以获取冗余度和统计模式的企图。做到这一点最容易的方法是通过代替,一,简单的代替密码,如单字母密码,其中每一个确定的明文字符被一个密文字符所代替。现代的代替密码更复杂：一个长的明文分组被代替成一个不同的密文分组,并且代替的机制随明文或者密钥中的每一位发生变化。好的混淆可以使这种统计关系变得复杂以致强有力的密码分析工具都不能有效。所谓扩散性原则是指所设计的密码应使得密钥的每一位数字能影响密文的许多位数字,以防止对密钥进行逐段破译,同时明文的每一位数字也能影响密文的许多位数字,以便隐藏明文的数字统计特性。扩散通过将明文冗余度分担到密文中使之分散开来,把单个明文位和密钥位的影响尽可能扩大到更多的密文中去。密码分析者寻求这些冗余度将会更难。产生扩散最简单的办法是换位<也称为置换>。为了能抵抗专用攻击,则需要对算法的自身结构进行分析,消除其中的不安全因素。AES算法在设计时,设计者通过轮函数的多轮迭代,为抵抗通用攻击提供了必要的混淆和扩散,同时这种多轮迭代的方法也消除了AES算法面向字节处理的不安全因素,有效地抵抗了对算法的专用攻击。§实现性原则一个好的密码算法要求设计简单,结构合理,易于用软件或硬件实现,也就是说密码具有良好的实现性[45]。一个密码算法若要用软件实现,则尽量使密码算法针对某一特定的长度进行,子块的长度应尽可能地适应软件编程,如采用8位、16位、32位的子块,这是因为在软件实现中,单个比特之间的置换是难于实现的,除了使用子块外,密码算法应采用一些易于软件实现的运算,如标准处理器能直接处理的加、减、乘、移位运算等。密码算法若要用硬件实现,那么要求密码算法的结构尽可能地紧凑,轮变换尽可能地一致,这样就便于用ASIC或FPGA实现；同时在设计时,使加密和解密过程尽可能地相似,这样就可以用一个功能模块同时实现加密和解密。§3.4AES算法的整体结构分组加密算法是由一种叫做轮变换的函数通过多次迭代构成的,轮变换的构成包括非线性层,扩散层和密钥调度等元素。这些设计是基于仙农提出的设计原则：非线性替代与线性混合函数交替进行。这样结合的结果导致来自密码的重要的统计特性是高度相关的和敏感的类型,即通过混合变换的扩散和混淆产生充分的混合,使加密后的分组统计特性分布更均匀。§迭代密码算法的结构分类为了符合安全性和实现性原则,现代实用分组密码算法一般采用了轮函数多次迭代的结构,也称为迭代密码算法。尽管所有的迭代密码算法在采用迭代方式上是一致的,但具体密码算法的整体结构却不尽相同。分组迭代密码的整体结构大致有三类:Feistel网络结构,如DES,CAST-256,DEAL等；替代/置换<SP>网络结构,如square,safer+,serpent等；除了这两种结构以外的算法归为第三类[45]。最近几年SP结构应用比较广泛。其中Feistel网络结构和SP网络结构如图2-1所示：<a>Feistel网络结构<b>SP网络结构图-1分组迭代密码的两种结构§.1Feistel网络结构Feistel网络结构是HorstFeistel在设计Lucifer分组密码时发明的,并由于IED的广泛使用而流行,对一个分组密码长度为2n的r轮Feistel型密码,其中一轮的加密过程如图2-1<a>所示[45]。图中的⊕表示两个长度为n的比特串的异或,F表示迭代密码的轮函数,Ki表示第i轮子密钥,Li、Ri表示第i轮输入同时也是第i-1轮输出的前n位和后n位,其中1ir。对图2-1<a>中每一轮变换有：Li=Ri-1Ri=Li-1⊕F<Ri-1,ki>由此可知,Feistel型算法必须经过两轮变换才能改变输入的每一位,这就说明了采用这种网络结构的密码算法扩散似乎就有点慢,但Feistel型的密码算法加密和解密相似,所以具有良好的实现性能。图2-1<a>的网络结构左边和右边的比特串长度是相同的,所以称这种网络结构为平衡的Feistel网络结构,近年又出现了左右两边比特串长度不等的Feistel网络结构,称为非平衡Feistel网络结构。§.2替换/置换<SP>网络结构SP网络结构是近几年来应用比较广泛的一种结构,这种网络的结构非常清晰,每一轮由非线性层S层和线性层P层组成,SP型密码的一轮加密过程如图2-1<P>所示[45]。SP型密码的每一轮变换中,首先将S层作用于轮输入使其混淆,然后经过P层作用使之得到扩散,图2-1<b>中的子密钥放在S层,在实际实现中子密钥可放在其他位置。SP型密码具有一个很大的优点,就是当给定S层和P层的密码指标后,可以从理论上给出抵抗差分密码攻击和线性攻击的能力,除此之外,经一轮变换后,轮输入的每一位均得到了扩散,从这个角度来看,SP型密码比Feistel型密码能更快的扩散。§.3AES算法的结构AES算法的结构紧凑、规整,加密和解密过程相似,算法结构属于SP结构,组成其每一轮轮变换的4个函数分别属于S层、P层和密钥加层[46]。S层是由字节代换函数<SubBytes>组成,该函数的作用主要是确保多轮迭代后结果的高度混淆,所以也称为非线性层。P层由行移函数<ShiftRows>和列混合函数<MixColoumns>组成,这两个函数的主要作用是确保多轮迭代后的高度扩散,所以又称为线性层。密钥加层由密钥加法函数<AddRoundkey>组成,该层主要起到子密钥的控制作用,即实现了密钥与明文的结合。许多密码分析方法对迭代密码的第一轮和最后一轮与中间的轮的分析方法不同,一般根据假定的密钥值和明文、密文进行运算来剥去迭代密码的首轮和末轮,为此,AES算法对第一轮和最后一轮进行了特殊的处理：第一轮之前加了一个密钥控制下的前期变换；而最后一轮则去掉了其中的列混合运算。因此,AES算法在总体结构上采用了第一轮和最后一轮特殊对待的SP结构。§加、解密的输入输出AES算法的输入输出可以看作是以字节为单位的一维数组[46]。对加密来说,其输入是一个明文分组和一个初始密钥,输出是一个密文分组。对解密而言,输入是一个密文分组和一个初始密钥,而输出是一个明文分组。AES算法的轮变换及其每一步均作用在中间结果上,我们将中间结果称为状态。状态是可以形象地表示为一个矩阵的字节数组,该状态矩阵共有4行。状态矩阵中的列数记为Nb,它等于数据分组长度的比特数除以32。将明文分组记为p0p1p2p3…p4Nb-1其中,p0表示明文分组的第一个字节,p4Nb-1表示明文分组的最后一个字节。类似地,将密文分组记为c0c1c2将状态记为si,j,0i<4,0j<Nb这里,si,j表示位于状态矩阵第i行第j列的字节。输入的字节依次映射到状态字节s0,0,s1,0,s2,0,s3,0,s0,1,s1,1,s2,1,s3,1,……上。当加密时,输入是一个明文分组,映射是si,j=pi+4j,0i<4,0j<Nb当Nb=4时,明文-状态矩阵的映射如表-1所示：表-1明文-状态矩阵的映射状态矩阵-SP0P4P0P12P1P5P9P13P2P6P10P14P3P7P11P15类似地,当解密时,输入是一个密文分组,映射是si,j=ci+4j,0i<4,0j<Nb当加密结束时,密文分组以相同的顺序从状态矩阵中取出,即ci=simod4,i/4,0i<4Nb当解密结束时,明文分组以相同的顺序从状态矩阵中取出,即pi=simod4,i/4,0i<4Nb类似地,初始密钥被映射到两维密钥矩阵上。密钥矩阵可以形象地表示为一个与状态矩阵类似的矩阵,该矩阵数组也有4行。密钥矩阵的列数记为Nk,它等于初始密钥长度的比特数除以32。当Nk=6时,初始密钥-密钥矩阵的映射如表-1所示：表-1初始密钥-密钥矩阵的映射密钥矩阵K0K4K8K12K16K20K1K5K9K13K17K21KK6K10K14K18K22K3K7K11K15K19K23AES加密解密时数据块操作的处理过程：现将a0,a1,a2,a3,a4,...,a15复制到状态数组；加密解密过程都对这个状态进行技术处理；等加密解密过程处理结束,再将状态组复制到b0,b1,b2,b3,b4,...,b15。最后得到ASE加密解密的输出结果。操作映射过程如图-1所示：输入数据中间结果<状态>输入数据图-1操作映射过程§3.4.3AES算法的步骤AES算法是一种迭代分组密码,采用的是代替/置换网络<SP>。它是对一个128比特的数据块进行加、解密操作。作为高级加密标准的Rijndael算法,其数据分组长度和初始密钥长度都是可变的,但为了满足AES的要求,将分组长度固定为128比特,密钥长度为128/192/256比特,相应的轮数为10/12/14轮。进行AES加、解密运算时,首先将输入的128比特数据排成4×4的字节矩阵,然后根据不同的密钥长度,进行10<128比特密钥>,12<192比特密钥>或14<256比特密钥>轮的运算。轮的数目由密钥长度决定,其关系如表-1所示：表-1加密轮数-密钥长度关系表AES密钥长度<Nk>分组大小<Nb>轮的数目<Nr>AES-1284<128/32>4<128/32>10AES-1926<192/32>4<128/32>12AES-2568<256/32>4<128/32>14AES加密算法的实现包括密钥扩展过程和加密过程。以密钥长度为128比特为例,加密过程包括一个作为初始轮的初始密钥加法<AddRoundKey>,接着进行9次轮变换<Round>,最后再使用一个轮变换<FinalRound>,如图-1所示：图-1加密全过程<密钥长度为128比特>其中,每个轮变换<Round>由4层组成：第一层<字节代换-SubBytes>为非线性层,是将一个输入为8比特输出也为8比特的S盒作用于状态矩阵中的每一个字节；第二层<行移变换-ShiftRows>和第三层<列混合变换-MixColumns>是线性层,是将4×4的状态矩阵按行移位,按列混合；第四层<密钥加法-AddRoundKey>为密钥加层,是将轮密钥的每个字节和状态矩阵中相应位置的字节进行异或。每一轮的流程如图-2所示：图-2每一轮的结构图-3AES算法加、解密过程<128比特密钥>其中,FinalRound包含除MixColumns这一步以外的其他3个步骤。AES解密算法的实现包括密钥扩展过程和解密过程。解密过程与加密过程类似,是加密过程的逆运算。以数据分组大小为128比特,初始密钥长度为128比特为例的AES算法加、解密过程如图-3所示：§3.4.4AES算法描述§.1字节代换〔SubBytes每个字节都可以表示成一个8×1的列向量,SubBytes就是通过S-盒独立地作用在每个字节上的非线性变换[46]。该变换由两个子变换构成：a.对每个字节求其在有限域G<28>上的乘法逆。注意,元素{00}的映射为其本身。b.对每个字节做有限域G<28>上的仿射变换。仿射变换f定义如表达式〔3.4-1所示〔注意：a0,a1,a2,a3,a4,a5,a6,a7就是状态中每个字节乘法逆元的比特表示：假设该步的输入的字节为a,输出的字节为b,通过字节代换变换后的结果可表示为b=SRD<a>=f<g<a>>。其中,g<a>表示字节在有限域G<28>上求乘法逆的变换；f<a>表示字节在有限域G<28>上的仿射变换。状态矩阵经过SubBytes变换作用后,其效果如图-1所示：图-1字节代换示意图SubBytes变换是可逆的,在AES解密过程中所用到的字节代换的逆变换InvSubBytes的运算如下：对状态矩阵的每一字节元素,先进行有限域G<28>上的逆仿射变换,然后计算其在有限域G<28>上的乘法逆。§.2行移变换〔ShiftRowsShiftRows是线性变换,它和列混合运算相互影响,在多轮变换后,使密码信息达到充分的扩散。行移变换是在状态矩阵的每个行间进行的,是状态矩阵中的行按照不同的偏移量进行循环左移运算,第0行循环左移C0字节,第1行循环左移C1字节,第2行循环左移C2字节,第3行循环左移C3字节,从而使第i行第j列的字节移到位置第i行第〔j-CimodNb列[46]。移动偏移量C0,C1,C2,C3依赖于Nb的取值,如表-1所示：表-1偏移量-分组大小关系表分组大小〔NbC0C1C2C34012350123601237012480134ShiftRows变换对状态矩阵的影响如图-2所示：图-2行移变换示意图在AES解密过程中所用到的ShiftRows的逆变换称为InvShiftRows,是状态矩阵中的行按照不同的偏移量进行循环右移运算,第0行循环右移C0字节,第1行循环右移C1字节,第2行循环右移C2字节,第3行循环右移C3字节,从而使第i行第j列的字节移到位置第i行第〔j+CimodNb列。移动偏移量C0,C1,C2,C3依赖于Nb的取值〔同ShiftRows中的C0,C1,C2,C3。§.3列混合变换〔MixColumnsMixColumns是对状态矩阵中的列做线性变换,进行四字节乘运算。具体定义如下：将状态矩阵的列看作有限域G<28>上的多项式,并在模x4+1下与一个给定的多项式c<x>相乘,其中c<x>=03x3+01x2+01x+02。假设该步变换状态的一列输入为a,输出为b,即b<x>=c<x>a<x>mod<x4+1>,利用在有限域G<28>上的算术特性的代换,其表达式如表达式<3.4-2>所示[46]：MixColumns变换对状态矩阵的影响如图-3所示：图-3列混合变换示意图在AES解密过程中所用到的MixColumns的逆变换称为InvMixColumns,它与MixColumns类似,是状态矩阵中的每一列在模x4+1下与多项d<x>=0Bx3+0Dx2+09x+0E相乘。假设该步变换状态的一列输入位a,输出为b,如表达式<3.4-3>所示：§.4密钥加法<AddRoundKey>AddRoundKey是将轮密钥的各字节和状态矩阵中相应位置的字节分别模2加,实现状态和密钥的混合[3]。轮密钥的长度和状态的长度是一样的。该步骤的逆变换是其自身。AddRoundKey变换对状态矩阵的影响如图-4所示<W表示经过密钥扩展后的密钥矩阵：图-4密钥加法示意图轮密钥是由初始密钥通过密钥扩展产生和选取的。§.5密钥扩展〔ExpandedKey密钥扩展可以描述为：初始密钥通过一个密钥扩展函数扩展后,为每一轮加、解密所使用的轮密钥产生适当的比特数。因为AES算法要求一个轮密钥用于初始密钥加法,并且每一轮都需要一个轮密钥。这样,所需要的轮密钥比特的总数等于32×Nb×<Nr+1>,其中Nb为数据分组大小,Nr为轮数。因此,如果使用的分组长度为128比特〔即Nb=4,轮数为10〔即Nr=10,那么就需要1408比特的轮密钥。经过密钥扩展后,最高位的128比特分组就用作初始密钥加法的轮密钥,扩展密钥的下一个128比特分组作为第一轮的轮密钥,依次类推。最后,最低位的128比特用作最后一轮的轮密钥。下面介绍密钥扩展函数。对于不同初始密钥长度,密钥扩展函数略有不同,但都使用了以下几个重要的函数：字节代换<S-盒>、以密钥矩阵的列为单位的列的循环位移以及与轮常数的异或运算。将初始密钥〔初始密钥可以形象的排列成一个4×Nk字节的矩阵作为初始密钥加法的密钥,利用初始的Nk列的密钥,通过递归的方式确定后面的各列。递归函数依赖于列的位置：当初始密钥的列数Nk6时,如果第i列不是Nk的整数倍,则第i列是第i-Nk列与第i-1列的逐位异或；否则,第i列是第i-Nk列与第i-1列的一个非线性函数的逐位异或。对于初始密钥的列数Nk>6时,如果第i列不是Nk的整数倍,则第i列是第i-Nk列与第i-1列的逐位异或；如果imodNk=4,则第i列是第i-Nk列与通过字节代换后的第i-1列的逐位异或；如果第i列是Nk的整数倍,则第i列是第i-Nk列与第i-1列的一个非线性函数的逐位异或。这个非线性函数是通过以下方式来实现的：将SRD分别作用在列的4个字节上,同时附加一个列字节的循环位移,增加一个轮常量〔用于消除对称。轮常量独立于Nk,并且被GF<28>中的一个递归规则所定义[46]：RC[1]=x0<即01>RC[2]=x<即02>RC[j]=xRC[j-1]=xj-1,j>2以数据分组长度为128比特,初始密钥长度为128比特或192比特为例,密钥扩展函数的表达式如下〔K[i][j]表示初始密钥矩阵的第i行第j列,W[i][j]表示扩展后密钥矩阵的第i行第j列,Nk表示初始密钥分组的列数,Nr表示轮数,Nb表示数据分组的列数,在这里Nk=4或6,Nr=10或12,Nb=4：当Nk≤6时For<j=0;j<Nk;j++>For<i=0;i<4;i++>W[i][j]=K[i][j];For<j=Nk;j<Nb*<Nr+1>;j++>{If<jmodNk=0>{W[0][j]=W[0][j-Nk]⊕SubByte<W[1][j-1]>⊕RC<j/Nk>;For<i=1;i<4;i++>W[i][j]=W[i][j-Nk]⊕SubByte<W[<i+1>mod4][j-1]>;}Else{For<i=0;i<4;i++>W[i][j]=W[i][j-Nk]⊕W[i][j-1];}}其中,SubByte<S>是表示对状态S进行字节代换运算；RC<j/Nk>=<02><j/Nk>-1,用于消除对称。加密时密钥的选取：第i轮的轮密钥就是由矩阵W中第Nb×i列到Nb×<i+1>-1列给出。解密时密钥的选取：第i轮的轮密钥就是由矩阵W中第Nb×〔Nr-i列到Nb×〔Nr-i+1-1列给出。扩展：当初始密钥长度大于192比特时,即Nk＞6时,各轮轮密钥是经过下列密钥扩展函数得到的〔K[i][j]表示初始密钥矩阵的第i行第j列,W[i][j]表示扩展后密钥矩阵的第i行第j列,Nk表示密钥分组的列数,Nr表示轮数,Nb表示数据分组的列数：当Nk＞6时For<j=0;j<Nk;j++>For<i=0;i<4;i++>W[i][j]=K[i][j];For<j=Nk;j<Nb*<Nr+1>;j++>{If<jmodNk=0>{W[0][j]=W[0][j-Nk]⊕SubByte<W[1][j-1]>⊕RC<j/Nk>;For<i=1;i<4;i++>W[i][j]=W[i][j-Nk]⊕SubByte<W[<i+1>mod4][j-1]>;}ElseIf<jmodNk=4>{For<i=1;i<4;i++>W[i][j]=W[i][j-Nk]⊕SubByte<W[i][j-1]>;}Else{For<i=0;i<4;i++>W[i][j]=W[i][j-Nk]⊕W[i][j-1];}}其中,SubByte<S>是表示对状态S进行字节替代运算；C<j/Nk>=<02><j/Nk>-1,用于消除对称。加密时密钥的选取：第i轮的轮密钥就是由矩阵W中第Nb×i列到Nb×<i+1>-1列给出。解密时密钥的选取：第i轮的轮密钥就是由矩阵W中第Nb×<Nr-i>列到Nb×<Nr-i+1>-1列给出。AES的快速实现随着网络通信的发展,传送数据量的不断增大,每天都可能要进行数以亿次的加密时,一个高效的加密算法将大大降低网络延时。因此,在某些应用场合中,对加解密速度的需求成为对AES算法的关键要求。本章研究了Rijndael算法的快速实现,并给出了算法在32位平台上的软件实现方案。§4.1Rijndael算法的实现方案当前AES算法的实现研究主要分为软件实现、DSP实现和硬件实现三个方向。软件实现是基于通用PC的编程实现,它具有实现简单、可移植性强、成本相对低廉、易于升级等优点；它的缺点是庞大的操作系统和大量硬件资源的支持。由于通用CPU主频的不断提高,软件实现也能达到相当高的速度。§实现考虑为了使设计的算法能在32位平台上高效地执行,在进行算法设计的时候做了以下的考虑：<1>算法要支持三种密钥长度,即128bits、192bits和256bits密钥长度。<2>为了提高算法的执行速度,在存储空间允许的情况下,尽可能多地采用表查找的方法。<3>采用32位设计思路。以4字节为运算的基本单位,算法的主要计算部件设计成32位的查表操作,这样算法更易于在32位处理器上快速执行。<4>轮变换模块的实现用宏而不用函数,以减少函数调用的时间开销。<5>展开所有可以进行预运算的操作,展开所有轮的轮函数,避免多次存复制。§实现方案及其分析AES算法主要有三个大的模块,即密钥扩展模块、加密模块和解密模块。密钥扩展模块由产生加密密钥的模块和解密密钥的模块组成；加解密模块均由AddRoundKey模块、轮函数模块、FinalRound变换模块组成,其中最重要的是轮函数模块,它是AES算法的核心模块。轮函数的改进。轮函数是AES的核心,其效率的高低对整个算法实现的速度影响极大,可以通过以下的方法改造轮函数,通过查表的方式达到快速实现轮函数的目的。现在假设轮变换的输入为a,SubBytes的输出为b,则又设ShiftRows的输出为c,轮密钥为k,经过MixColumns和AddRoundKey后的输出为d,则有：将上面三个表达式合并,并将矩阵乘法用线性的向量组合来表示,得到：这样,我们可以定义以下四个T表：使用这些四个表,轮函数变换可以改写为：以上四个T表都包含了256个4字节的条目,从而需要4KB的存储空间,有了这四表,对每一列的轮变换只需要进行4次查表和4次异或操作,这样极大的提高了算法的效率。此外,不难发现,对于任意的a,T0[a]、T1[a]、T2[a]和T3[a]可以通过相互循环移位来生成。如果对于每一轮的每一列都额外增加3次循环移位,则只需构造其中一表,查表只需要在一大小为1KB的表上实现即可,这种方法适用于存储空间十分紧的应用环境中。§4.2各模块的算法描述及其分析§计算轮函数的T表由可知,我们只需要求出T0[a],运用字节循环移位便可以求出其余3个表,从而实现轮函数。利用S盒表盒字节乘法〔即GF<28>上的多项式乘法,可以实现轮函数T0[a]表,T0[a]表中的每一个元数均为四个字节。下面将分别给出T0[a]的表达式〔4.2.1-1及生成轮函数的T表的算法〔算法4-1[47]。算法4-1轮函数的T0[a]的生成typedefunsignedlongintu32;typedefunsignedcharu8;CreatTbox<u32T[256]>{u8n1,n2,n3;for<inti=0;i<256;i++>{n1=S[i];n2=mul<0x02,S[i]>;//mul<>是GF〔28的多项式乘法n3=mul<0x03,S[i]>;T[i]=[<u32>n3<<24]|[<u32>n1<<16]|[<u32>n1<<8]|<u32>n2;}}根据算法4-1,我们将T0[a]的计算结果存放在T[256]数组中,得到了以下T0表,其余3个表可以由该表循环移位得到。§轮函数的C语言实现我们采取的方法用C语言实现轮变换,为了在32位平台上得到较高的效率,函数的输出和输入都采用unsignedlongint类型。算法4-2[47]给出了使用一个表查询时的C代码。算法4-2轮函数的实现〔一个T表typedefunsignedcharuint8;typedefunsignedlongintuint32;inlinevoidRound<uint8*ptext,uint8*roundkey,uint32*ctext>{uint32rk[4];uint32t0=0,t1=