# Image Encryption Scheme Based on Balanced Two-Dimensional

Authors: Xiaoyan Zhang; Chao Wang; Sheng Zhong; Qian Yao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Cellular automata (CA) are simple models of computation which exhibit fascinatingly complex behavior. Due to the universality of CA model, it has been widely applied in traditional cryptography and image processing. The aim of this paper is to present a new image encryption scheme based on
balanced two-dimensional cellular automata. In this scheme, a random image with the same size of the plain image to be encrypted is first generated by a pseudo-random number generator with a seed. Then, the random image is evoluted alternately with two balanced two-dimensional CA rules. At last, the cipher image is obtained by operating bitwise XOR on the final evolution image and the plain image. This proposed scheme possesses some advantages such as very large key space, high randomness, complex cryptographic structure, and pretty fast encryption/decryption speed. Simulation results obtained from some classical images at the USC-SIPI database demonstrate the strong performance of the proposed image encryption scheme.


---

## Body

## 1. Introduction

Nowadays images are widely used in multimedia applications. These images often contain private or confidential information and sometimes they are associated with financial interests. Security thus becomes increasingly important in the communication and storage of these images. In order to guarantee security, we need process images with the help of cryptography. The purpose of cryptography is to hide the content of messages by encrypting them, so as to make them unrecognizable unless decrypted by someone who has been given a special decryption key. There are several conventional encryption methods which are often used to encrypt common messages or texts, but these traditional cryptographic algorithms do not fit image encryption because of the different characteristics between digital data and image data. The notion of “image encryption” is aiming toward the emerging cryptographic technologies and applications on images. Image encryption has applications in many fields such as internet communication, multimedia systems, medical imaging, telemedicine, and military communication. However, images have intrinsic characteristics like bulk data capacity and high redundancy, as well as real-time requirement. Encryption on images has its own special requirements.Cellular automaton (CA) is a good candidate for image cryptosystems because of its inherent properties like parallelism, homogeneity, and unpredictability, as well as it is being easily implemented in both software and hardware systems. Ever since Wolfram studied the first secret key process based on cellular automata [1], many researchers had explored variant cryptology based on them [2–5]. In recent years, CA especially has been used widely for image cryptography, including image scrambling [6], watermarking [7], secret image sharing [8–11], image encryption [12–18], and image security system [19–21]. In addition, CA has been applied in the field of image processing [22], including image coding [23] and image segmentation [24]. Other methods also have been researched for image encryption [25–27].In the first beginning, some researchers designed image encryption schemes with one-dimensional (1D) CA [17, 18]. Because the image is a two-dimensional array of pixels instead of a one-dimensional digital data, two-dimensional (2D) cellular automata will be more suitable to be applied for image encryption. So later, some people introduced two-dimensional CA in the application of image encryption. But many of them used Von Neumann neighborhood [12, 13, 19, 20], or incomplete Moore neighborhood [14], instead of Moore neighborhood, which influenced the capacity of key space. In this paper, a new image encryption method is proposed based on balanced two-dimensional cellular automata with complete Moore neighborhood. Firstly, we use 2D cellular automata with complete Moore neighborhood which is easy to get larger key space. Secondly, we use balanced CA rules which are helpful to generate cipher images with higher randomness. Thirdly, we choose several rows from the initial random image to generate the sequence which controls the order of two balanced CA rules with different radius, which enhances the complexity of our encryption scheme. Furthermore, the encryption/decryption algorithms with their properties are tested and analyzed. Results show that this image encryption is lossless and has a good statistical performance.This paper is organized as follows. Some background knowledge of 2D CA is described in Section2. The proposed image encryption/decryption method is presented in Section 3. Simulation results are given in Section 4. The key space analysis and other security analysis are shown in Section 5. Finally, some conclusions are presented in Section 6.


## 2. 2D Cellular Automata

Acellular automaton is a discrete dynamical system that consists of an arrangement of basic components called cells together with a transition local rule f [1]. The cells have a finite number of states that are updated synchronously according to the specified local rule. Configuration Ct consists of all the states of cells at time t. Since image is made up of pixels specified by two-dimensional plane coordinates, we take a two-dimensional CA as example in a concrete description. ℤ2 is the underlying space of the two dimensional CA. The cells are arranged in the form of a square lattice structure. The intersections of squares form the cells of the automaton. We can use (a,b) to specify every cell whose state is assumed to be 0 or 1 and whose neighborhood is the set of nine cells (a±1,b), (a,b±1), (a±1,b±1), and (a,b). The neighborhood is the so-called Moore neighborhood which is formed by the specified cell (a,b) with its eight nearest neighbors. We denote the state of cell (a,b) by sa,b. Then, the nine cells are arranged in f in such a way as
(1)f(sa-1,b-1sa-1,bsa-1,b+1sa,b-1sa,bsa,b+1sa+1,b-1sa+1,bsa+1,b+1).
Hence, f can be expressed in equations as follows: (2)f(000000000)=ε0,f(000000001)=ε1,⋯f(bin(i))=εi⋯,f(111111111)=ε511,where bin(i) means the 8-bit binary representation of i, εi∈{0,1}, and i∈{0,1,…,511}. f is called a radius-1 neighborhood local rule. For convenience, we represent the local rule f by ε0ε1…ε511, which is called the Wolfram number of f. For example, f=0x(A16DB83C)16 represents a 128-bit hexadecimal number, that is, 512-bit binary number, combined by 16 copies of the same hexadecimal number 0xA16DB83C together. If there are 256 0s and 256 1s in the 512-bit binary representation of f, we call f a balanced CA local rule. If we consider the CA rule and the plain text as an information source, the amount of information is the increased uncertainty of ciphertext generated by the information source, that is, entropy. It can be proved that the ciphertext generated by the balanced CA rules has a bigger entropy than that generated by the unbalanced CA rules. The balanced CA rules are better rules to generate ciphertext with maximal entropy. So in the proposed image security system, we use balanced CA rules to encrypt images.We denote(3){(y1,y2):|yi-xi|≤j,1≤i≤2,j∈ℤ+}
as the radius-j neighborhood of the cell (x1,x2). Note that there are 25 cells in every cell's radius-2 neighborhood, and the number of independent variables of local rule achieves 225. Then, the set of local rules would contain
(4)2225=233554432
elements. Similar to radius-1 neighborhood local rule, we represent the radius-2 neighborhood local rule g by
(5)ε0,ε1,…,ε33554431.
For example,
(6)g=0x(E2A87F53C046BD191D5780AC3FB942E6)262144
represents a 8388608-bit hexadecimal number, that is, 33554432-bit binary number, combined by 262144 copies of the same hexadecimal number
(7)0xE2A87F53C046BD191D5780AC3FB942E6
together. If exactly half of these 33554432 binary numbers are 0, g is also a balanced CA local rule. A radius-j neighborhood local rule can be similarly represented if j≥3.Suppose that the original configuration isC0 at time t=0, and the states of cells, say, in the radius-1 neighborhood of a cell whose state is x0 are x0,x1,…,x8. If we operate the rule f on C0, the state of the cell will change to be f(x0,x1,x2,…,x8) at time t=1. All cells’ states can be obtained in the same way. We put the states together to obtain configuration C1 which can be considered as the result of the global transformation ρf acting on C0. We can write C1=ρf(C0). Sometimes, we simply write C1=f(C0). Furthermore, C2=f(C1), C3=f(C2), C4=f(C3), … can be generated in succession.


## 3. The Proposed Image Encryption and Decryption Scheme

Because every image is finite whileℤ2 is infinite, we must deal with this contradiction by applying two dimensional CA. If we consider the image to be on a topological anchor ring, that is, the right border of the image laps the left one and the top border superposes the bottom one, then every pixel has nine neighbors (including itself) in its neighborhood in the image.Without loss of generality, we take black-and-white binary imageM with height H and width W to illustrate how to encrypt image by applying the proposed CA approach. Let black represent 1 and let white represent 0 in a black-and-white binary image M. Each row of image M can be considered as a 0-1 binary string of length W.Our proposed image encryption/decryption scheme is a kind of stream cipher. In our image encryption scheme, the sender Alice and the receiver Bob agree on some necessary information in the beginning: a selected balanced radius-1 neighborhood local rulef0, a selected balanced radius-2 neighborhood local rule f1, a seed(seed) which is used to generate pseudo-random numbers, a subpermutation π(H)=i1i2…ik of {1,2,…,H}, where ij∈{1,2,…,H}, 1≤j≤k, 1≤k≤H. In other words, Alice should transmit f0, f1, seed, and π(H) to Bob through secret channel before she sends cipher images. Alice generates an original random binary image RM with the same size as the plain image M by a pseudo-random number generator (PRNG) with seed. Denote the ijth row of RM by Lij, where ij∈{1,2,…,H}. Lij will be a binary string of length W. We concatenate the strings Li1,Li2,…,Lik one by one, then we get a binary string of length kW, denoted by L~, that is, L~=Li1,Li2,…,Lik. Here L~ can be considered as a control sequence to determine whether f0 or f1 is being used in the encryption process. Suppose
(8)L~=p1,p2,…,pW∣pW+1,pW+2,…,p2W∣⋯∣p(k-1)W+1,p(k-1)W+2,…,pkW,
where pj is 0 or 1, 1≤j≤kW, and the short vertical lines are used to facilitate observation. The proposed image encryption/decryption scheme is described as follows.


### 3.1. The Image Encryption Algorithm

Step 1.
Alice generatesRM by a PRNG with seed. Let i=1 and C0=RM be the configuration at time t=0.Step 2.
Alice getsTi after the sequential local rules fp(i-1)W+1,fp(i-1)W+2,…,fpiW-1,fpiW acting on Ci-1 successively, that is, Ti=fpiW(fpiW-1(⋯fp(i-1)W+2(fp(i-1)W+1(Ci-1)))). Then let Ci=Ti⊕RM; that is, operate XOR on Ti and RM.Step 3.
Leti=i+1. If i≤k, go to Step 2; else, go to Step 4.Step 4.
Alice obtains the cipher-imageE=Ck⊕M through the operation of XOR on Ck and M.Step 5.
Alice sendsE to Bob.


### 3.2. The Image Decryption Algorithm

Step 1.
Bob getsC0=RM by the PRNG with seed that he has obtained through the secret channel from Alice. And then he gets L~=Li1,Li2,Li3,…,Lik from π(H) and RM; that is, he knows
(9)L~=p1,p2,…,pW∣pW+1,pW+2,…,p2W∣⋯∣p(k-1)W+1,p(k-1)W+2,…,pkW.
Let i=1.Step 2.
Bob getsTi after the sequential local rules fp(i-1)W+1,fp(i-1)W+2,…,fpiW-1,fpiW acting on Ci-1 successively, and then he gets Ci=Ti⊕RM.Step 3.
Leti=i+1. If i≤k, go to Step 2; else, go to Step 4.Step 4.
Bob easily recovers the original secret black-and-white binary imageM through the operation of XOR on Ck and E because Ck⊕E=Ck⊕(Ck⊕M)=M.


## 3.1. The Image Encryption Algorithm

Step 1.
Alice generatesRM by a PRNG with seed. Let i=1 and C0=RM be the configuration at time t=0.Step 2.
Alice getsTi after the sequential local rules fp(i-1)W+1,fp(i-1)W+2,…,fpiW-1,fpiW acting on Ci-1 successively, that is, Ti=fpiW(fpiW-1(⋯fp(i-1)W+2(fp(i-1)W+1(Ci-1)))). Then let Ci=Ti⊕RM; that is, operate XOR on Ti and RM.Step 3.
Leti=i+1. If i≤k, go to Step 2; else, go to Step 4.Step 4.
Alice obtains the cipher-imageE=Ck⊕M through the operation of XOR on Ck and M.Step 5.
Alice sendsE to Bob.


## 3.2. The Image Decryption Algorithm

Step 1.
Bob getsC0=RM by the PRNG with seed that he has obtained through the secret channel from Alice. And then he gets L~=Li1,Li2,Li3,…,Lik from π(H) and RM; that is, he knows
(9)L~=p1,p2,…,pW∣pW+1,pW+2,…,p2W∣⋯∣p(k-1)W+1,p(k-1)W+2,…,pkW.
Let i=1.Step 2.
Bob getsTi after the sequential local rules fp(i-1)W+1,fp(i-1)W+2,…,fpiW-1,fpiW acting on Ci-1 successively, and then he gets Ci=Ti⊕RM.Step 3.
Leti=i+1. If i≤k, go to Step 2; else, go to Step 4.Step 4.
Bob easily recovers the original secret black-and-white binary imageM through the operation of XOR on Ck and E because Ck⊕E=Ck⊕(Ck⊕M)=M.


## 4. Simulation Experiments

As an example, we take the classic gray-scale image “Lena” with sizeW×H, as the plain image M to show our algorithm. Here, W=H=128. The gray scale of each pixel in the image is between 0 and 255. In order to use our algorithm, we represent each pixel’s gray scale in the binary number system. For example, let mij be the gray scale of the pixel in the ith row and jth column and mij=b1,b2,…,b8, where bi=0 or 1, 1≤i≤8. Then, we regard “Lena” image as composition of 8 layers. Each layer is a black-and-white image of size W×H. And the pixel located in the ith row and jth column of the kth layer is black if bk=1 and white if bk=0. In other words, the kth layer consists of all the pixels with value 0 or 1 that equals to the kth bit of the binary representation of each pixel of “Lena” image.Suppose Alice and Bob both agree on the balanced radius-1 neighborhood local rulef0 and balanced radius-2 neighborhood local rule f1 being
(10)f0=0x(A16DB83C)16,f1=0x(E2A87F53C046BD19)524288,
respectively. Of course they can choose other appropriate balanced CA rules as they want.Alice generates a random gray-scale imageRM with the same size of “Lena” image by the PRNG with seed. RM is also considered as composition of 8 layers. Each layer consists of all the pixels with value 0 or 1 that equals to the kth bit of the binary representation of each pixel of image RM. For each layer of plain image M, this system uses one corresponding layer of RM to encrypt it.Figure1 is “Lena,” the original gray-scale image M encrypted by using our algorithm. And the encryption result is shown in Figure 2. After deciphering the cipher image E by performing the process of decryption with the help of random image RM, Bob can get the recovered image which is identical to the original “Lena” image in Figure 1.Figure 1
Original imageM.Figure 2
Cipher imageE.


## 5. Security Analysis

A good encryption scheme should be robust against all kinds of attacks that are already known, and key space should be large enough to make brute-force attack infeasible. In this section, some security analyses such as key space analysis, statistical analysis, and confusion analysis, have been performed on the proposed image encryption scheme to show that the proposed scheme is secured against the most common attacks.


### 5.1. Key Space Analysis

Key space should be large enough to be robust against the unpredicted attacks. In our encryption scheme, we only need at most(H+4M+64) byte memory to store the sequential local rules fp1,fp2,…,fpkW, which can be realized easily in practice. If the eavesdropper Charlie wants to break this scheme by brute force, he must contend with searching through all subpermutations of {1,2,…,H}, all (512256) possible balanced radius-1 neighborhood local rules and all (3355443216777216) possible balanced radius-2 neighborhood local rules. By counting arguments, we can know that the number of all subpermutations of {1,2,…,H} is
(11)∑k=1H‍(Hk)k!=∑k=1H‍H!(H-k)!=H!∑m=0H-1‍1m!≈H!e,
where e is the base of natural logarithm.Hence, the volume of security key of our encryption scheme is approximately(12)H!e×(512256)×(3355443216777216)>H!e×1010101039.The volume of security key of the scheme that we proposed is much larger than 256, which is the volume of security key introduced in [14]. And it is also larger than 109536, 102194×i, and 1014775 which are the lower bounds of the volume of security key introduced in [12], [19], and [20], respectively. In addition, it is larger than the volume of security key introduced in [16–18]. This makes the algorithm robust against unpredicted attacks.


### 5.2. Statistical Analysis

An encryption algorithm should be robust against statistical attacks. For testing it, statistical analysis such as image histogram and correlation coefficient of images has been conducted. In order to get the better statistical performance, we use the balanced CA rules instead of common CA rules in our proposed image encryption scheme.


#### 5.2.1. Histogram Analysis

Image histogram is used to show the number of pixels per gray level. In general, more uniformed histogram results in less statistical attacks. The encrypted results are shown in Figure3. Frame (a) is the original image and frame (c) is its histogram. Frame (b) is the encrypted image and frame (d) is the corresponding histogram of it.Figure 3
Histogram analysis.It is clearly shown in Figure3 that the histogram of the encrypted image is almost uniform regardless of the original image and is significantly different from that of the original image, so statistical attacks will become very difficult.


#### 5.2.2. Correlation Coefficients

In a digital image pixels are not independent and their relevance is great. This may indicate that a large area of the image has similar gray-scale value. For example, in a common television digital image, the correlation coefficient of adjacent pixels may reach 0.9; that is, the relevance (which means information redundancy) is very big. The smaller the relevance, the better is the encryption effect and the higher is the security.We show the fact that the relevance between plain images and cipher images is very small in two ways.First we repeat the encryption scheme 16 times using the plain-image “Lena.” Each time a different random imageRM is generated for the encryption scheme. We calculate the correlation coefficients between the plain-image M and the ciphered-image E.  Here, we use the formulae in [21]:
(13)ρ=cov(x,y)D(x)D(y)cov(x,y)=1N∑i=1N‍(xi-E(x))(yi-E(y))E(x)=1N∑i=1N‍xiD(x)=1N∑i=1N‍(xi-E(x))2,
where x are the gray-scale values of all the pixels in the images M, y are the gray-scale values of all the pixels in the images E, and N is total number of pixels of M or E. ρ can vary between −1 and 1, so 0≤|ρ|<1. If |ρ| is near 1, we will conclude that x and y are correlated and if |ρ| is near 0, we will conclude that there is a trivial correlation between x and y. All the correlation coefficients are calculated and listed in Table 1 as below.Table 1
Correlation coefficients ofM and E.
No.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ρ
0.01
−0.002
0.021
−0.035
0.03
0.008
−0.02
−0.047
0.011
−0.009
0.032
0.054
−0.023
0.018
−0.009
0.033Second, we test horizontal, vertical, and diagonal correlations for the plain-image and cipher-image after the encryption process. A number of 4096 random pairs of horizontally, vertically, and diagonally adjacent pixels have been tested. Numerical results are shown in Table2.Table 2
Correlation coefficients for horizontal, vertical, and diagonal directions.
Model
Original image
Encrypted image
Horizontal
0.9173
0.0053
Vertical
0.8425
0.0116
Diagonal
0.7744
−0.0097Correlation coefficients in the table are between −1 and 1. It is a fact that the closer the coefficients are to zero, the smaller the correlation between pixels is. The results show that the correlation coefficients of the encrypted image are close to zero, so correlation between pixels of the encrypted image is very small. This indicates little possibility of prediction and high security.In order to see it more clearly, we show the correlation of two horizontally, vertically, and diagonally adjacent pixels in the original image and the encrypted image in Figure4. Note that to be more explicit, only 600, instead of 4096, points are drawn in each frame.Correlation of two horizontally, vertically, and diagonally adjacent pixels: (a), (c), and (e) in the original image (b), (d), and (f) in the encrypted image.
(a)
(b)
(c)
(d)
(e)
(f)


### 5.3. Confusion Analysis

In Shannon's original definitions, confusion refers to making the relationship between the ciphertext and the private key as complex and involved as possible. An excellent encryption algorithm should be sensitive to small changes in key. In other words, a slight change in the key can cause very different results. For example, in the experiment simulation, we usef0 and f1 to encrypt the plain-images. Then we make a very slight modification, for example, changing the first bit of the Wolfram number of f0 to its complement to get f0′. In order to prove that the very small change can lead to a large difference, we perform two simulations as follows.(1) Encrypt three classical images at the USC-SIPI database [28] with key CA rules f0 and f1, f0′ and f1, respectively, while the subpermutation π(H) is the same. Here “Lena,” “House,” and “Pepper” are used as examples. The correlation coefficients between each pair of encrypted images are calculated in Table 3, which shows that a small change of key can lead to very different results.Table 3
Encrypted images with different keys with very small modification.
Original image
Encrypted image withf0 and f1
Encrypted image withf0′ and f1
Correlation coefficients
0.0112
−0.0032
−0.0038In order to give a clearer quantitive illustration, we introduce two indexes NPCR and UACI for further analysis.(
I) NPCR Analysis.In this analysis, a 128×128 image “Lena” is chosen and encrypted by using f0 and f1 to get E1. Then, it is encrypted once again by using f0′ and f1 to get E2. Label the gray-scale values of the pixels at grid (i,j) in E1 and E2 by E1(i,j) and E2(i,j), respectively. Define the “difference array,” D, which is a binary array, with the same size as images E1 and E2. And D(i,j) is determined by E1(i,j) and E2(i,j), namely,
(14)D(i,j)={1ifE1(i,j)=E2(i,j),0otherwise.The number of pixels change rate (NPCR) is defined as(15)NPCR=∑i,jD(i,j)W×H×100%,
where W and H are the width and height of E1 or E2.For two independent random images, the expected value of NPCR isE(NPCR)=(1-2-L)×100%, where L is the number of bits used to represent one pixel of the image. For 8-bit per pixel gray-scale random images, E(NPCR)=(1-2-8)×100%=99.6094%.(
II) UACI Analysis.The unified average changing intensity (UACI) is defined as
(16)UACI=1W×H[∑i,j‍|E1(i,j)-E2(i,j)|255]×100%,
where W and H are the width and height of E1 or E2. The UACI measures the average intensity of the differences between the two cipher images. For two random images, the expected value of UACI is
(17)E(UACI)=∑i=12L-1i(i+1)2L(2L-1)×100%=1+2-L3×100%,
where L is the number of bits used to represent one pixel of the image. For two 8-bit per pixel random gray-scale images, the expected value of UACI is E(UACI)=33.4635%.In our study, we encrypt the plain-image “Lena” with key CA rulesf0 and f1. Then, we encrypt the plain-image “Lena” once again with key CA rules f0′ and f1. f0 and f0′ only differ in the first bit. Finally, the encrypted images are compared. We measure NPCR and UACI of the two cipher images with only one bit difference in key rules and the results are given in Table 4.Table 4
Comparison of NPCR and UACI in encrypting different plain images.
Original images
NPCR of encrypted images
99.7736%
99.6950%
99.6532%
UACI of encrypted images
33.4916%
33.6278%
33.5719%As you see in Table4, the NPCR and UACI values of the scheme are very near to the ideal values 99.6094% and 33.4635%, respectively. Based on these findings, we conclude that our method is safe and our system is secured.(2) After encrypting the plain-image with key rulesf0 and f1 as mentioned above, we make a very slight modification, for example, changing the first bit of the Wolfram number of f0 to its complement to get f0′. Then, if we use f0′ and f1 to decrypt the ciphered image, the decryption should not succeed. Table 5 confirms our findings. In it, frame (a) is the plain image. Frame (b) is the cipher-image encrypted with rules f0 and f1. Frames (c) and (d) show the decrypted images from frame (b) with key rules f0 and f1, f0′ and f1, respectively. It is clear that the image encrypted by f0 and f1 cannot be correctly decrypted by using f0′ and f1. Since there is only one bit difference between the two keys, the results show the high key sensitivity of the proposed CA encryption scheme.Table 5
Encrypt Lena image with key rulesf0 and f1 and then decrypt it with f0′ and f1.
Original Lena image
Encrypted image withf0 and f1
Decrypted image withf0 and f1
Decrypted image withf0′ and f1
Frame (a)
Frame (b)
Frame (c)
Frame (d)


### 5.4. Information Entropy

Entropy is one of the important features for randomness.  The information entropy is defined as follows:(18)H(s)=-∑i=0L‍p(mi)log2p(mi)bits,
where mi is the ith gray value for an L level gray image. The closer an entropy rate is to eight, the less is the possibility of predictability and the higher is the security level. As specified in Table 6, entropy of the encrypted images is very close to 8, and it indicates that this algorithm is robust against entropy attack.Table 6
Entropy of encrypted image.
Original image
Entropy of the encrypted image
7.9886
7.9889
7.9885


## 5.1. Key Space Analysis

Key space should be large enough to be robust against the unpredicted attacks. In our encryption scheme, we only need at most(H+4M+64) byte memory to store the sequential local rules fp1,fp2,…,fpkW, which can be realized easily in practice. If the eavesdropper Charlie wants to break this scheme by brute force, he must contend with searching through all subpermutations of {1,2,…,H}, all (512256) possible balanced radius-1 neighborhood local rules and all (3355443216777216) possible balanced radius-2 neighborhood local rules. By counting arguments, we can know that the number of all subpermutations of {1,2,…,H} is
(11)∑k=1H‍(Hk)k!=∑k=1H‍H!(H-k)!=H!∑m=0H-1‍1m!≈H!e,
where e is the base of natural logarithm.Hence, the volume of security key of our encryption scheme is approximately(12)H!e×(512256)×(3355443216777216)>H!e×1010101039.The volume of security key of the scheme that we proposed is much larger than 256, which is the volume of security key introduced in [14]. And it is also larger than 109536, 102194×i, and 1014775 which are the lower bounds of the volume of security key introduced in [12], [19], and [20], respectively. In addition, it is larger than the volume of security key introduced in [16–18]. This makes the algorithm robust against unpredicted attacks.


## 5.2. Statistical Analysis

An encryption algorithm should be robust against statistical attacks. For testing it, statistical analysis such as image histogram and correlation coefficient of images has been conducted. In order to get the better statistical performance, we use the balanced CA rules instead of common CA rules in our proposed image encryption scheme.


### 5.2.1. Histogram Analysis

Image histogram is used to show the number of pixels per gray level. In general, more uniformed histogram results in less statistical attacks. The encrypted results are shown in Figure3. Frame (a) is the original image and frame (c) is its histogram. Frame (b) is the encrypted image and frame (d) is the corresponding histogram of it.Figure 3
Histogram analysis.It is clearly shown in Figure3 that the histogram of the encrypted image is almost uniform regardless of the original image and is significantly different from that of the original image, so statistical attacks will become very difficult.


### 5.2.2. Correlation Coefficients

In a digital image pixels are not independent and their relevance is great. This may indicate that a large area of the image has similar gray-scale value. For example, in a common television digital image, the correlation coefficient of adjacent pixels may reach 0.9; that is, the relevance (which means information redundancy) is very big. The smaller the relevance, the better is the encryption effect and the higher is the security.We show the fact that the relevance between plain images and cipher images is very small in two ways.First we repeat the encryption scheme 16 times using the plain-image “Lena.” Each time a different random imageRM is generated for the encryption scheme. We calculate the correlation coefficients between the plain-image M and the ciphered-image E.  Here, we use the formulae in [21]:
(13)ρ=cov(x,y)D(x)D(y)cov(x,y)=1N∑i=1N‍(xi-E(x))(yi-E(y))E(x)=1N∑i=1N‍xiD(x)=1N∑i=1N‍(xi-E(x))2,
where x are the gray-scale values of all the pixels in the images M, y are the gray-scale values of all the pixels in the images E, and N is total number of pixels of M or E. ρ can vary between −1 and 1, so 0≤|ρ|<1. If |ρ| is near 1, we will conclude that x and y are correlated and if |ρ| is near 0, we will conclude that there is a trivial correlation between x and y. All the correlation coefficients are calculated and listed in Table 1 as below.Table 1
Correlation coefficients ofM and E.
No.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ρ
0.01
−0.002
0.021
−0.035
0.03
0.008
−0.02
−0.047
0.011
−0.009
0.032
0.054
−0.023
0.018
−0.009
0.033Second, we test horizontal, vertical, and diagonal correlations for the plain-image and cipher-image after the encryption process. A number of 4096 random pairs of horizontally, vertically, and diagonally adjacent pixels have been tested. Numerical results are shown in Table2.Table 2
Correlation coefficients for horizontal, vertical, and diagonal directions.
Model
Original image
Encrypted image
Horizontal
0.9173
0.0053
Vertical
0.8425
0.0116
Diagonal
0.7744
−0.0097Correlation coefficients in the table are between −1 and 1. It is a fact that the closer the coefficients are to zero, the smaller the correlation between pixels is. The results show that the correlation coefficients of the encrypted image are close to zero, so correlation between pixels of the encrypted image is very small. This indicates little possibility of prediction and high security.In order to see it more clearly, we show the correlation of two horizontally, vertically, and diagonally adjacent pixels in the original image and the encrypted image in Figure4. Note that to be more explicit, only 600, instead of 4096, points are drawn in each frame.Correlation of two horizontally, vertically, and diagonally adjacent pixels: (a), (c), and (e) in the original image (b), (d), and (f) in the encrypted image.
(a)
(b)
(c)
(d)
(e)
(f)


## 5.2.1. Histogram Analysis

Image histogram is used to show the number of pixels per gray level. In general, more uniformed histogram results in less statistical attacks. The encrypted results are shown in Figure3. Frame (a) is the original image and frame (c) is its histogram. Frame (b) is the encrypted image and frame (d) is the corresponding histogram of it.Figure 3
Histogram analysis.It is clearly shown in Figure3 that the histogram of the encrypted image is almost uniform regardless of the original image and is significantly different from that of the original image, so statistical attacks will become very difficult.


## 5.2.2. Correlation Coefficients

In a digital image pixels are not independent and their relevance is great. This may indicate that a large area of the image has similar gray-scale value. For example, in a common television digital image, the correlation coefficient of adjacent pixels may reach 0.9; that is, the relevance (which means information redundancy) is very big. The smaller the relevance, the better is the encryption effect and the higher is the security.We show the fact that the relevance between plain images and cipher images is very small in two ways.First we repeat the encryption scheme 16 times using the plain-image “Lena.” Each time a different random imageRM is generated for the encryption scheme. We calculate the correlation coefficients between the plain-image M and the ciphered-image E.  Here, we use the formulae in [21]:
(13)ρ=cov(x,y)D(x)D(y)cov(x,y)=1N∑i=1N‍(xi-E(x))(yi-E(y))E(x)=1N∑i=1N‍xiD(x)=1N∑i=1N‍(xi-E(x))2,
where x are the gray-scale values of all the pixels in the images M, y are the gray-scale values of all the pixels in the images E, and N is total number of pixels of M or E. ρ can vary between −1 and 1, so 0≤|ρ|<1. If |ρ| is near 1, we will conclude that x and y are correlated and if |ρ| is near 0, we will conclude that there is a trivial correlation between x and y. All the correlation coefficients are calculated and listed in Table 1 as below.Table 1
Correlation coefficients ofM and E.
No.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ρ
0.01
−0.002
0.021
−0.035
0.03
0.008
−0.02
−0.047
0.011
−0.009
0.032
0.054
−0.023
0.018
−0.009
0.033Second, we test horizontal, vertical, and diagonal correlations for the plain-image and cipher-image after the encryption process. A number of 4096 random pairs of horizontally, vertically, and diagonally adjacent pixels have been tested. Numerical results are shown in Table2.Table 2
Correlation coefficients for horizontal, vertical, and diagonal directions.
Model
Original image
Encrypted image
Horizontal
0.9173
0.0053
Vertical
0.8425
0.0116
Diagonal
0.7744
−0.0097Correlation coefficients in the table are between −1 and 1. It is a fact that the closer the coefficients are to zero, the smaller the correlation between pixels is. The results show that the correlation coefficients of the encrypted image are close to zero, so correlation between pixels of the encrypted image is very small. This indicates little possibility of prediction and high security.In order to see it more clearly, we show the correlation of two horizontally, vertically, and diagonally adjacent pixels in the original image and the encrypted image in Figure4. Note that to be more explicit, only 600, instead of 4096, points are drawn in each frame.Correlation of two horizontally, vertically, and diagonally adjacent pixels: (a), (c), and (e) in the original image (b), (d), and (f) in the encrypted image.
(a)
(b)
(c)
(d)
(e)
(f)


## 5.3. Confusion Analysis

In Shannon's original definitions, confusion refers to making the relationship between the ciphertext and the private key as complex and involved as possible. An excellent encryption algorithm should be sensitive to small changes in key. In other words, a slight change in the key can cause very different results. For example, in the experiment simulation, we usef0 and f1 to encrypt the plain-images. Then we make a very slight modification, for example, changing the first bit of the Wolfram number of f0 to its complement to get f0′. In order to prove that the very small change can lead to a large difference, we perform two simulations as follows.(1) Encrypt three classical images at the USC-SIPI database [28] with key CA rules f0 and f1, f0′ and f1, respectively, while the subpermutation π(H) is the same. Here “Lena,” “House,” and “Pepper” are used as examples. The correlation coefficients between each pair of encrypted images are calculated in Table 3, which shows that a small change of key can lead to very different results.Table 3
Encrypted images with different keys with very small modification.
Original image
Encrypted image withf0 and f1
Encrypted image withf0′ and f1
Correlation coefficients
0.0112
−0.0032
−0.0038In order to give a clearer quantitive illustration, we introduce two indexes NPCR and UACI for further analysis.(
I) NPCR Analysis.In this analysis, a 128×128 image “Lena” is chosen and encrypted by using f0 and f1 to get E1. Then, it is encrypted once again by using f0′ and f1 to get E2. Label the gray-scale values of the pixels at grid (i,j) in E1 and E2 by E1(i,j) and E2(i,j), respectively. Define the “difference array,” D, which is a binary array, with the same size as images E1 and E2. And D(i,j) is determined by E1(i,j) and E2(i,j), namely,
(14)D(i,j)={1ifE1(i,j)=E2(i,j),0otherwise.The number of pixels change rate (NPCR) is defined as(15)NPCR=∑i,jD(i,j)W×H×100%,
where W and H are the width and height of E1 or E2.For two independent random images, the expected value of NPCR isE(NPCR)=(1-2-L)×100%, where L is the number of bits used to represent one pixel of the image. For 8-bit per pixel gray-scale random images, E(NPCR)=(1-2-8)×100%=99.6094%.(
II) UACI Analysis.The unified average changing intensity (UACI) is defined as
(16)UACI=1W×H[∑i,j‍|E1(i,j)-E2(i,j)|255]×100%,
where W and H are the width and height of E1 or E2. The UACI measures the average intensity of the differences between the two cipher images. For two random images, the expected value of UACI is
(17)E(UACI)=∑i=12L-1i(i+1)2L(2L-1)×100%=1+2-L3×100%,
where L is the number of bits used to represent one pixel of the image. For two 8-bit per pixel random gray-scale images, the expected value of UACI is E(UACI)=33.4635%.In our study, we encrypt the plain-image “Lena” with key CA rulesf0 and f1. Then, we encrypt the plain-image “Lena” once again with key CA rules f0′ and f1. f0 and f0′ only differ in the first bit. Finally, the encrypted images are compared. We measure NPCR and UACI of the two cipher images with only one bit difference in key rules and the results are given in Table 4.Table 4
Comparison of NPCR and UACI in encrypting different plain images.
Original images
NPCR of encrypted images
99.7736%
99.6950%
99.6532%
UACI of encrypted images
33.4916%
33.6278%
33.5719%As you see in Table4, the NPCR and UACI values of the scheme are very near to the ideal values 99.6094% and 33.4635%, respectively. Based on these findings, we conclude that our method is safe and our system is secured.(2) After encrypting the plain-image with key rulesf0 and f1 as mentioned above, we make a very slight modification, for example, changing the first bit of the Wolfram number of f0 to its complement to get f0′. Then, if we use f0′ and f1 to decrypt the ciphered image, the decryption should not succeed. Table 5 confirms our findings. In it, frame (a) is the plain image. Frame (b) is the cipher-image encrypted with rules f0 and f1. Frames (c) and (d) show the decrypted images from frame (b) with key rules f0 and f1, f0′ and f1, respectively. It is clear that the image encrypted by f0 and f1 cannot be correctly decrypted by using f0′ and f1. Since there is only one bit difference between the two keys, the results show the high key sensitivity of the proposed CA encryption scheme.Table 5
Encrypt Lena image with key rulesf0 and f1 and then decrypt it with f0′ and f1.
Original Lena image
Encrypted image withf0 and f1
Decrypted image withf0 and f1
Decrypted image withf0′ and f1
Frame (a)
Frame (b)
Frame (c)
Frame (d)


## 5.4. Information Entropy

Entropy is one of the important features for randomness.  The information entropy is defined as follows:(18)H(s)=-∑i=0L‍p(mi)log2p(mi)bits,
where mi is the ith gray value for an L level gray image. The closer an entropy rate is to eight, the less is the possibility of predictability and the higher is the security level. As specified in Table 6, entropy of the encrypted images is very close to 8, and it indicates that this algorithm is robust against entropy attack.Table 6
Entropy of encrypted image.
Original image
Entropy of the encrypted image
7.9886
7.9889
7.9885


## 6. Conclusion

In this paper, a new image encryption/decryption scheme is proposed based on balanced two-dimensional CA. If Alice wants to transmit a secret imageM with height H and width W to Bob, they need agree on a subpermutation π(H), a balanced radius-1 neighborhood local rule f0, a balanced radius-2 neighborhood local rule f1, and a seed. Then, Alice generates a random image RM by a PNRG with the seed and evolutes it kW times by alternatively using rules f0 and f1 according to the sub-permution π(H) and RM. After each evolution, a bitwise XOR will be operated on RM and the evoluted result to get Ci. At last, Alice sends to Bob E=Ck⊕M as the cipher-image. The decryption process is similar.The scheme proposed in this paper possesses the characteristics of convenient realization, very large number of security keys, pretty fast encryption speed, and low cost. Theoretical analysis and simulated experiment show that the scheme has the confusion property and excellent performance against statistical attacks.Cellular automata are simple models of computation which exhibit fascinatingly complex behavior. They have captured the attention of several generations of researchers, leading to an extensive body of work. For example, John Conway's Game of Life is actually a two-dimensional CA with special local rule. Due to the universality of CA model, it can be more widely used in cryptography and image processing, and that will be our future work.



---

*Source: 562768-2013-11-10.xml*