AES算法原理及其实现

AES算法原理及其实现

何明星1,2,林　昊2

(1.西南交通大学计算机与通信工程学院,四川成都610031;2.

四川成都610039)

3

四川工业学院计算机科学与工程系,

摘　要:在研究分析了AES加密原理的基础上着重说明了AES算法实现的具体步骤,并用C语言完整地实现

)方式将其用于对文件的加密/解密(密钥长度可选)。AES结合其它技了AES算法,并利用密文分组链接(CBC

术还可实现更为广泛的安全协议。

关键词:分组密码;对称密码;DES;AES中图法分类号:TP30917　　　文献标识码:A　　　文章编号:100123695(2002)1220061203

ImplementationoftheAdvancedEncryptionStandard

HEMing2xing

1,2

(AES)

,LINHao

2

(1.CollegeofComputer&CommunicationEngineering,SouthwestJiaotongUniversity,ChengduSichuan610031,China;2.Dept.ofComputerScience&En2gineering,SichuanUniversityofScience&Technology,ChengduSichuan,610039,China)

Abstract:BasedontheinvestigationtotheprincipleandspecificationsofAES,aneffectiveimplementationofAESblockcipheriscompleted(CBC).andthedocumentencryptionanddecryptionisalsocompletedbyusingCipherBlockChainingKeywords:BlockCipher;SymmetricCryptosystem;DES;AES(AdvancedEncryptionStandard)1　引言

对称密码算法主要用于保证数据的机密性,通信双

方在加密/解密过程中使用它们共享的单一密钥。对称密码算法的使用相当广泛,密码学界已经对它们进行了深入的研究[1]。最常用的对称密码算法是数据加密标准(DES)算法,它是由IBM在美国国家(NSA)授意之下研制的一种使用56位密钥的分组密码算法。自1977年公布成为美国的商用加密标准以来已使用20多年[2]。DES的主要问题是其密钥长度较短,已不适合于当今分布式开放网络对数据加密安全性的要求。在DES每隔五年的评估会议中,最后一次在1998年美国终于决定不再继续延用DES作为联邦加密标准,也就表明了DES将退出加密标准的舞台,而新的标准AES(AdvancedEncryptionStandard)将粉墨登场[3]。

AES是美国国家标准技术研究所NIST旨在取代DES的新一代的加密标准[3～5]。NIST对AES候选算法的基本要求是:对称分组密码;密钥长度支持128,192,256位;明文分组长度128位;算法应易于各种硬件和软件实现。1998年NIST开始AES第一轮征集、分析、测试,生了15个候选算法。1999年3月完成了第二轮AES的分析、测试。1999年8月NIST公布了五种算法(MARS,RC6,Rijndael,Serpent,Twofish)成为候选算法。最后,Rijn2dael[5],这个由比利时人设计的算法与其它候选算法在成

为高级加密标准(AES)的竞争中取得成功,于2000年10月被NIST宣布成为取代DES的新一代的数据加密标准,即AES。尽管人们对AES还有不同的看法[6～8],但总体来说,Rijndael作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点。AES设计有三个密钥长度:128,192,256比特,相对而言,AES的128比特密钥比DES的56比特密钥强1021倍[4]。

2　AES加密/解密算法原理

对称密码算法根据对明文消息加密方式的不同可分为两大类,即分组密码和流密码。分组密码将消息分为固定长度的分组,输出的密文分组通常与输入的明文分组长度相同。AES算法属于分组密码算法,它的输入分组、输出分组以及加/解密过程中的中间分组都是128比特。密钥的长度K为128,192或256比特。用Nk=4,6,8代表密钥串的字数(1字=32比特),在本文编制的程序中由用户选定。用Nr表示对一个数据分组加密的轮数(加密轮数与密钥长度的关系见表1)。每一轮都需要一个和输入分组具有同样长度(128比特)的扩展密钥Ke的参与。由于外部输入的加密密钥K长度有限,所以在AES中要用一个密钥扩展程序(KeyExpansion)把外部密钥K扩展成更长的比特串,以生成各轮的加密密钥。

AES的加密与解密框图如图1所示。

收稿日期:2002201208;修返日期:2002205221基金项目:国家自然科学基金资助项目(69825102)

　　・26・计算机应用研究

(state,w+round34)　　AddRoundKeyendfor

(state)SubBytes

(state)ShiftRows

(state,w+Nr34)AddRoundKey

out=stateend

2002年

31111　S盒变换SubBytes()

图1　AES的加密与解密框图

(1)加密变换

设X是AES的128比特明文输入,Y是128比特的密文输出,则AES密文Y可以用下面的复合变换表示:

Y=A

R・S・Akr・C・R・S・Ak(r21)・…・C・R・S・Ak1(X)k(r+1)・

对输入矩阵的任一个元素A做如下变换S[A]:

(1)一个元素A从存储角度看都是一个八位的二进制数。算出前四位所代表的十六进制数x和后四位所代表的十六进制数y。如A=11010100时,x=c,y=4。

(2)从AES算法给定的S2Box(16行16列的矩阵,其中每个元素为一个字节,具体的S2Box略)中找出S[A]=S[x,y]的值。如A=11010100时,S[A]=S[x,y]=S[c,4]={1c}=00011101。或直接通过下面的公式将A=b7b6b5b4b3b2b1b0变为S[A]=b’7b’6b’5b’4b’3b’2b’1b’0。

b′i=bi󰂽b(i+4)mod8󰂽b(i+5)mod8󰂽b(i+6)mod8󰂽b(i+6)mod8󰂽Ci

其中“・”表示复合运算。这里Aki:表示对X的一个变换

Aki(X)=X󰂽Ki(Ki为第i轮的子密钥,为比特串的异或运算)。S:S盒置换。即对每一个字节用S2Box做一个置换。S2Box是一个给定的转换表。R:行置换。C:列置

(x)=a(x)󰃁s(x)换。s′

s′0,cs1,cs′2,cs′3,c′

这里c=

(c0,c1,c2,c3,c4,c5,c6,c7)=(0,1,1,0,0,0,1,1)。

()31112　行变换ShiftRows

02　03　01　01=

01　02　03　0101　01　02　0303　01　01　02s0,cs1,cs2,cs3,c在行变换中,中间状态矩阵State的第一行不变;第

二至第四行做如下变换,即将表3的状态矩阵变为表4的状态矩阵。这里󰃁是特殊的乘法运算,将在31113节中详细介绍。

(2)解密变换

解密变换是加密变换的逆变换,这里不再详述。

()31113　列变换MixColumns

列变换是对中间状态矩阵State逐列进行变换。其

变换为如下的矩阵运算:

s′0,cs′1,cs′2,cs′3,c=

02　03　01　0101　02　03　0101　01　02　0303　01　01　02s0,cs1,cs2,cs3,c

3　AES加密/解密算法的实现

311　分组加密

表1是三种不同类型的AES加密密钥分组大小与

相应的加密轮数的对照表。

加密开始时,输入分组的各字节按表2的方式装入一个矩阵State中。如输入ABCDEFGHIJKLMNOP,则输入块影射到如表2的状态矩阵State中。

经过上面的运算,原来的一列就被替换成下面的式子所表达的新列:

S(0,c)′=({02}×S(0,c))󰂽({03}×S(1,c))󰂽S(2,c)󰂽S(3,c)S(1,c)′=S(0,c)󰂽({02}×S(1,c))󰂽({03}×S(2,c))󰂽S(3,c)S(2,c)′=S(0,c)󰂽S(1,c)󰂽({02}×S(2,c))󰂽({03}×S(3,c)S(3,c)′=({03}×S(0,c))󰂽S(1,c)󰂽S(2,c)󰂽({02}×S(3,c))

加密过程主程序由下面的伪代码描述。其中的子

程序SubBytes(),ShiftRows(),MixColumns()和Ad2dRounKey()将在接下来的部分介绍,密钥扩展程序(Key

)将在3.2介绍。Expansion

Cipher(bytein[434],byteout[434],wordw[43(Nr+1)])

begin

bytestate[4,4]state=in;

(state,w)　　AddRoundKey//SeeSec.3.1.4

forround=1step1toNr21

(state)　　//SeeSec.3.1.1　　SubBytes

(state)　　//SeeSec.3.1.2　　ShiftRows

(state)　　//SeeSec.3.1.3　　MixColumns

这里󰂽为按位异或运算,其中的乘法×按照下面介

绍的模乘同余规则进行计算。

列变换中要用到的模乘同余规则和我们一般用到的乘法有些不同,由于每一个元素都是一个字节,于是可把这个字节看成一个形式上的七次多项式,即将b7b6b5b4b3b2b1b0视为b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b

0

,如{11011001}2={d9}16可以被看成是

x7

+x6+x4+x3+1。列变换希望把一个字节变换为一个新的字节,所以需要把两个形式上的七次多项式的乘法结果变为一个新的形式上的七次多项式,然后才能将其恢

复为一个字节的长度。这里采用模一个八次不可约多项式的同余乘法,即将两七次多项式的乘法结果除以这个八次不可约多项式再取其余式。在AES中这个八次

第12期何明星等:AES算法原理及其实现・　　36・

不可约多项式为m(x)=x8+x4+x3+x+1。例如:

(x6+x4+x2+x+1)×(x7+x+1)=x13+x11+x9+x8+x6+x5+x4+x3+1

(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)=x7+x6+1

对应为{57}×{83}={c1}。

()31114　与扩展密钥的异或运算AddRoundKey

特)和密钥。

(3)用密钥扩展程序对密钥加以扩展。128比特、

(key),192比特、256比特密钥分别对应KeyExpansion128(key),KeyExpansion256(key),分别生成KeyExpansion192

72bytes,204bytes,236bytes的扩展密钥。

(4)创建加密/解密文件。文件都是以文本格式存

扩展密钥只参与了这一个变换。根据加密的轮数

用相应的扩展密钥的四个数据项和中间状态矩阵上的列进行按位异或。

[S(0,c)′,S(1,c)′,S(2,c)′,S(3,c)′]=[S(0,c),S(1,c),S(2,c),S(3,c)]XOR[W(round×nb+c)]

储的。

(5)从等待加密/解密文件中取出16字节。若是未取出16个字节文件就结束,则在结束处标上文件结束

)中。符。把取出的数据放入中间变量(STATE

(6)根据密钥的长度对STATE中的数据进行加密/

312　密钥扩展程序KeyExpansion

AES算法利用外部输入密钥K(密钥串的字数为

Nk),通过密钥扩展程序得到共4(Nr+1)字的扩展密钥w[4×(Nr+1)]。涉及如下三个模块:

(1)位置变换RotWord()。把一个四个字节的序列[a0,a1,a2,a3]左移一个字节变为[a1,a2,a3,a0]。

(2)SubWord()。对一个四字节的输入字[a0,a1,a2,a3]的每一个字节进行S盒变换,然后作为输出(见31111)。

(3)变换Rcon[]。Rcon[i]表示32比特字符串[xi21,00,00,00]。这里x=(02),xi21是x=(02)的(i21)次幂的十六进制表示。例如,Rcon[1]=[01000000],Rcon[2]=

[02000000],Rcon[3]=[04000000],Rcon[4]=[08000000],Rcon[10]=[36000000]。

解密。128比特、192比特、256比特分别对应Cipher128(InvCipher128),Cipher192(InvCipher192),Cipher256(In2)。并把加密/解密后的数据保存在STATEvCipher256

中。把STATE中的数据写入加密/解密文件中。

(7)如果等待加密/解密的文件已经结束,则关闭文件,回到操作(1);否则回到操作(5)。这样程序就实现了对一个文件的加密/解密操作。

…,

5　结束语本文在研究分析了AES加密原理的基础上着重说明了AES算法实现的具体步骤,包括扩展密钥的异或运算、AddRoundKey()、列变换MixColumns()、行变换()、ShiftRowsS盒变换SubBytes()等,以及各步骤的轮换

(4)扩展密钥的生成。扩展密钥的前Nk个字就是外部密钥K;以后的字w[[i]]等于它前一个字w[[i21]]与前第Nk个字w[[i2Nk]]的异或,即w[[i]]=w[[i21]]XORw[[i2Nk]]。但是若i为Nk的倍数,则w[i]=w[i2Nk]XORSubWord(RotWord(w[[i21]]))XORRcon[i/Nk]。

举例:①设外部输入的加密密钥CipherKey=2b7e151628aed2a6abf7158809cf4f3c

Nk=4,

顺序和最重要的密钥扩展程序KeyExpansion等,并用C语言完整地实现了AES算法。参考文献:

[1][2][3][4][5][6]

冯登国,裴定一1密码学导引[M]1北京:科学出版社,19991

NSA1DataEncryptionStandard[M]1FIPSPUB46,19771

则w0=2b7e1516w1=28aed2a6w2=abf71588w3=09cf4f3c;

…

(w3))XORRcon[4/Nk]=a0fafe17;w4=w0XORSubWord(RotWord

w5=w[[i21]]XORw[[i2Nk]=w[[4]]XORw[[1]]=882cb1;w43=b6630ca6。

何明星,范平志1新一代私钥加密标准AES进展与评述[J]1计算机应用研究,2001,18(10):426.

NIST1AdvancedEncryptionStandard(AES)[M]1FederalInfor2mationProcessingStandardsPublication,2001.

TheAdvancedEncryptionStandard(Rijndael)[EB/OL]1http://www.ccf.org.cn/,March,2001

②输入明文:0011223344556677aabbccddeeff;

输入密钥:000102030405060708090a0b0c0d0e0f各轮密文:

round[0].input0011223344556677aabbccddeeff;round[0].k

sch000102030405060708090a0b0c0d0e0f

round[1].start00102030405060708090a0b0c0d0e0f0

1

2

～sean/.AESForum

SMurphy,MRobshaw1FurtherCommentsontheStructureofRijndael[EB/OL]1http://www.cs.rbbnc.ac.uk/Comment,2000208217.

…

round[10].output69c4e0d86a7b0430d8cdb78070b4c55aOUTPUT:69c4e0d86a7b0430d8cdb78070b4c55a

[7]SMurphy,MRobshaw1NewObservationonRijndael[EB/OL]1http://www.cs.rbbnc.ac.uk/2000208207.

～sean/,AESForumComment,

2

4　对文件的加密/解密

在完成了DES分组加密算法实现的基础上,现在利

用密文分组链接(CBC)方式将其用于对文件的加密/解密(密钥长度可选),程序的操作步骤如下:

(1)根据文件处理方式选择模块,选择对文件加密、对文件解密或是退出程序。

(2)输入密钥K的长度(128比特、192比特、256比

[8]

AESDiscussionForum[EB/OL]1http://aes.nist.gov/aes/,2001031

作者简介:

何明星,男,四川工业学院计算机科学与工程系副教授,博士生,研究方向为电子商务、网络与信息安全等;林昊,男,学生,研究方向为网络与信息安全。