4.landasan matematika untuk kriptografi xx
-
Upload
universitas-bina-darma-palembang -
Category
Engineering
-
view
365 -
download
7
Transcript of 4.landasan matematika untuk kriptografi xx
Rinaldi Munir/IF5054 Kriptografi 1
Landasan Matematika Untuk Kriptografi
Bahan kuliah ke-3IF5054 Kriptografi
Rinaldi Munir/IF5054 Kriptografi2
Pendahuluan Perlu latar belakang matematika
untuk memahami kriptografi.
Materi matematika yang utama untuk kriptografi adalah matematika diskrit.
Rinaldi Munir/IF5054 Kriptografi3
Materi Matematika untuk Kriptografi:1. Relasi dan Fungsi2. Teori Bilangan
- Integer dan sifat2 pembagian- Algoritma Euclidean- Aritmetika modulo- Bilangan prima
3. Kombinatorial4. Probabilitas dan Statistik
Rinaldi Munir/IF5054 Kriptografi4
5. Kompleksitas algoritma6. Teori informasi7. Aljabar Abstrak (field, ring, group, Galois field)
No. 1 s/d 5 sudah dipelajari di kuliah Matematika Diskrit dan Probabilitas dan Statistik
Nomor 6 dan 7 Tidak akan diulang lagi di dalam kuliah ini
Rinaldi Munir/IF5054 Kriptografi5
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
Rinaldi Munir/IF5054 Kriptografi6
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
Rinaldi Munir/IF5054 Kriptografi7
Secara umum, entropi pesan dihitung dengan rumus:
X = pesanpi = peluang kemunculan simbol ke-i
∑=
−=n
iiii ppXH )(log)( 2
Rinaldi Munir/IF5054 Kriptografi8
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/8 log2(2/8) – 4/8 log2(4/8) – 1/8 log2(1/8) – 1/8 log2 (1/8) = 14/8 = 1,75
Berarti setiap simbol dikodekan sebanyak 1,75 bit
Rinaldi Munir/IF5054 Kriptografi9
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.
Rinaldi Munir/IF5054 Kriptografi10
Medan (Field) Medan adalah himpunan elemen dengan dua
jenis operasi, perkalian dan penjumlahan.
Sebuah medan disebut berhingga (finite field) jika himpunannya memiliki jumlah elemen yang berhingga.
Rinaldi Munir/IF5054 Kriptografi11
Medan Berhingga Fp
Fp adalah adalah himpunan bilangan bulat {0, 1, 2, …, p – 1} dengan p prima dan operasi aritmetika sbb:1. Penjumlahan
Jika a, b ∈ Fp, maka a + b = r
r adalah sisa hasil pembagian a + b dengan p0 ≤ r ≤ p - 1
Rinaldi Munir/IF5054 Kriptografi12
2. PerkalianJika a, b ∈ Fp, maka a × b = s
s adalah sisa hasil pembagian a × b dengan p0 ≤ r ≤ p - 1
Rinaldi Munir/IF5054 Kriptografi13
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)
Rinaldi Munir/IF5054 Kriptografi14
Medan Galois (Galois Field) Medan Galois adalah medan berhingga dengan pn
elemen, p adalah bilangan prima dan n ≥ 1. Notasi: GF(pn) Kasus paling sederhana: bila n = 1 GF(p)
dimana elemen-elemennya dinyatakan di dalam himpunan {0, 1, 2, …, p – 1} dan operasi penjumlahan dan perkalian dilakukan dalam modulus p.
Rinaldi Munir/IF5054 Kriptografi15
GF(2):+ 0 1 × 0 1
0 0 1 0 0 0
1 1 0 1 0 1
GF(3):+ 0 1 2 × 01 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1