254 (2001)

[MW99] Maurer, U.M., Wolf, S.: The relationship between breaking the dif¬e-hellman proto-

col and computing discrete logarithms. SIAM J. Comput. 28(5), 1689“1721 (1999)

[MW00] Maurer, U.M., Wolf, S.: The dif¬e-hellman protocol. Des. Codes Cryptogra-

phy 19(2/3), 147“171 (2000)

[OO91] Ohta, K., Okamoto, T.: A digital multisignature scheme based on the ¬at-shamir

scheme. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS,

vol. 739, pp. 139“148. Springer, Heidelberg (1993)

[OO99] Ohta, K., Okamoto, T.: Multisignature schemes secure against active insider attacks.

IEICE Transactions on Fundamentals of Electronics Communications and Com-

puter Sciences E82-A(1), 21“31 (1999)

[PKC00] PKCS#10. Certi¬cation request syntax standard. In: RSA Data Security, Inc. (2000)

[PS00] Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signa-

tures. J. Cryptology 13(3), 361“396 (2000)

[RY07] Ristenpart, T., Yilek, S.: The power of proofs-of-possession: Securing multiparty

signatures against rogue-key attacks. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS,

vol. 4515, pp. 228“245. Springer, Heidelberg (2007)

[Sho00] Shoup, V.: Practical threshold signatures. In: Preneel, B. (ed.) EUROCRYPT 2000.

LNCS, vol. 1807, pp. 207“220. Springer, Heidelberg (2000)

Using Normal Bases for Compact Hardware

Implementations of the AES S-Box

Svetla Nikova1 , Vincent Rijmen1,2 , and Martin Schl¨¬er2

a

1

Katholieke Universiteit Leuven, Dept. ESAT/SCD-COSIC,

Kasteelpark Arenberg 10, B-3001 Heverlee, Belgium

2

Institute for Applied Information Processing and Communications (IAIK),

Graz University of Technology, In¬eldgasse 16a, A-8010 Graz, Austria

martin.schlaeffer@iaik.tugraz.at

Abstract. The substitution box (S-box) of the Advanced Encryption

Standard (AES) is based on the multiplicative inversion s(x) = x’1 in

GF(256) and followed by an a¬ne transformation in GF(2). The S-box

is the most expansive building block of any hardware implementation of

the AES, and the multiplicative inversion is the most costly step of the

S-box transformation. There exist many publications about hardware

implementations of the S-box and the smallest known implementations

are based on normal bases. In this paper, we introduce a new method

to implement the multiplicative inversion over GF(256) based on normal

bases that have not been considered before in the context of AES imple-

mentations.

Keywords: AES, S-box, hardware implementation, normal basis.

1 Introduction

The ¬rst e¬cient hardware implementation of the multiplicative inversion in

GF(256) has been proposed by Rijmen [9] and ¬rst imlemented by Rudra et al.

[10] and Wolkerstorfer et al. [13]. They decompose the elements of GF(256) into

polynomials of degree 2 over the sub¬eld GF(16). In the next step, the elements

of GF(16) are further decomposed into polynomials of degree 4 over GF(2).

The resulting operations in GF(2) work on bit-level and can be implemented in

hardware using simple gates.

Satoh et al. [11] and further Mentens et al. [6] use the di¬erent tower ¬eld

decomposition in their implementation. They ¬rst start by decomposing the ele-

ments of GF(256) into polynomials over GF(16) as well. But then the elements

of the ¬eld GF(16) are further decomposed into polynomials over the sub¬eld

GF(4) before implementing the ¬nal operations in GF(2). In all these approaches

the ¬eld elements are represented by using polynomial bases. In contrast, Can-

right has been able to further reduce the size of the S-box computation by using

normal bases at all levels of the tower ¬eld decomposition [3,2].

In this paper, we propose a new way to implement the inversion of the AES S-

box. We use normal bases as in the approach of Canright but do not decompose

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 236“245, 2008.

c Springer-Verlag Berlin Heidelberg 2008

Using Normal Bases for Compact Hardware Implementations 237

the elements of GF(16) into elements of GF(4). Table 1 illustrates the relation

between the four mentioned approaches. We show that our implementation of the

AES S-box can be at least as compact as the one proposed by Canright when

counting the required number of gates. Which of the approaches is the best

depends not only on the used hardware technology, but also on the application

of the circuit and the resulting hardware criteria like size, timing, or power

consumption [12]. Therefore, we cannot make an unambiguous ranking of the

di¬erent implementations, but we are convinced that our alternative has its

merits, already simply because it increases the available options of a hardware

designer.

Table 1. Four approaches to decompose elements of GF(256) into elements of smaller

sub¬elds

Decomposition of ¬eld elements

GF(256) ’ GF(16) ’ GF(2) GF(256) ’ GF(16) ’ GF(4) ’ GF(2)

Polynomial Rijmen [9], Rudra et al. [10], Satoh et al. [11],

bases Wolkerstorfer et al. [13] Mentens el al. [6]

Normal bases this paper Canright [3,2]

The paper is organized as follows. In Section 2 we brie¬‚y recall some properties

of normal bases which are relevant for the implementation of the AES S-box.

Subsequently, in Section 3 we study extensively the di¬erent normal bases of

GF(16) over GF(2) and discuss the impact of the choice of basis on the structure

and complexity of the multiplicative inversion over GF(16). Additional hardware

related considerations are made in Section 4 and we conclude in Section 5

2 Normal Bases

In this section we brie¬‚y summarize some properties of normal bases over ¬nite

¬elds [5]. The ¬nite ¬eld GF(2mp ) is isomorphic to a p-dimensional vector space

over GF(2m ). This implies that it is possible to construct a basis for GF(2mp ).

A basis consists of p elements β0 , β2 , . . . , βp’1 ∈ GF(2mp ) such that all elements

of GF(2mp ) can be written as a linear combination of the elements βj , with

all coe¬cients elements of GF(2m ). As in all vector spaces, there are many

di¬erent choices possible for the basis, and the choice of basis may in¬‚uences the

complexity to describe transformations on the vector space.

2.1 Construction

A normal basis is constructed by choosing an element θ ∈ GF(2mp ) and setting

mj

βj = θ2 . Not all elements of GF(2mp ) result in a basis, but there exist always

some suitable elements. Let now

p’1

mj

cj ∈ GF(2m ).

cj θ 2

x= ,

j=0

238 S. Nikova, V. Rijmen, and M. Schl¨¬er

a

We raise both sides to the power 2m . This operation is linear over GF(2mp ) and

corresponds to the identity transformation for all elements in GF(2m ). Then we

obtain

p’1 p’1 p’1

m m mj m m(j+1) mj

x2 = (cj )2 (θ2 )2 = cj θ 2 cj’1 θ2

= .

j=0 j=0 j=0

In words, this corresponds to the following property.

Property 1 ([5]). If the elements of the ¬nite ¬eld GF(2mp ) are represented by

p-dimensional vectors over GF(2m ) using a normal basis, then raising an element

to the power 2m corresponds to rotating the coordinates of the element by one

position.

Let now m = 1 and consider the inversion map used in the AES S-box. We

denote this map by s. Then we have:

s(0) = 0,

s(x) = x’1 , x = 0.

Equivalently, we can write: s(x) = x254 . Clearly, s(x2 ) = x508 = (s(x))2 . Hence

we obtain the following property.

Property 2. If the elements of the ¬nite ¬eld GF(2mp ) are represented in a nor-

mal basis, then the inversion map s(x) is rotation invariant: