Graph theory is a primary source for cryptography

In order to reduce this terminology, strengthen the key and produce more security for the given information, we have proposed a new technique that uses the adjacency matrix and self-invertible matrix

The proposed approach is made by first finding the adjacency matrix of a Hamiltonian path of an undirected graph using the given message units as graph edges, and this adjacency matrix can be multiplied with the generated self-invertible key matrix. The output is sent to the receiver over an unsecured channel, and the receiver should use the reverse process to read the original message. The rest of this paper is defined as follows: The self-invertible key matrix generation was discussed in Section 2. Section 3 explains the new proposed methodology, and in Section 4, the results and discussion will be given. Finally, the conclusion was given in Section 5.

A matrix

After computing

The proposed methodology using the Hamiltonian path of an undirected graph with the self-invertible key matrix was explained in this section.

Step 1: The given plain text message is to be converted into its numerical equivalent values. These numerical equivalent values are put into the edges of an undirected graph (i.e., as weights of the edges of the path).

Step 2: Create a path of n-vertices (depending on the number of requirements), beginning with vertex 1.

Step 3: Draw a Hamiltonian path, assign each weight, and then compute the adjacency matrix of this Hamiltonian path. Name this matrix.

Step 4: For the key matrix, we are generating a self-invertible key matrix of even order. Since the key matrix is even, the adjacency matrix must be of order even (the number of edges of a Hamiltonian path must be odd) in case the given path doesn’t form an even-order adjacency matrix. We have to make that into the form of an even adjacency matrix by adding some dummy edges with false weights to the existing Hamiltonian path.

Step 5: After generating a self-invertible key matrix, multiplying it with the adjacency matrix. The final resultant matrix is the encrypted data for the original message units.

Step 6: Finally, this encrypted matrix shared with other users over an unsecure channel, either row-wise or column-wise, also represents the number of vertices, i.e., I, n, <encrypted matrix> <the matrix which helps to generate self-invertible matrix>, where I is the index value of the given Hamiltonian path, n being the size of the matrix.

Step 1: With the help of received data, the receiver is able to find the index value, order of the matrix, and the matrix which helps to generate the self-invertible matrix. The receiver will then separate the matrices.

Step 2: The given encrypted matrix can be multiplied with the generated self-invertible key matrix.

Step 3: Trace back the graph with the help of the above resultant matrix and write the edge length of the graph from the given index value.

Step 4: Decode these values with their numerical equivalent values. Then finally, the receiver is able to identify the original message.

Suppose that User A(sender) wants to send the message "YES" to User B(receiver) using the above-mentioned technique. Assume that both the users know the encryption and decryption techniques of the given procedure.

Encryption is done by the following steps

Firstly, the sender converts the given message units” YES” into their numerical equivalent values that is

Create a Hamiltonian path with 4 vertices, label the above mentioned numerical equivalent values as the edges of a path with 4 vertices which begins from the index value 1, the vertices are connected by sequential letters.

Compute the adjacency matrix for the above Hamiltonian path and denote it as ‘M’

Now we need to compute the key matrix. For that purpose, we construct the self-invertible key matrix ‘N’ with the help of a shared matrix and the procedure discussed above.

Finally, we have to compute

This

Decryption is done by the following steps

With the received information, the receiver separates the following matrix,

And the self-invertible key matrix be

Taking addition modulo 26 (since we are using 26 alphabets), we get

The Corresponding Path for the above adjacency matrix is

The edges(weights) of the above path are 25 5 19.

A new approach to cryptosystem using graphs and self-invertible matrices has been proposed in this study, which uses the concepts of Hamiltonian path, adjacency matrix, and self-invertible matrix in order to increase the security of our information. The proposed approach is more effective and resists the intermediate. In all the symmetric encryption methods provided previously using the concept of graph theory, they use a common key matrix for encryption/decryption. Sharing the key matrix, computing the inverse while decrypting are the main drawbacks in all of these methods. As we are using the self-invertible matrix as the key matrix, it eliminates the complexity involving for finding the inverse. Also, we are not sharing the entire key matrix over the unsecured medians, so this method is more effective than the existing approaches, it is also a simple encryption and decryption technique with better security. The proposed approach can also be used effectively in wireless applications.