1. Introduction

Rijndael ByteSub transformation (or AES substitution byte) [1] transforms an input byte into another byte by two operations:

1) Finding a multiplicative inverse of an input byte $\left(a_7{a}_6{a}_5{a}_4{a}_3{a}_2{a}_1{a}_0\right)$ in the finite field GF (2⁸).

2) Applying the following affine transform:

$\begin{array}{l}{c}_i=b_i+b_{\left(i+4\right)\mathrm{mod}\left(8\right)}+b_{\left(i+5\right)\mathrm{mod}\left(8\right)}+b_{\left(i+6\right)\mathrm{mod}\left(8\right)}\\ +b_{\left(i+7\right)\mathrm{mod}\left(8\right)}+d_i,0\le i\le 7\end{array}$ (1)

where $\left(b_7{b}_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0\right)$ is resulting from the first operation, $\left(d_7{d}_6{d}_5{d}_4{d}_3{d}_2{d}_1{d}_0\right)=01100011$ .

In general, the multiplicative inverse is found by using the extended Euclidean algorithm [2] , instead of using it, we use an elegant technique which finds the multiplicative inverse in clear steps.

The transform of the second operation can be expressed in the matrix form as:

$\left[\begin{array}{c}{c}_0\\ c_1\\ c_2\\ c_3\\ c_4\\ c_5\\ c_6\\ c_7\end{array}\right]=\left[\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7\end{array}\right]+\left[\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right]$ (2)

To solve this system, we use an unusual and more suitable technique which shows this multiplication of matrix (8 × 8) and matrix (8 × 1) as simple XOR operations, and we can find it directly from $\left(b_7{b}_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0\right)$ .

2. The Methodology

For an input byte $\left(a_7{a}_6{a}_5{a}_4{a}_3{a}_2{a}_1{a}_0\right)$ , we find its multiplicative inverse $\left(b_7{b}_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0\right)$ , and find $\left(e_7{e}_6{e}_5{e}_4{e}_3{e}_2{e}_1{e}_0\right)$ such that:

$\left[\begin{array}{c}{e}_0\\ e_1\\ e_2\\ e_3\\ e_4\\ e_5\\ e_6\\ e_7\end{array}\right]=\left[\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7\end{array}\right]$ (3)

Then, we find the output $\left(c_7{c}_6{c}_5{c}_4{c}_3{c}_2{c}_1{c}_0\right)$ as:

$\left[\begin{array}{c}{c}_0\\ c_1\\ c_2\\ c_3\\ c_4\\ c_5\\ c_6\\ c_7\end{array}\right]=\left[\begin{array}{c}{e}_0\\ e_1\\ e_2\\ e_3\\ e_4\\ e_5\\ e_6\\ e_7\end{array}\right]+\left[\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right]$ (4)

First, we find a multiplicative inverse of $a_7{x}^7+a_6{x}^6+a_5{x}^5+a_4{x}^4+a_3{x}^3+a_2{x}^2+a_{1}x+a_0\mathrm{mod}\left(x^8+x^4+x^3+x+1\right)$ .

Let $M_1=a_7{x}^7+a_6{x}^6+a_5{x}^5+a_4{x}^4+a_3{x}^3+a_2{x}^2+a_{1}x+a_0$ , $P=x^8+x^4+x^3+x+1$ , and represent the multiplicative inverse by T.

We seek for $q_1$ and $r_1$ satisfying:

$M_1{q}_1+r_1=Q_1$ (5)

where $Q_1=P+1$ [3] , (look at Table 1).

If $r_1=0$ , then $T=q_1$ .

If $r_1\ne 0$ , we let $M_2=r_1+1$ and seek for $q_i$ and $r_i$ satisfying:

$M_i{q}_i+r_i=Q_i,2\le i\le 7$ (6)

where $Q_i=M_{i-1}$ , and $M_{i+1}=r_i$ (look at Table 2).

Whenever $r_i=1$ , then

$T=T_i=q_i{T}_{i-1}+T_{i-2}$ (7)

where $T_0=1$ , and $T_1=q_1$ .

Then, to find $\left(e_7{e}_6{e}_5{e}_4{e}_3{e}_2{e}_1{e}_0\right)$ , we write the system (3), as follows:

$\left[e\right]=\left[\begin{array}{cc}X& Y\\ Y& X\end{array}\right]\left[b\right]$ (8)

$e_i=X{b}_i+Y{b}_j$ (9)

$e_j=Y{b}_i+X{b}_j$ (10)

where $0\le i\le 3$ , $4\le j\le 7$ , and

$X=\left[\begin{array}{cc}1& \begin{array}{ccc}0& 0& 0\end{array}\\ \begin{array}{c}1\\ 1\\ 1\end{array}& \begin{array}{ccc}\begin{array}{c}1\\ 1\\ 1\end{array}& \begin{array}{c}0\\ 1\\ 1\end{array}& \begin{array}{c}0\\ 0\\ 1\end{array}\end{array}\end{array}\right]$ (11)

$Y=\left[\begin{array}{cc}\begin{array}{cc}1& 1\\ 0& 1\end{array}& \begin{array}{cc}1& 1\\ 1& 1\end{array}\\ \begin{array}{cc}0& 0\\ 0& 0\end{array}& \begin{array}{cc}1& 1\\ 0& 1\end{array}\end{array}\right]$ (12)

$b_i=\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\end{array}\right],b_j=\left[\begin{array}{c}{b}_4\\ b_5\\ b_6\\ b_7\end{array}\right]$ (13)

Then we compute

$X{b}_i=\left[\begin{array}{cc}1& \begin{array}{ccc}0& 0& 0\end{array}\\ \begin{array}{c}1\\ 1\\ 1\end{array}& \begin{array}{ccc}\begin{array}{c}1\\ 1\\ 1\end{array}& \begin{array}{c}0\\ 1\\ 1\end{array}& \begin{array}{c}0\\ 0\\ 1\end{array}\end{array}\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\end{array}\right]=\left[\begin{array}{c}{b}_0\\ b_0+b_1\\ b_0+b_1+b_2\\ b_0+b_1+b_2+b_3\end{array}\right]$ (14)

$Y{b}_j=\left[\begin{array}{cc}\begin{array}{cc}1& 1\\ 0& 1\end{array}& \begin{array}{cc}1& 1\\ 1& 1\end{array}\\ \begin{array}{cc}0& 0\\ 0& 0\end{array}& \begin{array}{cc}1& 1\\ 0& 1\end{array}\end{array}\right]\left[\begin{array}{c}{b}_4\\ b_5\\ b_6\\ b_7\end{array}\right]=\left[\begin{array}{c}{b}_7+b_6+b_5+b_4\\ b_7+b_6+b_5\\ b_7+b_6\\ b_7\end{array}\right]$ (15)

$Y{b}_i=\left[\begin{array}{cc}\begin{array}{cc}1& 1\\ 0& 1\end{array}& \begin{array}{cc}1& 1\\ 1& 1\end{array}\\ \begin{array}{cc}0& 0\\ 0& 0\end{array}& \begin{array}{cc}1& 1\\ 0& 1\end{array}\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\end{array}\right]=\left[\begin{array}{c}{b}_3+b_2+b_1+b_0\\ b_3+b_2+b_1\\ b_3+b_2\\ b_3\end{array}\right]$ (16)

$X{b}_j=\left[\begin{array}{cc}1& \begin{array}{ccc}0& 0& 0\end{array}\\ \begin{array}{c}1\\ 1\\ 1\end{array}& \begin{array}{ccc}\begin{array}{c}1\\ 1\\ 1\end{array}& \begin{array}{c}0\\ 1\\ 1\end{array}& \begin{array}{c}0\\ 0\\ 1\end{array}\end{array}\end{array}\right]\left[\begin{array}{c}{b}_4\\ b_5\\ b_6\\ b_7\end{array}\right]=\left[\begin{array}{c}{b}_4\\ b_4+b_5\\ b_4+b_5+b_6\\ b_4+b_5+b_6+b_7\end{array}\right]$ (17)

$X{b}_i+Y{b}_j=\left[\begin{array}{c}{b}_0\\ b_0+b_1\\ b_0+b_1+b_2\\ b_0+b_1+b_2+b_3\end{array}\right]+\left[\begin{array}{c}{b}_7+b_6+b_5+b_4\\ b_7+b_6+b_5\\ b_7+b_6\\ b_7\end{array}\right]=\left[\begin{array}{c}{b}_0+b_7+b_6+b_5+b_4\\ b_0+b_1+b_7+b_6+b_5\\ b_0+b_1+b_2+b_7+b_6\\ b_0+b_1+b_2+b_3+b_7\end{array}\right]$ (18)

$Y{b}_i+X{b}_j=\left[\begin{array}{c}{b}_3+b_2+b_1+b_0\\ b_3+b_2+b_1\\ b_3+b_2\\ b_3\end{array}\right]+\left[\begin{array}{c}{b}_4\\ b_4+b_5\\ b_4+b_5+b_6\\ b_4+b_5+b_6+b_7\end{array}\right]=\left[\begin{array}{c}{b}_3+b_2+b_1+b_0+b_4\\ b_3+b_2+b_1+b_4+b_5\\ b_3+b_2+b_4+b_5+b_6\\ b_3+b_4+b_5+b_6+b_7\end{array}\right]$ (19)

The result is

$\left[\begin{array}{c}{e}_0\\ e_1\\ e_2\\ e_3\\ e_4\\ e_5\\ e_6\\ e_7\end{array}\right]=\left[\begin{array}{c}{b}_0+b_7+b_6+b_5+b_4\\ b_0+b_1+b_7+b_6+b_5\\ b_0+b_1+b_2+b_7+b_6\\ b_0+b_1+b_2+b_3+b_7\\ b_3+b_2+b_1+b_0+b_4\\ b_3+b_2+b_1+b_4+b_5\\ b_3+b_2+b_4+b_5+b_6\\ b_3+b_4+b_5+b_6+b_7\end{array}\right]$ (20)

and this satisfies:

$e_i=b_i+b_{\left(i+4\right)\mathrm{mod}\left(8\right)}+b_{\left(i+5\right)\mathrm{mod}\left(8\right)}+b_{\left(i+6\right)\mathrm{mod}\left(8\right)}+b_{\left(i+7\right)\mathrm{mod}\left(8\right)},0\le i\le 7$ (21)

At the last, to find $\left(c_7{c}_6{c}_5{c}_4{c}_3{c}_2{c}_1{c}_0\right)$ , we add $\left(e_7{e}_6{e}_5{e}_4{e}_3{e}_2{e}_1{e}_0\right)$ to $01100011$ .

3. Results

The matrices: $X{b}_i,Y{b}_j,Y{b}_i$ and $X{b}_j$ are just $\left(b_7{b}_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0\right)$ with some XOR operations. When multiplying X by $b_i$ or $b_j$ , the result will be:

(first element, first + second, first + second + third, first + second + third+ fourth) of $b_i$ or $b_j$ , and when multiplying Y by $b_i$ or $b_j$ , starting from the fourth element, the result will be:

(First + second + third + fourth, second + third + fourth, third + fourth, fourth) of $b_i$ or $b_j$ .

So, we can find $\left(e_7{e}_6{e}_5{e}_4{e}_3{e}_2{e}_1{e}_0\right)$ from $\left(b_7{b}_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0\right)$ directly.

4. Example

To encrypt:

Input: 32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34

Key: 2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C

using AES [1] .

Let us do the first step (Rijndael ByteSub transformation).

$\left[\begin{array}{cc}32& \begin{array}{ccc}88& 31& E0\end{array}\\ \begin{array}{c}43\\ F6\\ A8\end{array}& \begin{array}{ccc}\begin{array}{c}5A\\ 30\\ 8D\end{array}& \begin{array}{c}31\\ 98\\ A2\end{array}& \begin{array}{c}37\\ 07\\ 34\end{array}\end{array}\end{array}\right]+\left[\begin{array}{cc}2B& \begin{array}{ccc}28& AB& 09\end{array}\\ \begin{array}{c}7E\\ 15\\ 16\end{array}& \begin{array}{ccc}\begin{array}{c}AE\\ D2\\ A6\end{array}& \begin{array}{c}F7\\ 15\\ 88\end{array}& \begin{array}{c}CF\\ 4F\\ 3C\end{array}\end{array}\end{array}\right]=\left[\begin{array}{cc}19& \begin{array}{ccc}\mathrm{..}& \mathrm{..}& \mathrm{..}\end{array}\\ \begin{array}{c}\mathrm{..}\\ \mathrm{..}\\ \mathrm{..}\end{array}& \begin{array}{ccc}\begin{array}{c}\mathrm{..}\\ \mathrm{..}\\ \mathrm{..}\end{array}& \begin{array}{c}\mathrm{..}\\ \mathrm{..}\\ \mathrm{..}\end{array}& \begin{array}{c}\mathrm{..}\\ \mathrm{..}\\ \mathrm{..}\end{array}\end{array}\end{array}\right]$

We just transform the element {19},

$19=00011001=x^4+x^3+1$

Computing the multiplicative inverse, (look at Table 3).

Since $r_2=1$ ,

$\begin{array}{c}T=T_2\\ =q_2{T}_1+T_0\\ =x\left(x^4+x^3+x^2+x+1\right)+1\\ =x^5+x^4+x^3+x^2+x+1\\ =00111111\end{array}$

Now, we take $\left(00111111\right)$ , to do the second operation.

$\left[\begin{array}{c}1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 0\\ 0\end{array}\right]\to \frac{\left[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right]+\left[\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right]}{\left[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right]+\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]}\to \left[\begin{array}{c}1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\end{array}\right]$

Then we add the result to $\left(01100011\right)$

$\left[\begin{array}{c}1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\end{array}\right]+\left[\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 1\\ 0\\ 1\\ 0\\ 1\\ 1\end{array}\right]$

So,

$19\to 11010100=D4$

5. Conclusion

The modern technique proposed in this work equivalently finds the Rijndael byte substitute transformation without a need to compute multiplicative inverses and matrices multiplication by traditional methods.