## Metode perjanjian password  berdasarkan operasi matriks atas aljabar Min- Plus untuk keamanan pengiriman informasi rahasia
(The password agreement method based on matrix operation over Min-Plus algebra for safety of secret information sending)

## Musthofa dan Dwi Lestari
Jurdik Matematika, FMIPA, Universitas Negeri Yogyakarta (UNY), Kampus Karangmalang, Sleman, DI Yogyakarta 55281 tel. 08175456213, faks. (0274) 548203  dan e-mail: musthofa@uny.ac.id
diterima 2 Desember 2013, disetujui 3 Februari 2014

## Abstrak
Protokol  perjanjian kunci  merupakan suatu  metode  dalam kriptografi.  Protokol  perjanjian kunci  digunakan untuk  mengatasi  masalah  pengiriman  informasi  rahasia  melalui  jalur  komunikasi.Untuk  mengamankan  informasi tersebut  dibutuhkan  suatu  kunci  rahasia  yang  disebut  dengan  password.  Kedua  belah  pihak  yang  melakukan pertukaran  informasi  rahasia  harus  menyepakati  kunci  yang  sama.  Pada  metode  ini,  kedua  belah  pihak  saling menukarkan  parameter  yang  dapat  diketahui  umum,  akan  tetapi  dari  parameter  umum  tersebut  dapat  dibentuk satu password rahasia yang sama dan tidak diketahui oleh umum. Salah satu metode yang telah digunakan adalah menggunakan  serangkaian  operasi  perkalian  matriks  yang  didefinisikan  atas  suatu  lapangan  hingga.  Pada penelitian  ini  dikonstruksi  algoritma  yang  digunakan  dalam  metode  perjanjian  password,  yaitu  berupa  protokol perjanjian  kunci  yang  tingkat  keamanannya  didasarkan  pada  suatu  masalah  aljabar  pada  operasi  matriks  atas Aljabar Min Plus atas Z. Aljabar min-plus atas Z, yaitu Z ∪ {+ ∞ } dengan Z adalah himpunan semua bilangan bulat yang  dilengkapi  dengan  operasi  minimum  dan  operasi  penjumlahan  membentuk  sruktur  aljabar  yang  dinamakan semiring idempotent. Hasil penelitian menunjukkan bahwa penerapan operasi  matriks atas  aljabar min plus dapat digunakan sebagai protokol perjanjian password untuk mengamankan informasi rahasia.
Kata kunci: informasi rahasia, password, aljabar Min-Plus

## Abstract
Key  agreement  protocol  is  a  method  in  cryptography.  Key  agreement  protocol  is  used  to  overcome  the problem  of  sending  secret  information  over  communication  lines.  A  secret  key,  called  password,  is  needed  to secure  t  he  information.  Both  parties  who  exchange  confidential  information  must  agree  on  the  same  key.  In  this method,  both  parties  exchange  mutual  general  parameters  that  everyone  can  see,  however  from  the  general parameters  the  same  passwords  can  be  formed  and  not  publicly  known.  One  method  that  has  been  used  is applying  a  series  of  matrix  multiplication  operation  defined  over  a  finite  field.  In  this  study,  we  constructed  an algorithm in the form of a key agreement protocol that can be used in the password agreement method which the level of security based on algebraic problem of matrix operation over Z- min plus algebra. Min Plus algebra over Z, that  is  Z ∪ {  + ∞ }  with  Z  is  the  set  of  all  integers  equipped  with  the  minimum  and  addition  operation,    is  called idempotent  semiring.  The  results  showed  that  the  application  of  matrix  operation  over  min  plus  algebra  can  be used as key agreement protocol in securing secret information.
Key words: secret information, password, Min-Plus algebra

## Pendahuluan
Perkembangan teknologi informasi dewasa  ini  telah  berpengaruh  pada  hampir semua aspek kehidupan manusia, tak terkecuali dalam  hal  berkomunikasi.  Dengan  adanya teknologi  informasi  seperti  internet,  komunikasi jarak  jauh  dapat  dilakukan  dengan  cepat  dan murah. Namun di sisi lain, ternyata internet tidak terlalu aman karena merupakan jalur komunikasi  umum  yang  dapat  digunakan  oleh siapapun,  sehingga  sangat  rawan  terhadap penyadapan.  Apabila  informasi  yang  dikirimkan bersifat  rahasia,  maka  jaminan  keamanan informasi menjadi sangat mutlak untuk dipenuhi.
Salah  satu  solusi  untuk  mengatasi masalah tersebut adalah menggunakan kriptografi. Kriptografi adalah ilmu yang mempelajari  teknik-teknik  matematika  yang berhubungan dengan aspek keamanan informasi,  seperti  kerahasiaan  data,  keabsahan data,  integritas  data,  serta  autentikasi  data. Tetapi  tidak  semua  aspek  keamanan  informasi dapat diselesaikan dengan kriptografi.
Kriptografi  dapat  pula  diartikan  sebagai  ilmu atau  seni  untuk  menjaga  keamanan  pesan. Ketika suatu pesan dikirim dari suatu tempat ke tempat  lain,  isi  pesan  tersebut  mungkin  dapat disadap oleh pihak lain yang tidak berhak untuk mengetahui  isi  pesan  tersebut.  Untuk  menjaga pesan,  maka  pesan  tersebut  dapat  diubah menjadi suatu kode yang tidak dapat dimengerti oleh  pihak  lain.  Enkripsi  adalah  suatu  proses penyandian  yang  melakukan  perubahan  suatu pesan,  dari  yang  dapat  dimengerti,  disebut dengan plainteks, menjadi suatu kode yang sulit dimengerti, disebut dengan cipherteks. Sedangkan proses kebalikannya untuk
mengubah  cipherteks  menjadi  plainteks  disebut dekripsi [1,2] .
Proses enkripsi-dekripsi tersebut membutuhkan suatu kunci rahasia yang disebut dengan  password.  Kedua  belah  pihak  yang melakukan  pertukaran  informasi  rahasia  harus menyepakati  kunci  yang  sama.  Akan  menjadi masalah apabila keduanya tidak dapat menyepakati  password  yang  sama,  sebab keduanya  menggunakan  jalur  komunikasi  yang tidak aman. Protokol perjanjian kunci merupakan suatu metode dalam kriptografi yang digunakan  untuk  mengatasi  masalah  tersebut. Pada  metode  ini,  kedua  belah  pihak  saling menukarkan  parameter  yang  dapat  diketahui umum,  akan  tetapi  dari  parameter  umum
tersebut  dapat  dibentuk  satu  password  rahasia yang sama dan tidak diketahui oleh umum.
Protokol perjanjian kunci yang didasarkan  pada  grup  perkalian  matriks  yang merupakan  salah  satu  contoh  grup  non- komutatif telah dibahas dalam beberapa literature,  seperti  dalam  [3].  Selain  itu,  operasi matriks  pada  struktur  aljabar  yang  merupakan semiring telah dibahas dalam [4] dan [5]. Dalam penelitian  ini,  peneliti  ingin  mengembangkan protokol  perjanjian  kunci  yang  didasarkan  pada operasi matriks atas Aljabar Min-Plus.
Berdasarkan  latar  belakang  di  atas diidentifikasi  masalah  pentingnya  menjaga keamanan  informasi  yang  dikirim.  Hal  tersebut dapat  dilakukan  dengan menyepakati perjanjian antara  kedua  belah  pihak  dalam  pengiriman misal kunci atau password pengiriman. Berbagai metode  ditempuh  untuk  mengkonstruksi  kunci dalam  perjanjian  pengiriman  informasi.  Salah satu  metode  yang  dibahas  dalam  penelitian  ini adalah penggunaan operasi matriks atas aljabar Min-Plus yang akan diaplikasikan dalam pengkontruksian kunci rahasia atau password.

## Metode Penelitian
Dalam penelitian ini digunakan metode penelitian  studi  literatur  berupa  jurnal-jurnal ilmiah  yang  terkait  dengan  topik  penelitian,  dan buku-buku  referensi  yang  mendukung.  Pada tahap  awal  dipelajari  konsep-konsep  dasar tentang  Aljabar  Min-Plus  dan  Operasi  Matriks atas Aljabar Min-Plus beserta sifat-sifatnya yang dinyatakan dalam beberapa definisi dan teorema. Konsep-konsep ini nantinya digunakan sebagai  dasar  dalam  memahami  perkalian matriks  atas  Aljabar  Min-Plus  yang  akan digunakan dalam perhitungan protokol perjanjian  kunci.  Setelah  itu,  dipelajari  konsep- konsep  dalam  kriptografi  yang  digunakan  pada protokol perjanjian kunci.
Selanjutnya,  dipelajari  metode  protokol perjanjian  kunci  Stickel  (2005)  yang  telah dibahas  dalam  [3]  dan  menganalisa  perkalian matriks  atas  Aljabar  Min-Plus  [4]  yang  akan digunakan  sebagai  dasar  perhitungan  protokol perjanjian  kunci  yang  akan  dibuat  algoritma- algoritmanya.  Hal-hal  yang  dianalisa  adalah sifat-sifat Aljabar Min-Plus dan cara menghitung perkalian  matriks  atas  Aljabar  Min-Plus  dengan mengkaji pembahasan dalam [6] .
Langkah  terakhir  adalah  menerapkan hasil-hasil  yang  diperoleh  untuk  membuat rancangan algoritma-algoritma yang mendukung berjalannya  protokol  perjanjian  kunci  yang didasarkan  pada  operasi  matriks  atas  Aljabar Min-Plus.

## Hasil dan Diskusi

## Sistem Kriptografi Kunci Rahasia
Sistem  kriptografi  atau  sering  disebut dengan  cipher  merupakan  suatu  sistem  atau kumpulan  aturan-aturan  yang  digunakan  untuk melakukan enkripsi  dan dekripsi. Sistem kriptografi  simetris  adalah  sistem  kriptografi yang  menggunakan  kunci  enkripsi  dan  dekripsi yang sama. Sistem ini mengharuskan dua pihak yang  berkomunikasi  menyepakati  suatu  kunci rahasia  yang  sama  sebelum  keduanya  saling berkomunikasi.  Keamanan  dari  sistem  ini tergantung  pada  kunci,  membocorkan  kunci berarti bahwa orang  lain yang  berhasil mendapatkan kunci dapat mendekripsi cipherteks  [2].  Sistem  kriptografi  ini  sering disebut dengan sistem kriptografi kunci rahasia, seperti dijelaskan pada gambar berikut ini.
Sistem  kriptografi  atau  sering  disebut dengan  cipher  merupakan  suatu  sistem  atau kumpulan  aturan-aturan  yang  digunakan  untuk melakukan enkripsi  dan dekripsi. Sistem kriptografi  simetris  adalah  sistem  kriptografi yang  menggunakan  kunci  enkripsi  dan  dekripsi yang sama. Sistem ini mengharuskan dua pihak yang  berkomunikasi  menyepakati  suatu  kunci rahasia  yang  sama  sebelum  keduanya  saling berkomunikasi.  Keamanan  dari  sistem  ini tergantung  pada  kunci,  membocorkan  kunci berarti bahwa orang  lain yang  berhasil mendapatkan kunci dapat mendekripsi cipherteks [2].
Beberapa sistem kriptografi kunci rahasia  yang  saat  ini  telah  dikenal  secara  luas adalah  DES,  3DES,  Blowfish,  RC4,  A5  dan AES.  Sistem-sistem  kriptografi  yang  banyak digunakan  di  internet  adalah  RC4,  3DES  dan AES,  sedangkan  pada  pengamanan  telepon seluler  digunakan  sistem  kriptografi  A5.  Sistem kriptografi  AES  saat  ini  telah  menjadi  standar enkripsi  file  digital,  seperti  untuk  dokumen- dokumen rahasia.

## Aljabar Min Plus atas Z
Pada  penelitian  ini  digunakan  konsep- konsep  mengenai  matriks  Aljabar  Min-Plus. Berikut  ini  diberikan  pengertian-pengertian  dan sifat-sifatnya.  Berbeda  dengan  Aljabar  Min-Plus yang  dikenal  selama  ini  yaitu  didefinisikan  atas himpunan  semua  bilangan  real  R,  pada penelitian  ini  Aljabar  Min-Plus  yang  digunakan didefinisikan atas himpunan Z.
Aljabar  Min-Plus  atas  Z  merupakan himpunan  Z ∪ {+ ∞ }  yang  dilengkapi  dengan operasi  minimum,  dinotasikan  dengan ⊕ ,  dan operasi  penjumlahan  yang  dinotasikan  dengan ⊗ .  Selanjutnya  (Z ∪ {+ ∞ }, ⊕ , ⊗ )  dinotasikan dengan Z min .  Jadi, dalam Z min : 3 ⊕ 4 = min ( 3, 4 ) = 3 dan 3 ⊗ 4 = 3 + 4 = 7. Sifat –sifat yang berlaku dalam Z min antara lain:
1) x ⊕ (  y ⊕ z  )  =  min  (  x,  min  (  y,  z))  = min(min ( x,y), z ) =  (x ⊕ y) ⊕ z 2) x ⊕ {+ ∞ } = min ( x, + ∞ ) = x 3) x ⊗ {+ ∞ } = x + {+ ∞ } = {+ ∞ }
4) x ⊗ 0 = x + 0 = x 5) x ⊗ (y ⊗ z) = x + ( y + z ) = ( x + y) + z = ( x ⊗ y) ⊗ z 6) x ⊗ y =  x + y = y + x = y ⊗ x 7) x ⊗ (-x) = x + (-x) = 0 8) x ⊗ ( y ⊕ z ) = x + ( min (y, z)) = min ( x + y, x + z) = ( x ⊗ y) ⊕ (  x ⊗ z ) Dari sifat –sifat di atas, terlihat bahwa + ∞ merupakan  elemen  identitas  (elemen  netral) terhadap  operasi ⊕ dan  0  merupakan  elemen identitas  (elemen  satuan)  terhadap  operasi ⊗ . Oleh karena itu, ditinjau dari struktur aljabar R min merupakan semiring, yaitu:
1)  (Z ∪ {+ ∞ }, ⊕ )  merupakan  monoid komutatif dengan elemen netral + ∞ 2)  (Z ∪ {+ ∞ }, ⊗ )  merupakan  monoid dengan elemen satuan 0 3)  Operasi ⊗ terhadap ⊕ bersifat distributif 4)  Elemen netral terhadap operasi ⊕ , yaitu {+ ∞ } bersifat menyerap terhadap operasi ⊗ . Jadi  x ⊗ + ∞ = + ∞ ⊗ x = + ∞ , ∀ x ∈ Z min Selanjutnya  karena  operasi ⊕ bersifat idempotent, yaitu x ⊕ x = x , untuk setiap x ∈ Z min ,  maka  Z min merupakan  semiring  idempoten. Sifat idempotent ini mengakibatkan tidak adanya invers  terhadap  operasi  tersebut.  Lebih  lanjut karena  operasi  kedua  ,  yatu  “plus”  memiliki
invers,  maka  Z min merupakan    semifield idempotent.

## Matriks Atas Aljabar Minplus
Selanjutnya  seperti  pada  ring  pada umumnya,    jika  diberikan  suatu  semifield idempotent  Z min ,  dapat  dibentuk matriks dengan entri-entrinya  elemen-elemen  Z min .  Operasi ⊕ dan ⊗ pada  matriks  yang  telah  terbentuk didefinisikan sebagai berikut:
(1) ( ) ij ij ij A B A B ⊕ = ⊕
(2) ( ) ( ) ij ik kj k A B A B ⊗ = ⊕ ⊗ Contoh 1. Jika 0    2 -2  1 A   =     dan -2    3 1    2 B   =     , maka 0    2 -2    3 0 -2   2 3 -2    2
-2  1 1    2 -2 1   1 2 -2    1 A B ⊕ ⊕         ⊕ = ⊕ = =         ⊕ ⊕     
   dan 0    2 -2    3 (0+(-2) (2 1)     (0+3) (2 2) -2    3
-2  1 1    2 (-2+(-2)) (1 1)    (-2+3) (1 2) -4    1 A B ⊕ + ⊕ +         ⊗ = ⊗ =         ⊕ + ⊕ +         Selanjutnya didefinisikan (Z min ) n×n sebagai himpunan semua matriks berukuran n× n  dengan  entri-entrinya  elemen  Z min, .  Elemen netral  terhadap  operasi ⊕ dan  elemen  netral terhadap operasi ⊗ dalam (Z min ) n× n berturut-turut adalah matriks E
dengan 0,  jika ( ) ,  jika ij i j E i j =  =  +∞ ≠  dan  matriks ε
dengan ( ε ) ij = + ∞ ,untuk setiap i dan j . Jadi ,
(1)  ( E ⊗ A ) = (A ⊗ E ) = A untuk setiap A ∈ ( Z min ) n × n ; (2)  ( ε ⊕ A ) = (A ⊕ ε ) = A, untuk setiap A ∈ (Z min ) n × n .
Berikut  ini  beberapa  sifat  matriks  atas aljabar min-plus :
Sifat 2. Jika A, B, C ∈ ( Z min ) n × n maka berlaku :
(1)  A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C (2)  A ⊕ B = B ⊕ A (3)  A ⊗ ( B ⊗ C ) = ( A ⊗ B ) ⊗ C
(4)  A ⊗ ( B ⊕ C ) = ( A ⊗ B) ⊕ ( A ⊗ C ) (5)  ( A ⊕ B ) ⊗ C =  ( A ⊗ C ) ⊕ ( B ⊗ C) (6)  A ⊕ A = A Bukti : 1. [A ⊕ ( B ⊕ C )] ij = A ij ⊕ (B ij ⊕ C ij ) = (A ij ⊕ B ij ) ⊕
C ij = [ (A ⊕ B) ⊕ C ] ij . 2. [A ⊕ B] ij = A ij ⊕ B ij = B ij ⊕ A ij = [B ⊕ A] ij . 3. [ ] ( ) ij A B C ⊗ ⊗ = 1 1 n n ik kl lj k l A B C = =   ⊕ ⊕ ⊗     = 1 1 n n ik kl lj k l A B C = = ⊕ ⊕ ⊗ ⊗ = 1 1 n n ik kl lj k l A B C = =   ⊕ ⊕ ⊗ ⊗     = [ ] ( ) ij A B C ⊗ ⊗ 4. [ ] ( ) ij A B C ⊗ ⊕ = ( ) 1 n ik kj kj k A B C = ⊕ ⊕ = ( ) ( ) ( ) 1 n ik kj ik kj k A B A C = ⊕ ⊗ ⊕ ⊗ = ( ) 1 1 n n ik kj ik kj k k A B A C = =     ⊕ ⊗ ⊕ ⊕ ⊗         = [ ] ( ) ( ) ij A B A C ⊗ ⊕ ⊗ 5. [ ] ( ) ) ij A B C ⊕ ⊗ = ( ) 1 n ik ik kj k A B C = ⊕ ⊕ = ( ) ( ) ( ) 1 n ik kj ik kj k A C B C = ⊕ ⊗ ⊕ ⊗ = ( ) ( ) 1 1 n n ik kj ik kj k k A C B C = = ⊕ ⊗ ⊕ ⊕ ⊗ = [ ] ( ) ( ) ij A C B C ⊗ ⊕ ⊗ 6. [ ] ij A A ⊕ = ij ij ij A A A ⊕ = .
Berdasarkan  sifat-sifat  di  atas,  (  Z min ) n  ×  n merupakan semiring idempotent.

## Protokol Perjanjian Kunci
Apabila  Pihak  1  dan  Pihak  2  menggunakan sistem kriptografi kunci rahasia, masalah utama yang muncul adalah keduanya harus menyepakati kunci yang sama, padahal keduanya tidak dapat bertemu secara langsung. Apabila  Pihak  1  mengirimkan  kunci  kepada
Pihak  2,  maka  Pihak  3  dapat  mengetahui  kunci yang  dikirimkan,  hal  ini  dikarenakan  proses pengiriman  melalui  jalur  komunikasi  yang  tidak aman.
Salah  satu  cara  yang  dapat  digunakan untuk mengatasi masalah ini adalah menggunakan  protokol  perjanjian  kunci  (key establishment  protocol).  Protokol  perjanjian kunci  bertujuan  agar  kedua  belah  pihak  dapat menentukan  kunci  yang sama walaupun dilakukan  melalui  jalur  komunikasi  yang  tidak aman.  Salah  satu  contoh  protokol  perjanjian kunci  yang  paling  sederhana  dan  telah  dikenal secara  luas  adalah  protokol  perjanjian  kunci Diffie-Hellman  yang  dipublikasikan  pada  tahun 1976.
Pihak 1 atau Pihak 2 mempublikasikan suatu grup siklik Gdengan elemen pembangun
g G ∈ . Pihak 1 Pihak 2 1.  Pihak 1 memilih secara rahasia suatu bilangan bulat positif a
2.  Pihak 1 menghitung
a g
3.  Pihak 1 mengirim a g kepada Pihak 2
4.  Pihak 1 menerima
b g dari Pihak 2
5.  Pihak 1 menghitung ( ) 1 a b ba K g g = =
1.  Pihak 2 memilih secara rahasia suatu bilangan bulat positif b 2.  Pihak 2
menghitung b g
3.  Pihak 2  mengirim
b g kepada Pihak
1
4.  Pihak 2
menerima a g dari Pihak 1 5.  Pihak 2 menghitung ( ) 2 b a ab K g g = =
Pihak 1 dan Pihak 2 telah menyepakati kunci
rahasia 1 2 K K K = =
Gambar 1. Skema Protokol Perjanjian Kunci Diffie-Hellman [3].
Diketahui  grup  siklik  G  merupakan  grup komutatif, maka ab ba = , sehingga
1 2 K K K = = .  Misalkan  Pihak  1  dan  Pihak  2 berhasil  menyepakati  kunci  rahasia  yang  sama yaitu K. Selanjutnya, kunci rahasia K yang telah disepakati  digunakan  untuk  melakukan  proses enkripsi-dekripsi.  Di  lain  pihak,  Pihak  3  sebagai
penyerang  hanya  dapat  mengetahui  nilai  g, a g dan b g .  Untuk  mendapatkan  kunci  yang  telah disepakati  Pihak  1  dan  Pihak  2,  maka  Pihak  3 harus  menentukan  nilai  a  atau  b.    Dengan  kata lain,  Pihak  3  harus  menyelesaikan  masalah logaritma diskrit pada G,  yaitu menentukan nilai a  apabila  nilai    g  dan a g diketahui.  Tingkat kemanan  dari  protokol  perjanjian  kunci  Diffie- Hellman  didasarkan  pada  masalah  logaritma diskrit [1].
Pada  protokol  perjanjian  kunci  Diffie- Hellman  digunakan  grup  siklik  yang  merupakan grup  komutatif.  Dalam  [3]  telah  diperkenalkan konsep mengenai protokol perjanjian kunci yang menggunakan  grup  non-komutatif.  Untuk  dapat menggunakan  grup  tidak  komutatif,  protokol perjanjian  kunci  harus  dapat  dikonstruksi menggunakan  suatu  permasalahan  matematis yang ada pada grup non-komutatif.  Skema protokol perjanjian kunci Stickel yang didasarkan  atas  grup  non-komutatif  adalah sebagai berikut.
Pihak 1 atau Pihak 2 mempublikasikan suatu grup non-komutatif G dan
, , a b G ab ba ∈ ≠ , dengan N dan M berturut-turut adalah order dari a dan b
Pihak 1 Pihak 2 1.  Pihak 1 memilih secara rahasia n N < dan m M < 2.  Pihak 1 menghitung n m u a b =
3.  Pihak 1 mengirim u kepada Pihak 2 4.  Pihak 1 menerima v dari Pihak 2 5.  Pihak 1 menghitung
1 n m K a vb = 1.  Pihak 2 memilih secara rahasia r N < dan s M < 2.  Pihak 2 menghitung r s v a b = 3.  Pihak 2 mengirim v kepada Pihak
1 4.  Pihak 2 menerima u dari Pihak 1 5.  Pihak 2
menghitung
2 r s K a ub =
Pihak 1 dan Pihak 2 telah menyepakati
kunci rahasia 1 2 K K K = =
Gambar 2. Skema Protokol Perjanjian Kunci Stickel
Dapat  ditunjukkan  bahwa  Pihak  1  dan  Pihak  2 berhasil menyepakati kunci  rahasia  yang  sama, yaitu
= = = = = = .
Salah  satu  contoh  grup  yang  dapat digunakan  adalah  grup  perkalian  matriks  atas suatu lapangan hingga. Penggunaan grup pada Protokol  Stickel  ini  dapat  diperumum  menjadi sebarang  semigrup,  juga  dapat  diperumum menjadi  sebarang  semiring.  Pada  penelitian  ini semiring  yang  digunakan  adalah  himpunan semua  matriks  nxn  atas  bilangan  bulat  dengan operasi penjumlahan dan perkaliannya didefinisikan  atas  suatu  aljabar  min-plus,  yaitu (Z min ) n × n .

## Operasi Perkalian Matriks atas Aljabar Min Plus
Pada  pembahasan  operasi  perkalian matriks  atas  aljabar  min  plus  telah  dibuktikan bahwa  operasi  perkalian  matriks  atas  aljabar min plus memenuhi sifat assosiatif. Oleh karena itu, dapat diperoleh sifat berikut:

## Teorema 1.
Jika A merupakan matriks atas aljabar min plus, maka berlaku A m ⊗ A n =  A n ⊗ A m .

## Bukti :
Karena  perkalian  matriks  atas  aljabar  min  plus memenuhi  sifat  assosiatif,  maka  jelas  berlaku sifat di atas .

## Contoh 2.
Diberikan  matriks  atas  aljabar  min  plus
      = 3 11 7 1 A .
Diperoleh
      =       ⊗   
   = 6 12 8 2 3 11 7 1 3 11 7 1 2 A ;
      =       ⊗       = 11 13 9 3 3 11 7 1 6 12 8 2 3 A ;
      ⊗       = ⊗ 11 13 9 3 6 12 8 2 3 2 A A       = 17 15 11 5 2 3 6 12 8 2 11 13 9 3 A A ⊗ =       ⊗       =
Penerapan  Operasi  Matriks  atas  Aljabar  Min Plus pada Protokol  Perjanjian Kunci
Berdasarkan  sifat  operasi  matriks  atas aljabar  min  plus  di  atas,  selanjutnya  dapat disusun algoritma untuk melakukan pembentukan kunci sebagai berikut :
Pihak  1  atau  Pihak  2  mempublikasikan  suatu semiring ( Z min ) n × n dan A, B ∈ ( Z min ) n × n
Pihak 1 Pihak 2 1.  Pihak 1 memilih secara rahasia bilangan asli n dan m 2.  Pihak 1 menghitung  u  =  A n B m 3.  Pihak 1  mengirim u kepada Pihak 2 4.  Pihak 1 menerima v dari Pihak 2 5.  Pihak 1 menghitung K 1 = A n
v  B m 1.  Pihak 2 memilih secara rahasia bilangan asli r dan s 2.  Pihak  2  menghitung
v = A r B s
3.  Pihak  2  mengirim  v kepada Pihak 1
4.  Pihak  2  menerima  u dari Pihak 1
5.  Pihak  2  menghitung
K 1 = A n u  B m
Pihak 1 dan Pihak 2 telah menyepakati kunci rahasia
1 2 K K K = =
Menurut  sifat  perkalian  matriks  atas aljabar min plus diperoleh:
K 1 = s r s m n r m s r n m n uB A B B A A B B A A vB A = = = = K 2 .
Oleh  karena  itu  pihak  satu  dan  pihak  dua  telah berhasil menyepakati kunci yang sama.
   =       = 6 2 ; 3 11 7 1 menentukan 2 pihak atau 1
Pihak B A Pihak 1 Pihak 2 1.  Memilih secara rahasia  n = 2, m = 5 1. Memilih  secara  rahasia r = 3, s = 4
2.  Menghitung  U = A 2 B 5
=       = 11 16 11 12 U 2. Menghitung  V = A 3 B 4
V =       15 20 11 11
3.  Mengirim U ke pihak 2 3. mengirim V ke pihak 1 4.  Pihak  1    menghitung
K 1 = A 2
V B 5       = 9 14 13 18 1 K 4. Pihak 2 menghitung  K 2 = A 3 U B 4       = 9 14 13 18 2 K
Pihak  1  dan  pihak  2  menyepakati  kunci  yang  sama yaitu  K = K1 = K2

## Implementasi  Algoritma  untuk  Pengamanan
Pesan

## Misal pihak 1 akan mengirim pesan BOS
AWAS  DISADAP    LO    kepada  pihak  2  .  Oleh karena itu pesan tersebut dipecah menjadi blok- blok  4  huruf  yaitu  BOSA-WASD-ISAD-APLO. Selanjutnya  tiap  blok  di  ubah  ke  dalam    angka- angka menurut table konversi berikut:
Akhirnya diperoleh plain teks sebagai berikut :
    
 = 0 18 14 1 1 P ;
      = 3 18 0 22 2 P ;       = 3 0 18 8 3 P ; 
     = 14 11 15 0 4 P .
Tahap  selanjutnya  adalah  mengenkripsi  pesan dengan  menggunakan  kunci       = 9 14 13 18 K
dan  melakukan  perhitungan  mod  26  akan diperoleh cipher teks  sebagai berikut:
C 1 = K + P 1 = +       9 14 13 18
      =       =       9 6 1 19 9 32 27 19 0 18 14 1 = TBGJ. C 2 = K + P 2 = +       9 14 13 18 =       =       =       12 6 13 14 12 32 13 40 3 18 0 22 ONGM.
C 2 = K + P 3 = +       9 14 13 18 =       =       =       12 14 5 0 12 14 31 26 3 0 18 8
AFOM.
C 4 = K + P 4 = +       9 14 13 18 =       =       =       23 25 2 18 23 25 28 18 14 11
15 0
SCZX. Jadi, pihak 1 akan mengirim pesan TBGJONGMAFOMSCZX    kepada  pihak  2. Selanjutnya  pihak  2  akan  mendeskripsi  pesan tersebut  dengan  kunci  yang  sama,  yaitu
      9 14 13 18
menurut  langkah-langkah  sebagai

## berikut :
Langkah  1.  Membagi  pesan  menjadi  blok  4 karakter: TBGJ-ONGM-AFOM-SCZX.
Langkah  2.  Mengubah  pesan  menjadi  matriks yaitu:
C 1 =       9 6 1 19 ; C 2 =       12 6 13 14 ;
C 3 =  
    12 14 5 0 ; C 4 =       23 25 2 18
.
Langkah  3.  Mendeskripsi  pesan  dengan  cara sebagai berikut:
P 1 =  C 1
–  K  =      
9 6 1 19 -       9 14 13 18 =       = 0 18 14 1 BOSA.
P 2 =  C 2 –  K  =       12 6 13 14
-
      9 14 13 18 =       3 18 0 22 = WASD.
P 3 =  C 3 –  K  = 
    
12 14 5 0 -
     
9 14 13 18 =       3 0 18 8 = ISAD.
P 4 =  C 4 –  K  =       23 25 2 18 -       9 14 13 18 =       14 11 15 0 = APLO.
Pada  tahap  ini  pihak  satu  telah  berhasil membaca  pesan  tersebut,  yaitu    “  BOS  AWAS DISADAP LO “.

## Kesimpulan
Sifat  perkalian  matriks  atas  aljabar  min plus  dapat  diterapkan  untuk  menentukan  kunci sebagai  password  pada  proses  pengamanan informasi  rahasia.  Algoritma  untuk  menentukan kunci tersebut adalah sebagai berikut:
Pihak  1  atau  Pihak  2  mempublikasikan  suatu semiring ( Z min ) n × n
dan A, B ∈ ( Z min ) n × n
Pihak 1 Pihak 2 1.  Pihak 1 memilih secara  rahasia bilangan  asli  n dan m 2.  Pihak 1 menghitung  u  = A n B m 3.  Pihak 1 1.  Pihak  2  memilih secara rahasia bilangan asli r dan s 2.  Pihak 2 menghitung v = A r
B s 3.  Pihak  2  mengirim
mengirim u kepada Pihak 2 4.  Pihak 1 menerima v dari Pihak 2 5.  Pihak 1 menghitung  K 1 = A n v  B m
v kepada Pihak 1 4.  Pihak 2 menerima u dari Pihak 1 5.  Pihak 2 menghitung  K 1 =
A n u  B m
Pihak  1  dan  Pihak  2  telah  menyepakati  kunci
rahasia 1 2 K K K = =
Untuk  mengamankan  informasi  rahasia, pesan  dapat  dienkripsi  dengan  mengubah pesan menjadi blok-blok karakter sesuai dengan ukuran  matriks,  kemudian  enkripsi  dapat dilakukan  dengan  rumus  C i =  K+P i .  Pihak penerima  pesan  dapat  mendeskripsi  pesan tersebut  dengan  langkah  yang  sama  dan  untuk membaca pesan dapat digunakan rumus P i = C i – K.

## Ucapan Terimakasih
Tim  Peneliti  mengucapkan  terimakasih  kepada Universitas  Negeri  Yogyakarta,  khususnya Fakultas  MIPA  yang  telah  mendanai  kegiatan penelitian ini.

## Pustaka
[1]  A.  J.  Menezes,  P.  C.  Oorschoot,  dan  S.  A. Vanstone: Handbook of Applied Cryptography, CRC Press, Canada, 1996.
[2]  M.  Zaki  Riyanto:  Protokol  Perjanjian  Kunci Berdasarkan  Masalah  Konjugasi  atas  Grup Non-komutatif, dipresentasikan pada Seminar  Nasional  MIPA,  FMIPA  UNY Yogyakarta, 2011.
[3]  M.  Alexei,  V.  Shpilrain  dan  A.  Ushakov: Group-based Cryptography, Birkhauser Verlag,  Basel Switzerland, 2008.
[4]  Musthofa:  Sistem  Persamaan  Linear  pada Aljabar  Min-Plus,  dipresentasikan  pada Seminar  Nasional  MIPA,  FMIPA  UNY Yogyakarta, 2011.
[5]  J.  Y.  Le  Boudec,  P.  Thiran,  P:  Min-plus System  Theory  Applied  to  Communication
Network, Swiss. Didownload pada tanggal 5 Mei 2011.
[6]  D.  Grigoriev  dan  S.  Vladimir:  Tropical Crypthography.  Didownload  pada  tanggal 28 Mei 2013.