*Landasan Matematika Untuk Kriptografi

*PendahuluanPerlu latar belakang matematika untuk memahami kriptografi.Materi matematika yang utama untuk kriptografi adalah matematika diskrit.

*Materi Matematika untuk Kriptografi:Relasi dan FungsiTeori Bilangan- Integer dan sifat2 pembagian- Algoritma Euclidean- Aritmetika modulo- Bilangan primaKombinatorialProbabilitas dan Statistik

*Kompleksitas algoritmaTeori informasiAljabar Abstrak (field, ring, group, Galois field)

FUNGSI SATU ARAHFungsi f dari himpunan A dipetakan ke himpunan B dikatakan fungsi satu arah jika f(x) mudah dihitung untuk semua x A tetapi sangat sukar atau bahkan hampir tidak mungkin (infeasible) secara komputasi menemukan inversinya, yaitu menemukan X sedemikian sehingga f(x) = y untuk semua y jelajah f.*

CONTOH :X = {1,2,3,10} dan f(X) = 3X mod 11, untuk x X.Fungsi perkalian 2 buah bilangan prima yang besar. Contoh : p = 48611 dan q = 53993n = p.q = 2624653723*

FUNGSI PINTU KOLONG (TRAPDOOR ONE WAY FUNCTION)Jika f dari himp. A ke himp. B dikatakan fungsi pintu-kolong (trapdoor function) jika f(x) mudah dihitung untuk semua x A tetapi sangat sukar (infeasible) secara komputasi menemukan inversinya tanpa informasi tambahan yang disebut pintu kolong (trapdoor)*

Jika f adalah fungsi pintu-kolong, maka terdapat informasi rahasia, k, sedemikian sehingga bila diberikan f(x) dan k maka x lebih mudah dihitung.Contoh : pada sistem kriptografi kunci-publik, banyak menggunakan konsep fungsi pintu kolong dan fungsi satu arah.*

*Teori InformasiMendefinisikan 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

*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

*Secara umum, entropi pesan dihitung dengan rumus:

X = pesanpi = peluang kemunculan simbol ke-i

*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

*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.

*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.

*Medan Berhingga FpFp adalah adalah himpunan bilangan bulat {0, 1, 2, , p 1} dengan p prima dan operasi aritmetika sbb:1. PenjumlahanJika a, b Fp, maka a + b = rr adalah sisa hasil pembagian a + b dengan p0 r p - 1

*2. PerkalianJika a, b Fp, maka a b = ss adalah sisa hasil pembagian a b dengan p0 s p - 1

*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)

*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.

*GF(2):+ 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1

GF(3):+ 0 1 2 0 1 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