A. Pengertian Kriptografi
Kriptografi berasal dari bahasa yunani yang terdiri dari kata kryptos yang berarti tersembunyi dan grafo yang berarti tulis. Kriptografi secara umum adalah ilmu dan seni untuk menjaga kerahasiaan berita. Selain pengertian tersebut kriptografi juga merupakan ilmu yang mempelajari teknik-teknik matematika yang berhubungan dengan aspek keamanan informasi seperti kerahasiaan data, keabsahan data, integri tas data, serta autentikasi data.
Kriptografi memungkinkan beberapa operasi atau proses terhadap data. Dua buah operasi dasar adalah enkripsi (dengan dekripsi sebagai proses balikannya) dan signing (dengan verifikasi dari signature sebagai proses balikannya). Enkripsi analog dengan memasukkan surat kedalam sebuah amplop sedangkan dekripsi analog dengan membuang amplop dan mengambil data. Signature analog dengan pemberian tanda-tangan terhadap sebuah dokumen dan penanda bahwa dokumen tersebut tidak berubah dari aslinya.
B. Konsep Penggunaan Kriptografi
Konsep penggunaan kriptografi antara lain:
1. Kerahasiaan (Confidentiality).
Sederhananya, kerahasiaan adalah proses penyembunyian data dari orang-orang yang tidak punya otoritas.
2. Integritas (Integrity)
Proses untuk menjaga agar sebuah data tidak dirubah-rubah sewaktu ditransfer atau disimpan.
3. Penghindaran Penolakan (Non-repuditation)
Proses untuk menjaga bukti-bukti bahwa suatu data berasal dari seseorang. Seseorang yang ingin menyangkal bahwa data tersebut bukan berasal darinya, dapat saja melenyapkan bukti-bukti yang ada. Karenanya diperlukan teknik untuk melindungi data-data tersebut.
4. Autentikasi (Authentication)
Proses untuk menjamin keaslian suatu data.
5. Tanda Tangan Data (Data Signature)
Dapat disebut juga sebagai tanda tangan digital. Berguna untuk menandatangi data digital. Contohnya adalah Digital Signature Algorithm (DSA)
6. Kontrol Akses (Access Control)
Untuk mengontrol akses terhadap suatu entity.
Contoh penggunaan kriptografi di dunia internet antara lain: Secure Shell (SSH), SSL (Secure Socket Layer), Secure Hypertext Transfer Protocol (HTTP), dan lain lain.
C. Pengertian Fungsi Hash
Hash function atau fungsi hash adalah suatu cara menciptakan “fingerprint” dari berbagai data masukan. Hash function akan mengganti atau mentranspose-kan data tersebut untuk menciptakan fingerprint, yang biasa disebut hash value. Hash value biasanya digambarkan sebagai suatu string pendek yang terdiri atas huruf dan angka yang terlihat random (data biner yang ditulis dalam notasi heksadesimal). Suatu hash function adalah sebuah fungsi matematika, yang mengambil sebuah panjang variabel string input, yang disebut pre-image dan mengkonversikannya ke sebuah string output dengan panjang yang tetap dan biasanya lebih kecil, yang disebut message digest5. Hash function digunakan untuk melakukan fingerprint pada pre-image, yaitu menghasilkan sebuah nilai yang dapat menandai (mewakili) pre-image sesungguhnya. Fungsi hash satu arah (one-way hash function) adalah hash function yang bekerja satu arah, yaitu suatu hash function yang dengan mudah dapat menghitung hash value dari pre-image, tetapi sangat sukar untuk menghitung pre-image dari hash value. Sebuah fungsi hash satu arah, H(M), beroperasi pada suatu pre-image pesan M dengan panjang sembarang, dan mengembalikan nilai hash h yang memiliki panjang tetap. Dalam notasi matematika fungsi hash satu arah dapat ditulis sebagai:
h = H(M), dengan h memiliki panjang b
Ada banyak fungsi yang mampu menerima input dengan panjang sembarang dan menghasilkan output dengan panjang tetap, tetapi fungsi hash satu arah memiliki karakteristik tambahan yang membuatnya satu arah :
Diberikan M, mudah menghitung h.
Diberikan h, sulit menghitung M agar H(M) = h.
Diberikan M, sulit menemukan pesan lain, M', agar H(M) = H(M').
Dalam dunia nyata, fungsi hash satu arah dikembangkan berdasarkan ide sebuah fungsi kompresi. Fungsi satu arah ini menghasilkan nilai hash berukuran n bila diberikan input berukuran b. Input untuk fungsi kompresi adalah suatu blok pesan dan hasil blok teks sebelumnya. Sehingga hash suatu blok M, adalah
hi = f(Mi,hi-1)
dengan
hi = hash value saat ini.
Mi = blok pesan saat ini.
hi-1 = hash value blok teks sebelumnya.
Fungsi hash sangat berguna untuk menjaga integritas sebuah data. Sudah banyak algoritma hash function yang diciptakan, namun hash function yang umum digunakan saat ini adalah MD5 dan SHA (Secure Hash Algorithm). Algoritma hash function yang baik adalah yang menghasilkan sedikit hash collision.
D. Metode yang Digunakan Dalam Fungsi Hash
1. Metode Pembagian
Pada metode pembagian ini, kita memetakan suatu kunci k ke dalam salah satu slot dari m buah slot dengan mengambil sisa dari k dibagi oleh m. Maka, fungsi Hash ini adalah:
h(k) = k mod m
dimana : h(k) = fungsi Hash
k = kunci yang akan dihitung/di-hash,
m = jumlah keseluruhan slot.
2. Metode Perkalian
Metoda perkalian untuk memperoleh fungsi Hash dilakukan melalui dua langkah. Langkah pertama, kita mengalikan kunci dengan suatu konstanta didalam range 0 < A < 1 dan mengambil nilai fraksional dari kA. Kemudian, kita mengalikan nilai ini dengan m dan dapat diperoleh hasilnya. Singkatnya, fungsi Hash ini adalah
h(k) = └m (k A mod 1) ┘,
dimana: A » (Ö5 - 1)/2 = 0,6180339887... (Golden Number),
“k A mod 1” artinya adalah nilai fraksional dari kA, atau kA – └kA┘.
E. Macam-Macam Fungsi Hash
Fungsi Hash (dilambangkan dengan h(k)) bertugas untuk mengubah k (key) menjadi suatu nilai dalam interval [0....X], dimana "X" adalah jumlah maksimum dari record-record yang dapat ditampung dalam tabel. Jumlah maksimum ini bergantung pada ruang memori yang tersedia. Fungsi Hash yang ideal adalah mudah dihitung dan bersifat random, agar dapat menyebarkan semua key. Dengan key yang tersebar, berarti data dapat terdistribusi secara seragam bentrokan dapat dicegah. Sehingga kompleksitas waktu model Hash dapat mencapai O(1), di mana kompleksitas tersebut tidak ditemukan pada struktur model lain.
Ada beberapa macam fungsi hash yang relative sederhana yang dapat digunakan dalam penyimpanan database:
- Metode Pembagian Bersisa (Division-Remainder Method)
Jumlah lokasi memori yang tersedi dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci k pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.
2. Melipat (Folding)
Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya.
3. Transformasi Radiks (Radix Transformation)
Karena nilai dalam bentuk digital, basis angka atau radiks dapat diganti sehingga menghasilkan urutan angka-angka yang berbeda. Contohnya nilai desimal (basis 10) bisa ditransformasikan kedalam heksadesimal (basis 16). Digit atas hasilnya bisa dibuang agar panjang nilai hash dapat seragam.
4. Pengaturan Ulang Digit Radiks (Radix Transformation)
Metode ini mengubah urutan digit dengan pola tertentu. Contohnya mengambil digit ke tiga sampai ke enam dari nilai aslinya, kemudian membalikan urutannya dan menggunakan digit yang terurut terbalik itu sebagai nilai hash.
Fungsi hash yang bekerja dengan baik untuk penyimpanan pada database belum tentu bekerja dengan baik untuk keperluan kriptografi atau pengecekan kesalahan. Ada beberapa fungsi hash terkenal yang digunakan untuk keperluan kriptografi. Diantaranya adalah fungsi hash message-diggest, contohnya MD2, MD4, dan MD5, digunakan untuk menghasilkan nilai hash dari tanda tangan digital yang disebut message-diggest. Ada pula Secure Hash Algorithm (SHA), sebuah algoritma standar yang menghasilkan message-diggest yang lebih besar (60- bit) dan serupa dengan MD4.
F. Bentrokan Pada Fungsi Hash
Fungsi hash bukan merupakan fungsi satu-ke-satu, artinya beberapa record yang berbeda dapat menghasilkan nilai hash yang sama / terjadi bentrokan. Dengan fungsi hash yang baik, hal seperti ini akan sangat jarang terjadi, tapi pasti akan terjadi. Jika hal seperti ini terjadi, record-record tersebut tidak bisa menempati lokasi yang sama. Ada dua macam kebijakan resolusi bentrokan pada tabel hash, yaitu kebijakan resolusi bentrokan di luar tabel dan kebijakan resolusi bentrokan di dalam tabel. Harus diperhatikan juga teknik-teknik penempatan record agar mudah dicari jika dibutuhkan.
- Kebijakan Resolusi Bentrokan di Luar Table
Artinya tabel hash bukan lagi menjadi array of records, tetapi menjadi array of pointers. Setiap pointer menunjuk ke senarai berkait yang berisi record tersebut. Metode seperti ini dinamakan chaining. Dalam bentuk sederhananya berupa senarai berkait dari recordrecord yang menghasilkan nilai hash yang sama. Penambahan record dapat dilakukan dengan menambah senarai berisi record tersebut. Untuk pencarian pada tabel, pertama-tama dicari nilai hash terlebih dahulu, kemudian dilakukan pencarian dalam senarai berkait yang bersangkutan. Untuk menghapus suatu record, hanya menghapus senarainya saja.
Resolusi bentrokan dengan Chaining
Kelebihan dari metode chaining ini chaining ini adalah proses penghapusan yang relarif mudah dan penambahan ukuran tabel hash bisa ditunda untuk waktu yang lebih lama karena penurunan kinerjanya berbanding lurus meskipun seluruh lokasi pada table sudah penuh. Bahkan, penambahan ukuran tabel bias saja tidak perlu dilakukan sama sekali karena penurunan kinerjanya yang linier. Misalnya, table yang berisi record sebanyak dua kali lipat kapasitas yang direkomendasikan hanya akan lebih lambat dua kali lipat dibanding yang berisi sebanyak kapasitas yang direkomendasikan.
Kekurangan dari metode chaining ini sama dengan kekurangan dari senarai berkait. Operasi traversal pada senarai berkait memiliki performa cache yang buruk.
Struktur data lain dapat digunakan sebagai pengganti senarai berkait. Misalnya dengan pohon seimbang, kompleksitas waktu terburuk bisa diturunkan menjadi O(log n) dari yang sebelumnya O(n). Namun demikian, karena setiap senarai diharapkan untuk tidak panjang, struktur data pohon ini kurang efisien kecuali tabel hash tersebut memang didesain untuk jumlah record yang banyak atau kemungkinan terjadi bentrokan sangat besar yang mungkin terjadi karena masukan memang disengaja agar terjadi bentrokan.
- Kebijakan Resolusi Bentrokan di Dalam Table
Berbeda dengan kebijakan resolusi bentrokan di luar tabel, pada kebijakan resolusi di dalam tabel data disimpan di dalam hash tabel tersebut, bukan dalam senarai berkait yang bisa bertambah terus menerus. Dengan demikian data yang disimpan tidak mungkin bisa lebih banyak daripada jumlah ruang pada table hash.
Jika suatu record akan dimasukkan ke dalam table hash pada lokasi sesuai nilai hash-nya dan ternyata lokasi tersebut sudah diisi dengan record lain maka harus dicari lokasi alternatif yang masih belum terisi dengan cara tertentu. Cara ini disebut Open Addressing.
Ada beberapa metode untuk menemukan lokasi baru yang masih kosong. Dalam proses menemukan lokasi baru ini harus menggunakan pola tertentu agar record yang disimpan tetap bisa dicari dengan mudah saat dibutuhkan kemudian. Metode-metode yang sering digunakan adalah:
a. Linear Probing
Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah 1.
Resolusi bentrokan dengan Linear Probing
b. Quadratic Probing / Squared Probing
Hampir sama dengan linear probing, hanya saja pada quadratic probing, hasil yang diperoleh dari fungsi hash ditambahkan dengan kuadrat dari interval yang digunakan.
c. Double Hashing
Pada metode double hashing, jika lokasi yang diperoleh dengan fungsi hash sudah terisi, maka dilakukan proses hash lagi sampai ditemukan lokasi yang belum terisi.
- Perbandingan Antara Metode Chaining dan Open Addressing
Keunggulan metode chaining dibanding open addressing:
a. Lebih mudah diimplementasikan dengan efektif dan hanya membutuhkan struktur data dasar.
b. Metode chaining tidak rawan terhadap data-data yang berkumpul di daerah tertentu. Metode open addressing membutuhkan algoritma hash yang lebih baik untuk menghindari pengumpulan data di sekitar lokasi tertentu.
c. Performa menurun secara linier. Meskipun semakin banyak record yang dimasukkan maka semakin panjang senarai berantai, tabel hash tidak akan penuh dan tidak akan menimbulkan peningkatan waktu pencarian record yang tibatiba meningkat yang terjadi bila menggunakan metode open addressing.
d. Jika record yang dimasukkan panjang, memori yang digunakan akan lebih sedikit dibandingkan dengan metode open addressing.
Perbandingan waktu yang diperlukan untuk melakukan pencarian. Saat tabel mencapai 80% terisi, kinerja pada linear probing(open addressing)menurun drastis.
Untuk ukuran record yang kecil, keunggulan metode open addressing dibandingkan dengan chaining diantaranya
a. Ruang yang digunakan lebih efisien karena tidak perlu menyimpan pointer atau mengalokasi tempat tambahan di luar tabel hash.
b. Tidak ada waktu tambahan untuk pengalokasian memori karena metode open addressing tidak memerlukan pengalokasian memori.
c. Tidak memerlukan pointer.
Sebenarnya, penggunaan algoritma apapun pada table hash biasanya cukup cepat, dan persentase kalkulasi yang dilakukan pada tabel hash rendah. Penggunaan memori juga jarang berlebihan. Oleh karena itu, pada kebanyakan kasus, perbedaan antar algoritma ini tidak signifikan.
- Metode-Metode Lain
Selain metode-metode yang sudah disebutkan di atas, ada juga beberapa metode lain.
a. Coalesced Hashing
Gabungan dari chaining dan openaddressing. Coalesced hashing menghubungkan ke tabel itu sendiri. Seperti open addressing, metode ini memiliki keunggulan pada penggunaan tempat dan cache dibanding metode chaining. Seperti chaining, metode ini menghasilkan lokasi penyimpanan yang lebih menyebar, tetapi pada metode ini record yang disimpan tidak mungkin lebih banyak daripada ruang yang disediakan tabel.
b. Perfect Hashing
Jika record yang akan digunakan sudah diketahui sebelumnya, dan jumlahnya tidak melebihi jumlah ruang pada tabel hash, perfect hashing bisa digunakan untuk membuat tabel hash yang sempurna, tanpa ada bentrokan.
c. Probabilistic Hashing
Kemungkinan solusi paling sederhana untuk mengatasi bentrokan adalah dengan engganti record yang sudah disimpan dengan record yang baru, atau membuang record yang baru akan dimasukkan. Hal ini bisa berdampak tidak ditemukannya record pada saat pencarian. Metode ini digunakan untuk keperluan tertentu saja.
d. Robin Hood Hashing
Salah satu variasi dari resolusi bentrokan double hashing. Ide dasarnya adalah sebuah record yang sudah dimasukkan bisa digantikan dengan record yang baru jika nilai pencariannya (probe count – bertambah setiap menemukan termpat yang sudah terisi) lebih besar daripada nilai pencarian dari record yang sudah dimasukkan. Efeknya adalah mengurangi kasus terburuk waktu yang diperlukan untuk pencarian.
G. Pengertian MD5
Dalam kriptografi, MD5 (Message-Digest algortihm 5) ialah fungsi hash kriptografik yang digunakan secara luas dengan hash value 128-bit. Pada standart Internet (RFC 1321), MD5 telah dimanfaatkan secara bermacam-macam pada aplikasi keamanan, dan MD5 juga umum digunkan untuk melakukan pengujian integritas sebuah file.
MD5 di desain oleh Ronald Rivest pada tahun 1991 untuk menggantikan hash function sebelumnya, MD4. Pada tahun 1996, sebuah kecacatan ditemukan dalam desainnya, walau bukan kelemahan fatal, pengguna kriptografi mulai menganjurkan menggunakan algoritma lain, seperti SHA-1 (klaim terbaru menyatakan bahwa SHA-1 juga cacat). Pada tahun 2004, kecacatan-kecacatan yang lebih serius ditemukan menyebabkan penggunaan algoritma tersebut dalam tujuan untuk keamanan jadi makin dipertanyakan.
H. Langkah-Langkah Pembuatan MD
1. Penambahan Bit-bit Pengganjal
a. Pesan ditambah dengan sejumlah bit pengganjal sedemikian sehingga panjang pesan (dalam satuan bit) kongruen dengan 448 modulo 512.
b. Jika panjang pesan 448 bit, maka pesan tersebut ditambah dengan 512 bit menjadi 960 bit. Jadi, panjang bit-bit pengganjal adalah antara 1 sampai 512.
c. Bit-bit pengganjal terdiri dari sebuah bit 1 diikuti dengan sisanya bit 0.
- Penambahan Nilai Panjang Pesan
a. Pesan yang telah diberi bit-bit pengganjal selanjutnya ditambah lagi dengan 64 bit yang menyatakan panjang pesan semula.
b. Jika panjang pesan > 264 maka yang diambil adalah panjangnya dalam modulo 264. Dengan kata lain, jika panjang pesan semula adalah K bit, maka 64 bit yang ditambahkan menyatakan K modulo 264.
c. Setelah ditambah dengan 64 bit, panjang pesan sekarang menjadi kelipatan 512 bit.
- Inisialisai Penyangga MD
a. MD5 membutuhkan 4 buah penyangga (buffer) yang masing-masing panjangnya 32 bit. Total panjang penyangga adalah 4 ´ 32 = 128 bit. Keempat penyangga ini menampung hasil antara dan hasil akhir.
b. Keempat penyangga ini diberi nama A, B, C, dan D. Setiap penyangga diinisialisasi dengan nilai-nilai (dalam notasi HEX) sebagai berikut:
A = 01234567
B = 89ABCDEF
C = FEDCBA98
D = 76543210
4. Pengolahan Pesan dalam Blok Berukuran 512 bit
a. Pesan dibagi menjadi L buah blok yang masing-masing panjangnya 512 bit (Y0 sampai YL – 1).
b. Setiap blok 512-bit diproses bersama dengan penyangga MD menjadi keluaran 128-bit, dan ini disebut proses HMD5. Gambaran proses HMD5 diperlihatkan pada Gambar 13.3.
c. Pada Gambar 13.3, Yq menyatakan blok 512-bit ke-q dari pesan yang telah ditambah bit-bit pengganjal dan tambahan 64 bit nilai panjang pesan semula.
d. MDq adalah nilai message digest 128-bit dari proses HMD5 ke-q. Pada awal proses, MDq berisi nilai inisialisasi penyangga MD.
e. Proses HMD5 terdiri dari 4 buah putaran, dan masing-masing putaran melakukan operasi dasar MD5 sebanyak 16 kali dan setiap operasi dasar memakai sebuah elemen T. Jadi setiap putaran memakai 16 elemen Tabel T.
f. Fungsi-fungsi fF, fG, fH, dan fI masing-masing berisi 16 kali operasi dasar terhadap masukan, setiap operasi dasar menggunakan elemen Tabel T.
g. Operasi dasar MD5 diperlihatkan pada Gambar 13.4.
h. Karena ada 16 kali operasi dasar, maka setiap kali selesai satu operasi dasar, penyangga-penyangga itu digeser ke kanan secara sirkuler dengan cara pertukaran sebagai berikut:
temp ¬ d
d ¬ c
c ¬ b
b ¬ a
a ¬ temp
I. Cara Kerja MD5
MD5 mengolah blok 512 bit, dibagi kedalam 16 subblok berukuran 32 bit. Keluaran algoritma diset menjadi 4 blok yang masing-masing berukuran 32 bit yang setelah digabungkan akan membentuk nilai hash 128 bit.
Algoritma MD5
Pesan diberi tambahan sedemikian sehingga panjang menjadi k-bit, dimana k = 512n – 64 bit. n merupakan blok masukan. Tambahan ini diperlukan hingga pesan menjadi k bit. Kemudian 64 bit yang masing kosong, dibagian akhir, diisi panjang pesan. Inisiasi 4 variabel dengan panjang 32 bit yaitu a,b,c,d. Variabel a,b,c,d dikopikan ke variabel a,b,c,d yang kemudian diolah melalui 4 tahapan yang sangat serupa. Setiap tahapan menggunakan 16 kali operasi berbeda, menjalankan fungsi nonlinear pada tiga variabel a,b,c, atau d. Hasilnya ditambahkan ke variabel keempat, subblok pesan dan suatu konstanta. Kemudian dirotasi kekiri beberapa bit yang kemudian ditambahkan ke salah satu dari a,b,c, atau d. Kemudian nilai a,b,c, dan d menggantikan nilai a,b,c, dan d. Kemudian dikeluarkan output yang merupakan gabungan dari a,b,c, dan d. Fungsi kompresi yang digunakan oleh algoritma md5 adalah sebagai berikut :
a ← b + (( a + g ( b,c,d) + X[k] + T[i] <<< s ), dimana g adalah salah fungsi primitif F,G,H,I seperti dibawah ini :
J. Proses MD5 dengan Berbagai Macam Masukan
1. Proses MD5 Dengan Masukan Berupa String
Proses MD5 dengan masukan berupa string adalah proses yang masukannya berupa karakter yang dimasukan melalui keyboard.
- Proses MD5 Dengan Masukan Berupa File
Proses MD5 dengan masukan berupa file adalah proses MD5 yang masukannya memanggil file yang kenmudian dihitung berapa panjang bitnya, dalam keadaan ini file diperlakukan sebagai bit memori sehingga masukannya tidak terpengaruh pada ekstensinya. Kemudian dilakukan proses MD5.
- Proses MD5 Sebagai Test Suite
Test suite dilakukan untuk mengetahui apakah program yang dibuat ini sudah benar ataukah masih terdapat kesalahan-kesalahan. Sebagai perbandingannya digunakan hasil yang sudah didapatkan oleh Ron Rivest yang sudah didefinisikan pada RFC 1321. Pada gambar 3.3 dapat dilihat bahwa masukan dari MD5 sudah ditentukan sehinnga hanya membandingkan hasil pada layar dengan yang tercantum pada RFC 1321.
K. Analisis Kecepatan MD5
Created By : SITTI NURHAERATY, Jurusan Teknik Informatika Fakultas Sains Dan Informatika Universitas Islam Negeri Makassar.
0 comments:
Post a Comment