1 Introduction2 GF Arithmetic and Composite Fields 3 Slicing Techniques 3.1 Encrypting without Chaining4 Rijndael in a Composite Field 5 Optimizations 6 Finding a Transform 7 Performance AcknowledgmentsReferencesAppendix:Our Rijndael CiruitEfficient Rijndael Encryption Implementationwith Composite Field ArithmeticAtri Rudra1, Pradeep K. Dubey1, Charanjit S. Jutla2, Vijay Kumar,1,Josyula R. Rao2, and Pankaj Rohatgi21IBM India Research Lab, Block I, Indian Institue of Technology,Hauz Khas, New Delhi, 110016, India{ratri,pkdubey,vijayk}@in.ibm.com2IBM Thomas J. Watson Research Center,P.O.Box 704, Yorktown Heights, NY 10598, U.S.A.{csjutla,jrrao,rohatgi}@watson.ibm.comAbstract. We explore the use of subfield arithmetic for efficient imple-mentations of Galois Field arithmetic especially in the context of theRijndael block cipher. Our technique involves mapping field elements toa composite field representation. We describe how to select a represen-tation which minimizes the computation cost of the relevant arithmetic,taking into account the cost of the mapping as well. Our method resultsin a very compact and fast gate circuit for Rijndael encryption.In conjunction with bit-slicing techniques applied to newly proposed par-allelizable modes of operation, our circuit leads to a high-performancesoftware implementation for Rijndael encryption which offers significantspeedup compared to previously reported implementations.1 IntroductionIn October 2000, the US National Institute of Standards and Technology (NIST)announced that it had selected the Rijndael Block Cipher [3] as the new Ad-vanced Encryption Standard (AES). In addition to being the new standard,Rijndael is a cipher that offers a good “combination of security, performance,efficiency, implementability and flexibility” [20]. It has already attained consid-erable popularity and acceptance. Rijndael is a block cipher with a block size of16 bytes, each of which represents an element in the Galois Field GF (28). Alloperations in Rijndael are defined in terms of arithmetic in this field.Apart from Rijndael, there are several other instances of the use of GaloisField arithmetic in cryptography and coding theory [10]. The efficiency andperformance of such applications is dependent upon the representation of fieldelements and the implementation of field arithmetic. It is common practice toobtain efficiency by careful selection of the field representation [9,10,11]. In par-ticular, it is well-known that the computational cost of certain Galois FieldAs of April 2001, the author can be reached at Amazon.com, 605 5thAve South,Seattle, WA 98104, U.S.A.C¸ .K. Ko¸c, D. Naccache, and C. Paar (Eds.): CHES 2001, LNCS 2162, pp. 171–184, 2001.c Springer-Verlag Berlin Heidelberg 2001172 A. Rudra et al.operations is lower when field elements are mapped to an isomorphic compositefield, in which these operations are implemented using lower-cost subfield arith-metic operations as primitives [11]. Depending upon the computation involvedand the choice of representation, there are costs associated with the mapping andconversion, and a trade-off has to be made between such costs and the savingsobtained. The design task is to carefully evaluate these trade-offs to minimizethe computational cost.In addition to an efficient hardware implementation, a good circuit design isalso useful in obtaining fast software implementations. Using the technique ofbit-slicing [2] a circuit with a small number of gates can be simulated using awide-word processor. Multiple instances of the underlying computation are thusperformed in parallel to exploit the parallelism implicit in a wide-word computer.This technique has been used in [2] to obtain a fast DES implementation.In this paper, we study the use of composite field techniques for Galois Fieldarithmetic in the context of the Rijndael cipher. We show that substantial gainsin performance can be obtained through such an approach. We obtain a compactgate circuit for Rijndael and use its design to illustrate the trade-offs associatedwith design choices such as field polynomials and representations. We use ourcircuit design to obtain a simple and fast software implementation of Rijndaelfor wide-word architectures. The performances of both hardware as well as soft-ware implementations show large gains in comparison with previously reportedperformance figures.The rest of this paper is organized as follows. In Section 2, we detail the map-ping of Galois Field operations to composite field arithmetic. Section 3 outlinesthe data-slicing technique for realizing a highly parallel software implementationfrom a circuit design. In Section 4, we describe the mapping of Rijndael opera-tions to a particular class of composite fields. The selection of field polynomialsand representations and the associated optimizations are discussed in Sections5 and 6 respectively. Finally, in Section 7 we present our results and a compari-son with previously reported performance figures for Rijndael. Drawings of ourRijndael encryption circuit are included in the Appendix.2 GF Arithmetic and Composite FieldsComposite fields are frequently used in implementations of Galois Field arith-metic [9,10,11]. In cases where arithmetic operations rely on table lookups, sub-field arithmetic is used to reduce lookup-related costs. This technique has beenused to obtain relatively efficient implementations for specific operations such asmultiplication, inversion and exponentiation. Much of this work has been aimedat implementation of channel codes. The object has usually been to obtain bettersoftware implementations by using smaller tables through subfield arithmetic.Applications to hardware design (such as [10]) have been relatively infrequent.Our techniques are directed at both hardware and software implementations.We take advantage of the efficiency obtained by the use of subfield arithmetic,not merely in the matter of smaller tables but the overall low-level (gate count)An Efficient Rijndael Encryption Implementation 173complexity of various arithmetic operations. The computation and comparisonof such gains and cost is dependent upon several parameters – the overhead ofmapping between the original and the composite field representations, the na-ture of the underlying computation and its composition in terms of the relativefrequency of various arithmetic operations, and in case of software implemen-tations, the