Encryption is a method of encoding data so that only authorized parties can read or access that data. With the fast improvement of digital data exchange in electronic way, Information Security is becoming much more important in data storage and transmission. In this paper, the authors work on improving the security of data using a combination of Hill cipher and a Transposition cipher (G_p) , the plaintext will be encrypted using ordinary Hill cipher technique and encrypted again using G_p cipher there by producing a more complex ciphertext that will be very difficult for cryptanalyst to intrude, and the decryption process is done in two phases, the first decryption will return the ciphertext of the ordinary Hill cipher method and the second decryption will return the original plaintext.

Cryptography is the study of secure communications techniques that allow the sender and intended recipient of a message to view its contents. The term is derived from the Greek word kryptos, which means hidden. It is closely associated to encryption, which is the act of scrambling ordinary text into what is known as cipher text and then back upon required which is known as decryption, this is done primarily in two ways, one to change the position of letters or words in a message known as transposition and the other is by substitution of letters by different ones known as substitution respectively, A “substitution” cipher replaces plaintext symbols with other systems to produce cipher text, as a simple example, the plaintext might be “CONGRATULATIONS” when the letters (C,O,N,G,R,A,T,U,L,A,T,I,O,N,S) are replaced (C=E,O=Q,N=P,G=I,R=T,A=C,T=V,I=K,S=U) the text becomes “EQPITCVWVCVKQPU” respectively. With a transposition cipher, we permute the places where the plaintext letters sit. What this means is that we do not change the letters but rather move them around, transpose them, without introducing new letters. Here is a simple illustration. Suppose that we have seven letters in our plaintext, and the following is a permutation that tells us how to move the seven positions around.

Now if we interchange the numbers, then we are getting our cipher text as in

We have the cipher text as “OECWLEM”.

Transposition (permutation) pattern have been used in the past decade to study mathematical structures. For instance [2, 3, 21] and [4] studied the concept of permutation pattern using some elaborate scheme to determine the order of precedence and the position of each of the elements in a finite set of prime size. The science of cryptography can be traced back to 2000BC in Egypt. Subsequently many research on transposition and substitution ciphers were conducted by different researchers such as [11, 13] and [15]. Many discussions on transposition and substitution ciphers were made [5, 7, 9, 12] and [17] evaluates the security of transposition ciphers using stack approaches, [1, 20] and [22] discusses a combination of two independent ciphers for a better securing of a data over a communication channels, [4], [6], [8] and [10] investigated enhancement of Ceaser cipher method, [15] discusses an approaches in improving transpositions cipher systems, [16] on modified Ceaser cipher for a better security situations, Azzam and [18] discusses a strong cipher text by combining Hill and Substitution Ciphers, and [14] on modification of an Affine ciphers algorithm for cryptography password. Cryptographic techniques uses two fundamental systems which are symmetric (secret key) and asymmetric (public key), in this study we use a symmetric key for both encryption and decryption. In 2006, [9] using the concept of Catalan numbers a new scheme of generating function for prime numbers (p ≥ 5) was developed. And furthermore some new studies on the algebraic theoretic properties were been investigated by [19, 20] and [23] the generating function was defined as, w_𝐩 = {w₁,w₂, … ,w_p−1} for p ≥ 5such that $w_i = \left(\left(1\right)\left(1+i\right)mp\left(1+ 2i\right)mp\dots .. \left(1 + \left(p-1\right)i\right)mp\right)$ where mp ≔ modulop. Many algebraic properties of 𝐆_𝐩 were been investigated, and also cryptographic aspect of G_p were been investigated by [2] and [18].

The concept of Hill cipher and Transposition cipher are necessary tools for this study, they were presented in this section.

2.1. Preliminaries

Definition 2.1 Plaintext: - Plaintext is the original text from the sender’s end

Definition 2.2 Cipher: Cipher is a systematic mathematical method for encryption and decryption.

Definition 2.3 Ciphertext: Ciphertext is encrypted text transformed from plaintext using an encryption algorithm

Definition 2.4 Encryption is a process of transforming information that usually are plaintext using an algorithm (known as cipher) to make it unreadable to anyone except those who have the special knowledge known of the key.

Definition 2.5 Decryption: Is the process of converting cipher text to plaintext using a cipher and a key.

Definition 2.6 Key: Is a relatively small piece of information that is used by an algorithm to transform a plaintext into the ciphertext during encryption or a ciphertext into the plaintext during decryption.

Definition 2.7 Modulo arithmetic: A modulo of a number in terms of another number (i.e. a mod b) for a, b integers means that, if a number a is divided by b, it gives another number and a remainder then the remainder is the answer. E.g. If a mod b = r, then it implies that ab = C + r. where C is the answer. E.g. 80 mod 26 = 2. As in [2].

Definition 2.8 Padding: Is the addition of characters in a permutation when the letters are scarce. As in [4].

Definition 2.9 Hill cipher: Hill cipher is a polygraphic substitution cipher based on linear algebra, invented by Lester S. Hill in 1929, to encrypt a message, each block of n letters (n-component vector) is multiplied by an invertible “n x n matrix”, against modulus 26. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption.

Example. Let the plaintext message be “HELP” and let “$K=\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)$” be the key invertible matrix to be used.

Then, this plaintext is represented by two pairs $\left(\begin{array}{c}H\\ E\end{array}\right),\left(\begin{array}{c}L\\ P\end{array}\right)\to \left(\begin{array}{c}7\\ 4\end{array}\right),\left(\begin{array}{c}11\\ 15\end{array}\right)$

1. Encryption stage of Hill cipher, in encryption, the key multiplies the n-component vectors.

C=KP, where K is key, P is plaintext and C is the resulting plaintext.

Then we compute $\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)\left(\begin{array}{c}7\\ 4\end{array}\right)\equiv \left(\begin{array}{c}7\\ 8\end{array}\right)\left(mod26\right)and \left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)\left(\begin{array}{c}11\\ 15\end{array}\right)\equiv \left(\begin{array}{c}0\\ 19\end{array}\right)\left(mod26\right)$

Then, $\left(\begin{array}{c}7\\ 8\end{array}\right),\left(\begin{array}{c}0\\ 19\end{array}\right) \to \left(\begin{array}{c}H\\ I\end{array}\right),\left(\begin{array}{c}A\\ T\end{array}\right)$ the ciphertext of “HELP = HIAT”

1. Decryption stage of Hill cipher, in decryption, inverse key multiplies n-component vectors.

P=K^-1C where P is the resulting plaintext, k^-1 is the inverse key matrix and C is the cipher text

Then, ${\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)}^{-1}\equiv \left(\begin{array}{cc}15& 17\\ 20& 9\end{array}\right)\left(mod26\right)$ and $HIAT\mathrm{ }\to \left(\begin{array}{c}H\\ I\end{array}\right),\left(\begin{array}{c}A\\ T\end{array}\right)\to \left(\begin{array}{c}7\\ 8\end{array}\right),\left(\begin{array}{c}0\\ 19\end{array}\right)$

Then we compute $\left(\begin{array}{cc}15& 17\\ 20& 9\end{array}\right)\left(\begin{array}{c}7\\ 8\end{array}\right)\equiv \left(\begin{array}{c}7\\ 4\end{array}\right)\left(mod26\right)$ and $\left(\begin{array}{cc}15& 17\\ 20& 9\end{array}\right)\left(\begin{array}{c}0\\ 19\end{array}\right)\equiv \left(\begin{array}{c}11\\ 15\end{array}\right)\left(mod26\right)$

Therefore, $\left(\begin{array}{c}7\\ 4\end{array}\right),\left(\begin{array}{c}11\\ 15\end{array}\right)\to \left(\begin{array}{c}H\\ E\end{array}\right),\left(\begin{array}{c}L\\ P\end{array}\right)\to HELP$. The receiver of the message can now read the cipher text HIAT as HELP.

Definition 2.10 Cryptanalysis: Is the study of principles and methods of transforming an unintelligible message back into an intelligible message without knowledge of the key, sometimes using frequency analysis of the alphabets as in the table below.

Definition 2.11 Let Ω be a non-empty ordered set such that Ω ⊂ N. Let Gp = {w_i: 1≤i≤p-1} be a subgroup of symmetry group S_n, such that every ω_i is generated by arbitrary set Ω for any prime p ≥ 5. That means $G_p$ = {w₁, w₂, w₃, --- w_p-1} be structure such that each w_i is generated from the arbitrary set w for any prime$p\ge 5$, using the scheme below:

Then each $w_i$ is called a cycle and the elements in each $w_i$ are distinct and called successors.

When p = 5, we have:

Definition 2.12 Transposition cipher (Gp): Transposition cipher is a method of encryption which scrambles the position of characters without changing the characters themselves.

Encryption on 𝐺_𝑃

Since 𝑮_𝑃 = (1,₂, 𝜔₃, …, 𝜔_𝑝−1) then for the encryption process we can define a relation:

Where i< p-1 Where 𝜔₁= P, and P is called a plaintext.

Decryption On 𝐺_𝑃

Since 𝑮 = (1, 𝜔₂, 𝜔₃, …, 𝜔_𝑝−1) then for the decryption process we have:

Definition 2.13 Modulo Inverse: In a modular arithmetic a number ‘’a’’ has a modular inverse a^-1 for a number m, if (a.a^-1) mod_m = 1, The table below shows all the possible modular inverses of mod₂₆.

E.g. The modular inverse of 9 is 3 since 9x3 = 27 and 27 mod26 = 1.

Definition 2.14 Inverse Matrix: The inverse K^-1 of a matrix K is defined by the equation: KK^-1 =K^-1 K= I, where I is an “n x n” square identity matrix.

Encryption and decryption processes will take place through two processes. In the encryption process, the plaintext will be encrypted twice with the Hill cipher and Transposition cipher (G_p) algorithm, different keys will be used for the two encryptions because the two algorithms are different and also in order to make the cipher text more secure from attackers. So different plaintext, different keys.

𝐂_𝐢 ≔ Multiple cipher texts.

The encryption process will take the following steps.

1. Apply encryption function of the Hill cipher on the plaintext (P) to produce cipher text (C₁).
2. Apply encryption function of G_p on C₁ to produce C₂, where C₂ is the ciphertext sent to the receiver.

The decryption process will use the following steps.

1. Apply the decryption function of G_p on C₂ to produce first ciphertext (C₁).
2. Apply Hill decryption function on C₁ to produce the original text (plaintext)

Example. Encrypt the message “safe messages” using the key “ciphering”

3.1. Encryption Statge

• We encrypt the text using Hill cipher. The key is “ciphering”, plaintext should be converted into column vectors of length 3.

matrices, which is equivalent to $\left(\begin{array}{c}s\\ a\\ f\end{array}\right)\left(\begin{array}{c}e\\ m\\ e\end{array}\right)\left(\begin{array}{c}s\\ s\\ a\end{array}\right)\left(\begin{array}{c}g\\ e\\ s\end{array}\right)$, where

, and the key ciphering is $\left(\begin{array}{ccc}c& i& p\\ h& e& r\\ i& n& g\end{array}\right)=\left(\begin{array}{ccc}2& 8& 15\\ 7& 4& 17\\ 8& 13& 6\end{array}\right)$,

The encryption is given by C₁ = K P.

The cipher text is C₁=HDSIOEYQOCAA.

• We encrypt the C₁=HDSIOEYQOCAA using Gp where number of letters is 12 but p is always prime, then we pad the C₁with a padding letter X, now $C_1^{*}=\mathbf{H}\mathbf{D}\mathbf{S}\mathbf{I}\mathbf{O}\mathbf{E}\mathbf{Y}\mathbf{Q}\mathbf{O}\mathbf{C}\mathbf{A}\mathbf{A}\mathbf{X}$.

𝑮₁₃ =(₁,𝜔₂,𝜔₃,…, 𝜔₁₂), and w₁is given below by the table.

Let key =1, then we have. $w_1\to w_{(1+k)}$and k=1, then, we have $w_1\to w_2$, and w₂ is a transposition, given by the table below using the scheme of definition 2.1.11 for w_i.

Then, C₂ = HSOYOAXDIEQCA, the intended receiver and the intruder will receive C₂ as the message, and then decryption will be performed to get the original message sent.

3.2. Decryption Stage.

• We decrypt the code by using Gp cipher decryption using k=1, as shown method below.
$w_{\left(1+k\right)}\to w_{\left(\left(1+k\right)-k\right)}$
$w_2\to w_{\left(2-1\right)}$
$\to w_1$

And $w_1$ is given in table 3 above,

• We decrypt the code $"\mathbf{H}\mathbf{D}\mathbf{S}\mathbf{I}\mathbf{O}\mathbf{E}\mathbf{Y}\mathbf{Q}\mathbf{O}\mathbf{C}\mathbf{A}\mathbf{A}\mathbf{X}"$using Hill cipher decryption algorithm :

P = K^-1C where C = C₁= $\mathrm{H}\mathrm{D}\mathrm{S}\mathrm{I}\mathrm{O}\mathrm{E}\mathrm{Y}\mathrm{Q}\mathrm{O}\mathrm{C}\mathrm{A}\mathrm{A}\mathrm{X}$, and k is the key.

Therefore, $"\mathrm{H}\mathrm{D}\mathrm{S}\mathrm{I}\mathrm{O}\mathrm{E}\mathrm{Y}\mathrm{Q}\mathrm{O}\mathrm{C}\mathrm{A}\mathrm{A}\mathrm{X}"$ will be written in n-component vectors as

Where X is a padded later to be ignored. Then,

P = safemessages, after paraphrasing we have “safe messages”, the process of decryption is now complete.

The idea of using transposition on Gp was first proposed by [1] and [7] considering security features of transposition cipher which include being more simple to decipher for the intended recipient and very difficult for the unintended recipient of the message and therefore it provides higher level of security to the data being sent over communication channels, and also the Hill cipher is a digraph in nature but can expand to multiply any size of letters, adding more complexity and reliability for better security of the information sent. And finally, the authors discovered that, combination of Hill and transposition gives a cipher text that is somehow impossible for the attackers to get the original message due to multiple algorithms applied there by providing a more complicated cipher text for the intruders.

Hill cipher and transposition cipher (Gp) were been studied individually and their combination give more secure ciphertext than in their ordinary form and cryptanalysis fails due to multiple algorithms employed in the study.

Acknowledgement

We would like to express our gratitude to all of the staff of UDUSOK and FUBK Mathematics Department for their immense support in the development of this manuscript for their guidance and contribution in finishing this manuscript.

Author Contributions

Conception and design: Hassan, A., and Sani, S. Drafting of the manuscript: Hassan, A and Sani, S. Revision of the manuscript: Abdullahi, U and Sahalu, S. S. Critical Revision of the manuscript: all authors. All authors read and approved the final version of the manuscript.