Ch06 Crypto7e

Cryptography and
Network Security
Seventh Edition, Global Edition
by William Stallings
© 2017 Pearson Education, Ltd., All rights reserved.

Chapter 6
Advanced Encryption Standard

Finite Field Arithmetic
• In the Advanced Encryption Standard (AES) all operations
are performed on 8-bit bytes
• The arithmetic operations of addition, multiplication, and

division are performed over the finite field GF(28)
• A field is a set in which we can do addition, subtraction,

multiplication, and division without leaving the set
• Division is defined with the following rule:

• a /b = a (b-1 )
• An example of a finite field (one with a finite number of

elements) is the set Zp consisting of all the integers
{0, 1, . . . . , p - 1}, where p is a prime number and in which
arithmetic is carried out modulo p
Finite Field Arithmetic
If one of the operations For convenience and for
used in the algorithm is implementation efficiency we
division, then we need to would like to work with
work in arithmetic defined integers that fit exactly into a
over a field given number of bits with no
•Division requires that each nonzero wasted bit patterns
element have a multiplicative •Integers in the range 0 through 2n –
inverse 1, which fit into an n-bit word
The set of such integers, Z2n, A finite field containing 2n

using modular arithmetic, is elements is referred to as
not a field GF(2n)
•For example, the integer 2 has no •Every polynomial in GF(2n) can be
multiplicative inverse in Z2n, that is, represented by an n-bit number
there is no integer b, such that 2b
mod 2n = 1

Table 6.1
AES Parameters

Detailed Structure
• Processes the entire data block as a single matrix during each round using substitutions and
permutation
• The key that is provided as input is expanded into an array of forty-four 32-bit words, w[i]
Four different stages are used:

•Substitute bytes – uses an S-box to perform a byte-by-byte substitution of the block
•ShiftRows – a simple permutation
•MixColumns – a substitution that makes use of arithmetic over GF(28)
•AddRoundKey – a simple bitwise XOR of the current block with a portion of the expanded key
• The cipher begins and ends with an AddRoundKey stage

• Can view the cipher as alternating operations of XOR encryption (AddRoundKey) of a block,
followed by scrambling of the block (the other three stages), followed by XOR encryption,
and so on
• Each stage is easily reversible
• The decryption algorithm makes use of the expanded key in reverse order, however the
decryption algorithm is not identical to the encryption algorithm
• State is the same for both encryption and decryption
• Final round of both encryption and decryption consists of only three stages

Table 6.2
(a) S-box
(Table can be found on page 163 in textbook)

Table 6.2
(b) Inverse S-box
(Table can be found on page 163 in textbook)

S-Box Rationale
• The S-box is designed to be resistant to known
cryptanalytic attacks
• The Rijndael developers sought a design that

has a low correlation between input bits and
output bits and the property that the output is
not a linear mathematical function of the input
• The nonlinearity is due to the use of the

multiplicative inverse

Shift Row Rationale
• More substantial than it may first appear
• The State, as well as the cipher input and output, is
treated as an array of four 4-byte columns
• On encryption, the first 4 bytes of the plaintext are
copied to the first column of State, and so on
• The round key is applied to State column by column
• Thus, a row shift moves an individual byte from one
column to another, which is a linear distance of a
multiple of 4 bytes
• Transformation ensures that the 4 bytes of one

column are spread out to four different columns
Mix Columns Rationale
• Coefficients of a matrix based on a linear code
with maximal distance between code words
ensures a good mixing among the bytes of
each column
• The mix column transformation combined with

the shift row transformation ensures that after
a few rounds all output bits depend on all
input bits

AddRoundKey
Transformation
• The 128 bits of State are
bitwise XORed with the
128 bits of the round key
Rationale:
• Operation is viewed as a
columnwise operation Is as simple as possible and
affects every bit of State
between the 4 bytes of a
State column and one
word of the round key
The complexity of the round
• Can also be viewed as a key expansion plus the
byte-level operation complexity of the other
stages of AES ensure security

AES Key Expansion
• Takes as input a four-word (16 byte) key and produces a
linear array of 44 words (176) bytes
• This is sufficient to provide a four-word round key for the
initial AddRoundKey stage and each of the 10 rounds of the
cipher
• Key is copied into the first four words of the expanded key
• The remainder of the expanded key is filled in four words at a
time
• Each added word w[i] depends on the immediately

preceding word, w[i – 1], and the word four positions back,
w[i – 4]
• In three out of four cases a simple XOR is used
• For a word whose position in the w array is a multiple of 4, a
more complex function is used
Key Expansion Rationale
• The Rijndael developers The specific criteria that were used are:
designed the expansion •Knowledge of a part of the cipher key
key algorithm to be or round key does not enable
resistant to known calculation of many other round-key bits
cryptanalytic attacks •An invertible transformation
•Speed on a wide range of processors
•Usage of round constants to eliminate
• Inclusion of a round- symmetries
dependent round •Diffusion of cipher key differences into
constant eliminates the the round keys
symmetry between the •Enough nonlinearity to prohibit the full
determination of round key differences
ways in which round keys from cipher key differences only
are generated in different •Simplicity of description
rounds

Table 6.3
AES Example
Key
Expansion
(Table is located on page 175
in textbook)

Table 6.4
AES
Example
in textbook)

Table 6.5
Avalanche
Effect
in AES:
Change in
Plaintext
in textbook)

Table 6.6
Avalanche
Effect
in AES:
Change
in Key
in textbook)

Equivalent Inverse Cipher
• AES decryption cipher is
not identical to the Two separate changes are
encryption cipher needed to bring the
decryption structure in line
• The sequence of with the encryption structure
transformations differs
although the form of the
key schedules is the
same The first two stages of the
decryption round need to be
• Has the disadvantage interchanged
that two separate
software or firmware
modules are needed for
applications that require The second two stages of the
both encryption and decryption round need to be
decryption interchanged

Interchanging
InvShiftRows and InvSubBytes
• InvShiftRows affects the sequence of bytes in
State but does not alter byte contents and does
not depend on byte contents to perform its
transformation
• InvSubBytes affects the contents of bytes in
State but does not alter byte sequence and
does not depend on byte sequence to perform
its transformation
Thus, these two operations commute
and can be interchanged
Interchanging
AddRoundKey and InvMixColumns
If we view the
key as a
The sequence of
transformations words, then
These two
AddRoundKey both
operations are
and AddRoundKey
linear with
InvMixColumns and
respect to the
do not alter the InvMixColumns
column input
sequence of operate on
bytes in State State one
column at a
time

Implementation Aspects
• AES can be implemented very efficiently on an 8-
bit processor
• AddRoundKey is a bytewise XOR operation
• ShiftRows is a simple byte-shifting operation
• SubBytes operates at the byte level and only

requires a table of 256 bytes
• MixColumns requires matrix multiplication in the
field GF(28), which means that all operations are
carried out on bytes
Implementation Aspects
• Can efficiently implement on a 32-bit processor
• Redefine steps to use 32-bit words
• Can precompute 4 tables of 256-words
• Then each column in each round can be
computed using 4 table lookups + 4 XORs
• At a cost of 4Kb to store tables
• Designers believe this very efficient

implementation was a key factor in its
selection as the AES cipher

Summary
• Finite field arithmetic • AES transformation
functions
• AES structure • Substitute bytes
• General structure • ShiftRows
• Detailed structure • MixColumns
• AddRoundKey
• AES key expansion
• Key expansion • AES implementation
algorithm • Equivalent inverse
• Rationale cipher
• Implementation
aspects

Ch06 Crypto7e

Uploaded by

Copyright:

Available Formats

Ch06 Crypto7e

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ch06 Crypto7e

Uploaded by

Copyright:

Available Formats

Cryptography and

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

• The arithmetic operations of addition, multiplication, and

• A field is a set in which we can do addition, subtraction,

• Division is defined with the following rule:

• An example of a finite field (one with a finite number of

The set of such integers, Z2n, A finite field containing 2n

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

Four different stages are used:

• The cipher begins and ends with an AddRoundKey stage

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

(b) Inverse S-box

(Table can be found on page 163 in textbook)

© 2017 Pearson Education, Ltd., All rights reserved.

• The Rijndael developers sought a design that

• The nonlinearity is due to the use of the

© 2017 Pearson Education, Ltd., All rights reserved.

• Transformation ensures that the 4 bytes of one

• The mix column transformation combined with

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

• Each added word w[i] depends on the immediately

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

© 2017 Pearson Education, Ltd., All rights reserved.

• ShiftRows is a simple byte-shifting operation

• SubBytes operates at the byte level and only

• Designers believe this very efficient

© 2017 Pearson Education, Ltd., All rights reserved.

You might also like