Heritage and carob trees: Where the monumental and landscape intersect

1.   Introduction

Cryptography was widely used in military, diplomatic, and government applications until the 1970s. In the 1980s, the telecommunications and financial industries installed hardware cryptographic devices. The mobile phone system was the first cryptographic application in the late 1980s. Nowadays, everyone uses cryptographic applications in their daily lives. Our daily lives commonly depend on the secure transmission of information and data. Online shopping, cell phone messages and calls, ATMs, electronic mail, facsimile, wireless media, and data transfer over the internet all require a system to maintain the secrecy and integrity of private information. Cryptography offers a mechanism for everyone to interact safely in a hostile environment. Sensitive data is significantly aided by cryptography. Communication is encrypted to guarantee that its meaning is hidden, preventing anybody who reads it from understanding something regarding it unless somebody else manages to decrypt it ^[1].

Substitution boxes, also known as S-boxes, are a key component of modern cryptographic algorithms. Shannon suggested the notion of an S-box in 1949 ^[2]. S-boxes are used to replace one group of bits with another group of bits to provide confusion and non-linearity in the encryption process. The substitution boxes are designed to make it difficult for attackers to determine the relationship between the input and output of the encryption algorithm. This makes it harder for attackers to crack the encryption, providing increased security for sensitive data. S-boxes have been used in a wide range of cryptographic algorithms, including the Advanced Encryption Standard (AES), the Data Encryption Standard (DES), and the Blowfish encryption algorithm. The design of S-boxes is critical to the security of these algorithms, and much research has been done to create S-boxes that are resistant to attacks. The design of S-boxes typically involves a combination of mathematical analysis, computational complexity, and heuristics to produce a strong S-box that is difficult to break. One of the key properties of S-boxes is their non-linearity. Non-linearity ensures that small changes in the input produce large changes in the output, making it difficult for attackers to determine the relationship between the input and output of the encryption algorithm. This nonlinearity is achieved through careful design of the S-box, often involving complex mathematical functions that ensure that the output is as different as possible from the input. The security of S-boxes has been the subject of much research, with many attacks developed over the years to break them. One of the most famous attacks on S-boxes is the differential cryptanalysis attack, which was developed in the 1990s. This attack involves analyzing the differences between pairs of inputs to the S-box and the corresponding differences in the output. By analyzing these differences, attackers can learn more about the S-box and potentially break the encryption ^[3,4,5].

Many scholars employed diverse algebraic and statistical frameworks to confound data and produce S-boxes. In ^[6], the authors suggested S-boxes over the permutation of the symmetric group. Javeed and Shah utilized a chaotic dynamical system and symmetric group to construct the non-linear component of a block cipher ^[7]. Meanwhile, the authors of ^[8] described an S-box constructed using the subgroup of the Galois field. In ^[9], the authors proposed a dynamic S-box using novel chaotic map. In ^[10], a new scheme for constructing S-boxes was presented based on the linear fractional transformation and permutation function. The Mobius group and finite field were used to construct an S-box in ^[11], while ^[12] proposed an S-box based on a nonlinear chaotic map. Sajjad and Shah designed a pair of nonlinear components of a block cipher over Gaussian integers in ^[13], and ^[14] presented fundamental results of cyclic codes and decoding algorithms over octonion integers. Differential cryptanalysis of DES-like cryptosystems was developed by the authors of ^[15], while Quiroga and Cantón proposed generating dynamical S-boxes for block ciphers using an extended logistic map in ^[16]. Tang and Liao designed a new method of dynamical S-boxes based on discretized chaotic maps ^[17]. While Chen and Liao extended this method to obtain S-boxes based on three-dimensional chaotic Baker maps ^[18]. A novel approach for strong S-Box generation algorithm design based on a chaotic scaled zhongtang system was presented by Çavuşoğlu and Zengin in ^[19]. Siddiqui and Naseer developed a novel scheme of substitution-box design based on modified Pascal's triangle and elliptic curve ^[20]. Farhan and Ali designed a new S-box generation algorithm based on the multistability behavior of a plasma perturbation model ^[21]. In ^[22], the authors approached the S-boxes and permutation, substitution-based encryption. The authors constructed block ciphers based on chaotic maps in ^[23,24].

Quaternion integers are an extension of complex numbers that have gained significant attention in various fields of physics and engineering due to their unique properties. They are a type of hypercomplex number that can be used to describe rotations in 3D space and have applications in areas such as computer graphics, robotics, and quantum mechanics. The concept of quaternion integers was introduced by the Irish mathematician William Rowan Hamilton in 1843. He famously impressed the fundamental formula for quaternions onto a stone bridge in Dublin. Since then, quaternion algebra has been extensively studied, and its applications have been explored ^[25,26,27]. In ^[28], Ozen and Guzeltepe constructed cyclic codes over certain finite quaternion integer rings. Shah and Rasool presented codes over quaternion integers ^[29]. In ^[30], the authors constructed cyclic codes over quaternion integers and developed a decoding algorithm. These quaternion structures can be helpful for the construction of S-boxes.

This article presents a novel approach for designing a pair of nonlinear components for a block cipher over QI. Quaternions are an extension of complex numbers that allow for more complex arithmetic operations, which can enhance the security of the cipher. We demonstrate the effectiveness of our proposed design by implementing it in a block cipher and conducting extensive security analysis. Quaternion integers give pair of substitution boxes (S-boxes) after fixing parameters but other structures give only one S-box after fixing parameters. Our results show that the proposed design provides superior security compared to existing designs, two making a promising approach for future cryptographic applications.

The rest of this article is organized as follows. Section 2 provides an overview of the background and related work of quaternion integers. Section 3 presents our proposed design for a pair of nonlinear components, including a detailed description of the operations. Analysis of the proposed S-boxes including nonlinearity, bit independence criterion, strict avalanche criterion, linear approximation probability, and differential approximation probability investigated in Section 4. The comparison of the proposed S- boxes with some of the existing S- boxes are given in Section 5. Conclusions and future directions are given in Section 6.

2.   Preliminaries

The important ideas and fundamental conclusions that will be employed in the analysis of subsequent sections are presented in this section. Prior to that, we should review the definition of quaternion integers, their addition and multiplication, their residue class, and other associated findings.

2.1.   Quaternion integers

By following [28, Section 2], let $H\left(\mathbb{R}\right)$ be the Hamilton Quaternion algebra over the real number $\mathbb{R}$ is the non-commutative but associative unital algebra if it satisfies the following conditions.

• $H\left(\mathbb{R}\right) = \{{b}_{0}+{b}_{1}i+{b}_{2}j+{b}_{3}k:{b}_{0}, {b}_{1}, {b}_{2}, {b}_{3}\in \mathbb{R}\}$ is free $\mathbb{R}$ module.

• The multiplicative identity is 1.

• ${i}^{2} = {j}^{2} = {k}^{2} = -1~~ and~~ jk = -kj = i, ki = -ik = j, ij = -ji = k.$

The Quaternion integer ring $H\left(\mathbb{Z}\right) = \{{b}_{0}+{b}_{1}i+{b}_{2}j+{b}_{3}k:~~ for~~ all~~ {b}_{0}, {b}_{1}, {b}_{2}, {b}_{3}\in \mathbb{Z}\}$ contained in $H\left(\mathbb{R}\right)$, where $\mathbb{Z}$ is the ring of integers. If ${q = b}_{0}+{b}_{1}i+{b}_{2}j+{b}_{3}k$ is a Quaternion integer, then $\stackrel{-}{q}{ = b}_{0}-{b}_{1}i-{b}_{2}j-{b}_{3}k$ is the Quaternion conjugate of $q$. Let $N\left(q\right) = q\stackrel{-}{q} = {b}_{0}^{2}+{b}_{1}^{2}+{b}_{2}^{2}+{b}_{3}^{2}$ be the norm of $q$. A Quaternion integer $q$ has only two parts one is the scalar part (S.P) ${b}_{0}$ and the other is the vector part (V.P) ${b}_{1}i+{b}_{2}j+{b}_{3}k$. In Quaternion integer's commutative property of multiplication does not hold. It is possible only in case of two vector parts of quaternion integers are parallel.

Define $H\left(K\right)$ as: $H\left(K\right) = \{a+bU:a, b\in \mathbb{Z}\},$ Where $U$ is $(i+j+k)$. Hence $H\left(K\right)$ is a subring of the Quaternion integer ring $H\left(\mathbb{Z}\right)$, and also the commutative property of multiplication holds over $H\left(K\right)$.

2.1.1.   Sum and product of two quaternion integers

Let ${q}_{1} = {c}_{0}+{c}_{1}i+{c}_{2}j+{c}_{3}k$ and ${q}_{2} = {d}_{0}+{d}_{1}i+{d}_{2}j+{d}_{3}k$ be the two quaternion integers then, their sum ${q}_{1}+{q}_{2}$ and product ${q}_{1}{q}_{2}$ will be also a quaternion integer as;

Theorem: In [28, Section 2], the set of natural numbers for each odd rational prime $p$, there is a prime $\delta \in H\left(\mathbb{Z}\right)$, such that $N\left(\delta \right) = p = \delta \stackrel{-}{\delta }$. In particular, $p$ is not prime in $H\left(\mathbb{Z}\right)$.

Theorem: In [29, Section 2], let $\delta \in H\left(\mathbb{Z}\right)$ be prime in $H\left(\mathbb{Z}\right)$ if and only if $N\left(\delta \right)$ be prime in $\mathbb{Z}$.

2.1.2.   Residue class of quaternion integers

In [30, Section 2], let $H(K{)}_{\delta }$ be the residue class of $H\left(K\right)$ modulo $\delta$, where $\delta = a+bU$. Then, the modulo function

Where $z\in H(K{)}_{\delta }$. The previous equation involves rounding the number of [.] to the nearest integer. To accomplish QI rounding, it is necessary to round the coefficient of the vector part (C.V.P) and scalar part (S.P) independently to the nearest integer.

Theorem: In [30, Section 2], let $\delta$ be a quaternion prime, and the number of quaternion integers modulo $\delta$ is the norm of $\delta.$ If $\alpha \ne 0\left(mod~~ \delta \right)$, then ${\alpha }^{p-1}\equiv 1\left(mod~~ \delta \right).$

Remark: The group generated by $< \alpha >$ in the above Theorem is named ${G}^{*}.$

3.   Redesign of Pair of $\mathit{n}\times \mathit{n}$ S-boxes over Quaternion Integers

Multiple methods can be employed to cause confusion inside a security system. The S-box is a nonlinear component of a cryptographic algorithm. The S-boxes are generally formed by the QI class or the multiplicative cyclic group. As a result, it is feasible to create a variety of S-boxes across the residue class of QI, which presents a fantastic outlook for the development of secure and consistent cryptosystems. The subsequent procedures are useful for constructing S-boxes over the residue class of QI as;

Step 1: Construct a cyclic group ${G}^{*}$ of order $p-1$ over the residue class of QI.

Step 2: Apply permutation through affine mapping as $g\left(x\right) = (sx+t)\left(mod~~ {2}^{n}\right)$

Where $t\in {G}^{*}$ and $s$ be the unit element of ${G}^{*}.$

Step 3: Separate real parts (R.P) and coefficients of the vector parts (C.V.P) of Step 2.

Step 4: Apply modulo ${2}^{n}$ over the separated parts of Step 3.

Step 5: Select the first ${2}^{n}$ non-repeated elements from the elements of Step 4.

Step 6: Select the first ${2}^{n}$ non-repeated elements from the S.P and also select the first ${2}^{n}$ non-repeated elements from the C.V.P of Step 3.

Step 7: Get pair of nonlinear components of a block cipher.

The construction of S-boxes by Quaternion integers provides us with better performance than instead of S-boxes by using other structures like chaotic maps, elliptic curves, finite fields, Gaussian integers, Eisenstein integers, etc.

3.1.   Pair of $4\times 4$ S-boxes over the residue class of quaternion integers

Let $\delta = 16+i+j+k = (\mathrm{16, 1}, \mathrm{1, 1})$, $p = N\left(\delta \right) = {16}^{2}+{1}^{2}+{1}^{2}+{1}^{2} = 259,$ and $\beta = 5+i+j+k = (\mathrm{5, 1}, \mathrm{1, 1})$, then the cyclic group generated by $\beta$ shown in Table 1.

Select the first 16 non-repeated elements from the last two columns of Table 1, then apply the affine permutation mapping, $f\left(x\right) = \left(4x+1\right)\left(mod16\right),$ and get the pair of S-boxes separately in Table 2 and 3.

3.2.   Pair of $8\times 8$ S-boxes over the residue class of quaternion integers

Let $\delta = 68+31i+31j+31k = \left(68, 31, 31, 31\right), p = N\left(\delta \right) = 7507,$ and $\beta = 1+17i+17j+17k = \left(\mathrm{1, 17, 17, 17}\right)$, then the cyclic group generated by $\beta$ shown in Table 4;

Select the first 256 non-repeated elements from the real part of Table 4. Then apply the affine permutation map $g\left(x\right) = \left(121x+166\right)\left(mod~~ 256\right),$ and get the S- box from the scalar part of QI in Table 5.

Select the first 256 non-repeated elements from the imaginary part of Table 4. Then apply the affine permutation map $g\left(x\right) = \left(37x+120\right)\left(mod~~ 256\right),$ and get the S-box for the C.V.P of QI in Table 6.

3.3.   Inverse S-boxes

The S-boxes $A,$ and $B$ in $3.1.2$ are invertible and bijective. The procedure of inverse S-boxes over the residue class of GI is defined by applying inverse permutation through the following affine mapping $h\left(x\right) = \left(ux+v\right)\left(mod~~ {2}^{n}\right),$ where $u$ is the multiplicative inverse of $s$ under modulo ${2}^{n}$ and $v$ is the additive inverse of $ut$ under modulo ${2}^{n}.$

The Inverse S-box of A is defined by the map $, {h}_{1}\left(x\right) = (201x+143)\left(mod~~ 256\right)$ in Table 7.

The inverse S-box of B is defined by the map $, {h}_{2}\left(x\right) = (173x+24)\left(mod~~ 256\right)$ in Table 8.

4.   Analysis of S-boxes

The analysis of S-boxes is a crucial part of cryptanalysis, ensuring the security of encrypted data. Nonlinearity, output distribution, and resistance to attacks are all important aspects of S-box design, and their analysis requires mathematical and statistical tools to measure their effectiveness ^{[31,32,33,34,35,36,37,38,39,40]}. There is the following analysis.

4.1.   Nonlinearity

Nonlinearity (NL) is a fundamental property of many natural and artificial systems, and it describes the behavior of a system that is not proportional to its inputs. In other words, small changes in inputs may lead to significant changes in outputs, and the relationship between input and output is not a straight line. Nonlinearity is observed in a wide range of phenomena, such as fluid dynamics, electrical circuits, and signal processing. Nonlinear systems can exhibit complex behavior, including chaotic dynamics, oscillations, and bifurcations, and they are often more difficult to analyze and control than linear systems. Nonlinearity is a critical concept in many fields, including physics, engineering, economics, and biology, and it plays a crucial role in understanding the behavior of complex systems and designing effective control strategies. The upper bound of NL for the S-box is $N\left(f\right) = {2}^{n-1}-{2}^{\frac{n}{2}-1}$ ^[26]. The optimal value of the NL of the S-box is 120. The NL results of the proposed $8\times 8$ S- boxes $A,$ and $B$ are given in Table 9.

The proposed S-boxes A and B exhibit a maximum nonlinearity of 108, as well as a minimum nonlinearity of 106. Additionally, the average nonlinearity of both S-boxes A and B is calculated to be 107.00.

4.2.   Bit independent criterion

The bit-independent criterion (BIC) is a measure used in cryptanalysis to evaluate the security of substitution boxes, or S-boxes, used in block ciphers. The criterion is designed to assess the strength of an S-box against differential cryptanalysis, which is a type of attack used by cryptanalysts to recover the key used in encryption. The bit-independent criterion measures the ability of an S-box to satisfy certain properties that make it resistant to differential cryptanalysis. Specifically, the criterion evaluates whether the S-box is balanced, has high nonlinearity, and is immune to linear attacks. A balanced S-box ensures that for any input, there is an equal number of output bits with a value of 1 and 0. High nonlinearity ensures that small changes in input bits result in significant changes in output bits, making it difficult for attackers to deduce the key used in encryption. Finally, immunity to linear attacks ensures that the S-box cannot be easily broken using linear equations. To evaluate an S-box using the bit-independent criterion, a differential characteristic is chosen, and the expected value of the characteristic is computed. Next, the number of pairs of inputs that satisfy the differential characteristic is counted, and the difference between this value and the expected value is measured. If this difference is close to zero, the S-box is said to satisfy the bit-independent criterion ^[26]. The average value of BIC is $\frac{1}{2}.$ The BIC analysis with the pair of proposed S-boxes $A$ and $B$ are given in Tables 10 and 11. The BIC of the proposed S-boxes generated by QI is up to the standard in the sense of encryption strength.

The proposed S-boxes (A, B) have been evaluated using the bit-independent criterion (BIC), which measures the S-box's resistance to differential cryptanalysis. The BIC values of the S-boxes have been calculated as follows: the maximum BIC value for both S-boxes A and B is 0.6094, while the minimum BIC value for both is 0.375. The average BIC value for both S-boxes A and B is 0.5054.

4.3.   Linear approximation probability

Linear approximation probability (LAP) is a measure used in cryptanalysis to evaluate the security of substitution boxes, or S-boxes, used in block ciphers. The measure evaluates the probability of a linear approximation of an S-box being satisfied, where the linear approximation is a linear equation that approximates the behavior of the S-box. Linear approximation probability is based on the idea that a good S-box should not be easily modeled using linear equations. If an S-box can be modeled using a linear equation, it is vulnerable to linear attacks, where an attacker can use the linear equation to recover the key used in encryption. To evaluate the linear approximation probability of an S-box, a linear approximation is chosen, and the expected value of the linear approximation is computed. Next, the number of pairs of inputs that satisfy the linear approximation is counted, and the difference between this value and the expected value is measured. If this difference is close to zero, the S-box is said to have a low linear approximation probability and is considered to be resistant to linear attacks. The linear approximation probability of an S-box is closely related to its nonlinearity, which is another measure used to evaluate the security of S-boxes. A high nonlinearity implies a low linear approximation probability, and vice versa. However, nonlinearity measures the S-box's resistance to all types of attacks, while linear approximation probability focuses specifically on linear attacks ^[26]. The maximum values of LAP of proposed S-boxes are given in Table 12, which are not so bad against linear attacks.

4.4.   Differential approximation probability

The proposed S-boxes have been evaluated using differential approximation probability (DAP), which is a measure used in cryptanalysis to evaluate the security of substitution boxes (S-boxes) against differential attacks. The DAP value of an S-box measures the probability of a differential approximation of the S-box being satisfied. In the case of the proposed S-boxes, the DAP values were computed by selecting a differential approximation and counting the number of input-output pairs that satisfy the differential approximation. This count was then divided by the total number of possible input-output pairs, giving the DAP value. The DAP values of the proposed S-boxes were compared with those of existing S-boxes from the literature. The results showed that the proposed S-boxes have a lower DAP value than some existing S-boxes, indicating that they are more resistant to differential attacks. The DAP results of proposed S-boxes $A$ and $B$ are given in Tables 13 and 14.

The maximum DAP values of the proposed S-boxes $A$ and $B$ are 0.039. The comparison of the DAP values of the proposed S-boxes with the S-boxes on different structures from the literature is presented in the comparison section.

4.5.   Strict avalanche criterion

The strict avalanche criterion (SAC) is an important concept in the field of cryptography and information theory. It is a mathematical property that measures the sensitivity of a cryptographic function to small changes in the input. In other words, it determines how much the output of the function changes when a single bit of the input is flipped. The SAC is a fundamental requirement for the security of cryptographic algorithms. A function that satisfies the SAC is said to be an "avalanche effect" because the output of the function changes drastically (like an avalanche) when the input is changed even slightly. This means that an attacker cannot predict the output of the function even if they know a small part of the input. The SAC is typically measured using a metric called the "avalanche distance, " which is the proportion of output bits that change when a single input bit is flipped. A function that satisfies the SAC should have an avalanche distance of at least 50% (i.e., half of the output bits should change when a single input bit is flipped). This ensures that the function is highly sensitive to input changes and provides a high level of security. There are several techniques for evaluating the SAC of a cryptographic function, including statistical testing and algebraic analysis. These techniques are used to ensure that the function meets the strict avalanche criterion and is secure against attacks. The SAC results of the proposed S-boxes $A$ and $B$ are given in Tables 15 and 16. We have come to a close that the value of the proposed S-boxes is approximately equal to $\frac{1}{2}.$ So, we conclude that we can make use of proposed S-boxes in block cipher for secure communication.

The proposed S-boxes A and B have maximum Strict Avalanche Criterion (SAC) values of 0.594 each, and minimum SAC values of 0.406 each. On average, the SAC values of S-boxes A and B are 0.504 each. These results indicate that the proposed S-boxes are very close to achieving the optimal possible SAC value. Therefore, we can conclude that the SAC of the proposed S-boxes meets the required criteria.

5.   Comparison

The former tests are performed on well-known S-boxes over EC, chaotic maps, etc presented in ^{[18,19,20,21,22,23,24]} in order to compare them with the proposed S-boxes $A$ and $B$ over QI. Table 17 shows the results of the EC, CM, and QI analyses for the various parameters. It is discovered that the proposed S-boxes have a higher nonlinearity value than EC, CM, and other S-boxes. The intriguing features of the proposed technique provide S-boxes pair at a time by fixing three parameters $a, b,$ and $p$. However, the other structures have one S-box at a time by fixing three parameters $a, b,$ and $p$. Table 17 and Figure 1 show the nonlinearity of the proposed S-box. The proposed S-box LAP results are lower than those presented in ^{[18,19,20,21,22,23,24]} and Figure 2. As a result, the proposed S-boxes generate more data confusion and are more resistant to linear attack than ^{[18,19,20,21,22,23,24]}. The proposed S-boxes' SAC and BIC results are comparable to those of other S-boxes used in Table 17 and Figure 2. As a result, the S-box generated by the proposed technique and the S-boxes shown in Table 17 cause equal magnitude diffusion in the data. The proposed DAP is comparable to the DAP of S-boxes in ^{[18,19,20,21,22,23,24]} and Figure 2. Thus, when compared to the others, the proposed technique generates an S-box with high resistance to differential cryptanalysis.

6.   Conclusions and future directions

The proposed design methodology for the nonlinear substitution function of a block cipher based on quaternion integers has shown promising results in terms of enhancing the security of cryptographic applications. The use of quaternions in the design allows for more complex arithmetic operations, improving the cipher's confusion and diffusion properties. The implementation of the proposed design in a block cipher and extensive security analysis confirms its superiority over existing designs.

Future research directions could involve investigating the impact of varying parameters of the proposed design, such as the number of rounds and key size, on the cipher's security. Additionally, exploring the potential of combining the proposed design with other cryptographic techniques, such as key exchange or digital signatures, could lead to the development of more secure and versatile cryptographic systems.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Researchers supporting project number (RSP 2023R472), King Saud University, Riyadh, Saudi Arabia.

Conflict of interest

The authors declared that they had no conflict of interest.