Main The Design Of Rijndael: The Advanced Encryption Standard (AES)

The Design Of Rijndael: The Advanced Encryption Standard (AES)

,
This is the authoritative guide to Rijndael, the block cipher whose elegance, efficiency, security, and principled design made it the Advanced Encryption Standard (AES), now the most widely applied data encryption technology. The authors developed the Rijndael algorithm and in this book they explain the AES selection process and their motivation in the light of the earlier Data Encryption Standard. They explain their design philosophy and implementation and optimization aspects, and the strength of their approach against cryptanalysis. They support the text with the relevant mathematics, reference code, and test vectors. In this new edition the authors updated content throughout, added new chapters, and adapted their text to the new terminology in use since the first edition. This is a valuable reference for all professionals, researchers, and graduate students engaged with data encryption.
Year:
2020
Edition:
2nd Edition
Publisher:
Springer
Language:
english
Pages:
286
ISBN 10:
3662607689
ISBN 13:
9783662607695
Series:
Information Security And Cryptography
File:
PDF, 2.61 MB
Download (pdf, 2.61 MB)

Most frequently terms

 
 
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
Information Security and Cryptography

Joan Daemen
Vincent Rijmen

The Design
of Rijndael
The Advanced Encryption Standard
(AES)
Second Edition

Information Security and Cryptography

Series Editors
David Basin
Kenny Paterson
Advisory Board
Michael Backes
Gilles Barthe
Ronald Cramer
Ivan Damgård
Andrew D. Gordon
Joshua D. Guttman
Christopher Kruegel
Ueli Maurer
Tatsuaki Okamoto
Adrian Perrig
Bart Preneel

More information about this series at http://www.springer.com/series/4752

Joan Daemen • Vincent Rijmen

The Design of Rijndael
The Advanced Encryption Standard (AES)
Second Edition

Joan Daemen
Digital Security Group
Radboud University Nijmegen
Nijmegen, The Netherlands

Vincent Rijmen
COSIC Group
KU Leuven
Heverlee, Belgium

ISSN 2197-845X (electronic)
ISSN 1619-7100
Information Security and Cryptography
ISBN 978-3-662-60768-8
ISBN 978-3-662-60769-5 (eBook)
https://doi.org/10.1007/978-3-662-60769-5
© Springer-Verlag GmbH Germany, part of Springer Nature 2002, 2020
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of
the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or
information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
The publisher, the authors, and the editors are safe to assume that the advice and information in this
book are believed to be true and accurate at the date of publication. Neither the publisher nor the
authors or the editors give a warranty, expressed or implied, with respect to the material contained herein
o; r for any errors or omissions that may have been made. The publisher remains neutral with regard to
jurisdictional claims in published maps and institutional affiliations.
This Springer imprint is published by the registered company Springer-Verlag GmbH, DE part of
Springer Nature.
The registered company address is: Heidelberger Platz 3, 14197 Berlin, Germany

Foreword

Rijndael was the surprise winner of the contest for the new Advanced Encryption Standard (AES) for the United States. This contest was organized
and run by the National Institute of Standards and Technology (NIST) beginning in January 1997; Rijndael was announced as the winner in October
2000. It was the “surprise winner” because many observers (and even some
participants) expressed scepticism that the US government would adopt as
an encryption standard any algorithm that was not designed by US citizens.
Yet NIST ran an open, international, selection process that should serve
as a model for other standards organizations. For example, NIST held their
1999 AES meeting in Rome, Italy. The five finalist algorithms were designed
by teams from all over the world.
In the end, the elegance, efficiency, security, and principled design of
Rijndael won the day for its two Belgian designers, Joan Daemen and Vincent
Rijmen, over the competing finalist designs from RSA, IBM, Counterpane
Systems, and an English/Israeli/Danish team.
This book is the story of the design of Rijndael, as told by the designers
themselves. It outlines the foundations of Rijndael in relation to the previous
ciphers the authors have designed. It explains the mathematics needed to
understand the operation of Rijndael, and it provides reference C code and
test vectors for the cipher.
Most importantly, this book provides justification for the belief that
Rijndael is secure against all known attacks. The world has changed greatly
since the DES was adopted as the national standard in 1976. Then, arguments about security focused primarily on the length of the key (56 bits).
Differential and linear cryptanalysis (our most powerful tools for breaking
ciphers) were then unknown to the public. Today, there is a large public literature on block ciphers, and a new algorithm is unlikely to be considered
seriously unless it is accompanied by a detailed analysis of the strength of
the cipher against at least differential and linear cryptanalysis.
This book introduces the “wide trail” strategy for cipher design, and
explains how Rijndael derives strength by applying this strategy. Excellent
resistance to differential and linear cryptanalysis follows as a result. High
efficiency is also a result, as relatively few rounds are needed to achieve strong
security.

V

VI

Foreword

The adoption of Rijndael as the AES is a major milestone in the history
of cryptography. It is likely that Rijndael will soon become the most widely
used cryptosystem in the world. This wonderfully written book by the designers themselves is a “must read” for anyone interested in understanding
this development in depth.
Ronald L. Rivest
Viterbi Professor of Computer Science
MIT

Preface

This book is about the design of Rijndael, the block cipher that became
the Advanced Encryption Standard (AES). According to the ‘Handbook of
Applied Cryptography’ [110], a block cipher can be described as follows:
A block cipher is a function which maps n-bit plaintext blocks to nbit ciphertext blocks; n is called the block length. [. . . ] The function
is parameterized by a key.
Although block ciphers are used in many interesting applications, such as
e-commerce and e-security, this book is not about applications. Instead, this
book gives a detailed description of Rijndael and explains the design strategy
that was used to develop it.

Structure of this book
When we wrote this book, we had basically two kinds of readers in mind.
Perhaps the largest group of readers will consist of people who want to read
a full and unambiguous description of Rijndael. For those readers, the most
important chapter of this book is Chap. 3, which gives its comprehensive
description. In order to follow our description, it might be helpful to read
the preliminaries given in Chap. 2. Advanced implementation aspects are
discussed in Chap. 4. A short overview of the AES selection process is given
in Chap. 1.
A large part of this book is aimed at readers who want to know why we
designed Rijndael in the way we did. For them, we explain the ideas and
principles underlying the design of Rijndael, culminating in our wide trail
design strategy. In Chap. 5 we explain our approach to block cipher design
and the criteria that played an important role in the design of Rijndael. Our
design strategy has grown out of our experiences with linear and differential
cryptanalysis, two cryptanalytical attacks that have been applied with some
success to the previous standard, the Data Encryption Standard (DES). In
Chap. 6 we give a short overview of the DES and of the differential and
the linear attacks that are applied to it. Our framework to describe linear
cryptanalysis is explained in Chap. 7; differential cryptanalysis is described
VII

VIII

Preface

in Chap. 8. Finally, in Chap. 9, we explain how the wide trail design strategy
follows from these considerations.
Chap. 10 gives an overview of the published attacks on reduced-round
variants of Rijndael. Chap. 11 gives an overview of ciphers related to Rijndael.
We describe its predecessors and discuss their similarities and differences.
This is followed by a short description of a number of block ciphers that have
been strongly influenced by Rijndael and its predecessors.
In Chap. 12 we show how linear and differential analysis can be applied to
ciphers that are defined in terms of finite field operations rather than Boolean
functions. In Chap. 13 we discuss extensions of differential and linear cryptanalysis. In Chap. 14 we study the probability of differentials and trails over
two rounds of Rijndael, and in Chap. 15 we define plateau trails. To assist
programmers, Appendix A lists some tables that are used in various descriptions of Rijndael, Appendix B gives a set of test vectors, and Appendix C
consists of an example implementation of Rijndael in the C programming
language.

Acknowledgments
This book would not have been written without the support and help of
many people. It is impossible for us to list all people who contributed along
the way. Although we probably will make oversights, we would like to name
some of our supporters here.
First of all, we would like to thank the many cryptographers who contributed to developing the theory on the design of symmetric ciphers, and
from who we learned much of what we know today. We would like to mention
explicitly the people who gave us feedback in the early stages of the design
process: Johan Borst, Antoon Bosselaers, Paulo Barreto, Craig Clapp, Erik
De Win, Lars R. Knudsen and Bart Preneel.
Elaine Barker, James Foti and Miles Smid, and all the other people at
NIST who worked very hard to make the AES process possible and visible.
The moral support of our family and friends, without whom we would
never have persevered.
Brian Gladman, who provided test vectors.
Othmar Staffelbach, Elisabeth Oswald, Lee McCulloch and other proofreaders, who provided very valuable feedback and corrected numerous errors
and oversights.
The financial support of KU Leuven, the Fund for Scientific Research –
Flanders (Belgium), Banksys, Proton World and Cryptomathic is also greatly
appreciated.
November 2001

Joan Daemen and Vincent Rijmen

Preface

IX

Preface to the second edition
This edition contains updates of several chapters as well as four new chapters
(Chaps. 12 to 15). We adapted our text to new terminology that has come into
use since the first edition and removed some material that is now obsolete,
including the original Appendix A (Propagation Analysis in Galois Fields)
and the original Appendix B (Trail Clustering).
We thank Ronan Nugent of Springer for his persistent encouragements to
finalize this second edition. We thank Dave, Eric Bach, Nicolas T. Courtois,
Praveen Gauravaram, Jorge Nakahara Jr., Ralph Wernsdorf, Shengbo Xu
and Uyama Yasumasa for pointing out errors in the first edition of this book.
We thank Bart Mennink for proofreading some of the updates. All remaining
errors and those newly introduced are of course our own.
July 2019

Joan Daemen and Vincent Rijmen

Contents

1.

The Advanced Encryption Standard Process . . . . . . . . . . . . . .
1.1 In the Beginning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 AES: Scope and Significance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Start of the AES Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 The First Round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Evaluation Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2 Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.3 Algorithm and Implementation Characteristics . . . . . . .
1.6 Selection of Five Finalists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1 The Second AES Conference . . . . . . . . . . . . . . . . . . . . . . .
1.6.2 The Five Finalists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 The Second Round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8 The Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
1
2
3
4
4
4
4
5
5
6
7
7

2.

Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Groups, Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3 Fields with a Finite Number of Elements . . . . . . . . . . . .
2.1.4 Polynomials over a Field . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5 Operations on Polynomials . . . . . . . . . . . . . . . . . . . . . . . .
2.1.6 Polynomials and Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.7 Polynomials and Columns . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.8 Functions over Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.9 Representations of GF(pn ) . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 MDS Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Tuple Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Transpositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Iterative Boolean Transformations . . . . . . . . . . . . . . . . . .

9
10
10
11
13
13
14
15
16
17
18
20
20
22
22
23
24
25
26
XI

XII

Contents

2.4 Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.1 Iterative Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2 Key-Alternating Block Ciphers . . . . . . . . . . . . . . . . . . . . . 28
3.

Specification of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Differences Between Rijndael and the AES . . . . . . . . . . . . . . . . .
3.2 Input and Output for Encryption and Decryption . . . . . . . . . .
3.3 Structure of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 The Round Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 The SubBytes Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 The ShiftRows Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.3 The MixColumns Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.4 The Key Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.5 The Rijndael Super Box . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 The Number of Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.1 Design Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.1 Decryption for a Two-Round Rijndael Variant . . . . . . .
3.7.2 Algebraic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.3 The Equivalent Decryption Algorithm . . . . . . . . . . . . . .
3.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31
31
31
33
33
34
37
39
41
41
42
43
44
44
46
46
48
48
50

4.

Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Eight-Bit Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Finite-Field Multiplication . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Thirty-Two-Bit Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 T-Table Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Bitsliced Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Dedicated Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Decomposition of SRD . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Efficient Inversion in GF(28 ) . . . . . . . . . . . . . . . . . . . . . . .
4.3.3 AES-NI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Multiprocessor Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53
53
53
54
55
56
56
59
60
61
61
62
62
63

5.

Design Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1 Generic Criteria in Cipher Design . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.3 Key Agility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.4 Versatility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65
65
65
65
66
66

Contents

XIII

5.1.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Symmetry Across the Rounds . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Symmetry Within the Round Transformation . . . . . . . .
5.3.3 Symmetry in the D-Box . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.4 Symmetry and Simplicity in the S-Box . . . . . . . . . . . . . .
5.3.5 Symmetry Between Encryption and Decryption . . . . . .
5.3.6 Additional Benefits of Symmetry . . . . . . . . . . . . . . . . . . .
5.4 Choice of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2 Data-Dependent Shifts . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Approach to Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Security Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.2 Translation of Security Goals into Modern Security
Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.3 Unknown Attacks Versus Known Attacks . . . . . . . . . . . .
5.5.4 Provable Security Versus Provable Bounds . . . . . . . . . . .
5.6 Approaches to Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1 Nonlinearity and Diffusion Criteria . . . . . . . . . . . . . . . . .
5.6.2 Resistance Against Differential and Linear Cryptanalysis
5.6.3 Local Versus Global Optimization . . . . . . . . . . . . . . . . . .
5.7 Key-Alternating Cipher Structure . . . . . . . . . . . . . . . . . . . . . . . .
5.8 The Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8.1 The Function of a Key Schedule . . . . . . . . . . . . . . . . . . . .
5.8.2 Key Expansion and Key Selection . . . . . . . . . . . . . . . . . .
5.8.3 The Cost of the Key Expansion . . . . . . . . . . . . . . . . . . . .
5.8.4 A Recursive Key Expansion . . . . . . . . . . . . . . . . . . . . . . .
5.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74
75
76
76
76
76
77
79
80
80
80
81
81
82

6.

The Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 The DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83
83
85
87
89

7.

Correlation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1 The Walsh-Hadamard Transform . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Parities and Masks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.2 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.3 Real-Valued Counterpart of a Binary Boolean Function
7.1.4 Orthogonality and Correlation . . . . . . . . . . . . . . . . . . . . .
7.1.5 Spectrum of a Binary Boolean Function . . . . . . . . . . . . .
7.2 Composing Binary Boolean Functions . . . . . . . . . . . . . . . . . . . . .
7.2.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91
91
91
91
92
92
93
95
95

66
66
67
67
68
69
69
69
70
71
71
72
73
73

XIV

Contents

7.3

7.4

7.5
7.6
7.7
7.8
7.9

7.10

7.11
8.

7.2.2 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.3 Disjunct Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . .
Correlation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.1 Equivalence of a Boolean Function and Its Correlation
Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.2 Iterative Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . .
7.3.3 Boolean Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Special Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.1 Addition with a Constant . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.2 Linear Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.3 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.4 Keyed Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Derived Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Truncating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cross-correlation and Autocorrelation . . . . . . . . . . . . . . . . . . . . .
Linear Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.9.1 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.9.2 Key-Alternating Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.9.3 Averaging over All Round Keys . . . . . . . . . . . . . . . . . . . .
7.9.4 The Effect of the Key Schedule . . . . . . . . . . . . . . . . . . . . .
Correlation Matrices and the Linear Cryptanalysis Literature
7.10.1 Linear Cryptanalysis of the DES . . . . . . . . . . . . . . . . . . .
7.10.2 Linear Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95
96
96
97
98
98
100
100
100
100
101
101
103
104
105
106
106
106
107
109
111
111
112
113

Difference Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.1 Difference Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.2 Special Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.2.1 Affine Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.2.2 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.2.3 Truncating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.2.4 Keyed Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.3 Relation Between DP Values and Correlations . . . . . . . . . . . . . . 118
8.4 Differential Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.4.1 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.4.2 Independence of Restrictions . . . . . . . . . . . . . . . . . . . . . . . 120
8.5 Key-Alternating Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.6 The Effect of the Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.7 Differential Trails and the Differential Cryptanalysis Literature122
8.7.1 Differential Cryptanalysis of the DES Revisited . . . . . . 122
8.7.2 Markov Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Contents

9.

XV

The Wide Trail Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.1 Propagation in Key-Alternating Block Ciphers . . . . . . . . . . . . . 125
9.1.1 Linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.1.2 Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . 126
9.1.3 Differences Between Linear Trails and Differential Trails128
9.2 The Wide Trail Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
9.2.1 The γλ Round Structure in Block Ciphers . . . . . . . . . . . 129
9.2.2 Weight of a Trail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
9.2.3 Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9.3 Branch Numbers and Two-Round Trails . . . . . . . . . . . . . . . . . . . 133
9.3.1 Derived Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.3.2 A Two-Round Propagation Theorem . . . . . . . . . . . . . . . . 135
9.4 An Efficient Key-Alternating Structure . . . . . . . . . . . . . . . . . . . . 136
9.4.1 The Diffusion Step θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.4.2 The Linear Step Θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.4.3 A Lower Bound on the Byte Weight of Four-Round
Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.4.4 An Efficient Construction for Θ . . . . . . . . . . . . . . . . . . . . 139
9.5 The Round Structure of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . 140
9.5.1 A Key-Iterated Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9.5.2 Applying the Wide Trail Strategy to Rijndael . . . . . . . . 142
9.6 Constructions for θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.7 Choices for the Structure of I and π . . . . . . . . . . . . . . . . . . . . . . 145
9.7.1 The Hypercube Structure . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.7.2 The Rectangular Structure . . . . . . . . . . . . . . . . . . . . . . . . 147
9.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

10. Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.1 Truncated Differentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2 Saturation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.2 The Basic Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.3 Influence of the Final Round . . . . . . . . . . . . . . . . . . . . . . .
10.2.4 Extension at the End . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.5 Extension at the Beginning . . . . . . . . . . . . . . . . . . . . . . . .
10.2.6 Attacks on Six Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.7 The Herds Attack and Other Extensions . . . . . . . . . . . .
10.2.8 Division Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3 Gilbert-Minier and Demirci-Selçuk Attack . . . . . . . . . . . . . . . . .
10.3.1 The Four-Round Distinguisher . . . . . . . . . . . . . . . . . . . . .
10.3.2 The Attack on Seven Rounds . . . . . . . . . . . . . . . . . . . . . .
10.3.3 The Demirci-Selçuk Attack . . . . . . . . . . . . . . . . . . . . . . . .
10.4 Interpolation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.5 Related-Key Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.5.1 The Key Schedule of Rijndael-256 . . . . . . . . . . . . . . . . . .

149
149
149
150
151
152
153
153
154
154
155
155
155
156
157
157
158
159

XVI

Contents

10.5.2 The Biryukov-Khovratovich Attack . . . . . . . . . . . . . . . . .
10.5.3 The KAS of the Biryukov-Khovratovich Attack . . . . . .
10.6 Biclique Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.7 Rebound Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.8 Impossible-Differential Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.8.1 Principle of the Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.8.2 Application to Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.9 Implementation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.9.1 Timing Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.9.2 Power Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

159
160
162
162
163
163
164
164
164
165
166

11. The Road to Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.1.1 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.1.2 The Round Transformation . . . . . . . . . . . . . . . . . . . . . . . .
11.2 SHARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.3 Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.4 BKSQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

169
169
169
170
171
173
176
179

12. Correlation Analysis in GF(2n ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
12.1 Description of Correlation in Functions over GF(2n ) . . . . . . . . 182
12.1.1 Functions That Are Linear over GF(2n ) . . . . . . . . . . . . . 184
12.1.2 Functions That Are Linear over GF(2) . . . . . . . . . . . . . . 184

12.2 Description of Correlation in Functions over GF(2n ) . . . . . . . 186
n
12.2.1 Functions That Are Linear over GF(2 ) . . . . . . . . . . . . . 187
12.2.2 Functions That Are Linear over GF(2) . . . . . . . . . . . . . . 187
12.3 Boolean Functions and Functions in GF(2n ) . . . . . . . . . . . . . . . 188
12.3.1 Relationship Between Trace Masks and Selection Masks188
n
12.3.2 Relationship Between Linear Functions in GF(2) and
n
GF(2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
12.4 Rijndael-GF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
13. On the EDP and the ELP of Two and Four Rijndael Rounds195
13.1 Properties of MDS Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
13.2 Bounds for Two Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
13.2.1 Difference Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
13.2.2 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
13.3 Bounds for Four Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
13.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

Contents

XVII

205
205
207
207
209

14. Two-Round Differential Trail Clustering . . . . . . . . . . . . . . . . . .
14.1 The Multiplicative Inverse in GF(2n ) . . . . . . . . . . . . . . . . . . . . .
14.2 Bundles in the Rijndael Super Box . . . . . . . . . . . . . . . . . . . . . . .
14.2.1 Differentials, Trails and Trail Cores . . . . . . . . . . . . . . . . .
14.2.2 Bundles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.2.3 Number of Bundles with a Given Number of Active
Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.3 Conditions for a Trail Core to Extend to a Trail . . . . . . . . . . . .
14.3.1 The Naive Super Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.3.2 Sharp Conditions and Blurred Conditions . . . . . . . . . . .
14.4 Number of Trail Cores in a Bundle Extending to a Trail . . . . .
14.4.1 Bundles with One Active S-Box in the First Round . . .
14.4.2 Any Bundle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.4.3 Experimental Verification . . . . . . . . . . . . . . . . . . . . . . . . .
14.5 EDP of a Bundle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.5.1 Multiple Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.5.2 Occurrence in Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.5.3 How Li Makes a Difference . . . . . . . . . . . . . . . . . . . . . . . .
14.6 EDP of a Differential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.6.1 Differentials with Activity Pattern (1110; 1110) . . . . . . .
14.6.2 A Bound on the Multiplicity . . . . . . . . . . . . . . . . . . . . . . .
14.7 Differentials with the Maximum EDP Value . . . . . . . . . . . . . . .
14.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

210
211
211
212
213
213
214
215
216
217
217
218
218
218
219
220
221

15. Plateau Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2 Two-Round Plateau Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2.1 Planar Differentials and Maps . . . . . . . . . . . . . . . . . . . . . .
15.2.2 Plateau Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2.3 Plateau Trails in Super Boxes . . . . . . . . . . . . . . . . . . . . . .
15.3 Plateau Trails over More Than Two Rounds . . . . . . . . . . . . . . .
15.4 Further Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.4.1 Effect of the Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . .
15.4.2 Impact on the DP of Differentials . . . . . . . . . . . . . . . . . .
15.5 Two-Round Trails in Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.5.1 Trails in the Rijndael Super Box . . . . . . . . . . . . . . . . . . .
15.5.2 Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.5.3 Influence of L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.6 Trails over Four or More Rounds in Rijndael . . . . . . . . . . . . . . .
15.7 DP of Differentials in Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.8 Related Differentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.8.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.8.2 Related Differentials and Plateau Trails . . . . . . . . . . . . .
15.9 Determining the Related Differentials . . . . . . . . . . . . . . . . . . . . .
15.9.1 First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

223
223
224
224
226
227
229
230
230
231
231
231
232
234
234
236
236
236
237
239
239

XVIII Contents

15.9.2 For Any Given Differential . . . . . . . . . . . . . . . . . . . . . . . .
15.9.3 For All Differentials with the Same Activity Pattern . .
15.9.4 Second Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.9.5 A Combinatorial Bound . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.10 Implications for Rijndael-Like Super Boxes . . . . . . . . . . . . . . . .
15.10.1 Related Differentials over Circulant Matrices . . . . . . . .
15.10.2 Related Differentials in MixColumns . . . . . . . . . . . . . . . .
15.10.3 Avoiding Related Differentials . . . . . . . . . . . . . . . . . . . . .
15.11 Conclusions and Further Work . . . . . . . . . . . . . . . . . . . . . . . . . .

240
241
241
243
244
244
244
245
246

A. Substitution Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1 SRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Other Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2.1 xtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2.2 Round Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

249
249
252
252
252

B. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.1 KeyExpansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 Rijndael(128,128) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.3 Other Block Lengths and Key Lengths . . . . . . . . . . . . . . . . . . . .

253
253
253
255

C. Reference Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

1. The Advanced Encryption Standard Process

The main subject of this book would probably have remained an esoteric topic
of cryptographic research — with a name unpronounceable to most of the
world — without the Advanced Encryption Standard (AES) process. Therefore, we thought it proper to include a short overview of the AES process.

1.1 In the Beginning . . .
In January 1997, the US National Institute of Standards and Technology
(NIST) announced the start of an initiative to develop a new encryption
standard: the AES. The new encryption standard was to become a Federal
Information Processing Standard (FIPS), replacing the old Data Encryption
Standard (DES) and Triple DES.
Unlike the selection process for the DES, the Secure Hash Algorithm
(SHA-1) and the Digital Signature Algorithm (DSA), NIST had announced
that the AES selection process would be open. Anyone could submit a candidate cipher. Each submission, provided it met the requirements, would be
considered on its merits. NIST would not perform any security or efficiency
evaluation itself, but instead invited the cryptology community to mount
attacks and try to cryptanalyze the different candidates, and anyone who
was interested to evaluate implementation cost. All results could be sent to
NIST as public comments for publication on the NIST AES web site or be
submitted for presentation at AES conferences. NIST would merely collect
contributions, using them as the basis for their selection. NIST would motivate their choices in evaluation reports.

1.2 AES: Scope and Significance
The official scope of a FIPS standard is quite limited: the FIPS only applies
to the US Federal Administration. Furthermore, the new AES would only
be used for documents that contain sensitive but not classified information.
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
J. Daemen, V. Rijmen, The Design of Rijndael, Information Security and Cryptography,
https://doi.org/10.1007/978-3-662-60769-5_1

1

2

1. The Advanced Encryption Standard Process

However, it was anticipated that the impact of the AES would be much larger
than this: for the AES is the successor of the DES, the cipher that ever since
its adoption has been used as a worldwide de facto cryptographic standard
by banks, administrations and industry.
The major factors for the quick acceptance of Rijndael are that it is
available royalty-free, and that it can be implemented easily on a wide range
of platforms without reducing bandwidth in a significant way.

1.3 Start of the AES Process
In September 1997, the final request for candidate nominations for the AES
was published. The minimum functional requirements asked for symmetric
block ciphers capable of supporting block lengths of 128 bits and key lengths
of 128, 192 and 256 bits. An early draft of the AES functional requirements
had asked for block ciphers also supporting block sizes of 192 and 256 bits,
but this requirement was dropped later on. Nevertheless, since the request
for proposals mentioned that extra functionality in the submissions would be
received favorably, some submitters decided to keep the variable block length
in the designs. (Examples include RC6 and Rijndael.)
NIST declared that it was looking for a block cipher as secure as Triple
DES, but much more efficient. Another mandatory requirement was that the
submitters agreed to make their cipher available on a worldwide royalty-free
basis if it were to be selected as the AES. In order to qualify as an official
AES candidate, the designers had to provide:
1. A complete written specification of the block cipher in the form of an
algorithm.
2. A reference implementation in ANSI C, and mathematically optimized
implementations in ANSI C and Java.
3. Implementations of a series of known-answer and Monte Carlo tests, as
well as the expected outputs of these tests for a correct implementation
of their block cipher.
4. Statements concerning the estimated computational efficiency in both
hardware and software, the expected strength against cryptanalytic attacks, and the advantages and limitations of the cipher in various applications.
5. An analysis of the cipher’s strength against known cryptanalytic attacks.
It turned out that the required effort to produce a ‘complete and proper’ submission package would already filter out several of the proposals. Early in the
submission stage, the Cryptix team announced that they would provide Java
implementations for all submitted ciphers, as well as Java implementations

1.4 The First Round

3

of the known-answer and Monte Carlo tests. This generous offer took some
weight off the designers’ shoulders, but still the effort required to compile
a submission package was too heavy for some designers. The fact that the
AES Application Programming Interface (API), which all submissions were
required to follow, was updated twice during the submission stage increased
the workload. Table 1.1 lists (in alphabetical order) the 15 submissions that
were completed in time and accepted.
Table 1.1. The 15 AES candidates accepted for the first evaluation round
Submissions
CAST-256
Crypton
DEAL
DFC
E2
FROG
HPC
LOKI97
Magenta
Mars
RC6
Rijndael
SAFER+
Serpent
Twofish

Submitter(s)
Entrust (CA)
Future Systems (KR)
Outerbridge and Knudsen (USA–DK)
ENS-CNRS (FR)
NTT (JP)
TecApro (CR)
Schroeppel (USA)
Brown et al. (AU)
Deutsche Telekom (DE)
IBM (USA)
RSA (USA)
Daemen and Rijmen (BE)
Cylink (USA)
Anderson, Biham and Knudsen (UK–IL–DK)
Counterpane (USA)

Submitter type
Company
Company
Researchers
Researchers
Company
Company
Researcher
Researchers
Company
Company
Company
Researchers
Company
Researchers
Company

1.4 The First Round
The selection process was divided into several stages, with a public workshop
to be held near the end of each stage. The process started with a submission
stage, which ended on 15 May 1998. All accepted candidates were presented
at The First Advanced Encryption Standard Candidate Conference, held in
Ventura, California, on 20-22 August 1998. This was the official start of the
first evaluation round, during which the international cryptographic community was asked for comments on the candidates.

4

1. The Advanced Encryption Standard Process

1.5 Evaluation Criteria
The evaluation criteria for the first round were divided into three major categories: security, cost and algorithm and implementation characteristics. NIST
invited the cryptology community to mount attacks and try to cryptanalyze
the different candidates, and anyone interested to evaluate implementation
cost. The result could be sent to NIST as public comments or be submitted
for presentation at the second AES conference. NIST collected all contributions and would use these to select five finalists. In the following sections we
discuss the evaluation criteria.
1.5.1 Security
Security was the most important category, but perhaps the most difficult
to assess. Only a small number of candidates showed some theoretical design
flaws. The large majority of the candidates fell into the category ‘no weakness
demonstrated’.
1.5.2 Costs
The ‘costs’ of the candidates were divided into different subcategories. A first
category was formed by costs associated with intellectual property (IP) issues. First of all, each submitter was required to make his cipher available
for free if it were to be selected as the AES. Secondly, each submitter was
also asked to make a signed statement that he would not claim ownership
or exercise patents on ideas used in another submitter’s proposal that would
eventually be selected as the AES. A second category of ‘costs’ was formed
by costs associated with the implementation and execution of the candidates. This covers aspects such as computational efficiency, program size and
working memory requirements in software implementations, and chip area in
dedicated hardware implementations.
1.5.3 Algorithm and Implementation Characteristics
The category algorithm and implementation characteristics grouped a number of features that are harder to quantify. The first one is versatility, meaning
the ability to be implemented efficiently on different platforms. At one end
of the spectrum the AES should fit 8-bit micro-controllers and smart cards,
which have limited storage for the program and a very restricted amount of
RAM for working memory. At the other end of the spectrum the AES should
be implementable efficiently in dedicated hardware, e.g. to provide on-the-fly
encryption/decryption of communication links at gigabit-per-second rates. In

1.6 Selection of Five Finalists

5

between there is the whole range of processors that are used in servers, workstations, PCs, palmtops etc., which are all devices in need of cryptographic
support. A prominent place in this range is taken by the Pentium family of
processors due to its presence in most personal computers.
A second feature is key agility. In most block ciphers, key setup takes
some processing. In applications where the same key is used to encrypt large
amounts of data, this processing is relatively unimportant. In applications
where the key often changes, such as the encryption of Internet Protocol
(IP) packets in Internet Protocol Security (IPSEC), the overhead due to key
setup may become quite relevant. Obviously, in those applications it is an
advantage to have a fast key setup.
Finally, there is the criterion of simplicity, which may even be harder to
evaluate than cryptographic security. Simplicity is related to the size of the
description, the number of different operations used in the specification, the
symmetry or lack of symmetry in the cipher and the ease with which the
algorithm can be understood. All other things being equal, NIST considered
it to be an advantage for an AES candidate to be more simple for reasons of
ease of implementation and confidence in security.

1.6 Selection of Five Finalists
In March 1999, the second AES conference was held in Rome, Italy. The
remarkable fact that a US Government department organized a conference
on a future US Standard in Europe is easily explained. NIST chose to combine
the conference with the yearly Fast Software Encryption Workshop, which
had for the most part the same target audience and was scheduled to be in
Rome.
1.6.1 The Second AES Conference
The papers presented at the conference ranged from crypto-attacks, cipher
cross-analysis, smart-card-related papers, and so-called algorithm observations. In the session on cryptographic attacks, it was shown that FROG,
Magenta and LOKI97 did not satisfy the security requirements imposed by
NIST. For DEAL it was already known in advance that the security requirements were not satisfied. For HPC weaknesses had been demonstrated in a
paper previously sent to NIST. This eliminated five candidates.
Some cipher cross-analysis papers focused on performance evaluation. The
paper of B. Gladman [65], a researcher who had no link with any submission,
considered performance on the Pentium processor. From this paper it became
clear that RC6, Rijndael, Twofish, MARS and Crypton were the five fastest
ciphers on this processor. On the other hand, the candidates DEAL, Frog,

6

1. The Advanced Encryption Standard Process

Magenta, SAFER+ and Serpent appeared to be problematically slow. Other
papers by the Twofish team (Bruce Schneier et al.) [138] and a French team
of 12 cryptographers [10] essentially confirmed this.
A paper by E. Biham warned that the security margins of the AES candidates differed greatly and that this should be taken into account in the
performance evaluation [21]. The lack of speed of Serpent (with E. Biham
in the design team) was seen to be compensated for by a very high margin
of security. Discussions on how to measure and take into account security
margins lasted until after the third AES conference.
In the session on smart cards there were two papers comparing the performance of AES candidates on typical 8-bit processors and a 32-bit processor:
one by G. Keating [78] and one by G. Hachez et al. [69]. From these papers
and results from other papers, it became clear that some candidates simply
did not fit onto a smart card and that Rijndael was by far the best suited
for this platform. In the same session there were some papers that discussed
power analysis attacks and the suitability of the different candidates for implementations that can resist against these attacks [27, 39, 49].
Finally, in the algorithm observations session, there were a number of
papers in which AES submitters re-confirmed their confidence in their submission by means of a considerable amount of formulas, graphs and tables and
some loyal cryptanalysis (the demonstration of having found no weaknesses
after attacks on their own cipher).
1.6.2 The Five Finalists
After the workshop there was a relatively calm period that ended with the
announcement of the five candidates by NIST in August 1999. The finalists
were (in alphabetical order): MARS, RC6, Rijndael, Serpent and Twofish.
Along with the announcement of the finalists, NIST published a status
report [118] in which the selection was motivated. The choice coincided with
the top five that resulted from the response to a questionnaire handed out
at the end of the second AES workshop. Despite its moderate performance,
Serpent made it thanks to its high security margin. The candidates that had
not been eliminated because of security problems were not selected mainly
for the following reasons:
1. CAST-256: comparable to Serpent but with a higher implementation
cost.
2. Crypton: comparable to Rijndael and Twofish but with a lower security
margin.
3. DFC: low security margin and bad performance on anything other than
64-bit processors.

1.8 The Selection

7

4. E2: comparable to Rijndael and Twofish in structure, but with a lower
security margin and higher implementation cost.
5. SAFER+: high security margin similar to Serpent but even slower.

1.7 The Second Round
After the announcement of the five candidates NIST made another open call
for contributions focused on the finalists. Intellectual property issues and
performance and chip area in dedicated hardware implementations entered
the picture. A remarkable contribution originated from NSA, presenting the
results of hardware-performance simulations performed for the finalists. This
third AES conference was held in New York City in April 2000. As in the
year before, it was combined with the Fast Software Encryption Workshop.
In the sessions on cryptographic attacks there were some interesting results but no breakthroughs, since none of the finalists showed any weaknesses that could jeopardize their security. Most of the results were attacks
on reduced-round versions of the ciphers. All attacks presented are only of
academic relevance in that they are only slightly faster than an exhaustive
key search. In the sessions on software implementations, the conclusions of
the second workshop were confirmed.
In the sessions on dedicated hardware implementations attention was paid
to Field Programmable Gate Arrays (FPGAs) and Application-Specific Integrated Circuits (ASICs). In the papers Serpent came out as a consistently
excellent performer. Rijndael and Twofish also proved to be quite suited for
hardware implementation while RC6 turned out to be expensive due to its
use of 32-bit multiplication. Dedicated hardware implementations of MARS
seemed in general to be quite costly. The Rijndael-related results presented at
this conference are discussed in more detail in Chap. 4 (which is on efficient
implementations) and Chap. 10 (which is on cryptanalytic results).
At the end of the conference a questionnaire was handed out asking about
the preferences of the attendants. Rijndael was resoundingly voted to be the
public’s favorite.

1.8 The Selection
On 2 October 2000, NIST officially announced that Rijndael, without modifications, would become the AES. NIST published an excellent 116-page report
in which they summarize all contributions and motivate the choice [117]. In
the conclusion of this report, NIST motivates the choice of Rijndael with the
following words:

8

1. The Advanced Encryption Standard Process

Rijndael appears to be consistently a very good performer in both
hardware and software across a wide range of computing environments regardless of its use in feedback or non-feedback modes. Its
key setup time is excellent, and its key agility is good. Rijndael’s
very low memory requirements make it very well suited for restrictedspace environments, in which it also demonstrates excellent performance. Rijndael’s operations are among the easiest to defend against
power and timing attacks. Additionally, it appears that some defense
can be provided against such attacks without significantly impacting
Rijndael’s performance.
Finally, Rijndael’s internal round structure appears to have good
potential to benefit from instruction-level parallelism.

2. Preliminaries

In this chapter we introduce a number of mathematical concepts and explain
the terminology that we need in the specification of Rijndael (in Chap. 3),
in the treatment of some implementation aspects (in Chap. 4) and when we
discuss our design choices (Chaps. 5–9).
The first part of this chapter starts with a discussion of finite fields, the
representation of their elements and the impact of this on their operations
of addition and multiplication. Subsequently, there is a short introduction
to linear codes. Understanding the mathematics is not necessary for a full
and correct implementation of the cipher. However, the mathematics are
necessary for a good understanding of our design motivations. Knowledge
of the underlying mathematical constructions also helps for doing optimized
implementations. Not all aspects will be covered in detail; where possible, we
refer to books dedicated to the topics we introduce.
In the second part of this chapter we introduce the terminology that
we use to indicate different common types of Boolean functions and block
ciphers.
When the discussion moves from a general level to an example specific
to Rijndael, the text is put in a grey box.
Notation. We use in this book two types of indexing:
subscripts: Parts of a larger, named structure are denoted with subscripts.
For instance, the bytes of a state a are denoted by ai,j (see Chap. 3).
superscripts: In an enumeration of more or less independent objects, where
the objects are denoted by their own symbols, we use superscripts. For
instance the elements of a nameless set are denoted by {a(1) , a(2) , . . . },
and consecutive rounds of an iterative transformation are denoted by
ρ(1) , ρ(2) , . . . (see Sect. 2.3.4).

© Springer-Verlag GmbH Germany, part of Springer Nature 2020
J. Daemen, V. Rijmen, The Design of Rijndael, Information Security and Cryptography,
https://doi.org/10.1007/978-3-662-60769-5_2

9

10

2. Preliminaries

2.1 Finite Fields
In this section we present a basic introduction to the theory of finite fields.
For a more formal and elaborate introduction, we refer to the work of Lidl
and Niederreiter [95].
2.1.1 Groups, Rings and Fields
We start with the formal definition of a group.
Definition 2.1.1. An Abelian group (G, +) consists of a set G and an operation defined on its elements, here denoted by ‘+’:
+ : G × G → G : (a, b) → a + b.

(2.1)

For the group to qualify as an Abelian group, the operation has to fulfill the
following conditions:
closed: ∀ a, b ∈ G : a + b ∈ G
associative: ∀ a, b, c ∈ G : (a + b) + c = a + (b + c)
commutative: ∀ a, b ∈ G : a + b = b + a
neutral element: ∃ 0 ∈ G, ∀ a ∈ G : a + 0 = a
inverse elements: ∀ a ∈ G, ∃ b ∈ G : a + b = 0.

(2.2)
(2.3)
(2.4)
(2.5)
(2.6)

Example 2.1.1. The best-known example of an Abelian group is (Z, +), the
set of integers, with the operation ‘addition’. The structure (Zn , +) is a second
example. The set contains the integer numbers 0 to n − 1 and the operation
is addition modulo n.
Since the addition of integers is the best-known example of a group, usually
the symbol ‘+’ is used to denote an arbitrary group operation. In this book,
both an arbitrary group operation and integer addition will be denoted by
the symbol ‘+’.
Both rings and fields are formally defined as structures that consist of a
set of elements with two operations defined on these elements.
Definition 2.1.2. A ring (R, +, ·) consists of a set R with two operations
defined on its elements, here denoted by ‘+’ and ‘·’. For R to qualify as a
ring, the operations have to fulfill the following conditions:
1. The structure (R, +) is an Abelian group.
2. The operation ‘·’ is closed, and associative over R. There is a neutral
element for ‘·’ in R.

2.1 Finite Fields

11

3. The two operations ‘+’ and ‘·’ are related by the law of distributivity:
∀ a, b, c ∈ R : (a + b) · c = (a · c) + (b · c).

(2.7)

The neutral element for ‘·’ is usually denoted by 1. A ring (R, +, ·) is called
a commutative ring if the operation ‘·’ is commutative.
Example 2.1.2. The best-known example of a ring is (Z, +, ·): the set of integers, with the operations ‘addition’ and ‘multiplication’. This ring is a commutative ring. The set of matrices with n rows and n columns, with the
operations ‘matrix addition’ and ‘matrix multiplication’ is a ring, but not a
commutative ring (if n > 1).
Definition 2.1.3. A structure (F, +, ·) is a field if the following two conditions are satisfied:
1. (F, +, ·) is a commutative ring.
2. For all elements of F , there is an inverse element in F with respect to
the operation ‘·’, except for the element 0, the neutral element of (F, +).
A structure (F, +, ·) is a field iff both (F, +) and (F \{0}, ·) are Abelian groups
and the law of distributivity applies. The neutral element of (F \{0}, ·) is
called the unit element of the field.
Example 2.1.3. The best-known example of a field is the set of real numbers, with the operations ‘addition’ and ‘multiplication.’ Other examples are
the set of complex numbers and the set of rational numbers, with the same
operations. Note that for these examples the number of elements is infinite.
2.1.2 Vector Spaces
Let (F, +, ·) be a field, with unit element 1, and let (V, +) be an Abelian
group. Let ‘’ be an operation on elements of F and V :
 : F × V → V.

(2.8)

Definition 2.1.4. The structure (F, V, +, +, ·, ) is a vector space over F
if the following conditions are satisfied:
1. distributivity:
∀ a ∈ F, ∀ v, w ∈ V : a  (v + w) = (a  v) + (a  w)
∀ a, b ∈ F, ∀ v ∈ V : (a + b)  v = (a  v) + (b  v).

(2.9)
(2.10)

2. associativity:
∀ a, b ∈ F, ∀ v ∈ V : (a · b)  v = a  (b  v).

(2.11)

12

2. Preliminaries

3. neutral element:
∀ v ∈ V : 1  v = v.

(2.12)

The elements of V are called vectors, and the elements of F are the scalars.
The operation ‘+’ is called the vector addition, and ‘’ is the scalar multiplication.
Example 2.1.4. For any field F , the set of n-tuples (a0 , a1 , . . . , an−1 ) forms a
vector space, where ‘+’ and ‘’ are defined in terms of the field operations:
(a1 , . . . , an ) + (b1 , . . . , bn ) = (a1 + b1 , . . . , an + bn )
a  (b1 , . . . , bn ) = (a · b1 , . . . , a · bn ).

(2.13)
(2.14)

A vector v is a linear combination of the vectors w(1) , w(2) , . . . , w(s) if
there exist scalars a(i) such that:
v = a(1)  w(1) + a(2)  w(2) + · · · + a(s)  w(s) .

(2.15)

In a vector space we can always find a set of vectors such that all elements of
the vector space can be written in exactly one way as a linear combination of
the vectors of the set. Such a set is called a basis of the vector space. We will
consider only vector spaces where the bases have a finite number of elements.
We denote a basis by a column vector e:
T

(2.16)
e = e(1) , e(2) , . . . e(n) .
In this expression the T superscript denotes taking the transpose of the row
vector in the right-hand side of the equation. The scalars used in this linear
combination are called the coordinates of x with respect to the basis e:
n
(2.17)
co(x) = x = (c1 , c2 , . . . , cn ) ⇔ x = i=1 ci  e(i) .
In order to simplify the notation, from now on we will denote vector addition
by the same symbol as the field addition (‘+’), and the scalar multiplication
by the same symbol as the field multiplication (‘·’). It should always be clear
from the context what operation the symbols are referring to.
A function f is called a linear function of a vector space V over a field F ,
if it has the following properties:
∀ x, y ∈ V : f (x + y) = f (x) + f (y)
∀ a ∈ F, ∀ x ∈ V : f (ax) = af (x).

(2.18)
(2.19)

The linear functions of a vector space can be represented by a matrix multiplication on the coordinates of the vectors. A function f is a linear function
n
of the vector space GF(p) iff there exists a matrix M such that
n

co(f (x)) = M · x, ∀ x ∈ GF(p) .

(2.20)

2.1 Finite Fields

13

2.1.3 Fields with a Finite Number of Elements
A finite field is a field with a finite number of elements. The number of
elements in the set is called the order of the field. A field with order m exists
iff m is a prime power, i.e. m = pn for some integer n and with p a prime
integer. p is called the characteristic of the finite field.
All finite fields used in the description of Rijndael have characteristic 2.
Fields of the same order are isomorphic: they display exactly the same
algebraic structure, differing only in the representation of the elements. In
other words, for each prime power there is exactly one finite field, denoted
by GF(pn ). From now on, we will only consider fields with a finite number of
elements.
Perhaps the most intuitive examples of finite fields are the fields of prime
order p. The elements of a finite field GF(p) can be represented by the integers
0, 1, . . . , p − 1. The two operations of the field are then ‘integer addition
modulo p’ and ‘integer multiplication modulo p’.
For finite fields with an order that is not prime, the operations addition
and multiplication cannot be represented by addition and multiplication of
integers modulo a number. Instead, slightly more complex representations
must be introduced. Finite fields GF(pn ) with n > 1 can be represented in
several ways. The representation of GF(pn ) by means of polynomials over
GF(p) is quite popular and is the one we have adopted in Rijndael and its
predecessors. In the next sections, we explain this representation.
2.1.4 Polynomials over a Field
A polynomial over a field F is an expression of the form
b(x) = bn−1 xn−1 + bn−2 xn−2 + · · · + b2 x2 + b1 x + b0 ,

(2.21)

x being called the indeterminate of the polynomial, and the bi ∈ F the
coefficients. The degree of a polynomial equals  if bj = 0, ∀j > , and  is the
smallest number with this property. The set of polynomials over a field F is
denoted by F [x]. The set of polynomials over a field F that have a degree
below  is denoted by F [x]| .
In computer memory, the polynomials in F [x]| with F a finite field can
be stored efficiently by storing the  coefficients as a string.
Example 2.1.5. Let the field F be GF(2), and let  = 8. The polynomials can
conveniently be stored as 8-bit values, or bytes:
b(x) → b7 b6 b5 b4 b3 b2 b1 b0 .
Strings of bits are often abbreviated using the hexadecimal notation.

(2.22)

14

2. Preliminaries

Example 2.1.6. The polynomial in GF(2)|8
x6 + x4 + x2 + x + 1
corresponds to the bit string 01010111, or 57 in hexadecimal notation.
2.1.5 Operations on Polynomials
We define the following operations on polynomials.
Addition. Summing of polynomials consists of summing the coefficients
with equal powers of x, where the summing of the coefficients occurs in the
underlying field F :
c(x) = a(x) + b(x) ⇔ ci = ai + bi , 0 ≤ i < n.

(2.23)

The neutral element for the addition 0 is the polynomial with all coefficients
equal to 0. The inverse element of a polynomial can be found by replacing
each coefficient by its inverse element in F . The degree of c(x) is at most the
maximum of the degrees of a(x) and b(x), hence the addition is closed. The
structure (F [x]| , +) is an Abelian group.
Example 2.1.7. Let F be the field GF(2). The sum of the polynomials denoted by 57 and 83 is the polynomial denoted by D4, since:
(x6 + x4 + x2 + x + 1) + (x7 + x + 1)
= x7 + x6 + x4 + x2 + (1 + 1)x + (1 + 1)
= x7 + x6 + x4 + x2 .
In binary notation we have: 01010111 + 10000011 = 11010100. Clearly, the
addition can be implemented with the bitwise XOR instruction.
Multiplication. Multiplication of polynomials is associative (2.3), commutative (2.4) and distributive (2.7) with respect to addition of polynomials.
There is a neutral element: the polynomial of degree 0 and with coefficient
of x0 equal to 1. In order to make the multiplication closed (2.2) over F [x]| ,
we select a polynomial m(x) of degree , called the reduction polynomial.
The multiplication of two polynomials a(x) and b(x) is then defined as the
algebraic product of the polynomials modulo the polynomial m(x):
c(x) = a(x) · b(x) ⇔ c(x) ≡ a(x) × b(x) (mod m(x)).

(2.24)

Hence, the structure (F [x]| , +, ·) is a commutative ring. For special choices
of the reduction polynomial m(x), the structure becomes a field.
Definition 2.1.5. A polynomial d(x) is irreducible over the field GF(p)
iff there exist no two polynomials a(x) and b(x) with coefficients in GF(p)
such that d(x) = a(x) × b(x), where a(x) and b(x) are of degree > 0.

2.1 Finite Fields

15

The inverse element for the multiplication can be found by means of the extended Euclidean algorithm (see, e.g. [110, p. 81]). Let a(x) be the polynomial
we want to find the inverse for. The extended Euclidean algorithm can then
be used to find two polynomials b(x) and c(x) such that:
a(x) × b(x) + m(x) × c(x) = gcd(a(x), m(x)).

(2.25)

Here gcd(a(x), m(x)) denotes the greatest common divisor of the polynomials
a(x) and m(x), which is always equal to 1 iff m(x) is irreducible. Applying
modular reduction to (2.25), we get:
a(x) × b(x) ≡ 1

(mod m(x)),

(2.26)

which means that b(x) is the inverse element of a(x) for the definition of
the multiplication ‘·’ given in (2.24). A polynomial of degree n is primitive
if its roots generate the multiplicative group of GF(pn ), or equivalently, the
multiplicative polynomial x has order pn −1. It can be shown that a primitive
polynomial is irreducible.
Conclusion. Let F be the field GF(p). With a suitable choice for the reduction polynomial, the structure (F [x]|n , +, ·) is a field with pn elements,
usually denoted by GF(pn ).
Example 2.1.8. Consider the field GF(23 ). Let α be a root of x3 + x + 1 = 0.
Then the elements of GF(23 ) can be denoted by 0, 1, α, α+1, α2 , α2 +1, α2 +α
and α2 + α + 1.
2.1.6 Polynomials and Bytes
According to (2.22) a byte can be considered as a polynomial with coefficients
in GF(2):
b7 b6 b5 b4 b3 b2 b1 b0 → b(x)

(2.27)

b(x) = b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0 .

(2.28)

The set of all possible byte values corresponds to the set of all polynomials
with degree less than eight. Addition of bytes can be defined as addition of
the corresponding polynomials. In order to define the multiplication, we need
to select a reduction polynomial m(x).

16

2. Preliminaries

In the specification of Rijndael, we consider the bytes as polynomials.
Byte addition is defined as addition of the corresponding polynomials. In
order to define byte multiplication, we use the following irreducible polynomial as reduction polynomial:
m(x) = x8 + x4 + x3 + x + 1.

(2.29)

Since this reduction polynomial is irreducible, we have constructed a representation for the field GF(28 ). Hence we can state the following: In the
Rijndael specification, bytes are considered as elements of GF(28 ). Operations on bytes are defined as operations in GF(28 ).
Example 2.1.9. In our representation for GF(28 ), the product of the elements
denoted by 57 and 83 is the element denoted by C1, since:
(x6 + x4 + x2 + x + 1) × (x7 + x + 1)
= (x13 + x11 + x9 + x8 + x7 ) + (x7 + x5 + x3 + x2 + x)
+ (x6 + x4 + x2 + x + 1)
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
and
(x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1)
≡ x7 + x6 + 1 (mod x8 + x4 + x3 + x + 1).
2.1.7 Polynomials and Columns
In the Rijndael specification, 4-byte columns are considered as polynomials over GF(28 ), having a degree smaller than four. In order to define the
multiplication operation, the following reduction polynomial is used:
l(x) = x4 + 1.

(2.30)

This polynomial is reducible, since in GF(28 )
x4 + 1 = (x + 1)4 .

(2.31)

In the definition of Rijndael, one of the inputs of the multiplication is a
constant polynomial.
Since l(x) is reducible over GF(28 ), not all polynomials have an inverse
element for the multiplication modulo l(x). A polynomial b(x) has an inverse
if the polynomial x + 1 does not divide it.

2.1 Finite Fields

17

Multiplication with a fixed polynomial. We work out in more detail
the multiplication with the fixed polynomial used in Rijndael.
Let b(x) be the fixed polynomial with degree three:
b(x) = b0 + b1 x + b2 x2 + b3 x3

(2.32)

and let c(x) and d(x) be two variable polynomials with coefficients ci and di ,
respectively (0 ≤ i < 4). We derive the matrix representation of the transformation that takes as input the coefficients of polynomial c, and produces
as output the coefficients of the polynomial d = b × c. We have:
d=b·c

(2.33)

(b0 + b1 x + b2 x2 + b3 x3 ) × (c0 + c1 x + c2 x2 + c3 x3 )
≡ (d0 + d1 x + d2 x2 + d3 x3 ) (mod x4 + 1).

(2.34)

Working out the product and separating the conditions for different powers
of x, we get:
⎡ ⎤ ⎡
⎤ ⎡ ⎤
b0 b3 b 2 b 1
c0
d0
⎢ d 1 ⎥ ⎢ b1 b0 b 3 b 2 ⎥ ⎢ c 1 ⎥
⎢ ⎥ ⎢
⎥ ⎢ ⎥
(2.35)
⎣ d 2 ⎦ = ⎣ b2 b1 b 0 b 3 ⎦ × ⎣ c 2 ⎦ .
d3
b3 b2 b 1 b 0
c3
2.1.8 Functions over Fields
All functions over GF(pn ) can be expressed as a polynomial over GF(pn ) of
degree at most pn − 1:
pn −1

ci ai ,

f (a) =

(2.36)

i=0

with ci ∈ GF(pn ). For simplicity of notation we follow the convention that
00 = 1. Given a table specification where the output value f (a) is given for the
pn different input values a, the pn coefficients of this polynomial can be found
by applying Lagrange interpolation [95, p. 28]. On the other hand, given a
polynomial expression, the table specification can be found by evaluating the
polynomial for all values of a.
The trace function is a function from GF(pn ) to GF(p) that will turn out
to be useful later.
Definition 2.1.6. Let x be an element of GF(pn ). The trace of x over GF(p)
is defined by
2

3

Tr(x) = x + xp + xp + xp + · · · + xp

n−1

.

18

2. Preliminaries

The trace is linear over GF(p):
∀ x, y ∈ GF(pn ) : Tr(x + y) = Tr(x) + Tr(y)
∀ a ∈ GF(p), ∀ x ∈ GF(pn ) : Tr(ax) = aTr(x).
and it can be shown that Tr(x) is an element of GF(p).
2.1.9 Representations of GF(pn )
Finite fields can be represented in different ways.
Cyclic representation of GF(pn ). It can be proven that the multiplicative group of GF(pn ) is cyclic. The elements of this group (different from 0)
can be represented as the pn − 1 powers of a generator α ∈ GF(pn ):
∀x ∈ GF(pn )\{0}, ∃ ax ∈ Zpn −1 : x = αax .

(2.37)

In this representation, multiplication of two non-zero elements corresponds
to addition of their powers modulo pn − 1:
x · y = αax · αay = αax +ay mod p

n

−1

.

(2.38)

Operations such as taking the multiplicative inverse and exponentiation are
trivial in this representation. For addition, however, the vector representation
(discussed next) is more appropriate. In computations involving both addition
and multiplication, one may switch between the two different representations
by means of conversion tables. The table used for conversion from the vector
representation to the cyclic representation is called a log table, and the table
for the inverse conversion is called an alog table. We have used this principle
in our reference implementation (see Appendix C).
Vector space representation of GF(pn ). The additive group of the finite
field GF(pn ) and the n-dimensional vector space over GF(p) are isomorphic.
The addition of vectors in this vector space corresponds to the addition in
GF(pn ). We can choose a basis e consisting of n elements e(i) ∈ GF(pn ). We
depict the basis e by a column vector that has as elements the elements of
the basis:

T
e = e(1) e(2) · · · e(n)
The elements of GF(pn ) can be represented by their coordinates with respect
to this basis. We have
ai e(i) = aT e.

a=

(2.39)

i

where ai ∈ GF(2) are the coordinates of a with respect to the basis e and
where a is the column vector consisting of coordinates ai . The map
n

φe : GF(pn ) → GF(p) : a → φe (a) = a
forms an isomorphism.

2.1 Finite Fields

19

Dual bases. Coordinates of a field element with respect to a basis can be
expressed in terms of the dual basis and the trace map.
Definition 2.1.7. Two bases e and d are called dual bases if for all i and j
with 1 ≤ i, j ≤ n, it holds that
Tr(d(i) e(j) ) = δ(i − j)

(2.40)

with δ(x) the Kronecker delta that is 1 if x = 0 and 0 otherwise. Every basis
has exactly one dual basis. Let e and d be dual bases. Then we have
n

n

ai e(i)

Tr(d(j) a) = Tr d(j)

ai Tr(d(j) e(i) ) = aj .

=
i=1

i=1

Hence the coordinates with respect to basis e can be expressed in an elegant
way by means of the trace map and the dual basis d [95]:


φe (a) = a = Tr(d(1) a) Tr(d(2) a) . . . Tr(d(n) a) .
(2.41)
Applying (2.39) gives:
n

n

Tr(e(i) a)d(i) .

Tr(d(i) a)e(i) =

a=

(2.42)

i=1

i=1

Example 2.1.10. By choosing a basis, we can represent the elements of
GF(23 ) as vectors. We choose the basis e as follows:
e = [α2 + α + 1, α + 1, 1]T .
The dual basis of e can be determined by solving (2.40). It is given by
d = [α, α2 + α, α2 + 1]T .
Table 2.1 shows the coordinates of the elements of GF(23 ), with respect to
both bases.
Boolean functions and functions in GF(pn ). Functions of GF(pn ) can
n
be mapped to functions of GF(p) by choosing a basis e in GF(pn ). Given
f : GF(pn ) → GF(pn ) : a → b = f (a),
we can define a Boolean function f :
n

n

f : GF(p) → GF(p) : a → b = f (a)
where

20

2. Preliminaries

Table 2.1. Coordinates of the field elements, with respect to the bases e and d
a
0
1
α+1
α
α2 + α + 1
α2 + α
α2
2
α +1

a
000
001
010
011
100
101
110
111

ad
000
111
011
100
101
010
110
001

a = [a1 a2 . . . an ]
b = [b1 b2 . . . bn ] ,
and
ai = Tr(ad(i) )
bi = Tr(bd(i) ).
On the other hand, given a Boolean function g, a function over GF(pn ) can
be defined as
a = aT e
b = bT e.
and f = φ−1
So in short, f = φe ◦ f ◦ φ−1
e
e ◦ f ◦ φe . This can be extended to
functions operating on vectors of elements of GF(pn ).

2.2 Linear Codes
In this section we give a short introduction to the theory of linear codes.
For a more detailed treatment, we refer the interested reader to the work
of MacWilliams and Sloane [100]. In a code, message words are represented
by codewords that have some redundancy. In code theory textbooks, it is
customary to write codewords as 1 × n matrices, or row vectors. We will
follow that custom here. In subsequent chapters, one-dimensional arrays will
as often be denoted as n × 1 matrices, or column vectors.
2.2.1 Definitions
The Hamming weight of a codeword is defined as follows.

2.2 Linear Codes

21

Definition 2.2.1. The Hamming weight wh (x) of a vector x is the number
of non-zero components of the vector x.
Based on the definition of Hamming weight, we can define the Hamming
distance between two vectors.
Definition 2.2.2. The Hamming distance between two vectors x and y is
wh (x − y), which is equal to the Hamming weight of the difference of the two
vectors.
Now we are ready to define linear codes.
Definition 2.2.3. A linear [n, k, d] code over GF(2p ) is a k-dimensional subn
space of the vector space GF(2p ) , where any two different vectors of the subspace have a Hamming distance of at least d (and d is the largest number
with this property).
The distance d of a linear code equals the minimum weight of a non-zero
codeword in the code. A linear code can be described by each of the two
following matrices:
1. A generator matrix G for an [n, k, d] code C is a k × n matrix whose rows
form a vector space basis for C (only generator matrices of full rank are
considered). Since the choice of a basis in a vector space is not unique,
a code has many different generator matrices, which can be reduced to
one another by performing elementary row operations. The echelon form
of the generator matrix is the following:


(2.43)
Ge = Ik×k Ak×(n−k) ,
where Ik×k is the k × k identity matrix.
2. A parity-check matrix H for an [n, k, d] code C is an (n − k) × n matrix
with the property that a vector x is a codeword of C iff
HxT = 0.

(2.44)

If G is a generator matrix and H a parity-check matrix of the same code, then
GHT = 0.

(2.45)

Moreover, if G = [I C] is a generator matrix of a code, then H = −CT I is a
parity-check matrix of the same code.
The dual code C ⊥ of a code C is defined as the set of vectors that are
orthogonal to all the vectors of C:
C ⊥ = {x | xyT = 0, ∀ y ∈ C}.



(2.46)

It follows that a parity-check matrix of C is a generator matrix of C ⊥ and
vice versa.

22

2. Preliminaries

2.2.2 MDS Codes
The theory of linear codes addresses the problems of determining the distance
of a linear code and the construction of linear codes with a given distance.
We review a few well-known results.
The Singleton bound gives an upper bound for the distance of a code with
given dimensions.
Theorem 2.2.1 (The Singleton bound). If C is an [n, k, d] code, then
d ≤ n − k + 1.
A code that meets the Singleton bound is called a maximal distance separable (MDS) code. The following theorems relate the distance of a code to
properties of the generator matrix G.
Theorem 2.2.2. A linear code C has distance d iff every d − 1 columns of
the parity-check matrix H are linearly independent and there exists some set
of d columns that are linearly dependent.
By definition, an MDS code has distance n − k + 1. Hence, every set of n − k
columns of the parity-check matrix are linearly independent. This property
can be translated into a requirement for the matrix A:
Theorem 2.2.3 ([100]). An [n, k, d] code with generator matrix


G = Ik×k Ak×(n−k) ,
is an MDS code iff every square submatrix of A is nonsingular.
A well-known class of MDS codes is formed by the Reed-Solomon codes, for
which efficient construction algorithms are known.

2.3 Boolean Functions
The smallest finite field has an order of 2: GF(2). Its two elements are denoted
by 0 and 1. Its addition is the integer addition modulo 2 and its multiplication
is the integer multiplication modulo 2. Variables that range over GF(2) are
called Boolean variables, or bits for short. The addition of 2 bits corresponds
to the Boolean operation exclusive or, denoted by XOR. The multiplication of
2 bits corresponds to the Boolean operation AND. The operation of changing
the value of a bit is called complementation.
A vector whose coordinates are bits is called a Boolean vector. The operation of changing the value of all bits of a Boolean vector is called complementation. If we have two Boolean vectors a and b of the same dimension,
we can apply the following operations:

2.3 Boolean Functions

1. Bitwise XOR:
corresponding
2. Bitwise AND:
corresponding

23

results in a vector whose bits consist of the XOR of the
bits of a and b.
results in a vector whose bits consist of the AND of the
bits of a and b.

A function b = φ(a) that maps a Boolean vector to another Boolean
vector is called a Boolean function:
φ : GF(2)n → GF(2)m : a → b = φ(a),

(2.47)

where b is called the output Boolean vector and a the input Boolean vector.
This Boolean function has n input bits and m output bits.
A binary Boolean function b = f (a) is a Boolean function with a single
output bit, in other words m = 1:
f : GF(2)n → GF(2) : a → b = f (a),

(2.48)

where b is called the output bit. Each bit of the output of a Boolean function
is itself a binary Boolean function of the input vector. These functions are
called the component binary Boolean functions of the Boolean function.
A Boolean function can be specified by providing the output value for the
2n possible values of the input Boolean vector. A Boolean function with the
same number of input bits as output bits can be considered as operating on
an n-bit state. We call such a function a Boolean transformation. A Boolean
transformation is called invertible if it maps all input states to different output
states. An invertible Boolean transformation is called a Boolean permutation.
2.3.1 Tuple Partitions
In several instances it is useful to see the bits of a state as being partitioned
into a number of subsets. Boolean transformations operating on a state can
be expressed in terms of these subsets rather than in terms of the individual
bits of the state. In the context of this book we restrict ourselves to partitions
that divide the state bits into a number of equally sized subsets. We will use
the term tuples to describe these subsets.1 Because in the case of Rijndael,
tuples contain eight bits, we will often write bytes instead. However, the
reasoning applies as well to tuples of other sizes (larger than two).
Consider an nb -bit state a consisting of bits ai where i ∈ I. I is called the
index space. In its simplest form, the index space is just equal to {1, . . . , nb }.
However, for clarity the bits may be indexed in another way to ease specifications. A partitioning of the state bits may be reflected by having an index
with two components: one component indicating the byte position within
1

In the first edition we used the term bundles, but this term now gets another
meaning in Chap. 14.

24

2. Preliminaries

the state, and one component indicating the bit position within the byte. In
this representation, a(i,j) would mean the state bit in byte i at bit position
j within that byte. The value of the byte itself can be indicated by ai . On
some occasions, even the byte index can be decomposed. For example, in
Rijndael the bytes are arranged in a two-dimensional array with the byte
index composed of a column index and a row index.
Next to the obvious 8-bit bytes also the 32-bit columns in Rijndael define
a partitioning. The nonlinear steps in the round transformations of the AES
finalist Serpent [4] operate on 4-bit bytes. The nonlinear step in the round
transformation of 3-Way [43] and BaseKing [45] operate on 3-bit tuples. The
tuples can be considered as representations of elements in some group, ring
or field. Examples are the integers modulo 2m or elements of GF(2m ). In this
way, steps of the round transformation, or even the full round transformation
can be expressed in terms of operations in these mathematical structures.
2.3.2 Transpositions
A transposition is a Boolean permutation that only moves the positions of
bits of the state without affecting their value. For a transposition b = π(a)
we have:
(2.49)

bi = ap(i) ,

where p(i) is a permutation over the index space.
A byte transposition is a transposition that changes the positions of the
bytes but leaves the positions of the bits within the bytes intact. This can be
expressed as:
(2.50)

b(i,j) = a(p(i),j) .

An example is shown in Fig. 2.1. Figure 2.2 shows the pictogram that we will
use to represent a byte transposition in this book.

?

 U

+R

U

s

Fig. 2.1. Example of a byte transposition

2.3 Boolean Functions

25

Fig. 2.2. Pictogram for a byte transposition

2.3.3 Bricklayer Functions
A bricklayer function is a function that can be decomposed into a number
of Boolean functions operating independently on subsets of bits of the input
vector. These subsets form a partition of the bits of the input vector. A
bricklayer function can be considered as the parallel application of a number
of Boolean functions operating on smaller inputs. If nonlinear, these Boolean
functions are called S-boxes. If linear, we use the term D-box, where D stands
for diffusion.
A bricklayer function operating on a state is called a bricklayer transformation. As a bricklayer transformation operates on a number of subsets of
the state independently, it defines a byte partition. The component transformations of the bricklayer transformation operate independently on a number
of bytes. A graphical illustration is given in Fig. 2.3. An invertible bricklayer
transformation is called a bricklayer permutation. For a bricklayer transformation to be invertible, all of its S-boxes (or D-boxes) must be permutations.
The pictogram that we will use is shown in Fig. 2.4.
For a bricklayer transformation b = φ(a) we have:
(b(i,1) , b(i,2) , . . . , b(i,m) ) = φi (a(i,1) , a(i,2) , . . . , a(i,m) ),

(2.51)

for all values of i. If the bytes within a and b are represented by ai and bi ,
respectively, this becomes:
bi = φi (ai ).

φ

(2.52)

? ?

? ?

? ?

? ?

φ0

φ1

φ2

φ3

? ?

? ?

? ?

? ?

Fig. 2.3. Example of a bricklayer transformation

Fig. 2.4. Pictogram for a bricklayer transformation

26

2. Preliminaries

2.3.4 Iterative Boolean Transformations
A Boolean vector can be transformed iteratively by applying a sequence of
Boolean transformations, one after the other. Such a sequence is referred to
as an iterative Boolean transformation. If the individual Boolean transformations are denoted by ρ(i) , an iterative Boolean transformation is of the
form
β = ρ(r) ◦ . . . ◦ ρ(2) ◦ ρ(1) .

(2.53)

A schematic illustration is given in Fig. 2.5. We have b = β(d), where
d = a(0) , b = a(m) and a(i) = ρ(i) (a(i−1) ). The value of a(i) is called an
intermediate state. An iterative Boolean transformation that is a sequence of
Boolean permutations is an iterative Boolean permutation.
??

??
ρ

??

??
ρ

??

??

??

??

??

??

??

??

??

(1)

(2)

??
ρ(3)

??

??

Fig. 2.5. Iterative Boolean transformation

2.4 Block Ciphers
A block cipher transforms plaintext blocks of a fixed length nb into ciphertext
blocks of the same length under the influence of a cipher key k. More precisely,
a block cipher is a set of Boolean permutations operating on nb -bit vectors.
This set contains a Boolean permutation for each value of the cipher key k. In
this book we only consider block ciphers in which the cipher key is a Boolean
vector. If the number of bits in the cipher key is denoted by nk , a block cipher
consists of 2nk Boolean permutations.
The operation of transforming a plaintext block into a ciphertext block is
called encryption, and the operation of transforming a ciphertext block into
a plaintext block is called decryption.

2.4 Block Ciphers

27

Usually, block ciphers are specified by an encryption algorithm, being
the sequence of transformations to be applied to the plaintext to obtain
the ciphertext. These transformations are operations with a relatively simple
description. The resulting Boolean permutation depends on the cipher key
due to the fact that key material, computed from the cipher key, is used in
the transformations.
For a block cipher to be up to its task, it has to fulfill two requirements:
1. Efficiency. Given the value of the cipher key, applying the corresponding
Boolean permutation, or its inverse, is efficient, preferably on a wide range
of platforms.
2. Security. It must be impossible to exploit knowledge of the internal
structure of the cipher in cryptographic attacks.
All block ciphers of any significance satisfy these requirements by iteratively applying Boolean permutations that are relatively simple to describe.
2.4.1 Iterative Block Ciphers
In an iterative block cipher, the Boolean permutations are iterative. The block
cipher is defined as the application of a number of key-dependent Boolean
permutations. The Boolean permutations are called the round transformations of the block cipher. Every application of a round transformation is
called a round.
Example 2.4.1. The DES has 16 rounds. Since every round uses the same
round transformation, we say the DES has only one round transformation.
We denote the number of rounds by r. We have:
B[k] = ρ(r) [k(r) ] ◦ · · · ◦ ρ(2) [k(2) ] ◦ ρ(1) [k(1) ].

(2.54)

In this expression, ρ(i) is called the ith round of the block cipher and k(i) is
called the ith round key.
The round keys are computed from the cipher key. Usually, this is specified
with an algorithm. The algorithm that describes how to derive the round keys
from the cipher key is called the key schedule. The concatenation of all round
keys is called the expanded key, denoted by K:
K = k(0) |k(1) |k(2) | . . . |k(r)

(2.55)

The length of the expanded key is denoted by nK . The iterative block cipher model is illustrated in Fig. 2.6. Almost all block ciphers known can be
modeled this way. There is however a large variety in round transformations
and key schedules. An iterative block cipher in which all rounds (with the
exception of the initial or final round) use the same round transformation is
called an iterated block cipher.

28

2. Preliminaries
k(1)

-

k

-

k(2)

-

k(3)

-

??

??
ρ

??

??
ρ

??

??

??

??

??

??

??

??

??

(1)

(2)

??
ρ(3)

??

??

Fig. 2.6. Iterative block cipher with three rounds

2.4.2 Key-Alternating Block Ciphers
Rijndael belongs to a class of block ciphers in which the round key is applied in a particularly simple way: the key-alternating block ciphers. A keyalternating block cipher is an iterative block cipher with the following properties:
1. Alternation. The cipher is defined as the alternated application of keyindependent round transformations and key additions. The first round
key is added before the first round and the last round key is added after
the last round.
2. Simple key addition. The round keys are added to the state by means
of a simple XOR. A key addition is denoted by σ[k].
We have:
B[k] = σ[k(r) ] ◦ ρ(r) ◦ σ[k(r−1) ] ◦ · · · ◦ σ[k(1) ] ◦ ρ(1) ◦ σ[k(0) ].

(2.56)

A graphical illustration is given in Fig. 2.7.
Key-alternating block ciphers are a class of block ciphers that lend themselves to analysis with respect to their resistance against cryptanalysis. This
will become clear in Chaps. 7–9 and in Chaps. 13–15. A special class of keyalternating block ciphers are the key-iterated block ciphers. In this class, all
rounds (except maybe the first or the last) of the cipher use the same round
transformation. We have:
B[k] = σ[k(r) ] ◦ ρ ◦ σ[k(r−1) ] ◦ · · · ◦ σ[k(1) ] ◦ ρ ◦ σ[k(0) ].

(2.57)

In this case, ρ is called the round transformation of the block cipher. The
relations between the different classes of block ciphers that we define here
are shown in Fig. 2.8.

2.4 Block Ciphers

k(0) ? ?

??

??

??

??

??

??

??

-

29

ρ(1)
k

-

k(1) ? ?

??

??

??

??

??

??

??

-

ρ(2)
k(2) ? ?

??

??

??

??

??

??

??

-

Fig. 2.7. Key-alternating block cipher with two rounds

Key-iterated block ciphers lend themselves to efficient implementations.
In dedicated hardware implementations, one can hardwire the round transformation and the key addition. The block cipher can be executed by simply
iterating the round transformation alternated with the right round keys. In
software implementations, the program needs to code only the one round
transformation in a loop and the cipher can be executed by executing this
loop the required number of times. In practice, for performance reasons, block
ciphers in software will often have code for all rounds: so-called loop unrolling.
In these implementations, it is less important to have identical rounds. Nevertheless, the most-used block ciphers all consist of a number of identical
rounds. Some other advantages of the key-iterated structure are discussed in
Chap. 5.

iterated
block ciphers

key-iterated
block ciphers

key-alternating
block ciphers

iterative block ciphers
Fig. 2.8. Block cipher taxonomy

A block cipher is a cryptographic primitive that can convert a fixed-length
plaintext block to a fixed-length ciphertext block and vice versa under a given

30

2. Preliminaries

cipher key. In order to use a cipher to protect the confidentiality or integrity
of messages of arbitrary length, it must be specified how the cipher is used.
These specifications are the so-called modes of operation of a block cipher.
Modes of operation are out of scope of this book. We refer the reader to [102].

3. Specification of Rijndael

In this chapter we specify the cipher structure and the building blocks of
Rijndael. After explaining the difference between the Rijndael specifications
and the AES standard, we specify the external interface to the ciphers. This is
followed by the description of the Rijndael structure and the steps of its round
transformation. Subsequently, we specify the number of rounds as a function
of the block and key length, and describe the key schedule. We conclude this
chapter with a treatment of algorithms for implementing decryption with
Rijndael. This chapter is not intended as an implementation guideline. For
implementation aspects, we refer to Chap. 4.

3.1 Differences Between Rijndael and the AES
The only difference between Rijndael and the AES is the range of supported
values for the block length and cipher key length.
Rijndael is a block cipher with both a variable block length and a variable
key length. The block length and the key length can be independently specified to any multiple of 32 bits, with a minimum of 128 bits and a maximum
of 256 bits. It would be possible to define versions of Rijndael with a higher
block length or key length, but currently there seems no need for it.
The AES fixes the block length to 128 bits, and supports key lengths of
128, 192 or 256 bits only. The extra block and key lengths in Rijndael were
not evaluated in the AES selection process, and consequently they are not
adopted in the current FIPS standard.

3.2 Input and Output for Encryption and Decryption
The input and output of Rijndael are considered to be one-dimensional arrays
of 8-bit bytes. For encryption the input is a plaintext block and a key, and the
output is a ciphertext block. For decryption, the input is a ciphertext block
and a key, and the output is a plaintext block. The round transformation of
Rijndael, and its steps, operate on an intermediate result, called the state.
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
J. Daemen, V. Rijmen, The Design of Rijndael, Information Security and Cryptography,
https://doi.org/10.1007/978-3-662-60769-5_3

31

32

3. Specification of Rijndael

The state can be pictured as a rectangular array of bytes, with four rows.
The number of columns in the state is denoted by Nb and is equal to the
block length divided by 32. Let the plaintext block be denoted by
p0 p1 p2 p3 . . . p4·Nb −1 ,
where p0 denotes the first byte,and p4·Nb −1 denotes the last byte of the plaintext block. Similarly, a ciphertext block can be denoted by
c0 c1 c2 c3 . . . c4·Nb −1 .
Let the state be denoted by
ai,j , 0 ≤ i < 4, 0 ≤ j < Nb ,
where ai,j denotes the byte in row i and column j. The input bytes are
mapped onto the state bytes in the order a0,0 , a1,0 , a2,0 , a3,0 , a0,1 , a1,1 , a2,1 ,
a3,1 , . . . . For encryption, the input is a plaintext block and the mapping is
ai,j = pi+4j , 0 ≤ i < 4, 0 ≤ j < Nb .

(3.1)

For decryption, the input is a ciphertext block and the mapping is
ai,j = ci+4j , 0 ≤ i < 4, 0 ≤ j < Nb .

(3.2)

At the end of the encryption, the ciphertext is extracted from the state by
taking the state bytes in the same order:
ci = ai mod 4,i/4 , 0 ≤ i < 4Nb .

(3.3)

At the end of decryption, the plaintext block is extracted from the state
according to
pi = ai mod 4,i/4 , 0 ≤ i < 4Nb .

(3.4)

Similarly, the key is mapped onto a two-dimensional cipher key. The cipher
key is pictured as a rectangular array with four rows similar to the state. The
number of columns of the cipher key is denoted by Nk and is equal to the
key length divided by 32. The bytes of the key are mapped onto the bytes of
the cipher key in the order: k0,0 , k1,0 , k2,0 , k3,0 , k0,1 , k1,1 , k2,1 , k3,1 , k0,2 . . . .
If we denote the key by
z0 z1 z2 z3 . . . z4·Nk −1 ,
then
ki,j = zi+4j , 0 ≤ i < 4, 0 ≤ j < Nk .

(3.5)

The representation of the state and cipher key and the mappings plaintext–
state and key–cipher key are illustrated in Fig. 3.1.

3.4 The Round Transformation

p0

p4

p8

p12

k0

k4

k8

k12 k16 k20

p1

p5

p9

p13

k1

k5

k9

k13 k17 k21

p2

p6

p10 p14

k2

k6

k10 k14 k18 k22

p3

p7

p11 p15

k3

k7

k11 k15 k19 k23

33

Fig. 3.1. State and cipher key layout for the case Nb = 4 and Nk = 6

3.3 Structure of Rijndael
Rijndael is a key-iterated block cipher: it consists of the repeated application
of a round transformation on the state. The number of rounds is denoted by
Nr and depends on the block length and the key length.
Note that in this chapter, contrary to the definitions (2.54)–(2.57), the
key addition is included in the round transformation. This is done in order
to make the description in this chapter consistent with the description in the
FIPS standard.
Following a suggestion of B. Gladman, we changed the names of some
steps with respect to the description given in our original AES submission.
The new names are more consistent, and are also adopted in the FIPS standard. We made some further changes, all in order to make the description
more clear and complete. No changes have been made to the block cipher
itself.
An encryption with Rijndael consists of an initial key addition, denoted
by AddRoundKey, followed by Nr −1 applications of the transformation Round,
and finally one application of FinalRound. The initial key addition and every
round take as input the State and a round key. The round key for round i
is denoted by ExpandedKey[i], and ExpandedKey[0] denotes the input of the
initial key addition. The derivation of ExpandedKey from the CipherKey is
denoted by KeyExpansion. A high-level description of Rijndael in pseudocode
notation is shown in List. 3.1.

3.4 The Round Transformation
The round transformation is denoted Round, and is a sequence of four transformations, called steps. This is shown in List. 3.2. The final round of the
cipher is slightly different. It is denoted FinalRound and is also shown in
List. 3.2. In the listings, the transformations (Round, SubBytes, ShiftRows,

34

3. Specification of Rijndael
procedure Rijndael(State,Cipherkey)
KeyExpansion(CipherKey,ExpandedKey)
AddRoundKey(State,ExpandedKey[0])
for i = 1 to Nr − 1 do
Round(State,ExpandedKey[i])
end for
FinalRound(State,ExpandedKey[Nr ])
end procedure

List. 3.1. High-level algorithm for encryption with Rijndael
. . . ) operate on arrays to which pointers (State, ExpandedKey[i]) are provided. It is easy to verify that the transformation FinalRound is equal to
the transformation Round, but with the MixColumns step removed. The steps
are specified in the following subsections, together with the design criteria
we used for each step. Besides the step-specific criteria, we also applied the
following two general design criteria:
1. Invertibility. The structure of the Rijndael round transformation requires that all steps be invertible.
2. Simplicity. As explained in Chap. 5, we prefer simple components over
complex ones.

procedure Round(State,ExpandedKey[i])
SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State,ExpandedKey[i]);
end procedure
procedure FinalRound(State,ExpandedKey[Nr ])
SubBytes(State);
ShiftRows(State);
AddRoundKey(State,ExpandedKey[Nr ]);
end procedure

List. 3.2. The Rijndael round transformation

3.4.1 The SubBytes Step
The SubBytes step is the only nonlinear transformation of the cipher.
SubBytes is a bricklayer permutation consisting of an S-box applied to the
bytes of the state. We denote the particular S-box being used in Rijndael
by SRD . Figure 3.2 illustrates the effect of the SubBytes step on the state.
Figure 3.3 shows the pictograms that we will use to represent SubBytes and
its inverse.

3.4 The Round Transformation

35

- SRD
a0,0 a0,1 a0,2 a0,3

b0,0 b0,1 b0,2 b0,3

a1,0 a1,1 a1,2 a1,3

b1,0 b1,1 b1,2 b1,3

a2,0 a2,1 a2,2 a2,3

b2,0 b2,1 b2,2 b2,3

a3,0 a3,1 a3,2 a3,3

b3,0 b3,1 b3,2 b3,3

R

Fig. 3.2. SubBytes acts on the individual bytes of the state








































Fig. 3.3. The pictograms for SubBytes (left) and InvSubBytes (right)

Design criteria for SRD . We have applied the following design criteria for
SRD , appearing in order of i