ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



15AESѡ㷨
ᡡǹ˹
ժҪ¶ұ׼ͼо(NIST)15AESѡ㷨Ļ˼˼ҪܣͬʱҲ˶Щ㷨·.
ؼʡAES(advanced encryption standard),DES(data encryption standard),,,Կ.
ͼšTP391
Brief Commentary on the 15 AES Candidate Algorithms Issued by NIST of USA
WU Wen-ling FENG Deng-guo QING Si-han
(Institute of Software The Chinese Academy of Sciences Beijing 100080)
(Engineering Research Center for Information Security Technology The Chinese 
Academy of Sciences Beijing 100080)
Abstract In this paper, the authors introduce the basic ideas of the 15 AES(advanced encryption standard) candidate algorithms issued by National Institute of Standards and Technology (NIST) of USA. The current analysis results of these algorithms are also presented.
Key wordsAES(advanced encryption standard), DES(data encryption standard), encryption, decryption, key.
DES(data encryption standard)ߵľͷ.Կս֤DES56-Կ̫.ȻDESԽԿȵ⣬DESҪӲʵ.,ҪʵЧ㷨.ڴˣ1997415,ұ׼ͼоNISTAESadvanced encryption standard㷨Ļ1ݣAES.ĿΪȷһǱܵġ¶ġȫʹõļ㷨ڱһϢҲϣܹΪܺ͹ŵݼܱ׼DES.1997912գNISTǼǴFRAESѡ㷨ͨ.AESĻҪǱDES죬ٺDESһȫ鳤128أԿΪ128192256.1998820գNISTٿ˵1AESѡ飬15AESѡ.Ŀǰ۽׶.NISTЩѡķͲ⣬ҲӭÿԴ˸ȤĲź͸ԼĿ.1999322գNISTе2AESѡ飬15ѡ㷨۽.Щ㷨۽1999415սʱ15㷨ѡ5.5㷨ѡһ㷨ΪAESԤ2001̨.ΪøĹڶ˽Щѡ㷨ĽļҪЩ㷨Ļ˼·.
1 15AESѡ㷨
1.1 CAST-256㷨
CAST-256㷨ǼôCarlisle Adamsύһѡ㷨.еCAST-128㷨2ݵĻƵģ㷨õṹƹFeistel磬˽ṹصǣֱܹԣͳģFeistelֺ.ֺ֪ĹģһS-еĹģɢĹģ.S-еĹģɢĹģǱȽѵ.ˣƹFeistelɻߴ෽.
CAST-256ֺص㣺
(1) S-еƱ֤нϸߵķԡϵ͵Ĳ־ԡõĸ߽ϸѩԼõĸ߽ףض׼.
(2) áڱΡԿ͡ѭλԿȷÿȦԿظأҿʹּø.
(3) ԲͬȺĻƺЧؼֲĸʣͬҲԼٸ߽ײֹĿ.
еķʾCAST-256еķǰȫ.3֪ĴԼΪ2174ò440CAST-256ѡĴԼΪ21405ݣ߽ײ6ݶ5ϵCAST-256Ϊˣ7.
1.2 CRYPTON㷨
CRYPTON㷨ǺChae Hoon Limύһѡ㷨.㷨õĽṹǴ-û磬˼SQUARE㷨һ뵽һ44ֽھ󣬽ֽھĲֽڴ洦зʽıûееתãȻִԿӷʵֶ128ݵļ.
CRYPTON㷨Ҫʹ¼ֱ任(1) 滻, (2) Ա任кͦ,(3) Կӱ任.ֱ任ɦãУӺͦҹ4ֱ任϶ɣֺżֱֵ任вͬвȡһЩҪΪ˱֤ӽͬ.滻Ϊʵ֡Ƶģʹ88S-S0S1.S-Ǵ344S-ʹһ3Feistelṹģ㣺κ8سxS0(S1x)=S1(S0x)=x.Ա任кͦΪʵ֡ɢƵģɢûSQUARE㷨õɢʺ.
еķʾCRYPTONеķǰȫ.֪Ĳ2128.8CRYPTONѲĸʲ2-160.߽ײCRYPTONİȫûӰ.
1.3 DEAL㷨
DEAL㷨ǼôŲRichard Outerbridgeύĺѡ㷨.õṹһ6ֵFeistel磬ֺDES㷨.˼DES.ѡõֺǳӣǵٶ⣬ˣDEALܶ࣬6ֻ8.6ֵFeistel룬ҵһΪ05ֲ֣ô˲ֹDEAL270ѡġ2121μܼ264洢.
1.4 DFC㷨
DFC㷨ǻVauenay8,9ݵĿعƵ.õ8ֵFeistelṹ.F£
F(a,b)=CP(((aX+b)mod (264+13))mod264).
X64룬Ki=(a,b)Կ.
CPû£
CP(Y)=(((YrRT(trunc6(Yl))|(YrKC))+KD)mod264.
֤CPûѧԷǳ.ˣDFCİȫȫԿǶ뷽ʽ.
1.5 E2㷨
E2㷨ձNTT˾ύһѡ㷨õṹFeistel. Feistelһ㲻ֻ֮һֱ뵽1ֵֺͬʱֻһֱ뵽һֵֺ.ζѡĹʱ߿ԿƵ1ֺһֵֺ룻֪Ĺʱ߿֪1ֺһֵֺ.ʵʾ飬ǿȱȥFeistel1ֺһֵԿ.ΪˣE2㷨˳ʼ任ձ任ֱΪITFTԿ֮.
ֺƲ2ȦSPNṹ.˽ṹ3ɣ1Ϊ1Բ㣬2Ϊ˫Բ㣬3Ϊ2Բ.Բ8еS-йɣǡ.ԲһԱ任Pǡɢ.ֹֺŵǿԸֺѲָʺƫĽ.
S-еѡȡʹĲ־ԺƫֱΪ2-4.672-3.19Ϊ7.Ա任Pķ֧Ϊ5.ˣ8E2㷨ѲʺԱƽƫֱΪ2-93.42-44.8.12E2㷨ѲʺԱƽƫֱΪ2-1402-66.7.˿˵E2㷨еķߵ.
1.6 FROG㷨
FROG㷨һַṹ㷨˼ͨڲԿش̣ҲǾܲ߶ʵִйи˽⣬Ӷκι.FROGԿǿɱģ5ֽڵ125ֽ.8FROGҪڲԿ2 304ֽڣˣFROGԿŵĹȽϴ.
FROG·У
(1) ԴԼ2-33ԿòFROGѡΪ258.
(2) ԴԼ2-31.8ԿFROG֪Ϊ256.
(3) ԴԼ2-31.8ԿΨĵFROGΪ264.
(4) FROGĽܺȼܺö.ԽܺвԼ2-33ԿѡΪ236.
Ƕ϶,FROG㷨ѡAES.
1.7 HPC㷨
HPC㷨ķ鳤ȺԿȶģ0ػ.HPC512ؿѡĶԿ,SPICEһԿÿԿֵһͬļ.HPC5ͬɣһܵϢĳ.ÿʹԼԿչЩԿչͨԿαÿ25664.еԿչʹͬһ㷨ֻгʼֵͬ.
HPCڲʹ޷ŵ64֣κοɱֵԿȡĳȻĳȶԶ64ֱʾܺһʵ.SPICE8ֵָ.ҪʹõĲģӡģģˡλ.
ΪHPCƵ÷ǳãƺĻԭûκοɹοļֵܳ䵱AESҲֹͬ۵.
1.8 LOKI97㷨
LOKI97㷨õFeistelṹLOKIϵ²Ʒ.LOKI89BihamShamir10ݽ˷ȻLOKI89ټֱܲĹȫ16ֵLOKI89ȴĹ.Tokita SorimachiMatsui11ݽ12ϵLOKI91ǰȫ.LOKI97ѡȡS-еķԷǳ.ֺĹ£
ֺf:F642F642F642,
f(A,B)=Sb(P(Sa(E(KP(A,B))),B).
KP(A,B)һ򵥵Կû.EһչE64вһ96ֵ.SaɺS1ͺS2ùɣSa=S1,S2,S1,S2,S2,S1,S2,S1.PһԱ任.SbɺS1ͺS2ùɣSb=S2,S2,S1,S1,S2,S2,S1,S1ݣһԿ.
ȻLOKI97LOKIϵ²ƷֺƺҲܸӣ֣LOKI97Ǻܴ.òѡΪ256.ĳЩԿ֪Ϊ250.
1.9 MAGENTA㷨
MAGENTA㷨ĺĲԿٹ任Ϊģ㷨˼ӦһЩӲЧʵֵļ͸ļ.MAGENTAõ6ֻ8ֵFeistelṹ.MAGENTA㷨Կ̫򵥣Կֳ64صӿ飬ڼܹжԳʹ.ΪMAGENTA㷨ȱݣԸMAGENTAķ˷ѡΪ264.
1.10 MARS㷨
MARS㷨IBM˾ṩһѡ㷨صǳʹ÷ƽFeistel.Ϊ˱֤ܺͽܵǿ൱MARSɽṹƵ.MARSļ㷨6ɣ1Կӣ2ǲԿƵ8ǰڻ㣬3Կµ8ǰڼܱ任4Կµ8ֺڼܱ任5ǲԿƵ8ֺڻ㣬6Կ.
Ե1һֵĴмֲһһ㶼Ȳ²⼸ԿȻȥĵ1һ֣ٽʩʣµ.ڴˣMARSʹǰڻͺڻ.Ե1һԴΪǺбҪ.,MARSùڸӣ16֣ܻӰٶ.
MARSS-ǸݹԭƵģʽɲ⣬ʹõĲֺԣųԤŵ.
EMARSĺģ32صX332ص(Y2,Y1,Y0),
Y2=ROL(ROL(X,13)*k,10),
Y1=ROL(X+k),ROR(Y2,5),
Y0=ROL(S(X+k)ROL(Y2,5)Y2,Y2),
S932ĺ,kkԿROR(X,n)ʾXתnأROL(X,n)ʾXתn.
Eͨʹģ232˺תðȫ.ģ232˵Ҫǿڳ˻ĸߴαأΪЩصÿһԷԷʽбأЩмǿĲԣ,Eó˻ĸߴαΪתѭ,ʹMARSõĿַ.ֵע,˷ĴױȽϸߣʱʱ2Ӳʵִ׸.ʹģ232ˣʹMARSԿ.
еķMARSеߵ.ȱԿٶԽ.
1.11 RC6㷨
RC6㷨RC5㷨ĻƵ.֪RC5һǳ㷨صǴʹѭ.RC6̳Щŵ.ΪNISTҪ󣬼鳤Ϊ128أRC6ʹ4Ĵӽ32ص˷κB(2B+1)(ӦΪD(2D+1))ڼǿɢ.
RC6ķɹ£
(1) RC6ùƺûԿ.
(2) RC6вֺ12ݣݳе.
ֵעǣʹ32ص˷RC6ٶȿܵӰ. 
1.12 Rijndael㷨
Rijndael㷨ǱʱJoan DaemenVincent Rijmenύһѡ㷨.㷨ԭSquare㷨Ʋǿ켣(wide trail strategy)13.켣ԲַԷģ14ݣŵǿԸ㷨ѲĸԼԱƽƫĽ磻ɴ˿Է㷨.
RijndaelõǴ/û.ÿһ3ɣԻϲ㣺ȷ֮ϵĸ߶ɢԲ㣺16S-вöɣ𵽻ãԿӲ㣺Կ򵥵м״̬.S-ѡȡGF(28)еĳ˷㣬Ĳ־Ժƫﵽ.
Rijndaelİȫ£
4RijndaelѲĸʼԱƽƫֱΪ2-1502-768RijndaelѲĸʼԱƽƫֱΪ2-3002-151
SquareSquare㷨һֹRijndaelҲõ.ʾ,7ϵRijndaelԡSquareߵ.
1.13 SAFER+㷨
SAFER+㷨ǻSAFERϵ㷨15ģˣİȫԿ˵ǾʱĿ.,SAFER+㷨нʹֽ㣬ڴС.ˣSmartȷӦǺƵ.SAFER+㷨һ/Ա任.ԲʹָͶ㣬ѡɣ(1) ʹѧеĳúŵĿܣ(2) ֤ûķ֧ѡȡĲͬķԽ׵ֲ.SAFER+ǰSAFERϵ㷨16ݵҪĽ֮һڿԱ任MѡȡϣǰPHTõö࣬MѡȡʹSAFER+Ժܺõؿַ.
ͨSAFER+ое5С2-128.6ֵֻSAFER+Բߵ.SAFER+̳SAFERϵ㷨ֿ3SAFER+Ϳɵֿ.
۴ӽṹٶȣǴӰȫԷ SAFER+㷨һܺõ㷨.
1.14 SERPENT㷨
SERPENT㷨AndersonBihamKundsenύһѡ㷨.õǴ/û.SERPENT汾У17ݣʹDESS-УĿʹûκ.SERPENTƵı֤ΪS-Լ򵥵ġȷķʽ.SERPENTļ㷨3ɣ1ǳʼû232ֵļܲÿһְԿ㡢S-мԱ任3ĩβû.
SERPENTS-Ǿʵ4û
(1) ÿһһӽ0.25ĸʣ1任Բᵼһ1ص任.
(2) ÿԱƽһڷΧ0.50.25ڵĸʣҵ1뵥1ԹϵһڷΧ0.50.125ڵĸ.
(3) ÿ֧ĴΪ3.
Ա任ѡȡԭһΪ˼ѩЧΪ˱ڷ.֤SERPENTֿ֪ܵйSERPENTDESȫ.ĿǰûжSERPENTĽһ.
1.15 Twofish㷨
Twofish㷨Bruce Schneierύһѡ㷨.ṹһ16ֵFeistelṹҪصS-Կ.Twofishļܷ3:1ǳʼ׻216ֵļܣڵiУRi,0,Ri,1,Ri,2,Ri,3Ϊ432ص룬432صRi+1,0,Ri+!,1,Ri+!,2,Ri+1,3ʽӼ㣺
Ri+1,0=(g(Ri,0)+g(Ri,1<<<8)+K2i+8)Ri,2>>>1,
Ri+1,1=(g(Ri,0)+2g(Ri,1<<<8)+K2i+9)(Ri,3<<<1),
Ri+1,2=Ri,0,
Ri+1,3=Ri,1,
,+ģ232ӣ<<<1ʾת1أ>>>1ʾת1.3ĩβ׻.
gTwofishĺģgĹУõ̶88ûq0q1.q0q1ֱ444ût0,t1,t2,t3,ù̶.
TwofishķĿǰѹ222.5ѡĺ251ļ5Twofish.
2 
AESĿǰƷȻ벻ɵģʽ,ڼ϶ûʲô.15AESѡ㷨1999꽫ܼңȤĶעйر.
ĵоõȻѧĿΪ69673016.
оõȻѧ.,Ů,1966,ʿ,ҪоΪۺӦѧ.ǹ,1965,оԱ,ҪоΪϢȫۺͼ.˹,1939,оԱʿʦҪоΪϢȫۺͼ.
ͨѶϵ:˹100080,йѧԺо
ߵλйѧԺо100080
йѧԺϢȫоġ100080
ο
1AES Candidate Algorithms. http:csrc.nist.gov/encryption/aes/aes_home.htm#candidates
2Youssef A, Chen Z, Tavares S. Construction of highly nonlinear injective S-boxes with application to CAST-like encryption algorithm. In: Proceedings of the Canadian Conference on Electrical and Computer Engineering(CCECE'97), 1997. 330333
3Matsui Mitsuru. Linear cryptanalysis method for DES cipher. Lecture Notes in Computer Science, Springer-Verlag, 1993,765:368397
4Biham E, Shamir A. Differential Cryptanalysis of Data Encryption Standard. New York: Springer-Verlag, 1993
5Lee J, Heys H, Tavares S. Resistance of a CAST-like encryption algorithm to linear and differential cryptanalysis. Designs, Codes and Cryptography, 1997,12(3):267282
6Knudsen L R. Truncated and higher order differentials. Fast Software Encryption, Lecture Notes in Computer Science, Springer-Verlag, 1995,1008:196211
7Moriai S, Shimoyama T, Kaneko T. Higher order differential attack of a CAST cipher. Fast Software Encryption, Proceedings of 5th International Workshop. Springer-Verlag, 1998. 1731
8Vaudenay S. Provable security for block ciphers by decorrelation. In: STACS 98, Paris, France, Lecture Notes in Computer Science, Springer-Verlag, 1998,1373:249275
9Vaudenay S. The Decorrelation Technique Homepage. URL:http:www.dmi.ens.fr/vaudenay/decorrelation.html
10Biham E, Shamir A. Differential Cryptanalysis Snefru. Kharfe, REDOC-II, LOKI and Lucifer. Lecture Notes in Computer Science, Springer-Verlag, 1991,576:156171
11Tokita Toshio, Sorimachi Tohru, Matsui Mitsuru. Linear cryptanalysis of LOKI and S2DES. Lecture Notes in Computer Science, Springer-Verlag, 1994,917:363366
12Kaliski B S, Yin Y L. On differential and linear cryptanalysis of the RC5 encrytion algorithm. Advances in Cryptology-Crypto'95. Lecture Notes in Computer Science, 1995,963:171184
13Daemen J, Knudsen L, Rijmen V. The block cipher square, fast software encryption. In: Proceedings of the 4th International Workshop. Springer-Verlag, 1997. 469472
14Daemen J. Cipher and hash function design stategies based on linear and differential cryptanalysisPh.D. Thesis, K.U.Leuven, 1995
15Harpes C, Massey J. Partitioning cryptanalysis, fast software encryption. In: Proceedings of the 4th International Workshop. Springer-Verlag, 1997. 1327
16Massey J. SAFER K-64: a byte-oriented block-ciphering algorithm. Fast Software Encryption, Lecture Notes in Computer Science. 1994,809:117
17Jakobsen T, Knudsen L. The interpolation attack on block ciphers, fast software encryption. In: Proceedings of 4th International Workshop. Springer-Verlag, 1997. 2840
(1999-02-12ո)
