Kriptografi Kuliah 4 Computer Security n n n n
Kriptografi Terminology Secret-Key Encryption Public-Key Encryption
Direkomendasi u/ membaca n
Beberapa sumber a.l : ¨
U.S. Senate hearings on Internet Security: B. Schenier http://www.senate.gov/~commerce/hearings/071601Schneier.pdf ¨ Crypto-Gram Newsletters http://www.counterpane.com/cryptogram.html ¨ Security Focus Online, cryptanalysis tools http://online.securityfocus.com/tools/category/54
Computer security-
Eko AB-UAD
2
Software Kriptografi Crypt pembanding : http://wombat.doc.ic.ac.uk/foldoc/foldoc.cg i?Crypt+Breakers+Workbench n PGP, http://web.mit.edu/network/pgp.html n Crypto dan Security http://www.programmersheaven.com/zone 16/cat731/index.htm
n
Computer security-
Eko AB-UAD
3
Amankah komunikasi kita? Pengintai/ Penyadap Confidential
Tidak ada jaminan jalur komunikasi aman Recipient
Sender
Computer security-
Eko AB-UAD
4
Cryptographic Protocols § § § § § §
Messages should be transmitted to destination Only the recipient should see it Only the recipient should get it Proof of the sender’s identity Message shouldn’t be corrupted in transit Message should be sent/received once only
Computer security-
Eko AB-UAD
5
Terminologi Cryptography adalah “crypto” yaitu rahasia dan “graphy” adalah tulisan n tulisan yang bersifat rahasia n sbg ilmu dan seni untuk menjaga pesan agar tetap aman n Proses dalam Crypto : Enkripsi dan Dekripsi n
Computer security-
Eko AB-UAD
6
Terminologi § Plaintext (cleartext): pesan dalam format asli / mudah dipahami § Ciphertext (cyphertext): pesan yg sudah dienkripsikan § Encryption: transformasi pesan (plaintext) ke kode yg tidak dapat(sulit) dimengerti § Cipher: algoritma kriptografi. Fungsi matematik yg digunakan untuk meng-enkripsi dan mendekripsi. Computer security-
Eko AB-UAD
7
Lanjt §Decryption (decode) : mengubah ciphertext menjadi pesan asli. Proses Encryption dan Decryption butuh key yang sesuai hasil dari cipher
§Cryptanalysis (Code breaking): kegiatan untuk mengubah ciphertext menjadi pesan aslinya tanpa mengetahui kunci yang sesuai. Dengan cara coba-coba (trial and error).
§Cryptology: Ilmu yang mempelajari crypthography dan Cryptanalysis Computer security-
Eko AB-UAD
8
Enkripsi dan Dekripsi
Plaintext
Computer security-
Enkripsi
Ciphertext
Eko AB-UAD
Dekripsi
Plaintext
9
Kriptosistem Konvensional (Kunci simetrik ) Plaintext
Ciphertext Enkripsi
Plaintext Dekripsi
Pengirim
Penerima Kunci
Ciphertext=E(K,M) Message =D(K,C)
Computer security-
Kunci perlu ditransfer secara aman
Eko AB-UAD
10
Kriptosistem Public Key Kunci umum (Kpub) (dari penerima)
Plaintext
Ciphertext Enskripsi
Plaintext Dekripsi
Pengirim
Penerima
C=E(Kpub,M) M=D(Kpriv,C) Computer security-
Kunci private (Kpriv)
Kpub dapat dilihat / diketahui siapa saja Eko AB-UAD
11
Kripanalisis Tujuan kripanalisis ¨ Mengungkap/memecahkan
pesan ¨ Mengungkap/memecahkan kunci ¨ Memecahkan / mencari celah algoritma kriptografi ¨ Mengungkap unjuk kerja algoritma kriptografi ¨ Pembandingan suatu algoritma kriptografi dgn algoritma krisptografi lain
Computer security-
Eko AB-UAD
12
Breakable vs Practically breakable n Unconditionally secure: impossible to decrypt. No amount of ciphertext will enable a cryptanalyst to obtain the plaintext n Computationally secure: an algorithm that is not breakable in practice based on worst case scenario n Breakable: all algorithms (except one-time pad) are theoretically breakable
Computer security-
Eko AB-UAD
13
What makes a good cryptosystem? § A good cryptosystem is one whose security does not depend upon the secrecy of the algorithm. § From Bruce Schneier: § “Good cryptographers rely on peer review to separate the good algorithms from the bad.''
Computer security-
Eko AB-UAD
14
Kriptosistem Konvensional (Kunci simetrik ) Plaintext
Ciphertext
Plaintext Dekripsi
Enkripsi
Pengirim
Penerima Kunci
Ciphertext=E(K,M) Message =D(K,C)
Computer security-
Kunci perlu ditransfer secara aman
Eko AB-UAD
15
Secret Key Cryptosystem Vulnerabilities (1) Passive Attacker (Eavesdropper) n Obtain and/or guess key and cryptosystem use these to decrypt messages n Capture text in transit and try a ciphertextonly attack to obtain plaintext.
Computer security-
Eko AB-UAD
16
Secret Key Cryptosystem Vulnerabilities (2) Active Attacker n Break communication channel (denial of service) n Obtain and/or guess key and cryptosystem and use these to send fake messages
Computer security-
Eko AB-UAD
17
Kelemahan yg melekat pd Kriptografi kunci simetrik § Pendistribusian Kunci harus dilakukan secara aman § §
(terlebih jika kelompok secara geografi jauh atau satu sama lain tidak kenal) Dibutuhkan kunci untuk setiap pasangan user § n users membutuhkan n*(n-1)/2 kunci Jika kunci (dan kriptosistem) is compromised, the adversary will be able to decrypt all traffic and produce fake messages
Computer security-
Eko AB-UAD
18
Teknik Enkripsi dasar n n n
Substitution / substitusi : suatu karakter diganti dgn karakter lain Permutation / Transposition : penukaran posisi karakter dalam plaintext Combinations : gabungan antara kedua metode
Computer security-
Eko AB-UAD
19
Caesar cipher n
C=E(K,M), e.g., C=(M+n) mod 26 plaintext : ABCDE… ciphertext : ABC DEF… e.g., M=CAB C =FDE
Kelebihan: mudah diimplementasikan n Kekurangan : mudah dipecahkan n
Computer security-
Eko AB-UAD
20
Security Tradeoff Security
Functionality COST
Ease of Use Computer security-
Eko AB-UAD
21
Kasus Public Key ALGORITMA RSA Pertemuan ke 5 Mata Kuliah : Security Komputer Teknik Informatika UAD Eko AB-Teknik Informatika
Asal Mula • tahun 70-an Whitfield Diffie dan Martin Hellman menemukan teknik enkripsi asimetrik yang merevolusi dunia kriptografi • tahun 1977 tiga orang peneliti, yaitu R.L. Rivest, A. Shamir, dan L. Adleman, menemukan RSA • RIVEST-SHAMIR-ADLEMAN
Eko AB-Teknik Informatika
Apa Itu RSA ? • Merupakan salah satu teknik kripto, dimana kunci untuk meng-enkrip dan untuk –mendekrip berbeda • Contoh metode lain : ElGamal, Rabin, Elliptic Curve Cryptosistem (ECC), DiffieHelman, LUC
Eko AB-Teknik Informatika
Apa itu RSA ? • Orang yang mempunyai kunci publik dpt meng-enkripsi tapi yang dapat men-dekripsi cuma yang th kunci privat • Kuci publik dpt dimiliki oleh sembarang orang,tapi kunci privat cuma orang tertentu atau bahkan hanya seorang.
Eko AB-Teknik Informatika
Dasarnya? • Algoritma ini dibuat berdasarkan fakta bahwa dalam perhitungan dengan komputer, untuk menemukan suatu bilangan prima yang besar sangat mudah, namun untuk mencari faktor dari perkalian dua bilangan prima yang besar sangat sulit, bahkan hampir tidak mungkin.
Eko AB-Teknik Informatika
Prosesnya ? Pengirim
Menerima kunci Publik
Meng-enkrispi Plaintek dengan kunci publik
Mengirimkan cipherteks
Penerima
Membangkitkan kunci publik dan kunci privat
Mengirimkan kunci Publik
Mendekripsi Cipherteks dengan kunci provat
Eko AB-Teknik Informatika
Algoritmanya? Proses enkripsi : C = Me mod n Proses dekripsi : M = Cd mod n Dimana : M : bilangan integer yang merepresentasikan pesan C : bilangan integer yang merepresentasikan pesan tersandi e : kunci enkripsi (publik) d : kunci dekripsi (pribadi) n : modulus (publik)
Bilangan e dan n adalah kunci publik yg dapat diketahui umum Eko AB-Teknik Informatika
M dan C berupa Integer ? • Bila seorang pengguna A ingin mengirimkan pesan rahasia ke seorang pengguna B yang memiliki suatu sistem kriptografi RSA, langkah pertama yang harus dilakukan oleh pengguna A adalah merepresentasikan pesannya (yang biasanya berupa teks) dalam bentuk deretan bilangan integer nonnegatif dalam suatu basis tertentu. Konversi pesan teks ke bentuk deretan bilangan integer ini dapat dilakukan menggunakan berbagai teknik, pada umumnya adalah standar ASCII 8-bit atau yang lainnya Eko AB-Teknik Informatika
Menghitung Nilai e, d, dan n : 1. ambil secara random dua bilangan prima p dan q yang besar dan berbeda, namun ukuran keduanya (jumlah digitnya dalam basis bilangan yang dipergunakan) haruslah sama. 2. Hitung modulus n dan fungsi Euler’s Totient ф(n) : 3. n = p.q , 4. Ф(n) = (p-1)(q-1) 5. Pilih suatu bilangan integer e dimana : 6. 1 < e < ф(n) dan gcd (e, ф(n)) = 1 7. Hitung nilai integer d dimana 1 < d < ф(n) sedemikian hingga : 8. d = e-1 mod ф(n) atau e.d = 1 (mod ф (n)) 9. dengan menggunakan algoritma Euclidean yang diperluas 10.Public-key dari sistem ini adalah n dan e, sedangkan privatekey-nya adalah d Eko AB-Teknik Informatika
Kondisi Enkripsi Ada kondisi yang harus dipenuhi dalam proses Enkripsi : (C = Me mod n ) • Bilangan e harus lebih kecil dari n, demikian juga bilangan M harus lebih kecil dari n • Bilangan M harus lebih kecil dari n untuk menjamin terjadinya trasformasi satu-satu dengan domain dan range yang identik Eko AB-Teknik Informatika
Verifikasi ? Setelah menerima pesan tersandi C, penerima Cipherteks kemudian mendapatkan kembali pesan M semuila dengan melakukan penghitungan : M’ = Cd mod n Proses dekripsi ini dapat diverifikasi sebagia berikut : • M’ = (Me mod n)d mod n • M’ = Med mod n Karena e.d = k. Ф(n) +1 untuk suatu integer k tertentu : • M’ = Mk(Ф(n) +1) mod n • M’ = (M Ф(n))k. M mod n Jika gcd(Ф(n),n) = 1, maka teorema Eulier menjamin bahwa M’=M, Eko AB-Teknik Informatika
Contoh Membangkitkan Kunci • • • • •
• •
Membuat 2 bilangan prima lebar p dan q, dimana p ≠ q. Misalnya p = 17 dan q = 11 Hitung n = pq = 17 x 11 = 187 Hitung ф(n) = (p - 1)(q - 1) = (17-1)x(11-1) = 16 x 10 = 160 Menentukan bilangan terkecil e yang merupakan coprime ф(n) = 160, dengan syarat gcd (e, ф(n)) = 1, dimana 1 < e < ф(n), misalnya e = 7 Menghitung d = e-1 mod ф(n) dimana d * 7 = 1 mod 160 dan d < 160. Harga yang benar adalah d = 23 karena 23 x 7 = 161 = 1 x 160 + 1, d dapat dihitung menggunakan euclid’s algorithm Dari hasil perhitungan diatas didapatkan bahwa kunci publik (KU = {7, 187}), dimana e = 7 dan modulus n =187 Sedangkan kunci privat (KR = {23, 187}), dimana d = 23 dan n =187. Eko AB-Teknik Informatika
Contoh • Akan dienkripsikan planteks huruf “X” • Maka huruf ini kita konversikan lebih dulu ke suatu nilai integer, misalnya kode ASCI-nya berarti 88
Eko AB-Teknik Informatika
• Sebagai contoh yang menunjukkan penggunaan kunci ini pada pemasukan plaintext untuk M = 88 Encryption 88 Plaintext
88
7
Decryption
mod 187 = 11
11 Ciphertex t
KU = 7 , 187
11
23
mod 187 = 88
KR = 23, 187
Eko AB-Teknik Informatika
88 Plaintext
Enkripsinya ? • Untuk enkripsi, dapat dihitung dengan syarat plaintext M < n, dan • ciphertext C = Me (mod n), dimana C = 887 mod 187. • 887 mod 187 = ((884 mod 187) x (882 mod 187) x (881 mod 187)) mod 187 • 881 mod 187 = 88 • 882 mod 187 = 7744 mod 187 = 77 • 884 mod 187 = 59.969.536 mod 187 = 132 • 887 mod 187 = (88 x 77 x 132) mod 187 = 894.432 mod 187 = 11 Eko AB-Teknik Informatika
Dekripsinya? • Dekripsi dapat dihitung dengan ciphertext C, dan plaintext M = Cd (mod n), dimana M = 1123 mod 187 • 1123 mod 187 = ((111 mod 187) x (112 mod 187) x (114 mod 187) x • (118 mod 187) x (118 mod 187)) mod 187 • 111 mod 187 = 11 • 112 mod 187 = 121 • 114 mod 187 = 14.641 mod 187 = 55 • 118 mod 187 = 214.358.881 mod 187 = 33 • 1123 mod 187 = (11 x 121 x 55 x 33 x 33) mod 187 • = 79.720.245 mod 187 = 88 • Proses ini akan menghasilkan pesan plaintext semula. Eko AB-Teknik Informatika
