All the communications, whether it is social, business, or any other networking are done using digital technology. The world is getting more and more digitalized to make the life easy. The technology is compact in our hands and any work can be done with just a click. As everything is getting digitalized, it is the responsibility of the service provider, to make their system as safe and secure for their clients. Hence, updating security in a system becomes essential and a continuous process.
The coronavirus Covid-19 has affected almost all the countries and lakhs and lakhs of people got infected and millions of deaths have been reported globally. This pandemic forced the countries to shut down all their businesses. The governments are completely engaged in keeping the death rate of their countries under control. They are continuously motivating researchers to find vaccines for this virulent disease. The hackers have started using this unprecedented opportunity of chaos and panic to wield social, economic, and financial crises for their gain
The cryptography
Graph theory is a field having a lot of applications; any real-life problem is simplified using graphs and can be solved using graph theory properties and techniques. The flexibility of graph properties strengthens the cryptosystem. The graph structures play an important role in the encryption and decryption process. The literature survey given in
Any important secret document which has to be shared among people will be encrypted by a password. This encrypted document and the secret key to decrypt the document will be sent separately to the receiver. Mostly a single word is used as a password.
In this paper, a new cryptosystem using the amalgamation of paths, its double vertex graph and edge labelling has been proposed.
Graph theory
Alavi et al.
Comparing to the original graph, the distance between any two vertices is increased in its double vertex graph
In general, graphs can be represented in two ways namely adjacency list and adjacency matrix
The adjacency matrix
In this section, we first introduce an encryption algorithm based on a double vertex graph of a path. This path is constructed from the given password. An illustration is given for this encryption algorithm by considering a password. Then a decryption algorithm is introduced to decrypt the encrypted word. We use the encoding table
Alphabet |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
Coding Number |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
Alphabet |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |
Coding Number |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
The double vertex graph
Consider an edge
By the definition of double vertex graph, the corresponding edges in double vertex graph
Number of horizontal edges in
Number of vertical edges in
Therefore, the number of edges for
Hence the proof.
Let the first edge be labelled as,
The second edge to
The
The steps in the encryption algorithm using double vertex graph are as follows:
Convert the Plaintext to number string
Label the edges
Construct
Form an adjacency matrix
Extract the entries of
The encrypted message will be of the following form
Encrypted message
Suppose we want to send a message
The plaintext is “STRIKE”, which is a six-letter word. Therefore
In
By Theorem 3.1, each edge in
Consider the edge
Therefore, 45 =
Similarly, the weights of other edges in the path
46 = 10 + 8 + 6 + 5 + 17
44 = 9 + 7 + 6 + 5 + 17
35 = 7 + 6 + 5 + 4 + 13
37 = 8 + 6 + 5 + 4 + 14
31 = 7 + 5 + 4 + 3 + 12
(21, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 7, 0, 6, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 6, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 5, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 5, 0, 5, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0, 4, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 4, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 4, 0, 3, 4, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 3, 0, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 12, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0)
Form a matrix using the encrypted message and name it as A
Construct a graph using A, which would be
Extract
Calculate
Convert the number string
In this study, a double vertex graph to encrypt a word was proposed. First, the given message was encoded using the encoding table. In the second step, the plain text was converted into a path graph. From this path graph, a double vertex graph was constructed. Then an adjacency matrix is formed from this double vertex graph. These four stages make the encryption stronger. Without the knowledge of graph theory, it is very difficult to hack and decrypt the encrypted word. This kind of cryptosystem is used to communicate single word like password securely. This study can be extended to encrypt a sentence. This work can also be extended to other big graph structure to make the password even more secure and strong.
The authors wish to thank the management of Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam 603 110 for their continuous support and encouragement for the research work.