eISSN 2722-9886   pISSN 1411-6669 https://jurnal.unej.ac.id/index.php/MIMS/index
Modifikasi algoritma Hill cipher dengan matriks kunci berupa matriks ketetanggaan
(Modification of Hill cipher algorithm with key matrix in the form of a adjacency matrix)
Fakhry Asad Agusfrianto, Lukita Ambarwati, Yudi Mahatma*

## Program Studi Matematika, Fakultas MIPA, Universitas Negeri Jakarta
Jakarta Timur, Jakarta 13220, Indonesia
*korespondensi: yudi_mahatma@unj.ac.id
Received: 16-12-2022, accepted: 24-07-2023

## Abstract
Cryptography is one of the parts in mathematics, especially applied mathematics. Cryptography is the science that studies how to secure information that we don't want others to know about the information we  have. Based on the development of the times, cryptography is divided into two consisting  of  classical  cryptography  and  modern  cryptography.  In  this  paper,  the  focus  of discussion  is  on  classical  cryptography.  Furthermore,  there  are  many  kinds  of  classical cryptographic algorithms, such as the Caesar cipher algorithm, the Playfair cipher algorithm, the Vigenere cipher algorithm, and the Hill Cipher algorithm. The focus of discussion in this paper is on the Hill cipher algorithm. The  modifications  made to the Hill cipher algorithm  lie  in its key matrix. In this paper, it will be shown how to encrypt and decrypt the message we want to send using  the  Hill  cipher  algorithm  with  the  matrix  being  a  adjacency  matrix.  In  which  case,  the adjacency  matrix  itself  is  obtained  from  the  representation  of  the  graph.  It  is  hoped  that  this algorithm can avoid crypt attacks, especially on ciphertext only-attack.
Keywords: Hill cipher algorithm, cryptography, adjacency matrix, plaintext, ciphertext MSC2020: 94A60

## 1. Pendahuluan
Ketika seseorang ingin mengirim pesan yang sangat penting ke seseorang lainnya, tentu mereka  tidak  ingin  pihak  ketiga  selain  mereka  dan  teman  mereka  mengetahui.  Untuk mengatasi hal tersebut, dapat dilakukan pemodifikasian pada pesan yang ingin dikirim ke pihak  lain  supaya  hanya pemilik pesan penerima pesan  yang  mengetahui  makna pesan tersebut. Dalam matematika, khususnya pada matematika terapan, ilmu yang mempelajari hal tersebut dinamakan kriptografi. Kriptografi merupakan ilmu yang mempelajari terkait bagaimana mengamankan pesan menggunakan kode-kode rahasia [ 1 ]. Dalam kriptografi, terdapat  istilah  enkripsi,  dekripsi, plaintext, dan ciphertext .  Untuk  penjelasan  istilah
tersebut, dapat merujuk ke [ 1 ]. Berdasarkan perkembangan zaman, kriptografi terdiri atas kriptografi klasik dan kriptografi modern [ 2 ].
Dalam paper ini, pembahasan akan berfokus pada kriptografi klasik. Algoritma-algoritma kriptografi  klasik  terdiri  atas  berbagai  macam.  Algoritma  tersebut  antara  lain  adalah Caesar cipher, Playfair cipher , Vigenere cipher , dan Hill cipher [ 3 ]. Pembahasan paper ini akan berfokus pada algoritma Hill Cipher dan modifikasinya. Algoritma Hill cipher merupakan  algoritma  yang  menggunakan  matriks  persegi  sebagai  kuncinya.  Beberapa modifikasi yang dilakukan pada algoritma Hill cipher antara lain algoritma Hill Cipher dengan  matriks  kunci  adalah  matriks  Fibonacci  [ 4 ],  algoritma  Hill cipher dengan menggunakan  fungsi  himpunan  fuzzy  [ 5 ],  algoritma  Hill cipher dengan  menggunakan matriks kunci persegi panjang [ 6 ], algoritma Hill cipher dengan pemanfaatan kunjungan pohon biner [ 7 ], algoritma Hill cipher dengan matriks kunci yang dibangun dari algoritma Playfair cipher [ 8 ],  algoritma  Hill cipher dengan  menggunakan  matriks  sirkulan  [ 9 ], algoritma  Hill cipher dengan  menggunakan  tabel  periodik  unsur  kimia  [ 10 ],  algoritma Hill cipher dengan menggunakan transposisi dan operasi XOR [ 11 ], algoritma Hill cipher dengan menggunakan satuan massa [ 12 ], modifikasi Hill cipher dengan fungsi XOR dan XNOR  [ 13 ], dan Hill cipher untuk pengamanan fungsi hash [ 14 ].
Selanjutnya, dalam matematika terapan dikenal konsep graf. Graf merupakan himpunan yang terdiri atas titik dan sisi [ 15 ], [ 16 ]. Selanjutnya, untuk merepresentasikan banyaknya titik yang terhubung pada graf, salah satunya dapat menggunakan matriks ketetanggaan [ 15 ], [ 17 ].
Tujuan penelitian pada paper ini adalah akan dilakukan modifikasi pada algoritma Hill Cipher dengan  matriks  kuncinya  adalah  matriks  ketetanggaan.  Karakter-karakter  yang akan  digunakan  pada  informasi  yang  akan  dienkripsi  dan  didekripsi  menggunakan algoritma ini adalah karakter pada tabel ASCII mulai dari karakter ke 32 sampai dengan karakter ke 126 atau total sebanyak 95 karakter. Harapan dari algoritma ini adalah dapat menghindari serangan kriptanalis yaitu ciphertext only-attack [ 1 ].

## 2. Metodologi
Metodologi  yang  akan  digunakan  pada  penelitian  ini  adalah  kajian  literatur.  Langkah- langkah penelitian dalam paper ini disajikan dalam diagram proses penelitian berikut.
Gambar 1. Diagram proses penelitian pengenkripsian pesan
Gambar 2. Diagram proses penelitian pendekripsian pesan

## 3. Hasil dan Pembahasan
Pada  bagian  ini,  akan  diberikan  contoh  sebarang plaintext yang  akan  dienkripsi  dan didekripsi. Langkah-langkah untuk melakukan pengenkripsian dan pendekripsian adalah sebagai berikut.

## 3.1 Pengenkripsian Pesan
Langkah 1:
Diketahui plaintext : faya tahu . Tentukan kunci yang ingin digunakan dan nyatakan kunci sebagai
𝐾 = [banyaknya titik pada graf|titik yang terhubung pada graf].

## Langkah 2:
Untuk kesepakatan penulisan, perhatikan Tabel 1.
Tabel 1. Tabel penulisan kunci Simbol Makna 𝐴𝐵𝐸 Titik 𝐴 terhubung dengan titik 𝐵 dan 𝐸 𝐴 𝑛 𝐵 Titik 𝐴 terhubung-n kali dengan 𝐵 𝐴 Titik 𝐴 memiliki loop
Misalkan diambil kunci 𝐾 = [5|𝐴 2 𝐵𝐸, 𝐵 2 𝐴𝐶, 𝐶𝐵𝐷, 𝐷𝐶𝐸, 𝐸𝐴𝐷]

## Langkah 3:
Terjemahkan kunci tersebut ke dalam graf. Diperoleh gambar graf sebagai berikut.

## Langkah 4:
Nyatakan graf pada Gambar 1 dalam matriks ketetanggaan. Matriks ketetanggaan adalah matriks yang menyatakan keterhubungan titik suatu graf [15]. Matriks ketetanggaan dari graf diatas adalah
𝑋 = [ 0 2 0 2 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1] .
Langkah 5 :
Karena akan digunakan invers matriks untuk melakukan dekripsi pesan, maka harus dicek apakah (𝑋) ≠ 0 . Jika 𝑑𝑒𝑡 (𝑋) = 0 , maka proses berhenti dan harus ditentukan jenis graf yang lain. Dalam kasus ini, diperoleh 𝑑𝑒𝑡 (𝑋) = 9 .
Langkah 6:
Setelah itu, Ubah plaintext faya tahu ke dalam kode ASCII pada Tabel 2.

## Tabel 2. Tabel ASCII
Desimal Karakter Desimal Karakter Desimal Karakter Desimal Karakter Desimal Karakter 32 spasi 51 3 70 F 89 Y 108 l 33 ! 52 4 71
G 90 Z 109 m 34 “ 53 5 72 H 91 [ 110 n 35 # 54 6 73
I 92 \ 111 o 36 $ 55 7 74 J 93 ] 112 p 37 % 56 8 75
K 94 ^ 113 q 38 & 57 9 76
L 95 _ 114 r 39 ‘ 58 : 77 M 96 ’ 115 s 40 ( 59 ; 78 N 97 a 116 t 41 ) 60 < 79 O 98 b 117 u 42 * 61 = 80 P 99 c 118 v 43 + 62 > 81 Q 100 d 119 w 44 , 63 ? 82 R 101 e 120 x 45 - 64 @ 83 S 102 f 121 y 46 . 65 A 84 T 103 g 122 z 47 / 66 B 85 U 104 h 123 { 48 0 67 C 86 V 105 i 124 | 49 1 68 D 87 W 106 j 125 } 50 2 69 E 88 X 107 k 126 ~
Karena  diambil  5  titik,  maka  karakter  dibuat  menjadi  masing-masing  5  karakter  yaitu faya(spasi)tahu(spasi) .  Maka  diperoleh  kata faya  tahu dalam  kode  ASCII  sebagai berikut:
faya(spasi) = [ 102 97 121 97 32 ] = 𝑃 1 , tahu(spasi) = [116 97 104 117 32 ] = 𝑃 2 .
Di sini, 102 adalah kode ASCII dari f, 97 adalah kode ASCII dari a, dan seterusnya.
Langkah 7:
Tentukan ciphertext dengan menggunakan algoritma Hill cipher :
𝐶 = 𝑃𝑋 𝑚𝑜𝑑 95
dengan 𝑃 adalah  matriks plaintext , 𝐶 adalah  matriks ciphertext ,  dan 𝑋 adalah  matriks kunci. Dengan mensubstitusi nilai 𝑃 dan 𝑌 , diperoleh rumusan:
  1 1 1 mod 95 0 2 0 0 1 2 0 1 0 0
102 97 121 97 32 mod 95 0 1 1 1 0
0 0 1 1 1 1 0 0 1 1 C P X C                     2 2 2 mod 95 0 2 0 0 1 2 0 1 0 0 116 97 104 117 32 mod 95 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 C P X C         
        
Setelah dilakukan perhitungan, diperoleh
𝐶 1 = [36 2 40 3 30 3 60 2 41 2 ] ,
𝐶 2 = [36 2 51 3 33 3 63 2 75 2 ] ,
dengan 𝐶 1 adalah ciphertext dari 𝑃 1 dan 𝐶 2 adalah ciphertext dari 𝑃 2 . Indeks pada tiap nilai adalah karakter hasil bagi dengan 95. Jika hasil bagi 0 ditulis 0, hasil bagi 1 ditulis 1, dan seterusnya.

## Langkah 8:
Karena karakter dimulai dari karakter ke-32, maka tambahkan tiap nilai pada matriks 𝐶 1 dan 𝐶 2 dengan 32 , diperoleh
𝐶 1 = [68 2 72 3 62 3 92 2 73 2 ],
𝐶 2 = [68 2 83 3 65 3 95 2 107 2 ].
Langkah 9:
Terjemahkan ciphertext yang terdapat pada Langkah 8 menjadi karakter ASCII. Bilangan desimal 68 bersesuaian dengan 𝐷 , bilangan desimal 72 bersesuaian dengan karakter H, dan seterusnya. Jadi, ciphertext dari plaintext faya tahu adalah DH>]IDSA_k.

## 3.2 Langkah Pendekripsian Pesan
Setelah  pesan  dikirim  dan  diterima  oleh  penerima,  maka  penerima  harus  melakukan dekripsi  pesan.  Berdasarkan  Langkah  8  pada  langkah  pengenkripsian  pesan,  diketahui rumusan untuk memperoleh ciphertext adalah
𝐶 = 𝑃𝑋 mod 95 maka, untuk memperoleh plaintext dapat menggunakan rumusan:
𝑃 = 𝐶𝑋 −1 𝑚𝑜𝑑 95.
Dalam  Langkah  5  pengenkripsian  pesan,  telah  diperoleh  bahwa 𝑑𝑒𝑡 𝑑𝑒𝑡 (𝑋) ≠ 0 yang berarti matriks 𝑋 punya invers. Untuk lebih jelasnya, akan ditulis dalam bentuk langkah- langkah seperti proses mengenkripsi pesan.
Langkah 1:
Tentukan adjoint dari matriks 𝑋 =
[
0 2 0 2 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1] . Diperoleh adjoint dari matriks 𝑋
adalah Adjoint(𝑋) =
[ 0 3 0 3 0 3 0 −3 3 3 −3 0 0 6 −6 −3 3 −3 0 6 −3 6 −6 6 0 ] .
Langkah 2:
Tentukan invers dari 𝑋 . Untuk mencari invers dari matriks 𝑋 , dapat menggunakan rumus:
𝑋 −1 = 1 det(𝑋) Adjoint(𝑋).
Telah diketahui bahwa 𝑑𝑒𝑡 (𝑋) = 9. Dengan demikian diperoleh
1 1 1 1 0
0 3 3 3 1 1 1 0 0 3 3 3 1 2 2 0 0 3 3 3 1 1 2 1 2 3 3 3 3 3 1 2 2 0 0 3 3 3 X   
                                  .

## Langkah 3:
Tambahkan  matriks ciphertext yang belum  ditambahkan  32 dengan  karakter  hasil baginya. Jika hasil  bagi 0 ditambah 0, hasil  bagi  1 ditambah 95, hasil  bagi 2 ditambah 190, hasil bagi 3 ditambah 285, dan seterusnya. Notasikan matriks ini dengan 𝐷 1 untuk ciphertext 𝐶 1 dan 𝐷 2 untuk ciphertext 𝐷 2 . Maka diperoleh
𝐷 1 = [226 325 315 250 231 ] , 𝐷 2 = [226 336 318 253 265 ].
Langkah 4:
Kalikan 𝐷 1 dan 𝐷 2 masing-masing dengan 𝑋 −1 . Dengan demikian, diperoleh plaintext
𝑃 1 = [102 97 121 97 32 ], 𝑃 2 = [116 97 104 117 32 ].
Jika 𝑃 1 dan 𝑃 2 diterjemahkan ke dalam karakter ASCII, maka diperoleh plaintext yang sama dengan yang diberikan di awal yaitu faya tahu .

## 3.3  Analisis Ketahanan Terhadap Ciphertext Only-Attack
Pada  bagian  ini,  dianalisis  ketahanan  kriptografi  terhadap  serangan ciphertext  only- attack . Umumnya, kunci dari algoritma Hill cipher dituliskan dalam bentuk
𝐾 = [𝑘 𝑖𝑗 ].
Jika  terjadi  kebocoran  beberapa ciphertext dan  kunci,  maka  dengan  mudah  seorang kriptanalis  dapat  menjebol ciphertext tersebut.  Namun,  dalam  penelitian  ini,  penulisan kunci dilakukan dengan cara yang tidak umum, yaitu
𝐾 = [banyaknya titik pada graf|titik yang terhubung pada graf].
Sebagai contoh, dari pembahasan diatas dipunyai kunci
𝐾 = [5|𝐴 2 𝐵𝐸, 𝐵 2 𝐴𝐶, 𝐶𝐵𝐷, 𝐷𝐶𝐸, 𝐸𝐴𝐷].
Penulisan  kunci  seperti  ini  tidak  umum  seperti  penulisan  kunci  pada  algoritma  Hill cipher . Dengan penulisan kunci seperti ini, jika terjadi kebocoran beberapa ciphertext dan kunci,  maka kriptanalis  mengalami kesulitan untuk memecahkan kunci tersebut karena penulisan kunci yang tidak umum.

## 4. Kesimpulan
Berdasarkan pemaparan, telah diperoleh bagaimana cara melakukan enkripsi dan dekripsi pesan dengan  menggunakan  modifikasi algoritma Hill cipher dengan  matriks kuncinya adalah matriks ketetanggaan. Karena penulisan kunci dari pesan dinyatakan dalam bentuk yang  tidak  umum,  hal  ini  akan  mempersulit  kriptanalis  untuk  melakukan  pembobolan pesan. Untuk penelitian selanjutnya, dapat digunakan matriks Laplacian yang diperoleh dari matriks derajat dikurangi matriks ketetanggaan sebagai matriks kuncinya.

## Daftar Pustaka
[1] R. Munir, Kriptografi , 1st ed. Penerbit Informatika, 2019.
[2] H.  Delfs  and  H.  Knelb, Introduction  to  Cryptography ,  2nd  ed.  Springer,  2007. [Online].
[3] F.  Piper  and  S.  Murphy, Cryptography :  A  Very  Short  Introduction .  Oxford University Press, 2002.
[4] H.  Fitroti,  M.  U.  Romdhini,  and  N.  W.  Switrayni,  “Hill  Cipher  algorithm  with generalized Fibonacci  matrix  in  message encoding,” Eig. Math. J. , vol. 4, no. 2, pp. 52–59, 2021.
[5] P. Noviyanti and D. Ariyus, “Modifikasi metode Hill cipher menggunakan fungsi fuzzy dan kode ASCII,” JurTI (Jurnal Teknol. Informasi) , vol. 4, no. 2, pp. 174– 181, 2020.
[6] A. Hidayat and T. Alawiyah, “Enkripsi dan dekripsi teks menggunakan algoritma Hill Cipher dengan kunci matriks persegi panjang,” J. Mat. Integr. , vol. 9, no. 1, pp. 39–51, 2013. [ CrossRef ]
[7] T. Alawiyah, “Pemanfaatan  kunjungan  pohon  biner pada kriptografi Hill  cipher kunci  matriks persegi panjang,” Indones. J. Comput. Inf. Technol. , vol. 2, no. 1, pp. 77–82, 2017. [ CrossRef ]
[8] T.  Alawiyah,  A.  B.  Hikmah,  W.  Wiguna,  M.  Kusmira,  H.  Sutisna,  and  B.  K. Simpony, “Generation of rectangular matrix key  for Hill cipher algorithm using playfair cipher,” J. Phys. Conf. Ser. , vol. 1641, no. 1, pp. 1–5, 2020. [ CrossRef ]
[9] K.A.  Reddy,  B.  Vishnuvardhan,  Madhuviswanatham,  and  A.V.N.  Krishna,  “A modified Hill cipher based on circulant matrices,” Procedia Technol. , vol. 4, no. 1, pp. 114–118, 2012. [ CrossRef ]
[10]  N. D. Sari and D. Arius, “Modifikasi algoritma Hill cipher dengan tabel periodik unsur kimia menggunakan kode nomor operator seluler di Indonesia,” J. Teknol. Inf. , vol. 4, no. 2, pp. 202–207, 2020. [ CrossRef ]
[11]  E. Y. Sari, A. R. Harir, and D. Ariyus, “Modifikasi Hill cipher mod 36 kombinasi transposisi  dan  XOR  kunci  tabel  periodik  dengan  LSB  untuk  penyembunyian pesan,” CESS  (Journal  Comput.  Eng.  Syst.  Sci. ,  vol.  5,  no.  1,  p.  38,  2020,. [ CrossRef ]
[12]  V. S. Ginting, “Penerapan algoritma Vigenere cipher dan Hill cipher menggunakan satuan massa,” J. Teknol. Inf. , vol. 4, no. 2, pp. 241–246, 2020. [ CrossRef ]
[13]  T. Alawiyah and A. B. Hikmah, “Modifikasi kriptografi Hill cipher kunci matriks persegi  panjang  menggunakan  fungsi  XOR  dan  fungsi  XNOR,” Indones.  J. Comput. Inf. Technol. , vol. 1, no. 1, pp. 68–82, 2016. [ CrossRef ]
[14]  Z.  Panjaitan,  E.  F.  Ginting,  and  Y.  Yusnidah,  “Modifikasi  SHA-256  dengan algoritma Hill cipher untuk pengamanan fungsi hash dari upaya decode hash,” J. SAINTIKOM (Jurnal Sains Manaj. Inform. dan Komputer) , vol. 19, no. 1, p. 53, 2020. [ CrossRef ]
[15]  R. Munir, Matematika Diskrit , 7th ed. Penerbit Informatika, 2017.
[16]  R. Diestel, Graph Theory . Springer, 2017.
[17]  R.  Bronson,  G.  B.  Costa,  and  J.  T.  Saccoman, Linear  Algebra :  Algorithms, Applications, and Techniques . Academic Press, 2014.