密碼字典數據去重算法研究

陸浩 盧軍 修榕康

摘要 對直接去重算法、Hash去重算法和Hadoop集群數據去重算法進行研究分析，得出各算法在密碼字典數據去重中的適用場合。去重后的密碼字典作為密碼字符子集，為面向暴力破解的密碼字典生成提供了有效方法。

關鍵詞 數據去重；密碼字典；暴力破解

DOI DOI： 10.11907/rjdk.162429

中圖分類號： TP312

文獻標識碼： A 文章編號 文章編號： 16727800（2017）002005702

0 引言

密碼作為一種常見的認證方式之一，為用戶合法利用網絡信息系統提供了安全保障，同時也給不法分子運用VPN、加密郵件系統等，進行惡意軟件傳輸、敏感數據和網絡攻擊提供了逃避打擊的庇護。計算機網絡信息系統的安全性很多都是依靠密碼來加以保障，密碼破解對于網絡安全監管部門等追蹤網絡犯罪、進行電子取證和互聯網內容審計都有著十分重要的意義。而對于用戶而言，在設置密碼時，為了便于記憶，往往選擇位數較短、有規律的密碼，會選擇自己姓名、生日和有特殊意義的字母單詞，而且大多數用戶，在不同場合可能采用相同的密碼。通過不同網站公布的已泄露密碼整合的密碼字典發現，用戶密碼存在重復，因此，密碼字典數據去重對構建面向暴力破解密碼字典的密碼集合研究具有重要意義。

1 數據去重研究現狀

計算機信息數據的海量增長帶來了重復數據的指數級增長。中國知網上檢索“數據去重”、“重復數據刪除”等關鍵詞，發現其在相似文檔檢測[1]、海量圖片處理[2]、信息安全[3]和移動終端通訊錄[4]等方面研究較多。而在中國知網上檢索“數組去重算法”去重，發現幾乎沒有相關研究，也缺乏海量數據去重方面的研究。

文獻[1]提供了一種文本去重檢測方法，主要包括復制檢測和語義檢測，其主要內容是根據網頁文章長度取出除去停用詞后的短文本，即文章的指紋長度，使用綜合權值打分標準。文獻[1]得出結論如下：無論是原本的LCS（Longest Common Subsequence）還是改進后所得到的文檔集合都優于VSM（Vector Space Model）。文獻[2]針對圖片具有的數據特征，提取圖片集的特征值，計算任意圖片及其歐氏距離，判斷其是否為相同圖片。文獻[5]通過Mapreduce采用WordCount算法對文本進行鍵值排序，將文本中出現的單詞，按關鍵詞進行統計，實現對重復單詞的去除。該文對WordCount算法進行了探究，實現了單詞不區分大小寫排序和去重，但沒有對去重算法作深入研究，同時也沒有對去重算法作進一步比較。文獻[3]分析了不同群體密碼特征，介紹了一種利用馬爾科夫模型生成專用密碼字典的方法。該文構建密碼字典方法是在泄露密碼預處理和去重的基礎上開展，雖然詳細介紹了如何利用馬爾科夫預測模型構建專用的密碼字典，但并沒有研究密碼字典數據去重算法。

2 密碼字典數據去重

2.1 數組去重算法

（1）直接去重。直接去重是通過遍歷到元素集合，檢測是否是數組重復，存在兩層嵌套遍歷[6]。采用indexOf函數的方法是通過檢測數組在所在元素集中是否存在重復，從原理上也是一種直接去重的方法[7]。

（2）Hash去重。Hash函數，就是用于將數組對象轉換成一個隨機地址空間，數組采取散列表存儲，實現去重引擎以O（1）的時間復雜度來訪問對象的數組屬性。不同的去重引擎使用不同的Hash函數，常見的有MD5、SHA等。所以Hash去重的方式需要唯一ID才可以作為Hash索引，最后通過遍歷Hash索引，去除重復數據。與直接去重算法相比較，Hash索引去重方法需要對原始數據進行操作，建立Hash索引，此ID可以是臨時的，在算法結束時銷毀。Hash去重流程如圖1所示。

2.2 Hadoop集群密碼字典數據去重算法

Hadoop由HDFS和MapReduce兩個核心部件組成，HDFS實現文件的分布式存儲，MapReduce實現數據的分析處理。MapReduce基本思想：將待執行的任務分解成Map（映射）和Reduce（歸約）過程，其中每個過程都是以鍵值（key，value）作為輸入輸出，輸入輸出類型可以選擇。WordCount是通過Hadoop系統統計文檔中每個單詞出現的次數。Map函數檢查文檔，結束標示符為基準，標識出每一個條目，并標識出條目出現的次數為1，并記錄為的鍵值對。Reduce函數以key值為統計，輸出新的< key，value>鍵值對，實現對key出現的頻率進行計數。密碼字典去重的目的主要是實現密碼字典條目的清理，并不需要統計密碼字典中密碼條目出現的次數，只需在Reduce函數中作出修改，將計算詞頻的參數換成置null，就可以達到去重的目的。本研究的實驗環境是基于Hadoop 1.x（Hadoop-1.0.3）的3個計算節點的全分布模式。Hadoop系統集群部署如圖2所示。

2.3 算法時間復雜度

算法的時間復雜度T（n）隨著n增大，T（n）計算公式中，影響最大的就是冪次，其它低冪次和常數項可以忽略。時間復雜度T（n）=O（f（n）），n反映問題的規模，f（n）是一個與n相關的函數表達式。

直接去重時間復雜度每次去重需作1次比較，n個元素需要比較n-1次，在最壞的情況下，其時間復雜度為O（n2）。Hash去重是建立Hash索引進行的一次遍歷去重，其時間復雜度為O（n）。

Hadoop集群密碼字典數據去重算法適用于一定規模的問題，相互依存性不高，能夠分成獨立子文件，相互并行執行。Hadoop集群密碼字典數據去重算法時間復雜度取決于并行執行的線程m和待處理問題規模n，其時間復雜度為O（logmn）。

3 實驗分析

3.1 實驗設置

密碼字典包括testdic1，包含2億條密碼數組，由全涵蓋的8位數字0～9組成密碼字符串的2倍，其所占空間為1.86GB；testdic2包含隨機生成的1萬條密碼數組；testdic3包含隨機生成的100條密碼數組。實驗環境包含1臺桌面計算機和3個計算節點的Hadoop集群運算環境，如表1所示。

3.2 結果分析

實驗結果如表2所示，可以得出如下結論：

Hadoop集群數據去重算法[]集群運算環境[]適合海量數據的處理，如testdic1

（1）單機運行環境適合數據量較小的數據進行處理。由于Windows XP以后的操作系統都是多用戶多任務系統，應用不可能獨占CPU，為了讓應用高效運行，可以提高系統的優先級。

（2）直接去重算法和Hash去重算法各有其應用場合。對于極小數據量的處理，采用直接去重算法，因為直接去重算法不用對數據作預處理，其效率高于Hash去重 算法；對于稍大數據量的處理，采用Hash去重算法，因為Hash去重算法的時間復雜度遠低于直接去重算法，效率更高。

（3）Hadoop集群數據去重算法適合海量數據處理。由于單機運行的操作系統及硬環境限制，許多單機應用不支持GB、PB級數據處理，而HDFS文件系統在大數據處理中具有獨特優勢，因而該算法適合海量數據的處理。

4 結語

本文分析了直接去重算法、Hash去重算法和Hadoop集群數據去重算法各自的適用范圍，通過理論分析計算時間復雜度，同時對算法進行實驗分析，得出根據密碼字典規模選擇去重算法及開發手段。在密碼字典的暴力破解中，基于CPU/GPU的異構計算平臺[8]，一個精簡的密碼字典對于提高破解速度意義較大。去重后的密碼字典，作為字符集合子集，結合馬爾科夫模型，可以作為生成一種面向暴力破解的專用密碼字典的方法[3]。

參考文獻：

[1] 聶洋.改進算法的文本去重研究[D].北京：北京郵電大學，2011.

[2] 韓逢慶，宋志堅，余銳.海量圖片快速去重技術[J].計算機應用，2016（7）： 17971800.

[3] 劉建.基于專用字典的密碼破解方法研究與應用[D].哈爾濱：哈爾濱工業大學，2015：

[4] 吳朋朋，黃瑋，楊璐皓.移動終端通訊錄數據同步去重算法[C].2013年中國信息通信研究新進展論文集，2013.

[5] 陳靜.基于Hadoop云計算平臺的文本處理算法的研究與改進[J].天津科技，2016（1）：5255.

[6] 關于數組去重的算法[EB/OL].[20161005].https：//www.webtinker.com/article/20434.html.

[7] 從 JavaScript 數組去重談性能優化[EB/OL].[20161006].http：//blog.jobbole.com/33099/.

[8] 盧風順，宋君強，銀福康，等.CPU/GPU協同并行計算研究綜述[J].計算機科學，2011（3）： 59.

（責任編輯：孫 娟）