陸浩 盧軍 修榕康

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

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

DOI DOI： 10.11907/rjdk.162429

中圖分類號(hào)： TP312

文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào) 文章編號(hào)： 16727800（2017）002005702

0 引言

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

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

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

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

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

2.1 數(shù)組去重算法

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

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

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

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

2.3 算法時(shí)間復(fù)雜度

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

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

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

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

3.2 結(jié)果分析

實(shí)驗(yàn)結(jié)果如表2所示，可以得出如下結(jié)論：

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

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

（2）直接去重算法和Hash去重算法各有其應(yīng)用場(chǎng)合。對(duì)于極小數(shù)據(jù)量的處理，采用直接去重算法，因?yàn)橹苯尤ブ厮惴ú挥脤?duì)數(shù)據(jù)作預(yù)處理，其效率高于Hash去重 算法；對(duì)于稍大數(shù)據(jù)量的處理，采用Hash去重算法，因?yàn)镠ash去重算法的時(shí)間復(fù)雜度遠(yuǎn)低于直接去重算法，效率更高。

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 聶洋.改進(jìn)算法的文本去重研究[D].北京：北京郵電大學(xué)，2011.

[2] 韓逢慶，宋志堅(jiān)，余銳.海量圖片快速去重技術(shù)[J].計(jì)算機(jī)應(yīng)用，2016（7）： 17971800.

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

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

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

[6] 關(guān)于數(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] 盧風(fēng)順，宋君強(qiáng)，銀?？?，等.CPU/GPU協(xié)同并行計(jì)算研究綜述[J].計(jì)算機(jī)科學(xué)，2011（3）： 59.

（責(zé)任編輯：孫 娟）