Cryptography Reference
In-Depth Information
an inverse does not exist. However, for the AES S-Box, a substitution table is needed
that is defined for every possible input value. Hence, the designers defined the S-Box
such that the input value 0 is mapped to the output value 0.
Table 4.2
Multiplicative inverse table in
GF
(2
8
) for bytes
xy
used within the AES S-Box
Y
0123456789ABCDEF
0 00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7
1 74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
2 3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2
3 2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
4 1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
5 ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17
6 16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
7 79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82
X
8 83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
9 DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
A FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
B 0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
C 0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6
D 7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
E B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3
F 5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1C
Example 4.7.
From Table 4.2 the inverse of
x
7
+
x
6
+
x
=(1100 0010)
2
=(
C
2)
hex
=(
xy
)
is given by the element in row
C
, column 2:
(2
F
)
hex
=(0010 1111)
2
=
x
5
+
x
3
+
x
2
+
x
+ 1
.
This can be verified by multiplication:
(
x
7
+
x
6
+
x
)
(
x
5
+
x
3
+
x
2
+
x
+ 1)
·
≡
1mod
P
(
x
)
.
Note that the table above does not contain the S-Box itself, which is a bit more
complex and will be described in Sect. 4.4.1.
As an alternative to using lookup tables, one can also explicitly compute inverses.
The main algorithm for computing multiplicative inverses is the extended Euclidean
algorithm, which is introduced in Sect. 6.3.1.
4.4 Internal Structure of AES
In the following, we examine the internal structure of AES. Figure 4.3 shows the
graph of a single AES round. The 16-byte input
A
0
,...,
A
15
is fed byte-wise into the
