Synergistic Cryptography: Implementing K6 Graphs and Hamiltonian Cycles for Reliable Encryption and Decryption

Synergistic Cryptography: Implementing K6 Graphs and Hamiltonian Cycles for Reliable Encryption and Decryption

Abstract In today's digital era, encrypting messages is essential for ensuring secure communications. As internet and network technologies advance, encryption methods are becoming more sophisticated. Transmitting information, personal messages, images, or data over unsecured channels exposes them to potential attacks or hacking. To counter these threats and enhance security, cryptographic techniques are vital. Once ciphertext is produced and transmitted, it can be decrypted back to plaintext using the same key and a decryption algorithm. This paper describes an encryption method that employs a Complete K6 Graph and a Cycle to generate ciphertext using two keys, one of which is derived from a Hamiltonian Circuit. It also provides the corresponding decryption algorithm.

Keywords Complete Graph, Cycle, Hamiltonian Cycle, Encryption, Decryption, Cipher text.

1. INTRODUCTION

   Cryptography is vital in any area requiring secure data transmission and storage, safeguarding the confidentiality, integrity, and authenticity of information across various applications. In computer science, cryptography underpins data security, identity authentication, and privacy across numerous applications. From securing web communications and online transactions to protecting cloud data and IoT devices, cryptographic techniques are essential for preserving the integrity, confidentiality, and authenticity of digital information in our increasingly interconnected world.

   [4] provides some ideas for discovering how to use labeled graphs. The inner magic and inner antimagic labelings introduced in [1] were utilized in [5] for secure data transfer in a cryptographic application of the inner magic and inner antimagic graphs. [3] describes the use of super mean and magic graph labelings in cryptography. [6] provides concepts on graph. based cryptography, and certain specific graphs have been employed for cryptographic purposes in [7]. The relationship between randomness and cryptography is explained in [8], while [9] provides encryption and decryption techniques based on Graph Theory for symmetric keys. In [9], a Graph Theory-based encryption algorithm and bipartite graph approach for message encryption are discussed.

   This study introduces an encryption mechanism founded on Graph Theory concepts to safeguard messages. The technique encodes the initial data (Plain Text) as a complete graph, employing an encryption table for labeling. To enhance the Cycle Matrix complexity, an Alphabet Encoding Table is used. The approach uses an upper triangular matrix as a shared key, while the Hamiltonian Circuit generates the second key, thereby increasing the ciphertext's complexity. Section 2 covers definitions and fundamental principles, and Section 3 of Main Results outlines encryption instructions, alphabet encoding, and graph labeling.

2. FUNDAMENTAL CONCEPTS

   In this section, we outline the fundamental concepts of Graph Theory and Cryptography essential for the proposed encryption technique.

   1. Graph

      A graph is simply a collection of vertices and edges (or) a Graph G is an ordered pair(V,E), where V is its vertices and E be the edges.

   2. Complete Graph

      In graph theory, a complete graph is a simple, undirected graph where every pair of distinct vertices is connected by a unique edge.

   3. Directed/Undirected Graphs:

      In an undirected graph every edges as a set of vertices, an edge a, b is going to be the set ab, so it connects {a, b} this is same as the set {b, a} they both are same, there is no direction for the graphs and orderdoes not matter for a graph. For directed graph the directions and order of the graphs are important.

      STEP 2:

      A	B	C	D	E	F	G	H	I	J	K	L	M
      65	66	67	68	69	70	71	72	73	74	75	76	77
      N	O	P	Q	R	S	T	U	V	W	X	Y	Z
      78	79	80	81	82	83	84	85	86	87	88	89	90

      Table 1: ASCII Encryption Table

   4. Path

      A path is a walk with no repeated vertices., If a graph is connected then there is a a-b path for all a, b in V.

   5. Hamiltonian Path

      A connected graph G contains an open walk that visits every vertices of a given graph G exactly once is called Hamiltonian path.

   6. Hamiltonian cycle

      A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.

   7. Nearest Neighbor Algorithm:

      The Nearest Neighbor Algorithm traverses a graph starting at one vertex, and then it travels to the next vertex following the edge with the shortest distance (lightest weight) between them.

   8. Cryptography and Cryptanalysis

      Cryptography is the technique of converting readable data into unreadable data, ensuring message security. Cryptanalysis is the process of decoding a communication from a non-readable scheme to a readable scheme without understanding how it was originally encoded. Cryptology refers to a mix of cryptography and cryptanalysis.

   9. Plain text

      The plain text means Original readable data in its natural form.

   10. Ciphertext

       Ciphertext is encrypted text that is created by applying an encryption algorithm on plaintext.

   11. Encryption and Decryption

   Encryption is the process of transforming a standard message (plain text) into a meaningless message (ciphertext). Decryption is the process of transforming a meaningless message (ciphertext) back to its original form (plaintext).

   Apply the encoded information in the graph.

   The graph's vertices reflect the original data (Plain Text). We use a complete graph Kn, where 'n' is the total number of characters in the original message. Let A be the original message with length n that is to be encrypted. Table 1 is used to translate each character of message Ainto the relevant numercal values, which are then assigned to the vertices of the full graph Kn. Label the edges by calculating the modulus of differences in labeling of the linked vertices.

   STEP 3:

   Create the newly generated Complete Graph Matrix 'P' using Labelled Complete Graph Kn. Create a new Cycle Matrix 'T' for the cycle derived from the full Graph Kn by deleting inner edges.

   STEP 4:

   Store the diagonal entries in Matrix B by the respective number values of characters in original message M from the Alphabet Encoding table as given in Table 2 to obtain new modified matrix T*.

   A	B	C	D	E	F	G	H	I	J	K	L	M
   1	2	3	4	5	6	7	8	9	10	11	12	13
   N	O	P	Q	R	S	T	U	V	W	X	Y	Z
   14	15	16	17	18	19	20	21	22	23	24	25	26

   Table 2: Alphabet Encoding Table

   STEP 4:

   To create a new matrix 'M', multiply matrix P with matrix T*.

   STEP 5:

   To obtain the first Cipher Matrix 'S', we multiply matrix M with the Key 'U'. Figure 1 depicts the top triangular key matrix U, which has an order of n×n. where 'n' denotes the number of characters in the original message

   1	2			1
   0	1	2			1
   U = 0	0	1	2
   0	0	0	1	2
   0	0	0	0	1	2
   0	0	0	0	0	1

3. MAIN RESULTS

i) Encryption Algorithm STEP 1:

Encryption Table Construction

Encode the message using encoding chart.

STEP 6:

Select a Hamiltonian Cycle from the complete graph. Because any Complete graph includes total (n-1)! Hamiltonian Cycles: We will utilize the Nearest-Neighbor Algorithm to select the appropriate Hamiltonian Cycle.

STEP 7:

Nearest-Neighbor Algorithm

• As a starting point, select a vertex that contains the original message's beginning character.

• Go to the next vertex, which has an edge with the smallest labeling.

• If the labels on two or more edges are the same, select a random vertex; otherwise, proceed to the next.

• Repeat until the Hamiltonian Cycle is achieved.

  STEP 8:

  Add the edge labeling acquired while going along the Hamiltonian Cycle. Assume the total is "W". It serves as a secondary key.

  STEP 9:

  To create a new final Cipher Matrix 'R', apply mod W to each element of the previous Cipher Matrix 'S'.

  Decryption Algorithm

• Use Matrix Form R to write the linear message.

• Use key W to extract matrix S from matrix R.

• To calculate Matrix 'M', use Cipher Matrix 'S' and the inverse of Key Matrix 'U' (M = S×U-1).

• Using P-1 and M, calculate T* (T* = P-1 × M).

• Use the Alphabet Encoding Table to decode the diagonal entries from matrix T* and calculate the original message.

• The original Plain Text is acquired.

Encryption:

Consider the case where the original message is "GENIUS". Because it contains six characters, we will create a K6 Complete Graph and allocate these characters to the vertices of graphs, as illustrated in Figure 2. Use Table 1 to determine the number value for each character. We will get G = 71, E = 69, N = 78, I = 73, U= 85and S =

83. Label the vertices with the corresponding numerical values. We set V1 to 71, V2 to 69, V3 to 78, V4 to 73, V5 to 85 and V6 = 83 . Edge labels can be found as

E1 = | V1-V2| = |71-69| = 2 E2 = |V2-V3| = |69-78| = 9 E3 = |V3-V4| = |78-73| = 5. E4 = |V4-V5| = |73-85| = 12. E5 = |V5-V6| = |85-83| = 2. E6 = |V6-V1| = |83-71| = 12. E7 = |V1-V3| = |71-78| = 7. E8 = |V1-V4| = |71-73| = 2. E9 = |V1-V5| = |71-85| = 14. E10 = |V2-V6| = |69-83| = 14 E11 = |V2-V5| = |69-85| = 16 E12 = |V2-V4| = |69-73| = 4 E13 = |V3-V6| = |78-83| = 5 E14 = |V3-V5| = |78-85| = 7 E15 = |V6-V4| = |83-73| = 10

Figure 1 a): Complete Graph K6

Figure 1 b): Complete Graph K6

Obtain a freshly labeled Complete Graph Matrix from figure 1, indicated by 'P'.

Using the aforementioned Complete Graph K6 in figure 1 b), create a 6-length cycle.

Figure 2: Cycle of length 6

162 148

0 0 0 2

19

To replace the 0's in matrix 'T', use the Alphabet Encoding Table (Table 2) to assign new integer values to the characters in the original message. Table 2 yields the following English alphabet position numbers: G = 7; E = 5; N = 14; I = 9, U = 21; S = 19. By assigning these values to matrix 'T''s diagonal entries, we get a new matrix 'T*' (updated Cycle Matrix), as shown below.

S 12 0 0 0 2

Obtain New Matrix M as follows

M= PxT*

Create Key Matrix 'U'. As the original message has 6 characters, the Key Matrix will be 6×6 as indicated below:

Multiply the Key Matrix 'U' by the matrix M' to obtain the First Cipher Matrix 'S'.

S 12

0

Using the Nearest-Neighbor Algorithm, we can determine the needed Hamiltonian Cycle as shown below: We'll start with the vertex that contains the first character of the original message, 'G'. Next, we will select a vertex with 'E' as an edge linking to it that has the least weight (the edge label is comparable to the weight of an edge here) than others. Continuing this process yields the needed Hamiltonian Cycle: GEINUSG, with edge labels 2, 4, 5, 7, and 2,12, respectively. The Hamiltonian Cycle is represented in Figure 3.

Find second Key W.

W= 2+4+5+7+2+12 = 32.

Figure 3: Hamiltonian Cycle

To generate a new Final Cipher Matrix, apply mod 32 to each element of the initial Cipher Matrix S. As a result, the final Cipher Matrix is 'R'.

Thus, the R matrix contains the remainders after each entry in S is divided by 32, which is as follows:

The Quotient matrix Q records the outcomes of the division (quotients) after each element in S is divided by 32, which is as follows:

4 11 22 40 68 105

5 14 26 48 82 127

Text), Q (Quotient Matrix), W (second key) = 32 using Hamiltonian Cycle , U (Key Matrix), P (Complete Graph Matrix)

STEP 2:

Write the Cipher text 8 22 24 28 11 16 14 10 20 18

31 26 30 26 4 30 1 14 31 0 2 29 25 31 2 2212 30 1 22 0 18

4 12 17 20 (Right to Left ) in the Final Cipher Matrix R form as:

0 1/10 0 1/4 -7/20

0

STEP 7: Locate T* with help of T* = P1 x M T* = P1 x M

-1/2 1/4 0 1/4 0 0

STEP 4: Compute inverse of matrix U

U 1 =

As a result, the original text is: GENIUS

REFERENCES

1. Krishnaa A. and Dulawat M.S., Algorithms for Inner Magic and Inner Antimagic Labelings for Some Planar Graphs, Informatica (Lithuania), 17(3) (2006) 393-406.

2. Krishnaa A., Some Applications of Labelled Graphs, International Journal of Mathematics Trends and Technology, 37(3) (2016).

3. I.W. Sudarsana, S.A. Suryanto, D. Lucianti and N P A P S Putri, An application of super mean and mean graphs labeling in cryptography system, J. of Physics, Conference Series, 1763, The 2nd International Seminar on Sciencce and Technology, Palu, Indonesia. Published under license by IOP Publishing Ltd (2020).

4. Krishnaa A., An Example Usage of Graph Theory in Other Scientific Fields: On Graph Labeling, Possibilities and Role of Mind/C onsciousness, Chapter in the book titled Graph Theory : Advanced Algorithms and Applications, IntechOpen, London, UK (2018).

5. Krishnaa A., Inner magic and inner antimagic graphs in cryptography Journal of Discrete Mathematical Sciences and Cryptography, 22(6) (2019) 1057- 1066.

6. Ustimenko V.A., On graph based cryptography and symbolic computations, Serdica Journal of Computing I, (2007) 131-156.

7. Krishnaa A., Certain specific graphs in cryptography, Advances and Applications in Discrete Mathematics, 26(2) (2021) 157-177.

8. Perera P.A.S. and Wijesiri G.S., Encryption and decryption in symmetric key cryptography using graph theory, (2021).

9. Etaiwi W. M. A., Encryption Algorithm using Graph Theory. Journal of Scientific Research and Reports. 3(19) (2014) 2519-2527.