# To Study the Effect of the Generating Polynomial on the Quality of Nonlinear Components in Block Ciphers

Authors: Shahid Mahmood; Shabieh Farwa; Muhammad Rafiq; Syed Muhammad Jawwad Riaz; Tariq Shah; Sajjad Shaukat Jamal
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Substitution box (S-box), being the only nonlinear component, contributes to the confusion creating capability of a cryptosystem. Keeping in view the predominant role of S-box, many design algorithms to synthesize cryptographically stronger S-boxes have gained pivotal attention. A quick review of these algorithms shows that all these ideas mainly concentrate on the choice of bijective Boolean functions, with nonobservance to the irreducible polynomial that generates the Galois field. In this paper, we propose that the selection of irreducible polynomial has a deep influence on the highly desirable features of an S-box such as nonlinearity, strict avalanche, bit independence, linear approximation probability, and differential approximation probability. We underpin our claim by investigating a detailed model, which deploys the same algorithm but different polynomials and produces unusual changes in the results regarding the performance parameters of S-box.


---

## Body

## 1. Introduction

Electronic exchange of data has undoubtedly revolutionized the communication in recent years but, on the other hand, the secure transfer of confidential material over Internet has become the biggest challenge nowadays. It definitely demands seriously high level of security. The main problem is to avoid unauthorised access to the secret data. To achieve the desired level of security, many techniques such as cryptography, watermarking, and steganography have been the major focus of research for past few years [1–5]. In this paper, we deal with cryptography.Cryptography is categorized into two types,symmetric key cryptography andasymmetric key cryptography. The symmetric key cryptography can be further split into two types: block ciphers and the stream ciphers. Advanced Encryption Standard is an example of block cipher that was officially adopted by the US government as the Federal Information Processing Standard (FIPS) in May 2002. AES algorithm [6] is based on four steps: round key addition, byte substitution, shift row, and mix column, but the most influential of all these is the byte substitution step. This step relies on a substitution box (S-box), which serves as the only nonlinear component in anysubstitution-permutation network (SPN).It has been established that the substitution box (S-box) is a standout in different block ciphers and is a widely used mechanism in any substitution-permutation network as a source to produce nonlinearity [6]. It renders an absolutely complex, unforeseeable layout to requite various blocks of bits in output data. To extend high resistance against unexpected surveillance, S-box structure is required to fulfil certain standards. The indispensable involvement of S-box to induce complexity and nonlinearity motivates studying the properties and algorithms for safer and more reliable S-boxes. In this regard, many advanced structural developments are witnessed in literature. Khan et al. [7] proposed a technique for S-box construction based on chaotic Lorenz systems. Hussain et al. presented S-box algorithms using generalized Bakers map [8] and projective general linear group [9]. Algebraic, analytical, and chaotic approaches for S-box are studied in [10–13]. Özkaynak et al. [14] applied fractional-order chaotic Chen system, to develop S-box. Tian and Lu [15] structured dynamic chaos-based S-box in conjunction with DNA sequence operation. Some other more efficient algorithms could be reviewed in [6, 16–20]. In addition to this, applications of S-boxes in digital image encryption, steganography, and watermarking have become quite popular and influential in recent years [4, 11, 13, 21].The study of innovation in design algorithms forS-boxes witnesses that the change of model and the selection of Boolean function contribute little to the performance indices of an S-box. We, in this paper, propose that the performance of an S-box is highly related to the background Galois field. The fact that finite fields of the same order are isomorphic is definitely of worth but the scrambling effect of a nonlinear Boolean function applied on two different fields of the same order might vary. Since in cryptography, an S-box is the salient component used to produce confusion in the data, it is worth studying that the confusion creating ability is associated with the choice of the irreducible polynomial used to form the background Galois field.In [9], Hussain et al. presented an algorithm for generating S-box through the application of a linear fractional transformation on the Galois field GF(28), structured by the polynomial X8+X4+X3+X2+1. We in the proposed work show that the same algorithm used for a different polynomial exhibits highly improved values of nonlinearity, strict avalanche criterion (SAC), bit independent criterion (BIC), linear approximation probability (LAP), and differential approximation probability (DAP). By comparing the numerical results of these tests, we prove that different polynomials produce significantly different results. This observation leads to revising the existing models by choosing different background polynomials as it could be more influential in improvement of ideas rather changing the whole scheme.We organize the contents of this paper as follows. In Section2, we discuss the properties of the background Galois field GF(28). The detailed algorithm for the design of the S-box is presented in Section 3. Section 4 deals with the analyses of S-boxes against several common attacks and the comparison of respective results. We further compare the cryptographic standing of both of the newly synthesized S-boxes with the state-of-the-art AES S-box. Conclusion is presented in Section 5.


## 2. Generating Polynomial and the Galois Field

For any primep, Galois field GF(pn) is expressed as the factor ring Fp[X]/(μ(x)) where μ(x)∈Fp[X] is an irreducible polynomial of degree n. For GF(28) we choose an irreducible polynomial of degree 8 that generates the maximal ideal of the principal ideal domain F2[X]. We know that the multiplicative group of the resultant field GF(28) is cyclic and hence each nonzero element of the field can be expressed as a power of the generator α=00000010.In order to support our claim regarding the effect of polynomial, we choose two irreducible primitive polynomialsμ1 and μ2 of degree 8, to construct Galois fields F1 and F2, respectively, where μ1=X8+X6+X5+X4+1 and μ2=X8+X4+X3+X2+1, as used in [9]. We may choose other polynomials as well to compare our calculations but the selected pair beautifully serves for the purpose. Let Gi represents the multiplicative group of the Galois field, Fi. The exponential form of elements of the multiplicative group G1, along with their inverses, is represented in Table 1; however the elements of G2 are presented in Table 2 of [9]. In the next section, we use these calculations to develop the corresponding S-boxes.Table 1
Exponential representation and the multiplicative inverses of elements ofG1.
x ∈ G 1 α n x - 1 1 α 255 1 2 α 1 184 3 α 231 208 4 α 2 92 5 α 207 159 6 α 232 104 7 α 59 134 8 α 3 46 9 α 35 173 10 α 208 247 11 α 154 139 12 α 233 52 13 α 20 48 14 α 60 67 15 α 183 117 16 α 4 23 17 α 159 252 18 α 36 238 19 α 66 83 20 α 209 195 21 α 118 204 22 α 155 253 23 α 251 16 24 α 234 26 25 α 245 181 26 α 21 24 27 α 11 180 28 α 61 153 29 α 130 121 30 α 184 130 31 α 146 73 32 α 5 179 33 α 122 232 34 α 160 126 35 α 79 141 36 α 37 119 37 α 113 220 38 α 67 145 39 α 106 248 40 α 210 217 41 α 224 175 42 α 119 102 43 α 221 188 44 α 156 198 45 α 242 108 46 α 252 8 47 α 32 172 48 α 235 13 49 α 213 53 50 α 246 226 51 α 135 84 52 α22 12 53 α42 49 54 α12 90 55 α140 148 56 α62 244 57 α227 223 58 α131 132 59 α75 203 60 α185 65 61 α191 224 62 α147 156 63 α94 68 64 α6 225 65 α 70 60 66 α123 116 67 α195 14 68 α161 63 69 α53 157 70 α80 254 71 α167 143 72 α38 131 73 α109 31 74 α114 110 75 α203 154 76 α68 240 77 α51 150 78 α107 124 79 α49 186 80 α211 212 81 α40 196 82 α225 239 83 α189 19 84 α120 51 85 α111 227 86 α222 94 87 α240 193 88 α157 99 89 α116 163 90 α243 54 91 α128 149 92 α253 4 93 α205 158 94 α33 86 95 α18 192 96 α236 190 97 α163 235 98 α214 162 99 α98 88 100 α247 113 101 α55 123 102 α136 42 103 α102 189 104 α23 6 105 α82 135 106 α43 160 107 α177 169 108 α13 45 109 α169 199 110 α141 74 111 α89 155 112 α63 122 113 α8 100 114 α228 215 115 α 151 237 116 α132 66 117 α 72 15 118 α76 221 119 α218 36 120 α186 152 121 α125 29 122 α192 112 123 α200 101 124 α148 78 125 α197 187 126 α95 34 127 α174 140 128 α7 200 129 α150 171 130 α71 30 131 α217 72 132 α124 58 133 α199 202 134 α196 7 135 α173 105 136 α162 167 137 α97 176 138 α54 246 139 α101 11 140 α81 127 141 α176 35 142 α168 255 143 α88 71 144 α39 249 145 α188 38 146 α110 183 147 α239 243 148 α115 55 149 α127 91 150 α204 77 151 α17 241 152 α69 120 153 α194 28 154 α 52 75 155 α166 111 156 α108 62 157 α202 69 158 α 50 93 159 α 48 5 160 α212 106 161 α134 168 162 α 41 98 163 α139 89 164 α 226 207 165 α74 231 166 α 190 177 167 α 93 136 168 α 121 161 169 α 78 107 170 α 112 201 171 α 105 129 172 α 223 47 173 α 220 9 174 α 241 216 175 α 31 41 176 α 158 137 177 α 65 166 178 α 117 233 179 α 250 32 180 α 244 27 181 α 10 25 182 α 129 242 183 α 145 146 184 α 254 2 185 α 230 209 186 α 206 79 187 α 58 125 188 α 34 43 189 α 153 103 190 α 19 96 191 α 182 234 192 α 237 95 193 α 15 87 194 α 164 205 195 α 46 20 196 α 215 81 197 α 171 213 198 α 99 44 199 α 86 109 200 α 248 128 201 α 143 170 202 α 56 133 203 α 180 59 204 α 137 21 205 α91 194 206 α103 230 207 α29 164 208 α24 3 209 α25 185 210 α83 251 211 α26 228 212 α44 80 213 α84 197 214 α178 236 215 α27 114 216 α14 174 217 α45 40 218 α170 219 219 α85 218 220 α142 37 221 α179 118 222 α90 245 223 α28 57 224 α64 61 225 α249 64 226 α9 50 227 α144 85 228 α229 211 229 α57 250 230 α152 206 231 α181 165 232 α133 33 233 α138 178 234 α73 191 235 α92 97 236 α77 214 237 α104 115 238 α219 18 239 α30 82 240 α187 76 241 α238 151 242 α126 182 243 α16 147 244 α193 56 245 α165 222 246 α201 138 247 α47 10 248 α149 39 249 α216 144 250 α198 229 251 α172 210 252 α96 17 253 α100 22 254 α175 70 255 α87 142


## 3. Algorithm forS-Box

Ann×n  S-box is defined by avector Boolean functionSn:GF(2n)→GF(2n), defined as (1)Snv=s1v,s2v,…,snv,where v=(v1,v2,…,v2n)∈GF(2n) and each of si’s is regarded as a component Boolean function.For a fieldF, the general linear group GL(n,F) is a group formed by all n×n invertible matrices. A projective general linear group of degree n over a field F is defined to be the quotient group of GL(n,F) by its center. For this paper, we form the 8×8  S-box by considering the action of the Galois field GF(28) on the projective linear group PGL(2,GF(28)); that is, we take a function σ:PGL(2,GF(28))×GF(28)→GF(28) defined as follows:(2)σv=αv+βγv+δ.In (2), σ is known as a linear fractional transformation (LFT) with α,β,γ and δ∈GF(28) satisfying the nondegeneracy condition αδ-βγ≠0. The ease of implementation, lesser computational labour, and high algebraic complexity of an LFT are the prime features that give incentive to employ this map for byte substitution. We may choose any values for LFT parameters that satisfy the aforementioned condition but, for the presented calculations, we, in particular, choose the same values as in [9], so that a comparison could be set easily. We consider α=35,β=15,γ=9 and δ=5. The images of the map σ, when applied on F1 and F2, produce our S-boxes S1 and S2, respectively, as shown in Tables 2 and 3.Table 2
S-box S1.
3  214 37 74 126 4 18 26 219 62 45 226 50 136 104 148 154  38 200 199 185 228 170 245 177 114 137 231 139 35 8 134 158  27 223 232 17 157 217 49 83 141 171 42 47 206 64 194 106  29 30 110 14 40 72 236 105 221 202 87 241 41 11 71 186  28 253 175 67 31 23 33 66 189 117 118 94 149 135 252 235  43 124 125 90 229 204 215 218 100 101 249 243 54 173 166 138  234 244 201 167 44 250 25 16 187 207 246 107 103 161 1 183  99 179 240 129 123 188 193 20 143 155 174 7 220 213 239 108  84 113 184 5 57 208 153 75 112 223 178 180 150 65 24 224  248 102 89 70 111 59 172 95 131 198 163 93 164 55 209 86  132 6 225 51 79 53 34 97 48 197 142 182 210 91 247 195  15 10 144 85 63 168 238 196 162 98 32 251 254 203 156 80  152 237 24 127 78 165 12 52 222 122 58 211 36 140 191 216  146 109 96 147 73 116 190 128 68 56 77 115 160 19 92 69  2 192 121 145 21 76 61 60 181 133 151 159 0 88 205 13  230 22 82 39 119 9 255 120 46 81 212 227 130 176 169Table 3
S-box S2.
198 214 241 163 130 165 217 127 179 123 111 197 43 141 237 3 168 201 17 121 142 101 232 174 11 249 16 156 10 50 183 65 72 184 200 132 58 47 27 159 231 189 8 18 206 194 177 31 193 92 122 192 85 137 243 49 178 170 36 135 230 95 100 128 13 109 227 0 224 144 208 78 173 32 139 234 107 82 172 81 51 233 12 154 94 161 244 55 7 34 251 225 153 93 254 138 102 240 115 242 110 134 124 79 157 160 90 238 73 53 169 250 136 118 112 48 40 114 22 246 46 131 23 69 52 235 248 2 116 91 117 26 166 25 219 59 54 229 120 245 89 185 99 226 105 45 60 199 164 191 228 202 37 104 143 209 220 147 44 186 145 125 203 29 38 41 215 108 64 88 119 74 213 96 211 83 218 146 196 205 67 152 129 175 84 158 207 176 80 62 150 86 57 155 195 216 75 19 1 87 33 68 71 236 239 255 35 212 148 188 133 15 204 187 42 182 97 56 24 221 252 30 77 181 4 247 167 21 9 222 180 190 151 140 39 171 14 126 66 253 103 223 70 98 28 20 63 162 61 113 149 210 106 5 6 76


## 4. Performance Analysis ofS-Boxes

The cryptographic strength if theS-boxes, generated in the foregoing section, are examined through the most widely used analysis techniques such as nonlinearity, bit independence, strict avalanche, and linear and differential approximation probabilities. In the following subsections we present all these performance indices one by one and compare the performance of S1 and S2 with one another, as well as, with the ever-prevailing algorithm AES.


### 4.1. Nonlinearity

Nonlinearity analysis measures the distance of the reference function from all of the affine functions. Nonlinearity criterion outlines the total number of bits that must be altered in the truth table of a Boolean function to get close to the nearby affine function [22].Table4 shows that, for S1, the average nonlinearity measure is 112., which is the highest figure attained by the AES S-box. Figure 1 shows the comparison which clearly depicts outstanding performance of S1 as compared to S2.Table 4
Performance Indices for newS-box.
Analysis Max. Min. Average Square deviation DP LP Nonlinearity 113 111 112 SAC 0.546875 0.429688 0.498291 0.0157537 BIC  111 111.751 0.6227 DP     0.015625 LP      0.064063Figure 1
Nonlinearity of differentS-boxes.


### 4.2. Linear Approximation Probability

The measure of unevenness of an event is determined by linear approximation probability. This analysis is used to evaluate the maximum imbalance of the outcome. Mathematically, the linear approximation probability for a givenS-box is defined as follows: (3)LP=maxΓx,Γy≠0#x∣x·Γx=Sx·Γy2n-12, where X represents the set of all possible inputs and Γx and Γy are the input and output masks, respectively. Numerical results presented in Table 5 and compared in Figure 2 show that the linear approximation probability of S1 is much better than S2.Table 5
Comparison of performance indices for differentS-boxes.
S-box Nonlinearity SAC BIC DP LP AES 112 0.5058 112.0 0.0156 0.062 S 1 112 0.498291 111.751 0.015625 0.064063 S 2 105.5 0.507 106 0.0242 0.140Figure 2
LP of differentS-boxes.


### 4.3. Differential Approximation Probability

For further analysis, we use the differential approximation probability, which determines the differential uniformity demonstrated by anS-box. The mathematical expression for DP is given by the following: (4)DP=#x∈X∣Sx⊕Sx⊕Δx=Δy2n. In the above-mentioned expression input and output differentials are represented by Δx and Δy, respectively. The smaller the differential uniformity, the stronger the S-box. It is evident from Table 5 and Figure 3 that in terms of the differential approximation probability S1 is much stronger than S2.Figure 3
DP of differentS-boxes.


### 4.4. Strict Avalanche Criterion

This criterion examines the changes in the output bits caused as a result of single input bit change. This is one of the most desirable features of any cryptographic design that when we change a single input bit, changes must occur in half of the output bits. In other words anS-box, Sn:F2n→F2n is said to satisfy SAC if, for a change in an input bit, the probability of change in the output bit is 1/2. The results are shown in Table 5 and Figure 4.Figure 4
SAC of differentS-boxes.


### 4.5. Bit Independence Criterion

The independent behavior of the pair of variables and the variations of input bits are considered as important factors of bit independence criterion. In bit independence criterion, input bits are transformed exclusively, and then output results are scrutinized for their independency [23]. Bit independence has great worth in cryptographic structures. The goal of reaching the maximum complexity and perplexity in a system can be achieved through this property of increasing independence between the bits. In cryptographic systems, the increased independence between bits is an essential requirement as it makes harder to understand and forecast the design of the system.The numerical results of BIC when applied to the proposedS-box are given in Table 5 and are compared in Figure 5. It can be observed that according to these results our S-box S1 is pretty similar to the AES S-box and is much better than S2.Figure 5
BIC of differentS-boxes.One can observe that overall performance ofS1 is much better than that of S2. The performance parameters for S1 seem to be pretty close to that of AES S-box. The algorithm used for both S1 and S2 is the same but the primitive polynomial selected to generate the Galois field is different, which really contributes to the outputs.


## 4.1. Nonlinearity

Nonlinearity analysis measures the distance of the reference function from all of the affine functions. Nonlinearity criterion outlines the total number of bits that must be altered in the truth table of a Boolean function to get close to the nearby affine function [22].Table4 shows that, for S1, the average nonlinearity measure is 112., which is the highest figure attained by the AES S-box. Figure 1 shows the comparison which clearly depicts outstanding performance of S1 as compared to S2.Table 4
Performance Indices for newS-box.
Analysis Max. Min. Average Square deviation DP LP Nonlinearity 113 111 112 SAC 0.546875 0.429688 0.498291 0.0157537 BIC  111 111.751 0.6227 DP     0.015625 LP      0.064063Figure 1
Nonlinearity of differentS-boxes.


## 4.2. Linear Approximation Probability

The measure of unevenness of an event is determined by linear approximation probability. This analysis is used to evaluate the maximum imbalance of the outcome. Mathematically, the linear approximation probability for a givenS-box is defined as follows: (3)LP=maxΓx,Γy≠0#x∣x·Γx=Sx·Γy2n-12, where X represents the set of all possible inputs and Γx and Γy are the input and output masks, respectively. Numerical results presented in Table 5 and compared in Figure 2 show that the linear approximation probability of S1 is much better than S2.Table 5
Comparison of performance indices for differentS-boxes.
S-box Nonlinearity SAC BIC DP LP AES 112 0.5058 112.0 0.0156 0.062 S 1 112 0.498291 111.751 0.015625 0.064063 S 2 105.5 0.507 106 0.0242 0.140Figure 2
LP of differentS-boxes.


## 4.3. Differential Approximation Probability

For further analysis, we use the differential approximation probability, which determines the differential uniformity demonstrated by anS-box. The mathematical expression for DP is given by the following: (4)DP=#x∈X∣Sx⊕Sx⊕Δx=Δy2n. In the above-mentioned expression input and output differentials are represented by Δx and Δy, respectively. The smaller the differential uniformity, the stronger the S-box. It is evident from Table 5 and Figure 3 that in terms of the differential approximation probability S1 is much stronger than S2.Figure 3
DP of differentS-boxes.


## 4.4. Strict Avalanche Criterion

This criterion examines the changes in the output bits caused as a result of single input bit change. This is one of the most desirable features of any cryptographic design that when we change a single input bit, changes must occur in half of the output bits. In other words anS-box, Sn:F2n→F2n is said to satisfy SAC if, for a change in an input bit, the probability of change in the output bit is 1/2. The results are shown in Table 5 and Figure 4.Figure 4
SAC of differentS-boxes.


## 4.5. Bit Independence Criterion

The independent behavior of the pair of variables and the variations of input bits are considered as important factors of bit independence criterion. In bit independence criterion, input bits are transformed exclusively, and then output results are scrutinized for their independency [23]. Bit independence has great worth in cryptographic structures. The goal of reaching the maximum complexity and perplexity in a system can be achieved through this property of increasing independence between the bits. In cryptographic systems, the increased independence between bits is an essential requirement as it makes harder to understand and forecast the design of the system.The numerical results of BIC when applied to the proposedS-box are given in Table 5 and are compared in Figure 5. It can be observed that according to these results our S-box S1 is pretty similar to the AES S-box and is much better than S2.Figure 5
BIC of differentS-boxes.One can observe that overall performance ofS1 is much better than that of S2. The performance parameters for S1 seem to be pretty close to that of AES S-box. The algorithm used for both S1 and S2 is the same but the primitive polynomial selected to generate the Galois field is different, which really contributes to the outputs.


## 5. Conclusion

The kernel of the presented work lies in the fact that the choice of the background Galois field and its generating primitive polynomial matters to the function and performance of the substitution boxes. This fact leads to the fascinating idea that, rather than the development of new algorithms, the improvement of the existing algorithms is worth studying as its least laborious but most effective. We propose, on the basis of the example discussed, that the effect of the choice of generating polynomial may lead to an intensive research in future to modify the design models ofS-boxes. It will definitely affect the applications of S-boxes in other branches of the digital communication, such as steganography, watermarking, and image encryption.



---

*Source: 5823230-2018-04-10.xml*