Bab 2: Kriptografi Landasan Matematika Fungsi Misalkan A dan B adalah himpunan. Relasi f dari A ke B adalah sebuah fungsi apabila tiap elemen di A dihubungkan dengan tepat satu elemen di B. Fungsi juga disebut pemetaan atau transformasi. Jika f adalah fungsi dari A ke B, dapat dituliskan sebagai f :A→B
Fungsi Invers Jika terdapat f sehingga f : A → B berkoresponden satu-ke-satu dari A ke B, maka invers dari f , dilambangkan dengan f −1 yang memetakan B ke A. Dapat pula ditulis sebagai f −1 : B → A Fungsi yang memiliki invers dinamakan fungsi invertible (dapat dibalikkan) karena fungsi balikannya dapat didefinisikan. Sebaliknya, suatu fungsi dikatakan non invertible karena fungsi balikannya tidak dapat didefinisikan.
Fungsi Satu Arah Fungsi f : A → B dikatakan Fungsi Satu Arah apabila f (x) mudah dihitung untuk semua x ∈ A tetapi tidak mungkin atau sangat sukar mencari x yang memenuhi f (x) = y untuk y ∈ B. 9
Basis Bilangan (Radix) Dalam sistem numerik, basis atau Radix menunjukkan banyaknya lambang bilangan yang unik, termasuk nol, yang digunakan sebagai nilai tempat bilangan dalam merepresentasikan suatu nilai. Radix biasanya dideskripsikan dengan simbol b. Sebagai contoh, untuk sistem desimal b bernilai 10, untuk sistem oktal b bernilai 8, dan untuk sistem biner b bernilai 2. Cara lain adalah dengan menuliskan angka desimal dibawah angka yang direpresentasikan. Sebagai contoh 11110112 artinya bilangan 1111011 merupakan bilangan dengan basis 2 (biner), senilai dengan 12310 , 1738 , dan 7B16 . Lambang bilangan yang digunakan pada sistem bilangan dengan basis b adalah {0, 1, . . . , b − 2, b − 1}. Sehingga, sistem bilangan biner memiliki lambang bilangan {0, 1}, sistem bilangan basis 7 memiliki lambang bilangan {0, 1, . . . , 5, 6}. Mengubah bilangan dengan basis b ke bilangan desimal dapat dilakukan dengan cara pemangkatan, yaitu penjumlahan dari hasil perkalian nilai lambang bilangan dengan nilai tempatnya. Misalkan an an−1 . . . a2 a1 a0 adalah suatu bilangan dengan basis b, maka nilai desimal bilangan tersebut dapat dicari dengan: n X (ai × bi ). i=0
Sebagai contoh: 2415 = 2 × 52 + 4 × 51 + 1 × 50 = 7110 .
Sifat Pembagian Bilangan Bulat Bilangan bulat yang dimaksud adalah bilangan yang tidak memiliki pecahan desimal. Misalkan a dan b adalah bilangan bulat dengan a 6= 0. Apabila terdapat bilangan bulat c sehingga b = ac, dinyatakan bahwa a membagi b. Jika ditulis dengan notasi matematika: b = ac → a|b
, c ∈ Z, a 6= 0
Greatest Common Divisor (gcd) Apabila terdapat a dan b bilangan bulat tak nol, maka pembagi bersama terbesar (greatest common divisor ) dari a dan b adalah bilangan bulat terbesar d yang 10
memenuhi d|a dan d|b. Dalam hal ini dinyatakan bahwa gcd(a, b) = d. Untuk kasus dimana gcd(a, b) = 1, dikatakan bahwa a relatif prima terhadap b dan sebaliknya.
Fungsi Phi(φ) Untuk n ≥ 1 fungi Phi φ(n) didefinisikan sebagai banyaknya bilangan bulat positif yang tidak lebih dari n dan relatif prima terhadap n. Sebagai contoh, φ(24) = 9 sebab bilangan bulat positif yang relatif prima dan tidak lebih dari 24 adalah 1, 5, 7, 9, 11, 13, 17, 19, 23 Fungsi Phi ini juga sering disebut sebagai indikator ataupun totient. Jika n prima maka setiap bilangan bulat positif kurang dari n selalu relatif prima terhadap n, sehingga φ(n) = n − 1. Jika n komposit (bukan prima), maka terdapat 1 ≤ d ≤ n sehingga gcd(d, n) 6= 1. Dengan demikian, sedikitnya terdapat dua bilangan bulat positif diantara 1, 2, . . . , n yang tidak relatif prima terhadap n, yaitu d dan n. Oleh sebab itu didapat: φ(n) = n − 1
jika dan hanya jika n prima
Fungsi Phi merupakan fungsi multiplikatif, artinya φ(mn) = φ(m)φ(n)
Aritmatika Modular Aritmatika modular adalah sebuah sistem aritmatika dimana suatu bilangan bulat akan kembali ke nilai dasar setelah mencapai nilai tertentu (modulus). Contoh yang paling umum adalah pembagian waktu 24 jam. Sistem ini membagi waktu dari tengah malam ke tengah malam berikutnya menjadi 24 bagian, diberi angka dari 0 hingga 23. Jika saat ini waktu menunjukkan pukul 20:00, maka setelah 7 jam waktu akan menunjukkan pukul 03:00. Dalam penjumlahan biasa, 20+7 = 27, bukanlah solusi yang diinginkan; Melainkan 20+7 = 3. Hal ini disebabkan waktu ”kembali” saat tengah malam, yaitu pukul 24:00. Sistem ini disebut sistem aritmatika modulo 24. 11
Kongruensi Notasi ≡ menyatakan kongruensi. Bilangan bulat a dan b dikatakan kongruen modulo n apabila kedua bilangan dibagi dengan n memiliki sisa pembagian yang sama. a ≡ b mod n Notasi diatas dibaca: ”a kongruen terhadap b dalam modulo n” Dengan menggunakan notasi, penjumlahan yang disebutkan sebelumnya dapat ditulis: 20 + 7 = 27 ≡ 3 mod 24
Beberapa Sifat Kongruensi Beberapa sifat yang berkaitan dengan kongruensi (juga berkenaan dengan penjumlahan dan perkalian) yaitu: Jika a1 ≡ b1 mod n dan a2 ≡ b2 mod n, maka: • (a1 + a2 ) ≡ (b1 + b2 ) mod n • (a1 a2 ) ≡ (b1 b2 ) mod n
Fermat’s Little Theorem Fermat’s Little Theorem menyatakan bahwa untuk semua p bilangan prima, maka untuk semua bilangan bulat a, ap − a habis dibagi p. Dalam notasi aritmatika modular ditulis: ap ≡ a mod p Variasi lain teorema ini mengatakan: apabila p prima dan a bilangan bulat yang prima relatif terhadap p, maka ap−1 − 1 habis dibagi p. Notasinya: ap−1 ≡ 1 12
mod p
Perumuman Perumuman dari Fermat’s Little Theorem mengatakan bahwa jika p prima, m dan n bilangan bulat positif yang memenuhi m ≡ n mod (p − 1) maka ∀a ∈ Z : am ≡ an
mod p
lebih jauh, dengan ϕ(n) menyatakan fungsi ϕ Euler, n ∈ Z dan gcd(a, n) = 1 maka aϕ(n) ≡ 1
mod n
Chinese Remainder Theorem Andaikan ni , i = 1, 2, . . . , k bilangan bulat positif yang saling prima, maka untuk semua bilangan ai , i = 1, 2, . . . , k terdapat x yang memenuhi sistem kongruensi x ≡ a1 x ≡ a2 .. .
mod n1 mod n2
x ≡ ak
mod nk
k Y lebih jauh, semua solusi x kongruen terhadap modulo N . Dengan N = ni . i=1
Oleh sebab itu untuk semua 1 ≤ i ≤ k x≡y
mod ni ⇔ x ≡ y
mod N
Kriptografi Definisi Kriptografi Kriptografi (cryptography) berasal dari bahasa Yunani yaitu kryptos (κρυπτ oς) yang berarti rahasia dan gr´aph¯o (γραϕω) yang berarti tulisan. Jadi secara harfiah, Kriptografi berarti tulisan rahasia. Beberapa literatur berbeda dalam pendefinisian Kriptografi. Pada buku-buku yang diterbitkan sekitar tahun 1980 menyatakan bahwa Kriptografi adalah ilmu dan seni untuk menjaga kerahasiaan pesan dengan cara menyandikannya ke dalam bentuk yang tidak dapat dimengerti. 13
Definisi tersebut memang cocok dengan keadaan dimasa itu, dimana Kriptografi digunakan untuk saling bertukar pesan rahasia di kalangan militer, diplomat, dan intelejen. Namun sekarang Kriptografi tidak hanya menyandikan pesan, akan tetapi juga untuk pengecekan integritas data dan otentikasi pengirim.
Terminologi Kriptografi Istilah-istilah yang sering dipakai dalam Kriptografi antara lain: Message, Plaintext, Ciphertext Message (pesan) dan plaintext (teks polos) adalah informasi yang dapat dibaca dan dimengerti maksudnya. Pesan dapat berupa data atau informasi yang dikirim atau disimpan dalam suatu media. Supaya pesan tidak dapat dimengerti oleh pihak lain, pesan perlu disandikan ke bentuk lain yang tidak dapat dimengerti. Bentuk pesan yang telah tersandi disebut Ciphertext (teks tersandi). Teks tersandi harus dapat diubah kembali ke bentuk asal, plaintext, agar informasi yang dikirim/tersimpan dapat dibaca. Sender dan Recipient Dalam komunikasi terdapat sedikitnya dua pihak: pengirim (sender ) yaitu orang yang mengirimkan informasi dan penerima (recipient) yang menerima informasi. Enkripsi dan Dekripsi Enkripsi (encryption) adalah suatu proses penyandian teks polos menjadi teks tersandi. Sebaliknya, Dekripsi (decryption) adalah proses pengembalian teks tersandi menjadi teks polos. Kedua proses tersebut dapat diterapkan baik pada informasi yang dikirim maupun disimpan. Cipher dan Key Satu Algoritma Kriptografi adalah rangkaian aturan untuk en Ciphering dan de Ciphering. Selain itu, dapat diartikan sebagai fungsi matematika yang digunakan untuk Enkripsi dan Dekripsi. Konsep ini, juga biasa disebut Cipher atau Kriptosistem, didasari oleh relasi lima himpunan (P, C, K, E, D) yang memenuhi kondisi berikut: 14
• P adalah himpunan semua kemungkinan plaintext • C adalah himpunan semua kemungkinan Ciphertext • K, disebut keyspace, adalah himpunan semua kemungkinan key (kunci) • Untuk setiap K ∈ K, terdapat aturan Enkripsi ek ∈ E dan aturan Dekripsi dk ∈ D. Tiap ek : P → C dan dk : C → P adalah fungsi sedemikian sehingga dk (ek (x)) = x untuk setiap x ∈ P Kunci adalah parameter yang digunakan untuk transformasi en Ciphering dan de Ciphering. Kunci biasanya berupa string atau deretan bilangan.
Gambar 1: Skema Kriptosistem
Penyadap Penyadap (eavesdropper ) adalah pihak ketiga yang berusaha menangkap informasi ditengah transmisi pesan antara pengirim dan penerima. Tujuannya mengambil sebanyak-banyaknya informasi mengenai sistem Kriptografi yang digunakan untuk berkomunikasi dengan maksud untuk memecahkan Ciphertext. Penyadap dikenal juga dengan: enemy, intruder, interceptor, adversary, dan bad guy.
Kriptanalisis dan Kriptologi Apabila kriptografi adalah seni untuk menyandikan pesan, kriptanalisis adalah lawan dari kriptografi. Kriptanalisis adalah ilmu dan seni untuk memecahkan teks tersandi menjadi teks polos tanpa mengetahui kunci yang digunakan. Kriptologi adalah studi mengenai kriptografi dan kriptanalisis. Kedua ilmu dan seni ini saling berkaitan. 15
Gambar 2: Skema kriptologi
Tujuan Kriptografi Kerahasiaan Pesan yang telah disandikan haruslah terjaga kerahasiaannya. Oleh sebab itu pihak lain yang tidak berhak tidak dapat membacanya. Integritas Data Teks polos, informasi yang dikirim ke penerima, utuh dan dijamin keutuhannya setelah diterima. Pesan yang diterima juga dijamin belum pernah dimanipulasi selama pengiriman. Otentikasi Identitas pengirim dijamin keabsahannya. Artinya yang mengirim informasi adalah benar-benar pengirim, bukan pihak ketiga yang berpura-pura menjadi pengirim.
Beberapa Contoh Kriptosistem Secara umum, Kriptosistem dibagi menjadi dua bagian besar: 1. Kriptosistem Kunci Simetris 2. Kriptosistem Kunci Asimetris Perbedaan antara keduanya adalah banyaknya kunci yang digunakan. Di bawah akan dibahas satu per satu beserta contohnya. 16
Kriptosistem Kunci Simetris Kriptosistem kunci simetris (Symmetric-key Cryptosystem) adalah Algoritma yang menggunakan satu kunci untuk kedua proses Enkripsi maupun Dekripsi. Selain disebut symmetric-key, jenis Kriptosistem ini juga disebut secret-key, single-key, shared-key, dan one-key.
Gambar 3: Symmetric-key Algorithm Karena hanya menggunakan satu buah kunci, atau lebih dari satu kunci dengan kunci-kunci yang berkaitan secara simpel; Masalah utama yang muncul adalah cara mengirimkan kunci secara aman ke penerima. Tentunya pihak lain tidak boleh mengetahui isi kunci yang dikirimkan. Waktu proses Kriptosistem simetris jauh lebih cepat daripada Kriptosistem asimetris. Shift Cipher Shift Cipher atau sandi geser adalah salah satu contoh Algoritma kunci simetris yang sederhana. Algoritma ini bekerja dengan menggeser pesan huruf per huruf sebanyak k karakter. Ambil P = C = K = Z26 . Untuk 0 ≤ K ≤ 25, ek (x) = x + K dk (y) = y − K
mod 26 mod 26
dengan x, y ∈ Z26 Huruf-huruf pada plaintext diubah terlebih dahulu menjadi bentuk angka pada Z26 : A ↔ 0, B ↔ 1, . . . , Z ↔ 25. 17
Sebagai contoh, akan diubah teks INSTITUTTEKNOLOGIBANDUNG dengan K = 14. Hal pertama yang dilakukan adalah mengubah plaintext ke dalam bentuk angka, yaitu: 8 13 18 19 8 19 20 19 19 4 10 13 14 11 14 6 8 1 0 13 3 20 13 6 kemudian dimasukkan satu per satu nilai x ∈ P ke dalam e14 (x). Akan dihasilkan Ciphertext 22 1 6 7 22 7 8 7 7 18 24 1 2 25 2 20 22 15 14 1 17 8 1 20 terakhir, bentuk angka Ciphertext diubah kembali menjadi bentuk teks: WBGHWHIHHSYBCZCUWPOBRIBU. Untuk mendapatkan plaintext dilakukan proses yang sama dengan proses Enkripsi dengan urutan terbalik. Hill Cipher Algoritma ini diciptakan pada tahun 1929 oleh Lester S. Hill. Ambil m bilangan bulat positif, kemudian definisikan P = C = (Z26 )m . Ide besarnya adalah untuk mengambil sebanyak m kombinasi linear terhadap m karakter alfabet dalam satu elemen Ciphertext. Misalkan m = 2, dapat dituliskan satu elemen plaintext sebagai x = (x1 , x2 ) dan satu elemen Ciphertext sebagai y = (y1 , y2 ) sehingga y1 = ax1 + bx2 y2 = cx1 + dx2 atau dapat dituliskan dalam bentuk matriks (y1 , y2 ) = (x1 , x2 )
a b c d
Secara umum, diambil matriks Km×m sebagai kunci. Untuk x = (x1 , . . . , xm ) ∈ P dan K ∈ K, dapat dihitung y = eK (x) = (y1 , . . . , ym ) sebagai berikut: k11 k12 · · · k1m k21 k22 · · · k2m (y1 , y2 , . . . , ym ) = (x1 , x2 , . . . , xm ) .. .. .. .. . . . . km1 km2 · · · kmm dengan kata lain, y = xK. 18
Untuk proses Dekripsinya, dapat digunakan invers matriks K −1 sehingga x = dK (y) = yK −1 . Perlu dicatat bahwa seluruh operasi dilakukan pada Z26 . Dari bahasan diatas, dapat dituliskan deskripsi Hill Cipher : Ambil m bilangan bulat positif, P = C = (Z26 )m , dan K = {matriks m × m yang memiliki invers di Z26 } untuk kunci K ∈ K, definisikan eK (x) = xK dK (y) = yK −1 dimana semua operasi dilakukan di Z26 . Sebagai contoh, akan mengenkripsi kata JULY dengan kunci 11 8 K= 3 7 dapat diperiksa bahwa invers matriks K −1 di Z26 adalah 7 18 −1 K = 23 11 karena KK
−1
=
11 8 3 7
7 18 23 11
261 286 = 182 131 1 0 ≡ mod 26 0 1
terdapat dua elemen plaintext, yaitu (9, 20) (mewakili JU) dan (11, 24) (mewakili LY). Dapat dihitung 11 8 eK (9, 20) = (9, 20) 3 7 = (99 + 60, 72 + 140) ≡ (3, 4) mod 26 dan
11 8 eK (11, 24) = (11, 24) 3 7 = (121 + 72, 88 + 168) ≡ (11, 22) mod 26 19
menghasilkan Ciphertext DELW. Untuk proses Dekripsinya dapat dihitung 7 18 dK (3, 4) = (3, 4) 23 11 ≡ (9, 20) mod 26 dan dK (11, 22) = (11, 22) ≡ (11, 24)
7 18 23 11 mod 26
yang menghasilkan JULY, plaintext semula.
Kriptosistem Kunci Asimetris Algoritma ini umum juga disebul Kriptosistem kunci publik (Public-key Cryptosystem). Kriptosistem ini menggunakan dua buah kunci: Private Key (Kunci Privat) dan Public Key ( kunci publik). Sesuai dengan namanya, kunci publik bebas didistribusikan ke mana saja dan ke siapa saja sebab kunci ini hanya digunakan untuk mengenkripsi informasi. Sebaliknya, kunci privat hanya dimiliki oleh penerima untuk men Dekripsi informasi yang telah dienkripsi oleh kunci publik.
Gambar 4: Public-key Algorithm Pada Kriptosistem ini, masalah distribusi kunci dapat dieliminasi. Akan tetapi pasangan kunci yang dipakai haruslah dikomputasi, pengirim atau penerima data 20
tidak dapat sembarangan memilih kunci yang akan digunakan. Ini mengakibatkan proses yang dilalui menjadi lebih banyak sehingga total waktu proses menjadi lebih lama dibandingkan Kriptosistem kunci simetris. Bagaimanapun juga tingkat keamanan Kriptosistem jenis ini lebih tinggi daripada Kriptosistem kunci simetris. RSA RSA menggunakan operasi matematika di Zn dimana n adalah hasil kali dari dua bilangan prima ganjil p dan q, dimana p 6= q. Deskripsi Kriptosistem rsa: Misal n = pq, p dan q prima. Misal P = C = Zn , definisikan K = (n, p, q, a, b) : n = pq , p, q prima, ab ≡ 1
mod φ(n)
untuk K ∈ K definisikan eK (x) = xb dK (y) = y a
mod n mod n
dimana x, y ∈ Zn . Nilai (n, b) adalah kunci publik, (n, a) adalah kunci privat, dan nilai p, q rahasia. Dapat diperiksa bahwa eK dan dK adalah operasi yang saling invers. Telah didefinisikan bahwa ab ≡ 1 mod φ(n) sehingga ab ≡ 1 mod (p − 1)(q − 1) atau; ab − 1 = k(p − 1)(q − 1) untuk suatu k ∈ Z.
Dapat diperiksa bahwa ab − 1 = l(p − 1) atau; ab ≡ 1 mod (p − 1)
dan ab − 1 = m(q − 1) atau; ab ≡ 1 mod (q − 1) 21
dari hasil diatas didapat dk (ek (x)) = (xb )a ≡ ≡ ≡ ≡ ≡
xk(p−1)+1 mod p xk(p−1)+1 mod p (x(p−1) )k x mod p 1k x mod p (Fermat’s Little Theorem) x mod p.
Dengan cara serupa didapat dk (ek (x)) = (xb )a ≡ x mod q. Kemudian dengan Chinese Remainder Theorem, dapat disimpulkan dk (ek (x)) = (xb )a ≡ x mod pq ≡ x mod n.
Untuk menentukan kunci a dan b langkah yang perlu diambil antara lain: 1. Pilih dua bilangan prima p dan q; 2. Hitung n = pq dan φ(n) = (p − 1)(q − 1); 3. Pilih bilangan acak 1 < b < φ(n) dimana gcd(b, n) = 1; 4. Hitung a = b−1 mod φ(n), sehingga didapatkan a, b, n. Telah dibahas diatas bahwa (n, a) kunci privat dan (n, b) kunci publiknya. Sebagai contoh, akan dienkripsi pesan ”HARIINI” menggunakan RSA. Sebelumnya harus dicari dulu pasangan kuncinya. Pilih p = 47 dan q = 71, sehingga dapat dicari n = pq = 47 × 71 = 3337 φ(n) = (p − 1)(q − 1) = 46 × 70 = 3220 22
kemudian pilih b = 79. Dapat diperiksa bahwa gcd(79, 3220) = 1. Karena ab ≡ 1 mod φ(n) maka ab − 1 = kφ(n) 1 + kφ(n) a = b 1 + 3220k a = 79 untuk nilai k = 25 didapatkan nilai bulat a = 1019. Berikutnya ubah ”HARIINI” menjadi bentuk angka. Menggunakan sistem pengkodean standar ASCII, ”HARIINI” menghasilkan 19d03b412acb5116 atau 7265827332737873 dalam bentuk desimal. Oleh karena P = C = Zn = Z3337 , bagi plaintext menjadi blok berukuran 3 digit: 726 |{z} 582 |{z} 733 |{z} 273 |{z} 787 |{z} 3 |{z} x1
x2
x3
x4
x5
x6
akhirnya hitung y1 y2 y3 y4 y5 y6
= = = = = =
72679 mod 3337 ≡ 215 58279 mod 3337 ≡ 776 73379 mod 3337 ≡ 1743 27379 mod 3337 ≡ 933 78779 mod 3337 ≡ 1731 379 mod 3337 ≡ 158
Untuk proses Dekripsinya, digunakan kunci privat (1019, 3337): x1 x2 x3 x4 x5 x6
= = = = = =
2151019 7761019 17431019 9331019 1711019 1581019
mod 3337 ≡ 726 mod 3337 ≡ 582 mod 3337 ≡ 733 mod 3337 ≡ 273 mod 3337 ≡ 787 mod 3337 ≡ 3
yang apabila dirangkai kembali menghasilkan 7265827332737873, adalah bentuk desimal ”HARI INI”.
23
24
