Noor Hafidz (7.2.1 & 7.2
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Noor Hafidz (7.2.1 & 7.2 as PDF for free.
More details
- Words: 467
- Pages: 3
Perfect Secrecy Noor Hafidz, NPM: 0302100573, Tk. III Teknik Kripto
Definisi Perfect Secrecy dan Konsekuensinya Suatu sistem penyandian dikatakan perfect atau memenuhi perfect secrecy, jika dan hanya jika mutual information dari teks terang M dan pesan yang terenkripsinya C bernilai nol: I(C; M) = 0.
Teorema 1 Dalam suatu sistem penyandian perfect, jumlah kunci yang mungkin paling tidak adalah sama dengan jumlah pesannya. BUKTI I(C; M) = 0 mengakibatkan bahwa untuk setiap m, P(C|M = m) = P(C). Sekarang ambil sebuah kriptogram yang mungkin yaitu sebuah pesan yang terenkripsi c sedemikian hingga P(C = c)= 0. Maka untuk setiap pesan asli yang mungkin m, kita dapati P(C = c|M = m) ≠ 0 yang berarti bahwa untuk setiap m terdapat sebuah kunci, yang dinotasikan dengan k(m), sedemikian hingga c = e(k(m),m). Lebih jauh lagi, m ≠ m’ → k(m) ≠ k(m’), jika tidak maka pendekripsian tidak akan bisa ditentukan, maksudnya kita akan mendapatkan dua pesan yang berbeda yang dengan kunci yang sama akan menghasilkan kriptogram yang sama c! Maka terdapat jumlah kunci yang setidaknya sama dengan jumlah pesan yang mungkin m.
Teorema 2 Dalam suatu sistem penyandian perfect, ketidaktentuan (uncertainty) pada kunci H(K) minimal sama dengan uncertainty pada pesan H(M): H(K) ≥ H(M).
BUKTI H(M) = H(M|C) ≤ H(M, K|C) = H(K|C) + H(M|K, C) = H(K|C) ≤ H(K) Konsekuensi dari kedua teorema di atas ialah bahwa dalam suatu sistem perfect, kunci haruslah cukup kompleks, setidaknya lebih kompleks dari pesannya sendiri.
Contoh Perfect Secrecy: One-Time Pad Contoh dari sistem kriptografi perfect adalah one-time pad. Tanpa kehilangan sifat dari one-time pad itu sendiri, berikut ini akan diberikan contoh dari binary one-time pad yang berarti bahwa pesan, kriptogram, dan kuncinya berada dalam bentuk barisan biner ( ∑ = {0, 1}). Dalam sistem ini, kuncinya adalah barisan random dari n bit yang independen, K = K1K2...Kn : p(Ki = 0) = p(K1 = 0|K1,...,Ki-1) = 0.5 dimana n adalah ukuran dari pesan terpanjang yang akan ditransmisikan. Penyandiannya dilakukan dengan cara menambahkan (exor) simbolsimbol pada pesan dan simbol-simbol pada kunci: Ci = Mi + Ki. Contoh: Misalkan kunci k = 11010101010010101001 dan pesan yang akan ditransmisikan m = 11110000111100001111, maka pesan yang telah terenkripsi adalah c = m + k = 00100101101110100110.
Teorema 3 “One-timepad” adalah sistem penyandian perfect.
BUKTI Untuk 1 < i ≤ n: p(Ci = 0|C1, ..., Ci-1 , M1, ...Mn) = p(Mi = 0|C1, ..., Ci-1, M1, ...Mn) . p(Ki = 0) + p(Mi = 1|C1, ..., Ci-1, M1, ...Mn) . p(Ki = 1) = 0.5[p(Mi = 0|C1, ..., Ci-1, M1, ...Mi-1) + p(Mi = 1|C1, ..., Ci-1, M1, ...Mi-1)] = 0.5 Sama halnya dengan di atas, p(C1|M1, ...Mn) = 0.5, dan p(Ci|C1, ..., Ci-1) = 0.5 untuk setiap i, 1 ≤ i ≤ n. Maka, P(C|M) = P(C), atau dengan kata lain I(C; M) = 0.
Definisi Perfect Secrecy dan Konsekuensinya Suatu sistem penyandian dikatakan perfect atau memenuhi perfect secrecy, jika dan hanya jika mutual information dari teks terang M dan pesan yang terenkripsinya C bernilai nol: I(C; M) = 0.
Teorema 1 Dalam suatu sistem penyandian perfect, jumlah kunci yang mungkin paling tidak adalah sama dengan jumlah pesannya. BUKTI I(C; M) = 0 mengakibatkan bahwa untuk setiap m, P(C|M = m) = P(C). Sekarang ambil sebuah kriptogram yang mungkin yaitu sebuah pesan yang terenkripsi c sedemikian hingga P(C = c)= 0. Maka untuk setiap pesan asli yang mungkin m, kita dapati P(C = c|M = m) ≠ 0 yang berarti bahwa untuk setiap m terdapat sebuah kunci, yang dinotasikan dengan k(m), sedemikian hingga c = e(k(m),m). Lebih jauh lagi, m ≠ m’ → k(m) ≠ k(m’), jika tidak maka pendekripsian tidak akan bisa ditentukan, maksudnya kita akan mendapatkan dua pesan yang berbeda yang dengan kunci yang sama akan menghasilkan kriptogram yang sama c! Maka terdapat jumlah kunci yang setidaknya sama dengan jumlah pesan yang mungkin m.
Teorema 2 Dalam suatu sistem penyandian perfect, ketidaktentuan (uncertainty) pada kunci H(K) minimal sama dengan uncertainty pada pesan H(M): H(K) ≥ H(M).
BUKTI H(M) = H(M|C) ≤ H(M, K|C) = H(K|C) + H(M|K, C) = H(K|C) ≤ H(K) Konsekuensi dari kedua teorema di atas ialah bahwa dalam suatu sistem perfect, kunci haruslah cukup kompleks, setidaknya lebih kompleks dari pesannya sendiri.
Contoh Perfect Secrecy: One-Time Pad Contoh dari sistem kriptografi perfect adalah one-time pad. Tanpa kehilangan sifat dari one-time pad itu sendiri, berikut ini akan diberikan contoh dari binary one-time pad yang berarti bahwa pesan, kriptogram, dan kuncinya berada dalam bentuk barisan biner ( ∑ = {0, 1}). Dalam sistem ini, kuncinya adalah barisan random dari n bit yang independen, K = K1K2...Kn : p(Ki = 0) = p(K1 = 0|K1,...,Ki-1) = 0.5 dimana n adalah ukuran dari pesan terpanjang yang akan ditransmisikan. Penyandiannya dilakukan dengan cara menambahkan (exor) simbolsimbol pada pesan dan simbol-simbol pada kunci: Ci = Mi + Ki. Contoh: Misalkan kunci k = 11010101010010101001 dan pesan yang akan ditransmisikan m = 11110000111100001111, maka pesan yang telah terenkripsi adalah c = m + k = 00100101101110100110.
Teorema 3 “One-timepad” adalah sistem penyandian perfect.
BUKTI Untuk 1 < i ≤ n: p(Ci = 0|C1, ..., Ci-1 , M1, ...Mn) = p(Mi = 0|C1, ..., Ci-1, M1, ...Mn) . p(Ki = 0) + p(Mi = 1|C1, ..., Ci-1, M1, ...Mn) . p(Ki = 1) = 0.5[p(Mi = 0|C1, ..., Ci-1, M1, ...Mi-1) + p(Mi = 1|C1, ..., Ci-1, M1, ...Mi-1)] = 0.5 Sama halnya dengan di atas, p(C1|M1, ...Mn) = 0.5, dan p(Ci|C1, ..., Ci-1) = 0.5 untuk setiap i, 1 ≤ i ≤ n. Maka, P(C|M) = P(C), atau dengan kata lain I(C; M) = 0.
