A Compact Rijndael Hardware Architecture with S-Box OptimizationIntroductionRijndael AlgorithmData Path ArchitectureData Path Sharing between Encryption and DecryptionS-Box Sharing with Key ExpanderFactoring in MixColumns and InvMixColumnsS-Box OptimizationStructure of New S-BoxMultiplicative Inversion over A New Composite FieldGenerating Isomorphism FunctionsImplementation Results of the S-BoxPerformance Comparison in ASICsConclusionAcknowledgementsReferencesA Compact Rijndael Hardware Architecturewith S-Box OptimizationAkashi Satoh, Sumio Morioka, Kohji Takano, and Seiji MunetohIBM Research, Tokyo Research Laboratory, IBM Japan Ltd., 1623-14,Shimotsuruma, Yamato-shi, Kanagawa 242-8502, Japan{akashi,e02716,chano,munetoh}@jp.ibm.comAbstract. Compact and high-speed hardware architectures and logicoptimization methods for the AES algorithm Rijndael are described.Encryption and decryption data paths are combined and all arithmeticcomponents are reused. By introducing a new composite field, the S-Boxstructure is also optimized. An extremely small size of 5.4 Kgates is ob-tained for a 128-bit key Rijndael circuit using a 0.11-µm CMOS standardcell library. It requires only 0.052 mm2of area to support both encryp-tion and decryption with 311 Mbps throughput. By making effective useof the SPN parallel feature, the throughput can be boosted up to 2.6Gbps for a high-speed implementation whose size is 21.3 Kgates.1 IntroductionDES (Data Encryption Standard) [14,1], which is a common-key block cipherfor US federal information processing standards, has also been used as a defacto standard for more than 20 years. NIST (National Institute of StandardTechnology) has selected Rijndael [2] as the new Advanced Encryption Standard(AES) [13]. Many hardware architectures for Rijndael were proposed and theirperformances were evaluated by using ASIC libraries [8,18,10,9] and FPGAs [3,17,6,11,5]. However, they are simple implementations according to the Rijndaelspecification, and none are yet small enough for practical use. The AES has to beembeddable not only in high-end servers but also in low-end consumer productssuch as mobile terminals. Therefore, sharing and reusing hardware resources,and compressing the gate logic are indispensable to produce a small Rijndaelcircuit.The SPN structure of Rijndael is suitable for highly parallel processing, butit usually requires more hardware resources compared with the Feistel structureused in many other ciphers developed after DES. This is because, all data isencoded in each round of Rijndael processing, while only half of data is processedat once in DES. In addition, Rijndael has two separate data paths for encryptionand decryption.In this paper, we describe a compact data path architecture for Rijndael,where the hardware resources are efficiently shared between encryption and de-cryption. The key arithmetic component S-Box has been implemented usingC. Boyd (Ed.): ASIACRYPT 2001, LNCS 2248, pp. 239–254, 2001.c Springer-Verlag Berlin Heidelberg 2001240 A. Satoh et al.look-up table logic or ROMs in the previous approaches, which requires a lotof hardware support. Reference [16] proposed the use of composite field arith-metic to reduce the computation cost of the S-Box, but no detailed hardwareimplementation was provided. Therefore, we propose a methodology to optimizethe S-Box by introducing a new composite field, and show its advantages incomparison to the previous work.2 Rijndael AlgorithmFig. 1 shows a Rijndael encryption process for 128-bit plain text data string anda 128-bit secret key, with the number of rounds set to 10. These numbers areused throughout this paper, including for our hardware implementation. Eachround and the initial stage requires a 128-bit round key, and thus 11 sets of roundkeys are generated from the secret key. The input data is arranged as a 4 × 4matrix of bytes. The primitive functions SubBytes, ShiftRows and MixColumnsare based on byte-oriented arithmetic, and AddRoundKey is a simple 128-bitwiseXOR operation.SubBytes is a nonlinear transformation that uses 16 byte substitution ta-bles (S-Boxes). An S-Box is the multiplicative inverse of a Galois field GF (28)followed by an affine transformation. In the decryption process, the affine trans-formation is executed prior to the inversion. The irreducible polynomial used bya Rijndael S-Box ism(x)=x8+ x4+ x3+ x +1. (1)ShiftRows is a cyclic shift operation of the last three rows by different offsets.MixColumns treats the 4-byte data in each column as coefficients of a 4-termpolynomial, and multiplies the data modulo x4+ 1 with the fixed polynomialgiven byc(x)={03}x3+ {01}x2+ {01}x + {02}. (2)In the decryption process, InvMixColumns multiplies each column with the poly-nomialc−1(x)={0B}x3+ {0D}x2+ {09}x + {0E} (3)and InvShiftRows shifts the last three rows in the opposite direction fromShiftRows.The key expander in Fig. 1 generates 11 sets of 128-bit round keys from one128-bit secret key by using a 4-byte S-Box. These round keys can be prepared onthe fly in parallel with the encryption process. In the decryption process, thesesets of keys are used in reverse order. Therefore, all keys have to be generated andstored in registers in advance, or the final round key in the encryption processhas to be pre-calculated for on-the-fly key scheduling. Because the first methodrequires the equivalent of a 1,408-bit register (128 bits × 11), and is not suitableA Compact Rijndael Hardware Architecture with S-Box Optimization 24188 8SubBytesMixColumnsAddRoundKeySubBytesShiftRowsAddRoundKeySubBytesShiftRowsAddRoundKey88 8AddRoundKey128-bit 11round keysa00a10a20a30ab00a01 03aa10a11 13aa20a21 23aa30a31 33a00 01 0310 11 1320 21 2330 31 33bbbb bbb bbb bajS-Box0aj1aj2aj3bj0bj1bj2bj3c()a00 02a01a03aa10a11 13aa20 22a21a23aa30 32a31a33a12aa00 02a01a03a10a20a21a31a30a32aleft rotation by 1left rotation by 2left rotation by 311000110+a01 03aa11 13aa21 23aa31 33a02a22a32aaijb00 0201 0310 1211 1320 2221 2330 3231 33bbbbbbbbbbbbbbbbijno shifta00a10a20a30a01 03aa11 13aa21 23aa31 33a02a22a32ak00 0201 0310 1211 1320 2221 2330 3231 33kkkkkkkkkkkkkkk12ab00 0201 0310 1211 1320 2221 2330 3231 33bbbbbbbbbbbbbbb=xbij=1000111111111000011111000011111000011111110001111110001111110001MixColumnsShiftRowsEncryption Block32S-Box<<8S-Box<<8323232S-Box<<8Rcon[1]Rcon[9]Rcon[10]Key Expander128-bit plain text128-bit cipher textaij-1128-bit secret keyFig. 1. Encryption process of Rijndael algorithmfor compact hardware,