ABSTRACT

The paper describes a symmetric encryption algorithm based on bit permutations and using an iterative process combined with a chaotic function. The main advantages of such a cryptosystem is its ability to encrypt securely bit sequences and assuring confusion, diffusion and indistinguishability properties in the cipher. The algorithm is applied on the image encryption where the plain-image is viewed as binary sequence. The results of statistical analysis about randomness, sensitivity and correlation on the cipher-images show the relevance of the proposed cryptosystem.

1. Introduction

The use of the internet and network applications becomes indispensable in the modern society and the necessity to protect and secure such applications from prying eyes is essential. On internet, the informations can be your credit card numbers, bank account informations, health/social security informations or even personal communications with everybody. Such a challenge is the concern of cryptography that is developed and used to hide information against unauthorized users. Several encryption algorithms are available and used in information security. They can be classified into two categories: asymmetric (public) and symmetric (private) encryption algorithms. For asymmetric encryption, two keys are used: private and public keys. Public key is used for encryption and private key is used for decryption (e.g. RSA [1]). In symmetric case, only one key which must be secret is used to encrypt and decrypt the data. Some of the best known algorithms are DES, 3DES, BLOWFISH, IDEA or AES [2,3]. DES algorithm uses one 64-bits key where 8 bits are used solely for checking parity. Triple DES (3DES) uses three 64- bits keys. BLOWFISH has a 64-bits block size and a key length from 32 bits to 448 bits. IDEA operates with 64- bits block size and is controlled by a 128-bits key while AES uses various keys of 128, 192 and 256 bits. However, these algorithms do not always keep the same efficiency (quality of the cipher, execution time, etc.) depending on the structure of the input data (texts, images) [4,5].

Here we propose an encryption algorithm which is able to deal efficiently with any type of input data. The input data is considered as a simple binary sequence (or vector) constituted only by the bits “0” and “1”. The algorithm directly works on the entire input block of bits and uses an iterative process of substitution-permutation combined with a chaotic function. The algorithmic principle is simple and easy to implement. The encryption key corresponds to the set of seeds values used by the chaotic function. The same secret key is used for encryption and for decryption. The plaintext and ciphertext are bit sequences of various length. Such an algorithm encrypts any kind of binary sequence and produces highly secure ciphers. Here we apply the algorithm on images that are known to have high correlation between adjacent pixel values. The analysis, achieved on the binary corresponding sequences of the cipher-images, is based on the criteria of randomness, sensitivity and correlation. We also show that the size of the key space is large enough to resist to brute-force attacks. The paper is structured as follows. The description of the chaotic function and the encryption/decryption algorithm are given in Section 2. Section 3 presents the results and the security analysis of the proposed cryptosystem before concluding.

2. The Proposed Encryption Method

The present scheme uses an iterative process to encrypt a sequence of bits. The original input data is treated as a simple vector composed of bits “0” and “1”. A chaotic function is used during the iterative process to index the positions to be permuted. Before permutation, the bits of indexed positions will be transformed via a xor operator. This process simultaneously combines the confusion and diffusion properties that are required to obtain a high security level.

2.1. The Used Chaotic Function

The algorithmic process uses a standard chaotic function given by:

(1)

with between 3.57 and 4 [6]. The chaotic behavior of such a function has been widely studied. Here, the value of is fixed to 3.9999 which corresponds to a highly chaotic case [7]. In the last decade, several schemes have used this function for image encryption [5,8,9]. The chaotic function is defined by the recurrence relation

(2)

where the starting seed and all others elements are real numbers belonging to the interval ]0,1[. Such a chaotic function is used to compute the positions to be permuted into the input binary sequence.

2.2. Description of the Algorithm

The chaotic function given by Equation 2 is used and adapted through the iterative process. The principle of the encryption algorithm is described in four steps:

1) The original input sequence is transformed into its 1D corresponding binary vector. This vector is composed only of the bits “0” and “1”. For example, if the initial sequence is a RGB-color (resp. gray-level) image of size, the size of is (resp.).

2) A seed value is chosen in the interval to initiate the iterative relation of Equation 2. The seed contains decimal digits and the value of is computed relatively to the size of the vector.

3) A loop is started on the binary vector, with. With the current position in, a new position is computed by using the chaotic function:

(3)

with and the value of is initialized to and decremented by 1 after each iteration. Due to the modular operation, the value is chosen to be larger than. Thus, the value of is intrinsically related to the size of:

(4)

During the loop, the computed position has always a value and the elements of are transformed as follows:

(5)

(6)

(7)

(8)

where the symbol represents the exclusive OR operation bit-by-bit. That permutation process is the same until the end of the loop. One can remark that the new positions represent the values of the old already shuffled positions. Therefore, the value into the vector can move several times before fixing.

4) Depending to the encoding of the original sequence, the bits of the vector are gathered per small group to form the cipher. For RGB-color (resp. gray-level) images, the bits are gathered per group of (resp. 8). This step permits to reconstruct the obtained cipher sequence.

That constitutes the encryption steps for one round (i.e.) on the input sequence using the seed. Therefore, given an input sequence the system produces a corresponding cipher sequence, where is the total number of round used by the algorithm. The first step is done once before starting the iterative process and step 4 is used only at the end to construct the obtained cipher. The total number of round is computed by taking into account security criteria and characteristics of the initial sequence (see Section 2.3). Each cipher is produced by using a key composed of the values of seeds. The Figure 1 illustrates the main

steps of the encryption scheme and the corresponding algorithm is given by the Algorithm 1. The decryption consists in reversing the process and initiating it from the last seed. All positions used during the encryption must be computed and stored in a vector. A loop is done through the vector from the end to the start by making all necessary operations. The decryption algorithm is given by Algorithm 2.

2.3. Determination of the Round Number R

The number of round necessary for encryption/decryption is an important element which is connected to the security of the system. For a higher level of security it must also take into account the characteristics of the binary vector (e.g. encoding, size and entropy). The number of round is determined before starting the encryption process. Given today’s computer speed, it is generally accepted that a key space of size smaller than is not secure enough. In the present case, each key is composed of values of seeds. At each round, the corresponding seed belongs to the interval, with digits of accuracy (i.e.). Thus, excluding the null seed, the total number of possibilities for the seed space at each round is. To satisfy the condition:

(9)

and to avoid any brute-force attack, the minimum number of rounds is given by:

Algorithm 1. Encryption algorithm.

Algorithm 2. Decryption algorithm.

(10)

The condition assures the minimum entropy limit for the seed space but not necessarily all the required qualities for the cipher. Given the algorithmic structure of the system, the number of round is not sufficient to efficiently encrypt a binary sequence with a large imbalance of bits “0” and “1”. Therefore, the total number of rounds must also be related to the distribution of bits “0” and “1” in the input binary sequence. Let consider that, in binary sequence, the occurrence of the bit “0” has a probability and for the bit “1”. Then, at each new round, the probability is iteratively modified as follows:

(11)

and the limit of the suite must converge to to ensure a balanced binary proportion in the cipher. The purpose is to find the number of round satisfying the relation:

(12)

with a fixed numerical tolerance (here). The value of can be computed iteratively and can be large for with very low Shannon’s entropy or small for with Shannon’s entropy closed to its maximum (i.e. 1 in base 2). Such a value is computed by the Algorithm 3. Another problem occurs when two nearby binary sequences are encrypted using the same key, because the corresponding ciphers can be highly correlated. Thus, the number of round must also satisfy this case for a better encryption. For that, we consider the most unfavorable case where two sequences and differ by only one bit. The proportion of identical elements between these two binary suites is . The value of decreases according to the number of round as follows

(13)

and must satisfy:

(14)

where is the acceptable criterion of similarity between binary sequences (e.g., assuming a rate of identical bits smaller than 0.5%). The value of satisfying the Equation (14) is given by

(15)

Such a value of ensures to obtain two completely different ciphers. It mainly allows to resist to the differential attack or generally the chosen plaintext attack. Therefore, the relevant number of round of the encryption algorithm is given by:

(16)

The final number of rounds permits to satisfy simultaneously the criteria of key entropy, maximum Shannon’s entropy and sensitivity to initial conditions (sequence and key).

2.4. Bits Propagation Analysis

In this section, we show the evolution of bits propagation

Algorithm 3. Computation of the round number R₂.

into the cipher during the encryption process. To illustrate the bit propagation, we use a particular initial vector corresponding to a gray-level image composed by only black (0) and white (255) pixels. The image size is and the white pixels are gathered in the center of the image as a small white circle. The number of black pixels is 122276 (i.e. 99.81%) and white pixels is (i.e. 0.19%) (see Figure 2(a)). The values of are 5, 11 and 23 respectively. The encryption round number is. The plain-image is encrypted and the intermediate cipher-images obtained after r = 1, 2, 5, 7, 9, 11, 20 and 23 are shown in Figures 2(b)-(i). We note that, after rounds, the small white circle is vanishing. For, the intermediate cipher-image starts to look like a true random image and from it passes successfully the NIST tests [10]. One can remark that the randomness propagation is gradual before stabilizing and give a true random image. The ciphers obtained by this encryption scheme have all the same appearance and the same randomness quality, whatever the particularity of original binary sequence. The cipher quality does not depend on the structure of the input sequence. Additional analysis is achieved by computing the correlation coefficients [5], NPCR (Number of Changing Pixel Rate) and UACI (Unified Averaged Changed Intensity) [11], of intermediate cipher-

images between two consecutive rounds. For two uncorrelated sequences, the correlation coefficient is. A strong correlation occurs between two sequences for a coefficient value. The evolution of coefficient values is represented at Figure 3(a). One can also remark that, the NPCR and UACI indicator values increase with (see Figure 3(b)). For, the values appear to be stabilized for the three indicators. That confirms that from, the intermediate cipher-images are different and the correlation coefficients, NPCR and UACI values become stable for. Taking into account allows to include the plainimage sensitivity and therefore to obtain a better security level of the system. These results show the relevance of the iterative process and the choice of the round number of the encryption algorithm.

2.5. Key Space

An efficient encryption scheme should have a large key space in order to make brute-force attacks infeasible. It is generally accepted that a key space of size smaller than is not secure enough. In the present case, the determination of round number allows to satisfy the required entropy of the size of key space. For example,

for a bits sequence of length , the algorithm enables to produce exactly

different cipher sequences. Thereforethe proposed scheme is not vulnerable to brute-force attacks.

3. Results and Security Analysis

The cryptosystem is applied on the image encryption where the original image is treated as a sequence of bits. Generally, the adjacent pixels in an image are highly correlated therefore the pixel values are very close or identical throughout the image. The statistical analysis of the encryption scheme is based on the three fundamental properties that are: indistinguishability, confusion and diffusion [12]. Indistinguishability means that the produced ciphers should have a high level of randomness and not to be differentiated from the outputs of a truly random function. The property of confusion means that the plain-image and the cipher-image should be completely decorrelated. By diffusion, the cryptosystem should be very sensitive to the initial condition (i.e. a variation of at least one bit in the key or plain-image leads to strong different cipher-images). Therefore, the security of the system is analysed through these three properties.

3.1. The Used Images for Analysis

Two image formats are used for the analysis: a RGBcolor image and a gray-level image. The RGB-color image, noted, has 173 rows and 249 columns (see Figure 4(a)). Its binary length is, the computed round number is equal to 23 and the number of decimal digits is. An example of encryption with the key given in the Table 1 is presented at the Figure 4(b). The frequency histograms for the red, green and blue channels before and after encryption of the RGB-color image are presented in Figure 5. The second image of size encoded in gray-level is presented in Figure 6(a). The round number and the significant digits are and. An example of cipher-image with the key (here) is given in Figure 6(b). The Figures 6(c)-(d) show the frequency histograms of intensity levels before and after encryption of the image. The obtained histogram after encryption has a balanced distribution of frequencies.

3.2. Key Sensitivity Analysis

A good encryption system must be highly sensitive to the encryption key. A difference of a single bit into the key must provide a very different encryption/decryption result. In that case, the key is given by values of arbi

trarily chosen seeds in the interval. The sensitivity study focuses on a variation of the last seed value. In the following, we consider the RGB-color image (Figure 4(a)) and the gray-level image (Figure 6(a)). Each image is encrypted by using the seed values given in Table 1. On the last seed, a loop is done from 0.571410332 to 0.571411131 incrementing by. The variation on the last seed value (i.e.) produces 800 keys. The 800 cipher-images obtained from the 800 generated keys are analysed.

3.2.1. Randomness Analysis

The randomness level of the 800 ciphers is analysed through the NIST tests. Such a suite consists in a statistical package of fifteen tests developed to quantify and to evaluate the randomness of binary sequences produced by cryptographic random or pseudorandom number generators [10]. For each statistical test, a probability is computed. A of zero indicates that, the sequence appears to be completely non-random. A larger than 0.01 means that, the sequence is considered to be random with a confidence level of 99%. For multiple tested sequences at the same time, each test defines a proportion as the ratio of sequences passing successfully the test relatively to the total number of tested sequences. The proportion is compared to an acceptable proportion which corresponds to the ratio of sequences that should pass the test. The range of acceptable proportions, excepted for the tests Random Excursion-(Variant) is determined by using the confidence interval defined as

[10]. Forthe acceptable proportion should lie above 97.94%. Each binary sequence is individually tested and the percentage of success is given for each statistical test. The Table 2 presents the results of tests for the ciphers obtained from the two plain-images and. The tested binary sequences pass successfully the NIST tests. Therefore, these sequences can be considered as random sequences. This analysis checks the properties of indistinguishability and confusion.

3.2.2. Correlation Analysis

For each case (RGB and gray-level image), the correlation is analysed globally by computing the correlation coefficients between each pair of produced ciphers. The distribution of the coefficient values are presented by the histograms given by the Figure 7. All the coefficient

values belong to the interval. For the RGBcolor image, 99.56% of the coefficients have an absolute value smaller than 0.008. In the case of gray-level image, 99.24% of the coefficients have an absolute value smaller than 0.0065. The results show that the cipher-images have a very low correlation. This analysis shows that a small difference between the keys can be propagated and give completely different ciphers (diffusion property).

Additional analysis is achieved by calculating the NPCR and UACI between each pair of the 800 cipherimages. The average and the standard deviation values for the correlation coefficients, NPCR and UACI are computed and presented in the Table 3. The obtained values show that the tested ciphers are totally different. Such an analysis confirms the sensitivity of the encrypttion system in relation with the encryption key.

3.3. Plain-Image Sensitivity Analysis

A second important analysis concerns the sensitivity related to the original image. Therefore, we produce multiple nearby images by introducing a small variation of one bit in the original image. All these images are encrypted by using the same key and the corresponding ciphers are

analysed. For the RGB-color image, the first pixel (0, 0) of the image at upper left is encoded by the values [94,148,179] (i.e. blue, green, red). The value of the blue component (94) is incremented by 1 (i.e. from 94 to 233) to form 140 consecutive images. Obviously, the difference between the 140 produced images can not be visually distinguished. These images are encrypted using the same key (given in Table 1). The same approach is applied to the gray-level image for which the value of the first pixel (147) is decremented by 1 (i.e. from 147 to 8) to produce 140 new gray-level images. These images are encrypted with the key. For each case, the 140 cipher-images are constructed from the original image by using the same set of seed values.

3.3.1. Randomness Analysis

The NIST tests are used to evaluate the randomness level of the 140 ciphers. With such number of ciphers, the ratio must overpass The results of the NIST tests are presented in the Table 4. The results show that the tested sequences have a good level of randomness. This analysis checks the properties of indistinguishability and confusion.

3.3.2. Correlation Analysis

The correlation coefficient is calculated between each pair of the 140 cipher-images. The Figure 8 presents the two histograms of correlation coefficients for values belonging to the interval.

For the 140 cipher-images of the RGB-color image, 99.02% of the coefficients have absolute values smaller than 0.0072 and for the gray-level images 99.19% of the coefficients have absolute values smaller than 0.0065. These histograms illustrate the small correlation between the tested cipher-images. Such a quality is critical to resist to the chosen plaintext attack. The correlation is also evaluated via the NPCR and UACI indicators. The average and the standard deviation values for the correlation coefficients, NPCR and UACI are computed and presented in the Table 5. The results show that the tested ciphers are completely different. A difference of only one bit in the original binary sequence produces different cipher.

3.4. Efficiency Analysis

Efficiency is also an important indicator for a good encryption algorithm. Table 6 lists the execution time and the key space entropy for the encryption process for different sizes of gray-level images. A comparison with the results of other algorithms is also presented. The used computer is an Intel Core Duo T2300 (1.66 GHz) Processor with 2.5 Go memory under Fedora 14 (Laughlin). One can see that the size of the key space is larger for the proposed algorithm, assuring a secure encryption. Sensitivity to the plain-image should not be neglected because it is part of the assumptions to be verified for an encryption algorithm. If such an hypothesis is not respected, the algorithm can be broken by the chosen plaintext attack. In order to compare the time efficiency with reference algorithms, we also consider the two cases with and. The speed time of the version of the algorithm (not taking into account the sensitivity to the initial sequence) is achieved

in order to compare with reference algorithms which use the correlation, NPCR and UACI indicators. An alternative way to improve the encryption speed is to reduce the value of in Equation (15) which determines the number of round.

4. Conclusion

A new symmetric encryption algorithm based on binary permutations was presented. The algorithm uses an iterative process of substitution-permutation combined with a

chaotic function. The principle of such a process is to drastically disrupt the internal binary structure of the sequences and progressively induce randomness characteristics. The key space is large enough to resist brute-force attacks. The application to image encryption show that the cryptosystem is very sensitive to key and plain-image. The advantage of such an encryption algorithm is its ability to securely encrypt any kind of binary sequence. Such a cryptosystem can be used for secure storage or transmission of sensible binary data.

REFERENCES