Penerapan Aritmatika Modulo dan Matriks dalam Cipher Hill Edward Samuel Pasaribu - 13510065 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia
[email protected]
Abstrak—Aritmatika modulo dan matriks banyak digunakan dalam kehidupan sehari-hari, salah satunya dalam bidang kriptografi. Makalah ini membahas tentang penggunaan aritmatika modulo dan matriks pada cipher Hill. CipherHill merupakan salah satu teknik kriptografi sederhana dengan polygraphic substitution cipher. Pada proses enkripsi dan dekripsi, cipher Hill mengelompokkan huruf-huruf dalam sejumlah kelompok lalu mengalikannya dengan suatu matriks kunci yang kemudian dicari hasilnya yang kongruen dengan jumlah karakter yang didefinisikan. Selain itu pada makalah ini dibahas juga cara meningkatkan jumlah kunci yang diperbolehkan dan cara memperkuat cipher Hill ini.
berbagai jenis dan setiap jenisnya terdiri dari berbagai variasi. Cipher yang paling sederhana adalah substitution cipher. Pada substitution cipher, setiap simbol digantikan oleh sebuah simbol lain. Pada simple substitution cipher penggantian simbol ini bersifat tetap dalam suatu proses kriptografi, artinya suatu huruf pasti akan digantikan oleh huruf yang sama untuk setiap kasusnya. Salah satu contoh dari cipher ini adalah cipher Caesar yang menggeser posisi huruf. Contoh cipher Caesar dengan menggeser 5 huruf adalah sebagai berikut.
Kata Kunci—Cipher Hill, Matriks, Modulo
I. PENDAHULUAN Struktur diskrit atau lebih dikenal dengan matematika diskrit merupakan cabang ilmu matematika yang membahas hal-hal yang bersifat diskrit. Aritmatika modulo dan matriks merupakan bagian dari matematika diskrit. Banyak penerapan dari aritmetika modulo dan matriks dalam kehidupan sehari-hari, salah satunya adalah dalam penjagaan kerahasiaan data atau dikenal dengan kriptografi. Dalam kriptografi sendiri terdapat dua proses utama, yaitu enkripsi dan dekripsi. Enkirpsi adalah suatu proses untuk mengamankan data, yaitu dari data asli, yang dikenal dengan plaintext, menjadi data tersandi, yang dikenal dengan chipertext. Sedangkan proses dekripsi merupakan kebalikan dari enkripsi, yaitu mengubah chipertext menjadi plaintext.
Gambar 1.1 Proses pada kriptografi: enkripsi dan dekripsi Terdapat berbagai cara untuk melakukan enkripsi dan dekripsi salah satunya adalah dengan menggunakan cipher. Cipher adalah algoritma yang digunakan untuk melakukakan kriptografi. Cipher sendiri terdiri dari
Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012
Plain Cipher Plain Cipher
A F N S
B G O T
C H P U
D I Q V
E J R W
F K S X
G L T Y
H M U Z
I N V A
J O W B
K P X C
L Q Y D
M R Z E
Maka pada proses enkripsi, dengan mengubah masingmasing huruf plaintext menjadi chipertext. Demikian juga pada proses dekripsi. Plain : INFORMATIKAITB Chiper : NSKTWRFYNPFNYG Dekripsi : INFORMATIKAITB Terlihat bahwa pada jenis simple substitution cipher mudah ditebak dengan melihat susunan dan statistik huruf, karena setiap hurufnya digantikan oleh suatu huruf yang lain. Kemudian terdapat homophonic substitution, di mana dalam cipher ini setiap karakter dapat digantikan oleh beberapa karakter simbol ciphertext. Tujuannya adalah untuk meratakan frekuensi kemunculan masing-masing simbol. Pada perkembangan selanjutnya terdapat polyalphabetic substitution cipher. Di mana pada cipher jenis ini, setiap huruf digantikan oleh huruf lain bergantung pada karakter kunci yang kemudian dicocokan dengan sebuah tabel simbol. Cipher yang cukup terkenal dari jenis ini adalah cipher Vigenère. Pada jenis yang terakhir, polighraphic substitution cipher karakter dikelompokkan menjadi beberapa anggota dan diproses sekaligus. Cipher Hill merupakan salah satu cipher jenis ini. Dalam melakukan enkripsi dan dekripsi, cipher Hill memanfaatkan teknik aritmatika modulo dan operasi matriks. Pada tulisan ini akan dibahas mengenai
penerapan aritmatika modulo dan matriks dalam cipher Hill baik dalam proses enkripsi maupun dekripsi.
II. ARITMATIKA MODULO DAN MATRIKS A. Aritmatika Modulo Aritmatika modulo merupakan sebuah operasi yang menghasilkan sisa pembagian dari suatu bilangan terhadap bilangan lainnya. Didefinisikan operasi modulo sebagai berikut. Misalkan adalah bilangan bulat dan adalah bilangan bulat > 0. Operasi mod memberikan sisa jika dibagi dengan . Dengan kata lain, sedemikian sehingga , dengan . Atau dapat dituliskan sebagai, untuk sembarang bilangan bulat dan modulus , misal
adalah matriks persegi dan matriks identitas. Matriks persegi adalah matriks dengan jumlah baris dan kolom yang sama. Matriks identitas adalah matriks persegi yang setiap elemen diagonalnya bernilai 1 dan elemen lainnya bernilai 0. Terdapat berbagai operasi dasar matriks. Di antaranya pejumlahan, pengurangan, perkalian dengan matriks, dan perkalian dengan skalar. Untuk penjumlahan dan pengurangan A B C , maka nilai elemen pada matriks C adalah cij aij bij . Untuk perkalian matriks dengan matriks, misal A matriks berukuran m p dan B berukuran p n maka perkalian AB menghasilkan matriks C berukuran dengan elemen matriks C
m n
p
cij aik bkj k 1
(2.1) maka, r (disebut residu) sebagai hasil dari a mod m adalah
R, untuk a 0 r m R, untuk a 0 dan R 0 0, untuk a 0 dan R 0
(2.5)
k. A C , maka nilai elemen pada matriks C adalah cij k .aij . Untuk perkalian matriks dengan skalar
Pada matriks persegi terdapat istilah invertible (atau nonsingular). Jika A matriks persegi dan terdapat suatu matriks persegi B yang berukuran sama yang memenuhi
(2.2) Dalam aritmatika modulo juga dikenal kekongruenan atau equivalent. Jika m adalah bilangan bulat positif dan a serta b adalah bilangan bulat, maka dikatakan a kongruen terhadap b dalam modulus m
AB BA I
(2.6) maka A disebut invertible dan B adalah matriks inversi dari A yang sering dilambangkan dengan A-1.
III. CIPHER HILL
a b (mod m)
(2.3)
jika a b adalah kelipatan bulat dari m. Modulo juga mempunyai balikan modulo (invers modulo). Jika a dan m relatif prima dan m > 1, maka terdapat suatu bilangan yang merupakan balikan inversi (dilambangkan dengan a-1) yang memenuhi
aa 1 1 (mod m) B. Matriks Matriks adalah kumpulan bilangan berbentuk persegi panjang yang tersusun atas baris dan kolom. Bilangan penyusun matriks disebut dengan elemen matriks. Misalkan terdapat matriks A yang terdiri dari m baris dan n kolom. Maka,
a11 a A 21 a m1
a12 a 22 am2
a1n a2n a mn
(2.4) sedangkan aij merupakan elemen matriks baris ke-i dan kolom ke-j. Terdapat berbagai macam matriks khusus di antaranya
Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012
A. Sejarah Cipher Hill merupakan polygraphic substitution cipher. [4] Cipher Hill termasuk dalam kriptografi klasik. Cipher Hill ditemukan oleh Lester S. Hill pada tahun 1929, yang dipublikasikan pada jurnal The American Mathematical Monthly. Cipher Hill menjadi polygraphic substitution cipher sistematik pertama yang dapat mengoperasikan lebih dari tiga simbol sekaligus. [7]
B. Enkripsi menggunakan Cipher Hill Pada cipher Hill, untuk melakukan enkripsi harus ditentukan sebuah tabel penomoran simbol, di mana masing-masing simbol memiliki nilai tertentu. Misalkan jumlah simbol ada m simbol. Jangkauan nilai yang diperbolehkan adalah mulai dari 0 sampai dengan m – 1. Setelah itu dipilih sebuah matriks kunci yang merupakan matriks persegi dan bersifat invertible. Pemilihan matriks bersifat invertible dalam modulus m bertujuan agar plaintext yang dienkripsi dapat kembali dikembalikan seperti semula melalui proses dekripsi. Setiap elemen dari matriks kunci juga harus berada pada jangkauan mulai dari 0 sampai m – 1. Misalkan dipilih sebuah matriks kunci A yang berukuran n n .
Ann
a11 a12 a1n a 21 a 22 a 2 n a n1 a n 2 a nn
ciphertext menjadi matriks cipher dengan terlebih dahulu mengubah simbol-simbol menjadi angka yang bersesuaian dengan tabel. Dari persamaan (3.3) didapatkan
AM C
A1 AM A1C IM A1C
(3.1) Plaintext yang diberikan kemudian dikelompokkan sejumlah n anggota berurut dari kiri ke kanan di mana n adalah ukuran matriks kunci. Jika jumlah karakter tidak memenuhi n, maka harus dilakukan penambahan karakter dummy sembarang pada bagian akhir sampai kelompok simbol tersebut memenuhi n anggota. Namun, pada umumnya dilakukan penambahan karakter terakhir terus menerus hingga memenuhi n anggota. Maka dari langkah ini didapatkan k kelompok simbol yang masing-masing beranggotakan n anggota. Kemudian plaintext ini dikonversikan menjadi nilai yang sesuai dengan tabel yang dibuat sebelumnya. Susun setiap kelompok angka tersebut menjadi n baris dan k kolom, di mana pada kolom pertama merupakan nilainilai kelompok simbol pertama yang disusun ke bawah, begitu juga dengan kolom-kolom berikutnya. Susunan ini disebut sebagai matriks pesan M.
M nk
m11 m12 m1k m21 m22 m2 k m n1 mn 2 mnk
M A1C (3.4) Dari persamaan (3.4) terlihat bahwa matriks A haruslah bersifat invertible (mempunyai inverse) dalam modulus m. Jika matriks A tidak invertible dalam modulus m maka proses dekripsi tidak dapat dilakukan, sehingga proses enkripsi akan menjadi sia-sia karena ciphertext yang terbentuk tidak dapat dikembalikan seperti semula.
AA1 A1 A I (mod m) (3.5) Dengan melakukan perkalian inversi dari matriks kunci A dengan matriks berisi ciphertext maka akan kembali didapatkan matriks pesan yang nilainya telah dimodulasikan dengan jumlah simbol yang ada dalam tabel (m). Susun kembali matriks pesan menjadi pesan yang diinginkan. Maka akan didapat kembali plaintext awal sebelum dilakukan enkripsi. Jika diperlukan, buang karakter dummy pada bagian akhir plaintext yang tidak diinginkan.
IV. HASIL DAN ANALISIS A. Contoh Enkripsi menggunakan Cipher Hill dengan matriks kunci 2×2
(3.2) Lalu kalikan matriks kunci A dengan matriks pesan M sehingga mendapatkan sebuah matriks baru yang berukuran sama dengan matriks M. Sesudah itu, hasil perkalian ini dimodulasikan dengan jumlah simbol yang ada dalam tabel (m).
AM C0
C mod m
(3.3) Dari proses itu, akan didapat sebuah matriks baru, misalkan matriks C. Susun kembali elemen matriks tersebut menjadi sebuah baris seperti proses pembentukan matriks pesan yang langkahnya berkebalikan. Kemudian ganti angka-angka tersebut dengan karakter yang ada dalam tabel. Maka disapatlah sebuah ciphertext. Dengan demikian proses enkripsi telah selesai.
Misalkan plaintext yang akan dienkripsi adalah INFORMATIKAITB. Maka akan ditentukan sebuah tabel konversi simbolangka terlebih dahulu. Tabel 4.1 Contoh Tabel Konversi Simbol ke Angka Simbol A B C D E F G H I J K Nilai 0 1 2 3 4 5 6 7 8 9 10 Simbol N O P Q R S T U V W X Nilai 13 14 15 16 17 18 19 20 21 22 23
L 11 Y 24
M 12 Z 25
Dipilih sebuah matriks kunci berukuran 2 2 yang bersifat invertible dalam modulus 26.
9 7 A 5 4
C. Dekripsi menggunakan Cipher Hill Jika telah diketahui matriks kunci A dan tabel konversi simbol yang dipergunakan untuk enkripsi, maka proses dekripsi dapat dilakukan dengan mudah seperti membalikan proses pada enkripsi. Susun kembali
Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012
Dilakukan pengelompokan huruf yang masing-masing berjumlah 2 huruf, sesuai dengan ukuran matriks kunci. Lalu dikonversi menjadi nilai-nilai yang bersesuaian dengan tabel.
terlebih dahulu. (IN) (FO) (RM) (AT) (IK) (AI) (TB) (8 13) (5 14) (17 12) (0 19) (8 10) (0 8) (19 1) Disusun menjadi sebuah matriks pesan M
8 5 17 0 8 0 19 M 13 14 12 19 10 8 1 Lalu dikalikan, matriks kunci A dengan matriks pesan M.
9 7 8 5 17 0 8 AM 5 4 13 14 12 19 10 163 143 237 133 142 92 81 133 76 80
0 19 8 1 56 178 32 99
7 13 3 3 12 4 22 (mod 26) 14 3 3 24 2 6 21 Maka akan didapat matriks yang berisi ciphertext.
7 13 3 3 12 4 22 C 14 3 3 24 2 6 21 (7 14) (13 3) (3 3) (3 24) (12 2) (4 6) (22 21) (HO) (ND) (DD) (DY) (MB) (EG) (WV) Sehingga, didapatkan ciphertext HONDDDDYMBEGWV.
B. Contoh Dekripsi menggunakan Cipher Hill dengan matriks kunci 2×2 Misalkan plaintext yang akan didekripsi adalah HONDDDDYMBEGWV yang merupakan hasil enkripsi pada bagian sebelumnya. Dengan menggunakan tabel konversi simbol-angka yang sama seperti tabel 4.1 dan sebuah matriks kunci yang sama dengan proses enkripsi. Dilakukan pengelompokan huruf yang masing-masing berjumlah 2 huruf, sesuai dengan ukuran matriks kunci. Lalu dikonversi menjadi nilai-nilai yang bersesuaian dengan tabel. (HO) (ND) (DD) (DY) (MB) (EG) (WV) (7 14) (13 3) (3 3) (3 24) (12 2) (4 6) (22 21) Disusun menjadi sebuah matriks ciphertext C.
7 13 3 3 12 4 22 C 14 3 3 24 2 6 21 Perlu dicari inversi dari matriks A dalam modulus 26
Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012
7 1 4 A1 9 4 7 5 (mod 26) 5 9 19 1 4 1 (mod 26) 21 9 4 19 (mod 26) 21 9 Lalu kalikan inversi matriks kunci A dengan matriks berisi ciphertext C.
4 19 7 13 3 3 12 4 A1C 21 9 7 3 3 24 2 6 294 109 69 468 86 130 273 300 90 279 270 138
22 21 487 651
8 5 17 0 8 0 19 (mod 26) 13 14 12 19 10 8 1 Maka akan didapat matriks pesan.
8 5 17 0 8 0 19 M 13 14 12 19 10 8 1 (8 13) (5 14) (17 12) (0 19) (8 10) (0 8) (19 1) (IN) (FO) (RM) (AT) (IK) (AI) (TB) Sehingga, didapatkan plaintext INFORMATIKAITB.
C. Usaha Peretasan pada Cipher Hill Usaha untuk melakukan peretasan cipher hill sangatlah sulit jika yang hanya diketahui ciphertext saja. Hal ini disebabkan tidak adanya pola dalam ciphertext. Setiap simbol ciphertext dipengaruhi oleh simbol dalam satu blok. Untuk melakukan peretasan pada cipher Hill perlu diketahui setidaknya potongan plaintext dan ciphertext yang saling berhubungan sebesar ukuran panjang matriks kunci. Selain itu perlu juga diketahui tabel konversi nilai dalam cipher Hill. Jika telah diketahui semua itu, cipher Hill dapat diretaskan dengan bantuan perhitungan matematika. Misalkan diketahui ciphertext HONDDDDYMBEGWV, dan kata dimulai dengan INFO serta diketahui panjang kunci 4 dan tabel konversi seperti tabel 4.1. Akan dilakukan pembentukan matriks potongan pesan dan matriks potongan ciphertext.
8 5 M 1,2,3,4 13 14 7 13 C1,2,3,4 14 3 Dari persamaan (3.3) dapat dicari matriks kunci yang digunakan untuk melakukan dekripsi.
AM C
A1 AM A1C M A1C MC 1 A1CC 1 A1 MC 1 (4.1) Akan dicari matriks kunci dari informasi yang diberikan di atas melalui persamaan (4.1).
3 13 C1,2,3,4 1 (7 3 13 14) 1 (mod 26) 14 7 3 13 (161) 1 (mod 26) 12 7 3 13 (21) 1 (mod 26) 12 7 3 13 5 (mod 26) 12 7 15 60 15 8
65 (mod 26) 35 13 (mod 26) 9
Maka, didapat matriks kunci untuk dekripsi
A1 M 1,2,3,4C1,2,3,4 1 8 5 15 13 (mod 26) 13 14 8 9 160 149 (mod 26) 307 295 4 19 (mod 26) 21 9 Lalu, dengan cara yang sama seperti pada proses dekripsi didapatkan
Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012
4 19 7 13 3 3 12 4 22 A1C 21 9 7 3 3 24 2 6 21 8 5 17 0 8 0 19 (mod 26) 13 14 12 19 10 8 1 Sehingga, didapatkan kembali plaintext yang sama, yaitu INFORMATIKAITB.
D. Analisis Tambahan mengenai Cipher Hill Pada cipher Hill, cukup sulit untuk menentukan kunci yang sesuai, yaitu kunci yang bersifat invertible terhadap modulus jumlah karakter. Untuk memastikan suatu matriks bersifat invertible cukup memastikan bahwa determinan dari matriks kunci tersebut tidaklah 0. Tetapi untuk memastikan bahwa kunci bersifat invertible terhadap modulo tertentu, juga dapat dilihat dari determinan matriks tersebut. Determinan matriks kunci tersebut pada dasarnya harus mempunyai inverse terhadap modulo jumlah simbol yang ada. Dengan kata lain, residu determinan matriks kunci terhadap modulo jumlah simbol dalam tabel haruslah saling prima terhadap jumlah simbol dalam tabel. Pada kasus contoh di atas, jumlah simbol dalam tabel adalah 26 sehingga, determinan matriks kunci harus tidak boleh habis dibagi 2, 13, atau 26. Sehingga, penggunaan 26 simbol pada tabel cukup mengurangi jumlah matriks kunci yang diperbolehkan. Untuk mengatasi sedikitnya jumlah matriks kunci yang diperbolehkan, maka dapat mengatur jumlah simbol yang ada dalam tabel tersebut. Akan lebih baik jika jumlah karakter dalam tabel tersebut adalah bilangan prima misalnya 29, 31, 37, 41, atau lainnya. Hal ini dapat dilakukan dengan menambahkan simbol angka, tanda baca, atau spasi dalam tabel simbol. Tujuan dari jumlah simbol adalah bilangan prima, adalah untuk mengurangi faktor prima dari jumlah simbol dalam tabel tersebut. Sebagai contoh digunakan jumlah simbol dalam tabel adalah 41. Faktor prima dari 41 hanya bilangan 41, maka syarat yang harus dipenuhi matriks kunci, hanya determinan dari matriks kunci tidak boleh habis dibagi dengan 41. Dengan semakin sedikitnya faktor prima dan bilangan yang semakin besar, maka penentuan matriks kunci akan lebih dipermudah. Untuk mempersulit peretasan cipher Hill dapat dilakukan dengan penggunaan tabel di luar tabel konversi simbol-angka yang biasanya dilakukan. Misalnya dengan melakukan pemberian angka yang tidak berurut untuk abjad yang berurut. Pemberian angka yang berbeda dari biasanya untuk masing-masing simbol turut mempersulit proses peretasan cipher ini. Hal ini disebabkan, konversi angka yang salah menyebabkan hasil dekripsi yang salah juga. Selain itu, pemilihan kunci yang berukuran besar juga turut mempersulit peretasan. Hal ini disebabkan penghitungan pada setiap blok akan saling bergantung satu sama lainnya. Penggunaan blok yang semakin besar
juga memperkecil kemungkinan adanya kelompok simbol yang berurutan muncul beberapa kali. Misalnya, pada plaintext SAYASAYANGSASA jika dikelompokkan per 2 simbol, maka akan muncul banyak kelompok kata yang sama, yaitu SA dan YA. Dengan begini akan muncul sebuah pola tertentu pada hasil yang mempermudah penebakan jumlah kunci.
V. KESIMPULAN Berdasarkan pembahasan yang telah dilakukan di atas, dapat diambil kesimpulan sebagai berikut 1. Cipher Hill menggunakan pengelompokan karakterkarakter dalam teks yang kemudian diproses dalam kelompok tersebut (polygrahic substitution cipher) 2. Cipher Hill adalah salah satu jenis cipher yang memanfaatkan aritmatika modulo dan matriks dalam proses enkripsi dan dekripsinya. 3. Matriks kunci cipher Hill harus bersifat invertible terhadap modulo jumlah simbol dalam tabel. 4. Jumlah simbol dalam tabel yang merupakan bilangan prima akan menambah kemungkinan matriks kunci yang dipakai. 5. Untuk memperkuat cipher Hill dapat menyusun tabel konversi simbol ke angka di luar dari tabel standar dan juga dapat menggunakan ukuran kunci yang lebih besar.
DAFTAR REFERENSI [1]
[2] [3] [4] [5] [6] [7]
Howard Anton dan Chris Rorres, Elementary Linear Algebra with Supplemental Applications Internationan Student Version, 10th ed., New York: John Wiley & Sons, 2011. Rinaldi Munir, Diktat Kuliah IF2091 Struktur Diskrit, Bandung: Program Studi Teknik Informatika ITB, 2003. http://en.wikipedia.org/wiki/Cryptography, diakses pada 10 Desember 2011 pukul 13.49 http://en.wikipedia.org/wiki/Hill_cipher, diakses pada 10 Desember 2011 pukul 12.16 http://en.wikipedia.org/wiki/Substitution_cipher, diakses pada 10 Desember 2011 pukul 14.11 http://massey.limfinity.com/207/hillcipher.pdf, diakses pada 10 Desember 2011 pukul 15.38 http://www.apprendre-en-ligne.net/crypto/hill/Hillciph.pdf, diakses pada 10 Desember 2011 pukul 15.42
PERNYATAAN Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 11 Desember 2011
Edward Samuel Pasaribu 13510065
Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012
