Security analysis of image encryption based on two-dimensional chaotic maps and improved algorithm

Abstract

The article proposes a new algorithm to improve the security of image encryption based on two-dimensional chaotic maps. Chaotic maps are often used in encrypting images. However, the encryption has periodicity, no diffusion, and at the same time, the real keys space of encryption are fewer than the theoretical keys space, which consequently results in potential security problems. Thus, this article puts forward several ways to solve the problems including adding diffusion mechanism, changing the design of keys and developing a composite encryption system. It designs an algorithm for the version B of the discretized baker map, which is one of the most prevalent chaotic maps, based on which a new image encryption is proposed to avoid the above problems. The simulation results show that the new encryption algorithm is valid and the result can be applied to other two-dimensional chaotic maps, such as the cat map.

Keywords

chaotic map / baker map / image encryption

Introduction

Chaos has been widely used in cryptography in recent years [1–5]. However, some actual digital chaos systems face the problem of degradation dynamics [6,7]. The two-dimensional chaotic maps can ‘stretch-and-fold’ images by use of the natural features of images. Small changes in keys for a plain image can diffuse to everywhere in an encrypted image. At the same time, the analysis of keys is very difficult because there are too many combinations of encryption. Typical chaotic maps used for image encryption include the cat map, the baker map, the standard map, the tent map [8,9], etc. In Ref. [8], Fridrich proposes a class of invertible encryption systems based on the baker map. It uses a two-dimensional chaotic map to permutate the position of pixels. The permutations induced by the baker map behave as typical random permutations. The encryption has good diffusion properties with respect to the plain image and the keys. However, the baker map does not have a simple formula and the keys are limited by the size of the image. In Refs. [10,11] new image encryption schemes are constructed based on an extended three-dimensional chaotic baker map and the cat map.

There are similar characteristics in two-dimensional chaotic maps. With the two-dimensional baker map, the article analyzed security of image encryption and obtained factors for weakened encryption. Then the article designs a new image encryption based on the discretized baker map to improve security. The simulation results show that the new encryption algorithm is valid.

Two-dimensional chaotic map

Image pixels can be arranged arbitrarily and any pixel can be inserted between adjacent pixels. The process of this arrangement can be regarded as the stretch-and-fold of images. The encryption of the two-dimensional chaotic map uses this feature. The cat map is a geometric transformation process. The line map stretches all the pixels to form a straight line, and then folds them according to laws. After the process the pixels in plain image are randomly distributed in the encrypted image and the adjacent pixels are no longer relevant. The baker map is one of the major chaotic maps. It stretches the image horizontally, and then folds it vertically. Repeating this process, the positions of all the pixels of the plain image are changed.

Assume a square image consisting of N×N pixels. It can be divided into k rectangle-shaped parts horizontally whose size is [N_i–1,N_i]×]0,1] (here i=\mathrm{1},\mathrm{2},...,k) and N_i=P₁+P₂+…+P_i (here N₀=0, P_i is the rectangular width and i≤k). Thus to any (x, y) in the parts ]N_i–1, N_i]×]0, 1], the formula of the baker map is

B(x^{\prime },y^{\prime })=A\left({\displaystyle \frac{\mathrm{1}}{P_i}}(x-N_i),P_{i}y+N_i\right),

where i=\mathrm{1},\mathrm{2},...,k.

To encrypt the image the baker map must be discretized. For different keys, the discretized baker map is divided into two versions: version A and version B. When the map is of version A, every part of the keys is the divisor of the image size. The formula of version A is

B(x^{\prime },y^{\prime })=A\left({\displaystyle \frac{N}{n_i}}(x-N_i)+y\mathrm{mod}{\displaystyle \frac{N}{n_i}},{\displaystyle \frac{n_i}{N}}\left(y-y\mathrm{mod}{\displaystyle \frac{N}{n_i}}\right)+N_i\right),

where

Take an image with 8×8 for example. If the Key = (2, 2 ,4), the process of encryption can be seen in Fig. 1.

When part of the keys is not the divisor of the image size, the encryption uses version B of the discretized baker map. In Ref. [8], version B has no common formula. Taking an image with 8×8 for example. If the Key = (3, 5), encryption can be seen in Fig. 2.

The article first gives an algorithm for version B of the baker map. If the image consists of N×N pixels, the pixel (x, y) in the image is mapped to (x^{\prime },y^{\prime }) by the baker map.

Here, \mathrm{Key}=(n_{\mathrm{1}},n_{\mathrm{2}},...,n_k)(N=n₁+n₂+…+ n_k, i=\mathrm{1},\mathrm{2},...,k), n_i is not the divisor of N.

If we suppose

m=\mathrm{floor}\left({\displaystyle \frac{(x-N_i)+(N-y)\times n_i-\mathrm{1}}{N}}\right),

d_n=\mathrm{floor}\left({\displaystyle \frac{N-S_n}{n_k}}\right)+\mathrm{1},

S_{n+\mathrm{1}}=d_n\times n_i+S_n-N(S_{\mathrm{1}}=\mathrm{0},\mathrm{1}\le n\le n_i).

First, we have y^{\prime }=N-N_i-m_i-\mathrm{1}. Then

1) if x-N_i\le n_i-S_{m+\mathrm{1}}, when x-N_i\le n_i-S_{m+\mathrm{2}}, we have

x^{\prime }=(x-N_i-\mathrm{1})\times d_{m+\mathrm{1}}+N-y-{\displaystyle \sum _{i=\mathrm{1}}^m{d}_m};

when x-N_i>n_i-S_{m+\mathrm{2}}, we have

x^{\prime }=(n_i-S_{m+\mathrm{2}})\times d_{m+\mathrm{1}}+[x-(n_i-S_{m+\mathrm{2}})-\mathrm{1}]\times (d_{m+\mathrm{1}}-\mathrm{1})+N-y-{\displaystyle \sum _{i=\mathrm{1}}^m{d}_m};

2) if x-N_i>n_i-S_{m+\mathrm{1}}, when x-N_i\le n_i-S_{m+\mathrm{2}},we have

x^{\prime }=(n_i-S_{m+\mathrm{1}})\times d_{m+\mathrm{1}}+[x-(n_i-S_{m+\mathrm{1}})-\mathrm{1}]\times (d_{m+\mathrm{1}}+\mathrm{1})+N-y-{\displaystyle \sum _{i=\mathrm{1}}^m{d}_m+\mathrm{1}};

when x-N_i>n_i-S_{m+\mathrm{2}},S_{m+\mathrm{2}}\ge S_{m+\mathrm{1}}, we have

x^{\prime }=(n_i-S_{m+\mathrm{2}})\times d_{m+\mathrm{1}}+(S_{m+\mathrm{2}}-S_{m+\mathrm{1}})\times (d_{m+\mathrm{1}}-\mathrm{1})+[x-(n_i-S_{m+\mathrm{1}})-\mathrm{1}]\times d_{m+\mathrm{1}}+N-y-{\displaystyle \sum _{i=\mathrm{1}}^m{d}_m+\mathrm{1}};

when we have

x^{\prime }=(n_i-S_{m+\mathrm{1}})\times d_{m+\mathrm{1}}+(S_{m+\mathrm{1}}-S_{m+\mathrm{2}})\times (d_{m+\mathrm{1}}+\mathrm{1})+[x-(n_i-S_{m+\mathrm{2}})-\mathrm{1}]\times d_{m+\mathrm{1}}+N-y-{\displaystyle \sum _{i=\mathrm{1}}^m{d}_m+\mathrm{1}}.

The algorithm by C programming language is as follows:

for(j = 1; j <n_k; j ++)

{

if(n_k – 1<S_n+1)

m=1;

else

m=0;

if(n_k – 1<S_n+2)

n=1;

else

n=0;

for(i=1–m;i≤d_n+1–n;i++)

{

x=N–( i–1)–{\displaystyle \sum _{i=1}^n{d}_n};

y=N–N_i–m_i–1;

}

}

In Ref. [11], there is a formula of version B of the baker map. However, the direction of the map is different from the map in Ref. [8].

The keys space in version A of the baker map can be seen in Table 1.

The keys space of version B is K(N)=2^N–1. Obviously, it is much bigger than that of version A.

Security analysis of encryption of two-dimensional chaotic map

Because there are too many possible combinations of substitution algorithms and replacement algorithms of the two-dimensional chaotic map, analysis of the keys is very difficult. Currently, the ways of attacking keys are very few. However, the encryptions by the two-dimensional chaotic map inherently have potential security problems.

1) Encrypting an image by the two-dimensional chaotic map is only a process of permutation. Because the size of the image is limited, the process is cyclical. Acting as the baker map, pixels will first be divided by the keys. Then it stretches the image horizontally and folds it vertically. The cat map is a geometric transformation process. The line map stretches all the pixels to form a straight line, and then folds them according to laws. When the number of the transformation by these two-dimensional maps is small, the pixels of the image can be very confusing. However, because the image is a group of pixels, the combinations of pixels are limited. According to the feature of the system, the encrypted image can be restored to the plain image by mapping. Thus, if the encryption algorithm is known, an encrypted image can be chosen arbitrarily. By mapping the encrypted image and repeating the process, the plain image may be restored.

2) The encryption of the two-dimensional chaotic map is a technique without information loss. It only changes the position of pixels instead of the value of the pixels. Therefore, the encryption cannot resist cipher-text-only attack. Before encryption, it can choose a pixel (x, y) and then change its value to (x^{\prime },y^{\prime }), which is a special act as (0, 0). After encryption it can find pixels whose value is (x^{\prime },y^{\prime }). Repeating the process, it can validate a group of relationships between the pixels in the plain image and the ones in the encrypted image. Storing those relationships and creating a table. Using the table, the encrypted image may be restored to the plain image without keys.

3) The actual keys space is far less than the theoretic one. It can be seen in Fig. 3 that most of the plain image can be restored even with error keys. This is because images have visibility, and their part also has visibility and can be identified. Taking the baker map for example, in encryption, the image will be a division. If the difference between the parts of the plain image is little, the parts in the encrypted image are also similar, and thus it can attack the encrypted image by different keys.

To improve the security of encryption of the two-dimensional chaotic map, several improvements should be made.

1) Because the combinations of encryption are limited, the keys space can be enlarged and the number of iterations reduced to ensure the security of encryption.

The methods of adding keys space uses the general formula, increases the length of keys and takes a part of the keys to encrypt the image, and designs a composite encryption system, uses random sequence to modify the keys before encryption.

2) Confuse the value of pixels and change the demographic characteristics of the encrypted image. One simple method is using a little XOR function: (x^{\prime },y^{\prime })=(x,y)\oplus (i\times j)mod N. By the function, the histogram of the encrypted image is uniformly distributed. Another method is using XOR with a random sequence.

3) Designing a composite image encryption system can improve the security of encryption with several chaotic maps. Two classes of methods are presented. One is changing the value of pixels. Use the baker map and cat map to encrypt the image in order. The keys space of encryption can be enlarged. The other method is changing the pixels with some chaotic maps. The encryption might resist the ciphered-text attack and avoid regional analysis.

4) Develop the two-dimensional map to be a higher-dimensional map. After that, the speed of encryption is higher and encryption is more difficult to attack. In Ref. [10], the two-dimensional cat map is developed to a three-dimensional map. In Ref. [11], the baker map is also developed to be a three-dimensional one. These three-dimensional maps are proved to have an encryption that is faster with larger keys space.

Improved algorithm of encryption with two-dimensional chaotic map

Some chaotic maps are used, including PWLCM, logistic map and baker map, to design a composite image encryption system. Using the logistic map,

(1)X_{n+\mathrm{1}}=a\times X_n\times (\mathrm{1}-X_n),

here,a\in (\mathrm{0},\mathrm{4}],X_n\in (\mathrm{0},\mathrm{1}),n=\mathrm{1},\mathrm{2},\mathrm{3.}

First, design an encryption algorithm. Suppose the image size is m×n, with 256 levels of gray, where the \mathrm{Key=}(n_{\mathrm{1}},n_{\mathrm{2}},...,n_k,...,n_{uk}). Key₁ and Key₂ are parts of the Key respectively. The initial values of the logistic map are a, N. The whole algorithm includes two steps.

The first step: according to \mathrm{Ke}{\mathrm{y}}_{\mathrm{1}}=(n_{\mathrm{1}},n_{\mathrm{2}},...,n_k),

1) Calculate X_{0i}=n_i/m(i=\mathrm{1},\mathrm{2},...,k)(two significant digits);

2) By Eq.(1), it can get a chaotic sequence with X_0i, a. Then take a subsequence S_i=(a_1,a_2,...,a_{i\times n})from the sequence from the beginning of the N whose length is n_i×n.

3) Calculation:

S_i\Rightarrow S_i^{\prime }

. Here, S_i^{\prime } is a sequence that chooses three digits after the decimal point from the sequence S_i and mods with 256. Thus \mathrm{0}\le S_i^{\prime }\le \mathrm{256.}

4) Set n_i as the keys in encryption with the baker map. Then take the value of pixels XOR with S_i^{\prime } one by one.

The second step: encrypt the image with k keys in \mathrm{Ke}{\mathrm{y}}_{\mathrm{2}}=(n_{k+\mathrm{1}},n_{k+\mathrm{2}},...,n_{\mathrm{2}k},...,n_{uk}).

The above algorithm is applicable to other chaotic maps.

Use the encryption algorithm to encrypt a Lena image. Suppose the image size is 256×256, the process can be seen in Fig. 4. The keys of the encryption is Key₁ =(7, 74, 13, 9, 7, 19, 4, 31, 4, 3, 63, 5, 2, 11, 3, 1), m=1, n=10, a=4, N=1000. To test the sensitivity of keys, error keys are used to attack the encrypted image.

Conclusions

The article first analyzed the security of encryption with a two-dimensional map. Then it proposes some methods to improve it to avoid features that weaken security.

A new encryption algorithm is designed for a composite encryption system. In the encryption, the values of pixels are changed and the keys spaces are enlarged. With the baker map, the algorithm solves the problem of adopting two keys of little difference in encryption. The improved algorithm is applicable to all chaotic maps.

The encryption with chaotic maps is simple and effective and it is easy for hardware implementation.

References

[1] Schneier B. Applied Cryptography – Protocols, Algorithms, and Source Code in C. 2nd ed. New York: John Wiley & Sons, Inc., 1996

[2] Shannon C E. Communication theory of secrecy systems. The Bell System Technical Journal, 1949, 28(4): 656–715

[3] Matthews R. On the derivation of a ”chaotic“ encryption algorithm. Cryptologia, 1989, 13(1): 29–42

[4] Dachselt F, Schwarz W. Chaos and cryptography. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 2001, 48(12): 1498–1509

[5] Lian S G, Sun J S, Wang J W, Wang Z Q. A chaotic stream cipher and the usage in video protection. Chaos, Solitons & Fractals, 2007, 34(3): 851–859

[6] Wheeler D D. Problems with chaotic cryptosystems. Cryptologia, 1989, 13 (3): 243–250

[7] Li S J, Mou X Q, Cai Y L, Ji Z, Zhang J H. On the security of a chaotic encryption scheme: problems with computerized chaos in finite computing precision. Computer Physics Communications, 2003, 153(1): 52–58

[8] Fridrich J. Symmetric ciphers based on two-dimensional chaotic maps. International Journal of Bifurcation and Chaos, 1998, 8(6): 1259–1284

[9] Feng Y, Li L J, Huang F. A symmetric image encryption approach based on line maps. In: Proceedings of the 1st International Symposium on Systems and Control in Aerospace and Astronautics (ISSCAA 2006). 2006, 1362–1367

[10] Chen G R, Mao Y B, Chui C K. A symmetric image encryption scheme based on 3D chaotic cat maps. Chaos, Solitons & Fractals, 2004, 21(3): 749–761

[11] Mao Y B, Chen G R, Lian S G. A novel fast image encryption scheme based on 3D chaotic baker maps. International Journal of Bifurcation and Chaos, 2004, 14(10): 3613–3624

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg