為什麼來自低熵明文的密文不可壓縮？

這是在與同事討論之後發生的。

• 我的純文字文件plain包含大約 100,000 行“所有工作，沒有播放……”。它的大小是：2.2 MB。
• 壓縮後為：5.4kB
• 我加密原件：

openssl aes-128-cbc -in plain -out plain.ENC

plain.ENC比原來的稍微大一點，這是我所期望的。

• 我壓縮加密的副本：gzip plain.ENC. 但我觀察到壓縮副本現在略大於.plain.ENC

假設原始文件的熵約為 1000-10000 位，為什麼相應的密文是不可壓縮的？我對字元串熵的直覺概念是生成該字元串所需的最少位數。如果字元串是 3 MB 長的密文，它是使用 AES 實現（可能不超過幾千位）加密的 1000 位熵字元串以及幾百位密鑰生成的。直覺上，對我來說，密文的熵應該不超過生成它的字元串和過程的熵之和。

**所以，我的問題是：**我的直覺概念完全錯誤嗎？如果我們將低熵文件擴展為大幾個數量級，我們會開始觀察密文的可壓縮性嗎？

好吧，您對熵的定義被稱為Kolmogorov 複雜性，這並不是說它不正確，而是它不適用於 gzip 所做的事情。

例如，值 $ \pi $ 也可以通過短程序生成；但是，如果您嘗試壓縮二進制擴展的 2.2Mbyte 樣本，您還會發現 gzip 也無法壓縮它。

我們可以從中看出，gzip 實際上並不能很好地估計 Kolmogorov 複雜度。現在，這實際上並不是對 gzip 的主要批評；實際上不可能編寫一個計算它的程序（！）。

與其試圖與 Kolmogorov 複雜性作鬥爭，gzip（以及其他所有壓縮算法）依賴於壓縮數據的是啟發式算法。也就是說，它有一個出現在真實明文中的冗餘模型（例如重複的子串），並且能夠利用這些冗餘來縮短長度。現在，如果該模型對應於它給出的文本，gzip 可以很好地壓縮；如果模型不對應（以及加密文本和二進制擴展 $ \pi $ 落在這個陣營中），它根本無法壓縮。

而且，不，加密更多數據不會使結果更可壓縮。

引用自：https://crypto.stackexchange.com/questions/2921