Research Article  Open Access
Sajjad Shaukat Jamal, Dawood Shah, Abdulaziz Deajim, Tariq Shah, "The Effect of the Primitive Irreducible Polynomial on the Quality of Cryptographic Properties of Block Ciphers", Security and Communication Networks, vol. 2020, Article ID 8883884, 14 pages, 2020. https://doi.org/10.1155/2020/8883884
The Effect of the Primitive Irreducible Polynomial on the Quality of Cryptographic Properties of Block Ciphers
Abstract
Substitution boxes are the only nonlinear component of the symmetric key cryptography and play a key role in the cryptosystem. In block ciphers, the Sboxes create confusion and add valuable strength. The majority of the substitution boxes algorithms focus on bijective Boolean functions and primitive irreducible polynomial that generates the Galois field. For binary field F2, there are exactly 16 primitive irreducible polynomials of degree 8 and it prompts us to construct 16 Galois field extensions of order 256. Conventionally, construction of affine power affine Sbox is based on Galois field of order 256, depending on a single degree primitive irreducible polynomial over . In this manuscript, we study affine power affine Sboxes for all the distinct degree primitive irreducible polynomials over to propose 16 different substitution boxes. To perform this idea, we introduce 16 affine power affine transformations and, for fixed parameters, we obtained 16 distinct Sboxes. Here, we thoroughly study Sboxes with all possible primitive irreducible polynomials and their algebraic properties. All of these boxes are evaluated with the help of nonlinearity test, strict avalanche criterion, bit independent criterion, and linear and differential approximation probability analyses to measure the algebraic and statistical strength of the proposed substitution boxes. Majority logic criterion results indicate that the proposed substitution boxes are well suited for the techniques of secure communication.
1. Introduction
The exchange of digital data through the Internet has revolutionized the communication parameters over the years. But this rapid communication also provides opportunities to access this digital data illegally. For this reason, the security of this content on the Internet has become a serious challenge for the researchers of different fields. To counter the emerging challenges of security, cryptography and steganography are used to hide the secret information whereas watermarking is used for copyright protection. In this manuscript, we discuss cryptography and relevant aspects of this field. For convenience, cryptography is divided into two types named symmetric key cryptography and asymmetric key cryptography. In symmetric key cryptography, two parties share secret information and keys during encryption and decryption procedures. The private key is shared by both sender and receiver. In addition to this, block ciphers and stream ciphers are two main branches of symmetric key cryptography. In 1949, Shannon gave the idea of block cipher and some examples of block ciphers are Advanced Encryption Standard (AES) [1], Data Encryption Standard (DES), International Data Encryption Algorithm (IDEA), and many more [2, 3]. In AES, there is availability of three different key sizes such as 128, 192, and 256 bits, whereas in DES, the only available key size is 56 bits. The AES has 10, 12, and 14 rounds for key sizes of 128, 192, and 256 bits, respectively. All these rounds have four basic steps, that is, subbyte, shift row, mix column, and add round key. Subbyte is the step which substitutes the plaintext data with substitution box (Sbox). This Sbox is the only nonlinear part of block cipher used in different wellknown cryptosystems. It is used to create confusion to make plaintext data obscure for any attacker and hence Sbox is an integral part of any cryptosystem. Sbox is a function which has input and output from the Galois field. The Galois field is a finite field having order 256 and denoted by .
1.1. Related Work
Sbox is used to create confusion as observed in AES, International Data Encryption Algorithm (IDEA), DES, and many more cryptosystems [4]. It is an established fact that the strength of block cipher depends on the standard and quality of Sbox. Due to the necessary immersion of Sbox to generate nonlinearity, intricacy persuades different researchers to design strong Sboxes to enhance the security level of cryptosystems. Among different available methods, the algebraic structurebased construction of Sboxes has much more attention. These Sboxes have strong cryptographic features and are robust against linear and differential cryptanalysis.
In the literature, different structural advancements are viewed to improve the quality of Sboxes. The algebraic complexity of AES Sbox has been improved with the extension of this Sbox, that is, affine power affine (APA) [5]. Furthermore, the symmetric group S_{8} has also been applied to AES Sbox to improve the quality and numbers of Sboxes [6]. Similarly, the application of transformation using binary gray codes on AES Sbox gives Gray Sbox [7]. In [8], Sboxes are constructed by using the projective general linear group (PGL). Moreover, the construction scheme of chaotic Sboxes using DNA sequence and chaotic Chen system is given in [9, 10]. Different analytical, algebraic, and chaosbased techniques for the construction of Sboxes are given in [11–16]. Conventionally, AES uses a polynomial of 8 terms which have all the required properties and improves the security for AES. But the Gray Sbox has a term polynomial. Moreover, residue prime, Xyi, and Skipjack Sboxes are frequently used for the encryption and decryption schemes [17, 18].
It is assumed that the model of Boolean functions and primitive irreducible polynomial has an impact on the strength of Sbox. In [19], different primitive irreducible polynomials have been used to identify the effect of primitive irreducible polynomial. To investigate this fact, we want to study all the primitive irreducible polynomials to understand whether there is an impact of irreducible polynomial or not. Archetypally in the synthesis of an Sbox, the numbers and in affine transformation belong to Galois field . As the polynomial ring has 16 primitive irreducible polynomials of degree 8, it shows that only 16 opportunities are available for constructing Galois fields . In this paper, we have constructed 16 different robust Sboxes over the elements of these 16 irreducible polynomials. Firstly, we define 16 affine power affine transformations on these different Galois fields which can be given as ; here, for values, we would be able to get 16 distinct Sboxes.
1.2. Motivation
Due to the role of Sboxes in cryptosystems, it is essential to explore all of its aspects. The motivation behind this work is to study all primitive irreducible polynomials and their role in the construction of Sboxes.(1)The Mobius transformation used in a different construction of Sboxes has certain limitations and restrictions in its structure [7]. For example, the condition on the parameters, i.e., squeezes the remaining cases. Hence, there is a need for any other transformation.(2)There are 16 primitive irreducible polynomials in the principal ideal domain whose impact was not studied yet regarding their impression on analyses of Sboxes.(3)By exploring all primitive irreducible polynomials, we have a better opportunity to obtain the cryptographically strong cryptosystems.
1.3. Our Contribution
In this manuscript, we studied all binary degree 8 primitive irreducible polynomials for the construction of Sboxes. The quality of the proposed work can be seen from the different security analyses and resistance against malicious attacks. This whole study can be summarized as follows:(1)We constructed Sboxes associated with the 16 binary degree 8 primitive irreducible polynomials.(2)The APA transformation is used in this work, which is bijective and has no restrictions on the parameters.(3)To evaluate the strength of the proposed Sboxes, we have performed different analyses along with differential cryptanalysis. The outcomes of these analyses are compared with the wellknown Sboxes.
The remaining part of the paper is planned as follows: Section 2 presents the preliminaries and construction scheme of the proposed Sboxes. In Section 3, algebraic and statistical analyses are calculated in detail. Section 4 presents definitions of the balanced Boolean function. Section 5 concludes the paper.
2. Primitive Irreducible Polynomials of Degree 8 and GF (2^{8})
2.1. The Galois Fields
We summarize here some wellknown facts from the theory of rings and fields. Let be a commutative ring with identity. A nonempty subset of is called an ideal of if is an additive subgroup of and for every , where . If, furthermore, there does not exist a proper ideal of properly containing , then we say that is a maximal ideal of Besides; is said to be a field if each of its nonzero elements has a must inverse in . If is a field of prime characteristic , then is an extension of the prime field . A polynomial is said to be irreducible if it cannot be factored in into two polynomials of strictly smaller degrees. The principal ideal,generated by a monic irreducible polynomial is a maximal ideal in . If is of degree , then the quotient ring,is an extension field of of degree consisting of elements. This field is called a Galois field and is denoted by and is said to be the field extension of defined by the irreducible polynomial . A representative of each element of can be chosen to be of degree strictly less than . If is a root of in an algebraic closure of , then is isomorphic to the field:and so we can identify the two fields. Furthermore, if is a generator of the cyclic finite multiplicative group of nonzero elements of , then we say that is primitive.
The Galois field is particularly of specific interest in cryptographic applications, especially in Sboxes constructions. For our cryptographic purposes, we are interested in such a field whose defining irreducible polynomial is “primitive” (of degree 8, of course). It is well known that there are such polynomials over , for example, , which we list in Table 1. In the following section, we construct 16 Sboxes out of the Galois fields corresponding to the aforementioned sixteen primitive irreducible polynomials.

2.2. The Proposed SBox Construction Method
For each , consider the affine power affine map (APA):where and are two affine maps with , and
Among other things, the map , which is obviously bijective, was introduced by [5] to produce confusion in the scheme. For our Sboxes, we choose , and and Figure 1 demonstrates the flow chart of the construction of the 16 different Sboxes. Moreover, the construction of Sboxes in correspondence to polynomial 1 (P_{1}) to polynomial 16 (P_{16}) is shown in Figure 1. All the Sboxes are given in Tables 2–17, corresponding to P_{1} to P_{16}. These tables are before the conclusion section.
















In the proposed work, we present an APA Sbox corresponding to each where the APA map gives the lookup tables. We, then, show that these Sboxes have strong cryptographic properties certified with the help of analyses such as nonlinearity, strict avalanche criterion (SAC), bit independent criterion (BIC), linear approximation probability (LP), and differential approximation probability (DP) [20].
3. Security Analysis
In this section, we present some algebraic and statistical analyses of Sbox followed [21]. Such analyses indicate the strength of all the proposed Sboxes and give an idea for their application in image encryption and other modes of secure communication.
3.1. Nonlinearity
Nonlinearity analysis of a function is the minimum hamming distance between the Boolean function : and its all nbit affine functions. In the truth table of Boolean function , the nonlinearity of represents the degree of dissimilarity between and all affine function. If the function has high minimum hamming distance, it indicates it has high nonlinearity. It is an established fact that high nonlinearity provides resistance to any kind of linear approximation attacks [22, 23]. The calculated upper bound of nonlinearity is so that, for, the optimal value of nonlinearity is. Table 18 shows the nonlinearity of 16 Sboxes corresponding to all primitive irreducible polynomials. From this table, it can be seen that the value of nonlinearity has not been affected due to background irreducible polynomial.

3.2. Strict Avalanche Criteria
In [24], Webster and Tavares introduced the strict avalanche criteria (SAC) on the concepts of completeness and avalanche. If a single input bit changes, the output bits change with almost 0.5 probability. It helps to show that the resulting output vector is highly random, and no single pattern can be predictable by minor variation in the input vector [25]. By seeing the performance indexes of Sboxes, the proposed Sboxes successfully satisfy SAC. Table 19 depicts the value of SAC for all the proposed 16 Sboxes. It shows that the maximum value of SAC is 0.562500 for the first 9 Sboxes including 11^{th}, 14^{th}, and 16^{th} Sboxes. Similarly, the minimum value of SAC is 0.453125 for the first 10 Sboxes including 12^{th} and 14^{th} Sboxes. The average value of SAC lies in the interval [0.4856, 0.509766].

3.3. Bit Independent Criterion
Another algebraic criterion (BIC) is used to evaluate the strength of Sbox, which is presented by Detombe and Tavares in [26]. In Table 14, the outcomes of BIC to SAC and BIC for the proposed Sboxes are given. The minimum BIC to SAC value is 0.47070 for 12^{th} Sbox and the highest minimum value is 0.49219 for 2^{nd} Sbox. The average BIC to SAC lies between 0.49679 and 0.50739. Similarly, the square deviation values for all the proposed Sboxes are given in Table 20. The maximum and average value of BIC is 112 for all Sboxes. It is depicted that the proposed Sboxes give the nearest best value of BIC analyses.

3.4. Linear Approximation Probability
Matsui defines the extreme value of the imbalance of an event as the linear approximation probability. It is notable that the parity of the input bits that is, the mask , is equal to the parity of the output bits, i.e., the mask . The linear approximation probability of a given Sbox is defined in the following equation:where and are input and output masks, respectively, and the set represents the set of all possible inputs; is the number of elements of. The value of linear approximation indicates the strength of Sbox against various linear attacks. In Table 21, the maximum count and the LP value for all proposed Sboxes is 144 and 0.0625. These values of LP of the proposed Sboxes are appropriate against linear attacks.

3.5. Differential Approximation Probability
The degree of differential uniformity is known as differential approximation probability (DP^{s}) of Sbox. Mathematically, it can be given as
Briefly, it can be explained as follows: an input differential must be mapped to an output differential uniquely for each i. Here, represents all the possible input values and the number of its elements is given by . Table 21 depicts the results of DP, which include the maximum and DP value.
Moreover, Table 22 represents the values of proposed Sboxes along with AES, Skipjack, Xyi, APA, Gray, and residue prime Sboxes.

3.6. Statistical Analyses
To evaluate the visual strength of the substitution with the help of the proposed Sboxes, various statistical analyses are made on the host and substituted images. In this proposed work, statistical analyses like homogeneity, entropy, contrast, energy, and correlation are used to evaluate the substitution ability of the 16 proposed Sboxes. These analyses are given aswhere give the row and column locations of an image. The pixel value at k^{th} row and l^{th} column is represented by and is the probability of the image pixel. In equation (8), are mean and standard deviation, respectively.
Correlation analysis helps to find the similarity between the host and substituted image. The correlation analysis provides the range which indicates the perfect, negative, and positive correlation. This is interval for correlation and value of 1 indicates the perfect correlation.
The randomness of the digital image can be calculated with the help of entropy. The higher value of entropy from the interval represents the higher amount of randomness in a digital image. For any viewer, it is only possible with the help of contrast analysis to intensely recognize the objects in the texture of an image. With the help of contrast analyses, one can observe the maximum distinction in image pixels. The range of the contrast can be given by. For constant image, the value of contrast is zero. The goal of finding close distribution between the matrix and its diagonal is obtained in homogeneity analysis. The matrix used in this analysis is named gray level cooccurrence matrix (GLCM) and the range of homogeneity lies between 0 and 1. The range for energy analysis also lies in the interval [0, 1]. The results of Table 23 are obtained by applying these analyses on the original and encrypted images. For all the proposed 16 Sboxes, we calculated the values of the statistical analyses.

A 256 × 256 JPEG image of Lena is considered for MLC analysis. Figure 2 shows the results of image encryption with 16 proposed Sboxes.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)
(q)
4. Balanced Boolean Function
4.1. Balance Property
The imbalance of a Boolean function weak system against linear cryptanalysis highlights the importance of balance property. The balance property indicates that the higher the magnitude of a function’s imbalance, the more the chances of a high probability linear approximation. A Boolean function is balanced. If the cardinality or Hamming weight of these two functions, that is, is the same, then it is named the balance function.
4.2. Balance Property of the Proposed SBox
All the Boolean functions involved in proposed Sboxes are balanced just like the Boolean functions of AES, , AES and other wellknown Sboxes. The nonlinearity of the proposed Sboxes is equal to 112.
5. Conclusion
In this paper, a scheme for the synthesis of Sboxes over 16 isomorphic Galois fields is presented. Here, we fixed all the parameters of affine power affine transformation, that is, for 16 Sboxes. We have 16 primitive irreducible polynomials of degree 8 and they prompt us to construct 16 Galois field extensions of order 256. By using elements of the Galois field, corresponding to each different pair of the parameters, one can construct different Sboxes. These Sboxes obtained as a result of APA transformation which is bijective, pass nonlinearity test, and out bit independent criterion (BIC) which demonstrates that the existing Sboxes have high confusion producing capability. The evaluation of constructed Sboxes is done with some algebraic and statistical analyses. The results of these analyses highlight the characteristics of all the proposed Sboxes and later these Sboxes are equated with some of the existing Sboxes. In addition to this, we also ensured that all these constructed Sboxes are balanced that guarantee the strength of our Sboxes. Hence, we have concluded that a large class of Sboxes can be obtained by varying parameters of affine power affine transformations. These Sboxes can be used for secure communication.
Data Availability
The data that support the findings of this study are available from the corresponding author upon reasonable request.
Conflicts of Interest
There are no conflicts of interest among the authors.
Acknowledgments
The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through research groups program under Grant no. R.G.P. 1/234/41.
References
 J. Daemen and V. Rijmen, “The design of Rijndael: AES,” in The Advanced Encryption Standard, Springer, Berlin, Germany, 2002. View at: Google Scholar
 R. Zimmermann, A. Curiger, H. Bonnenberg, H. Kaeslin, N. Felber, and W. Fichtner, “A 177 Mb/s VLSI implementation of the international data encryption algorithm,” IEEE Journal of SolidState Circuits, vol. 29, no. 3, pp. 303–307, 1994. View at: Publisher Site  Google Scholar
 E. Biham and A. Shamir, “Differential cryptanalysis of DESlike cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3–72, 1991. View at: Publisher Site  Google Scholar
 National Bureau of Standards, Data Encryption Standard, vol. 46, FIPS Publication, U.S. Department of Commerce, Washington, DC, USA, 1977.
 L. Cui and Y. Cao, “A new Sbox structure named affinepoweraffine,” International Journal of Innovative Computing, Information and Control, vol. 3, no. 3, pp. 751–759, 2007. View at: Google Scholar
 I. Hussain, T. Shah, H. Mahmood, and M. A. Gondal, “Construction of S8 Liu J Sboxes and their applications,” Computers & Mathematics with Applications, vol. 64, no. 8, pp. 2450–2458, 2012. View at: Publisher Site  Google Scholar
 M. T. Tran, D. K. Bui, and A. D. Duong, “Gray Sbox for advanced encryption standard,” in Proceedings of the 2008 International Conference on Computational Intelligence and Security, vol. 1, IEEE, Suzhou, China, December 2008. View at: Publisher Site  Google Scholar
 T. Shah and D. Shah, “Construction of highly nonlinear Sboxes for degree 8 primitive irreducible polynomials over ℤ2,” Multimedia Tools and Applications, vol. 78, no. 2, pp. 1219–1234, 2019. View at: Publisher Site  Google Scholar
 M. Khan, T. Shah, H. Mahmood, M. A. Gondal, and I. Hussain, “A novel technique for the construction of strong Sboxes based on chaotic Lorenz systems,” Nonlinear Dynamics, vol. 70, no. 3, pp. 2303–2311, 2012. View at: Publisher Site  Google Scholar
 M. Khan and T. Shah, “An efficient construction of substitution box with fractional chaotic system,” Signal, Image and Video Processing, vol. 9, no. 6, pp. 1335–1338, 2015. View at: Publisher Site  Google Scholar
 I. Hussain, T. Shah, H. Mahmood, and M. A. Gondal, “A projective general linear group based algorithm for the construction of substitution box for block ciphers,” Neural Computing and Applications, vol. 22, no. 6, pp. 1085–1093, 2013. View at: Publisher Site  Google Scholar
 Y. Tian and Z. Lu, “Novel permutationdiffusion image encryption algorithm with chaotic dynamic Sbox and DNA sequence operation,” AIP Advances, vol. 7, no. 8, Article ID 085008, 2017. View at: Publisher Site  Google Scholar
 M. Khan, F. Masood, A. Alghafis, M. Amin, and S. I. Batool Naqvi, “A novel image encryption technique using hybrid method of discrete dynamical chaotic maps and Brownian motion,” PLoS One, vol. 14, no. 12, Article ID e0225031, 2019. View at: Publisher Site  Google Scholar
 M. Khan and T. Shah, “A novel cryptosystem based on general linear group,” 3D Research, vol. 6, no. 1, 2015. View at: Publisher Site  Google Scholar
 D. Shah, T. Shah, and S. S. Jamal, “A novel efficient image encryption algorithm based on affine transformation combine with linear fractional transformation,” Multidimensional Systems and Signal Processing, vol. 31, no. 3, pp. 885–905, 2020. View at: Publisher Site  Google Scholar
 Y. Naseer, D. Shah, and T. Shah, “A novel approach to improve multimedia security utilizing 3D mixed chaotic map,” Microprocessors and Microsystems, vol. 65, pp. 1–6, 2019. View at: Publisher Site  Google Scholar
 K. E. A. Skipjack, “Algorithm,” Specifications Version, vol. 2, no. 29, pp. 1–23, 1998. View at: Google Scholar
 E. S. Abuelyman and A.A. Sultan Alsehibani, “An optimized implementation of the Sbox using residue of prime numbers,” International Journal of Computer Science and Network Security, vol. 8, no. 4, pp. 304–309, 2008. View at: Google Scholar
 S. Mahmood et al., “To study the effect of the generating polynomial on the quality of nonlinear components in block ciphers.,” Security and Communication Networks, vol. 2018, Article ID 5823230, 8 pages, 2018. View at: Publisher Site  Google Scholar
 M. Matsui, “Linear cryptanalysis method for DES cipher,” in Advances in Cryptology—Eurocrypt’93, pp. 386–397, Springer Berlin Heidelberg, Heidelberg, Germany, 1993. View at: Google Scholar
 Y. Wang, Q. Xie, Y. Wu, and B. Du, “A software for Sbox performance analysis and test,” in Proceedings of the 2009 International Conference on Electronic Commerce and Business Intelligence, pp. 125–128, IEEE, Beijing, China, June 2009. View at: Publisher Site  Google Scholar
 M. A. Gondal, A. Raheem, and I. Hussain, “A scheme for obtaining secure Sboxes based on chaotic Baker’s map,” 3D Research, vol. 5, no. 3, pp. 5–17, 2014. View at: Publisher Site  Google Scholar
 A. Belazi, R. Rhouma, and S. Belghith, “A novel approach to construct Sbox based on Rossler system,” in Proceedings of the 2015 International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 611–615, Dubrovnik, Croatia, August 2015. View at: Publisher Site  Google Scholar
 A. F. Webster and S. E. Tavares, “On the design of Sboxes,” in Advances in Cryptology—Crypto’85 Proceedings, pp. 523–534, Springer Berlin Heidelberg, Heidelberg, Germany, 1985. View at: Google Scholar
 F. Sattar and M. Mufti, “Spectral characterization and analysis of avalanche in cryptographic substitution boxes using walshhadamard transformations,” International Journal of Computer Applications, vol. 28, no. 6, 2011. View at: Publisher Site  Google Scholar
 J. Detombe and S. Tavares, “On the design of Sboxes,” Advances in Cryptology: Proceedings of CRYPTO_92, Springer Berlin Heidelberg, Heidelberg, Germany, 1992, Lecture Notes in Computer Science. View at: Google Scholar
 A. K. Farhan, R. S. Ali, H. Natiq, and N. M. G. AlSaidi, “A new Sbox generation algorithm based on multistability behavior of a plasma perturbation model,” IEEE Access, vol. 7, pp. 124914–124924, 2019. View at: Publisher Site  Google Scholar
 A. Farhan, R. Subhi, H. Rashed Yassein, and N. AlSaidi, “A new approach to generate multi Sboxes based on RNA computing,” International Journal of Innovative Computing, Information and Control: IJICIC, vol. 16, no. 1, pp. 331–348, 2020. View at: Google Scholar
 D. Shah and T. Shah, “Binary galois field extensions dependent multimedia data security scheme,” Microprocessors and Microsystems, vol. 77, Article ID 103181, 2020. View at: Publisher Site  Google Scholar
Copyright
Copyright © 2020 Sajjad Shaukat Jamal et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.