Genetic Algorithm Using Feistel and Genetic Operator Acting at the Bit Level for Images Encryption

In today's digital age, the security of sensitive data, especially medical images, is of paramount importance. Safeguarding the integrity and the confidentiality of images is crucial in a digital world where the exchange and the storage of visual information are commonplace. Images may contain private, confidential, or strategic data, and unauthorized exposure can lead to several consequences for individuals and organizations. To address this growing concern, numerous image encryption methods have been developed, yet some still exhibit vulnerabilities to sophisticated attacks.

With advancements in mathematics, cryptography swiftly made its way into the realm of security. The emergence of standards such as Hill ‎[1-4], Vigenère‎ [5-8], DES ‎[9], Feistel ‎[10-13], AES ‎[14, 15], and others has been observed. The development of chaos theory and the availability of multiple chaotic maps facilitate the creation of encryption algorithms. Furthermore, by following Shannon's guidelines ‎[16] and incorporating feedback in the encryption mode, a strong resilience is conferred upon the new cryptographic systems.

With the rapid advancement of chaos theory, we are witnessing several improvements in these classical techniques. Additionally, some of the currently highly recommended solutions are genetic algorithms. In fact, genetic algorithms are among the most frequently used optimization methods, with numerous applications in various scientific fields ‎[17-20]. The genetic algorithm, first proposed by John Holland in 1975, is one of the most renowned evolutionary algorithms, inspired by the evolutionary process of living species. The genetic algorithm is widely used to solve a variety of optimization problems, starting with the initial random generation of individuals, followed by selection for reproduction of the new tribes, according to the value of their evaluation function. In other words, the best-performing individuals have the opportunity to be selected for the reproduction of future generations. The selected individuals will be subjected to genetic operators such as mutation, crossover, insertion and reversion (Figure 1). With this in mind, most researchers have developed encryption methods based on adaptation of genetic algorithm to image encryption. Ghazvini et al. ‎[21] proposed an image encryption method based on genetic and chaos algorithms. The method consists of three main steps: a confusion phase using the Chen map, a second phase performed by the logistic-sine map, and the final phase involves selecting the encrypted image that yields the highest entropy and the lowest correlation. Mahmud et al. [22] had developed a novel cryptosystem based on the hybridization of Ribonucleic Acid (RNA) and Genetic Algorithm (GA). Initially, the logistic map and RNA codons are used to create initial populations for GA. Finally, GA optimizes the images using the fitness function based on entropy to find the optimized encrypted image. Ferdush et al. ‎[23] proposed a new hybrid encryption system using PSO and GA with a chaotic map. An image is initially encrypted using a chaotic function, then PSO and GA are applied to select the best encrypted image that exhibits the highest entropy and the lowest correlation coefficient between adjacent pixels.

Our contribution in this work is to develop a robust encryption system based on genetic algorithms using chaos and an enhanced Feistel scheme employing a circular shift for the right bloc and a pseudo-random permutation for the left bloc. Followed by the two most widely used genetic operators in cryptography, namely crossover and genetic mutation adapted to image encryption.

1.png

Figure 1. Genetic algorithm process

Our encryption technique consists of coupling the rows of (MG) and (MD) matrices using an enhanced Feistel laps followed by a crossover and mutation operations.

3.1 Feistel laps

The two matrices (MG) and (MD) will undergo coupling through an enhanced Feistel TF circuit defined by Eq. (4).

$\operatorname{TF}(G, D)=\left(G^{\prime}, D^{\prime}\right)=\left\{\begin{array}{c}G^{\prime}=h_i(D) \\ D^{\prime}=G \oplus f_i(D)\end{array}\right.$             (4)

where, $h_i$ is a binary permutation constructed by the binary vector $(W B(:, 3))$ and $f_i$ is a circular shift function determined by the coefficient $\mathrm{WC}(\mathrm{i}, 3)$. The coupling process is described by Algorithm 5.

Using VIG and VID are obtained by applying the XOR operation on all the rows of the MG matrix and MD natrix, excluding the first row. The enhanced Feistel round is illustrated in Figure 8.

At the end of the Feistel round. The two matrices (GM) and (DM) of size (2n, 6m+16) are combined into a single matrix (M') of size (2n, 12m+32). This matrix will be transformed into a vector (BX) of size (24 nm+64n).

8.png

Figure 8. Feistel lap

3.2 Genetic crossover

The second encryption phase involves a genetic crossover adapted for image encryption. For this reason, a pseudo-random transformation at the DNA level is necessary. This operation is described by the following steps:

3.2.1 Transition to $G_4$

Transition to $G 4$ the binary vector (BX) of size (24nm+64 n) will be converted into a vector (BY) of size (12nm+32n) taking values in $G_4$ using Algorithm 6.

3.2.2 Transition to DNA notation

The transition to DNA notation involves writing the vector (BY) into (YB) vector using the symbols {A, C, T, G}. For this, we will use two conversion tables T1 and T2 defined in Figure 9. The choice of the conversion table is determined by the control vector (WB(:, 3)). The process of converting to DNA notation is illustrated by Algorithm 7.

9.png

Figure 9. DNA conversion table

3.2.3 Genetic crossover function

The vector (YB) will be genetically crossed with a pseudorandom vector (R) of size (12nm+32n) defined by Algorithm 8.

The genetic crossover operation is controlled by a crossover table TC of size (12nm+32n, 3) where each column is defined as follows:

· The first column: a permutation P obtained by sorting the 12nm+32n values of the sequence s, indicating the index of the pixel to be processed.

· The second column: a permutation Q obtained by sorting the 12nm+32n values of the sequence t, indicating the index of the factor of R to be used.

· The third column: the QoP permutation indicating the index of the pixel obtained through genetic crossover.

The process of genetic crossover is illustrated by Algorithm 9.

10.png

Figure 10. DNA conversion table

With $\oplus$ and $\otimes$ are crossover operators defined at DNA level defined by Figure 10.

3.3 Genetic mutation

The third encryption phase involves establishing a diffusion operation ensured by a genetic mutation adapted for medical image encryption. This step will be described by the following axes:

3.3.1 Transition to $G_4$

The vector (WQ) written in DNA notation of size (12nm+32n) will be reconverted into a vector (QW) with coefficients in $G_4$ using conversion tables defined in Figure 11. The choice of the conversion table is determined by the control vector (WB(:, 2)). The process of conversion to $G_4$ is illustrated by Algorithm 10.

11.png

Figure 11. DNA to $G_4$ tables conversion

3.3.2 Transition to gray level (G₂₅₆)

The vector (QW) of size (12nm+32n) will be converted into a vector (QZ) of size (3nm+8n) with values in (G₂₅₆). This conversion is illustrated by Algorithm 11.

3.3.3 Initial value calculation

An initial value (WI) will be calculated to initialize the diffusion process. The calculation of the initial value is shown in Algorithm 12.

3.3.4 Genetic mutation function

12a.png

(a) first step

12b.png

(b) second step

Figure 12. Encryption process

The vector (QZ) of size (3nm+8 n) will undergo a genetic mutation function, defined by an inversion operation, and controlled by a mutation table of size (3nm+8n, 3). Each column of the mutation table is defined as follows:

· The first column: a permutation P obtained by sorting the 3nm+8n values of the sequence s+t, indicating the index of the pixel to be processed.

· The second column: a permutation Q obtained by sorting the 3nm+8n values of the sequence t+2s, indicating the index of the pixel obtained through genetic crossover.

· The third column: is a pseudo-random control vector used to control genetic mutation. This vector is defined by Algorithm 13.

The diffusion process is illustrated by Algorithm 14.

The vector (Z) constitutes the encrypted image by our algorithm and the entire encryption process is presented in Figure 12.

To evaluate the performance of our encryption system, we randomly select many reference images and then subject them to our encryption method. In this section, all experiments are conducted using the Python programming language on a personal computer based on i5, with 8GB of RAM and a 500GB hard drive, running Ubuntu 20.04.

5.1 Brutal attacks

Brutal attacks consist of reconstructing the encryption keys in a random manner by exploring all the key-space values.

5.1.1 Key-space analysis

To ensure the robustness of a good image encryption algorithm, the key space should have at least 2100 possibilities. If the key space is not sufficiently large, the algorithm could be vulnerable to brute-force attacks. In this algorithm, the key space encompasses the initial condition and control parameters of the chaotic maps. The secret key of our system consists of:

• $s_0=0.79878796$, r=0.755654 logistique map.
• $t_0=0.6789654$, v=0.98788755 skew tente map.

In our case, we consider the precision to be of the order of 1016. Therefore, the total key space reaches 1064. Thus, our algorithm is capable of resisting brute-force attacks due to the sufficiently large size of its key space.

5.1.2 Secret key’s sensitivity analysis

The high sensitivity of our encryption key is manifested by an amplified reaction following a slight modification of a single parameter, resulting in a significant difference from the original image. This assertion is visually confirmed by Figure 16.

16.png

Figure 16. Encryption key sensitivity

5.2 Visual test

The visual test is the first test which aims to detect a certain resemblance between the original image and the image encrypted by the new crypto system. In our simulations, visually the encrypted image is totally different from the original image and does not reflect any information or resemblance, this initially ensures the robustness of our system is illustrated by the result of the Table 1.

5.3 Histogram analysis

The histogram represents the distribution of pixels in an image. In the case of an encrypted image, the histogram should be uniformly distributed to prevent attackers from guessing information about the image. Furthermore, the histogram of the encrypted image should not resemble that of the original image. Table 2 shows the histograms of some encrypted images. As can be seen, the histograms of the encrypted images obtained with our algorithm are uniform.

Table 1. Visual test

Image Name	Clair Image	Encrypted Image	Decrypted Image
Img1 243$\times$411	t1.png	t2.png	t3.png
Img2 1057$\times$1200	t4.png	t5.png	t6.png
Img3 837$\times$821	t7.png	t8.png	t9.png
Img4 512$\times$512	t10.png	t11.png	t12.png
Img5 512$\times$512	t13.png	t14.png	t15.png

5.4 Correlation analysis

Table 2. Histogram

Image	Histogram
Img1	21.png
Img2	22.png
Img3	23.png
Img4	24.png
Img5	25.png

Table 3. Correlation and entropy

Image		Vertical Correlation	Diagonal Correlation	Horizontal Correlation	Entropy
Img1	R	0.00194	-0.00264	-0.00064	7.99829
	G	0.00162	-0.00201	-9.11e-05	7.99806
	B	0.00014	-0.00307	0.00092	7.99811
Img2	R	-0.00122	0.00090	0.00098	7.99985
	G	0.00031	-7.75e-05	0.00093	7.99983
	B	-0.00056	0.00050	-0.00043	7.99987
Img3	R	0.00064	-0.00159	8.17e-05	7.99977
	G	-0.00177	-0.00156	0.00068	7.99971
	B	-0.00102	0.00112	0.00124	7.99975
Img4	R	0.00020	0.00161	0.00166	7.99930
	G	-0.00127	-0.00312	-0.00213	7.99930
	B	0.00023	0.00233	0.00138	7.99929
Img5	R	0.00125	0.00096	0.00232	7.99935
	G	0.00059	0.00178	-0.00224	7.99925
	B	-0.00464	-0.00014	-0.00173	7.99922

$\begin{gathered}N P C R=\left(\frac{1}{n m} \sum_{i, j=1}^{n m} D(i, j)\right) * 100 \\ \text { with } D(i, j)=\left\{\begin{array}{lll}1 & \text { if } & C_1(i, j) \neq C_2(i, j) \\ 0 & \text { if } & C_1(i, j)=C_2(i, j)\end{array}\right.\end{gathered}$              (7)

The UACI mathematical analysis of an image is given by Eq. (8).

$U A C I=\left(\frac{1}{255 n m} \sum_{i, j=1}^{n m} A b s\left(C_1(i, j)-C_2(i, j)\right)\right) * 100$             (8)

The avalanche effect refers to the number of bits that change when a single bit in the original image is modified [24]. The mathematical representation of the avalanche effect is expressed by Eq. (9).

$A E=\left(\frac{\sum_i \text { bit change }}{\sum_i \text { bit total }}\right) * 100$                (9)

Table 4. Differential parameters

Table 4 presents some results of the calculation of differential parameters for images encrypted using our method. All calculated NPCR values are greater than the threshold of 99.60%, UACI is greater than 33.46%, and AE is greater than 50%. This demonstrates that our algorithm can resist differential attacks.

5.7 Encryption time

The encryption time is a crucial benchmark for assessing the efficiency of an image encryption algorithm. Effectively encrypting substantial data, such as images, within a reasonable timeframe has become a challenging aspect of algorithm development. In our study, we present the encryption times for images of sizes 256×256 and 512×512 in (Table 5), along with a comparison to other recent works. Furthermore, the time complexity of our method for an image of size (N, M) is O(NM).

Table 5. Encryption time

5.8 Comparison to other techniques

Table 6 shows that our technique gives satisfactory results compared to other method in the literature. The entropy of the tow images gives values extremely close to the ideal value of 8 and higher than the values obtained by most other methods. For the NPCR and UACI, the values of the proposed scheme are very close to the values of NPCR (99.6%) and UACI (33.4%) expected. Accordingly, from Table 6, we can conclude that the suggested method outperforms many recently published studies in terms of entropy, NPCR and UACI values.

Table 6. Comparison to other technique