Next Article in Journal
Automating Privacy Compliance Using Policy Integrated Blockchain
Previous Article in Journal
Acknowledgement to Reviewers of Cryptography in 2018
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Novel Algorithm of Constructing Highly Nonlinear S-p-boxes

Department of Mathematics, Quaid-i-Azam University, Islamabad 44000, Pakistan
*
Author to whom correspondence should be addressed.
Submission received: 16 December 2018 / Revised: 3 January 2019 / Accepted: 9 January 2019 / Published: 16 January 2019
(This article belongs to the Section Hardware Security)

Abstract

:
The role of substitution boxes is very important in block ciphers. Substitution boxes are utilized to create confusion in the cryptosystem. However, to create both confusion and diffusion in any cryptosystem p-boxes and chaos base substitution boxes are designed. In this work, a simple method is presented that serves both ways. This method is based on composition of the action of symmetric group on Galois field and inversion map. This construction method provides a large number of highly non-linear substitution permutation boxes having the property of confusion as well as diffusion. These substitution permutation boxes have all the cryptography properties. Their utilization in the image encryption application is measured by majority logic criterion. We named these newly designed substitution boxes (S-boxes) as substitution permutation boxes (S-p-boxes), because they serve as both substitution boxes (S-boxes) as well as permutation boxes (p-boxes).

1. Introduction

Cryptography techniques have been utilized in different areas. In this era, due to progress in computer and communication technology have facilitated mankind to transfer important personal data through the long-distance channels. The concerns that are related to secrecy of transfer data is a big problem. Cryptology provides the solution of all such requirements in modern day communication systems. The symmetric (private) and asymmetric (public) key cryptography are two most trusted cryptographic models for secure communication. Both methodologies have several benefits and drawbacks as well.
Symmetric key cryptography algorithms have two types. These types are block ciphers and stream ciphers. The concept of block cipher was introduced by C. Shannon. Block ciphers, like DES, advanced encryption standard (AES), and international data encryption algorithm (IDEA), play an important role in multimedia security. The substitution box and permutation box are the two most indispensable parts of a secure block cipher. The role of substitution box is to make the relationship between the secret key and the ciphertext as complex as possible. Permutation box induces diffusion in the system.

2. Related Work

In literature, different researchers worked in this aspect. The construction of AES [1] is based on the composition of inversion map and affine transformation. In 2007 Cui and Cao presented the APA S-box [2]. In the construction of affine-power-affine S-box, the composition of affine surjection, power function, and again affine surjection are used. This model of S-box improves algebraic complexity as compared to AES. In 2008 Minh-Triet Tran, Doan-Khanh Bui and Anh-Duc Duong proposed Gray S-box [3]. It was obtained that AES includes an additional transformation based on the binary gray code. This S-box has similar properties to AES. In addition, it is more secure against algebraic and interpolation attacks in comparison to AES. In 2009, Kim and Phan suggest Skipjack S-box [4]. This S-box is a Feistel network that is based on 32 rounds. This scheme uses the 80-bit key for encryption or decrypts 64-bit blocks. Later, Iqtadar et al. in [5] proposed chaos based S-boxes. Also, in [6,7,8,9,10,11,12,13,14] different S-boxes are constructed utilizing different algebraic structures and chaotic maps. These S-boxes have strong algebraic analysis but weak statistical analysis [13]. In [14] Iqtadar et use permutations of S 8 on Liu S-box to attain 40,320 S-boxes, but there are p- boxes that were obtained from S-boxes and a different author using group action on Galois field by linear fractional transformation.
A substitution box is a mapping S : 2 r 2 t . This mapping map r input bits to t output bits. Substitution box is signified in matrix from a rectangular and square matrix. Substitution box of dimension r × t with r = t has two categories. In first category, every input has a distinctive output. Second category involves those substitution boxes where several inputs may have the same output and all possible output are not existing in S-box. An S-box of dimension r × t , which is one-to-one and onto is said to be bijective S-box. This S-box maps each input to a distinct output and all possible outputs are included in the S-box. The existence of bijective S-boxes may imply that r = t and these S-boxes are also renowned as reversible S-boxes. Reversible S-boxes are very significant in symmetric key cryptosystems.
Most of the work that is related to S-boxes is based on affine transformations and linear fractional transformations [14,15,16,17,18,19,20,21,22,23,24,25,26]. In both cases, we have some constraints on coefficients of affine transformations and linear fractional transformations. Also, for diffusing property chaotic maps [27], permutations on S-box entries and binary gray code are used. The motivations behind the present work are to obtain a scheme free of constraints, to generate large number of highly nonlinear S-boxes and the S-boxes having the diffusing property as well. This work is unique in the aspect of constructing a large number of highly non-linear substitution permutation boxes (S-p-boxes).

3. Preliminaries

Group is a non-empty set with an associative binary operation having the properties of unique identity and each member of the set has unique inverse. For instance, a set of rational number Q / { 0 } under multiplication is a group.
Symmetric Group S n is also an example of group. It is the group of all possible permutations on a set of n members with the binary operation of composition of functions.
A polynomial h ( y ) R [ Y ] is said to be irreducible over a unitary commutative ring R if it is non-unit in R [ Y ] and if we write it as h ( y ) = n ( y ) · m ( y ) , then one of n ( y ) , m ( y ) is unit in R [ Y ] .
Galois field G F ( q r ) is a field that has order q r , where q is prime and r is a positive integer. Suppose that h ( y ) be the r degree polynomial, which is primitive irreducible over the prime field q , where q is prime. For primitive root ς of the polynomial h ( y ) , we define Galois field, as follows
G F ( q r ) = q [ y ] h ( y ) = { b 0 + b 1 ς + b 2 ς 2 + + b r 1 ς r 1 : b j q , j = 0 , 1 , 2 , , r 1 }
For instance, q = 2   a n d   r = 3 , we have following Galois field.
G F ( 2 3 ) = 2 [ y ] h ( y ) = { b 0 + b 1 ς + b 2 ς 2 : b j 2 , j = 0 , 1 , 2 }
here h ( y ) = 1 + y + y 3 , G F ( 2 3 ) has eight elements.
Let ς be the primitive irreducible root of h ( y )
h ( ς ) = 0   i m p l i e s   t h a t   1 + ς + ς 3 = 0   i m p l i e s   t h a t   ς 3 = ς 1
here, the coefficient belongs to 2 and −1 in 2 is equal to 1.
ς 3 = 1 + ς ,   ς 4 = ς + ς 2 ,   ς 5 = 1 + ς + ς 2 ,   ς 6 = 1 + ς 2 ,   ς 7 = 1
Similarly, G F ( 2 8 ) is constructed and we computed it computationally.
G F ( 2 8 ) = 2 [ y ] h ( y ) = { b 0 + b 1 y + b 2 y 2 + + b 7 y 7 : b i 2 , i = 0 , 1 , 2 , , 7 }
where h ( y ) = 1 + y 2 + y 3 + y 4 + y 8 is a primitive irreducible polynomial.

4. Design for Proposed S-p-Boxes

The design of the suggested S-p-box is dependent on the composition of action of symmetric group S 8 on to Galois field G F ( 2 8 ) and inversion map. The action of S 8 on G F ( 2 8 ) is defined as:
η : S 8 × G F ( 2 8 ) G F ( 2 8 )
1 :   η ( σ e , d ( z ) ) = ( d ( z ) ) σ e = d ( z ) : w h e r e   σ e S 8 ,   d ( z ) G F ( 2 8 )
2 :   η ( σ , η ( ρ , d ( z ) ) ) = η ( σ ρ , d ( z ) ) = ( d ( z ) ) σ ρ
The construction of S-p-boxes has four steps:
Step 1: Construct Galois field G F ( 2 8 )
Step 2: Define action of the symmetric group η : S 8 × G F ( 2 8 ) G F ( 2 8 ) , defined by
η ( σ , d ( z ) ) = ( d ( z ) ) σ ,   w h e r e   σ S 8   a n d   d ( z )   G F ( 2 8 )
here, a fixed σ S 8 is utilized in the design of a single S-p-box. This phase of design will kill the structure of Galois field and induced diffusion.
Step 3: Define inversion map ξ : G F ( 2 8 ) G F ( 2 8 ) by
ξ ( d ( z ) ) = ( d ( z ) ) 1 ,   w h e r e   d ( z ) G F ( 2 8 )
Step 4: Define composition map τ : G F ( 2 8 ) G F ( 2 8 ) by
ξ ( η ( σ i , d ( z ) ) ) = w ( z ) ,   τ = ξ η
This composition gives us the desired S-p-box. We pick a specific permutation, and using this permutation, we permute according to the defined action in the Galois field (in Table 1) in step 2. In the third step, each member of Galois field is mapped to its inverse. Following the same procedure, we get 40,320 highly nonlinear S-p-boxes. The method is explained below by a simple example by constructing a small S-box and with the similar method, an S-box of dimension 16 × 16 is constructed. The computational scheme is presented in Figure 1. It notable that, in this construction, zero is always mapped on zero and the remaining numbers are mapped on a different number according to the permutations.
In Table 1, Galois field G F ( 2 3 ) is constructed. We choose S 3 = { I , ( 01 ) ,   ( 02 ) ,   ( 12 ) ,   ( 012 ) ,   ( 021 ) } to explain the procedure by a small example. We select σ = ( 012 ) .
In step 1, as G F ( 2 3 ) is constructed in Table 1.
In step 2 (Table 2), η : S 3 × G F ( 2 3 ) G F ( 2 3 )
In step 3 (Table 3), the resulting form which is again a G F ( 2 3 ) is mapped on there inverses.
Hence, the S-box obtained is of dimension 2 × 4
0734
5126
The S-p-box presented in Table 4 is designed using a permutation σ = ( 1467253 ) . Similarly, for each permutation of S 8 , we can get an S-p-box. These S-p-boxes depend on permutation. For each permutation of S 8 , we have a new S-p-box that is different from other S-p-boxes. Accordingly, permutation can be used as a key for the unique S-p-boxes. The inverse S-p-box is obtained by using reverse procedure.

5. Algebraic Analysis and Simulation Results

In order to judge the utility of proposed S-box for any cryptosystem, we generally used standard algebraic analysis. This analysis includes bit independence criterion, nonlinearity, strict avalanche criterion, and differential and linear approximation probability. The comparison of proposed S-p-box is also made with some classical S-boxes and presently constructed S-boxes. The proposed S-p-box fulfills all of the optimal values of standard algebraic analysis. Detail of these analyses is discussed below.

5.1. Nonlinearity

Nonlinearity measures the minimum distance between the set of all n-variable affine functions and an n-variable Boolean function ( x ) . Mathematically, it is defined as
N L ( g ) = 0.5 ( 2 n W H T m a x )
where W H T m a x is the maximum absolute value in the Walsh-Hadamard transform vector.
Non-linearity of newly suggested S-p-box is 112 and a comparison is made with some classic as well, as recently constructed S-boxes is shown in Table 5. The graphical representation is shown in Figure 2. Here, it is noteworthy that, following the similar method, 40,320 highly non-linear S-p-boxes are obtained. The non-linearity of proposed S-p-box has a superior value than Ref. [8], Ref. [10], and Ref. [12], and it has equal value to AES, Ref. [6], and Gray.

5.2. Strict Avalanche Criterion

A Boolean function g ( x ) such that for every t satisfies the expression
H W ( t ) = 1 x g ( x ) g ( x t ) = 2 n 1
Known as strict avalanche criterion. In other words, strict avalanche criterion (SAC) measures how much the output bits altered when a single change in input bits is made.
An S-box fulfills SAC criterion if an alteration in one bit in the input bit can cause an avalanche change in the output bits that is nearly half of the output bits must be altered. The comparison of overall SAC analysis of proposed S-p-box with AES and Gray is shown in Table 6, Table 7 and Table 8, while the average outcomes are shown in Table 9 and graphical representation of analysis comparison is described in Figure 3. It can be observed from Table 9 that the proposed S-p-box has attained a maximum value = 0.526, minimum value = 0.437, average value = 0.487, and square deviation = 0.015. These outcomes are better than the Gray S-box.

5.3. Bit Independence Criterion

Bit independence criterion (BIC) investigated those input bits that continue unaltered. The modification of unaltered input bits and the avalanche vectors’ independent performance of pairwise variables are the assets of this criterion. In the symmetric cryptosystem, BIC is an effective property as, by increasing independence between bits, it is almost impossible to predict and recognize the pattern of the system [11].
The outcomes of nonlinearity are presented in Table 10. The bits, which are generated by eight constituent functions, are compared with each other for the purpose to measure the independence characteristics. The correlation due to the alteration in input bit and the corresponding alteration in output bits is calculated. Initially, j t h and k t h bits are kept fixed and t h e   i t h bit is changed from 1 to n after that j and k are altered.
BIC analysis performed on different S-boxes and their comparison with the proposed S-box is shown in Table 11. It can be observed that BIC analysis of proposed S-box has a minimum value = 112, average value = 112, and square deviation = 0. These outcomes are comparatively excellent when compared to Ref. [8] and Ref. [10]. Graphical representations of outcomes are presented in Figure 4.

5.4. Linear Approximation Probability

Linear approximation probability measures the imbalance of the incident. This analysis is convenient in enumerating the supreme value of the discrepancy of an event between input and output. The two masks, Γ x and Γ y , are applied to the parity of the input bits and output bits, respectively.
L P = [ # { x : x Γ x = S ( x ) Γ y } 2 n 0.5 ] Γ x , Γ y 0 m a x
where x is all possible inputs and 2 n is a number of the input element.
In Table 12, linear probability (LP) analysis is presented and a comparison with selected S-boxes is also shown. The maximum value of linear approximation of the proposed S-box is 144, which demonstrates that the proposed S-p-box has strong resisting ability against linear attacks. In Figure 5, a graphical representation of the suggested S-p-box with some selected S-boxes is presented. LP analysis of the proposed S-p-box is better than Ref. [8], Ref. [10], and Skipjack, while its Max LP is the same as AES, Gray, and Ref. [6].

5.5. Differential Approximation Probability

Differential approximation probability guaranteed uniform mapping. For every change in the input, there must be a unique change in output. These features of differential approximation probability guarantee uniform mapping probability for every input bit i.
D P ( x y ) = [ # { x X : S ( x ) S ( x x ) = y } 2 m ]
where x is the input differential and y is the output differential.
The proposed S-p-box has maximum differential probability is 0.015625, which is comparable to the S-boxes that are present in Table 13. These S-boxes include Ref. [6], Ref. [8], Ref. [10], AES, Gray, and skipjack. The performance of proposed S-p-box is better than Ref. [8], Ref. [10], and skipjack. Figure 6 represents the graphical representation of differential approximation probability analysis.

6. Statistical Analysis

Statistical analyses are judged through majority logic criteria (MLC). MLC decides the suitability of an S-box for the encryption procedure of a specific type of data. In this criterion, a test image is encrypted using S-box by substituting the pixel values. This process is just testing of S-box suitability in the encryption process. This is not itself an encryption scheme. In this criterion, statistical analysis is applied on the original data and encrypted data. It measures the statistical properties. During the procedure of encryption, data is used and during this utilization of data produces alterations in the original data. The outcomes of several statistical analyses, which include contrast analysis, entropy analysis, energy analysis, correlation analysis, mean of absolute deviation analysis, and homogeneity analysis, which defines the appropriateness of S-box in encryption applications. This criterion is a decider, its analysis described whether the S-box is suitable for encryption applications or not [13].
Figure 7 shows that the image encryption sample image of Lena by using the proposed S-p-box and their corresponding histogram, respectively. The outcomes of statistical analysis of proposed S-p-box and a comparison with AES, Ref. [6], Ref. [10] and Gray are shown in Table 14. In Table 14, AES and Ref. [6] are the most suitable for encryption and the proposed S-p-box has a better outcome than both, according to the majority logic criterion. The MLC analysis of proposed S-p-box showed that this S-p-box is more diffusing and better for any cryptosystem as compared to the best S-boxes in the literature. The proposed S-p-box is confusing as well as diffusing, which differentiate it from all other S-boxes constructed so far in literature. The majority logic criterion suggests that the proposed S-p-box has excellent image encryption properties.

7. Conclusions

A simple and innovative method is suggested for the construction of S-p-boxes in an unconstraint system as compared to linear fractional and affine transformation. The proposed S-p-box has an additional property of diffusion as well. S-p-box is constructed using the composition of the action of symmetric group S 8 on Galois field G F ( 2 8 ) and inversion map. Due to this scheme, 8! highly nonlinear S-p-boxes are obtained. To judge the strength and efficiency of S-p-box, we apply nonlinearity analysis, strict avalanche analysis, bit independence analysis, and linear and differential approximation probability analysis. Suitability of S-p-box in image encryption application is measured by MLC analysis and its diffusing capability proves its superiority in image encryption application. It is further summarized that the suggested scheme of the proposed S-p-box has all the desired cryptographic properties and it is useable in any cryptosystem.

Author Contributions

Conceptualization, S.H.; Methodology, Y.N.; Software, D.S.; Supervision, T.S.

Funding

This research received no external funding.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Daemen, J.; Rijmen, V. The Design of Rijndael-AES: The Advanced Encryption Standard; Springer: Berlin, Germany, 2002. [Google Scholar]
  2. Cui, L.; Cao, Y. A new S-box structure named Affine Power-Affine. Int. J. Innov. Comput. Inf. Control 2007, 3, 45–53. [Google Scholar]
  3. Tran, M.T.; Bui, D.K.; Doung, A.D. Gray S-box for advanced encryption standard. In Proceedings of the 2008 International Conference on Computational Intelligence and Security, Suzhou, China, 13–17 December 2008; pp. 253–256. [Google Scholar]
  4. Kim, J.; Phan, W.R. Advanced differential-style cryptanalysis of the NSA’s Skipjack block cipher. Cryptologia 2009, 33, 246–270. [Google Scholar] [CrossRef]
  5. Hussain, I.; Shah, T.; Mahmood, H. A new algorithm to construct secure keys for AES. Int. J. Contemp. Math. Sci. 2010, 5, 1263–1270. [Google Scholar]
  6. Farwa, S.; Shah, T.; Idrees, L. A Highly Non-Linear S-Box Based on A Fractional Linear Transformation. Springerplus 2016, 5, 1658. [Google Scholar] [CrossRef] [PubMed]
  7. Altaleb, A.; Saeed, M.S.; Hussain, I.; Aslam, M. An algorithm for the construction of substitution box for block ciphers based on a projective general linear group. AIP Adv. 2017, 7, 035001. [Google Scholar] [CrossRef]
  8. Ozkaynak, F. Construction of robust substitution boxes based on chaotic systems. Neural Comput. Appl. 2017. [Google Scholar] [CrossRef]
  9. Shi, X.; Xiao, X.Y.H.; Lam, K. A method for obtaining cryptographically strong 8 × 8 S-boxes. Int. Conf. Inf. Netw. Appl. 2002, 2, 14–20. [Google Scholar]
  10. Razaq, A.; Yousaf, A.; Shuaib, U.; Siddique, N.; Ullah, A.; Waheed, A. A novel construction of substitution box coset diagram and a bijective map. Hindawi Secur. Commun. Netw. 2017, 2017, 5101934. [Google Scholar] [CrossRef]
  11. Webster, A.F.; Tavares, S.E. On the design of S-boxes. In Advances in Cryptology—CRYPTO ’85 Proceedings; Lecture Notes in Computer Science; Springer: Berlin, Germany, 1986; Volume 218, pp. 523–534. [Google Scholar]
  12. Alkhaldi, A.H.; Hussain, I.; Gondal, M.A. A novel design for the construction of safe S-boxes based on TDERC sequence. Alex. Eng. J. 2015, 54, 65–69. [Google Scholar] [CrossRef] [Green Version]
  13. Shah, T.; Hussain, I.; Gondal, M.A.; Mahmood, H. Statistical analysis of S-box in image encryption applications based on majority logic criterion. Int. J. Phys. Sci. 2011, 6, 4110–4127. [Google Scholar]
  14. Hussain, I.; Shah, T.; Gondal, M.A.; Mahmood, H. Construction of S8 Liu J S-boxes and their applications. J. Comput. Math. Appl. 2012, 64, 2450–2458. [Google Scholar] [CrossRef]
  15. Shah, T.; Shah, D. Construction of highly nonlinear S-boxes for degree 8 primitive irreducible polynomials over ℤ2. Multimed. Tools Appl. 2018, 1–16. [Google Scholar] [CrossRef]
  16. Naseer, Y.; Shah, D.; Shah, T. A Novel Approach to improve multimedia security utilizing 3D Mixed Chaotic map. Microprocess. Microsyst. 2019, 65, 1–6. [Google Scholar] [CrossRef]
  17. Preneel, B.; Dodunekov, S.; Rijmen, V.; Nikova, S. Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes; IOS Press: Amsterdam, The Netherlands, 2009. [Google Scholar]
  18. Alvarez, R.; Zamora, A. Randomness analysis and generation of key-derived s-boxes. Log. J. IGPL 2016, 24, 68–79. [Google Scholar] [CrossRef]
  19. Youssef, A.M.; Tavares, S.E. Resistance of balanced s-boxes to linear and differential cryptanalysis. Inf. Process. Lett. 1995, 56, 249–252. [Google Scholar] [CrossRef] [Green Version]
  20. Ferguson, N.; Lucks, S.; Schneier, B.; Whiting, D.; Bellare, M.; Kohno, T.; Callas, J.; Walker, J. The Skein Hash Function Family, Version 1.3. 1 October 2010. Available online: http://www.skein-hash.info/sites/default/files/skein1.3.pdf (accessed on 3 January 2019).
  21. Zhang, Y. The unified image encryption algorithm based on chaos and cubic S-Box. Inf. Sci. 2018, 450, 361–377. [Google Scholar] [CrossRef]
  22. Zhu, C.; Wang, G.; Sun, K. Cryptanalysis and Improvement on an Image Encryption Algorithm Design Using a Novel Chaos Based S-Box. Symmetry 2018, 10, 399. [Google Scholar] [CrossRef]
  23. Khan, M.A.; Ali, A.; Jeoti, V.; Manzoor, S. A Chaos-Based Substitution Box (S-Box) Design with Improved Differential Approximation Probability (DP). Iran. J. Sci. Technol. Trans. Electr. Eng. 2018, 42, 219–238. [Google Scholar] [CrossRef]
  24. Zhu, C.; Wang, G.; Sun, K. Improved Cryptanalysis and Enhancements of an Image Encryption Scheme Using Combined 1D Chaotic Maps. Entropy 2018, 20, 843. [Google Scholar] [CrossRef]
  25. Liu, H.; Kadir, A.; Sun, X.; Li, Y. Chaos based adaptive double-image encryption scheme using hash function and S-boxes. Multimed. Tools Appl. 2017. [Google Scholar] [CrossRef]
  26. Islam, F.U.; Liu, G. Designing S-Box Based on 4D-4Wing Hyperchaotic System. 3D Res. 2017, 8, 9. [Google Scholar] [CrossRef]
  27. Zhu, S.; Zhu, C.; Wang, W. A New Image Encryption Algorithm Based on Chaos and Secure Hash SHA-256. Entropy 2018, 20, 716. [Google Scholar] [CrossRef]
Figure 1. Diagram of proposed S-p-box.
Figure 1. Diagram of proposed S-p-box.
Cryptography 03 00006 g001
Figure 2. Graphical Representation of Nonlinearities.
Figure 2. Graphical Representation of Nonlinearities.
Cryptography 03 00006 g002
Figure 3. Graphical Representation of SAC.
Figure 3. Graphical Representation of SAC.
Cryptography 03 00006 g003
Figure 4. Graphical Representation of BIC.
Figure 4. Graphical Representation of BIC.
Cryptography 03 00006 g004
Figure 5. Graphical Representation of LP.
Figure 5. Graphical Representation of LP.
Cryptography 03 00006 g005
Figure 6. Graphical Representation of DP.
Figure 6. Graphical Representation of DP.
Cryptography 03 00006 g006
Figure 7. The original image, encrypted images, and their histograms.
Figure 7. The original image, encrypted images, and their histograms.
Cryptography 03 00006 g007aCryptography 03 00006 g007b
Table 1. G F ( 2 3 ) generated by 1 + y + y3.
Table 1. G F ( 2 3 ) generated by 1 + y + y3.
Power FormBinary FormPolynomial FormPower FormBinary FormPolynomial
0 000 0 ς 3 110 1 + ς
ς 7 100 1 ς 4 011 ς + ς 2
ς 010 ς ς 5 111 1 + ς + ς 2
ς 2 001 ς 2 ς 6 101 1 + ς 2
Table 2. Explanation of step 2.
Table 2. Explanation of step 2.
Polynomial Form η ( ( 012 ) , d ( z ) ) = ( d ( z ) ) ( 012 ) Resulting Polynomial Form
0 0 ( 012 ) 0
1 ( z 0 ) ( 012 ) z
z ( z ) ( 012 ) z 2
z 2 ( z 2 ) ( 012 ) z 0 = 1
1 + z ( z 0 + z 1 ) ( 012 ) z + z 2
z + z 2 ( z 1 + z 2 ) ( 012 ) 1 + z 2
1 + z + z 2 ( z 0 + z 1 + z 2 ) ( 012 ) 1 + z + z 2
1 + z 2 ( z 0 + z 2 ) ( 012 ) 1 + z
Table 3. Explanation of step 3.
Table 3. Explanation of step 3.
Resulting Polynomial Form ( d ( z ) ) 1
0 0
z 1 + z 2
z 2 1 + z + z 2
z 0 = 1 1
z + z 2 1 + z
1 + z 2 z
1 + z + z 2 z 2
1 + z z + z 2
Table 4. Proposed S-p-box.
Table 4. Proposed S-p-box.
012161141082377213714224419288578111146
549556353687402092482131041402029117217
1731571442221122088034221152851283174207169
4813619193821412191194330203992391796187
27842422328130135229161296879159198238107
188941113206322723116553200246230240181234
73491122020659197100394518914813607123
21024716115250116662129890118120243180232117
7116722462968616419512218676102441386494
1467812926185196233251166437972377218121
6117016013138139171129315075425111021225
2210315114322361322056914755654750254252
124204155188521942352422281761592705191175
101184249671341773143163158215214226241211201
83105172915681491542245199162190183174182
13312515310109331272551685825145178106126253
Table 5. Outcomes of nonlinearity analysis of constituent functions of different S-boxes.
Table 5. Outcomes of nonlinearity analysis of constituent functions of different S-boxes.
S-Boxes g 0 g 1 g 2 g 3 g 4 g 5 g 6 g 7 Average
Proposed 112 112 112 112 112 112 112 112 112
Gray 112 112 112 112 112 112112 112 112
Ref. [6] 112 112 112 112 112 112 112 112 112
AES 112 112 112 112 112 112 112 112 112
Ref. [10] 108 106 108 108 108 104 106 106 106.75
Ref. [8] 106 106 106 104 108 102 106 104 105.25
Ref. [12] 108 104 106 106 102 98 104 108 104
Table 6. SAC Analysis of Proposed S-p-box.
Table 6. SAC Analysis of Proposed S-p-box.
g 0 g 1 g 2 g 3 g 4 g 5 g 6 g 7
Bit 0128116120124136112116116
Bit 1128116116124128116124128
Bit 2116132120140116124128128
Bit 3116124144144112116116128
Bit 4132124136140124128128116
Bit 5128128132124116128116124
Bit 6124136124136128128116132
Bit 7124128120132116116128116
Table 7. SAC Analysis of AES S-box.
Table 7. SAC Analysis of AES S-box.
g 0 g 1 g 2 g 3 g 4 g 5 g 6 g 7
Bit 0132132116144116124116128
Bit 1120124144128124116128136
Bit 2132132128120144128136128
Bit 3136136120116128136128140
Bit 4116128116132128128140136
Bit 5116132132120120140136136
Bit 6136136120132120136136124
Bit 7128140136132144120132120
Table 8. SAC Analysis of Gray S-box.
Table 8. SAC Analysis of Gray S-box.
g 0 g 1 g 2 g 3 g 4 g 5 g 6 g 7
Bit 0132132116144116124116128
Bit 1120128136120132120136136
Bit 2136120120128140136136112
Bit 3132136128124132136112132
Bit 4120132124124116112132132
Bit 5120128124120140132132120
Bit 6120136120136136132120132
Bit 7128140136132144120132120
Table 9. Average outcomes of SAC.
Table 9. Average outcomes of SAC.
S-BoxesProposedGrayRef. [6]AESPrime
Minimum Value0.4370.4210.4530.4530.343
Maximum value0.5260.5250.5250.5260.671
Average0.4870.4760.5100.5040.516
Square Deviation0.0150.0150.01650.01560.032
Table 10. Non-linearity of bit independence criterion (BIC) of Proposed S-p-box.
Table 10. Non-linearity of bit independence criterion (BIC) of Proposed S-p-box.
-112.000112.000112.000112.000112.000112.000112.000
112.000-112.000112.000112.000112.000112.000112.000
112.000112.000-112.000112.000112.000112.000112.000
112.000112.000112.000-112.000112.000112.000112.000
112.000112.000112.000112.000-112.000112.000112.000
112.000112.000112.000112.000112.000-112.000112.000
112.000112.000112.000112.000112.000112.000-112.000
112.000112.000112.000112.000112.000112.000112.000-
Table 11. BIC analysis of Proposed S-p-box.
Table 11. BIC analysis of Proposed S-p-box.
S-BoxesAverageMinimum ValueSquare Deviation
Proposed1121120
AES1121120
Gray1121120
Ref. [6]1121120
Ref. [8]103.2943.53
Ref. [10]103.643962.7283
Table 12. Linear approximation analysis of the Proposed S-p-box.
Table 12. Linear approximation analysis of the Proposed S-p-box.
S-BoxesProposedGrayRef. [6]AESRef. [10]Ref. [8]Skipjack
Max Value144144144144162164156
Max LP0.06250.06250.06250.06250.14840.1590.109
Table 13. Comparison of Differential approximation probability of different S-boxes.
Table 13. Comparison of Differential approximation probability of different S-boxes.
S-BoxesProposedGrayRef. [6]AESRef. [10]Ref. [8]Skipjack
Max DP0.0156250.01560.0156250.01560.04680.2810.0468
Table 14. Statistical Analysis of Proposed S-p-Box.
Table 14. Statistical Analysis of Proposed S-p-Box.
S-BoxesInformation EntropyContrastCorrelationEnergyHomogeneityMAD
S-p-box7.74619.81980.05730.01630.422838.5638
AES7.73017.32200.08790.02440.483536.3631
Ref. [6]7.24157.45680.07850.02230.473137.3631
Ref. [10]7.65956.36830.09960.02600.498436.3082
Gray7.23017.52830.05860.02030.462327.4974

Share and Cite

MDPI and ACS Style

Naseer, Y.; Shah, T.; Shah, D.; Hussain, S. A Novel Algorithm of Constructing Highly Nonlinear S-p-boxes. Cryptography 2019, 3, 6. https://0-doi-org.brum.beds.ac.uk/10.3390/cryptography3010006

AMA Style

Naseer Y, Shah T, Shah D, Hussain S. A Novel Algorithm of Constructing Highly Nonlinear S-p-boxes. Cryptography. 2019; 3(1):6. https://0-doi-org.brum.beds.ac.uk/10.3390/cryptography3010006

Chicago/Turabian Style

Naseer, Yasir, Tariq Shah, Dawood Shah, and Sadam Hussain. 2019. "A Novel Algorithm of Constructing Highly Nonlinear S-p-boxes" Cryptography 3, no. 1: 6. https://0-doi-org.brum.beds.ac.uk/10.3390/cryptography3010006

Article Metrics

Back to TopTop