Materials prepared by WP

Sekuriti Digital, Teori dan Praktek

Administrasi Kuliah

2

Materials prepared by WP

Tim Pengajar & Text Book

• Tim pengajar– Nursalim Hadi (dosen)

– Wishnu Prasetya (dosen)

– Yova (asisten)

– Pembicara tamu (?)

• 14 x kuliah– tugas paper, tugas pemrograman, mid-test, final test

• Informasi ttg kuliah lihat di http://www.cs.ui.ac.id/staf/wishnu.html

– Lihat juga info tambahan ttg topik-topik sekuriti di page tsb.

• Buku: Bruce Schneier, Applied Cryptography, Wiley. Secepatnya!

3

Materials prepared by WP

Sub-topik Kuliah, Bagian Teori

• Analisa Algoritme • Sistem Sandi Sederhana• Protokol Kriptografis• Sistem Sandi RSA• Serangan Kriptografis• Generator Random dan Test Keprimaan• Protokol Uang Elektronis Anonim

Materials prepared by WP

T1 : Sistem-sistem Enkripsi Sederhana

5

Materials prepared by WP

Mengapa Mempelajari Sistem Sandi Sederhana?

• Sejarah

• Mudah dipelajari dan mewakili konsep2 yang cukup penting dalam tehnik penyandian.

• Walaupun lemah tapi ternyata masih digunakan oleh software2 modern. Contoh: wordperfect.

6

Materials prepared by WP

Caesar Systemdigunakan bangsa Romawi jaman Julius Caesar, 300 BC(?)

• Untuk melakukan enkripsi, teks asli (plain text) m, setiap huruf x di m diganti dengan x' yang diperoleh dengan men-shift x ke kanan k-kali (siklis modulo 26) dalam alphabet.

• Hasil enkripsi disebut teks sandi (chiper text).• k disebut kunci.

• Contoh :– teks asli "you lose"

– kunci k = 3

– teks sandi : "brx orvh"

7

Materials prepared by WP

Algoritme Caesar

caesar::Int->String->Stringcaesar k [] = []caesar k (a:s) = a': caesar k s where a' = chr(((ord a) + k) mod 128)

deCaesar::Int->String->StringdeCaesar k [] = [] deCaesar k (a:s) = a': deCaesar k s where a' = chr(((ord a) + 128 - k) mod 128)

8

Materials prepared by WP

Generalisasi dari Caesar System

Kunci k yang mengatakan jarak shift dalam sistem Caesar diganti dengan fungsi f (yang ivertibel dengan invers g) yang melakukan substitusi huruf, bergantung pada posisi huruf dalam pesan asli.

Contoh: f0 dan inversnya g0

f0 a k = chr(((ord a) + (k mod 7)*13) mod 128)g0 a k = chr(((ord a) + 128 - (k mod 7)*13) mod 128)

genCaesar::(Char->Int->Char)->String->StringgenCaesar f s = gC f 0 s where gC f j [] = [] gC f j (a:s) = (f a j): gC f (j+1) s

9

Materials prepared by WP

Menyandi Karakter dengan String

Fungsi genCaesar bisa digeneralisasi lebih lanjut dengan mengijinkan huruf untuk disandi dengan satu atau lebih deret huruf (string). Fungsi f yang digunakan sebagai kunci harus invertibel.

genCaesar2::(Char->Int->String)->String->StringgenCaesar2 f s = gC f 0 s where gC f j [] = [] gC f j (a:s) = (f a j) ++ (gC f (j+1) s)

10

Materials prepared by WP

Mesin Rotor / Enigma

type Rotor = Char->Char

rotor1 = some permutation on ASCII symbolsrotor2 = …rotor3 = …

rotor a k = r3 (r2 (r1 a k) k) k where r1 b j = rotor1 (chr(((ord a)+(k div speed1)) mod 128)) r2 b j = rotor2 (chr(((ord a)+(k div speed2)) mod 128)) r3 b j = rotor3 (chr(((ord a)+(k div speed3)) mod 128)) speed1 = 1 speed2 = 7 speed3 = 17

rotorCrypt s = genCaesar rotor s

11

Materials prepared by WP

Mesin Sandi Sempurna : One Time PadJoseph Mauborgne & Gilbert Vernam (1917)

• Dalam sistem One Time Pad, kunci untuk enkripsi sama panjangnya dengan teks asli, dan merupakan deret dari substitusi huruf secara random. Huruf ke j dari teks asli disubtitusi menurut substitusi ke j dari kunci.

• Sifat : no periodicity, so absolutely impossible to break.

• Digunakan oleh kalangan militer :– hot-line US - Soviet

– Soviet spies

12

Materials prepared by WP

Substitution Chiper

• Setiap huruf di teks asli disubstitusi dengan huruf sandi.

• Dekripsi dilakukan dengan melakukan substitusi balik. Jadi, substitusi harus injektif.

• Bisa digeneralisasi sebagai berikut:– substitusi dilakukan per blok teks asli

– substitusi blok tidak harus menghasilkan blok yang konsisten besarnya

– substitusi cukup secara probabilistis sangat injektif.

13

Materials prepared by WP

Klasifikasi Sistem Sandi Substitusi

• Substitusi sederhana/monoalphabetis– tiap huruf diganti dengan satu huruf sandi

– contoh : sistem Caesar

• Substitusi homophonis– tiap huruf bisa memiliki lebih dari satu huruf sandi

– contoh : genCaesar

• Substitusi poligram– tiap blok teks asli diganti dengan blok sandi– contoh : DES

• Substitusi polialphabetis– kombinasi beberapa substitusi sederhana. Penerapannya bergantung posisi

huruf dalam teks asli– contoh : mesin rotor

Materials prepared by WP

T2 : Analisa Algoritme

15

Materials prepared by WP

Analisa Algoritme

• Ditujukan untuk memperkirakan kebutuhan waktu (ruang) relatif sebuah algoritme. Pengertian ‘relatif’ adalah: tidak bergantung pada platform/mesin.

• Untuk melakukan analisa kekuatan sebuah sistem sandi, kita meninjau berbagai cara untuk membongkar sandi tersebut. Apabila ada strategi pembongkaran yang efesien, maka sistem sandi tersebut lemah dan tidak layak digunakan. Untuk menentukan seberapa efesiennya sebuah strategi pembongkaran, orang menggunakan tehnik analisa algoritme.

16

Materials prepared by WP

Notasi O untuk Menyatakan Efesiensi Program

Definisi :Untuk fungsi f,g : Nat Float

f O(g) = ( n0,K: 0<n0,K : ( n : n0 n : f n K.(g n))

f O(g) diartikan “untuk n besar, naik turunnya f dibatasi diatas oleh kelipatan konstan dari g”.

Taksiran kebutuhan waktu relatif sebuah program P bisa dinyatakan sebagai sebuah fungsi f : Nat Float, dimana f(n) adalah kebutuhan waktu P untuk memproses input berukuran n.

17

Materials prepared by WP

Running Time dari berbagai kelas algoritme

Kelas Efesiensi #operasi untuk waktu eksekusi n = 106 kecepatan 1 MIPS

Konstan O(1) 1 1 usecLinier O(n) 106 1 secKwadratis O(n2) 1012 11.6 hariKubis O(n3) 1018 32,000 tahunEksponensial O(2n) 10310030 10310006 kali

umur alamsemesta

18

Materials prepared by WP

Kelas Problem P dan NP

• Problem kelas P : problem yang bisa dipecahkan dengan algoritme dengan efesiensi polinomial.

• Problem kelas NP : problem yang bisa dipecahkan dengan algoritme dengan efesien polinomial, tetapi menggunakan mesin (Turing) non-deterministis (ie mesin dengan unlimited parallelism)

• Tidak diketahui apakah kelas P= kelas NP

• Kelas NP-complete terdiri dari problem2 yang bisa dibuktikan sama sulitnya (dari kebutuhan komputasi) untuk dipecahkan. Jadi, bila satu problem dr. kelas NP-complete ditemukan solusi polinomialnya, maka seluruh problem dari kelas itu bisa dipecahkan dengan efesiensi polinomial.

• Masih ada lagi kelas problem yang undecidable, artinya tidak bisa dihitung solusinya menggunakan algoritme apapun juga.

19

Materials prepared by WP

Beberapa Problem dari Kelas NP-complete

• Menentukan sembarang jaringan G dan H adalah isomorfis• Travelling salesman problem• Hamiltonian cycle• Satisfiability in proposition logic