ANALISIS KOMBINASI ALGORITMA KNAPSACK DAN RLE PADA FILE TEKS SKRIPSI NAMIRA LISTYA UTAMI TANJUNG

ANALISIS KOMBINASI ALGORITMA KNAPSACK DAN RLE PADA FILE TEKS

SKRIPSI

NAMIRA LISTYA UTAMI TANJUNG 081401093

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer NAMIRA LISTYA UTAMI TANJUNG 081401093

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013


PERSETUJUAN

Judul

: ANALISIS KOMBINASI ALGORITMA KNAPSACK DAN RLE PADA FILE TEKS

Kategori

: SKRIPSI

Nama

: NAMIRA LISTYA UTAMI TANJUNG

Nomor Induk Mahasiswa

: 081401093

Program Studi

: SARJANA (S1) ILMU KOMPUTER

Departemen

: ILMU KOMPUTER

Fakultas

: ILMU

KOMPUTER

INFORMASI

DAN

TEKNOLOGI

(FASILKOM-TI)

UNIVERSITAS

SUMATERA UTARA

Diluluskan di Medan, 22 Agustus 2013

Komisi Pembimbing

:

Pembimbing 2

Syahril Efendi, S.Si, MIT NIP. 196711101996021001

Pembimbing 1

M. Andri Budiman S.T., M.Comp.Sc., M.E.M. NIP. 197510082008011001

Diketahui/disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Dr. Poltak Sihombing, M.Kom NIP. 196203171991021001


PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, Agustus 2013

NAMIRA LISTYA UTAMI TANJUNG 081401093


PENGHARGAAN

Puji dan syukur penulis ucapkan kehadirat Allah SWT atas segala rahmat dan karuniaNya, sehingga penulis dapat menyelesaikan skripsi yang berjudul ” Analisis Kombinasi Algoritma Knapsack Dan Rle Pada File Teks”. Skripsi ini merupakan salah satu syarat yang ditetapkan untuk memperoleh gelar sarjana komputer di Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, shalawat beriring salam penulis persembahkan kepada Nabi Besar Muhammad SAW. Pada kesempatan kali ini penulis ingin mengucapkan terima kasih kepada semua pihak yang telah membantu penulis selama pengerjaan skripsi ini, antara lain kepada : 1.

Rektor USU Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc (CTM), Sp.A(K).

2.

Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.

3.

Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Departemen Ilmu Komputer, Fakultas Ilmu komputer dan Teknologi Informasi, Universitas Sumatera Utara dan sebagai dosen penguji dan pembanding I.

4.

Ibu Maya Silvi Lydia, BSc,.MSc selaku sekretaris Departemen Ilmu Komputer Fakultas Ilmu komputer dan Teknologi Informasi, Universitas Sumatera Utara.

5.

Bapak M. Andri Budiman, ST, M.Comp.Sc, MEM dan bapak Syahril Efendi, S.Si, MIT selaku dosen pembimbing.

6.

Bapak Ade Chandra, ST, M.Kom selaku dosen pembanding.

7.

Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.

8.

Seluruh dosen Departemen Ilmu Komputer, Fakultas Ilmu komputer dan Teknologi Informasi, Universitas Sumatera Utara yang telah membimbing dan mencurahkan ilmunya selama masa perkuliahan.

9.

Seluruh pegawai di lingkungan Program Studi S1 Ilmu Komputer Fasilkom-TI USU.

10. Kedua orang tua tercinta, Ayahanda H.M. Bustami Tanjung dan ibunda H. Ummi Salamah Lubis atas kasih sayang, do’a, dukungan dan motivasi yang tak ternilai harganya. 11. Ketiga adinda Dhabitah Amalina Utami Tanjung, M.Raja’a Fawwaz Tanjung, dan M. Rafiuddin Tanjung yang selalu memberi semangat dan do’anya.


12. Keluarga besar S1 Ilmu Komputer, khususnya angkatan 2008 yang telah banyak memberi dukungan, masukan, dan kerjasama yang baik. 13. Dira Fahrendy Sembiring yang telah memberi semangat, bimbingan dan serta doanya. 14. Terkhusus ParkirRanger Saria Mahdi Ginting, S.kom, Nurul Faradhilla, S.Kom , Khairunisa Lubis, Skom, Octi Fadhilla Khair, S.Kom. Gustaf Prameswara, S.Kom. Setyo M. Syamsudin Noor, S.Kom, Nanang Tri Bhuana, S.Kom, Nasan Siregar, S.Kom, Marthin F.P, serta teman-teman dilingkungan kampus yang tidak bisa disebutkan satu-persatu yang telah memberikan dukungan yang begitu membekas dihati. 15. Guru-guru dari SD Kemala Bhayangkari 1 Medan, SMPN 15 Medan dan SMAN 14 Medan untuk ilmu yang telah diberikan. 16. Semua pihak yang terlibat langsung ataupun tidak langsung dalam membantu penyelesaian skripsi ini dan tidak dapat penulis ucapkan satu persatu.

Tak ada gading yang tidak retak, demikian juga halnya dengan skripsi ini. Kritik dan saran yang membangun sangat penulis harapkan. Semoga skripsi ini bisa memberikan manfaat bagi pembaca penulis sendiri, amin. Medan, Agustus 2013

Penulis


ABSTRAK

Algoritma Knapsack merupakan bagian dari kriptografi asimetri yang mana kunci enkripsinya berbeda dengan kunci dekripsinya. Di samping masalah keamanan file teks, masalah ukuran dari sebuah file teks juga menjadi pertimbangan. File teks yang berukuran besar dapat dimampatkan dengan melakukan proses kompresi. Algoritma Run Length Encoding (RLE) merupakan algoritma yang mengecilkan ukuran file teks, apabila teks tersebut mengalami banyak perulangan karakter. Kombinasi algoritma Knapsack dan RLE dapat menjamin file Teks tidak dapat dilihat oleh pengguna yang tidak berhak dan dapat menjamin file teks dapat disimpan dalam media file yang berkapasitas rendah. Pada penelitian ini, penulis membuat program kombinasi algortitma knapsack dan RLE pada file teks. Pada algoritma Knapsack akan terjadi penambahan ukuran file teks, hal ini dapat dilihat pada contoh kasus yang mana ukuran plainteks (pesan asli) adalah 9 bytes, kemudian setelah dilakukan proses enkripsi ukuran file teks menjadi 37 bytes. Pada algoritma kompresi RLE terjadi pengurangan ukuran sebagai contoh kasus cipherteks (pesan yang disamarkan) yang awalnya berukuran 37 bytes setelah dilakukan proses kompresi ukurannya menjadi 7 bytes. Proses kombinasi dapat dilakukan sebaliknya, yaitu kompresi teks terlebih dahulu kemudian enkripsi teks tersebut, masih dengan plainteks yang sama beukuran 9 bytes, setelah dilakukan kompresi ukuran file menjadi 2 bytes. Kemudian dilakukan enkripsi ukuran file menjadi 9 bytes. Karena itu pengunaan kombinasi enkripsi dan kompresi data lebih baik karena file menjadi lebih kecil dibandingkan kombinasi kompresi dan enkripsi data. Plainteks yang memiliki banyak perulangan karakter akan terkompresi dengan baik. Katakunci

: File Teks, Knapsack, Kompresi, Kriptografi, Run Length Encoding


ANALYSIS COMBINATION KNAPSACK ALGORITHM AND RLE FOR TEXT FILE

ABSTRACT

Knapsack algorithm is part of the asymmetric cryptography which the encryption key is different from the decryption key. Apart from safety, the size of the file is also measure and the file may be compressed further. Run Length Encoding (RLE) algorithm is an algorithm that shrink the size of the text file, if and only if the text has a lot of looping of character. Combination of Knapsack and RLE algorithm can guarantee that text files may not be seen by unauthorized users and to ensure the text file may be stored in a low-capacity media file. In this paper, writer makes a combination program of Knapsack and RLE for text files. Sometimes Knapsack algorithm may add the size of the text file, it can be seen in the case where the size of the plaintext is only 9 bytes, then after the encryption process the text file size becoming 37 bytes. In the RLE compression algorithm happen size reduction as an example the case of the ciphertext which initially measuring 37 bytes after compression process the size becoming 7 bytes. Combination process can be done otherwise, the text compression first and then the encrypting text, still with the same plaintext measuring 9 bytes, after the compressed file size to 2 bytes. Then do the encryption of the file size to 9 bytes. There for using a combination of encryption and file compression are better because it is smaller than a combination of compression and file encryption. The plaintext who has a lot of looping of character will be compressed correctly.

Keywords: Compression, Cryptography, Knapsack, Run Length Encoding, Text File


DAFTAR ISI

Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

Bab 1

Bab 2

Bab 3

ii iii iv vi vii viii x xi

Pendahuluan

1

1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7.

1 3 3 3 3 4 5

Latar Belakang Rumusan Masalah Batasan Masalah Tujuan Penelitian Manfaat Penelitian Metodologi Penelitian Sistematika Penulisan

Landasan Teori

6

2.1. Kriptografi 2.1.1 Pengertian Kriptografi 2.1.2 Enkripsi dan Dekripsi 2.1.3 Jenis Kriptografi 2.2. Algoritma Knapsack 2.3. Teori Dasar Kompresi 2.3.1 Kompresi data 2.3.2 Dekompresi data 2.4. Run Length Encoding

6 6 7 8 10 14 14 16 17

Analisis dan Perancangan Sistem

19

3.1. Analisis Sistem 3.1.1 Analisis Masalah 3.2 Analisis Persyaratan 3.2.1 Analisis Persyaratan Fungsional 3.2.2 Analisis Persyaratan Non-Fungsional 3.3 Pemodelan

19 19 20 21 21 22


3.3.1 3.3.2 3.3.3 3.3.4

3.4

Bab 4

Pemodelan Persyaratan Sistem Use Case Activity Diagram Sequence Diagram Perancangan Flowchart Sistem 3.3.4.1 Flowchart Proses Algoritma Knapsack 3.3.4.2 Flowchart Proses Algoritma RLE 3.3.4.3 Flowchart Proses Algoritma Kombinasi Perancangan Antar Muka 3.4.1 Perancangan Form Beranda 3.4.2 Perancangan Form Menu

22 26 31 34 34 36 37 40 41 41

Implementasi dan Pengujian

45

4.1. Implementasi Sistem 4.1.1. Proses Tahapan Algoritma Knapsack dan RLE 4.1.1.1 Proses Bangkit Kunci 4.1.1.2 Proses Kompresi dan Enkripsi 4.1.1.3 Proses Enkripsi dan Kompresi 4.1.2. Tampilan Antarmuka Sistem 4.1.1.1. Tampilan Form Beranda 4.1.1.2. Tampilan Form Menu 4.1.1.3. Tampilan Form Tentang 4.1.1.4. Tampilan Form Bantuan 4.2 Pengujian 4.2.1 Pengujian Kompresi 4.2.2 Pengujian Dekompresi 4.2.3 Pengujian Bangkit Kunci 4.2.4 Pengujian Enkripsi 4.2.5 Pengujian Dekripsi 4.2.6 Pengujian Kombinasi Algoritma Knapsack dan RLE 4.2.7 Pengujian Dekripsi dan Dekompresi 4.2.8 Pengujian Dekompresi dan Dekripsi 4.2.9 Hasil Pengujian

45 45 45 47 50 51 51 52 52 53 54 54 55 56 57 58 59 61 63 64

Bab V Kesimpulan dan Saran 5.1. Kesimpulan 5.2. Saran Daftar Pustaka Lampiran A Listing Program

66 66 67 68 A-1


DAFTAR TABEL

Halaman 3.1 3.2 3.3 3.4 3.5 3.6 4.1 4.2

Spesifikasi Use Case Kompresi Spesifikasi Use Case Dekompresi Spesifikasi Use Case Bangkit Kunci Spesifikasi Use Case Enkripsi Spesifikasi Use Case Dekripsi Spesifikasi Use Case Kombinasi Tabel Hasil Pengujian Kombinasi untuk TEKS1.txt Tabel Hasil Pengujian Kombinasi untuk TEKS2.txt

23 23 24 24 25 25 65 66


DAFTAR GAMBAR

2.1 2.2 2.3 2.4 2.5 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13

Proses Enchipering dan Deciphering Kriptografi Simetris Kriptografi Kunci Publik Compresion dan Decompresion Coder dan Decoder Diagram Ishikawa untuk Analisis Permasalahan Sistem Use case diagram Activity Diagram Kompresi Activity Diagram Dekompresi Activity Diagram Bangkit Kunci Activity Diagram Enkripsi Activity Diagram Dekripsi Activity Diagram Kombinasi Sequence diagram Kombinasi Algoritma Kompresi dan Enkripsi Sequence diagram Kombinasi Algoritma Enkripsi dan Kompresi Sequence diagram Bangkit Kunci Flowchart Enkripsi Flowchart Dekripsi Flowchart Kompresi Flowchart Dekompresi Flowchart Kompresi dan Enkripsi Flowchart Enkripsi dan Kompresi Flowchart Dekompresi dan Dekripsi Flowchart Dekripsi dan Dekompresi Form Beranda Form Bangkit Kunci Form Kombinasi Form Dekripsi dan Dekompresi Form Dekompresi dan Dekripsi Source Code proses Bangkit Kunci Rahasia Source Code proses Bangkit Kunci Publik Source Code proses Kompresi Source Code proses Enkripsi Source Code proses Dekripsi Source Code proses Dekompresi Tampilan Form Beranda Tampilan Form Tentang Tampilan Form Bantuan Tampilan Pop-up Windows Pilih Teks Tampilan Pengujian Kompresi Tampilan Pengujian Dekompresi Tampilan Pengujian Bangkit Kunci

Halaman 6 8 9 16 17 20 22 26 27 28 29 30 31 32 33 34 35 35 36 36 37 38 39 40 41 42 43 44 45 47 48 49 50 51 51 53 54 54 55 56 57 58


4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22

Tampilan Pengujian Enkripsi Informasi Penyimpanan File Enkripsi Tampilan Pengujian Dekripsi Tampilan Pengujian Kombinasi untuk TEKS1 Tampilan Pengujian Kombinasi untuk TEKS2 Tampilan Pengujian Dekripsi dan Dekompresi untuk TEKS1 Tampilan Pengujian Dekripsi dan Dekompresi untuk TEKS2 Tampilan Pengujian Dekompresi dan Dekripsi untuk TEKS1 Tampilan Pengujian Dekompresi dan Dekripsi untuk TEKS2


59 59 60 61 62 63 63 64 65

ANALISIS KOMBINASI ALGORITMA KNAPSACK DAN RLE PADA FILE TEKS SKRIPSI NAMIRA LISTYA UTAMI TANJUNG

Recommend Documents