基于信息熵的明密文識別算法*

籍 帥，石元兵，明 爽，張運理，蘇攀西

（中電科網絡安全科技股份有限公司，四川 成都 610041）

0 引言

隨著加密技術的廣泛應用，加密數據呈現爆炸式增長，尤其隨著加密技術的演進和推廣，全加密時代悄然來臨。加密技術在保護用戶隱私的同時也深刻改變了網絡安全的威脅形勢。

明密文識別技術屬于網絡安全、商密監管等領域的細分方向，近幾年逐步受到國內外相關企業的重視和關注。

加密的本質是使用加密算法對數據進行加密處理，生成一組無意義的數據，由此產生的數據是人們無法辨識和篡改的密文。針對明密文識別的研究，需要分析密文數據區別于明文數據的特征。從密碼學角度看，經過加密得到的密文消除了統計特征，近似為隨機數[1]。

目前明密文識別方法主要有兩種：一種基于美國國家標準與技術研究所發布的隨機性檢測標準（National Institute of Standards and Technology，NIST），一種基于信息熵。

文獻[2]基于NIST 隨機性檢測標準[3]，統計了密文與明文的隨機性特征值，得出密文文件與未被加密的文件在頻率檢驗、塊內頻數檢驗、非重疊模板檢驗、游程檢驗、近似熵檢驗和離散傅里葉變換檢驗上的特征分布存在著明顯區別，即從隨機性分布出發，可有效識別與區分加密數據和非加密數據。但是隨機性檢測有16 項之多，效率差，準確率也只有90%，而且不能處理較短的數據。

基于信息熵的方法主要使用數據的信息熵作為特征，根據不同信息熵計算方法，可以將其分為基于連續若干字節的信息熵計算方法、基于滑動窗口的信息熵計算方法和基于采樣的信息熵計算方法[4-5]。文獻[6]提出了一種基于信息熵的加密判斷算法應用于木馬檢測系統，但該算法最多只能識別1 500 個字節的數據。

本文提出一種基于信息熵的明密文識別算法，采用基于連續若干字節的信息熵計算方法和基于滑動窗口的信息熵計算方法，通過計算數據的信息熵，并和對應數據長度的置信區間進行比較，來判斷數據是否加密。該方法可以識別任意長度的數據，并且具有很高的準確率。同時，該方法實用性強，可以運用在任何需要判斷數據是否加密的領域。

本文內容分為相關技術、方案設計和實驗結果3 個部分。

1 相關技術介紹

1.1 信息熵

信息熵[7]是信息論的基本概念，用于度量信息量，由信息論之父香農提出。信息熵的定義如下文所述。對于一個有m種可能的事件A1,A2,…,Am，并且這些事件發生的概率為p1,p2,…,pm，其信息熵計算公式為：

式中：K為一個正整數，一般情況下K=1。由于要事先知道每個事件發生的概率，才能計算信息熵，這是相當困難的，因此通常計算信息熵的估計來代替計算信息熵。文獻[8-11]介紹了幾種估計熵值的方法，但是這些方法需要大量的樣本，而且計算復雜。本文采用Monte-Carlo 方法計算一致分布條件下的信息熵的估計值。

1.2 Monte-Carlo 方法

Monte-Carlo 方法也稱統計模擬法，是把概率現象作為研究對象的數值模擬方法，是按抽樣調查法求取統計值來推定未知量的計算方法，適用于對離散系統進行計算仿真試驗。在計算仿真中，通過構造一個和系統性能相近似的概率模型，并在數字計算機上進行隨機試驗，可以模擬系統的隨機特性。它使用隨機數（或偽隨機數）來解決計算的問題，是一類重要的數值計算方法。

一個簡單的例子可以解釋Monte-Canlo 方法。假設需要計算一個不規則圖形的面積，首先把圖形放到一個已知面積的方框內；其次假想有一些豆子，把豆子均勻地朝這個方框內撒，撒好后數這個圖形之中有多少顆豆子；最后根據圖形內外豆子的比例來計算面積。當豆子越小，撒的越多的時候，結果就越精確。

設數據流F的長度為N，隨機產生10 萬條樣本，分別計算每個樣本的熵值，然后取平均值，得到長度為N的信息熵的估計。

1.3 評價指標

基于機器學習的評價指標包括準確率、查準率、召回率、誤報率、漏報率等。本文采用準確率作為評價指標。

準確率反映了分類器對整個樣本的判定能力，即能將正的判定為正，負的判定為負。

假設原始樣本中有兩類，總共有P個正例，N個負例。經過分類后，有TP個屬于該類的樣本被系統判定為該類，FN個屬于該類的樣本未被系統判定為該類，FP個不屬于該類的樣本被系統誤判定為該類，TN個不屬于該類的樣本被系統判定為不屬于該類。準確率定義如下：

2 方案設計

加密數據具有機密性，經過加密的數據和完全隨機的數據非常相似，也就是說，經過加密的數據比明文的數據表現出了更大的不確定性，即熵值更大。本文將一條數據當作一系列事件的集合，將數據的各個字節作為一個獨立事件，由于每個字節有256 個可能的取值，而且經過加密的數據各個字節數值近似服從一致分布，因此當數據的長度足夠長時，整個數據流的熵值會趨近于log2(256)=8。但是明文數據不具有隨機性，也就是說，明文數據的熵值會小很多，這是因為由式（1）可知，每個事件的概率分布服從一致分布時，信息熵取最大值。

定義有N個字節的數據流F的字節熵為：

式中：m為字節所有可能的取值數，即m=256；fi是某一確定的字節取值在整條數據中出現的頻率。式（3）計算的熵值就是熵的最大似然估計值。

2.1 截斷熵的計算

要實現加密數據的識別，首先需要計算有一系列特定長度的加密數據的熵值作為算法的閾值。直接計算熵值是不現實的，因此本文不直接計算一條數據的真實熵，而是計算概率分布p=(pi)i∈∑的N-截斷熵（N-truncated entropy）[12-13]HN(p)。HN(p) 被定義為所有長度為N的根據概率分布p產生的數據流F的簡單熵的平均值。可以通過下式進行求和計算：

當p服從一致分布u時，可以得到服從一致分布的N-截斷熵的計算公式為：

2.2 置信區間的確定

2.1 節雖然計算了HN(u)的值，但是當一個具體的文件數據的與HN(u)進行比較時，它們之間具體相差多少被認為是加密數據，因此還是未知。本節將確定這一置信區間。

2.3 算法描述

用Monte-Carlo 方法計算長度為16～1 000的隨機數據流的N-截斷熵HN(u)和標準差并將其與長度一一對應填入表里，這樣就可以很輕易地計算出置信度為99.9%的置信區間對于一條待檢測數據，若數據長度大于或等于16 字節，小于或等于1 000 字節，只需要計算待檢測數據的并且將其與相應長度為N的置信區間比較，就可以在置信度99.9%的條件下判斷該數據是否加密。若數據長度大于1 000 字節，則將數據長度除以1 000 得到商和余數。分別判斷各個1 000 字節及余數字節是否加密，若某一段數據未加密，則整段數據判定為未加密；若所有段數據為已加密，則整段數據為已加密。之所以從長度16 開始才能判斷，是因為上文的實驗結果顯示，只有在N≥16 的情況下，置信區間才有效，在實際情況中數據長度小于16 的情況很罕見。具體算法如下文所述。

（1）載入已經計算好的與長度對應的N-截斷熵HN(u)和標準差

（2）輸入要判斷的數據文件名。

（3）判斷待檢測文件的長度是否大于或等于16字節，若是則轉入步驟（4）；反之，本算法無法判斷。

（4）將數據按照每1 000 字節進行劃分，則數據長度為1 000n+m（n≥0，0 ≤m＜1 000）。分別對n+1 段數據計算并判斷是否在其長度對應的置信區間內。若有一段數據不在置信區間內，則判斷該數據未加密；若所有數據均在置信區間內，則判斷數據已加密；若m＜16，則該段不進行判斷。

（5）輸出判斷結果。

3 算法測試

3.1 測試環境

本次測試在實驗室現有環境下進行，總體環境設置如表1 所示。

表1 實驗環境

3.2 測試方法

為了測試本文所述算法識別明密文的準確性，在實驗中選擇了不加密的數據（base64、zip 壓縮、rar 壓縮、hash）和加密的數據（AES、DES、sm2、sm4）。

測試算法見第2 節，此處不再贅述。本文所用的數據集源于實驗室網絡環境，測試數據組成情況如表2 所示。

表2 算法可行性檢測結果

3.3 測試結果

測試結果如表3 所示。

表3 算法可行性檢測結果

通過上述實驗可以看到，對于明文或經過編碼的明文數據，該方法均能準確識別為明文；對于對稱加密或非對稱加密的密文數據，該方法識別率超過99%。總體來說，本文所提算法具有很高的準確率和時間效率，可以區分加密數據和未加密數據。

4 結語

本文介紹了一種基于信息熵的明密文識別算法。該算法只需要輸入待檢測數據的文件名即可判斷文件數據是否加密。通過實驗可知，該算法具有很高的準確率和很低的誤報率，可以運用在任何需要明密文識別的場景中。

本文所提算法中，針對一條待檢測數據是每1 000 個字節進行一次判斷，所以數據越短效率越高。在將來的研究中，需要研究如何提高算力，每2 000 個字節或更多字節判斷一次，從而提高大數據的時間效率。