AES算法原理及其实现

1、第12期何明星等:AES算法原理及其实现16AES何明星叫林昊2（1.西南交通大学计算机与通信工程学院.四川成都610031:2.四川工业学院计算机科学与工程系, 四川成都610039）:在研究分析了 AES加密原理的基础上着重说明了 AES算法实现的具体步骤并用C语言完難地实现 TAES算法并利用密文分组链接（CBO方式将其用于对文件的加密/解密（密钥长度可选）o AES结合其它技 术还可实现更为广泛的安全协议。:分组密码；对称密码体制:DES:AES:TP309 7: A: 100 卜3695 （2002） 12006 卜03ImplementationoftheAdvancedEncry

2、ptionStandard (AES)HEMing-xin2 .LINHao 2(1. College of Computer <£ Conuttu/ticahon Enginecrmg. Southwest Jiuotong University. Clungdu Sic huan 610031. China: 2. DepL of ComputerScience A £>r gineering. Sichium University of Science Technology. Chengdu Sichuan. 610039. Chmai.Abstract:

3、 BasedontheinvestigationtotheprincipleandspecificationsofAES.aneffcctiveimplcmentationofAESblockcipheriscoinpletcdandthedocumentencryptionaiiddecry ptionisalsocompletedbyusingCipherBlockChaining(CBO Keywords: BlockCipher:SymmetricCr)ptosystein:DES;AES(AdvancedEncrptionStandard>© 1994-2008 Ch

4、ina Academic Journal Electronic Publishing House. All rights reserved, 第12期何明星等:AES算法原理及其实现16:2002-01-08：:2002 -05-21国家自然科学基金资助项目（69825103对称密码算法主要用于保证数据的机密性通僧双 方在加密/解密过程中使用它们共享的单一密钥。对称 密码算法的使用相当广泛密码学界巳经对它们进行了 深入的研究山最常用的对称密码算法是数据加密标 准（DES）算法.它是由IBM在美国国家安全局（NSA）授 意之下研制的一种使用56位密钥的分组密码算法。自 1977年公布战为美国政府

5、的商用加密标准以来已使用 20多年。DES的主要问题是其密钥长度较短.巳不适 合于当今分市式开放网络对数据加密安全性的要求。 在DES每隔五年的评估会议中最后一次在1998年美 国政府终于决定不再继续延用DES作为联邦加密标准, 也就表明了 DES将退出加密标准的舞台.而新的标准 AES（ AdvancedEncrjptionStandard ）将粉墨登场 。AES是美国国家标准技术研究所NIST旨在取代DES 的新一代的加密标准卩勺。NIST对AES候选算法的基本 要求是:对称分组密码体制:密钥长度支持128.192,256 位:明文分组长度128位:算法应易于各种硬件和软件实 现。1998

6、年NIST开始AES第一轮征集、分析、测试.共产 生了 15个候选算法。1999年3月完成了第二轮AES的 分析、测试。1999年8月NIST公布了五种算法（MARS. RC6.Rijndacl.Scrpcnt.Twofish）成为候选算法。最后.Rijir dael15'.这个由比利时人设计的算法与其它候选算法在成 为髙级加密标准（AES）的竞争中取得成功，于2000年10 月被NIST宣布咙为取代DES的新一代的数据加密标准 即AES。尽管人们对AES还有不同的看法“勺.但总体来 说.Rijndael作为新一代的数据加密标准汇聚了强安全性、 高性能、高效率、易用和灵活等优点。AES

7、设计有三个密 钥长度:128.192,256比特.相对而言.AES的128比特密 钥比DES的56比特密钥强1屮倍o2 AES /对称密码算法根据对明文消息加密方式的不同可 分为两大类.即分组密码和流密码。分组密码将消息分 为固定长度的分组输出的密文分组通常与输入的明文 分组文度相同。AES算法属于分组密码算法.它的输入 分组、输出分组以及加/解密过程中的中间分组都是128 比特，密钥的长度K为128.192或256比特。用Nk=4, 6,8代表密钥串的字数（I字=32比特）.在本文编制的 程序中由用户选定。用Nr表示对一个数据分组加密的 轮数（加密轮数与密钥长度的关系见表Do每一轮都需 要一

8、个和输入分组具有同样长度（128比特）的扩展密钥 Ke的參与。由于外部输入的加密密钥K长度有限，所 以在AES中要用一个密钥扩展程序（KcyExpimsion）把外 部密钥K扩展成更长的比特串.以生成各轮的加密密 钥。AES的加密与解密框图如图I所示。/28位好据分蛆/UZT变揀I1炮岷1的#说|(粽;11"代数槪)川花十仞的片成仏有|CSVirf "二n<!Fw¥WgX>反列2换G転冷咿的H坟 砸更爭拥)图1 AES的加密与解密框图(1)加密变换设X是AES的128比特明文输入.Y是128比特的 密文输出，则AES密文Y可以用下面的复合变换表示：Y二

9、A k(r>i)R s A" C R S Amd C R S Ak|(X)其中“ ”表示复合运算。这里Ax ：表示对X的一个变换 Akl(X) =X OKi ( Ki为第i轮的于密钥为比特串的异或运算)o S:S盒直换。即对每一个字节用XBox做一个置 换。MBox是一个给定的辕换表。R:行直换。C:列直 换 o sr(x) =a (x) 0s(x)02 03 01 on Sox01 02 03 01"01 01 02 03L03 01 01 02* Ls,这里o是特殊的乘法运算将在31.3节中详细介 绍。(2)解密变换解密变换是加密变换的逆变换这里不再详述。3 AE

10、S3. 1表1是三种不同类型的AES加密密钥分组大小与 相应的加密轮数的对照表。加密开始时输入分组的各字节按表2的方式装入 一个矩阵State中。如输入ABCDEFGHIJKLMNO侧输 入块影射到如表2的状态矩阵State中。表I表2AES爻if Bl 14分爼大小加密轮数FS-I2K4?4710AFS.I926 7J字12AES-256if4 r14AE1MRFiN<；<；K门1)H1-r加密过程主程序由下面的伪代码描述。其中的子 程序 SubBytes () eShiftRows ()MixColumns ()和 A(h dRounKe>()将在接下来的部分介绍密钥扩屐

11、程序(KeyExpansioii 将在 3.2 介绍 ©Ciphert bytein|4 *4.byteout(4 beginbytestate(4.4) state=in;AddRoundKef stale.w )<*4).wordw|4* (Nr+1 ) /SeeSec.3.1.4/SeeSec.3.l.l/SeeSec.3.1.2/SeeScc.3.1.3forround= 1 step 1 tcNr 1 SubByte state) ShiftRowi state) MixCohimnfistate)Add Rou nd Kef state. w+round 4) en

12、dforSubByte< slate)Shi ft Rowi stale)AddRoundKe< state.w+Nr 4 > oul=statcend3. 1. 1 S 盒变换 SubBytesO对输入矩阵的任一个元素A做如下变换S|AJ:仃)一个元素A从存储角度看都是一个八位的二进 制数.算出前四位所代表的十六进制数x和后四位所 代表的十六进制数y。如A=11010100时.x=c.y=4。从AES算法给定的S-Box(16行16列的矩阵.其 中每个元素为一个字节具体的S-Box略)中找出SA=Sx.y 的值。如 A=11010100 时,SA=Sx,y=Sc.4=lc=

13、00011101接通过下面的公式耳各A=S&gb血gbiby 变为 SA=bb |=b j irroJK Imodx (二叽“ im(idK <w6 imodh (二C这里 c= (c0clc2c3c4c5c6.c7) = (0.1.1.0.0.0)3. 1.2 行变换 ShiftRowi)在行变换中中间状态矩阵State的第一行不变:第 二至第四行做如下变换即将表3的状态矩阵变为表4 的状杰矩阵。表3表4列变换是对中间状态矩阵S3C逐列进行变换。其变换为如下的矩阵运算:l r<0x02 03 01 or01 02 03 Oi>r2x01 01 02 03、J

14、9;03 01 01 02经过上面的运算原来的一列就被瞽换成下面的式 于所表达的新列：S(').c) * = (02 xS(0.c ) 0(03) xSd.c ) GS(2.c ) OS(3.c) S(l.c),=S(0.c ) 0(02 xS(l.c) 0(03) xS(2.c ) GS(3.c ) S(2.c)'=S(0.c ) GS(l.c) GX02 xS(2.c ) 0(03 xS<3.c > S".c)' = (03 xS(0.c ) <SS(l.c)GS(2.c) 0(02) xS(3.c )这里G)为按位异或运算其中的乘法X按

15、照下面介 绍的模乘同余规则进行计算。列变换中要用到的模乘同余规则和我们一般用到 的乘法有些不同，由于每一个元素都是一个字节于是 可把这个字节看成一个形式上的七次多项式即将 SbbbjbqSbabibo 视为 b?x +b 6x6 +b +b 4x4 +b 3X +b2X2 +b ix+b 0 ,ftl110110012 =(d9 16可以被看成是 x7 +x6 +x4 +x3 +!-列变换希望把一个字节变换为一个新 的字节，所以需要把两个形式上的七次多项式的乘法结 果变为一个新的形式上的七次多项式，然后才能将其恢 复为一个字节的长度。这里釆用模一个八次不可约多 项式的同余乘法即将两七次多项式的

16、乘法结果除以这 个八次不可约多项式再取其余式。在AES中这个八次 不可约多项式为m(x) =x8 +x4 +x3 +x+l o例如: (x6+x4+x:+x+l ) X(x +X+1 ) =x 1' +x 11 +xM +xK +x6 +x5 +x4 +X 1 +1 (x1 A +x 11 +x9 +x+x6+x5 +x4 +x - +1 )mod(xK +x4+x A+x+I ) =x ' + x6 + l 对应为57 X83=cl o3. 1.4 与扩展密钥的异或运算AddRoundKejO扩展密钥只參与了这一个变换。根据加密的轮数 用相应的扩展密钥的四个数据项和中间状态矩

17、阵上的 列进行按位异或。S(Ox ) S( Lc )r .S(2.c )f .S(3.c )1 |=|S (O.c) S(l.c) S(2.c ) S(3.c ) XORW (round Xnb+c ) J3.2KcyExpansionAES算法利用外部输入密钥K(密钥串的字数为 Nk)，通过密钥扩展程序得到共4 (Nr+1)字的扩展密钥w4 X(Nr+l )<>涉及如下三个模块：(1) 位置变涣Rot Word)。把-个四个宇节的序列 a0.al.a2.a3左移一个字节变为aLa2.a3.aO。(2) SubWordO。对一个四字节的输入字aO.al. a2.a3的每一人字节进行

18、S盒变换，然后作为输出(见 3. 1. 1)。(3) 变换Rcon|。Rconi表示32比特字符串xr，,00.00.00。这里 x二(02) .x 是 x二(02)的(卜1) 次幕的十六进制表示。例如，Rconl=0l000000|.Rcon2= 02000000.Rcon3 |=|0W00000.Rcon|4=08000000.Rcon 101=1360000001 (4) 扩屐密钥的生成。扩展密钥的前2个字就是 外部密钥K:以后的字wi等于它前一个字w(i-l 与前第2个字wi -Nk的异或，即wi=wi1 XORwi -Nk|l # 但是若 i 为 Nk 的倍数,则 wi=wi NkJ

19、XORSubWord (RotWord(wi 1 ) XORRconi/ Nk。举例： 殳外部输入的加密密钥CipherKey=2b7e 1516 28aed2a6abf7158809cf4f3cNk=4,則 uO=2b7e 1516w 1 =28aed2a6w2=abf71588w3=09cf4f3c; w4=OXORSubWord (RocWordw3) XORRcon|4/Nk)=aOfafel7;w5=wRi -lJJXORwHi Nk|=w4JXORw| 1 =88542cbl:w43=b6630ca6 入明文：00112233445566778899aabbccddccfF: 输入

20、密钥：00010203040506070809(ta0b0c0d0e0f 各轮密文：round0.i 叩 ul0011223344556677889933bbccddeeff;round(0.k - schOOO 1 ()2030405060708090aOM)c()dOeOf round! 1 5uirt00102030405060708090a0b0c0d0e0f0 round(10|.output69c4e0d86a7b0430d8cdb78070b4c55a OUTPlIT:69c4e0d86a7b(M30d8cdb78070b4c55a4 /在完成了 DES分组加密算法实现的基础上现

21、在利 用密文分组链接(CBO方式将其用于对文件的加密/解 密(密钥长度可选).程序的操作步骤如下：(1) 根据文件处理方式选择模块，选择对文件加密、 对文件解密或是退出程序.(2) 输入密钥K的长度(128比特、192比特、256比特)和密钥。用密钥扩屐程序对密钥加以扩展。128比特、 192比特、256比特密钥分别对应KeyExpansionl2<key). KeyExpansion 192key) ,KeyExpansion256 (key).分别生成 72bytcs,2O4bytes,236bytes 的扩展密钥。(4) 创建加密/解密文件。文件都是以文本格式存 储的.(5) 从等

22、待加密/解密文件中取出16字节。若是未 取岀16个字节文件就结束.则在结束处标上文件结束 符。把取出的数据放入中间变量(STATB中。根据密钥的长度对STATE中的数据进行加密/ 解密。128比特、192比特、256比特分别对应Cipher 128 (InvCipherl28 .Cipher 192 (InvCipherl92 .Cipher256 (Iir vCiphcr256。并把加密/解密肓的数据保存在STATE 中。把STATE中的数据写入加密/解密文件中。如果等待加密/解密的文件巳经结束，则关闭文 件回到操作：否则回到操作(5) o这样程序就实现了对一个文件的加密/解密操作。本文在研究分析了 AES加密原理的基础上着莹说 明了 AES算法实现的具体步骤.包括扩展密钥的异或运 算、AddRoundKcyO、列变换 MixColumnsO、行变换 ShiftRowO >S盒变换SubBytesO等.以及各步骤的轮换 颠序却最重要的密钥扩展程序KeyExpansion等.并用C