k-Order Fibonacci Polynomials on AES-Like Cryptology

Mustafa Asci; Suleyman Aydinyuz

doi:10.32604/cmes.2022.017898

Pamukkale University, Kinikli, Denizli, 20160, Turkey
*Corresponding Author: Suleyman Aydinyuz. Email: aydinyuzsuleyman@gmail.com
Received: 15 June 2021; Accepted: 26 October 2021

Abstract: The Advanced Encryption Standard (AES) is the most widely used symmetric cipher today. AES has an important place in cryptology. Finite field, also known as Galois Fields, are cornerstones for understanding any cryptography. This encryption method on AES is a method that uses polynomials on Galois fields. In this paper, we generalize the AES-like cryptology on 2×2 matrices. We redefine the elements of k-order Fibonacci polynomials sequences using a certain irreducible polynomial in our cryptology algorithm. So, this cryptology algorithm is called AES-like cryptology on the k-order Fibonacci polynomial matrix.

Keywords: Fibonacci numbers; Fibonacci polynomials; k-order Fibonacci polynomials; Fibonacci matrix; k-order Fibonacci polynomial matrix; Galois field

AES (Advanced Encryption Standard) is a standard offered for encryption of electronic data. AES, adopted by the American government, is also used as a defacto encryption standard in the international arena. It replaces DES (Data Encryption Standard). The encryption algorithm defined by AES is a symmetric-key algorithm in which the keys used in both encryption and decryption of encrypted text are related to each other. The encryption and decryption keys are the same for AES.

The algorithm standardized with AES was created by making some changes to the Rijndael algorithm, which was mainly developed by Vincent Rijmen and Joan Daeman. Rijndael is a name obtain using the developers’ names: RIJmen and DAEmen.

AES is based on the design known as substitution-permutation. Its predecessor, DES, is an algorithm designed in Feistel structure. AES’ software and hardware performance is high. The 128-bit input block has a key length of 128, 192 and 256 bits. Rijndael, on which AES is based, supports input block lengths that are multiples of 32 between 128 and 256 bits and key lengths longer than 128 bits. Therefore, in the standardization process, key and input block lengths were restricted. AES works on a 4×4 column-priority byte matrix called state. Operations in the matrix are also performed on a special finite field.

The algorithm consists of identical rounds that transform a certain number of repeating input open text into output ciphertext. Each cycle consists of four steps, except for the last cycle. These cycles are applied in reserve order to decode the encrypted text. The number of repetitions of cycles is a function of the key length according to Table 1.

These cycles include key addition, byte substitution, ShiftRow and MixColumn. We can see these cycles in Fig. 1. One can see detailed information about AES in Fig. 2 [1].

A finite field, sometimes also called Galois field, is a set with a finite number of elements. Roughly speaking, a Galois field is a finite set of elements in which we can add, subtract, multiply and invert. Before we introduce the definition of a field, we first need the concept of a simple algebraic structure, a field.

• All elements of F form an additive group with the group operation “+” and the neutral element 0.

• All elements of F except 0 form a multiplicative group with the group operation “×” and the neutral element 1.

• When the two group operations are mixed, the distributivity law holds, i.e., for all a,b,c∈F:a(b+c)=(ab)+(ac).

Galois field arithmetic is the most widely used field involving matrix operations. One can see detailed information about the Galois field and the operations performed on it in [2]. Also, you can find information on the classical cryptology benefit in [3].

In extension fields GF(2m) elements are not represented as integers but as polynomials with coefficients in GF(2). The polynomials have a maximum degree of m −1, so that there are m coefficients in total for every element. In the field GF(28), which is used in AES, each element A∈GF(28) is thus represented as

Note that there are exactly 256 = 28 such polynomials. The set of these 256 polynomials is the finite field GF(28). It is also important to observe that every polynomial can simply be stored in digital form as an 8-bit vector

In particular, we do not have to store the factors x7, x6, etc. It is clear from the bit positions to which power xi each coefficient belongs.

Fibonacci numbers are defined by the recurrence relation of Fn = Fn −1 +Fn −2 for n≥2 with the initial conditions F0 = 0 and F1 = 1. There are a lot of generalizations of Fibonacci numbers satisfied and studied by some authors. For more information one can see in [4–8]. The Fibonacci Q-matrix is defined in [9,10] as follows:

Fibonacci polynomials that belong to the large polynomial classes are defined by a recurrence relation similar to Fibonacci numbers. The Belgian mathematician Eugene Charles Catalan and the German mathematician E. Jacobsthal were studied Fibonacci polynomials in 1983. The polynomials fn(x) studied by Catalan are defined by the recurrence relation

where f0(x)=0,f1(x)=1,f2(x)=x and n≥3. Fig. 3 notice that for x = 1, fn(1)=Fn, Fn is nth Fibonacci number.

In [14], the k-order Fibonacci polynomial is defined by A. N. Philippou, C. Georghiou and G. Philippou in 1983.

The sequence of polynomials {fn(k)(x)}n=0∞ is said to be the sequel of Fibonacci polynomials of order k if f0(k)(x)=0,f1(k)(x)=1 and

fn(k)(x)={∑i=1nxk−ifn−i(k)(x)if2≤n≤k∑i=1kxk−ifn−i(k)(x)ifn≥k+1}.

Kizilates et al. studied a new generalization of convolved (p,q)−Fibonacci and (p,q)−Lucas polynomials in [4]. Also, Qi et al. gave a closed formula for the Horadam polynomials in terms of a tridiagonal determinant in 2019 in [15] and Kizilates et al. defined several determinantel expressions of generalized tribonacci polynomials and sequences in [5]. In [6], Kizilates et al. introduced new families of three-variable polynomials coupled with well-known polynomials and numbers in 2019. New families of Horadam numbers associated with finite operators and their applications were studied by Kizilates in [7].

In [16], Basu et al. introduced the generalized relations among the code elements for Fibonacci coding theory in 2009. In 2014, Basu et al. defined a new coding theory for Tribonacci matrices in [17] and they expended the coding theory on Fibonacci n-step numbers in [18]. Also, Basu et al. defined generalized Fibonacci n-step polynomials and stated a new coding theory called generalized Fibonacci n-step polynomials coding theory in [19].

Qk(x)=[xk−1xk−2xk−3⋯x1100000010000⋮⋮⋱⋱⋮⋮00⋯⋯0000⋯010]k×k

Qkn(x)= [ Fn+k−1(k)(x)xk−2Fn+k−2(k)(x)+xk−3Fn+k−3(k)(x)+⋯+Fn(k)(x)Fn+k−2(k)(x)xk−2Fn+k−3(k)(x)+xk−3Fn+k−4(k)(x)+⋯+Fn−1(k)(x)⋮⋮Fn+1(k)(x)xk−2Fn(k)(x)+xk−3Fn−1(k)(x)+⋯+Fn−k+2(k)(x)Fn(k)(x)xk−2Fn−1(k)(x)+xk−3Fn−2(k)(x)+⋯+Fn−k+1(k)(x) xk−3Fn+k−2(k)(x)+xk−4Fn+k−3(k)(x)+⋯+Fn+1(k)(x)⋯Fn+k−2(k)(x)xk−3Fn+k−3(k)(x)+xk−4Fn+k−4(k)(x)+⋯+Fn(k)(x)⋯Fn+k−3(k)(x)⋮⋮⋮xk−3Fn(k)(x)+xk−4Fn−1(k)(x)+⋯+Fn−k+3(k)(x)⋯Fn(k)(x)xk−3Fn−1(k)(x)+xk−4Fn−2(k)(x)+⋯+Fn−k+2⋯(k)(x)⋯Fn−1(k)(x) ](1)

Diskaya et al. created a new encryption algorithm (known as AES-like) by using the AES algorithm in [20]. They created the encryption algorithm by splitting the message text into 2×2 block matrices using Fibonacci polynomials.

Fibonacci polynomials have many applications in algebra. In recent years, we see that these polynomials have many uses in the field of engineering. Also, Fibonacci polynomials are used in solving differential equations. These solutions are used in engineering and science, adding new approaches to the solution of engineering problems. Mirzae and Hoseini solved singularly perturbed differential-difference equations arising in science and engineering with Fibonacci polynomials in [21]. Also, in [22], Haq et al. studied approximate solution of two-dimensional Sobolev equation using a mixed Lucas and Fibonacci polynomials.

In this paper, we generalize the encryption algorithm given in [20] and study the encryption made with the 2×2 type block matrix operation to the k×k type in Galois field. We redefine the elements of k-order Fibonacci polynomials sequences using a certain irreducible polynomial in our cryptology algorithm. The algorithm consist of four steps as in the AES encryption algorithm. The encryption algorithm defined in this algorithm is a symmetric-key algorithm in which the keys used in both encryption and decryption of encrypted text are related to each other. The encryption and decryption keys are the same like AES. So, this cryptology algorithm is called AES-like cryptology algorithm on the k-order Fibonacci polynomials.

In this chapter, we redefine the elements of k-order Fibonacci polynomial sequences using a certain irreducible polynomial in our coding algorithm. In extension fields GF(2m) elements are not represented as integers but as polynomials with coefficients in GF(2). Throughout this section, we take m = 5 for next process. Since m = 5, we consider the finite Galois field containing 32 elements in this algorithm and this Galois field is denoted as GF(25). Note that there are exactly 25 = 32 such polynomials. The set of these 32 polynomials is the finite field GF(25). Each elements of this polynomials correspond to one letter of the alphabet.

The AES encryption algorithm uses the P(x)=x8+x4+x3+x+1 polynomial as the irreducible polynomial.

In this paper, we consider the irreducible polynomials as P(x)=x5+x2+1. We can also diversify our encryption algorithm by using other irreducible polynomials.

Definition: In [8], the Fibonacci polynomial sequence {fn(x)}n≥0 is f0(x)=0,f1(x)=1 and fn+2(x)=xfn+1(x)+fn(x).

For later use the first few terms of the sequence Fibonacci polynomials can be seen in the following Table 2 and a few the irreducible polynomials for Fibonacci polynomials are given as Table 3.

Polynomials of the Galois field are equivalent of each alphabet in Table 4 is as following:

Now, we obtain our encryption algorithm in line preliminary information we have given.

• Step 1: We can consider the message text of length n and assume that each letter represents one length.

• Step 2: We can choose arbitrary value of k and n. The k-value we choose determine which order Fibonacci polynomials to use. We can create the matrix Qkn(x) in Eq. (1) according to the kand n value we have chosen. Our message text is divided into blocks according to the value k. We get matrices of k×1 type. We get a new matrix by multiplying the k×1 type matrix with the Qkn(x). Our new message is created by looking at the values in the matrix we obtained from the alphabet table.

• Step 3: We multiply the message matrix we just obtained by the invertible key matrix. In this paper, we accept the key matrix as follows:

If there is an ascending 2 letters in the text, it letters is multiplied by 2. Key matrix in 2×2:

• Step 4: The text created in the 3th step is collected sequentially with the k-order Fibonacci polynomials by starting from left and our encrypted message is created.

• Step 1: We can consider encrypted a text of length n and assume that each letter represents one length.

• Step 2: The text created is addition sequentially with the k-order Fibonacci polynomials by starting from the left and our new message is created.

• Step 3: We multiply the message matrix we just obtained by inverse of the 1. key matrix.

If there is an ascending 2 letters in the text, it letters is multiplied by 2. Inverse key matrix in 2×2:

• Step 4: We can obtain the matrix (Qkn(x))−1 according to the k and n we have chosen. Our text is divided into blocks according to the value k. We get matrices of k×1 type. We get a new matrix by multiplying the k×1 type matrix with the (Qkn(x))−1. Our new message is created by looking at the values in the matrix we obtained from the alphabet table. We can obtain our text message text.

2.3 Illustrative Examples for AES-Like Cryptology on the k-Order Fibonacci Polynomial Matrix

• Step 1: “HELLO” is 5 letters. In this example, we encrypt process by choosing n = 5 (We can choose n arbitrarily).

• Step 2: For k = 3 and n = 5, we can use Tribonacci polynomials for encryption.

Q35(x).[ HEL ]=[ x4+1x4+x+1x3+x2x3+x2x2x3+x+1x3+x+1x2+1x4+x ][ x3+1x2+1x3+x2+x ] =[ x4+x3+xx4+x3+xx3+x2+x+1 ]=[ VVM ]

Since the word “HELLO” has 5 letters, we divide it into blocks of 3×1 and 2×1. So now we encrypt the 2×1 block with the usual Fibonacci polynomial matrix.

Q25(x).[ LO ]= =[ x2+x+1x4+x2+1x4+x2+1x3 ][ x3+x2+xx4+1 ] =[ x3+x2+1x4+x2 ] =[ KR ]

• Step 3: We multiply the message matrix we just obtained by the invertible 1. Key matrix. Turn into blocks of 3s and multiply with the key matrix.

[ BBCCEG⌣KEY ][ VVM ]=[ 11xx+1x2+1x3x3+x2+1x2+1x4+x3+x2+1 ][ x4+x3+xx4+x3+xx3+x2+x+1 ] =[ x4+x3+x2+x1x2 ]=[ ZBD ]

Z+T1(x)=x4+x3+x2+x+1=QB+T2(x)=1+x2=ED+T3(x)=x4+x2+x=SX+T4(x)=x4+x2+x+1=TU¨+T5(x)=x4+x2+1=S

Q+T1(x)=x4+x3+x2+x=ZE+T2(x)=1=BS+T3(x)=x2=DT+T4(x)=x4+x3+x2=XS+T5(x)=x4+x3+1=U¨

• Step 2: We multiply the message matrix we just obtained by inverse of the 1. Key matrix.

• Step 3: We can obtain the matrix (Qkn(x))−1 according to the k and n value we have chosen. For k = 3 and n = 5; we get as

(Q35(x))−1[ VVM ]=[ 0xx3+1x3+11x4x4x+1x2 ][ x4+x3+xx4+x3+xx3+x2+x+1 ] =[ x3+1x2+1x3+x2+x ]=[ HEL ]

(Q25(x))−1[ KR ]=[ x3x4+x2+1x4+x2+1x2+x+1 ][ x3+x2+1x4+x2 ] =[ x3+x2+xx4+1 ]=[ LO ]

We have handled the example given in [20] again with the algorithm we created. The correct result was obtained as a result of the operation we have done. In addition, the encryption process performed with 2×2 block matrices in the other study was performed faster and easier with this method.

• Step 1: “PUBLIC” is 6 letters. In his example, we encrypt process by choosing n = 6 (We can choose n arbitrarily. We do not have to choose the same number of letters as the number of n in our message text to be encrypted).

• Step 2: For k = 4 and n = 6, we can use Tetranacci polynomials for encryption. We can get as

Q46(x)=[ x3x2x1100001000010 ]6 =[ x4+x3+xx3+xx3+1x4+x3+x2+x+1x4+x3+x2+x+1x4+x3+1x4+x3+1x4+xx4+xx4+x3+x+1x4+x3+x+1x4+x3x4+x3x3+x2x4+x2x3+x2+x ]

19=(10011)=x4+x+1=P24=(11000)=x4+x3=U1=(00001)=1=B14=(01110)=x3+x2+x=L10=(01010)=x3+x=I2=(00010)=x=C

Q46(x)[ PUBL ]=Q46(x)[ x4+x+1x4+x31x3+x2+x ] =[ x4+x3+x2+xx+1x3+x2+xx3+x2+x+1 ]=[ ZCLM ]

Since the word “PUBLIC” has 6 letters, we divide it into blocks of 4×1 and 2×1. So now:

Q26(x)[ IC ]=[ x4+x3+x+1x2+x+1x2+x+1x4+x2+1 ][ x3+xx ] =[ x4+x3+x+1x4+x3+x2 ]=[ WX ]

• Step 3: We multiply the message matrix we just obtained by the invertible 1. Key matrix. Turn into blocks of 3s and multiply with the key matrix.

[ BBCCEG⌣KEY ][ ZCL ]=[ 11xx+1x2+1x3x3+x2+1x2+1x4+x3+x2+1 ][ x4+x3+x2+xx+1x3+x2+x ] =[ 1x4+x2+x+1x4+x3+x ]=[ BTV ]

B+F1(4)=1=BT+F2(4)=x4+x2+x+1=TV+F3(4)=x4+x3+x+1=WH+F4(4)=1=BO¨+F5(4)=x4+x3+x2=XO¨+F6(4)=x3+x=I

B+F1(4)=1=BT+F2(4)=x4+x2+x+1=TW+F3(4)=x4+x3+x=VB+F4(4)=1+x3=HX+F5(4)=x4+x=O¨I+F6(4)=x4+x=O¨

• Step 2: We multiply the message matrix we just obtained by inverse of the 1. Key matrix.

• Step 3: We can obtain the matrix (Qkn(x))−1 according to the k and n value we have chosen. For k = 4 and n = 6; we get as

AES (Advanced Encryption Standard) is a standard offered for encryption of electronic data. The AES cipher is almost identical to the block cipher Rijndael. The Rijndael block and key size vary between 128, 192 and 256 bits. However, the AES standard only calls for a block size of 128 bits. Hence, only Rijndael with a block length of 128 bits is known as the AES algorithm. In the remainder of this page, we only discuss the standard version of Rijndael with a block length of 128 bits.

The Rijndael algorithm perform encryption with the help of polynomials in Galois fields. We have obtained a new encryption algorithm by generalizing the previous studies. In this paper, we generalized the encryption algorithm given in [20] and studied the encryption made with the 2×2 type block matrix operation to the k×k type in Galois field. We redefined the elements of k-order Fibonacci polynomials sequences using a certain irreducible polynomial in our cryptology algorithm. The algorithm consist of four steps as in the AES-like encryption algorithm. The encryption algorithm defined in this algorithm is a symmetric-key algorithm in which the keys used in both encryption and decryption of encrypted text are related to each other. The encryption and decryption keys are the same like AES. So, this cryptology algorithm is called AES-like cryptology algorithm on the k-order Fibonacci polynomials. In this way, researchers can perform the encryption process based on arbitrary choices.

In this paper, we present the mathematical basis for understanding the design rationale and the features that follow the description itself. Then, we define AES-like encryption by giving the encryption method and its implementation.

Funding Statement: This work is supported by the Scientific Research Project (BAP) 2020FEBE009, Pamukkale University, Denizli, Turkey.

Conflicts of Interest: The authors declare that there are no conflicts of interest regarding the publication of this article.

References

1. Avaroglu, E., Koyuncu, I., Ozer, A. B., Turk, M. (2015). Hybrid pseudo-random number generator for cryptographic systems. Nonlinear Dynamics, 82(1–2), 239–248. DOI 10.1007/s11071-015-2152-8. [Google Scholar] [CrossRef]

2. Paar, C., Pelzl, J. (2009). Understanding cryptography: A textbook for students and practitioners. London: Springer Science, Business Media. [Google Scholar]

3. Klima, R. E., Sigmon, N. P. (2012). Cryptology: Classical and modern with maplets. New York: Chapman and Hall/CRC. [Google Scholar]

4. Kizilates, C., Tuglu, N. (2017). A new generalization of convolved (p,q)-Fibonacci and (p,q)-Lucas polynomials. Journal of Mathematics and Computer Science, 7, 995–1005. DOI 10.28919/jmcs/3476. [Google Scholar] [CrossRef]

5. Kizilates, C., Du, W. S., Fi, Q. (2022). Several determinantal expressions of generalized tribonacci polynomials and sequences. Tamkang Journal of Mathematics, 53, 17–35. DOI 10.5556/j.tkjm.53.2022.3743. [Google Scholar] [CrossRef]

6. Kizilates, C., Cekim, B., Tuglu, N., Kim, T. (2019). New families of three-variable polynomials coupled with well-known polynomials and numbers. Symmetry, 11(264), 1–13. DOI 10.3390/sym11020264. [Google Scholar] [CrossRef]

7. Kizilates, C. (2021). New families of Horadam numbers associated with finite operators and their applications. Mathematical Methods in the Applied Science, 3(4), 161. DOI 10.1002/mma.7702. [Google Scholar] [CrossRef]

8. Koshy, T. (2001). Fibonacci and Lucas numbers with applications. A Wiley-Interscience Publication, John Wiley & Sons, Inc. [Google Scholar]

9. Gould, H. W. (1981). A history of the Fibonacci Q-matrix and a higher-dimensional problem. The Fibonacci Quarterly, 19(3), 250–257. DOI 10.1177/001316448104100337. [Google Scholar] [CrossRef]

10. Hoggat, V. E. (1969). Fibonacci and Lucas numbers. Palo Alto: Houghton-Mifflin. [Google Scholar]

11. Stakhov, A. P. (1999). A generalization of the Fibonacci Q-matrix. Reports of the National Academy of Sciences of Ukraine, 9, 46–49. [Google Scholar]

12. Stakhov, A. P., Mssinggue, V., Sluchenkov, A. (1999). Introduction into Fibonacci coding and cryptography. Kharkov: Osnova. [Google Scholar]

13. Vajda, S. (1989). Fibonacci and Lucas numbers and the golden section theory and applications. Lancashire, UK: Ellis Harwood Limitted. [Google Scholar]

14. Philippou, A. N., Geoughiou, C., Philippou, G. (1983). Fibonacci polynomials of order k, multinomial expansions and probability. International Journal of Mathematics and Mathematical Sciences, 6(3), 545–550. DOI 10.1155/S0161171283000496. [Google Scholar] [CrossRef]

15. Qi, F., Kizilates, C., Du, W. S. (2019). A closed formula for the Horadam polynomials in terms of a tridiagonal determinant. Symmetry, 11(6), 8. DOI 10.3390/sym11060782. [Google Scholar] [CrossRef]

16. Basu, M., Prasad, B. (2009). The generalized relations among the code elements for Fibonacci coding theory. Chaos Solitons and Fractals, 41(5), 2517–2525. DOI 10.1016/j.chaos.2008.09.030. [Google Scholar] [CrossRef]

17. Basu, M., Das, M. (2014). Tribonacci matrices and a new coding theory. Discrete Mathematics Algorithms and Applications, 6(1), 1450008. DOI 10.1142/S1793830914500086. [Google Scholar] [CrossRef]

18. Basu, M., Das, M. (2014). Coding theory on Fibonacci n-step numbers. Discrete Mathematics Algorithms and Applications, 6(2), 1450017. DOI 10.1142/S1793830914500177. [Google Scholar] [CrossRef]

19. Basu, M., Das, M. (2017). Coding theory on generalized Fibonacci n-step polynomials. Journal of Information & Optimization Sciences, 38(1), 83–131. DOI 10.1080/02522667.2016.1160618. [Google Scholar] [CrossRef]

20. Diskaya, O., Avaroglu, E., Menken, H. (2020). The classical AES-like cryptology via the Fibonacci polynomial matrix. Turkish Journal of Engineering, 4(3), 123–128. DOI 10.31127/tuje.646926. [Google Scholar] [CrossRef]

21. Mirzaee, F., Hoseini, S. F. (2013). Solving singularly perturbed differential-difference equations arising in science and engineering with Fibonacci polynomials. Results in Physics, 3(5), 134–141. DOI 10.1016/j.rinp.2013.08.001. [Google Scholar] [CrossRef]

22. Haq, S., Ali, I. (2021). Approximate solution of two-dimensional Sobolev equation using a mixed Lucas and Fibonacci polynomials. Engineering with Computers, 21, 366–378. DOI 10.1007/s00366-021-01327-5. [Google Scholar] [CrossRef]