陸浩 盧軍 修榕康

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

關鍵詞 數(shù)據(jù)去重；密碼字典；暴力破解

DOI DOI： 10.11907/rjdk.162429

中圖分類號： TP312

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

0 引言

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

1 數(shù)據(jù)去重研究現(xiàn)狀

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

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

2 密碼字典數(shù)據(jù)去重

2.1 數(shù)組去重算法

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

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

2.2 Hadoop集群密碼字典數(shù)據(jù)去重算法

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

2.3 算法時間復雜度

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

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

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

3 實驗分析

3.1 實驗設置

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

3.2 結果分析

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

Hadoop集群數(shù)據(jù)去重算法[]集群運算環(huán)境[]適合海量數(shù)據(jù)的處理，如testdic1

（1）單機運行環(huán)境適合數(shù)據(jù)量較小的數(shù)據(jù)進行處理。由于Windows XP以后的操作系統(tǒng)都是多用戶多任務系統(tǒng)，應用不可能獨占CPU，為了讓應用高效運行，可以提高系統(tǒng)的優(yōu)先級。

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

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

4 結語

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

參考文獻：

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

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

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

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

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

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

[7] 從 JavaScript 數(shù)組去重談性能優(yōu)化[EB/OL].[20161006].http：//blog.jobbole.com/33099/.

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

（責任編輯：孫 娟）