Nonlinear Dyn DOI 10.1007/s11071-016-2912-0

ORIGINAL PAPER

An image encryption scheme combining chaos-memory cellular automata and weighted histogram Amina Souyah · Kamel Mohamed Faraoun

Received: 7 January 2016 / Accepted: 19 June 2016 © Springer Science+Business Media Dordrecht 2016

Abstract This paper presents a new symmetric scheme for enciphering digital images. The proposal is based on the combination of chaos and cellular automata (CA) under the scenarios of one round enciphering/deciphering and permutation–diffusion architecture. All the generated key-streams in the proposed cryptosystem are based on the use of an improved one-dimensional (1D) chaotic system [i.e., logistic– tent system (LTS)] with excellent chaotic properties. These key-streams are related to both the secret key and the characteristics of the plain image. Before applying the encryption process, one pixel of the plain image at a random position is overwritten by inserting the weighted histogram value as a new measure to represent the plain image’s features, this pixel withholds the encryption routine and further will be used to guarantee the resistance to known/chosen plain image attacks (CPA secure). In the confusion phase, a bit-level permutation is adopted with the generated one-time keystreams using an improved 1D chaotic system. This strategy of shuffling is handled in which besides to the modification of each pixel’s position, its value is also changed, to further render the achievement of both confusion and diffusion possible within just this phase. The diffusion phase is divided into two subphases: In the A. Souyah (B) · K. M. Faraoun Computer Science Department, Djilalli Liabes University, Sidi Bel Abbès, Algeria e-mail: [email protected] K. M. Faraoun e-mail: [email protected]

first one, the value of each pixel is changed sequentially by means of an improved one-dimensional chaotic system, to fasten the diffusion process and spread the influence of a single bit over the others, and in the second subphase, two-dimensional reversible memory cellular automata are associated with quadtree decomposition strategy and applied to the output of the first subphase, to enhance both the security and the diffusion effect of the cryptosystem. Security analysis shows the capacity of the proposed scheme to resist the commonly known attacks besides to its competitive speed that traces its suitability for practical image encryption. Keywords Image encryption · An improved 1D chaotic system · Reversible memory cellular automata · Weighted histogram

1 Introduction Nowadays, the security of multimedia data such as digital images is taking more and more attention due to its wide use in various applications such as military, e-commerce, telemedicines, video conferencing, broadcasting and financial transaction that lead to the importance of responding to the challenge of fast and sufficiently secure image encryption schemes. It has become aware of that the encryption of images is quite different from those of textual information that can be satisfied through the use of classical cryptographic techniques [1], and this is because of the inher-

123

A. Souyah, K. M. Faraoun

ent features of images such as large data size, bulk data capacity, high redundancy and strong correlation among adjacent pixels besides to the large computational time. Several image encryption schemes are proposed in the scientific literature among which chaosbased approaches, due to the close relationship between chaos and cryptography from the viewpoint of the inherent features of strong sensitivity and dependency on initial conditions and control parameters [2] that characterize the chaotic systems, and establish its direct connectivity with the cryptographic properties of confusion and diffusion [3]. Chaos-based image encryption schemes contain mainly two major phases: confusion and diffusion. In the confusion phase, the pixels of the image are permuted using a chaotic map without any change in the pixel values. In the diffusion phase, the pixel values are modified with the manner that a minor change at one pixel level of the plain image leads to the corresponding cipher image to be significantly different. Therefore, many variants and improvements of the main architecture of chaos-based schemes are proposed including [4–9,43,44]. In [4], a combined architecture of both permutation–diffusion is considered as one phase is proposed, for the purpose of avoiding the duplicated scanning effort for obtaining pixel values, and improving the runtime, the scheme is resisted to known and chosen plaintext attacks by taking into account the extraction of information from the plain image. The use of bit level at the permutation phase rather than the conventional usage of pixel level for shuffling is proposed in [5,6], to meet both the relocation and alteration of pixel values which have the effect of both confusion and diffusion, respectively, in the permutation phase. In [9], besides to the bit-level permutation in confusion phase, a generated random matrix rotation is also used after a block diffusion is applied, for changing the statistical properties of the image. This scheme can be extended easily to be executed in parallel, since there is no sequential mode between pixels as the conventional diffusion operation for image encryption. An improved diffusion scheme named continuous diffusion strategy is proposed in [7,8], the diffusion phase is composed of a supplementary diffusion procedure after the application of the conventional diffusion process, and the motivation of the proposed works is to meet the same level of security under few numbers of rounds. On the other hand, cellular automata-based approaches are widely used and investigated by several researchers, for designing efficient image encryp-

123

tion schemes that are compared with the conventional algorithms. Cellular automata (CAs) are mathematical models and a class of discrete dynamical systems. The concept of CAs was introduced at first by Stanislaw Ulam and John Von Neumann to study the biological processes as self-reproduction, by giving its mathematical model [10]. CAs are proved to be suitable for modeling biological, physical, mathematical, statistical and several types of other systems [11]. It was initially the idea of Steven Wolfram who suggested for the first time the use of CA for cryptography in 1985 [12]. After that, several works are proposed in the scientific literature for image encryption including [13–19]. A combination of both cellular automata and chaos for designing cryptosystems for image security is also proposed where the use of chaotic map is selected in the permutation phase and cellular automata solely in the diffusion phase [20,21,26,42] or the use of both chaotic map and cellular automata in the diffusion phase [22]. Recently, DNA cryptography comes to light as a new cryptographic direction of research due to the attractive properties of parallelism, information density and huge storage [23] that characterize DNA computing. The combination of DNA and chaos is widely investigated by researchers who proposed in this way several image encryption schemes [30–34]. In this paper, we combine chaos with cellular automata for designing a new symmetric image encryption scheme that is easy to be implemented and hard to be cryptanalyzed. The proposed scheme is based on the use of an improved 1D chaotic system suggested in [25], in both confusion and diffusion phases. This chaotic map is shown to exhibit excellent chaotic properties, incorporating uniform data distribution and wide range of parameter settings. It can also easily overcome the commonly known drawbacks of 1D chaotic maps [25] and further enhances the runtime of the cryptosystem by avoiding the use of higher-dimensional chaotic maps. The impact and novelty of the proposed scheme can be summarized as follows: The cryptosystem has an immunity against known/chosen plain image attacks (i.e., the scheme is CPA secure), in which one pixel of the plain image at a random position is overwriting, by inserting the weighted histogram (Wh) value as a new measure to introduce the plain image’s characteristics. This pixel doesn’t undergo the encryption routine, and its value together with the secret key is used to extract the initial conditions and control parameters of the utilized chaotic map, which leads to a random-like gen-

Chaos-memory cellular automata and weighted histogram

erating key-streams (i.e., for every cryptosystem’s execution with the same secret key and a minor alteration at a bit level that can be applied to the plain image, new key-streams are produced in which their recovering comes to be harder by choosing different plain images). In the confusion phase, a bit-level permutation is carried out in incorporation of the generated one-time key-streams using an improved 1D chaotic system, and this way of permuting is handled to ensure that besides to the modification of each pixel’s position, its value is also changed, to further attain both confusion and diffusion within just this phase. The diffusion phase is divided into two subphases: In the first one, the value of each pixel is modified sequentially by means of an improved 1D chaotic system, to accelerate the diffusion process and spread the influence of a single bit over the others, and in the second subphase, two-dimensional (2D) reversible memory cellular automata (RMCA) with moore neighborhood are associated with the mechanism of quadtree decomposition and performed to the output of the first subphase, to enhance the security of the cryptosystem by making it relies on the unfeasibility of inverting a memory k-order cellular automata without the knowledge of the utilized transition rules and at least k-different successive configurations, in addition to the intrinsic chaotic properties of cellular automata that lead to the implicit conduct of the plain image’s sensitivity. The rest of the paper is organized as follows: In Sect. 2, basic definitions of both an improved 1D chaotic system and cellular automata are covered. Section 3 gives a detailed description of the proposed scheme, and its security analysis is shown in Sect. 4. At the end, Sect. 5 concludes the paper.

(ii) these improved chaotic maps are characterized by a wider chaotic range; and (iii) the Lyapunov exponent of each improved chaotic map is larger than its matching seed maps, which reflects the better chaotic performance. Among these suggested 1D chaotic systems, Logistic Tent chaotic system (LTS) is arbitrary selected to be used as a base to design the proposed scheme in this paper, and the two remaining chaotic maps can also do the task as well. Logistic Tent chaotic system (LTS) is based on the use of both logistic map and tent map as seed maps, and it is defined by the following equation [25]:

2 An improved 1D chaotic system and memory cellular automata

V = {(−1, −1) , (−1, 0) , (−1, 1) , (0, −1) , (0, 0) ,

2.1 An improved 1D chaotic system (LTS) In [25], three improved 1D chaotic systems are proposed in the scientific literature. These improved 1D chaotic systems possess at least three advantages in comparison with their matching seed maps, which are illustrated as follows: (i) the generated chaotic sequences of these new proposed maps have a uniform distribution within [0, 1], whereas their corresponding seed maps have a limited data ranges within [0, 1];

xn+1 = A L T (r, xn ) = L (r, xn ) + T ((4, r ) , xn )) mod 1  if xi < 0.5 (r xn (1 − xn ) + (4 − r ) xn /2) mod 1 = (r xn (1 − xn ) + (4 − r ) (1 − xn ) /2) mod 1 else

(1) where the parameter r belongs to the interval (0, 4].

2.2 Cellular automata Two-dimensional cellular automata are discrete dynamical systems that can be defined by a 4-tuple A = (C, S, V, f ), where C = {i, j1 ≤ i ≤ r, 1 ≤ j ≤ c} is the cellular space formed by a finite two-dimensional array of r × c identical objects called cells, each of which has a state belonging to the state set S = Z 2 = {0, 1}. The neighborhood of each cell is expressed by a set V , in which the neighborhood of a cell determined by its indexes of i, j ∈ C is: Vi j = {i + α, j + β, (α, β) ∈ V }

(2)

In the current work, Moore neighborhood is used, and it is formed by the considered cell to be updated and its eight surrounding cells as: (0, 1) , (1, −1) , (1, 0) , (1, 1)}

(3)

The local transition function f : Z 29 = Z 2 is the function that determines the next state of each cell in cellular space, by taking into account its current state and the states of its considered neighbors. So, if Sit j ∈ Z 2 is the state of the cell i, j at time t, the next state of such cell is given by the following formula:  t t t t t = f Si−1, Sit+1 j−1 , Si−1, j , Si−1, j+1 , Si, j−1 , Si, j , j  t t t (4) Si,t j+1 , Si+1, j−1 , Si+1, j , Si+1, j+1

123

A. Souyah, K. M. Faraoun

To deal with the finite cellular space, periodic boundary condition is considered: t ↔ i ≡ u (mod r ) and j ≡ v (mod c) Sit j = Suv

(5)

Until now, each cell at time t depends only on the states of its neighbors at the previous time t − 1. However, if such dependence is expanded to cover states of neighbors at previous times t − 2, t − 3, …, then the CA is named memory CA. The reversibility of cellular automata is a necessary property to force the backward evolution, and one says that CA is reversible if there is another cellular automata that give the opportunity of having the inverse evolution [29]. We denote by C the set of all possible configurations of CA, and the configuration at the next time step is given by the global transition function as follows: Φ:C →C C →C t

t+1

(6)

  = Φ Ct

(7)

And Φ : C × ... × C → C (8)     t t−k t+1 t t−k →C (9) = Φ C ,...,C C ,...,C For memory cellular automata. A 4th order reversible memory cellular automata is considered in the current work, and it is of the form:   C t+1 = Φ C t , . . . , C t−3       = Ψ0 C t ⊕ Ψ1 C t−1 ⊕ Ψ2 C t−2 ⊕ C t−3 (10) where Ψk is defined by the following transition function:

is based on the use of an improved 1D chaotic system and reversible memory cellular automata, and the encryption/decryption process is performed by following the permutation–diffusion architecture under just one round. Firstly, a random pixel overwriting mechanism is handled, and the new measure of plain image’s weighted histogram (Wh) is inserted instead. This mechanism ensures the immunity of the proposed cryptosystem to known/chosen plain image attacks (CPA secure) like the following: the incorporation of the Wh value as a new measure that handles the plain image’s characteristics together with the secret key, in the procedure of extracting the initial values of the used chaotic map (LTS), this conducts to a random-like generating key-streams, i.e., for different plain images, different chaotic sequences are produced, which makes their recovering harder. Secondly, the confusion phase is based on a bit-level permutation and the generated onetime key-streams using the chosen 1D chaotic system, this kind of shuffling permits to modify both the pixel’s location and value to further attain both confusion and diffusion within just this phase. Thirdly, the diffusion phase is separated into two subphases: In the first one, the value of every pixel is modified sequentially by means of the chosen chaotic system, for accelerating the diffusion process and spread out the influence of a single bit over the others, and the second subphase, 2D reversible memory cellular automata (RMCA) is associated with quadtree decomposition method and performed to the output of the former subphase, to enhance the security and diffusion effect of the proposed cryptosystem. The total procedure is shown in Fig. 1.

k t k t k t Sit+1 j = λ1 Si−1, j−1 ⊕ λ2 Si−1, j ⊕ λ3 Si−1, j+1

⊕λk4 Si,t j−1 ⊕ λk5 Si,t j ⊕ λk6 Si,t j+1 t ⊕λk7 Si+1, j−1

t ⊕ λk8 Si+1, j k 9 λi ∈ Z 2 .

t ⊕ λk9 Si+1, j+1

3.1 Random pixel overwriting (11)

For each 1 ≤ i ≤ This kind of cellular automata is reversible [32], and its inverse evolution is possible following the formula:       C t+1 = Ψ C t ⊕ Ψ C t−1 ⊕ Ψ C t−2 ⊕ C t−3 0

1

2

(12) 3 The proposed scheme In this section, a detailed description of the proposed image cryptosystem will be discussed. The proposal

123

One pixel of the plain image at a random position is overwritten, by inserting the weighted histogram value (Wh) as a new measure that represents all the plain image’s pixels except one (i.e., in where we will insert the Wh value), this value handles the plain image’s characteristics and further will be employed to ensure the resistance of the proposed cryptosystem to both known/chosen plain image attacks (CPA secure). The proposed cryptosystem utilizes 512 bits as external key K , and this later is used to calculate the ith and jth positions of the overwriting pixel using the proposed technique in [39] as follows:

Chaos-memory cellular automata and weighted histogram Fig. 1 Block diagram of the proposed cryptosystem where the Wh value is the weighted histogram of all image’s pixels

1. The 512-bits external key K is divided into 8-bit blocks ki as: k = k1 , k2 , . . . , k64 ;

(13)

2. Extract two numbers from the first half of the external key (128 bits) as follows:  64 1 k=1 ki ,1 + V1 = mod 512 (k1 ⊕ · · · ⊕ k8 ) 64 

1 V2 = mod + 512 (k9 ⊕ · · · ⊕ k16 )

64

(14)

In the proposed scheme, the parameter r and the initial condition X0 of the improved 1D chaotic system, are extracted from the external secret key as follows:  64 1 k=1 ki ,1 + r = mod 512 (k17 ⊕ · · · ⊕ k32 ) 64  X 0 = mod

k=1 ki ,1 64

(15) 3. Discretize V1 and V2 using the following two equations:

V1 = {V1 } × 1015 mod M (16)

15  (17) V2 = {V2 } × 10 mod N 4. The ith position and the jth position of the overwriting pixel are calculated as follows: i = V1

(18)

j = V2

(19)

5. The weighted histogram value (Wh) is included in the plain image P as Val 2 (which will be computed in the next section) as follows: P (i, j) = Val 2

3.2 Initial values generation

(20)

1 + 512 (k33 ⊕ · · · ⊕ k48 )

64

k=1 ki

64

(21) ,1 (22)

For updating the values of both the parameter r and the initial condition X 0 , the plain image’s characteristics are handled by means of the weighted histogram (Wh) value, this new measure represents the distribution of all the plain image’s pixels except one pixel (which is used for Wh’s value insertion), and it is calculated as follows: 255

(h [i] /N × M) × h [i] (23) Val 1 = i=0

where N and M are the width and the height of image, respectively, h[i] is an integer array containing the distribution of the considered pixels in [0, 255] range. Then, we calculate Val 2 as follows: Val 2 = Val1 mod 256

(24)

where Val 2 ∈ [0, 255] and mod is the module operation. At the end, the weighted histogram (Wh) value

123

A. Souyah, K. M. Faraoun Fig. 2 Boat plain image (a) and its permuted version (b)

with 10−15 decimal precision is given by: Wh = Val 2 /255

(25)

Then, the parameter r and the initial condition X0 are updated as follows: r = r + Wh X 0

= X 0 + Wh

(26) (27)

Clearly, the new values of r’ as parameter and X’0 as initial condition of LTS chaotic map are both secret key/plain image related, and thus, they are extremely sensitive to any minor change to either the secret key or the plain image, to further generate different keystreams for different plain images even with the same set of keys.

2. Divide each pixel into 8 parts, each one contains 8 bits, and the image is extended to be M × N × 8. 3. After iterating the LTS chaotic map for 500 times to avoid the transient effect, continue to iterate it for M × N × 8 to get the two sequences {X K }, {Y K } and discretize them:

 X K = {X k } × 1015 mod M (28)

15  (29) Y K = {Yk } × 10 mod N × 8 4. Exchange the Pi j and Pxi x j values, where i = 0, 1, . . ., M − 1 and j = 0, 1, . . ., 8N − 1, the permuted image P’ of boat grayscale image 512 × 512 size is shown in Fig. 2.

3.3.2 Diffusion phase 3.3 Description of the cryptosystem 3.3.1 Confusion phase

This phase has as input the shuffled image P and gives as output the ciphered-image C. It is divided into two main phases:

In this phase, a bit-level permutation is considered using the generated one-time key-streams of LTS chaotic map. The procedure of such task is described in detail as follows: Input: The grayscale image P with M rows, N columns and the calculated initial condition of X 0 and parameter r from the Sect. 3.2. Output: The shuffled image P .

First diffusion subphase In this subphase, a sequential mode for enciphering image’s pixels is followed, in which the encryption of each pixel is related to the sum of all the next pixels and the generated key-stream using LTS chaotic map, for the purpose of de-correlating the relations among pixels and accelerating the diffusion effect under just one round. The first subphase of diffusion is described as follows:

1. Get the weighed histogram (Wh) of the plain image and compute the initial values of LTS chaotic map through Eqs. (26), (27).

1. The plain image is transformed from its twodimensional to one-dimensional vector format P = { p1 , p2 , . . ., pM×N }.

123

Chaos-memory cellular automata and weighted histogram

2. Calculate the sum of the plain image pixels according to the following equation:

S=

M×N

−1

X 0

=



X 0 + mod 64 +

Pi

(30)

3. Encrypt all the plain image pixels using the following equations:

Ci = Pi ⊕ (ki + Ci−1 ) mod 256 ⊕ S

64

 

r = r + mod



i=0

S = S − Pi

k=1 ki

(31) (32)

where Ci is the ith encrypted pixel, Pi is the ith plain pixel, ki is a sequence generated using LTS chaotic map in which its initial condition and control parameter are based on the latest two generated values in the previous phase, Ci−1 is the previously encrypted pixel and S is the sum of all image pixels except the ith one (i.e., S is all the next pixels of the ith pixel). The index i is performed from the first pixel of 0 to the last one of M × N − 1. Second diffusion subphase In this subphase, the association of 4th order two-dimensional reversible memory cellular automata (RMCA) with quadtree decomposition strategy is performed, to further amplify the propagation of each bit alteration over the others by means of MCA evolution mechanism, and enhances the security of the cryptosystem. Three different subkeys (i.e., transition rules) are needed for every decomposition level, since 4th order MCA is performed, so, the mechanism of sub-keys’ generation is based on a cryptographically secure pseudorandom bit generator. Since two-dimensional cellular automata Moore neighborhood is used in this subphase, the length of each sub-key (i.e., rule) is 29 i.e., 512 bits. The initial configuration of 512 bits for evolving cellular automata and generating sub-keys is based on the use of LTS chaotic map with the initial condition X 0

and the parameter r

extracted from both the external key of 512 bits and the plain image’s characteristics as follows: 1. Extract two numbers from the last 128 bits of the external key and the plain image’s characteristics using the following equations:

64 +

k=1 ki

64



1 512 (k49 ⊕ · · · ⊕ k56 )

,1

mod1

(33)

1 512 (k57 ⊕ · · · ⊕ k64 ) ,1

mod1

(34)

2. Iterate the LTS chaotic map for 500 times to avoid the transient effect, continue the iteration of the chaotic map for 512 times to get the sequence {S K } and discretize it: 

  Sk = {Sk } × 1015  mod 2

(35)

Then, the second subphase of diffusion is described as follows: 1. Quadtree decomposition strategy with two level of decomposition is applied. 2. In the first level, the image is decomposed into 4 sub-images, each one is a quarter size of the original image and we denote them as C 0 , C 1 , C 2 and C 3 . 3. The sub-images of (C 0 )0 , (C 1 )0 , (C 2 )0 and (C 3 )0 form the first configuration of 4th order RMCA, to gather with the generated three subkeys as described is Sect. 3.2 and the evolution of cellular automata is applied according to Eq. (10). 4. The resulted 4 sub-images are denoted as (C 0 )1 , (C 1 )1 , (C 2 )1 and (C 3 )1 , the last three subimages ((C 1 )1 , (C 2 )1 and (C 3 )1 ) are directly saved to form the final ciphered image C. 5. In the second level, the top left corner of (C 0 )1 is decomposed again to form (C 0 )10 , (C 1 )11 , (C 2 )12 and (C 3 )13 as another configuration of 4th order RMCA, to gather with the generated three sub-images, following the 3.2 subsection and the evolution of cellular automata is applied according to Eq. (10). 6. The resulted 4 sub-images are denoted (C 0 )20 , (C 1 )21 , (C 2 )22 and (C 3 )23 , and they are combined to form the top left corner of (C 0 )1 which is saved directly to form the complete final ciphered image.

123

A. Souyah, K. M. Faraoun

3.3.3 The decryption process

Table 1 Comparison of key space between the proposed scheme and other cryptosystems

In order to decrypt the ciphered-image C, Wh value is needed otherwise the decryption can’t be done successfully. For this reason, the value val2 is included on the plain image at a secret local before encryption. The encryption routine is applied to all plain image’s pixels except one pixel in where the val2 value is added, its location is deduced based on the secret key using Eqs. (14), (15), and Wh value is recalculated using Eq. (25), after all the used chaotic key-streams/sub-keys are regenerated using LTS chaotic map with the correct secret key and Wh value. The decryption process is as equal as the encryption one, in which it is performed in the reverse order keeping the same used keys, and it is as follows: Firstly, the second diffusion subphase is defined by the inverse cellular automata of (12). Secondly, the reverse of the first diffusion subphase should be applied, and it is defined as follows:

Cryptosystem

Key space

The proposed scheme

2520

Ref. [42]

2256

Ref. [21]

2280

Ref. [18]

2128

Ref. [22]

1044 × 5

Ref. [43]

>2128

Ref. [25]

1084

1. After transforming the resulted image of the previous sub phase from its two-dimensional to onedimensional vector format C = {C1 , C2 , . . ., CM×N }. 2. Implement the reverse operations from the last pixel to the first as: pi = Ci ⊕ (ki + Ci−1 ) mod 256 ⊕ S

(36)

S = S + pi

(37)

where S = 0, pi is the ith recovered plain pixel, Ci is the ith cipher pixel, ki is a sequence generated using the skew tent map, and Ci−1 is the previously cipher pixel. The index i is performed from the last pixel of M × N − 1 to the first one of 0. Finally, the confusion phase is governed by 1D LTS chaotic map, and the reverse operation of permutation should be carried out to obtain the original plain image.

4 Performance and security analysis The robustness of the proposed scheme is shown in this section by means of commonly used security analysis of secret key size and its sensitivity, information entropy analysis, histogram analysis, correlation analysis, differential analysis, classical attacks analysis besides to the performance analysis.

123

4.1 Secret key space analysis A good cryptosystem is one in which the best attack is an exhaustive search (i.e., brute force attack) [45]. In the proposed scheme, the key depends on both confusion and diffusion phases. The keys are built using: (1) the initial values of 1D LTS chaotic map which are the initial condition X 0 ∈ [0, 1] and the parameter r ∈ (0, 4] that are extracted from val 2 of one byte (i.e., 8 bits) and the external key, and (2) the external used secret key k of 512 bits. So, the total key space is calculated as: 28 × 2512 = 2520 which makes the aforementioned attack infeasible in practical time. Table 1 shows a comparison of key space between the proposed scheme and other proposals in the scientific literature.

4.2 Secret key sensitivity analysis A good cryptosystem is one in which a small modification in the secret key, can cause significant modifications in the ciphered image, making the well verification of the confusion property. Sensitivity to the secret key is shown in Fig. 3, Fig. 3a is the cipheredimage (C1 ) using the key (X0 = 0.43, r = 3.57, k), while Fig. 3b is a ciphered-image (C2 ) using the key (X0 = 0.43 + δ, r = 3.57, k), δ is a very small value called the perturbing value [22], in our work, it is equal to 10−15 , and in the shown figures it is the only modified value and all the remained parameters of the key are kept unchanged. The percentage of difference is calculated between the two obtained ciphered-images C1 and C2 using the following equation:

Chaos-memory cellular automata and weighted histogram Fig. 3 Shows the key sensitivity experiment. a Encrypted using key (X 0 = 0.43). b Encrypted using key (X 0 = 0.43 + δ). c Decrypted with right key. d Decrypted with the wrong key

⎛

⎞ L L

1 diff = ⎝ sg (C1 [i, j] − C2 [i, j])⎠ 512 ∗ 512 i=1 j=1  1 if x = 0 ∗100 where sg (x) = (38) 0 otherwise

Similarly, the experiment is extended to cover the decryption process. Fig. 3c represents the decrypted image with the right key, while Fig. 3d represents the decrypted image using the key (X0 = 0.43 + δ, r = 3.57, k). Table 2 shows the sensitivity to secret keys, in which a minor modification is applied to just one key at a time, in the initial key set ρi , and the remaining keys are kept unchanged. From the obtained results in Table 2, we deduce that our proposed scheme has a high level of key sensitivity.

4.3 Information entropy analysis Shannon’s entropy is one of the most used measurements of randomness. It represents the degree of uncertainty associated with a random variable. The entropy H (m) of a source m is given by: H (m) = −

L

P (m i ) log2 P (m i )

(39)

n=1

where L represents the number of dissimilar symbols emitted by source m, and P(m i ) is the probability of symbol’s m i occurrence in m. The entropy is expressed in bits. The obtained results of the entropy test applied to different ciphered images, that are shown in Table 3, are very nearby to the theoretical value (i.e., the truly random source entropy which is 8), indicating the unpredictability and the randomness of the proposed

123

A. Souyah, K. M. Faraoun Table 2 Key sensitivity test results Secret keys 

Difference rates (%) 

ρ1 X 0 = X 0 + δ   ρ2 X 0 = X 0 − δ  

ρ3 r = r + δ   ρ4 r = r − δ

Boat

Lena

Pepper

Lake

99.5971

99.6070

99.6189

99.6101

99.5892

99.6128

99.6170

99.6017

99.6166

99.6147

99.6185

99.5914

99.5914

99.6036

99.6166

99.5861

ρ5 (alter the 1st bit of k)

99.6033

99.6156

99.6188

99.5966

ρ6 (alter the 128th bit of k)

99.6074

99.6067

99.6157

99.6022

ρ7 (alter the last bit of k)

99.6144

99.5937

99.6160

99.6001

Table 3 Shannon’s entropy test results Image

Plain image

Ciphered image

Boat

7.2154

7.9993

Lena

7.4183

7.9992

Pepper

7.5838

7.9992

Lake

7.4762

7.9993

Table 4 Comparison of the entropy value on Lena image Cryptosystem

Entropy value

The proposed scheme

7.9992

Ref. [21]

7.9992

Ref. [22]

7.9696

Ref. [44]

7.9973

Ref. [24]

7.9970

scheme’s output. Table 4 compares the entropy results on Lena grayscale image using the proposed scheme and some other proposals in the scientific literature.

it is clear that the histogram of the ciphered image (b) uniformly distributed and quite different from its corresponding of plain image (a). Hence, the proposed scheme is in the measure of defeating statistical attacks.

4.5 Correlation analysis One important feature of an image is its high redundancy between its adjacent pixels. The intention of each secure cryptosystem is to decrease this relationship between adjacent pixels, by making it as near as possible to the theoretical value of zero that reflects the sufficient randomness of the ciphered image, and its independency from the corresponding plain image. To measure the correlation of adjacent pixels in vertical, horizontal and diagonal directions, the following procedure is applied: We select randomly 10,000 pairs of adjacent pixels in every aforementioned direction from the plain image and its corresponding ciphered image. The correlation coefficient is calculated using the following equation: cov (x, y) (40) √ D (x) × D (y) where cov (x, y) = E [{x − E (x)} {y − E (y)}] ,

ρx y = √ 4.4 Histogram analysis

1 × xi and N N

Image histogram is one of the commonly utilized analysis standards for image. It is characterized by the distribution of image’s pixels by plotting the number of pixels in each intensity level. To defeat statistical attacks, a relationship of dissimilarity should depict both the plain image and its corresponding ciphered image. To do the experiment, we have calculated and analyzed the histogram of the plain image boat of size 512 × 512 and its corresponding ciphered image. From the Fig. 4,

123

E (x) =

k=i

1 {xi − E [x]} × N N

D (x) =

(41)

k=i

where x and y are the grayscale values of two neighboring pixels in the image, and N is the total number of the adjacent pixels selected from the image to measure the correlation. Table 5 gives the obtained corre-

Chaos-memory cellular automata and weighted histogram

Fig. 4 Histogram test of Boat (512 × 512) image. a Plain image. b Ciphered image

Table 5 Correlation test results Image

Plain

Ciphered

Horizontal

Vertical

Diagonal

Horizontal

Vertical

Diagonal

Boat

0.9673

0.9868

0.9555

0.0059

0.0037

Lena

0.9707

0.9923

0.9687

0.0010

0.0054

0.0056

Pepper

0.8893

0.9734

0.8703

0.0112

0.0065

0.0056

Lake

0.9549

0.9729

0.9351

0.0034

0.0094

0.0065

−0.0062

Fig. 5 Correlation diagrams of plain/ciphered image (boat): a horizontal, b vertical and c diagonal

123

A. Souyah, K. M. Faraoun

lation coefficient values of the chosen used images for the experiment. So, obviously a negligible correlation coefficient, which is very nearby to the theoretical value of zero between neighboring pixels of the plain and that of the ciphered image is shown in Fig. 5. Therefore, the plain image and its corresponding ciphered image are totally different, that’s mean a high randomness of the ciphered image is found using the proposed scheme.

4.6 Differential analysis The role of differential attack is the deduction of how a small change on the plain image can greatly affect the ciphered image. The attackers select arbitrary plain images having a minor difference of one bit, after encrypting these images using the proposed scheme, they try to gain some useful information from the difference between the plain image and its matching ciphered image. A good cryptosystem is one in which has a sufficient immunity against this kind of attacks, by the satisfaction of more than 50 % of change appear on the ciphered image corresponding to a minor change on the matching plain image. This can be observed by the commonly used measurements i.e., number of pixel change rate (NPCR) and unified averaged changing intensity (UACI), which are calculated using the following equations of 5 and 6, respectively. ⎞ ⎛ N M

1 (42) D [i, j]⎠ · 100 % NPCR = ⎝ N .M i=1 j=1 ⎛ ⎞ N M

|C1 [i, j] − C2 [i, j]| 1 ⎠ · 100 % UACI = ⎝ N .M 255

Table 6 NPCR and UACI tests for ciphered image Image

NPCR (%)

UACI (%)

Boat

99.6086

33.4453

Lena

99.6070

33.5009

Pepper

99.6017

33.4288

Lake

99.6177

33.4353

Average for all images

99.6087

33.4525

Table 7 Comparison of the NPCR and UACI values on Lena image Cryptosystem

NPCR (%)

UACI (%)

The proposed scheme

99.60

33.50

Ref. [44]

99.62

33.51

Ref. [22]

99.46

33.21

Ref. [39]

99.61

33.45

Ref. [27]

99.60

33.46

Ref. [24]

99.58

33.25

Table 8 The decryption error test Image

Decryption Error

Boat

0.0022

Lena

0.0049

Pepper

0.0030

Lake

0.0050

4.7 Chosen/known plain image attack

Most of the proposed image encryption schemes have been broken with chosen/known plain image attacks despite of their competitive statistical results of high i=1 j=1 (43) NPCR and UACI [35–38]. In this paper, we take into account to increase more the security of our scheme to where N and M are the image’s width and height, defeat these powerful attacks using the random pixel respectively, C1 [i, j] is the ciphered image of the origoverwriting mechanism, in which a new measure of inal plain image, and C2 [i, j] is after one bit alteration, the plain image’s weighted histogram (Wh) value is for every (i, j) position if C1 [i, j] = C2 [i, j], then inserted on the plain image at a secret local (one D[i, j] = 0, else D[i, j] = 1. From the shown results randomly chosen pixel). This mechanism is used to in Table 6, it is clear how much is the sensitivity of our further ensure the immunity of the proposed scheme proposed scheme to plain image minor change which to known/chosen plain image attacks (CPA secure) reflects the good chaotic behavior of both LTS chaotic that conducts to a random-like generating chaotic system and cellular automata. Table 7 compares the sequences. So, no information can be obtained by NPCR and UACI results on Lena grayscale image using cryptanalyzers since each encryption is both plain the proposed scheme and some other proposals in the image/secret key related. In addition, one round of scientific literature. permutation–diffusion is enough to have the aforemen-

123

Chaos-memory cellular automata and weighted histogram Table 9 The runtime performance test Plain image Size

Encryption time (ms) Ref. [18]

Ref. [41]

Ref. [25]

Proposed

256 × 256

189

120

178

109

512 × 512

758

475

663

390

3097

1951

3142

1482

1024 × 1024

tioned competitive statistical results, for this reason, our proposed scheme can resist a divide and conquer attack [28].

4.8 Decryption error It is highly recommended in secure communication applications as military, biometric systems, etc, that the difference between the original plain image and its recovered decrypted one should be very low (negligible) [40]. In [25], a random pixel insertion is applied to the plain image for realizing the task of having different encrypted images in every execution time for the same plain image and the same used keys and after all the plain image’s pixels passed to the encryption routine; therefore, the recovered decrypted image has a high error of about 0.2 % comparing it with its matching plain image. Another work in [40], proposed to add secret information (Z value) to the ciphered image for the reason of its recovering in the decryption process. In this work, and for the same reason of recovering the added secret information (Wh value), we alter one pixel from the original plain image and use it for inserting the secret information of Wh value. Despite [25], the encryption routine is applied to the entire plain image’s pixels except one pixel (where Wh value is added); therefore, the recovered image is extremely identical to the original plain image making the decryption error very low. Table 8 shows the found results of the decryption error which is calculated using the following equation [40]: ⎞ ⎛ N M

1 Q (i, j)⎠ · 100 % DErr = ⎝ N .M i=1 j=1  1 if P (i, j) = D (i, j) (44) where Q (i, j) = 0 otherwise where M is the width of the image, N is its height, P is the original plain image and D is its decrypted image.

4.9 Performance analysis Besides to security consideration, some other issues on an image encryption scheme are also important, including the running speed, especially for real-time Internet applications. The implementation of the proposed protocol was realized using C programming language, and the experiment was performed using Intel(R) Core (TM)i7-CPU of 3 Ghz with 8 Gb of memory. Table 9 shows the test results applied to grayscale images of different sizes. 5 Conclusion In this paper, a new scheme for enciphering digital images is suggested. It is based on the combination of chaotic map and reversible memory cellular automata and follows the permutation–diffusion architecture under one round. This method is mainly based on the iterative application of two phases: The confusion phase which is governed by bit-level permutation incorporated with 1D LTS chaotic system, and diffusion phase which is ruled by means of 1D LTS chaotic system and 2D reversible cellular automata with memory. The notable feature of the proposal is its capacity of resisting chosen/known plain image attacks (CPA secure) that leads to random-like generating keystreams. The proposed scheme satisfies all the searched properties for a secure cryptosystem of confusion, diffusion, large key space, resistance to entropy, differential, chosen/known plain image attacks besides to its competitive speed that make its suitability to be used in practical image encryption. References 1. Ahamd, J., Hwang, S.O., Ali, A.: An experimental comparison of chaotic and non-chaotic image encryption schemes. Wirel. Pers. Commun. 84(2), 901–918 (2015)

123

A. Souyah, K. M. Faraoun 2. Peja´s, J., Skrobek, A.: Chaos-based informationsecurity. In: Handbook of Information and Communication Security, pp. 91–128. Springer, Berlin (2010) 3. Carmen, P.-L., Ricardo, L.-R.: Notions of chaotic cryptography: sketch of a chaos based cryptosystem. In: Applied Cryptography and Network Security, pp. 267–294 (2012) 4. Wang, Y., Wang, K.-W., Liao, X., et al.: A new chaos-based fast image encryption algorithm. Appl. Soft Comput. 11(1), 514–522 (2011) 5. Zhu, Z., Zhang, W., Wong, K., et al.: A chaos-based symmetric image encryption scheme using a bit-level permutation. Inf. Sci. 181(6), 1171–1186 (2011) 6. Zhang, W., Wong, K., Yu, H., et al.: A symmetric color image encryption algorithm using the intrinsic features of bit distributions. Commun. Nonlinear Sci. Numer. Simul. 18(3), 584–600 (2013) 7. Chen, J., Zhu, Z., Yu, H.: A fast chaos-based symmetric image cryptosystem with an improved diffusion scheme. Opt. Int. J. Light Electron Opt. 125(11), 2472–2478 (2014) 8. Fu, C., Chen, J., Zou, H., et al.: A chaos-based digital image encryption scheme with an improved diffusion strategy. Opt. Express 20(3), 2363–2378 (2012) 9. Zhang, Y., Xiao, D.: An image encryption scheme based on rotation matrix bit-level permutation and block diffusion. Commun. Nonlinear Sci. Numer. Simul. 19(1), 74–82 (2014) 10. von Neumann, J., Burks, A.W.: Theory of self-reproducing automata. University of Illinois Press, Urbana (1966) 11. Wolfram, S.: A New Kind of Science. Wolfram Media, Champaign (2002) 12. Wolfram, S.: Cryptography with cellular automata. In: Advances in Cryptology—CRYPTO’85 Proceedings, pp. 429–432. Springer, Berlin (1986) 13. Chatzichristofis, S.A., Mitzias, D.A., Sirakoulis, G.C., et al.: A novel cellular automata based technique for visual multimedia content encryption. Opt. Commun. 283(21), 4250– 4260 (2010) 14. Chen, R.-J., Lai, J.-L.: Image security system using recursive cellular automata substitution. Pattern Recognit. 40(5), 1621–1631 (2007) 15. Chen, R.-J., Horng, S.-J.: Novel SCAN-CA-based image security system using SCAN and 2-D von Neumann cellular automata. Signal Process. Image Commun. 25(6), 413–426 (2010) 16. Abdo, A.A., Lian, S., Ismail, I.A., et al.: A cryptosystem based on elementary cellular automata. Commun. Nonlinear Sci. Numer. Simul. 18(1), 136–147 (2013) 17. Jin, J.: An image encryption based on elementary cellular automata. Opt. Lasers Eng. 50(12), 1836–1843 (2012) 18. Mohamed, F.K.: A parallel block-based encryption schema for digital images using reversible cellular automata. Int. J. Eng. Sci. Technol. 17(2), 85–94 (2014) 19. Faraoun, K.M.: A genetic strategy to design cellular automata based block ciphers. Expert Syst. Appl. 41(17), 7958–7967 (2014) 20. Del Rey, A.M., Sánchez, G.R., De La Villa Cuenca, A.: Encrypting digital images using cellular automata. In: Hybrid Artificial Intelligent Systems, pp. 78–88. Springer, Berlin (2012)

123

21. Wang, X., Luan, D.: A novel image encryption algorithm using chaos and reversible cellular automata. Commun. Nonlinear Sci. Numer. Simul. 18(11), 3075–3085 (2013) 22. Bakshandeh, A., Eslami, Z.: An authenticated image encryption scheme based on chaotic maps and memory cellular automata. Opt. Lasers Eng. 51(6), 665–673 (2013) 23. Watada, J., et al.: DNA computing and its applications. In: Eighth International Conference on Intelligent Systems Design and Applications, 2008. ISDA’08, pp. 288–294. IEEE (2008) 24. Wang, X., Liu, L., Zhang, Y.: A novel chaotic block image encryption algorithm based on dynamic random growth technique. Opt. Lasers Eng. 66, 10–18 (2015) 25. Zhou, Y., Bao, L., Chen, C.P.: A new 1D chaotic system for image encryption. Signal Process. 97, 172–182 (2014) 26. Del Rey, A.M., Sánchez, G.R., De La Villa Cuenca, A.: A protocol to encrypt digital images using chaotic maps and memory cellular automata. Log. J. IGPL jzv013 23(3), 485– 494 (2015) 27. El Assad, S., Farajallah, M.: A new chaos-based image encryption system. Signal Process. Image Commun. 41, 144–157 (2016) 28. Li, C., Li, S., Lo, K.-T.: Breaking a modified substitution– diffusion image cipher based on chaotic standard and logistic maps. Commun. Nonlinear Sci. Numer. Simul. 16(2), 837– 843 (2011) 29. Toffoli, T., Margolus, N.H.: Invertible cellular automata: a review. Phys. D 45(1), 229–253 (1990) 30. Huang, X., Ye, G.: An image encryption algorithm based on hyper-chaos and DNA sequence. Multimed. Tools Appl. 72(1), 57–70 (2014) 31. Hermassi, H., Belazi, A., Rhouma, R., et al.: Security analysis of an image encryption algorithm based on a DNA addition combining with chaotic maps. Multimed. Tools Appl. 72(3), 2211–2224 (2014) 32. Jain, A., Rajpal, N.: A robust image encryption algorithm resistant to attacks using DNA and chaotic logistic maps. Multimed. Tools Appl. 75(10), 5455–5472 (2016) 33. Zhen, P., Zhao, G., Min, L., et al.: Chaos-based image encryption scheme combining DNA coding and entropy. Multimed. Tools Appl. 75(11), (2015). doi:10.1007/ s11042-015-2573-x 34. Kulsoom, A., Xiao, D., Abbas, S.A., et al.: An efficient and noise resistive selective image encryption scheme for gray images based on chaotic maps and DNA complementary rules. Multimed. Tools Appl. 75(1), 1–23 (2016) 35. Kabirirad, S., Hajiabadi, H.: Cryptanalysis of an authenticated image encryption scheme based on chaotic maps and memory cellular automata. IACR Cryptol. ePrint Arch. 2015, 326 (2015) 36. Li, C., Zhang, L.Y., Ou, R., et al.: Breaking a novel colour image encryption algorithm based on chaos. Nonlinear Dyn. 70(4), 2383–2388 (2012) 37. Wang, Y., Lei, P., Yang, H., et al.: Security analysis on a color image encryption based on DNA encoding and chaos map. Comput. Electric. Eng. 46, 433–446 (2015) 38. Zhang, Y.: Cryptanalysis of a novel image fusion encryption algorithm based on DNA sequence operation and hyperchaotic system. Opt. Int. J. Light Electron Opt. 126(2), 223– 229 (2015)

Chaos-memory cellular automata and weighted histogram 39. Norouzi, B., Seyedzadeh, S.M., Mirzakuchaki, S., et al.: A novel image encryption based on row-column, masking and main diffusion processes with hyper chaos. Multimed. Tools. Appl. 74(3), 781–811 (2013) 40. Murillo-Escobar, M.A., Cruz-Hernández, C., AbundizPérez, F., et al.: A RGB image encryption algorithm based on total plain image characteristics and chaos. Sig. Process. 109, 119–131 (2015) 41. Kanso, A., Ghebleh, M.: A novel image encryption algorithm based on a 3D chaotic map. Commun. Nonlinear Sci. Numer. Simul. 17(7), 2943–2959 (2012)

42. del Rey, A.M., Pastora, J.L.H., Sánchez, G.R.: 3D medical data security protection. Expert Syst. Appl. 54, 379–386 (2016) 43. Yavuz, E., Yazici, R., Kasapba¸si, M.C., et al.: A chaos-based image encryption algorithm with simple logical functions. Comput. Electric. Eng. 2015. (in press) 44. Xu, L., Li, Z., Li, J., et al.: A novel bit-level image encryption algorithm based on chaotic maps. Opt. Lasers Eng. 78, 17– 25 (2016) 45. Knudsen, L.R., Robshaw, M.: The Block Cipher Companion. Springer Science & Business Media, Berlin (2011)

123