A New Encryption Algorithm Based on Fibonacci Polynomials and Matrices

According to a novel method put forth by Mukherjee and Samanta [1], a message can be both encoded and hidden in an image by using the Fibonacci series to encrypt it.

In their study, Uçar et al. [2] developed two new encoding/decoding methods that make use of Fibonacci Q-matrices and R-matrices. The models rely on blocked message matrices and key-based encryption for each message matrices. These new algorithms have great accuracy capabilities in addition to increasing information security.

Zou et al. [3] introduced a brand-new technique for digital image mixing based on the Fibonacci numbers. There have been concerns raised about the mixing transform's homogeneity and periodicity. The benefits of mixing transform are as follows: Encoding and decoding are both very easy to use in real - time scenarios. The mixing effect is excellent, as the image data is randomly redistributed across the image. The technique is resistant to common image attacks like noise, compression, and data packet loss.

Khadri et al. [4] dealt with text encoding in such a way that the receiver can only find out the original message without any data loss or shift or data leakage. Some possible approaches were presented to solve their identified problem, using Fibonacci series. The data was encrypted by combining the original data with Fibonacci numbers to get a cipher text, which is incomprehensible to any intruder. Only the receiver knows the logic of the way doing this.

Diskaya et al. [5] developed a classical Aes-like cryptology based on the Fibonacci polynomial matrix, using a certain irreducible polynomial. Asci and Aydinyuz [6] generalized the AES-like cryptology on 2×2 matrices with the elements of k-order Fibonacci polynomial series using a certain irreducible polynomial in the cryptology algorithm, which is called AES-like cryptology on the k-order Fibonacci polynomial matrix. Anderson [7] proposed a number of keystream generators based on Fibonacci series. Karacam et al. [8] examined the transmission of time and position variable cryptology in the Fibonacci and Lucas number series with music.

4.1 Our approach

The encryption algorithm involves three rounds, the initial round, the main round, and the final round. In the initial round, XOR operation is performed between the state matrix (clear text) and the key matrix (private key).

In the main round, the mixing process is applied in general. The confusion and diffusion in this round are created in the following steps:

• Traverse conversion

• Fibonacci s-box conversion

• Change row and column matrix

• Multiply matrix (multiplication by Fibonacci polynomial matrix)

The results obtained through con and diff operations and the key generated from the round key are subjected to XOR operation. The above operations in the main round are repeated twelve times.

In the final round, the matrix from the main part is once again processed through Fibonacci sbox conversion and the last key, before terminating the encryption process.

The process of our approach is detailed as follows:

Firstly, cross transform is applied on the add matrix, and the matrix is mixed using Fibonacci AES s-box [11].

Step 1 (Initial round): The 128-bit image (state matrix) and the polynomials in each cell of the key matrices are added as follows:

Suppose X_ij, Y_ij, and Z_ij are order 7 polynomials, where 1≤i, j≤4,

$Z_{i j}=X_{i j}+Y_{i j}=\left(a_7^{(i j)}+b_7^{(i j)}\right) x^7+\cdots+a_0^{(i j)}+b_0^{(i j)}$, $a_k^{(i j)}, b_k^{(i j)} \in\{0,1\}, 0 \leq k \leq 7$.

is obtained.

Step 2 (Main Round): According to mod 2, the order 7 polynomials are divided into two order 3 blocks, forming the 4th degree A and B polynomial elements. That is:

$Z_{i j}=c_7^{(i j)} x^7+c_6^{(i j)} x^6+\cdots+c_0^{(i j)}, c_k^{(i j)} \in\{0,1\}, 0 \leq k \leq 7$.

In the case that A_ij, B_ij are order 3 polynomials;

$A_{i j}=c_7^{(i j)} x^3+c_6^{(i j)} x^2+c_5^{(i j)} x+c_4^{(i j)}, c_k^{(i j)} \in\{0,1\}, 4 \leq k \leq 7$,

$B_{i j}=c_3^{(i j)} x^3+c_2^{(i j)} x^2+c_1^{(i j)} x+c_0^{(i j)}, c_k^{(i j)} \in\{0,1\}, 0 \leq k \leq 3$.

is obtained.

Then, the values marked in the traverse conversion matrix are multiplied by the first eight Fibonacci elements obtained using mod 2 and the irreducible polynomial x⁴+x+1.

The first eight Fibonacci elements are:

$f_1(x)=1, f_2(x)=x, f_3(x)=x^2+1, f_4(x)=x^3, f_5(x)=x^2+x$, $f_6(x)=x^2, f_7(x)=x^3+x^2+x, f_8(x)=x^3$.

The multiplication goes as follows:

$C_{i j}=A_{i j} \times f_{i+j}(\bmod 2)$ or $C_{i j}=B_{i j} \times f_{i+j}(\bmod 2)$

If polynomials A_ij, B_ij, and C_ij of the obtained matrix are converted using the hexadecimal base against the Fibonacci s-box table, it is possible to obtain the Fibonacci s-box conversion matrix. The rows of this matrix are shifted by the first four terms of the Fibonacci numbers (i.e., 1, 1, 2 and 3), respectively. Then similar operations are applied to the columns, respectively:

• The first row of the matrix is shifted 1 bit left based on the value of the first term of the Fibonacci s-box table.
• The second row of the matrix is shifted 1 bit to the left based on the value of the second term of the Fibonacci s-box table.
• The third row of the matrix is shifted 2 bits to the left based on the value of the third term of the Fibonacci s-box table.
• The fourth row of the matrix is shifted 3 bits to the left based on the value of the fourth term of the Fibonacci s-box table.

The row changes result in a change row matrix. Then, the column change is applied to the change row matrix:

• The first column of the matrix is shifted up by 1 bit based on the value of the first term of the Fibonacci s-box table.
• The second column of the matrix is shifted up by 1 bit based on the value of the second term of the Fibonacci s-box table.
• The third column of the matrix is shifted up by 2 bits based on the value of the third term of the Fibonacci s-box table.
• The fourth column of the matrix is shifted up by 3 bits based on the value of the fourth term of the Fibonacci s-box table.

Thereby, a change column matrix is obtained, and then divided into blocks to be multiplied by the 2×2 Fibonacci polynomial matrix (1). The generated new 2×2 type matrices adopt mode 2 and irreducible polynomials x⁴+x+1, respectively. On this basis, the multiply matrix can be obtained by:

$\left[\begin{array}{ll}K_{22} & L_{22} \\ K_{33} & L_{33}\end{array}\right]\left[\begin{array}{ll}f_{n+1}(x) & f_n(x) \\ f_n(x) & f_{n-1}(x)\end{array}\right]=\left[\begin{array}{ll}D_{11} & E_{11} \\ D_{21} & E_{21}\end{array}\right]$,

$\left[\begin{array}{ll}K_{23} & L_{23} \\ K_{34} & L_{34}\end{array}\right]\left[\begin{array}{ll}f_{n+1}(x) & f_n(x) \\ f_n(x) & f_{n-1}(x)\end{array}\right]=\left[\begin{array}{ll}D_{12} & E_{12} \\ D_{22} & E_{22}\end{array}\right], \cdots$,

$\left[\begin{array}{ll}K_{21} & L_{21} \\ K_{32} & L_{32}\end{array}\right]\left[\begin{array}{cc}f_{n+1}(x) & f_n(x) \\ f_n(x) & f_{n-1}(x)\end{array}\right]=\left[\begin{array}{ll}D_{34} & E_{34} \\ D_{44} & E_{44}\end{array}\right]$.

and {n=2+t:t.round=t} where for 1≤i,j≤4, K_ij, L_ij, D_ij, and E_ij  are order 4 polynomials.

The n value is updated for these operations each round. The add matrix is created in the final phase of the main round by adding the multiply matrix and round key 0. The round key is added to the key created using the prior key in each loop.

Step 3 (Final Round): The final round takes place after the image has been encrypted in the main round.  The image that needs to be encrypted will undergo multiply matrix operations in the final round, be added with round key 13, putting an end to the encryption process.

Figure 1 depicts the flow of the encryption process. Figure 2 presents the flow of the encryption algorithm.

1.png

Figure 1. The encryption process

2.png

Figure 2. Flow of the encryption algorithm

Tables 1-5 display the nominal codes of cross transformation, s-box function, mix column and row, product of matrix and sum of matrix stages in the flowchart, respectively.

4.2 Practical applications of the proposed method and analysis results

This section discusses the practical application and test results of the proposed encryption algorithm. Specifically, our approach was applied to Lena, baboon and baby images, which are widely used in the literature. All tests were carried out on a computer with Intel Core i5 (7300HQ) quad-core CPU, 8 GB DDR4 RAM, 1 TB HDD and Windows 10. All images were processed by MATLAB R2019b. The application effect was measured by histogram analysis, root mean square error (RMSE) and differential attack analysis.

Table 1. The croos transformation

Table 2. SBOX function

Table 3. Mix column and row

Table 4. Product of matrix

Table 5. Sum of matrix

4.2.1 Histogram analysis

For an image with brightness of [0, L − 1], the histogram can be described by a discrete function:

H(rk)= nk,

where, rk is the brightness intensity; nk is the number of image pixels with brightness intensity of rk [12]. For the target image of histogram analysis, the number of pixels with brightness of 0, 1, 2 … L-1 is calculated. The results are placed on the vertical axis. The histogram provides useful statistics about the image, which facilitates image compression, and segmentation. The histogram of encrypted images must be uniform [13, 14]. Figures 3-5 present the original, encrypted and decrypted states of the sample images, respectively. The R, G, B values are given on the right of these states. A uniform distribution has been obtained for all values, as shown by the coded histograms in the images. The histogram of the original images and the encrypted images are very different from one another. A uniform distribution makes it challenging to draw statistical inferences and makes statistical attacks on the suggested encryption technique more difficult.

4.2.2 Root Mean Square Error (RMSE)

This section investigates whether there is a difference between the original image and the decoded image, using the RMSE defined in formula (4). This metric measures the magnitude of error in quadric terms. As the standard deviation of the estimation errors, it is often used to find the distance between the predicted and true values. The value range of RMSE is 0 to ∞. The smaller the RMSE, the better the prediction. If RMSE equals zero, the model must have made no error [15].

$R M S E=\sqrt{\frac{\sum_{j=1}^n e_j^2}{n}}$      (4)

where, A_jand P_j are the actual and predicted values, respectively; e_j=A_j-P_j is the error; n is the size of the dataset.

The magnitude of the error, absolute error, and squared error can be respectively expressed as D1=A_j-P_j=e_j, $D 2=\left|A_j-P_j\right|=\left|e_j\right|$, and $D 3=\left(A_j-P_j\right)^2=\left(e_j\right)^2$, respectively.

The results in Table 6 demonstrate that no loss arises from encryption in the original images, for the decoded image that was acquired from the encrypted image has no difference. The histogram density graphs of the encrypted and decoded images are identical, as can be seen in Figures 3, 4, and 5.

3.png

Figure 3. Histogram of the Lena image

4.png

Figure 4. Histogram of the baby image

5.png

Figure 5. Histogram of the baboon image

Table 6. RMSE values of images

4.2.3 Differential attack analysis

By using an encryption algorithm with a fixed key, differential attacks attempt to alter the original text pair in some way. The impact on the original text can be assessed by analyzing how much the encrypted output differ from the original input [16, 17]. The avalanche effect is being strengthened in cryptographic systems in an attempt to improve their defenses against differential attacks. This is a useful feature in cryptographic algorithms, for it causes minor changes in input to result in significant changes in output [18].

NPCR is one of the criteria for the effect of differential attacks on image encryption. NPCR evaluates an algorithm's sensitivity to minute alterations in the original image. First, the original image is subjected to the C1 cryptographic technique in order to determine the NPCR. Then, a randomly chosen pixel from the original image is altered. After that, the encryption algorithm is applied to the image of which a pixel has been modified again, yielding a second encrypted image, denoted C2. The following formulae are used to calculate the NPCR value [19, 20].

Table 7. UACI and NPCR test results

Table 8. Comparison of the proposed method with the studies in the literature

$D(i, j)=\left\{1\right.$ if $C_1(i, j) \neq C_2(i, j) 0$ if $C_1(i, j)=C_2(i, j)$

$N P C R=\frac{1}{M \times N} \sum_{i=1}^M \sum_{j=1}^N D(i, j) \times \% 100$       (5)

As shown in formula (5), the ideal value for the NPCR value is 100%. According to the results in Table 1 about the proposed approach, the NPCR value is very close to 100%, indicating that the approach is extremely precise to the smallest changes in the input. Hence, changing a pixel value in the original image causes all pixels in the encrypted image to change.

UACL is another metric of image encryption efficiency. This metric is a yardstick of the avalanche effect:

$U A C I=\left(\sum_{i=1}^M \sum_{j=1}^N \frac{\left|C_1(i, j)-C_2(i, j)\right|}{255 \times M \times N}\right) \times \% 100$      (6)

Eq. (6) is used to calculate the UACI.

The UACI value for successful image encryption is close to 33%. As shown in Table 7, our encryption algorithm achieved an UACI very close to 33%.

Table 8 compares the proposed approach with the methods in literature, using Lena and baboon images and chaotic systems. It is clear that our approach achieved the desired results in NPCR and UACI, surpassing the performance of the contrastive methods. This is attributable to the use of Fibonacci polynomials matrix, which has an important place in the field of mathematics.

There are different-based image encryption studies in the literature [33, 34].