A Modern Method for Constructing the S-Box of Advanced Encryption Standard ()
1. Introduction
The S-Box table of AES is taken as a lookup table to substitute an input byte by another, this table is constructed using a non-linear transformation depends on the usual method taking more calculation steps to give the corresponding byte.
The S-Box plays a fundamental role in encryption and decryption processes, as byte substitution appears in many steps. At the first round of the encryption process, we add the plaintext matrix to the key matrix, then we substitute each byte by another byte according to S-Box, for example, to substitute the byte xy(say), we take the byte in the cell that has x as the column index and y as the row index, we do this substitute byte step in all rounds of the encryption process, and in all round of the decryption process, we do the inverse substitute byte step, to substitute the byte xy(say), we take the index of the column, and the index of the row of the cell that contains xy, as the left and the right character of the result byte, respectively. The S-Box (Table 1), involves substitution bytes for all bytes from {00} to {FF} in hexdecimal presentation.
The S-Box is constructed using the following operations [1] :
1) Finding the multiplicative inverse of an input byte in the finite field
based on the irreducible polynomial
.
2) Multiplying this multiplicative inverse by a specific matrix (matrix M).
3) Adding the multiplication result to a specific vector
.
We convert the hexadecimal presentation of the input byte into binary presentation as
and write it as a polynomial
, let its multiplicative inverse be
, we multiply
by the following characteristic matrix:
(1)
Then, we add the result to (01100011).
We note that, for the input {00} the output is {63}.
1.1. Problem Statement
We search for an easier and straightforward method for constructing the AES S-Box.
1.2. Proposed Solution
The multiplicative inverse of an input byte can be computed in clear steps using an iterated formula.
Multiplying the multiplicative inverse matrix by the characteristic matrix can be determined directly from this multiplicative inverse using simple XOR operations, without a need to use the characteristic matrix.
2. Traditional Way
In cryptography, the extended Euclidean algorithm has wide uses especially for finding a multiplicative inverse (modular inverse).
Euclidean algorithm is used to find the greatest common divisor of two integers a and b, (denoted by
).
When
, and
(2)
for some integers r and q, we say
(3)
and if
then
(4)
With the polynomials
and
, we write
[2] .
The algorithm below gives
, where
The step (1.(a)) of the algorithm (1) involves the division algorithm:
(5)
where
.
It implies that [4]
(6)
If
, the step will be repeated, let us write the repeated application of the division algorithm as:
,
,
,
,
,
(7)
When
, and since
(8)
we get
(9)
The extended form of the Euclidean algorithm is called Extended Euclidean algorithm, it gives (besides
,
and
such that
(10)
Rewrite the equations of the system (7) as:
(11)
Then, in the last equation of system (11),
, replace
with its value from the above equation (it involves
), then replace
with its value from the above equation, continue doing this replacement, we obtain
(12)
Equation (12) takes the form
(13)
In our problem
, and since the multiplicative inverse only exists when the gcd is 1 [5] .
(14)
The multiplicative inverse [2] of
modulo
is
such that
(15)
When
,
(16)
(17)
and since
(18)
we get
(19)
So, the procedure of the extended Euclidean algorithm finds the greatest common divisor, also it finds the multiplicative inverse.
Below an algorithm to find
, we will denote
by
.
Now, we have
, we multiply it (from the left) by matrix M
(20)
Then, we add the result to
to obtain the output of the input
(21)
Example
Using the traditional way, we want to find the output byte that corresponding to the input byte {53} (Table 2).
,
,
.
Iteration 1
Iteration 2
Iteration 3
.
(22)
(23)
The output is
.
Table 2. To find the output of {53}.
3. Modern Way
We use the formula [6] below to find the multiplicative inverse.
3.1. The Iterated Formula
The iterated formula
,
(24)
where
, gives the multiplicative inverse
when
.
To show that, we use the system (11).
When
,
,
(25)
(26)
We obtain
. (Equation (24), takes this as given).
When
,
,
,
(27)
(28)
We obtain
. From Equation (24)
(29)
When
,
,
,
,
(30)
(31)
We obtain
(32)
and from Equation (24)
(33)
By this way, we can show that Equation (24) gives
for
, when
.
Below an algorithm to find
using the modern way.
Now, we want to multiply
by the matrix M.
First, write M as [7]
(34)
Let
,
(35)
And write
as
(36)
Let
,
(37)
Then
(38)
(39)
(40)
(41)
So, the multiplication of M and
gives
From Equation (38) and Equation (39), we note that the results of these multiplications give the form
of the second matrix, and similarly, Equation (40) and Equation (41), show that the results give the form
of the second matrix, so we don’t need to use matrix M, as the traditional method.
In the last step, we add
to
.
3.2. Example
Using the modern way, we want to find the output of {53}
,
,
.
First, finding the multiplicative inverse (Table 3).
Table 3. Finding multiplicative inverse of {53}.
Since
,
Then, computing the matrices multiplication:
(42)
Last, adding (01100011)
(43)
So, the output is
.
4. Conclusions
In this paper, a straightforward method for obtaining the Advanced Encryption Standard S-Box look-up table without the traditional use of the characteristic Matrix M is proposed. We have demonstrated that the two methods are equivalent. In addition, the multiplicative inverse of
has been found more elegantly.
In future work, we will investigate the properties and the impact of this technique on cipher complexity analysis.