Perbandingan entropi dan distribusi byte dalam data terkompresi / terenkripsi

Saya punya beberapa pertanyaan yang cukup lama.

Tes entropi sering digunakan untuk mengidentifikasi data yang dienkripsi. Entropi mencapai maksimum ketika byte dari data yang dianalisis didistribusikan secara seragam. Tes entropi mengidentifikasi data yang dienkripsi, karena data ini memiliki data terkompresi seperti distribusi yang seragam, yang diklasifikasikan sebagai terenkripsi ketika menggunakan tes entropi.

Contoh: Entropi dari beberapa file JPG adalah 7.9961532 Bits / Byte, entropi dari beberapa TrueCrypt-container adalah 7.9998857. Ini berarti dengan tes entropi saya tidak dapat mendeteksi perbedaan antara data terenkripsi dan terkompresi. TAPI: seperti yang Anda lihat pada gambar pertama, jelas byte dari file JPG tidak didistribusikan secara seragam (setidaknya tidak seragam seperti byte dari truecrypt-container).

Tes lain dapat berupa analisis frekuensi. Distribusi setiap byte diukur dan misalnya uji chi-square dilakukan untuk membandingkan distribusi dengan distribusi hipotesis. sebagai hasilnya, saya mendapatkan nilai-p. ketika saya melakukan tes ini pada JPG dan TrueCrypt-data, hasilnya berbeda.

Nilai p dari file JPG adalah 0, yang berarti bahwa distribusi dari tampilan statistik tidak seragam. Nilai p dari file TrueCrypt adalah 0,95, yang berarti bahwa distribusinya hampir seragam sempurna.

Pertanyaan saya sekarang: Dapatkah seseorang memberi tahu saya mengapa tes entropi menghasilkan positif palsu seperti ini? Apakah ini skala unit, di mana konten informasi diekspresikan (bit per byte)? Apakah misalnya p-value "unit" jauh lebih baik, karena skala yang lebih halus?

Terima kasih banyak atas jawaban / ide!

JPG-Image TrueCrypt-Container

Pertanyaan ini masih kekurangan informasi penting, tapi saya pikir saya bisa membuat beberapa tebakan cerdas:

• The entropi dari suatu distribusi diskrit$\mathbb{p} = (p_0, p_1, \ldots, p_{255})$ didefinisikan sebagai

  $$H(\mathbb{p}) = -\sum_{i=0}^{255} p_i \log_2{p_i}.$$

• Karena $-\log$ adalah fungsi cekung, entropi dimaksimalkan ketika semuanya $p_i$adalah sama. Karena mereka menentukan distribusi probabilitas (mereka berjumlah satu), ini terjadi ketika$p_i = 2^{-8}$ untuk setiap $i$, dari mana entropi maksimum adalah

  $$H_0 = -\sum_{i=0}^{255} 2^{-8} \log_2{(2^{-8})} = \sum_{i=0}^{255} 2^{-8}\times 8 = 8.$$

• Entropi dari $7.9961532$bit / byte ( yaitu , menggunakan logaritma biner) dan$7.9998857$ sangat dekat satu sama lain dan dengan batas teoritis $H_0 = 8$.

  Betapa dekat? Memperluas$H(\mathbb{p})$ dalam seri Taylor sekitar maksimum menunjukkan bahwa penyimpangan antara $H_0$ dan entropi apa pun $H(\mathbb{p})$ sama dengan

  $$H_0 - H(\mathbb{p}) = \sum_i \frac{(p_i - 2^{-8})^2}{2 \cdot 2^{-8} \log(2)} + O(p_i - 2^{-8})^3.$$

  Dengan menggunakan rumus ini kita dapat menyimpulkan bahwa entropi dari $7.9961532$, yang merupakan perbedaan $0.0038468$, Diproduksi oleh deviasi akar-rata-kuadrat dari adil $0.00002099$ diantara $p_i$ dan distribusi seragam yang sempurna $2^{-8}$. Ini mewakili penyimpangan relatif rata-rata saja$0.5$%. Perhitungan serupa untuk entropi$7.9998857$ sesuai dengan penyimpangan RMS di $p_i$ hanya 0,09%.

  (Pada gambar seperti yang paling bawah dalam pertanyaan, yang tingginya berkisar sekitar $1000$ piksel, jika kami menganggap ketinggian bilah mewakili $p_i$, lalu a $0.09$% Variasi RMS sesuai dengan perubahan hanya satu piksel di atas atau di bawah tinggi rata-rata, dan hampir selalu kurang dari tiga piksel. Seperti itulah tampilannya. SEBUAH$0.5$% RMS, di sisi lain, akan dikaitkan dengan variasi tentang $6$ piksel rata-rata, tetapi jarang melebihi $15$piksel atau lebih. Itulah tidak apa sosok penampilan atas suka, dengan variasi yang nyata dari$100$atau lebih banyak piksel. Karena itu saya menduga bahwa angka-angka ini tidak dapat dibandingkan secara langsung satu sama lain.)

Dalam kedua kasus ini adalah penyimpangan kecil, tetapi satu lebih dari lima kali lebih kecil dari yang lain. Sekarang kita harus membuat beberapa tebakan, karena pertanyaannya tidak memberi tahu kita bagaimana entropi digunakan untuk menentukan keseragaman, juga tidak memberi tahu kita berapa banyak data yang ada. Jika "tes entropi" yang sebenarnya telah diterapkan, maka seperti tes statistik lainnya, tes ini perlu memperhitungkan variasi peluang. Dalam hal ini, frekuensi yang diamati (dari mana entropi telah dihitung) akan cenderung bervariasi dari frekuensi dasar yang sebenarnya karena kebetulan. Variasi ini menerjemahkan, melalui rumus yang diberikan di atas, ke dalam variasi entropi yang diamati dari entropi yang mendasarinya. Diberikan data yang cukup, kita dapat mendeteksi apakah entropi yang benar berbeda dari nilai $8$terkait dengan distribusi yang seragam. Semua hal lain dianggap sama, jumlah data yang diperlukan untuk mendeteksi perbedaan rata-rata hanya$0.09$% dibandingkan dengan perbedaan rata - rata $0.5$% akan menjadi sekitar $(0.5/0.09)^2$ kali lebih banyak: dalam hal ini, hasilnya lebih dari $33$ kali lebih banyak.

Akibatnya, sangat mungkin ada data yang cukup untuk menentukan bahwa entropi yang diamati $7.996\ldots$berbeda secara signifikan dari$8$ sementara jumlah data yang setara tidak dapat dibedakan $7.99988\ldots$ dari $8$. (Situasi ini, omong-omong, disebut negatif palsu , bukan "positif palsu," karena telah gagal mengidentifikasi kurangnya keseragaman (yang dianggap sebagai hasil "negatif").) Dengan demikian, saya mengusulkan bahwa (a ) entropi memang telah dihitung dengan benar dan (b) jumlah data cukup menjelaskan apa yang telah terjadi.

Kebetulan, angka-angka itu tampaknya tidak berguna atau menyesatkan, karena mereka tidak memiliki label yang sesuai. Meskipun bagian bawah tampak menggambarkan distribusi yang hampir seragam (dengan asumsi sumbu x terpisah dan sesuai dengan$256$ nilai byte yang mungkin dan sumbu y sebanding dengan frekuensi yang diamati), yang teratas tidak mungkin sesuai dengan entropi di dekat $8$. Saya menduga nol dari sumbu y pada gambar atas belum diperlihatkan, sehingga perbedaan di antara frekuensi dilebih-lebihkan. (Tufte akan mengatakan angka ini memiliki Faktor Kebohongan besar.)