Home | | **Cryptography and Network Security** | Advanced Encryption Standard(AES) Transformation Functions

We now turn to a discussion of each of the four transformations used in AES. For each stage, we describe the forward (encryption) algorithm, the inverse (decryption) algorithm, and the rationale for the stage.

**AES TRANSFORMATION FUNCTIONS**

We now turn to a discussion of each of the four
transformations used in AES. For each
stage, we describe
the forward (encryption) algorithm, the inverse
(decryption) algorithm, and the rationale for the stage.

Substitute Bytes
Transformation

*F**ORWARD AND **I**NVERSE **T*** RANSFORMATIONS **The

of the S-box, which contains the value {2A}.
Accordingly, the value {95} is mapped into the value {2A}.

Here is an example of the SubBytes transformation:

The S-box is constructed in the following fashion (Figure 5.6a).

**1.
**Initialize the S-box
with the byte values in ascending sequence row by row.

The first row
contains {00}, {01}, {02}, ... , {0F}; the second
row
contains

{10}, {11}, etc.;
and so on. Thus, the value
of the byte at row *y*, column *x *is {*yx*}.

**2.
**Map each byte in the S-box to its multiplicative
inverse in the finite field GF(28); the value {00} is mapped
to itself.

**3.
**Consider that each byte in the S-box consists
of 8 bits labeled (*b*7, *b*6, *b*5, *b*4, *b*3, *b*2, *b*1, *b*0). Apply
the following transformation to each bit of each byte in the
S-box:

where *c**i *is the *i*th bit of byte *c *with the value {63}; that is,
(*c*7*c*6*c*5*c*4*c*3*c*2*c*1*c*0) = (01100011). The prime (¿) indicates that the variable is to be updated by the value on the right. The AES standard
depicts this transformation in matrix
form as follows.

Equation (5.2) has to be interpreted
carefully. In ordinary matrix multiplica- tion,4 each element in the product matrix is the sum of products
of the elements of one row and one
column. In this case, each element in the product matrix is the bitwise
XOR of products of elements
of one row and one column. Furthermore, the final addition shown in Equation (5.2) is a bitwise XOR.
Recall from Section 4.7 that the bitwise
XOR is addition in GF(28).

As an example, consider the input value
{95}. The multiplicative inverse in GF(28) is {95} - 1 = {8A},
which is 10001010 in binary. Using Equation (5.2),

The result is {2A}, which should appear in
row {09} column {05} of the S-box.

This is verified by checking Table 5.2a.

The **inverse
substitute byte transformation**, called InvSubBytes, makes use of
the inverse S-box shown in Table 5.2b. Note, for example, that the input
{2A} produces the output
{95}, and the input {95} to the S-box produces
{2A}. The inverse S-box is constructed
(Figure 5.6b) by applying the inverse of the transfor- mation in Equation (5.1) followed by taking the multiplicative inverse in GF(28).

The inverse transformation is

*b**i*¿ = *b*(*i** *+ 2) mod
8 Ⓧ *b*(*i** *+ 5) mod
8 Ⓧ *b*(*i** *+ 7)
mod 8 Ⓧ *d**i*

where byte *d *= {05},
or 00000101. We can depict this transformation as follows.

To see that InvSubBytes is the inverse of
SubBytes, label the matrices in SubBytes and InvSubBytes as X and B, respectively,
and the vector versions of con- stants c and d as C and D, respectively. For
some 8-bit vector B,
Equation (5.2) becomes B¿ = XB Ⓧ C. We need to show
that Y(XB Ⓧ C) Ⓧ
D =
B. To multiply out, we must show
YXB Ⓧ YC Ⓧ D = B. This
becomes

We have demonstrated that YX equals the
identity matrix, and the YC = D, so that YC Ⓧ D equals the null vector.

** RATIONALE **The
S-box is designed to be resistant to
known cryptanalytic attacks. Specifically,
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 [DAEM01]. The nonlinearity is due to the use of the multiplicative
inverse. In addition,
the constant in Equation (5.1)
was chosen so that the S-box has no fixed points [S-box(

Of course,
the S-box must
be invertible, that is, IS-box[S-box(a)] =
a.

However, the
S-box does not
self-inverse in the
sense that it
is not true that S-box(a) = IS-box(a). For example, S-box({95}) =
{2A}, but IS-box({95}) = {AD}.

ShiftRows Transformation

*FORWARD AND **INVERSE *** TRANSFORMATIONS
**The

The **inverse shift row transformation**, called
InvShiftRows, performs the circu-
lar shifts in the opposite direction for each of the last three rows, with a 1-byte circular right shift for the second row, and so on.

** RATIONALE
**The shift row transformation is more
substantial than it may first appear. This is because the

distance of a multiple of 4 bytes. Also note that the transformation
ensures that the 4 bytes of one column are spread out to four different
columns. Figure 5.4 illustrates the
effect.

MixColumns Transformation

*F**ORWARD** **AND **I**NVERSE **T*** RANSFORMATIONS **The

Each element
in the product matrix is the sum of products
of elements of one row and one
column. In this case,
the individual additions and multiplications5 are performed in GF(28). The MixColumns transformation on a single
column of **State **can be expressed as

Let us verify the first column of this example. Recall from Section
4.7 that, in GF(28), addition is the bitwise XOR
operation and that multiplication can be per- formed according to the rule established in Equation (4.14).
In particular, multipli- cation of a value
by *x *(i.e., by {02}) can be implemented as a 1-bit
left shift followed by a conditional bitwise XOR
with (0001 1011) if the leftmost bit of the original value (prior
to the shift) is 1. Thus, to verify
the MixColumns transformation on the first column,
we need to show that

The other equations can be similarly verified.

The **inverse mix column transformation**, called
InvMixColumns, is defined by the following matrix multiplication:

It is not immediately clear
that Equation (5.5)
is the **inverse **of
Equation (5.3).

We
need to show

That
is, the inverse transformation matrix times the forward transformation matrix
equals the identity matrix. To verify the first column of Equation (5.6), we
need to show

For the
first equation, we have
{0E} . {02} = 00011100
and {09} . {03} = {09} Ⓧ ({09}
# {02}) = 00001001 Ⓧ 00010010 = 00011011.
Then

The other equations can be similarly verified.

The AES document describes another way of characterizing the MixColumns
transformation, which is in terms
of polynomial arithmetic. In the standard,
MixColumns is defined
by considering each column of **State **to be a four-term poly- nomial with coefficients in GF(28). Each column is multiplied
modulo (*x*4 + 1) by the fixed polynomial *a*(*x*),
given by

*a*(*x*) = {03}*x*3 + {01}*x*2 + {01}*x *+ {02} **(5.7)**

Appendix
5A demonstrates that multiplication of each column of **State **by *a*(*x*) can be written as the matrix
multiplication of Equation (5.3). Similarly, it can be seen that the
transformation in Equation (5.5) corresponds to treating each column as a four-term polynomial and
multiplying each column by *b*(*x*), given by

*b*(*x*) = {0B}*x*3 + {0D}*x*2 + {09}*x *+ {0E} **(5.8)**

It readily
can be shown that *b*(*x*) = *a *- 1(*x*) mod (*x*4 + 1).

** RATIONALE **The coefficients
of the matrix in Equation (5.3) are based on a linear code with maximal distance between code words, which 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.
See [DAEM99] for a discussion.

In
addition, the choice of coefficients in MixColumns, which are all {01}, {
02}, or { 03}, was influenced by
implementation considerations. As was discussed, multi- plication by these
coefficients involves at most a shift and an XOR. The coefficients in InvMixColumns are more formidable to
implement. However, encryption was deemed
more important than
decryption for two reasons:

**1.
**For the CFB and OFB cipher modes (Figures 6.5 and 6.6; described in Chapter
6), only encryption
is used.

**2.
**As with any block cipher,
AES can be used to construct a message authentica- tion code (Chapter 12), and for this, only encryption is used.

**AddRoundKey
Transformation**

*FORWARD *** AND INVERSE TRANSFORMATIONS **In the

The first matrix is **State**, and
the second matrix is the round key.

The **inverse
add round key transformation **is identical to the forward add round key
transformation, because the XOR operation is its own inverse.

** RATIONALE
**The add round key
transformation is as simple as possible and affects every bit of

Figure
5.8 is another view of a single round of AES, emphasizing the mecha- nisms and
inputs of each transformation.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Advanced Encryption Standard : Advanced Encryption Standard(AES) Transformation Functions |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.