INTRODUCTION
Since, Rijndael (Cheon and Lee, 2004; Demirci et al., 2013), the SPNStructure block cipher algorithm designed by Vincent Rijmen and Joan Danmen was chosen by NIST as the Advanced Encryption Standard (AES) on October, 2, 2000, many schemes have been proposed to attack it (Zhang et al., 2011; Kim et al., 2007; Chen et al., 2011). It has been proved that Rijndael has the security against differential attack and linear attack which are the most well known attacks on block ciphers. Because of the simple algebraic structure of Rijndael Sbox, many cryptanalysts focus on the algebraic attack which may be an efficient method. As the only nonlinear component of Rijndael, Sbox is a crucial element and it determines the performance of Rijndael.
Many researchers devote time to design and improve the algebraic cryptanalysis scheme (Zhang et al., 2007; Ghosh and Das, 2012; Cheon and Lee, 2004). Courtois and Pieprzyk (2002) analyzed the overdefined system and proposed XSL attack on Rijndael. Hussain et al. (2013) analyzed the algebraic structure of Rijndael Sbox and proposed a new Sbox structure. Much study has concentrated on Rijndael Sbox, however they did not explicitly give the approach to generating its multivariate quadratic equation system over GF(2). Murphy and Robshaw (2002) showed that the Rijndael preserves algebraic curves and that it can be expressed as a very simple system of multivariate quadratic equations over GF(2^{8}). Cheon and Lee (2004) proposed a new system of multivariate quadratic equations over GF(2^{8}) to describe completely Rijndael in 2004. There have been few research results of the equation system optimization in recent years.
In this study a new approach to generating the multivariate quadratic equations of Rijndael Sbox over GF(2) is given explicitly and an equation system over GF(2^{8}) is proposed to describe the new Rijndael Sbox. This study is organized into sections: Principle of Rijndael Sbox, new approach to generating multivariate quadratic equation system of Rijndael Sbox, the optimization of Rijndael Sbox equation system and conclusion.
PRINCIPLE OF RIJNDAEL SBOX
Looking upon 8bit bytes as elements in GF(2^{8}), Rijndael Sbox is a combination of an inverse function I(x) which is the multiplicative inverse modulo the irreducible polynomial x^{8}+x^{4}+x^{3}+x+1 and an affine transformation function A(x). The I(x) and A(x) are as follows:
•  The inverse function I(x) is defined as: 
•  The affine transformation function A(x) is defined as: 
where, x_{i}(i = 0,…, 7) are the bits of the byte x and x_{7} is the most significant bit. Therefore, Rijndael Sbox can be denoted by:
From the construction principle of Rijndael Sbox, the algebraic expression of Rijndael Sbox can be derived as follow:
S(x) = 05x^{FE}+09x^{FD}+F9x^{FB}+25x^{F7}+F4x^{EF}+01x^{DF}+
B5x^{BF}+8Fx^{7F}+63
NEW APPROACH TO GENERATING MQ EQUATION SYSTEM OF RIJNDAEL SBOX
Rijndael Sbox is a composition of the “patched” inverse in GF(2^{8}) with 0 mapped on itself with a multivariate affine transformation GF(2^{8})→GF(2^{8}). We call these functions, respectively g and f and we call S = fBg. We note x an input value and y = g(x) the corresponding output value. We will also note z = S(x) = f(y) = f(g(x)).
For inverse transformation y = g(x), obviously xy = 1 when x ≠ 0. i.e.:
Expanding the Eq. 1, we have:
where, m(t) = t^{8}+t^{4}+t^{3}+t+1.
Comparing the both sides coefficients of t^{k}(0≤k<8) in Eq. 1, we can obtain the 8 multivariate quadratic equations of inverse transformation. Since, is linear, we can obtain 8 multivariate quadratic equations of Rijndael Sbox.
Now, we give the generation principle of Rijndael Sbox equation system. Multiplying x by y and the multiplication result modulo m(t), we can obtain the coefficients c_{7},…, c_{0} of t^{k}(0≤k<8). Firstly, we give the computation process of the coefficients c_{7},…, c_{0}.
We note (x_{7},…, x_{0}) = x, (y_{7},…, y_{0}) = y and (z_{7},…, z_{0}) = z. i.e.,:
We have:
The multiplication result modulo m(t) one by one and we give the process in detail as follows:
Step 1:x⊗y modulo:
x_{7}y_{7}•t^{14}+x_{7}t_{7}•t^{10}+x_{7}y_{7}•t^{9}+x_{7}y_{7}•t^{7}+x_{7}y_{7}•t^{6} = R1
Step 2:R1 modulo:
(x_{7}y_{6}+x_{6}y_{7})•t^{13}+(x_{7}y_{6}+x_{6}y_{7})•t^{9}+(x_{7}y_{6}+x_{6}y_{7})•t^{8}+(x_{7}y_{6}+x_{6}y_{7})•
t^{6}+(x_{7}y_{6}+x_{6}y_{7})•t^{5} = R2
Step 3:R2 modulo:
(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{12}+(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{8}+
(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{7}+(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{5}+(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})
t^{4 }= R3
Step 4:R3 modulo:
(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{11}+(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{7}+
(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{6}+(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{4}+
(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{3} = R4
Step 5:R4 modulo:
(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{10}+
(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{6}+
(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{5}+
(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{3}+
(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{2} = R5
Step 6:R5 modulo:
(x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+
x_{7}y_{6}+x_{6}y_{7})•t^{9}+(x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+
x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•t^{5}+(x_{7}y_{2}+x_{6}y_{3}+
x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•t^{4}+(x_{7}y_{2}+
x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•
t^{2}+(x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•
t = R6
Step 7:R6 modulo:
(x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{6}+
x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{8}+(x_{7}y_{1}+x_{6}y_{2}+
x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+
x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{4}+(x_{7}y_{1}+
x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+
x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{3}+(x_{7}y_{1}+
x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{6}+
x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t+(x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+
x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{6}+x_{6}y_{7}+
x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7}) = R7
R7 = (x_{7}y_{0}+x_{6}y_{1}+x_{5}y_{2}+x_{4}y_{3}+x_{3}y_{4}+x_{2}y_{5}+x_{1}y_{6}+
x_{0}y_{7}+x_{7}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+
x_{4}y_{7})•t^{7}+x_{6}y_{0}+x_{5}y_{1}+x_{4}y_{2}+x_{3}y_{3}+x_{2}y_{4}+x_{1}y_{5}+x_{0}y_{6}+
x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7}+x_{7}y_{3}+
x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7})•t^{6}+(x_{5}y_{0}+x_{4}y_{1}+x_{3}y_{2}+x_{2}y_{3}+
x_{1}y_{4}+x_{0}y_{5}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7}+x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6
}+x_{3}y_{7}+x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7})•t^{5}+(x_{4}y_{0}+
x_{3}y_{1}+x_{2}y_{2}+x_{1}y_{3}+x_{0}y_{4}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7}+
x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{1}+x_{6}y_{2}+
x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7})•t^{4}+(x_{3}y_{0}+x_{2}y_{1}+x_{1}y_{2}+
x_{0}y_{3}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7}+x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6
}+x_{3}y_{7}+x_{7}y_{7}+x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+
x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{3}+(x_{2}y_{0}+x_{1}y_{1}+x_{0}y_{2}+x_{7}y_{3}+x_{6}y_{4}+
x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{6}+x_{6}y_{7})
•t^{2}+(x_{1}y_{0}+x_{0}y_{1}+x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+
x_{7}y_{7}+x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{5}+
x_{6}y_{6}+x_{5}y_{7})•t+(x_{0}y_{0}+x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+
x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})
Now we obtain the coefficients c_{7},…, c_{0} from R7 as Eq. 3.
Then, we give the generation process of the 24 multivariate quadratic equations. According to the principle of Rijndael Sbox, the relationship between z and y can be denoted as:
z = Ay+‘63’
We can get:
y = A^{1}z+A^{1}. ‘63’ = A^{1}z+‘05’
Where:
Then we get:
Substituting Eq. 4 into 3, we obtain 8 multivariate quadratic equations of Sbox as Eq. 5:
Since, there is no nonzero const term in 7 of these equations in Eq. 5, for x = 0, these 7 equations are true with probability 1. The 8th equation is true when, x ≠ 0, so this equation is true with probability 255/256.
Since, xy = 1(∀x ≠ 0) we can get:
∀x ≠ 0 x = x^{2}y
Obviously, this equation is also true when x = 0, so we have:
We might as well choose the last equation in Eq. 6. It is symmetric with respect to the exchange of x and y, so we can obtain the following two equations:
Then we have two equations over GF(2^{8}) are true with probability 1. Because is linear, each of above two equations will give eight quadratic equations with eight variables. Similarly, we can obtain these sixteen equations as Eq. 7 and 8:
From Eq. 7 and 8, we have 23 quadratic equations between x_{i} and z_{j} that are true with probability 1. We have explicitly generated these equations have verified that they are all linearly independent and have also verified that there are no more such equations. It is easy to find that there is no terms in x_{i}x_{j} or z_{i}z_{j} in the above 23 equations and the terms present in these equations are t = 81: these are {x_{1}z_{1},…x_{8}z_{8}, z_{1},…z_{8}, x_{1},…x_{8}, 1}:
OPTIMIZATION OF RIJNDAEL SBOX EQUATION SYSTEM
Definition 1: Cheon and Lee (2004). For r equations in t terms over GF(2^{n}), the Resistance of Algebraic Attacks (RAA) is denoted by Γ and is defined as follow:
Γ = ((tr)/n)^{j(tr)/nk}
The resistance of algebraic attacks reflects a difficulty of solving multivariate equations. Thus we will use this quantity to measure the resistance of algebraic attacks in this study.
Definition 2: An AffineInverseAffine (AIA) Sbox is defined as follow:
where, A denotes the affine transformation and I denotes the inverse transformation in GF(2^{8}).
Equation system of the AIA structure rijndael Sbox: In the Cui et al. (2011), we designed a new Rijndael Sbox structure named AffineInverseAffine (AIA) to increase the algebraic complexity of Rijndael Sbox. Now we analyze the equation system of the new Rijndael Sbox.
We obtain the coefficients of the algebraic expression of the new Rijndael Sbox as Table 1.
From Table 1 and the algebraic expression of Rijndael Sbox, it can be seen that the algebraic expression of Rijndael Sbox is very simple (i.e., only 9 terms are involved) while the new Rijndael Sbox involves 255 terms and is very complex.
From Table 1, it is easy to see that the algebraic expression of the new Rijndael Sbox is as follow:
S’(x) = Fax^{∞}+A6x^{01}+A9x^{02}+…+E7x^{FC}+26x^{FD}+12x^{FE
}= FA+A6(x^{1})^{254}+A9(x^{1})^{253}+…+E7(x^{1})^{3}+26(x^{1})^{2}+12x^{1
}= FA+A6y_{253}+A9y_{252}+…+E7y_{2}+26y_{1}+12y_{0}
where, y_{0} = x^{1}, y_{1} = (x^{1})^{2}, y_{2} = (x^{1})^{3},…, y_{252} = (x^{1})^{253}, y_{253} = (x^{1})^{254} and it can be denoted as S(x) = g(y_{0}, y_{1},…, y_{252}, y_{253}).
We denote by the (j, k)th input byte variable of the th round Sbox function. In consequence we denote the intermediate variable by and the output variable by According to the algebraic expression of the new Rijndael Sbox, the (j, k)th Sbox transformation of the th round can be described as the following quadratic equations over GF(2^{8}):
where, 0≤i≤9, 0≤j, k≤3.
Table 1: 
Coefficients of algebraic expression of the new Rijndael Sbox 

Table 2: 
Comparisons of equation systems of Rijndael Sbox 

The last linear equation can be seen as another linear transformation after Sbox transformation. From the Eq. 9, it can be seen that each Sbox has 255 quadratic equations. Then, the total 255 quadratic equations of the new Rijndael Sbox are obtained.
These 255 quadratic equations comprise a total of 510 terms: 1,
For the new Rijndael Sbox, it is easy to obtain that t = 510, r = 255, n = 8. According to the definition 1, it can be obtained that Γ = 31.875^{32} ≈ 2^{160}.
Comparison with the existing equation systems: Table 2 shows the comparison results. As can be seen from Table 2 for each Sbox, the equation system (Murphy and Robshaw, 2002) comprises 24 quadratic equations of 41 terms over GF(2^{8}) and the equation system (Li and Chen, 2004) comprises 17 quadratic equations of 34 terms over GF(2^{8}) while our equation system comprises 255 quadratic equations of 510 terms over GF(2^{8}).
According to the definition of RAA, we can obtain that the RAA of the equation system (Murphy and Robshaw, 2002; Li and Chen, 2004; Xiao and Zhang, 2008) are 9.6, 9.6 and 2^{8}, respectively. However, our equation system has the following property: Γ = 2^{160}. Cheon and Lee (2004) pointed out that should be greater than 2^{32 }for secure ciphers.
This suggests that the complexity of solving our equation system is much more than that of solving other existing equation systems. Our work is helpful to improving the security of Rijndael cipher.
CONCLUSION
In this study, a new approach to generating the multivariate quadratic equation system over GF(2) is proposed and an equation system over GF(2^{8}) is proposed to describe the new Rijndael Sbox. Firstly, the construction principle and the algebraic expression of Rijndael Sbox are described. Secondly, a new approach to generating the multivariate quadratic equation system over GF(2) is proposed and the generation process of the multivariate quadratic equations is given explicitly. Finally, an equation system over GF(2^{8}) is proposed to describe the new Rijndael Sbox and it suggest that the new equation system has stronger resistance against algebraic attacks than other existing equation systems.
ACKNOWLEDGMENT
The study was supported by the National Natural Science Foundation of China (No. 61173188, 61173187, 61272074), the Educational Commission of Anhui Province, China (No. KJ2013A017), the Research Fund for the Doctoral Program of Higher Education (No. 20133401110004) and the Doctoral Research Startup Funds Project of Anhui University. The authors are very grateful to Chinchen Chang and the anonymous referees for their detailed comments and suggestions regarding this study.