結合特征選擇與集成學習的密碼體制識別方案

王 旭，陳永樂，王慶生，陳俊杰

（太原理工大學信息與計算機學院，山西晉中 030600）

0 概述

安全的密碼體制必須能夠抵御各種不同類型的攻擊。由于攻擊者主要關注如何通過密文獲取密鑰以及如何將密文恢復為明文，因此諸多以此為目的的攻擊方法常針對特定密碼體制而設計，其中，設計識別密文所用的加密算法是開展密碼分析的重要前提。

明文經不同密碼體制加密后形成的密文數據并不能達到完全隨機，彼此間尚存有微小差異，對此，可通過提取表征密文信息的相關特征作為區分不同密文類別的依據。現階段研究主要利用機器學習方法和統計學方法對密文所用的加密算法進行識別。相比于利用統計學方法，基于機器學習方法的識別方案設計思路清晰，適應性強，并且可供利用的理論基礎豐富，是目前的主流研究方向。

文獻［1］借鑒文檔分類方法中的詞袋模型，以支持向量機為分類算法，研究針對DES、3DES、AES、RC5 和Blowfish 密碼體制的識別問題。文獻［2］借鑒信息檢索中的向量空間模型，通過合理構建神經網絡對MARS、RC6 和Twofish 等密碼體制進行識別研究，但該方案受限于計算復雜度，僅可在密文數據量較小的情況下完成識別，推廣難度較大。文獻［3］結合統計學與機器學習方法，以NIST 發布的隨機性測試作為構造密文特征的依據，即以密文隨機性度量值作為判斷密文相似性的標準，使用K-均值聚類算法對AES、DES、Camellia、SMS4 和3DES 密碼體制進行識別研究。文獻［4］依據密碼學常識，提出一種基于隨機森林的分層識別方案，并初步給出一種密碼體制識別問題的定義系統，以助于對識別問題的形式化研究。

在現有研究中，所提取的特征基本為借鑒其他領域中有關識別任務中的所用特征，如文獻［1-2］借鑒文檔分類中所用相關特征（詞袋模型和向量空間模型），文獻［4-6］引入信息論的理論作為提取特征的方法，文獻［3-4，7］利用隨機性測試的方法提取密文特征。對于所用分類方法，文獻［1］選擇支持向量機作為提取密文特征后進行分類的算法，并比較不同核函數情景下的識別情況，文獻［2，8-9］引入神經網絡作為識別任務的分類模型，文獻［5］利用C4.5 算法構建決策樹作為識別任務中的分類模型。為比較不同分類算法在識別任務中的優劣，文獻［10-11］選擇樸素貝葉斯、支持向量機、神經網絡等8 種常見分類算法對4 種分組密碼體制進行識別，并對不同分類算法的識別性能進行對比。為比較不同分組密碼工作模式下的識別情況，文獻［12-13］對利用CBC 和ECB 模式加密的密文數據進行了研究。

目前，較多識別密碼體制的研究基于多種密文特征和分類算法，但研究者較少探討不同特征對識別性能的影響，并且現有理論框架還有待進一步完善。對此，本文提出一種新的密文特征提取方法，同時完善密碼體制識別問題的定義系統，給出提取密文特征的形式化描述。在此基礎上，結合特征選擇方法設計基于集成學習的密碼體制識別方案。比較特征不同的屬性對識別方案識別效果的影響，并且使用該方案分別對包含多種序列、分組和公鑰密碼體制的3 種具體識別情景進行實驗。

1 密文特征建模

現有基于機器學習算法的密碼體制識別研究基本符合構造新特征，即選擇新分類模型的簡單研究模式，但較少對該問題進行更深入的探討，因此，利用現有研究成果難以做進一步推進。另一方面，鑒于密碼體制識別問題的理論基礎尚不完備。文獻［4］初步給出了密碼體制識別問題的定義系統，該定義系統有助于將識別問題規范化和形式化。但對于識別問題的進一步深入研究，此理論框架仍稍顯單薄。首先，該定義系統僅對識別問題和識別方案進行了形式化描述，但未涉及識別任務的主要難點，如密文特征提取和分類模型選擇等問題；其次，形式化識別問題和識別方案仍沒有改變先提出識別方案再將其統一于定義系統之下的流程，割裂了理論框架與方案設計間的關系；此外，利用識別問題和識別方案的形式化描述難以對各類識別方案的設計思路和彼此優劣作出較完備的解釋，無法做到由理論指導實踐。

鑒于以上考量，本文基于文獻［4］識別問題的定義系統，對識別方案中提取密文特征的環節做形式化定義。

遵照文獻［4］密碼體制識別任務的定義系統，令F 表示密文文件，其可表示為由某類字符組成的有序集合，定義如下：

定義1（密文） 設有未知密碼體制的密文文件：

其中，ci表示密文文件的第i個字符，且ci可表示為不同類型的字符，現階段研究［3-5，10-11］多將密文表示為以比特或字節為基本字符ci的有序集合。

獲取密文后需要提取密文的特征，定義如下：

定義2（密文特征） 對未知密碼體制的密文文件提取特征，得到維數為d的特征向量：

可將提取密文特征的過程抽象為將密文文件F映射為特征vfea的過程，即Fea（F）→vfea，其中，Fea（）表示具體的特征提取過程或方法，如計算密文數據中各字符出現概率［4，6-7］、各字符熵或最大熵［4-5］等。

定義3（加工函數） 給定未知密碼體制的密文F，將密文映射為特征vfea過程中的計算方法稱為加工函數，記作f。計算各字符的概率、熵值或最大熵值等方法，均為不同種類的加工函數。

加工函數的輸入對象是密文數據。輸入的密文數據可以是密文依順序按固定長度分塊后的每一分塊，也可以是各分塊相同位置處字節或比特重新組合后的數據［4］。此外，還可將表示密文的字符分別組合，以每一類字符組合作為加工函數的輸入對象［5］。

定義4給定未知密碼體制的密文F 和加工函數f，令oper 表示加工函數輸入對象，即密文數據的組織形式。

定義5綜合以上定義系統，密碼體制識別方案中提取的密文特征可表示為四元組vfea=（C，f，oper，d）。其中：C 為密文數據的表示方式，如將密文F 表示為以比特或字節為單位的有序集合，并從中提取密文特征；f 表示將密文映射為特征的加工函數；oper 表示加工函數的輸入對象，即對密文數據的組織形式；d表示密文特征的維數。

在定義5 中，識別方案提取的密文特征被表述為具有4 條屬性的四元組。以此密文特征模型為出發點，下文將通過實驗比較該四元組中各屬性對識別方案效果的影響。

2 密文特征及識別方案

2.1 特征對比

基于上文對密文特征的定義，本節通過實驗探究特征的不同屬性對識別準確率的影響。

依照現有密碼體制識別方案，選擇AES、DES、3DES、RSA 和RC4 這五組包含分組、序列和公鑰的加密算法［14］作為待識別的密碼體制，并以KNN 分類算法作為實驗所用分類模型。根據密文表現形式、加工函數和特征維數等的不同，選擇文獻［3-5，10-11］中的多類特征進行實驗，實驗的具體細節見本文第3 節。

從現有研究及密文特征的定義系統出發，此處實驗所選特征為vfea=（C，f，oper，d），其中，C 包含比特和字節兩種形式，即C=｛bit，Byte｝。選取熵、最大熵［15］、概率和隨機性測試［16］作為加工函數f 的待選項，即f=｛Entropy，Maxentropy，Probability，NIST｝。關于密文數據組織方式oper，此處選擇將密文依次序分塊、各分塊內相同位置再組合和不同類型字符組合3 種方式。

圖1 所示為所選12 種特征的識別準確率比較結果，其中，圖1（a）所示為選擇不同加工函數密文特征的識別準確率曲線，圖1（b）所示為將密文分別表示為比特與字節的有序集合后不同維數特征的識別準確率曲線。由圖1（a）可以看出，當以字符出現頻率、熵、最大熵和隨機性測試作為提取密文特征的加工函數時，以最大熵與隨機性測試作為加工函數的特征表現最好。由圖1（b）可以看出，在加工函數與密文組織方式相同的情況下，比特類特征與字節類特征的識別準確率差距不大，且不同維數特征間識別準確率的差異不明顯。

圖1 不同密文特征屬性對識別性能的影響Fig.1 Influence of different attributes of ciphertext feature on recognition performance

通過分析圖1 可以發現：在密文特征的4 種屬性中，密文數據的字符形式C，即提取密文特征時表示密文數據的基本字符單位對識別準確率的影響有限；密文特征的維數d對識別準確率的影響有限；加工函數f 選擇計算各字符頻率的特征遠不如以隨機性測試和信息熵為加工函數的特征，且以熵或最大熵作為加工函數的特征表現更穩定，適應性更好。此外，在提取密文特征時，對密文數據的不同組織方式也對識別效果有較大影響。

綜合以上分析，本文選擇以ASCII 表中的256 種字符作為表示密文數據的基本字符。對于密文數據的組織方式oper，此處選擇將表示密文數據的字符重新組合的方式，即把表示密文數據的256 個字符分為6 組字符組合，分別為所有字符、可見字符、大寫字母、小寫字母、數字以及字母和數字之外的字符。同時，以熵、最大熵和基尼系數等信息論中度量信息的不確定性及數據隨機性的方法作為提取密文特征的加工函數。3 種加工函數的計算方法如下：

對密文文件F，計算其中對應上述6 組字符組合中每一組字符的熵、最大熵和基尼系數，并以6 組字符的計算結果作為密文文件F 的特征。在此基礎上，根據不同密碼體制識別情景構造不同的字符組合方法。

2.2 特征選擇

在識別包含多種密碼體制的密文時，提取相同特征難以應對密文數據間的多樣性，此處選擇以上述6 組字符集作為基礎，利用Relief 特征選擇算法［17］對每組字符集進行字符選擇，在不同密碼體制識別情景中以不同字符集合作為提取密文特征的基礎。

其中，f（x）表示上文所提3 種信息熵類加工函數，表示去掉字符j 后，其余字符經加工函數f（x）計算后的值，pl表示第l類樣本占總體樣本的比例，diff（a，b）表示a、b間的差值。

對每一組字符集，若去掉字符j 后，其與猜中近鄰的距離小于與其他各類別猜錯近鄰的距離，說明去掉字符j 后對分類有積極作用，則減小字符j 的權重；若去掉字符j 后，其與猜中近鄰的距離大于與其他各類別猜錯近鄰的距離，說明去掉字符j 后對分類有消極影響，則增加字符j 的權重。

在不同密碼體制識別情景下，以2.1 節中6 組字符集為基礎，利用式（4）的方法重新構造各字符集，并根據新的字符組合，利用式（3）中的函數提取密文特征。

2.3 識別方案

在包含多種密碼體制的識別情景中，現有分階段識別方案對多種密碼體制劃分層次，通過減少各階段待識別密碼體制的數量，降低識別任務的難度［4，9］。但在識別方案不同階段均使用相同特征及分類模型，難以兼顧不同密碼體制識別情景間可能存在的差異。因此，本文在分階段識別方案設計思路的基礎上，選擇集成學習算法［18］作為識別方案中的分類模型。集成學習算法流程如圖2 所示。

圖2 集成學習算法流程Fig.2 Procedure of ensemble learning algorithm

在包含多種密碼體制的識別情景中，依據密碼學常識可將識別過程分為兩個階段，即識別出密文所用加密算法所屬序列、分組或公鑰密碼體制的類別，此處稱為密碼體制類別識別階段，以及完成識別出密文所用具體加密算法的任務，如在已知密文所用加密算法所屬類別為分組密碼后，進一步識別出其所屬AES、DES 或3DES 等分組密碼加密算法。

在不同密碼體制識別情景中，待識別的密碼體制類別和具體算法間均存在差異，若選擇單一分類算法進行訓練，可能因誤選導致該分類算法的泛化性能不足，而結合多種分類學習算法作為個體學習器并集成的方式可降低此風險。本文以集成學習算法作為分類學習器設計密碼體制識別方案，工作流程如圖3 所示。

在訓練階段，首先對帶有密碼體制標簽的密文數據（F，label）以2.2 節中的方法進行特征選擇，得到在該識別情景下各字符的權重，然后根據各字符的權重重新提取密文特征，并將帶標簽的密文特征（Fea，label）導入分類模型進行訓練。

在識別階段，首先提取密文類別特征fea0，利用訓練好的分類模型識別出其所屬的密碼體制類別，然后根據所屬類別，進一步提取可識別具體加密算法的密文特征feak并導入訓練好的分類模型，最終輸出識別結果。

圖3 本文識別方案流程Fig.3 Procedure of the identification scheme proposed in this paper

3 實驗與結果分析

3.1 密文數據采集與實驗設置

為驗證本文方案的有效性并開展后續實驗，隨機選取Caltech-256 圖片庫中大小固定為512 KB 的1 000 張圖片作為實驗所用明文數據，以RC4、Salsa、AES、DES、3DES、Camellia、Blowfish、SMS4、IDEA和RSA 密碼體制為基礎，通過改變每種密碼體制的參數長度或工作模式等設置，擴展為36 種不同的密碼體制，并分別對1 000 張圖片進行加密，得到共計36 000 個512 KB 的密文文件。有關各密碼體制的設置情況及實現方式如表1 所示，其中涉及各密碼體制的詳細介紹參見文獻［19-21］。

表1 密文數據采集使用的10 種密碼體制Table 1 Ten cryptosystems for ciphertext data collection

以下實驗以識別準確率p作為評價識別方案效果的標準。在每組實驗中均對密文數據進行十折交叉驗證，并以各次結果的平均值作為衡量識別效果的指標。

3.2 密碼體制類別實驗

在包含多密碼體制的識別情景中，需要識別密文所用加密算法的類別。依據密碼學常識，首先將上述36 種密碼體制作為以下兩種識別情景分別進行實驗：一種是將上述密碼體制分為對稱加密與非對稱加密類型2 類識別情景（簡稱兩類情景）；另一種是將其分為序列、分組及公鑰密碼體制3 類識別情景（簡稱三類情景）。為探究不同序列密碼及分組密碼中不同分組長度、工作模式等識別情景下的識別情況，從上述3 類密碼體制中各選出一部分組成新的密碼體制識別情景，具體如下：

在由式（5）～式（7）給出的3 種情景中，序列密碼RC4 和Salsa 通過選擇不同密鑰分別各擴展為4 種不同的密碼體制：情景1 中選取分組長度與工作模式均相同的6 種分組密碼（AES、DES 等）；情景2 中選取分組長度相同但工作模式不同的4 種分組密碼（SMS4）；情景3 中選取工作模式相同但分組長度不同的3 種密碼（AES）；公鑰密碼體制選取2種密鑰長度的RSA。

實驗利用2.2 節中的算法對各類具體識別情景進行特征選擇，結果如圖4 所示。可以看出，在不同識別情景下，每種字符對識別任務的權重存在差異。因此，根據每種識別情景中的字符權重重新提取密文特征，實驗結果如表2 所示。可以看出，在兩類情景中基本可實現準確識別，在三類情景中，識別準確率也高于隨機分類的準確率，在改變不同參數設置的3 種情景中，由于待識別密碼體制數量的減少，因此整體好于三類情景的情況，且熵與最大熵作為加工函數時要好于基尼系數。

圖4 不同識別情景下的字符權重Fig.4 Character weight under different recognition scenarios

表2 不同識別情景下的類別識別準確率Table 2 Class recognition accuracy under different recognition scenarios %

3.3 加密算法識別

完成對密文所屬密碼體制類別的識別后，執行對相同類別內具體加密算法的識別任務。針對式（5）～式（7）給出的情景，對其中具體的加密算法進行識別實驗，組成6 種識別情景。其中，序列1 對應式（5）中的RC4，序列2 對應式（7）中的Salsa，分組1～分組3 分別對應式（5）～式（7）中的分組密碼設置，最后一種為識別公鑰的情景。圖5、圖6 分別表示以熵和最大熵為加工函數f 時，各具體識別情景中的字符權重。根據各識別情景中的字符權重重新提取密文特征，實驗結果如表3 所示。可以看出：本文方案在識別公鑰密碼體制的情景中基本可達到準確識別；在兩種序列密碼識別情景中最高識別準確率分別為55%和48%；在3 種不同參數設置的分組密碼識別情景中最高準確率分別為32.46%、41.20%和39.29%，均高于隨機分類的準確率。利用十折交叉驗證過程中的結果進行單樣本的T-檢驗，結果顯示，3 種分組密碼識別情景下的p-value 均小于9.93×10-9。實驗結果表明，在這3 種識別情景下，各最優特征的識別準確率顯著高于隨機識別的準確率。

圖5 不同識別情景下的熵權重Fig.5 Entropy weight under different recognition scenarios

圖6 不同識別情景下的最大熵權重Fig.6 Maximum entropy weight under different recognition scenarios

表3 不同識別情景下的識別準確率Table 3 Recognition accuracy under different recognition scenarios %

3.4 整體評價

對本文方案在由式（5）～式（7）給出的3 種情景中的整體識別效果進行分析。每種情景的總體識別準確率計算公式如下：

其中，P表示總體的準確率，pc和p1～p3分別表示識別密碼體制類別階段和識別各類別中每種具體加密算法的準確率，相應地，k1～k3表示每類密文樣本占總樣本的比例。

實驗以不區分具體識別情景均提取相同密文特征的文獻［4］識別方案作為對比方案，并選擇其中表現較好的3 種特征進行識別實驗。文獻［4］方案與本文方案的識別結果比較如表4 所示。可以看出：在不區分識別情景的文獻［4］方案中，密文特征以熵作為加工函數的識別效果整體優于以計算概率作為加工函數的特征，但在3 種識別情景中的差異不大；在區分識別情景的本文方案中，不同識別情景間表現最好的特征存在差異，但以熵和最大熵為加工函數的特征整體表現更好；本文方案準確率整體上優于文獻［4］方案，但在不同識別情景中，提升效果存在差異，在3 種識別情景下最優識別準確率分別提升6.41%、10.03%和11.40%。

表4 本文方案與文獻［4］方案的識別準確率比較Table 4 Comparison of identification accuracy between the scheme proposed in this paper and the one in literature［4］ %

為進一步檢驗兩種方案識別結果的差異，對上述3 種情景中各最優特征間的識別準確率進行兩獨立樣本T-檢驗，結果顯示，3 種情景下的p-value 分別為2.24×10-10、1.16×10-11和3.46×10-15，表明在統計學意義下本文方案的提升效果明顯。

4 結束語

本文對密碼體制識別問題進行探討，并以現有理論框架為基礎，對識別方案中提取的密文特征進行建模。為分析識別方案所用密文特征對識別結果的影響，從特征模型出發，提取12 種密文特征進行對比實驗，結果表明，在提取密文特征時，密文數據的組織方式及所用的加工函數這兩種因素對識別方案識別效果的影響較大。為此，在本文方案中加入特征選擇的環節，并重新設計了提取密文特征的方法。運用該方法對包含多種密碼體制的3 類不同識別情景進行實驗，結果表明，與不區分識別情景均采用相同密文特征的識別方案相比，本文方案在包含多種密碼體制的識別情景中具有更顯著的優勢。下一步將研究多種加密算法的原理及性能差異，同時探究其他密文組織方式和加工函數在識別問題中的應用。