BAB II
LANDASAN TEORI
2.1 Kriptografi
2.1.1 Definisi Kriptografi
Ditinjau dari terminologinya, kata kriptografi berasal dari bahasa Yunani yaitu ‘cryptos’ yang berarti ‘menyembunyikan’, dan ‘graphein’ yang artinya ‘menulis’. Menurut Schneier kriptografi adalah ilmu dan seni dalam menjaga keamanan pesan. A.Menezes mendefinisikan kriptografi sebagai ilmu yang mempelajari teknik-teknik matematika yang berhubungan dengan aspek keamanan informasi seperti kerahasiaan, integritas data serta otentifikasi [4]. Sedangkan ilmu dan seni memecahkan cipherteks disebut kriptanalisis. Pelakunya disebut kriptanalis. Cabang ilmu yang mempelajari keduanya, yaitu kriptografi dan kriptanalisis disebut kriptologi. Pelakunya disebut kriptologis [10]. Dari pengertian diatas dapat didefinisikan bahwa kriptografi adalah cabang ilmu yang mempelajari cara mengubah informasi dari keadaan/bentuk normal (dapat dipahami) menjadi bentuk yang tidak dapat dipahami [13]. Pesan asli disebut sebagai plainteks dan pesan yang telah disandikan disebut cipherteks. Pesan terakhir yang telah disandikan dan kemudian dikirim disebut kriptogram. Proses mengubah plainteks menjadi cipherteks disebut enkripsi atau enciphering. Kebalikan dari proses tersebut, yaitu mengubah cipherteks menjadi plainteks disebut dekripsi atau deciphering.
Konsep matematika yang mendasari algoritma kriptografi adalah relasi antar dua
buah himpunan yaitu himpunan yang berisi elemen-elemen plainteks dan
himpunan yang berisikan cipherteks. Enkripsi dan dekripsi merupakan fungsi yang memetakan elemen-elemen antara dua himpunan tersebut. Misalnya P mewakili plainteks dan C menyatakan cipherteks maka fungsi enkripsi E memetakan P ke C.
E(P) = C
Dan fungsi dekripsi D memetakan C ke P,
D(C) = P
Karena proses enkripsi kemudian dekripsi mengembalikan pesan ke pesan awal, maka persamaan berikut harus benar,
D(E(P)) = P
Jika keamanan kriptografi ditentukan dengan menjaga kerahasiaan algoritmanya, maka algoritma kriptografinya dinamakan algoritma restricted [10], dimana algoritma restricted ini mempunyai sejarah tersendiri di dalam kriptografi. Hal ini tidak sesuai dengan prinsip Kerckhoffs bahwa bahwa dalam menilai keamanan suatu kriptosistem, kita harus selalu berasumsi bahwa musuh mengetahui metode yang kita gunakan [7]. Yang berarti algoritma yang digunakan haruslah bersifat publik dan hanya kunci yang privat. Algoritma
restricted biasanya digunakan oleh sekelompok orang untuk
bertukar pesan satu sama yang lain.Tetapi algoritma restricted tidak cocok lagi saat ini, sebab setiap kali ada anggota kelompok keluar, maka algoritma kriptografi harus diganti lagi [10]. Auguste
Kerckhoffs
didalam
bukunya
“La
Cryptographie
militare”
memformulasikan enam atribut yang harus dimiliki oleh sebuah sistem kriptografi [6] : 1. Sistem seharusnya, jika tidak unbreakable secara teoritis, haruslah unbreakable secara praktek.
2. Keamanan sistem tidak boleh mengganggu kenyamanan dalam berkomunikasi.
3. Metode yang digunakan sistem dalam memilih kunci harus mudah untuk di ingat dan di ubah.
4. Cipherteks haruslah dikirim melalui telegram
Telegram adalah teknologi komunikasi yang yang dominan pada abad kesembilan belas. Pada zaman sekarang persyaratan ini di artikan bahwa teks tersebut dapat dikodekan dan dikirim dalam bentuk digital sehingga memudahkan dalam pengiriman dan penyimpanan.
5. Peralatan yang digunakan haruslah mudah untuk dibawa. Peralatan yang relatif besar seperti yang digunakan pada perang dunia II telah digantikan oleh mikoprosesor yang memenuhi persyaratan Kerckhoffs.
6. Penggunaan sistem seharusnya tidak membutuhkan peraturan yang panjang atau regangan mental. Kemudahan dalam pemakaian, biaya, dan dampak kecepatan dalam penyandian menjadi isu yang dominan saat ini.
2.1.2 Komponen Kriptografi
Dalam kriptografi terdapat beberapa istilah penting antara lain : 1) Pesan, Plainteks, dan Cipherteks Pesan merupakan data atau informasi yang dapat dibaca dan dimengerti maknanya. Nama lain untuk pesan adalah plainteks (plaintext). Pesan dapat berupa data atau informasi yang dikirim atau yang disimpan dalam media penyimpanan. Pesan yang tersimpan bisa berbentuk teks, citra (image), suara/bunyi (audio) dan video. Agar pesan tidak dapat dimengerti maknanya oleh pihak lain maka, pesan dapat disandikan ke bentuk lain yang tidak dapat dipahami. Bentuk pesan yang tersandi disebut cipherteks (ciphertext). 2) Pengirim dan Penerima Komunikasi data melibatkan pertukaran pesan antara dua entitas. Pengirim (sender) adalah entitas yang mengirim pesan kepada entitasnya yang lain. Penerima (receiver) adalah entitas yang menerima pesan. Entitas di sini dapat berupa orang, mesin (komputer), kartu kredit, dan sebagainya. 3) Enkripsi dan Dekripsi
Proses menyandikan pesan asli (plainteks) menjadi pesan tersandi (cipherteks) disebut enkripsi (encryption) sedangkan proses untuk mengembalikan pesan tersandi (cipherteks) menjadi plainteks semula dinamakan dekripsi (decryption). 4) Cipher dan Kunci Algoritma kriptografi disebut juga cipher yaitu aturan untuk enchipering dan dechipering, atau fungsi matematika yang digunakan untuk enkripsi dan dekripsi. Keamanan algoritma kriptografi sering diukur dari banyaknya kerja (work) yang dibutuhkan untuk memecahkan cipherteks menjadi plainteks tanpa mengetahui kunci yang digunakan. Kunci (key) merupakan parameter yang digunakan untuk transformasi enciphering dan deciphering. Kunci biasanya berupa string atau deretan bilangan. 5) Sistem kriptografi Kriptografi membentuk sebuah sistem yang dinamakan sistem kriptografi. Sistem kriptografi (cryptosystem) terdiri dari algoritma kriptografi, semua plainteks dan cipherteks yang mungkin dan kunci. 6) Penyadap (eavesdropper) Penyadap
merupakan
orang
yang
mencoba
menangkap
pesan
selama
ditransmisikan. Tujuan penyadap adalah untuk mendapatkan informasi sebanyakbanyaknya mengenai sistem kriptogafi yang digunakan untuk berkomunikasi dengan maksud untuk memecahkan cipherteks. Nama lain penyadap : enemy, adversary, intruder, interceptor, bad guy. 7) Kriptanalisis Kriptografi berkembang sedemikian rupa sehingga melahirkan bidang yang berlawanan yaitu kriptanalisis. Kriptanalisis (crytanalysis) adalah ilmu dan seni untuk memecahkan cipherteks menjadi plainteks tanpa mengetahui kunci yang digunakan. Pelakunya disebut kriptanalis.
2.1.3 Tujuan Kriptografi
Kriptografi bertujuan untuk memberikan layanan keamanan (yang juga dinamakan aspek-aspek keamanan) sebagai berikut : 1) Kerahasiaan (confidentiality)
Adalah layanan yang ditujukan untuk menjaga agar pesan tidak dapat dibaca oleh pihak-pihak yang tidak berhak [9]. 2) Integritas data (data integrity) Merupakan kemampuan penerima pesan untuk memverifikasi pesan, memastikan bahwa pesan belum dimodifikasi dalam perjalanan, seorang penyusup seharusnya tidak mampu mengganti pesan asli dengan yang palsu. 3) Otentikasi (authentication) Otentifikasi adalah kemampuan penerima pesan untuk memastikan pesan tersebut asli. Seorang penyusup seharusnya tidak bisa menyamar sebagai orang lain. 4) Nirpenyangkalan (non-repudiation) Adalah dimana pengirim pesan tidak bisa menyangkal bahwa dia telah mengirim pesan [10].
2.1.4 Jenis Kriptografi
1. Algoritma Simetris
Adalah algoritma dimana kunci untuk enkripsi bisa dihitung dari kunci dekripsi, dan sebaliknya. Algoritma simetris kadang disebut juga algoritma konvensional. Sebagian besar algoritma simetris menggunakan kunci enkripsi dan kunci dekripsi yang sama. Algoritma simetris sering juga disebut sebagai algoritma kunci rahasia, algoritma kunci tunggal atau algoritma satu kunci [3]. Pengirim dan penerima harus menyetujui suatu kunci tertentu sebelum mereka dapat berkomunikasi dengan aman. Keamanan algoritma simetris tergantung pada kunci, membocorkan kunci berarti bahwa orang lain dapat mengenkripsi dan mendekripsi pesan. Agar komunikasi tetap aman, kunci harus tetap dirahasiakan [10]. Yang termasuk algoritma kunci simetris adalah OTP, DES, RC2, RC4, RC5, IDEA, Twofish, Magenta, FEAL, SAFER, LOKI, CAST, Rijndael (AES), Blowfish, GOST, A5, Kasumi dan lain-lainnya.
plainteks (P)
Enkripsi
Dekripsi
Ek(P) = C
Dk(C) = P
cipherteks (C) Gambar 2.1 Kriptografi Simetris
plainteks (P)
Keterangan : E
: fungsi enkripsi
k
: kunci (key)
P
: plainteks
C
: cipherteks
D
: fungsi dekripsi
2. Algoritma Kunci Publik
Sering juga disebut sebagai algoritma asimetris. Merupakan algoritma dimana kunci untuk mengenkripsi pesan berbeda dengan kunci yang digunakan untuk mendekripsi. Bahkan kunci untuk mendekripsi tidak bisa dihitung dari kunci untuk mengekripsi. Dinamakan kunci publik, sebab kunci untuk enkripsi tidak rahasia dan dapat diketahui oleh siapapun (diumumkan ke publik), sementara kunci untuk dekripsi hanya diketahui oleh penerima pesan. Pada kriptografi jenis ini, setiap orang yang berkomunikasi mempunyai sepasang kunci, yaitu kunci privat dan kunci publik. Pengirim mengenkripsi pesan dengan menggunakan kunci publik si penerima pesan. Hanya penerima pesan yang dapat mendekripsikan pesan karena hanya dia yang mengetahui kunci privatnya sendiri.
plainteks (P)
Enkripsi
Dekripsi
Ee(P) = C
Dd(c) = P
cipherteks (C) Gambar 2.2 Kriptografi Kunci Publik
Keterangan
: E
: Fungsi enkripsi
e
: kunci publik/ public key
P
: Plain teks
C
: Cipher teks
D
: Fungsi dekripsi
plainteks (P)
d
: kunci privat/private key
2.2 Algoritma One Time Pad
Algoritma ini ditemukan pada tahun 1917 oleh Mayor Joseph Mauborgne dan Gilbert Vernam. Cipher ini termasuk ke dalam kelompok algoritma kriptografi simetri. Cipher ini diimplementasikan melalui sebuah kunci yang terdiri dari sekumpulan random karakter-karakter yang tidak berulang. Setiap huruf kunci dijumlahkan modulo 26 dengan huruf pada plaintext. Pada One Time Pad, tiap huruf kunci digunakan satu kali untuk satu pesan dan tidak digunakan kembali.Panjang stream karakter kunci sama dengan panjang pesan. One time pad (pad = kertas bloknot) berisi barisan karakterkarakter kunci yang dibangkitkan secara acak. Satu pad hanya digunakan sekali (one time) saja untuk mengenkripsi pesan, setelah itu pad yang telah digunakan dihancurkan.
Misalkan, kita akan mengenkripsi kata ‘O N E’ menggunakan algoritma one time pad. Yaitu : (P + K) mod 26 = C
Dimana P adalah plain teks, K adalah kunci, dan C adalah cipher teks. Misalkan A = 0, B = 1, …, Z = 25. Sehingga : Plainteks
:ONE
Kunci
:GNR
Cipherteks
:UAV
Yang didapat dari : (O + G) mod 26 = U, yaitu (14 + 6) mod 26 = 20 (N + N) mod 26 = O, yaitu (13 + 13) mod 26 = 0 (E + R) mod 26 = V, yaitu (4 + 17) mod 26 = 21
Proses dekripsinya dilakukan dengan menggunakan kunci yang sama dengan yang dipakai untuk enkripsi, dengan langkah sebagai berikut :
(U - G) mod 26 = O, yaitu (20 - 6) mod 26 = 14 (A - N) mod 26 = N, yaitu (0 - 13) mod 26 = 13 (V - R) mod 26 = E, yaitu (21 - 17) mod 26 = 4
Algoritma ini memiliki beberapa kelemahan. Yaitu kunci yang dipakai haruslah benar-benar acak. Menggunakan pseudorandom generator tidak dihitung, karena algoritma ini memiliki bagian yang tidak acak [10]. Panjang kunci juga harus sama dengan panjang pesan, sehingga hanya cocok untuk pesan berukuran kecil. Selain itu, karena kunci dibangkitkan secara acak, maka ‘tidak mungkin’ pengirim dan penerima membangkitkan kunci yang sama secara simultan. Dan karena kerahasiaan kunci harus dijamin, maka perlu ada perlindungan selama pengiriman kunci. Oleh karena itu, algoritma ini hanya dapat digunakan jika tersedia saluran komunikasi kedua yang cukup aman untuk mengirim kunci.
2.3 Algoritma Knapsack
Algoritma Knapsack adalah algoritma kriptografi kunci publik yang keamanannya terletak pada sulitnya memecahkan persoalan knapsack (knapsack problem) [9]. Algoritma enkripsi kunci publik pertama yang digunakan untuk umum adalah knapsack. Algoritma ini dikembangkan oleh Ralph Merkle dan Martin Hellman yang hanya bisa digunakan untuk enkripsi, meskipun kemudian Adi Shamir mengadaptasi sistem ini untuk tanda tangan digital[10]. Walaupun kriptosistem ini dan beberapa variannya telah dipecahkan pada awal tahun 1980, namun tetap masih dipelajari karena konsepnya yang anggun serta desain teknik yang mendasarinya[12].
Knapsack problem merupakan masalah di mana orang dihadapkan pada persoalan optimasi pada pemilihan benda yang dapat dimasukkan ke dalam sebuah wadah yang memiliki keterbatasan
ruang atau daya tampung. Dengan
adanya
optimasi dalam pemilihan benda yang akan dimasukkan ke dalam wadah tersebut diharapkan dapat menghasilkan keuntungan yang maksimum. Benda-benda yang akan dimasukkan ini masing-masing memiliki berat dan sebuah nilai yang digunakan untuk menentukan prioritasnya dalam pemilihan tersebut. Nilainya dapat berupa tingkat kepentingan, harga barang, nilai sejarah, atau yang lainnya.
Wadah yang dimaksud di sini juga memiliki nilai konstanta yang merupakan nilai pembatas untuk benda-benda
yang akan dimasukkan ke dalam
wadah tersebut sehingga harus diambil sebuah cara memasukkan benda-benda tersebut ke dalam wadah sehingga menghasilkan hasil optimum tetapi tidak melebihi kemampuan wadah untuk menampungnya.
Permasalahan Knapsack adalah permasalahan optimisasi kombinatorial [2]. Diberikan kumpulan benda, masing-masing memiliki berat dan nilai, tentukan benda mana saja yang akan diambil sehingga total beratnya <= suatu batas nilai (biasanya kapasitas tas) dan nilai yang sebesar-besarnya. Nama dari problem ini diperoleh dari masalah yang dihadapi seseorang saat berhadapan dengan tas yang ukurannya terbatas namun harus diisi dengan benda yang paling berharga atau berguna [5].
Ide algoritma ini berasal dari persoalan Knapsack. Diketahui himpunan angka A dan sebuah bilangan b, dimana hasil penjumlahan dari himpunan bagian A = b. Knapsack
problem
atau
rucksack
problem
adalah masalah
optimasi
kombinatorial. Namanya berasal dari masalah maksimasi untuk pilihan paling tepat dari barang-barang yang akan dibawa dalam sebuah tas pada sebuah perjalanan. Sejumlah barang yang tersedia ini, masing-masing memiliki berat dan nilai, yang menentukan jumlah barang yang dapat dibawa sehingga total berat tidak melebihi kapasitas tas dan dengan total nilai yang sebesar mungkin.
Terdapat beberapa variasi knapsack problem, yaitu [2]: •
0/1 Knapsack Problem Setiap barang hanya tersedia 1 unit, take it or leave it. Misalnya kotak sepatu yang akan dimasukkan dalam tas. Yang apabila kotak ini dimasukkan, maka tas akan penuh dan tidak bisa dipakai untuk memasukkan barang lainnya.
•
Fractional Knapsack Problem Barang boleh dibawa sebagian saja(unit dalam pecahan). Versi problem ini menjadi masuk akal apabila barang yang tersedia dapat dibagi-bagi. Misalnya tepung terigu yang bisa kita masukkan 1.3 kg, 1.5 kg atau 1 kg.
•
Bounded Knapsack Problem
Setiap barang hanya tersedia N unit (jumlahnya terbatas). Misalnya buku yang akan dimasukkan kedalam tas, dimana ada 2 buku tulis, 1 buku gambar, dan 3 batang pensil. •
Unbounded Knapsack Problem Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas. Contohnya berupa air laut atau pasir yang jumlahnya banyak dan tidak terbatas.
Ada dua macam bentuk atau tipe knapsack yaitu : •
General knapsack Dimana m, n Є N dan a adalah set S = {b j : b j Є N, untuk j = 1, 2, ..., n}, yang biasa disebut set knapsack.
•
Superincreasing knapsack Superincreasing knapsack adalah persoalan knapsack yang dapat dipecahkan dalam orde O(n) (jadi, polinomial)[9]. Superincreasing knapsack adalah sebuah urutan (b 1 , b 2 , . . . , b n ) dengan b j є N untuk j = 1, 2, . . . , n [8]. Superincreasing knapsack dapat dibentuk dari barisan superincreasing. Yaitu suatu barisan dimana setiap nilai didalam barisan lebih besar dari jumlah semua nilai sebelumnya. Misalnya {1, 3, 6, 13, 27, 52} adalah barisan superincreasing, tetapi {1, 3, 4, 9, 15, 25} bukan. dapat dinyatakan sebagai berikut :
Untuk setiap i = {2, 3, . . ., n}. Untuk menyelesaikan superincreasing knapsack adalah dengan menemukan S = {b 1 , b 2 , . . . , b n } dengan cara sebagai berikut : 1. Jumlahkan semua bobot didalam barisan
2. Bandingkan bobot total dengan bobot terbesar didalam barisan. Jika bobot terbesar lebih kecil atau sama dengan bobot total, maka ia dimasukkan kedalam knapsack, jika tidak, maka ia tidak dimasukkan. 3. Kurangi bobot total dengan bobot yang telah dimasukkan, kemudian bandingkan bobot total sekarang dengan bobot terbesar selanjutnya. Demikian seterusnya sampai seluruh bobot didalam barisan selesai dibandingkan. 4. Jika bobot total menjadi nol, maka terdapat solusi persoalan superincreasing knapsack, tetapi jika tidak nol, maka tidak ada solusinya.
Sebagai contoh, kita akan mengenkripsi kunci yang dipergunakan dalam algoritma One Time Pad di atas. Yaitu teks ’G N R’. Misalkan A = 0, B = 1, …, Z = 25, maka : G = 6, nilai binernya adalah 000110 N = 13, nilai binernya adalah 001101 R = 17, nilai binernya adalah 010001 Sehingga didapatlah plainteks : 000110 001101 010001 yang akan dienkripsi menggunakan private key sebagai berikut [11]: •
Super Increasing Knapsack {2, 3, 6, 13, 27, 52}
•
n = 31 dan m = 105
Maka Public key didapatkan dengan : (w . n) mod m Dimana w adalah barisan super increasing knapsack, yaitu {2, 3, 6, 13, 27, 52}.
Sehingga : ( 2 x 31) mod 105 = 62 ( 3 x 31) mod 105 = 93 ( 6 x 31) mod 105 = 81 (13 x 31) mod 105 = 88 (27 x 31) mod 105 = 102 (52 x 31) mod 105 = 37
Maka didapatkanlah publik key, yaitu {62, 93, 81, 88, 102, 37}
Plainteks dibagi menjadi blok yang panjangnya n, kemudian setiap bit di dalam blok dikalikan dengan w i yang berkoresponden sesuai dengan persamaan, sbb : Blok plainteks ke-1
: 000110
Kriptogram
: (1 x 88) + (1 x 102) = 190
Blok plainteks ke-2
: 001101
Kriptogram
: (1 x 81) + (1 x 88) + (1 x 37) = 206
Blok plainteks ke-3
: 010001
Kriptogram
: (1 x 93) + (1 x 37) = 130
Jadi cipherteks yang dihasilkan : 190, 206, 130
Untuk mendekripsikan cipherteks menjadi plainteks, maka digunakanlah kunci privat, yaitu barisan super increasing knapsack. Mula-mula penerima pesan menghitung nilai n-1 , yaitu inversi n modulo m, sedemikian sehingga n . n-1 ≡ 1 (mod m) [9]. Kekongruenan ini dapat dihitung dengan cara sederhana sebagai berikut : n. n-1 ≡ 1 ( mod m) Sehingga untuk mendekripsikan cipherteks tersebut menggunakan kunci privat {2, 3, 6, 13, 27, 52}, maka :
Tabel 2.1 n invers -1
n
n . n-1 mod m
1
31 x 1 mod 105 = 31
2
31 x 2 mod 105 = 62
3
31 x 3 mod 105 = 93
...
...
61
31 x 61 mod 105 = 1
Sehingga didapatlah n-1 yaitu 61. Maka plainteksnya yang berkoresponden dengan {2, 3, 6, 13, 27, 52} diperoleh kembali dengan cara sebagai berikut :
(190 x 61) mod 105 = 40 = 13 + 27, yang berkoresponden dengan 000110 (206 x 61) mod 105 = 71 = 6 + 13 + 52, yang berkoresponden dengan 001101 (130 x 61) mod 105 = 55 = 3 + 52, yang berkoresponden dengan 010001
Sehingga plainteks yang dihasilkan adalah : 000110 001101 010001, dimana : 000110
= 6, berkoresponden dengan karakter ’G’
001101
= 13, berkoresponden dengan karakter ’N’
010001
= 17, berkoresponden dengan karakter ’R’
