Cryptography Reference
In-Depth Information
The S-box has the task of minimizing the susceptibility of the algorithm
to methods of linear and differential cryptanalysis and to algebraic attacks. To
accomplish this, the S-box operation should possess a high algebraic complexity
in
F
2
8
and thus create a good extension to the
ShiftRows
and
MixColumns
operations. Not having such a function would support attacks within
F
2
8
and
thereby decisively weaken the procedure.
In addition to the requirement of complexity, the S-box function must of
course be invertible; it must have no fixed points
S
(
a
)=
a
or complementary
fixed points
S
(
a
)=
a
; and it must also execute rapidly and be easy to implement.
All these desiderata were achieved through a combination of multiplicative
inversion in
F
2
8
to
itself. The S-box consists of a list of 256 bytes, which are constructed by first
thinking of each nonzero byte as a representative of
F
2
8
and the previously mentioned affine mapping from
F
2
8
and replacing it with its
multiplicative inverse (zero remains unchanged). Then an affine transformation
over
F
2
is calculated as a matrix multiplication and addition of
(11000110)
:
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
y
0
y
1
y
2
y
3
y
4
y
5
y
6
y
7
10001111
11000111
11100011
11110001
11111000
01111100
00111110
00011111
x
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
1
1
0
0
0
1
1
0
=
·
+
.
(11.2)
In this representation
x
0
and
y
0
denote the least-significant, and
x
7
and
y
7
the most-significant, bits of a byte, where the 8-tuple
(11000110)
corresponds to the hexadecimal value '63'.
Through this construction, all of the requisite design criteria were satisfied.
The substitution is thereby an ideal strengthening of the algorithm. Successive
application of the construction plan to the values 0 to 255 leads to Table 11-9 (in
hexadecimal form; read horizontally from left to right).
For decryption the S-box must be used backwards: The affine inverse
transformation is used, followed by multiplicative inversion in
F
2
8
. The inverted
S-box appears in Table 11-10.
11.5 The ShiftRows Transformation
The next step in the cycle of a round consists in the permutation of a block at
the byte level. To this end the bytes are exchanged within the individual lines
(
b
i,
0
,b
i,
1
,b
i,
2
,...,b
i,L
b
−
1
)
of a block according to the schemata depicted in
Tables 11-11 through 11-13.
