An image encryption algorithm based on spatiotemporal chaos and middle order traversal of a binary tree

Yining Su(苏怡宁), Xingyuan Wang(王兴元), and Shujuan Lin(林淑娟)

School of Information Science and Technology,Dalian Maritime University,Dalian 116026,China

This paper proposes an image encryption algorithm based on spatiotemporal chaos and middle order traversal of a binary tree. Firstly, other programming software is used to perform the middle order traversal, and the plaintext image is sorted according to the middle order traversal sequence on the permutation. Secondly, the chaotic sequence is generated using the coupled map lattice to set the chaotic interference value. Finally,the XOR operation between the adjacent pixel values of the replacement image is completed to generate the ciphertext matrix. The simulation and experimental results show that the proposed algorithm can resist typical attacks and has good robustness.

Keywords: spatiotemporal chaos,image encryption,middle order traversal,coupled map lattice

1. Introduction

With the rapid development of network and communication technology,information based on audio,video and image storage is distributed on various public platforms. Therefore,information security has become an important topic.[1–4]The key to researching information security is to preserve information security during the process of information transmission.

Chaos has cryptographic characteristics such as parameter sensitivity.[5–7]Recently, many image encryption schemes have been proposed, based on DNA,[8,9]neural networks,[10–12]chaos,[13–16]substitution boxes,[17–20]etc.These encryption schemes are based on the sensitivity of chaos to the initial conditions.In the past 10 years they have attracted widespread attention and achieved positive results in the field of image encryption. Wanget al.proposed the anti-dynamic degradation theorem, which proved that a chaotic stream cipher system is theoretically secure.[21]Therefore, chaotic cryptography has entered a new stage. The recently proposed spatiotemporal chaotic system caused fluctuations in chaotic cryptography with its excellent chaotic dynamics.[21–25]However, for the image encryption algorithm proposed in this paper, space–time chaos alone is not sufficient and it does not meet the standards of information security. Therefore, different mechanisms are needed to jointly resist the destruction of and tampering with information in the transmission process.

Middle order traversal of a binary tree is a method for traversing a binary tree in a data structure.Its traversal method is to traverse the left subtree first, then access the root node and finally traverse the right subtree. The sequence generated by this method is not sequential nor is it periodic,like cat mapping, and is easy to implement. In this paper, sequential traversal of a binary tree is applied to replace image encryption, which effectively disturbs the original position of plaintext pixels.

The encryption algorithm proposed in this paper is based on a combination of spatiotemporal chaos and sequential traversal of a binary tree. The key is generated by the plaintext image through the SHA-512 hash function, which increases the sensitivity of the plaintext. The chaotic dynamics of spatiotemporal chaos and the permutation method of order traversal in binary trees effectively increase the image confusion.

The rest of the paper is summarized as follows. Section 2 introduces the preparation work before the algorithm is implemented. Section 3 introduces the implementation of the encryption algorithm in detail. Section 4 shows the simulation results of the encryption algorithm. Section 5 is a security analysis of the algorithm. Section 6 gives a performance analysis of the algorithm. Section 7 contains our conclusions.

2. Related work

2.1. Coupled map lattices

A coupled map lattice (CML) is a dynamic system with discrete time, discrete space and a continuous state. CMLs are widely used to generate spatiotemporal chaos. A CML consists of a non-linear map located on a grid point called a local map. Each local map is coupled to other local maps according to a certain coupling rule. In fact, in computer implementations,any chaotic system must have periodicity with limited precision,but the actual period of a CML may be large enough to protect information security. CMLs were proposed by Kaneko[26]and can be described as

whenu ∈(3.5699456,4) andxn ∈(0,1) the system is in a chaotic state.

2.2. Middle order traversal of a binary tree

Middle order traversal is a kind of binary tree traversal,also called middle root traversal and middle order travel. In a binary tree,the in-order traversal first traverses the left subtree,then accesses the root node and finally traverses the right subtree.The order traversal process in the binary tree is shown in Fig.1.

Fig.1. Middle order traversal of a binary tree.

2.3. Replacement method based on middle order traversal of a binary tree

In this paper, middle order traversal of a binary tree is applied to the permutation of the image, and the chaos of the ordered traversal sequence in the binary tree is adopted. Due to the large number of pixel values of the image, constructing a binary tree and performing a middle order traversal operation on the pixel values of the image may be difficult to implement and increase the running speed and time of the algorithm. Therefore,this paper adopts the middle order traversal 1–65536 through VC++ 6.0 to generate the sequence.txt document,which stores the middle order traversal sequence of 1–65536 and then traverses the image pixel values according to the order. Sorting is done to complete the image replacement operation. The pseudo code that generates the middle order traversal sequence is as follows:

3. Encryption algorithm

3.1. Key structure

The key system structure of this paper is shown in Fig.2 and consists of four parts. Hereεanduare the control parameters of the CML anda1anda2are the initial values of the two coupled maps. In this paper,the keykis generated by the plaintext image through the SHA-512 hash function,which is divided into 8-bit blocks and converted into 64 decimal numbersk1,k2,...,k64.

wherea0andb0are control parameters added to increase the sensitivity of the key. The function uses parameters within the range ofu ∈(3.89,4].uis obtained by the following transformationu:

SHA-512 (512bit)ε u a1 a2

3.2. Encryption process

The encryption process based on spatiotemporal chaos and middle order traversal of a binary tree is as follows:

Step 1: A 512-bit keykis generated by the plaintext image through the SHA-512 hash function.

Step 2: The sequence.txt file generated in Subsection 2.3 is converted into matrixIaccording to

Step 3: Since the matrixIis a middle order traversal sequence, the plaintext imagePis converted into a onedimensional sequence,P1, a sequence traversal sequence is used for sortingP1according to Eq.(6)and a permutation matrixBis generated,

Step 4:Equation(1)is iteratedM×N+500 times according to the key in Subsection 3.1,cancelling the first 500 values and avoiding transient reaction. Finally,chaotic sequencesS1,S2are generated.

Step 5: According to Eq. (7),S1,S2are integerized to generateS,which is used for the chaotic interference value of the diffusion,

S(i)=mod(floor(double(S1(i)+S2(i))×256),256).(7)

Step 6: A ciphertext matrixCis generated by performing a XOR operation between the pixel value and the adjacent pixel value according to

3.3. Decryption process

The ciphertext imageCis transmitted to the receiver through the common channel,and the keys are transmitted to the receiver through the key exchange protocol.[27]The decryption process is the reverse of the encryption process. Specific steps are as follows:

Step 1:The chaotic sequencesS1,S2are obtained by substituting the key iterative chaotic system. SequenceSis obtained according to Step 5 in Subsection 3.2.

Step 2: The inverse XOR operation is performed according to Eq.(9)to obtainB,

Step 3: The sequenceIgenerated in Subsection 2.3 is used to inverse scrambleBto getP1. Finally,P1is recombined into plaintext imageP.

4. Simulation results

In this paper,Matlab 2017 is used as a simulation tool to test the binary images‘Lena’,‘Cameraman’,and‘House’and a colored‘Lena’image with the encryption method described in this article. The simulation results are shown in Fig.3. Figures 3(a)–3(e) show different plaintext images, figures 3(f)–3(j)are the corresponding ciphertext images,figures 3(k)–3(o)are the corresponding decrypted images,and figures 3(p)–3(r)illustrate the encryption and decryption process for the colored image‘Lena’. We can see that the ciphertext image has completely covered the plaintext information, and the decrypted image is no different from the plaintext image.

5. Security analysis

5.1. Key space analysis

A good encryption algorithm is extremely sensitive to the key,and the key space is large enough to resist typical attacks.In the algorithm described in this paper, the keys used are SHA-512 generated hash value and given keysa0,b0. When the accuracy of the key reaches 10-14, the key space reaches 2512×1028≈2512×293= 2605, which is much larger than 2200. Table 1 compares the key space between this algorithm and other algorithms,and it can be seen from the table that the key space of this algorithm is larger than that of most algorithms. So the key space is large enough to resist a variety of typical attacks.

Table 1. Comparison of the key spaces of different algorithms.

5.2. Key sensitivity analysis

Four sets of experiments were performed to test the sensitivity of the keys,and the color and grayscale‘Lena’images were tested separately. Figure 4 shows the test results. Figures 4(a) and 4(e) show the use of the correct key to decrypt the encrypted image; figures 4(b)–4(d) and figures 4(f)–4(h)show the respective use of the wrong key to decrypt the encrypted image. The wrong key is just a minor change to the correct key. When the plaintext image is not decrypted using the wrong key,the algorithm is sensitive to the key.

Fig.3. Encrypted image and decrypted image of plaintext image: (a)plaintext‘Lena’;(b)plaintext‘Cameraman’;(c)plaintext‘House’;(d)plaintext white;(e) plaintext black; (f) ciphertext of ‘Lena’; (g) ciphertext of ‘Cameraman’; (h) ciphertext of ‘House’; (i) ciphertext of white; (j) ciphertext of black; (k)decryption of‘Lena’;(l)decryption of‘Cameraman’;(m)decryption of‘House’;(n)decryption of white;(o)decryption of black;(p)plaintext color‘Lena’;(q)ciphertext of color‘Lena’;(r)decryption of color‘Lena’.

Fig.4. Key sensitivity analysis: (a)decrypted image with the correct key;(b)decrypted image with ε =ε+10-16;(c)decrypted image with u=u+10-16;(d)decrypted image with a1 =a1+10-16; (e)decrypted image with the correct key; (f)decrypted image with a2 =a2+10-16; (g)decrypted image with ε =ε+10-14;(h)decrypted image with u=u+10-14.

6. Performance analysis

6.1. Histogram analysis

A histogram is a graph that shows the frequency at which gray values of a digital image appear.In order to hide the information of the plaintext image,the histogram of the encrypted image tends to be straight. Figure 5 shows the histogram of the plain image and the ciphertext image of the grayscale images ‘Lena’, ‘Cameraman’, and ‘House’ and figure 6 shows the plaintext images of the R,G,and B channels of the color image ‘Lena’ and the histogram of the ciphertext image. It can be seen from Figs.5 and 6 that the histograms of the encrypted images are very similar. In order to better express the encrypted image histograms, we use the chi-square test. The critical values for the 5% and 1% probability of 255 degrees of freedom are 293.2478 and 310.457,respectively. It can be seen from Table 2 that significance levels of 5%and 1%were accepted. Obviously, the histograms of all ciphertext images tend to be flat, so it is difficult to obtain pure image information through statistical analysis.

Fig.5. Histogram analysis: (a)plaintext‘Lena’;(b)histogram of‘Lena’;(c)ciphertext of‘Lena’;(d)histogram of ciphered‘Lena’;(e)plaintext‘Cameraman’;(f)histogram of‘Cameraman’;(g)ciphertext of‘Cameraman’;(h)histogram of ciphered‘Cameraman’;(i)plaintext‘House’;(j)histogram of‘House’;(k)ciphertext of‘House’;(l)histogram of ciphered‘House’.

Fig.6. Histogram analysis: (a)plaintext color‘Lena’; (b)histogram for plain R component; (c)histogram for plain G component; (d)histogram for plain B component;(e)ciphertext of color‘Cameraman’;(f)histogram for encrypted R component;(g)histogram for encrypted G component;(h)histogram for encrypted B component.

6.2. Correlation analysis

Adjacent pixels have a high correlation between plaintext pixels. In order to hide the information between the plaintext images,the correlation between the pixels is greatly reduced.The formula for calculating the correlation between pixels is as follows:

Herexandyare the gray values of two adjacent pixels. In this paper, 2000 pairs of pixels were selected to test the ‘Lena’,‘Cameraman’ and ‘House’ gray images and the ‘Lena’ color image in clear images with Eq. (10). Figures 7–12 show the correlation between ciphertext images in the horizontal,vertical and diagonal directions.

Table 3 shows the correlation coefficients of the three plaintext images ‘Lena’, ‘Cameraman’, and ‘House’ and the three directions of the ciphertext image. When the correlation coefficient is close to zero, the proposed algorithm can resist statistical analysis. Experiments show that the algorithm is feasible.

Table 4 shows the plaintext image of the three channels of the ‘Lena’ color image and the correlation coefficients in three directions of the ciphertext image. When the correlation coefficient is close to zero, the proposed algorithm can resist statistical analysis. Experiments show that the algorithm is feasible.

Table 2. The χ2 evaluation results of ciphertext images.

Table 3. Correlations of the plain-image(PI)and the corresponding cipher image(CCI)between adjacent pixels.

Table 4. Correlations of the color plain-image(CPI)and the corresponding cipher image(CCI)between adjacent pixels.

Fig.7. Correlation analysis: (a)plaintext‘Lena’;(b)horizontal correlation of plain image;(c)vertical correlation of plain image;(d)diagonal correlation of plain image; (e)ciphertext of‘Lena’; (f)horizontal correlation of ciphered image; (g)horizontal correlation of ciphered image; (h)diagonal correlation of ciphered image.

Fig. 8. Correlation analysis: (a) plaintext ‘Cameraman’; (b) horizontal correlation of plain image; (c) vertical correlation of plain image; (d) diagonal correlation of plain image; (e) ciphertext of ‘Cameraman’; (f) horizontal correlation of ciphered image; (g) horizontal correlation of ciphered image; (h)diagonal correlation of ciphered image.

Fig.9. Correlation analysis: (a)plaintext‘House’;(b)horizontal correlation of plain image;(c)vertical correlation of plain image;(d)diagonal correlation of plain image;(e)ciphertext of‘House’;(f)horizontal correlation of ciphered image;(g)horizontal correlation of ciphered image;(h)diagonal correlation of ciphered image.

Fig. 10. Correlation analysis: (a) plaintext of R component; (b) horizontal distribution for R component; (c) vertical distribution for R component; (d)diagonal distribution for R component; (e) ciphertext of R component; (f) horizontal distribution for ciphered R component; (g) vertical distribution for ciphered R component;(h)diagonal distribution for ciphered R component.

Fig.11. Correlation analysis:(a)plaintext of G component;(b)horizontal distribution for G component;(c)vertical distribution for G component;(d)diagonal distribution for G component; (e) ciphertext of G component; (f) horizontal distribution for ciphered G component; (g) vertical distribution for ciphered G component;(h)diagonal distribution for ciphered G component.

Fig.12. Correlation analysis: (a)plaintext of B component;(b)horizontal distribution for B component;(c)vertical distribution for B component;(d)diagonal distribution for B component; (e) ciphertext of B component; (f) horizontal distribution for ciphered B component; (g) vertical distribution for ciphered B component;(h)diagonal distribution for ciphered B component.

6.3. Information entropy analysis

Information entropy is used to reflect the degree of confusion in an image. It is calculated as follows:

wherep(si)represents the probability of occurrence ofsi. For an image, the ideal value for information entropy is 8. Table 5 shows the plaintext images of the three grayscale images‘Lena’,‘Cameraman’and‘House’and the color image‘Lena’and the information entropy of the ciphertext images. Experiments show that the information entropy of all ciphertext images is close to 8, which means that the cipher image of the algorithm has good randomness.

6.4. Differential attack analysis

The number of pixels change rate(NPCR)and unified average changing intensity (UACI) randomness tests are commonly used to evaluate the ability of an encrypted image to resist differential attacks. NPCR and UACI are calculated as follows:

hereWandHrepresent,respectively,the width and height of the image andc1andc2are the two ciphertext images after the original plaintext image changes by one pixel value. Ifc1(i,j)/=c2(i,j),thenD(i,j)=1,otherwiseD(i,j)=0. Table 6 shows the NPCR and UACI values for the three grayscale images‘Lena’,‘Cameraman’and‘House’and the color image‘Lena’. The ideal value of NPCR is 99.6094%and for UACI it is 33.4635%. It can be seen from Table 7 that the NPCR and UACI values of this algorithm are closer to ideal values than those of most algorithms.

6.5. Robust analysis

Images are vulnerable to hijacking, tampering or destruction during transmission,so we usually use noise-adding methods to evaluate whether the encryption algorithm is robust.[34]Figure 13 shows the decryption effect after adding noise to the encrypted image. Experiments show that the image information can still be obtained after adding noise,which shows that the proposed algorithm has good robustness.

Table 5. Information entropy of the plain-image (PI) and the cipher-image(CI).

Table 6. The average NPCR and UACI values with various images.

Table 7. Comparison of NPCR and UACI for different algorithms for the image‘Lena’.

Fig. 13. Robust analysis. (a) The encrypted image with 0.01 salt and pepper noise. (b) The encrypted image with 0.05 salt and pepper noise. (c) The encrypted image with 0.01 Gaussian noise. (d)The encrypted image with 0.05 Gaussian noise. (e)The encrypted image with 0.01 speckled noise. (f)The decrypted image with 0.01 salt and pepper noise. (g) The decrypted image with 0.05 salt and pepper noise. (h) The decrypted image with 0.01 Gaussian noise. (i)The decrypted image with 0.05 Gaussian noise. (j)The decrypted image with 0.01 speckled noise.

6.6. Time analysis

Encryption time is also a necessary condition for evaluating encryption algorithms. The experimental environment is MATLAB R2016a with AMD Ryzen 5 3500H CPU and 8 GB RAM. We encrypt the ‘Lena’ image 50 times, take the average value and compare it with other algorithms to get Table 8.It can be seen from the table that the encryption time of this algorithm is shorter than that of most of the other algorithms,which shows that encryption of this image is faster.

Not only experimental time analysis but also theoretical time complexity analysis should be carried out. Assuming the size of the image isM×N, Step 1 generates the hash value whose time complexity isO(512). The required binary tree sequence is obtained in Step 2, with the time complexity ofO(M×N). In Step 3, the binary tree sequence is used to scramble the image, whose time complexity isO(M×N).Step 4 is to iterate the chaotic system and generate two chaotic sequences, whose time complexity is 2O(M×N). In Step 5,the required XOR sequence is generated, whose time complexity isO(M×N). In Step 6 the ciphertext image is obtained from the XOR scrambled image,and its time complexity isO(M×N). Therefore, the time complexity of the algorithm is 2O(M×N). Table 9 compares the time complexity between the present algorithm and other algorithms, and shows the present algorithm is superior to most of the other algorithms.

Table 8. Time comparisons for different algorithms.

Table 9. Comparison of time complexity for different algorithms.

7. Conclusion

The encryption algorithm proposed in this paper is based on a combination of spatiotemporal chaos and sequential traversal of a binary tree. The key is generated by the plaintext image through the SHA-512 hash function, which increases the sensitivity of the plaintext. The chaotic dynamics of spatiotemporal chaos and the permutation method of order traversal in binary trees effectively increase the image confusion.Diffusion uses an adjacent or exclusive XOR based on chaotic interference values, which makes ciphertext images resistant to differential attacks.

Acknowledgments

Project supported by the National Natural Science Foundation of China (Grant No. 61672124), the Password Theory Project of the 13th Five-Year Plan National Cryptography Development Fund (Grant No. MMJJ20170203), Liaoning Province Science and Technology Innovation Leading Talents Program Project (Grant No. XLYC1802013), Key Research and Development Projects of Liaoning Province,China(Grant No.2019020105-JH2/103),and Jinan City‘20 universities’Funding Projects Introducing Innovation Team Program(Grant No.2019GXRC031).