BAB II LANDASAN TEORI
2.1 Teori Bilangan 2.1.1 Keterbagian Jika a dan b ∈ Z (Z = himpunan bilangan bulat) dimana b ≠ 0, maka dapat dikatakan b habis dibagi dengan a atau b mod a = 0 dan dinotasikan dengan a|b jika terdapat suatu bilangan x ∈ Z sehingga membentuk a = bx. Jika b tidak habis dibagi dengan a atau b mod a ≠ 0, maka dapat dinotasikan sebagai a | b [9]. Contoh: 3|9
à 9 ÷ 3 = 3 atau 9 mod 3 = 0
3 | 5 à 5 ÷ 3 = 1,67 atau 5 mod 3 = 2
2.1.2 Greatest Common Divisor (GCD) Misalkan a,b ∈ Z dan a,b ≠ 0, maka d disebut Greatest Common Divisor (GCD) atau Faktor Persekutuan Terbesar (FPB) dari a dan b jika: (i)
d>0
(ii)
d|a dan d|b
dan dinotasikan sebagai d = gcd(a,b) [9]. Contoh: Faktor Pembagi 15 = {1,3,5,15} Faktor Pembagi 25 = {1,5,25} Maka gcd(15,25) adalah 5
2.1.3 Algoritma Euclidean Algoritma Euclidean merupakan algoritma yang digunakan untuk mencari gcd dari dua bilangan bulat. Algoritma ini ditemukan oleh seorang matematikawan Yunani bernama Euclid, yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element [11].
51 Universitas Sumatera Utara
Misalkan m dan n adalah bilangan bulat tak negatif dengan m ≥ n. Misalkan r0 = m dan r1 = n. Lakukan pembagian secara berturut – turut untuk memperoleh r0 = r1q1 + r2
0 ≤ r2 ≤ r1,
r1 = r2q2 + r3
0 ≤ r3 ≤ r2,
⋮ rn-2 = rn-1 qn-1 + rn
0 ≤ rn ≤ rn-1,
rn-1 = rn qn + 0 gcd (m,n)
= gcd(r0,r1) = gcd(r1,r2) = ... = gcd(rn-2,rn-1) = gcd(rn-1,rn) = gcd(rn,0) = rn
Jadi, gcd dari m dan n adalah sisa terakhir yang tidak nol dari runtunan pembagian tersebut [11]. Contoh: Tentukan gcd(150, 22) 150 mod 22 = 18 22 mod 18 = 4 18 mod 4 = 2 4 mod 2 = 0 (berhenti) Maka gcd(150,22) adalah 2
2.1.4 Relatif Prima Jika a,b ∈ Z dan gcd(a,b) = 1 maka a dan b dikatakan relatif prima [9]. Contoh: 11 dan 7 relatif prima karena gcd(11,7) = 1 15 dan 5 tidak relatif prima karena gcd(15,5) = 0 ≠ 1
2.1.5 Least Common Multiple (LCM) Misalkan a,b dan d ∈ Z, d disebut Least Common Multiple atau Kelipatan Persekutuan Terbesar (KPK) dari a dan b jika:
Universitas Sumatera Utara
(i)
d>0
(ii)
a|d dan b|d
dan dinotasikan sebagai d = lcm(a,b) [9]. Contoh: Tentukan lcm(12,20). Kelipatan 12 = {12,24,36,48,60,72,84,...} Kelipatan 20 = {20,40,60,80,100,...} Maka lcm(12,20) adalah 60
2.1.6 Aritmatika Modulo Misalkan a,m ∈ Z dan m > 0, operasi a mod m (dibaca “a modulo m”) memberikan sisa jika a dibagi dengan m. Dengan kata lain a mod m = r sedemikian sehingga a = mq +r, dengan 0 ≤ r < m [11].
Contoh: (i) 33 mod 5 = 3 (karena 33 dibagi 5 memberikan hasil (q) = 6 dan sisa (r) = 3, atau ditulis sebagai 33 = 5 ⋅ 6 + 3) (ii) 30 mod 3 = 0
(30 = 3 ⋅ 10 + 0)
Misalkan a,b ∈ Z dan m > 0, a dan b dikatakan kongruen dalam hal modulo m jika memiliki sisa yang sama jika dibagi dengan bilangan positif m. Hal ini dilambangkan dengan a ≡ b (mod m) . Contoh: 38 mod 5 = 3 13 mod 5 = 3 Maka 38 ≡ 13 (mod 5)
2.1.7 Invers Modulo Misalkan suatu bilangan a relatif prima terhadap n atau gcd(a,n) = 1, maka invers dari a mod n adalah a-1 sedemikian hingga a-1. a = 1(mod n) [11].
Universitas Sumatera Utara
Contoh: Invers Modulo dari 4 mod 11 a-1
a-1. 4 (mod 11)
1
4
2
8
3
1
Maka, invers modulo dari 4 mod 11 = 3 karena 3.4 = 1 (mod 11). 2.2 Kriptografi Secara etimologi, Kriptografi berasal dari bahasa Yunani, yaitu krypto dan graphia. Kripto berarti rahasia dan graphia yang berarti tulisan. Menurut terminologinya kriptografi adalah ilmu dan seni untuk menjaga keamanan pesan ketika pesan dikirim dari suatu tempat ketempat yang lain. Dalam perkembangannya, kriptografi juga digunakan untuk mengidentifikasi pengiriman pesan dengan tanda tangan digital dan keaslian pesan dengan sidik jari digital (fingerprint) [3].
Pada dasarnya, kriptografi terdiri dari beberapa komponen seperti [4]: 1.
Enkripsi Enkripsi merupakan hal yang sangat penting dalam kriptografi sebagai pengamanan atas data yang dikirmkan agar rahasianya terjaga. Enkripsi mengubah pesan asli (plaintext) menjadi kode-kode yang tidak dimengerti (ciphertext).
2.
Dekripsi Dekripsi merupakan kebalikan dari proses enkripsi, yaitu mengubah kembali pesan yang telah dienkripsi ke bentuk asalnya.
3.
Kunci Kunci yang dimaksud disini adalah kunci yang dipakai untuk melakukan proses enkripsi dan dekripsi. Kunci terdiri atas dua, yaitu kunci pribadi (private key) dan kunci publik (public key)
4.
Ciphertext
Universitas Sumatera Utara
Ciphertext merupakan suatu pesan yang sudah melalui proses enkripsi. Pesan yang ada pada ciphertext tidak bisa dibaca karena berisi karakter-karakter yang tidak memiliki makna. 5.
Plaintext Plaintext merupakan suatu pesan bermakna yang akan diproses menggunakan algoritma kriptografi agar menjadi ciphertext.
6.
Pesan Pesan bisa berupa data atau informasi yang dikirim melalui kurir, saluran komunikasi data dan sebagainya.
7.
Cryptanalysis Cryptanalysis bisa diartikan sebagai analisis sandi untuk mendapatkan plaintext tanpa harus mengetahui kunci secara wajar.
Adapun fungsi dari kriptografi adalah [13]: -
Confidentiality (Kerahaasiaan). Menjaga agar pesan tidak dapat dibaca oleh pihak-pihak yang tidak berhak.
-
Authentication
(Otentikasi).
Memungkinkan
penerima
pesan
untuk
memastikan asal usulnya ; artinya seorang penyelundup tidak dapat menyamarkan dirinya sebagai orang lain -
Integrity
(Integritas
Data).
Memungkinkan
penerima
pesan
untuk
membuktikan bahwa pesan tidak di modifikasi/manipulasi selama dalam pengiriman; artinya seorang penyelundup tidak bisa menukar pesan yang asli dengan pesan yang salah. -
Nonrepudiation (Non-Penyangkalan). Pengirim tidak bisa menyangkal bahwa ia telah mengirimkan pesan.
2.2.1 Algoritma Simetris Algoritma simetris merupakan algoritma yang menggunakan kunci yang sama pada proses enkripsi dan dekripsinya. Algoritma simetris juga biasa disebut algoritma konvensional. Sistem kriptografi dengan algoritma simetris ini mengasumsikan pengirim dan penerima pesan sudah berbagi kunci yang sama sebelum bertukar pesan. Keamanan algoritma simetris ini terletak pada kerahasiaan kuncinya [10]
Universitas Sumatera Utara
Gambar 2.1 Skema Kriptografi Algortma Simetris. [10]. Algoritma simetris dibagi menjadi dua kategori, yaitu stream cipher (cipher aliran) dan block cipher. Stream cipher beroperasi dengan melakukan enkripsi dan dekripsi terhadap satu bit atau satu byte data. Sedangkan block cipher beroperasi dengan melakukan enkripsi dan dekripsi terhadap satu blok data [13].
Beberapa sistem kriptografi yang menggunakan algoritma simetris adalah [3]: -
One Time Pad
-
RC 4
-
Data Encryption Standard (DES)
-
Advanced Encryption Standard (AES)
2.2.2 Algoritma Asimetris (Public Key Algorithm) Algoritma asimetris merupakan algoritma yang memiliki kunci yang berbeda untuk proses enkripsi dan dekripsinya. Algoritma ini biasa juga disebut dengan algoritma kunci publik karena kunci untuk proses enkripsi bersifat publik, artinya siapapun bisa menggunakan kunci tersebut untuk melakukan enkripsi. Sementara itu, kunci untuk mendekripsikan pesan bersifat privat sehingga hanya si penerima pesan yang dapat mendekripsikan pesan karena hanya ia yang mengetahui kunci privatnya sendiri [13].
Gambar 2.2 Skema Kriptografi Algoritma Asimetris [10].
Universitas Sumatera Utara
Contoh sistem kriptografi yang menggunakan algoritma kunci publik adalah RSA (Rivest Shamir Adleman), ElGamal dan LUC.
2.2.3 Algoritma Asimetris Non Public Key Algoritma kriptografi non Public Key merupakan algoritma kriptografi dimana kunci yang digunakan untuk proses enkripsi dan dekripsinya berbeda, maka tidak termasuk algoritma simetris. Namun algoritma ini tidak termasuk dalam kriptografi kunci publik karena kedua kunci dapat dengan mudah diturunkan satu sama lain, jadi kedua kuncinya harus tetap dirahasiakan. Contoh algoritma yang menggunakan kriptografi non-public key adalah Pohlig-Hellman [13]. Kunci Privat, K1
Plaintext, P
Enkripsi EK1(P) = C
Kunci Privat, K2
Ciphertext, C
Dekripsi DK2(C) = P
Plaintext, P
Gambar 2.3. Skema Kriptografi Algoritma Non Public Key.
2.3 Algoritma Kriptografi LUC Algoritma kriptografi LUC merupakan salah satu sistem kriptografi yang menerapkan algoritma kunci publik. Algoritma ini dikemukakan oleh Peter J. Smith dan Michael J.J. Lennon pada tahun 1993 di New Zealand. LUC memiliki tiga tahap utama, yaitu pembangkitan kunci, enkripsi dan dekripsi [2]. LUC dibangun berdasarkan fungsi Lucas (Lucas Function). Penggunaan fungsi Lucas didalam mengolah data dari plaintext menjadi ciphertext atau sebaliknya hampir menyerupai fungsi pemangkatan yang digunakan oleh RSA.
Universitas Sumatera Utara
Fungsi Lucas merupakan fungsi deret
dan
yang dibangun dari dua
bilangan integer P dan Q. Kemudian dibangun sebuah persamaan kuadrat
−
+
= 0. Jika akar dari persamaan tersebut adalah a dan b, maka didapatkan P = a+b dan Q = ab. Kemudian fungsi Lucas didefinisikan sebagai berikut [2]: =( =
)/( − )
−
(1)
+
(2)
Dua fungsi pada barisan Lucas dapat diturunkan dari persamaan (1) dan (2) yang didefinisikan sebagai berikut: =
−
dimana n ≥ 2,
=
(3) = 0 dan
=1
−
dimana n ≥ 2,
(4) = 2 dan
=
Sistem kriptografi LUC hanya akan menggunakan deretan
dengan nilai Q=1
sehingga persamaan (4) dapat didefinisikan sebagai =
−
dimana n ≥ 2,
(5) = 2 dan
=
Sebagai contoh dimisalkan P = 3, Q = 1, maka 10 barisan Lucas pertama: Tabel 2.1 Perhitungan barisan Lucas sampai n=10. [12]
2.3.1 Pembangkitan Kunci LUC Dibutuhkan dua buah kunci, yaitu kunci publik e dan kunci privat d untuk melakukan proses enkripsi dan dekripsi pada LUC. Proses pembangkitan kunci dilakukan dengan cara sebagai berikut [15]: 1.
Pilih dua buah bilangan prima acak besar p dan q, dimana p ≠ q dan gcd(p,q) = 1
2.
Hitung N = p . q
3.
Ambil kunci publik acak e dengan syarat e relatif prima terhadap ϕ(N) =(p-1)(p+1)(q-1)(q+1) atau gcd(e, ϕ(N)) = 1
4.
Hitung kunci dekripsi d dengan ketentuan
Universitas Sumatera Utara
R(N)=lcm((p-1),(q-1),(p+1),(q-1)) dan de =1 mod R(N)
2.3.2 Lehmann Prime Generator Dalam algoritma kriptografi kunci publik diperlukan bilangan prima untuk proses pembangkitan kunci. Salah satu algoritma pengujian bilangan prima adalah algoritma Lehmann. Cara kerja algoritma Lehmann adalah sebagai berikut: 1. Pilih bilangan acak a yang lebih kecil dari p (
2. Hitung
=
3. Jika
(
)/
4. Jika
(
)/
)/
≠ 1 atau − 1 ( ≡ 1 atau − 1 (
), maka p pasti bukan prima ), maka kemungkinan p bikan prima tidak
lebih dari 50% Pengujian diulangi sebanyak t kali. Jika pehitungan menghasilkan nilai 1 atau -1, tetapi tidak selalu 1, maka kemungkinan p adalah prima dengan tingkat kesalahan tidak lebih dari 1/2
[13]. Pengujian sebaiknya dilakukan sehingga kemungkinan
primanya ≥ 99%.
Contoh 1: Misalkan penulis ingin melakukan pengujian apakah 9 adalah bilagan prima a=2 = 2(
)/
≡2
9 9
≡ 16 mod 9 ≡ 7 (
9)
Maka, dapat disimpulkan jika 9 bukan bilangan prima.
Contoh 2: Misalkan penulis ingin melakukan pengujian apakah 11 adalah bilangan prima a=2 = 2( ≡2
)/
11 11
≡ 32 mod 11 ≡ −1(
11) --- Kemungkinan tidak prima < 50 %
a=3
Universitas Sumatera Utara
= 3( ≡3
)/
11 11
≡ 243 mod 11 ≡ 1(
11) --- Kemungkinan prima 50 % + 25 % = 75 %
Setelah melakukan pengujian sebanyak dua kali dan menghasilkan nilai 1 dan -1, maka dapat disimpulkan bahwa 11 adalah bilangan prima dengan kemungkinan prima 75 %.
2.3.3 Algoritma Enkripsi LUC Dengan menggunakan kunci publik e yang telah dibangkitkan sebelumnya, maka proses enkripsi pesan plaintext menjadi ciphertext dengan algoritma kriptografi LUC adalah sebagai berikut: C=
=(P
−
) mod N
(6)
Fungsi enkripsi akan menghitung suku ke-n dari fungsi deret Lucas dengan indeks n adalah kunci publik e dan P adalah plaintext. Proses enkripsi akan menghasilkan ciphertext C.
2.3.4 Algoritma Dekripsi LUC Untuk mengembalikan ciphertext C menjadi pesan asli/plaintext P, maka dilakukan proses dekripsi dengan menggunakan kunci privat d. Fungsi dekripsi dengan algoritma kriptografi LUC didefinisikan sebagai berikut: P=
=(C.
−
) mod N
(7)
Seperti pada proses enkripsi, fungsi dekripsi akan menghitung suku ke-n dari fungsi deret Lucas dengan indeks n adalah kunci privat d dan C adalah ciphertext. Proses dekripsi akan menghasilkan pesan asli/plaintext P. 2.4 Steganografi Istilah steganografi berasal dari bahasa Yunani, yaitu steganos yang berarti penyamaran atau penyembunyian dan graphein yang berarti tulisan. Jadi, steganografi bisa diartikan sebagai ilmu dan seni menyamarkan/menyembunyikan pesan tertulis ke dalam pesan lainnya. Steganografi menyembunyikan pesan dalam data lain tanpa mengubah data yang
Universitas Sumatera Utara
ditumpanginya sehingga data yang ditumpanginya sebelum dan setelah proses penyembunyian hampir terlihat sama. Steganografi
yang
bersifat
“computer-based”
bisa
diterapkan
dengan
menggunakan berbagai media sebagai cover (media penyisipan). Media penyisipan merupakan suatu media untuk menyimpan pesan rahasia. Beberapa contoh media pemyimpan pesan rahasia yang digunakan dalam teknik steganografi antara lain adalah teks, audio, citra dan video. Perbedaan mendasar antara steganografi dengan kriptografi terletak pada proses penyembunyian data dan hasil akhir proses tersebut. Kriptografi melakukan proses pengacakan data asli sehingga dihasilkan data terenkripsi yang benar-benar acak dan berbeda dari aslinya. Sementara itu steganografi menyembunyikan data dalam data lain dengan cara menumpanginya tanpa mengubah data yang ditumpanginya tersebut sehingga tampilan data tetap terlihat sama [4]. Perbedaan steganografi dan kriptografi terlihat pada Gambar 2.4.
Gambar 2.4 Perbedaan Steaganografi dan Kriptografi [1].
2.4.1 Steganografi End of File Salah satu teknik dari steganografi adalah End of File. Teknik ini digunakan dengan cara menambahkan data diakhir file citra. Pada teknik ini, data atau file yang akan ditambahkan dapat lebih besar dari ukuran file citra [1]. Pesan yang disisipkan dengan metode ini jumlahnya tidak terbatas. Akan tetapi efek sampingnya adalah ukuran berkas menjadi lebih besar dari ukuran sebelumnya.
Universitas Sumatera Utara
Perhitungan kasar ukuran file yang telah disisipkan pesan sama dengan ukuran file sebelum disisipkan pesan ditambah dengan ukuran pesan rahasia yang disisipkan. Untuk mengenal data yang disisipkan pada akhir file, diperlukan suatu tanda pengenal atau simbol pada awal dan akhir data yang akan disisipkan [14][16]. Misalkan sebuah citra ukuran 10x6 memiliki nilai pixel seperti Gambar 2.5.
Gambar 2.5 Citra *bmp true color 200
42
97
182
101
40
24
88
63
112
67
200
100
50
75
50
121
42
91
109
25
150
65
200
75
28
56
90
83
100
156
46
77
19
25
189
84
210
78
33
101
34
213
40
101
60
80
111
143
77
44
66
99
125
190
200
31
80
92
111
Citra RGB tersebut akan disisipkan ciphertext “79 75
69”. Kemudian ciphertext
yang akan ditambahkan diberi karakter “&&&” dengan kode ASCII 38 sebagai penanda awal dan ÿÿÿ dengan kode ASCII 255 sebagai penanda akhir pesan. Selanjutnya sisipkan pesan di akhir citra, sehingga citra menjadi:
200
42
97
182
101
40
24
88
63
112
67
200
100
50
75
50
121
42
91
109
25
150
65
200
75
28
56
90
83
100
156
46
77
19
25
189
84
210
78
33
101
34
213
40
101
60
80
111
143
77
44
66
99
125
190
200
31
80
92
111
38
38
38
79
75
69
255
255
255
0
Universitas Sumatera Utara
Gambar 2.6 Citra setelah disisip pesan
Dan matriks tersebut akan dipetakan kembali dalam bentuk citra baru seperti Gambar 2.6 yang disebut stego image [7]. Jika besar plaintext tidak memenuhi lebar pixel citra, maka akan ditambahkan nilai pixel 0 yang merepresentasi warna hitam.
2.5 Penelitian yang Relevan Berikut adalah beberapa penelitian tentang algoritma kriptografi LUC dan steganografi End of File: 1. Pada penelitian yang dilakukan Irawan [7]. Penelitian yang bertujuan untuk merancang sebuah aplikasi yang mampu melakukan pengamanan pesan SMS pada telepon seluler berbasis android dengan menggunakan algoritma kriptografi LUC. Penelitian ini berhasil melakukan enkripsi dan dekripsi pesan teks yang terdiri dari huruf kapital.
2. Pada penelitian yang dilakukan Jauyah [8]. Penelitian ini bertujuan untuk membangun sebuah prototipe untuk aplikasi pengenalan telnet di lingkungan sistem operasi Linux dengan menggunakan sistem kriptografi LUC. Selain itu, peneliti juga melakukan perbandingan antara sistem kriptografi LUC dan RSA dari aspek pelaksanaan dan keselamatan, dan menyatakan bahwa sistem kripto LUC memiliki perbedaan yang tidak begitu signifikan dibandingkan dengan
Universitas Sumatera Utara
sistem kripto RSA dan dapat dijadikan sebagai alternatif dengan kemampuan yang cukup baik [8]. 3. Penelitian yang dilakukan oleh Wandani [16]. Penelitian ini berhasil mengkombinasikan algoritma kriptografi Rabin untuk mengenkripsi pesan berupa angka, lalu menyisipkan pesan kedalam sebuah citra berformat *bmp dengan teknik steganografi End of File.
Universitas Sumatera Utara
