Enkripsi Kunci Simetrik
Kriptografi dan Sistem Keamanan Komputer Standar Sistem Keamanan Enkripsi Kunci Simetrik Number Theory Enkripsi Kunci Publik Autentikasi Pesan dan Fungsi Hash
2011-2012-3
Anung Ariwibowo
2
Konvensional / Private-key / Single-key Pengirim dan Penerima berbagi kunci enkripsi Basis dari semua penyandian klasik Penyandian yang dikenal sebelum 1970an Paling banyak digunakan
2011-2012-3
Anung Ariwibowo
3
plaintext – pesan asli ciphertext – pesan terenkripsi / tersandikan cipher – algoritma untuk mengubah plaintext ke ciphertext, algoritma penyandian key – informasi yang digunakan oleh algoritma penyandian, diketahui oleh pengirim dan penerima encipher (encrypt) – mengubah plaintext ke ciphertext decipher (decrypt) – mengembalikan plaintext dari ciphertext
2011-2012-3
Anung Ariwibowo
4
cryptography – ilmu tentang metode-metode dan prinsip-prinsip enkripsi cryptanalysis (codebreaking) – ilmu tentang prinsip-prinsip untuk men-decipher cihpertext tanpa keberadaan key cryptology – bidang ilmu yang mencakup cryptography dan cryptanalysis
2011-2012-3
Anung Ariwibowo
5
Syarat yang diperlukan untuk penggunaan enkripsi simetrik yang aman Algoritma enkripsi yang 'kuat' Kunci hanya diketahui oleh sender / receiver
Notasi matematis Y = EK(X) X = DK(Y)
Asumsi
Algoritma enkripsi diketahui ada secure channel untuk mendistribusikan key
Sistem kriptografi dibedakan berdasarkan beberapa hal
Tipe operasi yang digunakan substitution / transposition / product
Jumlah kunci yang digunakan single-key or private / two-key or public
Bagaimana plaintext diolah menjadi ciphertext block / stream
Membongkar key dan pesan asli Teknik yang digunakan
cryptanalytic attack brute-force attack
ciphertext
known plaintext
select plaintext and obtain ciphertext
chosen ciphertext
know/suspect plaintext & ciphertext
chosen plaintext
algoritma & ciphertext diketahui, pendekatan statistik, mengidentifikasi plaintext
select ciphertext and obtain plaintext
chosen text
select plaintext or ciphertext to en/decrypt
unconditional security
seberapa pun sumber daya komputasi dan waktu yang tersedia, sandi tidak dapat dipecahkan. Ciphertext tidak cukup menyediakan informasi untuk secara unik menentukan plaintext yang sesuai.
computational security
diberikan sumber daya komputasi yang terbatas, sandi tidak dapati dipecahkan (misal: waktu yang digunakan untuk menjalankan algoritma lebih besar daripada umur alam semesta)
Mencoba setiap kemungkinan key serangan paling dasar proporsional dengan ukuran key asumsinya plaintext diketahui / dikenal
Key Size (bits)
Number of Alternative Keys
Time required at 1 decryption/µs
Time required at 106 decryptions/µs
32
232 = 4.3 109
231 µs
= 35.8 minutes
2.15 milliseconds
56
256 = 7.2 1016
255 µs
= 1142 years
10.01 hours
128
2128 = 3.4 1038
2127 µs
= 5.4 1024 years
5.4 1018 years
168
2168 = 3.7 1050
2167 µs
= 5.9 1036 years
5.9 1030 years
26! = 4 1026
2 1026 µs = 6.4 1012 years
26 characters (permutation)
6.4 106 years
Simbol Huruf Angka Tanda baca
Simbol-simbol plaintext digantikan oleh simbol-simbol lain Sebagai rangkaian bit, substitution mengganti pola bit plaintext dengan pola bit ciphertext
Sandi substitusi yang paling awal dikenal dalam sejarah Pertama kali digunakan untuk merahasiakan pesan militer Substitusi huruf dengan huruf ke-3 berikutnya
2011-2012-3
meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB
Anung Ariwibowo
14
Transformasi didefinisikan sebagai pemetaan a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Secara matematis memberikan nilai kepada masing-masing huruf a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Secara matematis sandi Caesar didefinisikan sebagai fungsi pemetaan c = E(p) = (p + k) mod (26) p = D(c) = (c – k) mod (26)
Hanya ada 26 kemungkinan sandi Brute force search Diberikan ciphertext, coba semua kemungkinan shifts Plaintext harus bisa dikenali
GCUA VQ DTGCM CVBG HSSLG CVBZ
1 2 3 4 5 6 7 8 9 10 11 12 13
CVBG BUAF ATZE ZSYD YRXC XQWB WPVA VOUZ UNTY TMSX SLRW RKQV QJPU PIOT
2011-2012-3
HSSLG GRRKF FQQJE EPPID DOOHC CNNGB BMMFA ALLEZ ZKKDY YJJCX XIIBW WHHAV VGGZU UFFYT
CVBZ BUAY ATZX ZSYW YRXV XQWU WPVT VOUS UNTR TMSQ SLRP RKQO QJPN PIOM
14 15 16 17 18 19 20 21 22 23 24 25
CVBG OHNS NGMR MFLQ LEKP KDJO JCIN IBHM HAGL GZFK FYEJ EXDI DWCH
HSSLG TEEXS SDDWR RCCVQ QBBUP PAATO OZZSN NYYRM MXXQL LWWPK KVVOJ JUUNI ITTMH
Anung Ariwibowo
CVBZ OHNL NGMK MFLJ LEKI KDJH JCIG IBHF HAGE GZFD FYEC EXDB DWCA
17
Setiap huruf plaintext dipetakan ke huruf ciphertext secara acak Panjang key 26 huruf abcdefghijklmnopqrstuvwxyz DKVQFIBJWPESCXHTMYAUOLRGZN ifwewishtoreplaceletters WIRFRWAJUHYFTSDVFSFUUFYA
Total kemungkinan key
26! 4 x 1026
with so many keys, might think is secure language characteristics
human languages bersifat redundant
Dalam bahasa Inggris huruf E paling banyak digunakan
"th lrd s m shphrd shll nt wnt"
T,R,N,I,O,A,S Z,J,K,Q,X cukup jarang digunakan
Tabel frekuensi huruf untuk berbagai bahasa single, double & triple letter frequencies
Substitusi monoalphabetic tidak mengubah frekuensi relatif huruf dalam bahasa yang digunakan Arabian scientists in 9th century Hitung frekuensi huruf dalam ciphertext Sandi monoalphabetic harus mengidentifikasi setiap huruf
Tabel frekuensi double/triple letters dapat membantu memecahkan sandi
Diberikan ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
Hitung frekuensi relatif huruf Single letters
P dan Z dipetakan ke e atau t
Double letters
ZW dipetakan ke th ZWP = the
proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow
2011-2012-3
Anung Ariwibowo
24
Jumlah kombinasi key tidak menjamin keamanan sandi Monoalphabetic Sandikan multiple letters Contohnya Playfair Cipher
Charles Wheatstone in 1854 named after his friend Baron Playfair
Matriks huruf 5X5 berdasarkan sebuah katakunci Kata-kunci tidak mengandung huruf duplikat Isi matriks sisanya dengan huruf yang lain
keyword MONARCHY M
O
N
A
R
C
H
Y
B
D
E
F
G
I/J
K
L
P
Q
S
T
U
V
W
X
Z
plaintext is encrypted two letters at a time 1. 2. 3.
4.
if a pair is a repeated letter, insert filler like 'X’ if both letters fall in the same row, replace each with letter to right (wrapping back to start from end) if both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom) otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the pair
26 x 26 = 676 digrams Membutuhkan tabel frekuensi dengan 676 entri Lebih banyak kemungkinan ciphertext Banyak digunakan bertahun-tahun
US & British military in WW1
it can be broken, given a few hundred letters
Statistics don't lie
improve security using multiple cipher alphabets make cryptanalysis harder with more alphabets to guess and flatter frequency distribution use a key to select which alphabet is used for each letter of the message use each alphabet in turn repeat from start after end of key is reached
simplest polyalphabetic substitution cipher effectively multiple caesar ciphers key is multiple letters long K = k1 k2 ... kd ith letter specifies ith alphabet to use use each alphabet in turn repeat from start after d letters in message decryption simply works in reverse
write the plaintext out write the keyword repeated above it use each key letter as a caesar cipher key encrypt the corresponding plaintext letter eg using keyword deceptive key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
have multiple ciphertext letters for each plaintext letter hence letter frequencies are obscured but not totally lost start with letter frequencies
see if look monoalphabetic or not
if not, then need to determine number of alphabets, since then can attach each
Mencari solusi dalam ruang masalah yang besar
Problem space
Traveling Salesman Problem
2011-2012-3
Diberikan n kota Cari rute terpendek yang mengunjungi setiap kota tepat satu kali Problem space: n! O(n!)
Anung Ariwibowo
33
Quiz:
2011-2012-3
1000 kombinasi kota per detik 10 kota
Anung Ariwibowo
34
Stallings, "Cryptography and Network Security"http://williamstallings.com/Cryptography/ Schneier, "Applied Cryptography" http://www.schneier.com/book-applied.html Thomas L Noack, http://ece.uprm.edu/~noack/crypto/ Slides tjerdastangkas.blogspot.com/search/label/ikh323
2011-2012-3
Anung Ariwibowo
35
