JURNAL FOURIER | Oktober 2023, Vol. 12, No. 2, 51-59

## Protokol Otentikasi Menggunakan Konstruksi Matriks Komutatif Atas Matriks Aljabar Max-Plus
Mufarij Anna Ziaulhaq 1 , Muhamad Zaki Riyanto 2
1,2 Program Studi Matematika, Fakultas Sains dan Teknologi, Uiniversitas Islam Negeri Sunan Kalijaga Yogyakarta, Jl. Marsda Adisucipto No. 1 Yogyakarta 55281, Indonesia

## Korespondensi; Mufarij Anna Ziaulhaq, Email:mufarijanna123@gmail.com

## Abstrak
Aljabar max-plus adalah himpunan bilangan real bersama elemen negatif tak hingga yang dilengkapi operasi penjumlahan didefinisikan  sebagai  operasi  maksimum  dan  operasi  perkalian  didefinisikan  sebagai  operasi  penjumlahan.  Konsep aljabar  max-plus  diperluas  untuk  membentuk  suatu  himpunan  matriks  atas  aljabar  max-plus.  Lebih  lanjut  himpunan matriks atas aljabar max-plus merupakan struktur semiring non komutatif. Salah satu penelitian tentang matriks atas aljabar max-plus membahas tentang pengkonstruksian suatu matriks yang bersifat komutatif terhadap operasi perkalian pada matriks atas aljabar max-plus.  Salah satu aplikasi dari aljabar max-plus adalah dapat diaplikasikan pada bidang kriptografi,  seperti  proses  enkripsi-dekripsi,  protokol  pertukaran  kunci  dan  protokol  otentikasi.    Fungsi  protokol otentikasi  yaitu  untuk  memastikan  kebenaran  identitas  pihak  pengirim  kepada  pihak  penerima,  agar  tidak  terjadi pemalsuan  data  pengirim.    Artikel  ini  akan  mengembangkan  protokol  otentikasi  menggunakan  konstruksi  matriks komutatif atas aljabar max-plus.  Penggunaan matriks komutatif atas aljabar max-plus dimaksudkan untuk meningkatkan keamanan protokol otentikasi dari pihak yang hendak menyadap protokol otentikasi tersebut.
Kata Kunci : Aljabar max-plus, semiring non komutatif, matriks komutatif, kriptografi, protokol otentikasi

## Abstract
The max-plus algebra is a set of real numbers along with infinitely negative element that completed addition operations defined as maximum operations and multiplication operations defined as addition operations. The concept of max-plus algebra is extended to form a matrix set over max-plus algebra. Furthermore, the set of matrices over max-plus algebra is a noncommutative semiring structure. One of the studies of max-plus matrix is discussing about the construction of commutative matrix over multiplication operations in max-plus algebra. One of the applications of max-plus algebra is that it can be applied to the field of cryptography, such as encryption-decryption processes, key exchange protocols and authentication protocols. The function of the authentication protocol is to ensure the correctness of the identity of the sending  party  to  the  receiving  party,  so  that  falsification  of  sender  data  does  not  occur. This  article  will  develop authentication  protocols  using  construction  of  commutative  matrix  over  max-plus  algebra.  The  use  of  commutative matrices over max-plus algebra is intended to increase the security of authentication protocols from those who want to intercept the authentication protocol.
Keywords : Max-plus algebra, non commutative semiring, commutative matrix, cryptography, authentication protocol

## Pendahuluan
Komunikasi  merupakan  proses  yang  digunakan  untuk  menyampaikan  suatu  informasi  atau  pesan kepada orang lain, tentunya komunikasi merupakan hal penting dalam kehidupan sehari-hari. Seiring berjalannya waktu terlebih di era teknologi seperti saat ini, komunikasi mengalami perkembangan yang sangat pesat, yang dahulu hanya bisa dilakukan dengan menulis surat atau berbicara secara langsung kepada orang lain, menjadi mudah dengan cukup menuliskan pesan yang kita inginkan melalui media internet.  Namun  seiring  perkembangan  teknologi,  komunikasi  juga  terdapat  dampak  negatif,  yaitu
rawan terjadi penyadapan atau pemalsuan pesan. Oleh karena itu aspek keamanan sangat diperlukan dalam komunikasi pada era teknologi seperti ini [14] .
Salah satu solusi sebagai pengamanan pesan yaitu menggunakan kriptografi. Kriptografi merupakan ilmu  yang  mempelajari teknik-teknik matematika  yang  berkaitan  dengan aspek keamanan  informasi meliputi  kerahasiaan  data,  keabsahan  data,  integritas  data,  dan  otentikasi  data.  Aspek  yang  sering dibahas  dalam  kriptografi  yaitu  tentang  kerahasiaan  data [3] .  Proses  yang  dilakukan  untuk merahasiakan  suatu  data  atau  informasi  yaitu  menggunakan  proses  enkripsi  dan  dekripsi.  Enkripsi adalah  proses  penyandian  pesan  yang  dapat  dimengerti  (plainteks)  menjadi  kode-kode  yang  sulit dimengerti (cipherteks). Sementara dekripsi adalah proses kebalikan dari enkripsi. Proses enkripsi dan dekripsi membutuhkan kunci yang hanya diketahui dan disepakati oleh pihak yang saling berkomunikasi [13] . Salah satu metode untuk menyepakati kunci tersebut menggunakan protokol pertukaran kunci.
Selain aspek kerahasiaan, aspek otentikasi juga merupakan salah satu aspek penting yang digunakan sebagai  pengamanan  data.  Diperlukannya  aspek  otentikasi  untuk  mencegah  adanya  pemalsuan identitas pihak pengirim pesan. Aspek otentikasi dapat diselesaikan menggunakan skema tanda tangan digital. Saat ini skema tanda tangan digital yang dikenal secara luas yaitu skema tanda tangan digital RSA  dan  DSA.  Konsep  matematika  yang  digunakan  kedua  skema  tanda  tangan  digital  tersebut  yaitu menggunakan permasalahan faktorisasi bilangan bulat dan logaritma diskrit pada grup komutatif [7] . Namun adanya ancaman komputer kuantum diklaim dapat memecahkan masalah faktorisasi bilangan bulat  dan  logaritma  diskrit  dengan  cepat,  salah  satunya  yaitu  dengan  algoritma  Shor [9] .  Beberapa peneliti  pun  mencari  alternatif  efisien  lain  yang  dapat  meminimalisir  serangan  komputer  kuantum, salah  satunya  yaitu  menggunakan  struktur  aljabar  max-plus.  Struktur  aljabar  max-plus  mempunyai operasi penjumlahan  yang  didefinisikan  operasi maksimum  dan operasi perkalian  yang didefinisikan operasi penjumlahan biasa [4] .
Struktur  aljabar  max-plus  dinilai  dapat  dijadikan  sebagai  alternatif  lain  untuk  digunakan  dalam bidang  kriptografi  sebab  dinilai  efisien  dan  tergolong  masih  sulit  untuk  diserang  keamanannya. Pembahasan tentang aljabar max-plus pun mulai banyak dikembangkan oleh para peneliti, diantaranya [1] membahas  tentang  pengkonstruksian  matriks  komutatif  atas  aljabar  max-plus, [11] membahas tentang matriks-matriks dalam aljabar max-plus yang mempunyai struktur-struktur khusus, sementara dalam bidang kriptografi aljabar max plus mulai dikembangkan oleh para peneliti, seperti pada [2] , [8] dan [15] yang  menerapkan  aljabar  max-plus  pada  protokol  pertukaran  kunci.    Penelitian  ini  akan diperkenalkan suatu pengembangan protokol otentikasi baru yang mengaplikasikan konstruksi matriks komutatif atas operasi perkalian aljabar max-plus.

## Landasan Teori
Berikut akan dijelaskan tentang teori-teori dasar yang digunakan untuk pembahasan, seperti aljabar max-plus dan matriks atas aljabar max-plus.
Definisi 1. [5] Diberikan suatu himpunan max yang didefinisikan sebagai max { }    . Untuk setiap max , a b  didefinisikan operasi penjumlahan ( )  dan perkalian ( )  sebagai
max( , )
. a b a b a b a b     
Selanjutnya himpunan max yang dilengkapi operasi penjumlahan ( )  dan perkalian ( )  disebut dengan aljabar max-plus.
Aljabar max-plus merupakan suatu semifield komutatif terhadap operasi  dan  sebab memenuhi :
1. Himpunan max adalah monoid komutatif dengan elemen netral max   terhadap operasi

2. Himpunan max adalah grup komutatif dengan elemen satuan max 0  terhadap operasi 
3. Operasi  bersifat distributif terhadap operasi 
4. Elemen  netral max   merupakan  elemen  penyerap  terhadap  operasi  ,  yaitu  untuk setiap max a  berlaku a
a

##      
Konsep aljabar max-plus selanjutnya diperluas untuk membentuk sebuah matriks atas aljabar max-plus. Definisi 2. [10] Himpunan semua matriks atas aljabar max-plus berukuran n n  dinotasikan dengan max n n  . Untuk setiap max , n n A B   didefinisikan operasi  dan operasi  sebagai berikut :
{1,2,..., } [ ] max( , ) [ ] max ( ) ij ij ij ij k p ik kj A B a b A B a b      

## Hasil dan Pembahasan
Pembahasan  pada  penelitian  ini  akan  membahas  tentang  konstruksi  matriks  komutatif  terhadap operasi perkalian atas aljabar max-plus yang selanjutnya diaplikasikan pada protokol otentikasi

## Konstruksi Matriks Komutatif atas Aljabar Max-Plus
Himpunan matriks atas aljabar max-plus membentuk suatu struktur aljabar semiring non komutatif.
[1] telah mengkonstruksikan sebuah matriks komutatif atas semiring non komutatif tersebut dan [2] memanfaatkan matriks komutatif tersebut untuk diaplikasikan pada protokol pertukaran kunci Stickel. Penggunaan matriks komutatif tersebut diharapkan dapat meningkatkan keamanan dari protokol yang digunakan, sebab menggunakan konstruksi matriks komutatif atas semiring non komutatif. Selanjutnya akan dibahas tentang konstruksi matriks komutatif atas semiring non komutatif.
Dibentuk sebuah matriks atas aljabar max-plus
11 12 1 21 22 2 max 1 2 , n n n n n n nn a a a a a a A a a a     
         
dengan  entri ii a k  ,  untuk  setiap i dan 2 ij r a r   ,  dengan i j  dan , k r  ,  dengan 0 k  dan 0. r  Himpunan  semua  matriks  dengan  entri-entri  tersebut  dinotasikan  dengan max ( ) . r n k CM
Teorema selanjutnya akan menjelaskan bahwa matriks-matriks dengan entri-entri yang telah dijelaskan sebelumnya bersifat komutatif terhadap operasi perkalian matriks atas aljabar max-plus.
Teorema  3. [2] Diberikan  matriks max ( ) r n k A CM  dan max ( ) s n l B CM  ,  dengan , 0 r s  dan 0, 0 ii ii a k b l     , maka berlaku
. A B B A l A k B       
Bukti. Diambil  sebarang max ( ) r n k A CM  dan max ( ) s n l B CM  ,  dengan , 0 r s  dan
0, 0 ii ii a k b l     , diperoleh { , } { , } ( ) ij ii ij ij jj ip pj p i j ij ij ip pj p i j A B a b a b a b k b l a a b                 
Selanjutnya  akan  dibuktikan  bahwa ip pj ij ij a b k b l a      .  Karena 2 ij r a r   dan 2 ij s b s   , untuk setiap i j  , diperoleh
2 2 . ip pj ij ij ij ij a b r s r s a b k b l a           
Dengan demikian diperoleh
{ , } ( ) ( ) ( ) . ij ij ij ip pj p i j ij ij ij ij ij ij A B k b l a a b
k b l a l a k b l A k B B A
               
      
Untuk setiap i dan j .
Selanjutnya  diberikan  teorema  bahwa  perkalian  antara  konstruksi  matriks  komutatif  dengan sebarang matriks atas aljabar max-plus dengan syarat tertentu juga berlaku sifat komutatif.
Teorema  4. [2] Diberikan  matriks max ( ) r n k A CM  dan max n n B   ,  dengan 0 r  dan 0 k  .  Jika 0 ij b k   untuk setiap i dan j , maka . A B B A   
Bukti. Diberikan max ( ) r n k A CM  dan max n n B   ,  dengan 0 r  dan 0 k  .  Diketahui 0 ij b k   untuk setiap i dan j , maka berlaku 0 ij ij a b k    , sehingga diperoleh { , } { , } ( ) ( ) . ij ii ij ij jj ip pj p i j ij ij ii ij ij jj ip pj p i j ij A B a b a b a b k b B A b a b a b a
b k         
 
      
 
 
Untuk setiap i dan j . Dengan demikian A B B A    .

## Protokol Pertukaran Kunci dan Protokol Otentikasi
Proses enkripsi dan dekripsi pesan membutuhkan suatu kunci rahasia yang disepakati oleh kedua belah  pihak  yang  melakukan  komunikasi.  Salah  satu  metode  untuk  menentukan  kunci  yaitu menggunakan protokol pertukaran kunci.Protokol pertukaran kunci yang sering sekali digunakan yaitu protokol pertukaran kunci Diffie-Hellman. Dalam protokol pertukaran kunci tersebut, tingkat keamanan didasarkan  pada  masalah  logaritma  diskrit  pada  grup  siklik  terhadap  operasi  perkalian  modulo . p Berikut skema dari protokol pertukaran kunci Diffie-Hellman [12] .
Tabel 1. Protokol Pertukaran Kunci Diffie-Hellman
Alice dan Bob menyepakati secara publik bilangan prima p dan generator g dari grup siklik G
Alice Bob 1. Alice memilih secara rahasia bilangan bulat 1 1 a p   
2. Alice menghitung mod a u g p  3. Alice mengirimkan u kepada Bob
4. Alice menghitung mod a A K v p 
1. Bob memilih secara rahasia bilangan bulat 1 1 b p   
2. Bob menghitung mod b v g p 
3. Bob mengirimkan v kepada Alice
4. Bob menghitung mod b B K u p  Alice dan Bob menyepakati kunci yang sama, yaitu A B K K K  
Berdasarkan  protokol  pertukaran  kunci  Diffie-Hellman,  dapat  dikembangkan  menjadi  protokol otentikasi.Protokol  otentikasi  bertujuan  sebagai  alat  pembuktian  Alice  sebagai  pihak  user  untuk membuktikan  identitasnya  kepada  Bob  sebagai  pihak  verifikator  atau  sebagai  server.Berikut  skema protokol otentikasi Diffie-Hellman.
Tabel 2. Protokol Otentikasi Diffie-Hellman
Alice dan Bob menyepakati secara publik bilangan prima p dan generator g dari grup siklik G
Alice Bob 1. Alice memilih secara rahasia bilangan bulat 1 1 a p   
2. Alice menghitung mod a u g p 
3. Alice mengirimkan u kepada Bob
4. Bob menerima u dari Alice
5. Bob memilih secara rahasia bilangan bulat 1 1 b p    6. Bob mengirimkan tantangan
mod b v g p  kepada Alice
7. Alice menerima v dari Bob
8. Alice merespon dengan mengirimkan
mod a P v p  kepada Bob
9. Bob memverifikasi dengan menghitung apakah mod b u p P 
Beberapa peneliti mengembangkan protokol pertukaran kunci yang diharapkan keamanannya kuat terhadap serangan komputer kuantum. Salah satu protokol pertukaran kunci tersebut, yaitu protokol pertukaran kunci Stickel yang menggunakan grup non komutatif [6] . Berikut skema protokol pertukaran kunci Stickel.
Tabel 3. Protokol Pertukaran Kunci Stickel
Alice dan Bob menyepakati secara publikgrup non komutatif G dan , a b G  Alice Bob 1. Alice memilih secara rahasia bilangan bulat m dan n
2. Alice menghitung m n u a b 
3. Alice mengirimkan u kepada Bob
4. Alice menghitung m n A K a vb 
1. Bob memilih secara rahasia bilangan bulat r dan s
2. Bob menghitung r s v a b 
3. Bob mengirimkan v kepada Alice
4. Bob menghitung r s B K a ub  Alice dan Bob menyepakati kunci yang sama, yaitu A B K K K  
Untuk  meningkatkan  keamanan, [2] menggunakan  konstruksi  matriks  komutatif  untuk mengembangkan protokol pertukaran kunci Stickel. Berikut skema protokol pertukaran kunci Stickel yang dimodifikasi menggunakan konstruksi matriks komutatif atas aljabar max-plus.
Tabel 4. Protokol Pertukaran Kunci Stickel Menggunakan Konstruksi Matriks Komutatif
Alice dan Bob menyepakati secara publik matriks max n n W  
Alice Bob 1. Alice memilih secara rahasia matriks
max ( ) r n k A CM  dan max ( ) s n l B CM  dengan , 0 r s  dan , 0 k l 
2. Alice menghitung U A W B    3. Alice mengirimkan U kepada Bob
4. Alice menghitung A K A V B   
1. Bob memilih secara rahasia matriks
max ( ) a n x C CM  dan max ( ) b n y D CM 
dengan , 0 a b  dan , 0 x y 
2. Bob menghitung V C W D   
3. Bob mengirimkan V kepada Alice
4. Bob menghitung B K C U D    Alice dan Bob menyepakati kunci yang sama, yaitu A B K K K  

## Protokol Otentikasi Menggunakan Konstruksi Matriks Komutatif
Berdasarkan  protokol  pertukaran  kunci  menggunakan  konstruksi  matriks  komutatif,  dapat dikembangkan menjadi protokol otentikasi. Berikut skema dari protokol otentikasi tersebut.
Tabel 5. Protokol OtentikasiMenggunakan Konstruksi Matriks Komutatif
Alice dan Bob menyepakati secara publik matriks
max n n W  
Alice Bob

## 1. Alice memilih secara rahasia matriks
max ( ) r n k A CM  dan max ( ) s n l B CM 
dengan , 0 r s  dan , 0 k l 
2. Alice menghitung U A W B   
3. Alice mengirimkan U kepada Bob
4. Bob menerima U dari Alice
5. Bob memilih secara rahasia matriks
max ( ) a n x C CM  dan max ( ) b n y D CM  dengan , 0 a b  dan , 0 x y  6. Bob mengirimkan tantangan V C W D    kepada Alice
7. Alice menerima V dari Bob
8. Alice merespon dengan mengirimkan
P A V B    kepada Bob
9. Bob memverifikasi dengan menghitung apakah C U D P   
Contoh. Alice  dan  Bob  mempublikasikan  matriks
3 3 max 30 24 26 12 18 34 . 34 21 20 W   
             Alice  memilih
secara rahasia dua
buah matriks
12 3 max 24 24 12 18 24 24 15 ( ) 17 13 24 A CM   
 
              dan 15 3 max 21 21 15 30 18 21 22 ( ) 24 27 21 B CM     
       
   
 
selanjutnya Alice menghitung
24 12 18 30 24 26 21 15 30 = 24 24 15 12 18 34 18 21 22 17 13 24 34 21 20 24 27 21 54 48 50 21 15 30 = 36 6 58 18 21 22 58 7 21 24 27 21 U A W B
                                                                             75 69 71
= 57 31 79 . 79 43 42  




   
Selanjutnya  Alice  mengirimkan
75 69 71
= 57 31 79 79 43 42 U           kepada  Bob.  Pada  lain  pihak,  Bob  menerima
75 69 71 = 57 31 79 79 43 42 U        
  .  Langkah  selanjutnya  Bob  memilih  secara  rahasia  dua  buah  matriks
20 3 max 32 32 40 36 37 32 29 ( ) 25 21 32 C CM   
 
           
  dan 17 3 max 29 29 17 18 19 29 20 ( ) 33 34 29 D CM     
              Selanjutnya Bob
menghitung
32 40 36 30 24 26 29 17 18
= 37 32 29 12 18 34 19 29 20 25 21 32 34 21 20 33 34 29 62 56 58 29 17 18 = 44 14 66 19 29 20 66 11 13 33 34 29 91 85 87 = 73 43 95 95 V C W D
  
                                                                          . 49 48    
     
Setelah  menghitung V ,  Bob  mengirimkan  tantangan  tersebut  kepada  Alice.  Selanjutnya  Alice menerima tantangan V dari Bob dan mengirimkan respon kepada Bob yaitu
24 12 18 91 85 87 21 15 30
= 24 24 15 73 43 95 18 21 22
17 13 24 95 49 48 24 27 21
115 109 111 21 15 30 = 97 67 119 18 21 22 119 73 82 24 27 21 136 130 132 = 118 P A V B
                                                                         
92 140 . 140 104 103    


    Bob  menerima  respon 136 130 132 118 92 140 140 104 103
P  
         dari  Alice.  Untuk  melakukan  otentikasi  Bob menghitung apakah C U D P    , diperoleh
32 40 36 75 69 71 29 17 18
= 37 32 29 57 31 79 19 29 20
25 21 32 79 43 42 33 34 29 107 101 103 29 17 18 = 89 63 111 19 29 20 111 75 74 33 34 29 C U D                                                                      
   136 130 132
= 118 92 140 .
140 104 103           Bob memperoleh hasil bahwa C U D P    , sehingga proses otentikasi berhasil.

## Kesimpulan
Adanya  pengembangan  protokol  otentikasi  menggunakan  struktur  aljabar  semiring  non  komutatif diharapkan tingkat keamanannya lebih tinggi terhadap serangan computer kuantum di masa mendatang, terlebih lagi menggunakan konstruksi matriks komutatif atas aljabar max-plus berukuran besar, hal ini diharapkan  pihak  yang  melakukan  otentikasi  lebih  efisien  dan  pihak  penyerang  mengalami  kesulitan karena harus memecahkan masalah aljabar linear dalam aljabar max-plus.

## Referensi
[1] J. Linde and M. J. de la Puente, "Matrices commuting with a given normal tropical," Linear Algebra and its Applications , pp. 101- 121, 2015.
[2] Any Muanalifah and Sergei Sergeev, "Modifying The Tropical Version Of Stickel's Key," Applications of Mathematics , pp. 727-753, 2020.
[3] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography . Boca Raton: CRC Press, 1996.
[4] Subiono, Aljabar Max-Plus dan Terapannya . Surabaya: Matematika FMIPA ITS, 2013.
[5] M.  Andy  Rudhito, Aljabar  Max-Plus  dan  Penerapannya .  Yogyakarta:  Program  Studi  Pendidikan  Matematika  FKIP  Universitas Sanata Dharma, 2016.
[6] E.  Stickel,  "A  New  Method  for  Exchanging  Secret  Keys," Third  International  Conference  on  Information  Technology  and Applications (ICITA'05) , 2005.
[7] Johannes A.Buchmann, Introduction to Cryptography . New York: Springer New York, 2004.
[8] Dima Grigoriev and Vladimir Shpilrain, "Tropical Cryptography," Communications in Algebra , pp. 2624–2632, 2014.
[9] Peter  W.  Shor,  "Polynomial-time  Algorithms  for  Prime  Factorization  and  Discrete  Logarithm  on  a  Quantum  Computer," SIAM Journal on Computing , pp. 1484-1509, 1997.
[10] Kasie G. Farlow, Max-Plus Algebra .: Virginia Polytechnic Institute, 2009.
[11] Daniel Jones, Special and Structured Matrices in Max-Plus Algebra .: The University of Birmingham, 2017.
[12] W. Diffie and M. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory , pp. 644-654, 1976.
[13] Douglas  R. Stinson  and  Maura B. Paterson, Textbooks  in  Mathematics  Cryptography Theory and  Practice  Fourth  Edition .:  CRC Press, Inc, 2019.
[14] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, An Introduction to Mathematical Cryptography Second Edition .: Springer- Verlag New York, Inc, 2014.
[15] Musthofa,  "An  Application  of  Max-Plus  Algebra  in  Criptography,"  in International  Seminar  on  Innovation  in  Mathematics  and Mathematics Education , 2014.