对称密钥密码算法研究应用

河南科技大学毕业设计（论文）题目＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿姓名＿＿＿＿＿＿＿＿院（系）＿＿＿＿＿＿＿＿专业＿＿＿＿＿＿＿＿指引教师＿＿＿＿＿＿＿＿年月日毕业设计（论文）任务书填表时间：年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摘要 IABSTRACT II第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§3.1.1高加密原则制定过程 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§3.4.2加、解密输入输出 26§3.4.3AES算法环节 28§3.4.4AES算法描述 30§字节代换（SubBytes） 30§行移变换（ShiftRows） 31§列混合变换（MixColumns） 32§密钥扩展（ExpandedKey） 34第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盒非线性度、差分均匀度及其分量函数代多次数和项数。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寿命还不届时,就已被多次攻破而被以为不安全了,其中最知名两个袭击是差分密码分析和线性密码分析。但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]。当前,三重DES112位密钥长度被以为是很“强健”加密方式。此外,由于DES算法完全公开,其安全性完全依赖于对密钥保护,必要有可靠信道来分发密钥(如采用信使递送密钥等),不适合在网络环境下单独使用。§2.5IDEA分组密码对DES成功破译迫使人们重新设计密码算法。IDEA[38]是第一种不采用Feistel网络密码。IDEA安全性设计思想是:采用同一明文空间上三个不同群运算,使掩蔽,混淆和扩散溶为一体。IDEA是分组密码杰出代表,开创了新一类设计风格。AES加密算法§3.1AES发展史§3.1.1高加密原则制定过程最初阶段,1997年1月,美国国标和技术研究所(NIST)发布公示征集新加密原则,即AES。新加密原则将取代旧数据加密原则(DES)和三重DES而成为一种(美国)联邦信息解决原则(FIPS)。与DES、安全散列算法(SHA-1)和数字签名算法(DSA)选取过程不同。NIST宣布AES选取过程将是公开,任何人都可以提交候选密码算法,任何符合规定提案都将被仔细考虑,NIST自身不进行任何安全或效率评估,而是邀请密码学界袭击候选算法并进行密码分析,并且任何感兴趣人都可以评估候选算法实当代价。所有成果都可以作为公开评论发给NIST,并在NISTAES网站发布,或者也可以提交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算法。11月从中选用Rijndael算法作为下一代密码算法AES[39-40]在AES候选算法评估过程中,AES工作组考虑所有评论、论文、NIST研究和报告,提出了如下评判准则[41].安全性。这是评估中最重要因素,涉及：算法抗密码分析强度,稳定数学基本,算法输出随机性以及与其她候选算法比较相对安全性。(2)代价。这是评估中第二重要因素[42],重要涉及：应具备高执行效率和低存储需求有点；并且各运算部件具备良好记录特性,并行执行度高；加、解密速度快,不需要繁琐乘法运算。(3)算法实现特性[43]。它涉及：灵活性,硬件和软件适应性,算法简朴性。其中灵活性应涉及：解决密钥和分组长度必要超过最小支持范畴；在许多不同类型环境中可以安全和有效地实现；可以作为序列密码、杂凑算法实现,并且提供附加密码服务。2月28日,NIST发布FIPS草案供公众讨论。11月2日NIST发布正式文本FIPS1971,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算法设计原理进行阐明。§3.3.1安全性原则针对某一特定分组密码算法,其袭击办法可分为通用袭击办法和专用袭击办法。所谓通用袭击办法就是对所有分组加密算法袭击均有效办法,而专用袭击办法只针对某特定算法有效,普通与详细密码算法某种特定构造关于。设计当代实用密码算法时,为了能有效地抵抗通用袭击,普通遵循仙农(Shannon)提出混淆(Confusion)原则和扩散(Diffusion)原则。同步,混淆和扩散也是分组密码算法设计理论中保证明文可以可靠、隐蔽最基本技术[45]。所谓混淆性原则是指所设计密码应使密文对密钥和明文依赖关系相称复杂,以至于这种依赖性对于密码分析者来说是无法运用。混淆用于掩盖明文、密文和密钥之间关系。这可以挫败通过研究密文以获取冗余度和记录模式企图。做到这一点最容易办法是通过代替,一,简朴代替密码,如单字母密码,其中每一种拟定明文字符被一种密文字符所代替。当代代替密码更复杂：一种长明文分组被代替成一种不同密文分组,并且代替机制随明文或者密钥中每一位发生变化。好混淆可以使这种记录关系变得复杂以致强有力密码分析工具都不能有效。所谓扩散性原则是指所设计密码应使得密钥每一位数字能影响密文许多位数字,以防止对密钥进行逐段破译,同步明文每一位数字也能影响密文许多位数字,以便隐藏明文数字记录特性。扩散通过将明文冗余度分担到密文中使之分散开来,把单个明文位和密钥位影响尽量扩大到更多密文中去。密码分析者谋求这些冗余度将会更难。产生扩散最简朴办法是换位(也称为置换)。为了能抵抗专用袭击,则需要对算法自身构造进行分析,消除其中不安全因素。AES算法在设计时,设计者通过轮函数多轮迭代,为抵抗通用袭击提供了必要混淆和扩散,同步这种多轮迭代办法也消除了AES算法面向字节解决不安全因素,有效地抵抗了对算法专用袭击。§3.3.2实现性原则一种好密码算法规定设计简朴,构造合理,易于用软件或硬件实现,也就是说密码具备良好实现性[45]。一种密码算法若要用软件实现,则尽量使密码算法针对某一特定长度进行,子块长度应尽量地适应软件编程,如采用8位、16位、32位子块,这是由于在软件实现中,单个比特之间置换是难于实现,除了使用子块外,密码算法应采用某些易于软件实现运算,如原则解决器能直接解决加、减、乘、移位运算等。密码算法若要用硬件实现,那么规定密码算法构造尽量地紧凑,轮变换尽量地一致,这样就便于用ASIC或FPGA实现；同步在设计时,使加密和解密过程尽量地相似,这样就可以用一种功能模块同步实现加密和解密。§3.4AES算法整体构造分组加密算法是由一种叫做轮变换函数通过多次迭代构成,轮变换构成涉及非线性层,扩散层和密钥调度等元素。这些设计是基于仙农提出设计原则：非线性代替与线性混合函数交替进行。这样结合成果导致来自密码重要记录特性是高度有关和敏感类型,即通过混合变换扩散和混淆产生充分混合,使加密后分组记录特性分布更均匀。§3.4.1迭代密码算法构造分类为了符合安全性和实现性原则,当代实用分组密码算法普通采用了轮函数多次迭代构造,也称为迭代密码算法。尽管所有迭代密码算法在采用迭代方式上是一致,但详细密码算法整体构造却不尽相似。分组迭代密码整体构造大体有三类:Feistel网络构造,如DES,CAST-256,DEAL等；代替/置换(SP)网络构造,如square,safer+,serpent等；除了这两种构造以外算法归为第三类[45]。近来几年SP构造应用比较广泛。其中Feistel网络构造和SP网络构造如图2-1所示：(a)Feistel网络构造(b)SP网络构造图3.4.1-1分组迭代密码两种构造§Feistel网络构造Feistel网络构造是HorstFeistel在设计Lucifer分组密码时创造,并由于IED广泛使用而流行,对一种分组密码长度为2nr轮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网络构造。§替代/置换(SP)网络构造SP网络构造是近几年来应用比较广泛一种构造,这种网络构造非常清晰,每一轮由非线性层S层和线性层P层构成,SP型密码一轮加密过程如图2-1(P)所示[45]。SP型密码每一轮变换中,一方面将S层作用于轮输入使其混淆,然后通过P层作用使之得到扩散,图2-1(b)中子密钥放在S层,在实际实现中子密钥可放在其她位置。SP型密码具备一种很大长处,就是当给定S层和P层密码指标后,可以从理论上给出抵抗差分密码袭击和线性袭击能力,除此之外,经一轮变换后,轮输入每一位均得到了扩散,从这个角度来看,SP型密码比Feistel型密码能更快扩散。§AES算法构造AES算法构造紧凑、规整,加密和解密过程相似,算法构造属于SP构造,构成其每一轮轮变换4个函数分别属于S层、P层和密钥加层[46]。S层是由字节代换函数(SubBytes)构成,该函数作用重要是保证多轮迭代后成果高度混淆,因此也称为非线性层。P层由行移函数(ShiftRows)和列混合函数(MixColoumns)构成,这两个函数重要作用是保证多轮迭代后高度扩散,因此又称为线性层。密钥加层由密钥加法函数(AddRoundkey)构成,该层重要起到子密钥控制作用,即实现了密钥与明文结合。许多密码分析办法对迭代密码第一轮和最后一轮与中间轮分析办法不同,普通依照假定密钥值和明文、密文进行运算来剥去迭代密码首轮和末轮,为此,AES算法对第一轮和最后一轮进行了特殊解决：第一轮之前加了一种密钥控制下前期变换；而最后一轮则去掉了其中列混合运算。因而,AES算法在总体构造上采用了第一轮和最后一轮特殊对待SP构造。§3.4.2加、解密输入输出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时,明文-状态矩阵映射如表3.4.2-1所示：表3.4.2-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时,初始密钥-密钥矩阵映射如表3.4.2-1所示：表3.4.2-1初始密钥-密钥矩阵映射密钥矩阵K0K4K8K12K16K20K1K5K9K13K17K21KK6K10K14K18K22K3K7K11K15K19K23AES加密解密时数据块操作解决过程：现将a0,a1,a2,a3,a4,...,a15复制到状态数组；加密解密过程都对这个状态进行技术解决；等加密解密过程解决结束,再将状态组复制到b0,b1,b2,b3,b4,...,b15。最后得到ASE加密解密输出成果。操作映射过程如图3.4.2-1所示：输入数据中间成果(状态)输入数据图3.4.2-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比特密钥)轮运算。轮数目由密钥长度决定，其关系如表3.4.3-1所示：表3.4.3-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)，如图3.4.3-1所示：图3.4.3-1加密全过程(密钥长度为128比特)其中，每个轮变换(Round)由4层构成：第一层(字节代换-SubBytes)为非线性层，是将一种输入为8比特输出也为8比特S盒作用于状态矩阵中每一种字节；第二层(行移变换-ShiftRows)和第三层(列混合变换-MixColumns)是线性层，是将4×4状态矩阵按行移位，按列混合；第四层(密钥加法-AddRoundKey)为密钥加层，是将轮密钥每个字节和状态矩阵中相应位置字节进行异或。每一轮流程如图3.4.3-2所示：图3.4.3-2每一轮构造图3.4.3-3AES算法加、解密过程(128比特密钥)其中，FinalRound包括除MixColumns这一步以外其她3个环节。AES解密算法实现涉及密钥扩展过程和解密过程。解密过程与加密过程类似，是加密过程逆运算。以数据分组大小为128比特，初始密钥长度为128比特为例AES算法加、解密过程如图3.4.3-3所示：§3.4.4AES算法描述§字节代换（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变换作用后，其效果如图3.4.4-1所示：图3.4.4-1字节代换示意图SubBytes变换是可逆，在AES解密过程中所用到字节代换逆变换InvSubBytes运算如下：对状态矩阵每一字节元素，先进行有限域G(28)上逆仿射变换，然后计算其在有限域G(28)上乘法逆。§行移变换（ShiftRows）ShiftRows是线性变换，它和列混合运算互相影响，在多轮变换后，使密码信息达到充分扩散。行移变换是在状态矩阵每个行间进行，是状态矩阵中行按照不同偏移量进行循环左移运算，第0行循环左移C0字节，第1行循环左移C1字节，第2行循环左移C2字节，第3行循环左移C3字节，从而使第i行第j列字节移到位置第i行第（j-Ci）modNb列[46]。移动偏移量C0，C1，C2，C3依赖于Nb取值，如表3.4.4-1所示：表3.4.4-1偏移量-分组大小关系表分组大小（Nb）C0C1C2C34012350123601237012480134ShiftRows变换对状态矩阵影响如图3.4.4-2所示：图3.4.4-2行移变换示意图在AES解密过程中所用到ShiftRows逆变换称为InvShiftRows，是状态矩阵中行按照不同偏移量进行循环右移运算，第0行循环右移C0字节，第1行循环右移C1字节，第2行循环右移C2字节，第3行循环右移C3字节，从而使第i行第j列字节移到位置第i行第（j+Ci）modNb列。移动偏移量C0，C1，C2，C3依赖于Nb取值（同ShiftRows中C0，C1，C2，C3）。§列混合变换（MixColumns）MixColumns是对状态矩阵中列做线性变换，进行四字节乘运算。详细定义如下：将状态矩阵列看作有限域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.4.4-3所示：图3.4.4-3列混合变换示意图在AES解密过程中所用到MixColumns逆变换称为InvMixColumns，它与MixColumns类似，是状态矩阵中每一列在模x4+1下与多项d(x)=0Bx3+0Dx2+09x+0E相乘。假设该步变换状态一列输入位a，输出为b，如表达式(3.4-3)所示：§密钥加法(AddRoundKey)AddRoundKey是将轮密钥各字节和状态矩阵中相应位置字节分别模2加，实现状态和密钥混合[3]。轮密钥长度和状态长度是同样。该环节逆变换是其自身。AddRoundKey变换对状态矩阵影响如图3.4.4-4所示(W表达通过密钥扩展后密钥矩阵）：图3.4.4-4密钥加法示意图轮密钥是由初始密钥通过密钥扩展产生和选用。§密钥扩展（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主频不断提高，软件实现也能达到相称高速度。§4.1.1实现考虑为了使设计算法能在32位平台上高效地执行，在进行算法设计时候做了如下考虑：(1)算法要支持三种密钥长度，即128bits、192bits和256bits密钥长度。(2)为了提高算法执行速度，在存储空间容许状况下，尽量多地采用表查找办法。(3)采用32位设计思路。以4字节为运算基本单位，算法重要计算部件设计成32位查表操作，这样算法更易于在32位解决器上迅速执行。(4)轮变换模块实现用宏而不用函数，以减少函数调用时间开销。(5)展开所有可以进行预运算操作，展开所有轮轮函数，避免多次内存复制。§4.1.2实现方案及其分析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各模块算法描述及其分析§4.2.1计算轮函数T表由3.1.2可知，咱们只需规定出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个表可以由该表循环移位得到。§4.2.2轮函数C语言实现咱们采用4.1.2办法用C语言实现轮变换，为了在32位平台上得到较高效率，函数输出和输入都采用unsignedlongint类型。算法4-2[47]给出了使用一种表查询时C代码。算法4-2轮函数实现（一种T表）typedefunsignedcharuint8;typedefunsignedlongintuint32;inlinevoidRound(uint8*ptext,uint8*roundkey,uint32*ctext){uint32rk[4];uint32t0=0,t1=0,t2=0,t3=0;t0=T[ptext[0]];t1=(T[ptext[5]]>>8)|(T[ptext[5]]<<24);t2=(T[ptext[10]]>>16)|(T[ptext[10]]<<16);t3=(T[ptext[15]]>>24)|(T[ptext[15]]<<8);ctext[0]=t0^t1^t2^t3;rk[0]=((uint32)roundkey[0]<<24)|((u