matematika untuk kriptografi

21
Rinaldi Munir/IF5054 Krip tografi 1 Matematika Untuk Kriptografi Bahan kuliah ke-3 IF5054 Kriptografi

Upload: turner

Post on 05-Jan-2016

120 views

Category:

Documents


6 download

DESCRIPTION

Matematika Untuk Kriptografi. Bahan kuliah ke-3 IF5054 Kriptografi. Pendahuluan. Perlu latar belakang matematika untuk memahami kriptografi. Materi matematika yang utama untuk kriptografi adalah matematika diskrit.. Materi Matematika untuk Kriptorafi:. Teori Bilangan - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

1

Matematika Untuk Kriptografi

Bahan kuliah ke-3IF5054 Kriptografi

Page 2: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

2

Pendahuluan Perlu latar belakang matematika

untuk memahami kriptografi.

Materi matematika yang utama untuk kriptografi adalah matematika diskrit.

Page 3: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

3

Materi Matematika untuk Kriptorafi:

1. Teori Bilangan- Integer dan sifat2 pembagian- Algoritma Euclidean- Aritmetika modulo- Bilangan prima

2. Probabilitas dan Statistik

Page 4: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

4

3. Kompleksitas algoritma4. Teori informasi5. Medan berhingga (finite field)

No. 1 s/d 3 sudah dipelajari di kuliah Matematika Diskrit dan Probabilitas dan Statistik

Page 5: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

5

Teori Informasi Mendefinisikan jumlah informasi di dalam

pesan sebagai jumlah minimum bit yang dibutuhkan untuk mengkodekan pesan.

Contoh: - 1 bit untuk mengkodekan jenis kelamin- 3 bit untuk mengkodekan nama hari- 4 bit untuk mengkodekan 0 s/d 9

Page 6: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

6

Entropy:ukuran yang menyatakan jumlah informasi di dalam pesan.

Biasanya dinyatakan dalam satuan bit. Entropi berguna untuk memperkirakan

jumlah bit rata-rata untuk mengkodekan elemen dari pesan.

Contoh: entropi untuk pesan yang menyatakan jenis kelamin = 1 bit, entropi untuk pesan yang menyatakan nama hari = 3 bit

Page 7: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

7

Secara umum, entropi pesan dihitung dengan rumus:

X = pesanSi = simbol ke-i di dalam pesan

p(Si) = peluang kemunculan Si

ai = jumlah kemunculan Si

n

iiiiSpaXH ))(log()( 2

Page 8: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

8

Contoh: pesan X = ‘AABBCBDB’ n = 4 (A, B, C, D) p(A) = 2/8, p(B) = 4/8 p(C) = 1/8, p(D) = 1/8

H(x) = -2 2log(2/8) - 4 2log(4/8) -1 2log(1/8) - 1 2log(1/8)

= 4 + 4 + 3 + 3 = 14 bit

Entropi rata-rata = 14/4 = 1,75 bit per simbol

Page 9: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

9

Entropi juga menyatakan ketidaktentuan (uncertainty) dari pesan.

Contoh: kriptogram “Y6RuPZ” menyatakan plainteks “MALE” atau “FEMALE”, maka uncertainty pesan = 1.

Kriptanalis harus mempelajari hanya 1 bit yang dipilih secara tepat untuk menemukan plainteks.

Page 10: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

10

Entropi sistem kriptografi adalah ukuran ruang kunci, K.

Misal, sistem kriptografi dengan kunci 64-bit mempunyai entropi 64 bit.

Makin besar entropi, makin sulit memecahkan cipherteks.

Page 11: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

11

Laju bahasa (rate of a language):r = H(X)/N

N = panjang pesan

Laju normal Bahasa Inggris: 1.0 bit/huruf s/d 1.5 bit/huruf untuk N besar.

Page 12: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

12

Laju mutlak (absolute rate):R = 2log L

L = jumlah karakter di dalam bahasa

Dalam Bahasa Inggris (26 huruf):R = 2log 26 = 4.7 bit/huruf

Page 13: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

13

Redundansi bahasa (D):D = R – r

Pada Bahasa Inggris (r = 1.3): D = 4.7 – 1.3 = 3.4 bit/huruf

artinya setiap huruf dalam Bahasa Inggris membawa 3.4 bit informasi redundan (mubazir)

Page 14: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

14

Pada pesan ASCII (256 karakter):

R = 2log 256 = 8r = 1.3 (sama seperti B. Inggris)

D = 8 – 1.3 = 6.7 bit/karakter

Page 15: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

15

Kriptanalis menggunakan redundansi alami dari bahasa untuk mengurangi kemungkinan jumlah plainteks.

Contoh: kata “dan” dalam B. Indonesia redundan. Misalnya jika di dalam cipherteks banyak muncul kriptogram “ftY” (3 huruf) maka kemungkinan besar itu adalah “dan”.

Makin besar redundansi bahasa, makin mudah melakukan kriptanalisis.

Page 16: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

16

Dalam dunia-nyata, implementasi kriptografi dilengkapi dengan program kompresi sebelum mengenkripsi pesan.

Kompresi mengurangi redundansi pesan.

Page 17: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

17

Medan (Field) Medan adalah himpunan elemen

dengan dua jenia operasi, perkalian dan penjumlahan.

Sebuah medan disebut berhingga (finite field) jika himpunannya memiliki jumlah elemen yang berhingga.

Page 18: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

18

Medan Berhingga Fp

Fp adalah adalah himpunan bilangan bulat {0, 1, 2, …, p – 1} dengan p prima dan operas aritmetika sbb:1. Penjumlahan

Jika a, b Fp, maka a + b = rr adalah sisa hasil pembagian a + b dengan p0 r p - 1

Page 19: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

19

2. PerkalianJika a, b Fp, maka a b = s

s adalah sisa hasil pembagian a b dengan p0 r p - 1

Page 20: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

20

Contoh: F23 mempunyai anggota

{0, 1, 2, …, 22}. Contoh operasi aritmetika:12 + 20 = 9 (karena 32 mod 23 = 9)8 9 = 3 (karena 72 mod 23 = 3)

Page 21: Matematika Untuk Kriptografi

Rinaldi Munir/IF5054 Kriptografi

21

Medan Galois (Galois Field) Medan Galois adalah medan

berhingga dengan pn elemen, p adalah bilangan prima.

Notasi: GF(p) Artinya: Medan Galois berorde p