Microsoft Word - 151-159


 

Mathematics | 151 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

"Cryptography by  Using"Hosoya"Polynomials for"Graphs Groups of 
Integer Modulen and"Dihedral Groups with'Immersion"Property 

 
Awni M.Gaftan 

awnijeh@yahoo.com 
Akram S. Mohammed  

akr_tel@tu.edu.iq  
Osama H. Subhi  

osama.hameed67@gmail.com 
Department of Mathematics, College of Computer Science and Mathematics, University of Tikrit, 

Iraq. 
 

Received 15 May 2018, Accepted 1 July 2018, Published December 2018"" 

 

Abstract  
      In this paper we used Hosoya polynomial ofgroupgraphs Z1,...,Z26 after representing each 
group as  graph and using Dihedral group to"encrypt the plain texts with the immersion 
property which provided Hosoya polynomial to immerse the cipher text in another"cipher text 
to become very"difficult to solve. 
 
Keywords: Hosoya"polynomials,Dihedral groups,Cryptography,Encryption"processes , 
"Decryption"processes.   

1. Introduction"" 
" In modern"times, cryptography is an important science in"algebra and graph theory, 
where"many articles linked in"this side, In"2014,"Natalia"tokareva"[1] linked the graph 
theory"and"cryptography,"with"conclusion"good"results"[2]. Thomas Risse studied this 
concept and gave some important example, Simon"Richard,"Carlos"Cid and Ciaran Mullan in 
[3], presented:and studied:of group theoryand cryptography where they get good results. 
The main goal of cryptography is to secure and save important messages by special methods 
that cannot be easily identified. 

This paper includes three parts"The first part is the basic concepts."The second partsuggested 
algorithm of the method. 
"  
"The third part is the application method. 

  
 Concepts"Basic .2  

In this section, we will provide some basic concepts known 
  

Definition1 [4]  

consists of the elements of n ) be a group of integers module n ,then the graph of Zn,+ nLet (Z
b =e nas avertices ,while the edges for any two distinict vertices  a,b would be adjcent if a+ nZ

.nand the element 0 associated with all elements of Z  

. ne is the identity element of the groups Z 



 

Mathematics | 152 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

Example 2 

:group is ) then the graph of this8,+ 8If we take the group (Z 

0

4

5

3

6
2

7

1

  

8of Z Neutral Graph .1 Figure  

Definition 3[5]  

"Let G be a graph, then the Hosoya polynomial of G is  

H(G,X)= d G", k 𝑋 

Where d(G,k) is the number of vertices  pairs at distance k , k≥0 , dim(G) is the diameter of 

the geaph G and X is the guide of the polynomial.  

Example 4 

) then the simple graph of this group is5,+ 5If we take the group (Z 

0

3

2

4

1

  

5of Z Neutral Graph .Figure 2  

and the hosoya polynomial of this graph is 5+6X+4X  

 

 



 

Mathematics | 153 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

Definition 5 [6]  
  

} is called the dihedral  1-n,…, ba 2 , b , ba , ba 1-n, … , a 2, a , a °{a"Dn="The set has the form "
group with order 2n, a, b the elements of this group.  
Definition 6 [7]  
"Cryptographyis the scientific and practical activity associated with developing of 
cryptographic security facilities of information and also with argumentation of their 
cryptographic resistance". 
 
Definition 7 [7]  
"Encryption is the process of disguising a message in such a way as to hide its substance (the process 
of change the plaintext into cipher text by virtue of cipher)". 
 

Definition 8 [7]  
"Decryption is the process of turning a cipher text into the plain text". 
 
Definition 9 [8]  

⎣
⎢
⎢
⎢
⎢
⎢
⎡

𝑘n
𝑘𝑛 1

.

.

.
𝑘2
𝑘1 ⎦

⎥
⎥
⎥
⎥
⎥
⎤

= Rthe adverse of V is Vbe a vector , then  

⎣
⎢
⎢
⎢
⎢
⎢
⎡

𝑘1
𝑘2
.
.
.
𝑛𝑘1

𝑛𝑘⎦
⎥
⎥
⎥
⎥
⎥
⎤

 =Let  V  

Definition 10 [8]                                                                                          

⎣
⎢
⎢
⎢
⎢
⎡

"𝑊0
"𝑊1

.

.

.
"𝑊𝑛 1⎦

⎥
⎥
⎥
⎥
⎤

= be an element in W , Let  W ke a vector and let WB  

”.k-1-n=WRkW"iskW"hen the adverse of T   

2.1. The Suggested Algorithm 
   In this section we introduce two algorithms, the first is algorithm of encryption process and 
the second is algorithm of decryption process 

  
Note 11 
""We consider the blank is character, that is the alphabet is 27 letters and we used the function 
(mod 28).  
i-  algorithm of encryption process  

.26,...,Z2Z1,Converts each letter with corresponding groups Z – 1 

.as a graph 26,...,Z2Z1,Representing each groups Z-2  

3-Extraction of Hosoya polynomial for all groups graphs.  



 

Mathematics | 154 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

4–Take positive integer number"n .  

5 –"Divide the text with length 2n by using dihedral group as:  

"W=

⎣
⎢
⎢
⎢
⎢
⎡

"𝑊1
"𝑊2

.

.

.
"𝑊2𝑛⎦

⎥
⎥
⎥
⎥
⎤

 =
𝑼
𝑽

     Where" U=

⎣
⎢
⎢
⎢
⎢
⎡
"𝑊1
𝑊2

.

.

.
"𝑊𝑛⎦

⎥
⎥
⎥
⎥
⎤

"  and  V=

⎣
⎢
⎢
⎢
⎡
"𝑊𝑛 1

.

.

.
"𝑊2𝑛 ⎦

⎥
⎥
⎥
⎤

 

6 – "Apply the dihedral operations (x,y):  

 .1-k=0,1…n " 
𝑥 "𝑢         𝑚𝑜𝑑 28

𝑦𝑥 "𝑣  𝑚𝑜𝑑 28
= wnD"  

  

⎣
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎡

⎣
⎢
⎢
⎢
⎢
⎡

0 1 1
1 1 1
. . .
. . .
. . .

𝑛 1 1 1⎦
⎥
⎥
⎥
⎥
⎤

"
ℎ𝑜𝑠𝑜𝑦𝑎 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙 

𝑜𝑓 𝑍𝑖    𝑣𝑒𝑐𝑡𝑜𝑟𝑠

⎝

⎜⎜
⎛

⎣
⎢
⎢
⎢
⎢
⎡

0 1 1
1 1 1
. . .
. . .
. . .

𝑛 1 1 1⎦
⎥
⎥
⎥
⎥
⎤

"
ℎ𝑜𝑠𝑜𝑦𝑎 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙 

𝑜𝑓 𝑍𝑖    𝑣𝑒𝑐𝑡𝑜𝑟𝑠

⎠

⎟⎟
⎞

⎦
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎤

= wnD  

7-To improve this method we must encryption the first letter because the first letter by using 

this method stay the same letter always then we encryption the first letter by this equation 

 +(2*n) mod 28i= w ic 

ii- Algorithm of Decryption Process  

First decryption the first letter by the Equation (1):  

(2*n) mod 28-1=c1w"  

2- For other letter using: 

                                                                        1-k=0,1…n 
" 𝑥 𝑢     𝑚𝑜𝑑 28

" 𝑦𝑥 𝑣     𝑚𝑜𝑑 28
=CnD'  

Note 12  
"If the"number"0"appears, then"it"always"takes"the"code"#: 

 
 
Note 13  
     After the decryption, we always take the first letter and then we cancel two letters after it 
and take the fourth letter and cancel two letters after it and so on because the clear text is 
immersed in another text. 



 

Mathematics | 155 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

3. Application Method 
Now, we apply the above method in two examples. 

 
Example 14  
 Take the plain text (college) 

 
1-"Encryption  

and representing this groups  26,...,Z2Z1,We converts each letter with corresponding groups Z
as graphs and extract hosoya polynomaial for all this graphs  

the graph of this  , and3C→ Z -

group is                            

 

       3Zraph of Geutral N .3 Figure  

)2(3+3X+0Xand the hosoya polynomail of this graph is   

  and the graph of this group is ,15O→Z -  

08

7

9

6

10
5

11 4
12

3

13

2

14

1

  

15raph of ZGeutral N .4 Figure  

and the hosoya polynomail of this graph is (15+18X+84X )  
and for all letters we will get 

)2(3+3X+0Xc→   

)X(15+18X+84o→   

  )l→ (12+16X+50X  

  )X(5+6X+4e→  

  )g→ (7+9X+12X  

, a , b , ab }°={ a 4= D 2nNow let   n=2 , D  

Then {college}→ {coll} + {ege_} 



 

Mathematics | 156 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

12
12

=and V 
3

15
=where U 

𝑈
𝑉

=

3
15
12
12

= 1{coll}→ w  

)mod 28( 

0 1 1
1 1 1

3 3 0
15 18 84

0 1 1
1 1 1

12 16 50
12 16 50

= 1w1D  

=  

3 4 1
16 19 1

12 17 23
13 17 23

=

3 4 1
16 19 1
16 11 5
15 11 5

  

CDAPSAPKEOKE 

The first letter C→3→3+4=7→G 

 "→ "GDAPSAPKEOKE1C 

5
27

=and  K 
5
7

=where J 
𝐽
𝐾

=  

5
7
5

27

=  2{ege_}→ W  

) mod 28(  

0 1 1
1 1 1

5 6 4
7 9 12

0 1 1
1 1 1

5 6 4
27 0 0

= 1w1D   

=  

5 7 5
8 10 13
5 7 5
0 1 1

   =    

5 7 5
8 10 13

23 21 23
0 27 27

  

EGEGJMWUW#_ _ The first letter E→5→5+4=9→I 
#_ _"→"IGEHJMWUW2C 

Then the cipher text is: 
C→"GDAPSAPKEOKEIGEHJMWUW#_ _" 
2-Decryption  
Notice that  

ʺ →ʺGDAPSAPKEOKE1C 
The first letter G→7→7-4=3→C 

)                                     mod 28( 

3 4 1
16 19 1

0 1 1
1 1 1

16 11 5
15 11 5

0 1 1
1 1 1

=  n= D 1C1D    



 

Mathematics | 157 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

  = 

3 3 0
15 18 0

12 16 22
12 16 22

 

CC#OR#LPVLPV  

#_ _ʺ→ʺIGEHJMWUW2C 

The first letter I→9→9-4=5→E 

)                                     mod 28( 

5 7 5
8 10 13

0 1 1
1 1 1

23 21 23
0 27 27

0 1 1
1 1 1

=  n= D 2C2D    

= 

5 6 4
7 9 12
5 6 4

27 0 0

  

EFDGILEFD_## 

Then the plain text is (college).  

Example 15  
   If we encryption the text (college of computer science and mathematics) by the same 
technique with choose n=3 then we will get  
P→"college of computer science and mathematics"  

C→"IDAPVAMQWPKEVUWTROKGEPVAGHIYX_LGENJMKGEPVAGHIYX_LGENJ
M IDAJMYFGENHKXX_VUWGAAOTQEECOIWZ_ _G_ENKSFGENSE_ _ _G_EROC 
CDAT#E#AAA_ _#_ _#_ _"  

Now we find a table of ratios of letters and a statistical scheme of plan text and cipher text and 
try to compare these two texts  

For plan text 

Table 1. The ratio of plan text characters  
G  F E D C B A 

0.02631579  0.02631579 0.15789474 0.02631579  0.13157895 0  0.07894737 

N  M L K J I H  

0.05263158 0.07894737 0.05263158  0  0  0.05263158 0.02631579 

U  T  S R  Q  P  O  

0.02631579  0.07894737  0.05263158  0.02631579  0 0.02631579 0.07894737 

    Z Y  X W V  

    0  0  0 0  0  

And the statistical scheme 



 

Mathematics | 158 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

  

Scheme 1.Histogram of Plan Text  

For cipher text 

Table 2. The Ratio of Cipher Text Characters  
G  F  E D C  B A 

0.08730159 0.01587302 0.1031746 0.02380952 0.02380952 0  0.08730159 

N  M L K J I  H  

0.03968254 0.03174603 0.01587302  0.03968254 0.02380952  0.03968254 0.02380952  

U T  S R  Q  P O 
0.01587302  0.02380952  0.01587302  0.01587302  0.01587302 0.03174603  0.03174603  

#  _  Z Y X W V 
0.03174603  0.12698413  0.00793651 0.02380952  0.03174603  0.03174603  0.03968254  

And the statistical scheme 

  

Scheme 2.Histogram of Cipher Text  

Now to compare these percentages we give some observations  

1-Notice that the clear text consists of 38 characters while the encrypted text consists of 126 
characters this means that each letter of clear text corresponds to three letters of the 
encryption text and this is the immersion property we mentioned. 

2-Notice in the statistical scheme of the encryption text that almost all alphabets were used as 
well as the symbols added to the alphabet, whereas in the plan text there are nine non-existent 
characters. 

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

0.18

ZYXWVUTSRQPONMLKJIHGFEDCBA

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

#ZXVTRPNLJHFDB



 

Mathematics | 159 

Ibn Al-Haitham Jour. for Pure & Appl. Sci.                                                   IHJPAS      
                            https://doi.org/10.30526/ 31.3.2008                                                                      Vol. 31 (3) 2018 

3-Notice that the highest ratio of letters or symbols in the encoded text is the ratio of the 
symbol _ which has been added to the alphabet which does not represent any letter of the 
clear text and this indicates that this code added to the alphabet has increased the strength of 
encryption significantly. 

References 

1. Natalia, T. Connections between graph"theory and Cryptography. G2C2:"Graphs 
and"Groups,"Cycles and Coverings; 24–26,"Novosibirsk, "Russia. 2014. 

2. Thomas, R.Cryptography and Graph theory two Examples of DiscreteMathematics 
SAGA. HSB"university of applied"sciences. 2011.  

3. Simon, R.; Carlos, C.; Ciaran, M. Group theory and Cryptography. university of 
London. 2010.  

4. Vasantha, K. W. B; Florentins,S.Groups As Graphs,Editura CuArt, Slatina,Judctul olt, 
Romania, 2009. 

5. Ali, A.M. Wiener"polynomial"of Generalized Distance"in graph.,,Mosuluniversity. 
2005. 

6. Edwin, C. Elementary Abstract Algebra. university of south Florida, 2001.  
7. Hans, D.; Helmut, K. Introduction to Cryptography,Principles and application. 

second edition, verlay Berlin Heidelberg, 2007.  
8. David, C.; Tom, D.; Rohit, T. ; Andrew, W. Linear Algebra . Davis"California. 2013.