分布式系統(tǒng)中的一種特殊規(guī)格字符集分片算法

黃穎臻　朱弘

摘要：通常使用分布式系統(tǒng)來處理網(wǎng)絡安全產品的口令算法測試，但基于一種特殊規(guī)格的密碼字符集（密碼的每一位的字符集都有不同的約定），一般需要先生成字典處理，效率低下；文章通過建立一種快速分片算法，使用了一系列的進制轉換方法以及掩碼對應法，找到這種密碼字符集的潛在規(guī)律，繞過I/O效率低下的問題；通過實驗將傳統(tǒng)分片法與本算法對比，顯示本算法的速度不隨字符空間的增大而增大，整體性能是傳統(tǒng)方法的3～600倍。完全可替代傳統(tǒng)方法。

關鍵詞：分布式系統(tǒng)；密碼；分片；安全；窮舉；口令算法

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2015）20-0174-03

A Fragmentation Algorithm for Character Set of a Special Model on Distributed System

HUANG Ying-zhen， ZHU Hong

（The Third Research Institute of Ministry of Public Security， Shanghai 201204， China）

Abstract： Typically distributed system is used to deal with the password algorithm in network related security products. However if it is based on a password character set on a particular standard （e.g Every character set in the password follows different convention）， generally it has to be handled by first generating a dictionary， which is inefficient； this article introduce a method which involves establishing a rapid fragmentation algorithm，using binary conversion method and the relation of mask，the law was found that resolved the I/O efficiency ，the speed of which remain unchanged as the gap between characters gets bigger. By comparison in experiments， speed of algorithm is 3 to 600 times better then traditional method ，it proves to be able to be applied to replace the traditional method.

Key words：distributed system； password； fragmentation； security；exhaustive； password algorithm

[1]分布式計算機系統(tǒng)是一種計算機硬件的配置方式和相應的功能配置方式，它是將多種類型的電腦或者計算實體通過互聯(lián)網(wǎng)絡聯(lián)系起來，利用專用的軟件使之構成邏輯上統(tǒng)一的可協(xié)同工作的系統(tǒng)，因此具有高度的內聚性和透明性（高內聚性是指各實體并行處理單個任務，內部聯(lián)系緊密，協(xié)調性好；透明性是指用戶在利用分布式系統(tǒng)處理任務時感覺不到有多臺設備運行，也不用關心各設備的物理位置。）

正是由于分布式系統(tǒng)的特性，從而要求系統(tǒng)能對不同的種類的任務進行分片（將大的任務通過算法分割成多個較小的子任務），由分布式調度程序將這些任務分片分配到個計算實體進行并行處理。[2-3]因此對待不同的計算任務都有相應的任務分片模型算法，分片程序一般在一臺獨立的電腦上處理，算法的性能將直接影響到整個任務執(zhí)行的效率。

1 算法描述

1.1 算法提出的背景

在安全領域，一個應用產品完工后，需要進行安全測試，其中有一項是對該產品的認證模塊應用窮舉法進行密碼探測，以驗證認證密鑰算法的安全性。[4]普通的窮舉算法需定義密碼長度，字符集，[5]根據(jù)n進制掩碼算法進行分片（擴展了傳統(tǒng)十進制轉二進制的算法），例如：密碼長度為4位，字符集為[e，t，y]， 每個分片的長度為10個密碼，處理流程為：

1）字符集為3個字符，設計4位長度的掩碼{θ，θ，θ，θ}，θ的取值范圍為[0，1，2]，對應的字符集為ety，這樣就把一個無序的字符集轉換為一個有序的3進制掩碼；

2）算出2個偏移量的掩碼：1 {0，0，0，1}、9 {0，1，0，0}；

3）第一個分片的起始掩碼為{0，0，0，0}～{0，1，0，0}；

4）根據(jù)掩碼和字符集的關系，得出字符串的范圍為：eeee～etee；

5）應用3進制的加法，可得到下一組的起始掩碼為：上一分片的起始掩碼+偏移量1，結束掩碼為：本次分片的起始掩碼+偏移量9；結果為：{0，1，0，1}～{0，2，0，1}；

6）以此類推，得到全部的分片：eeee～etee、etet～eyet、eyey～teey、tete～ttte、yyyy；

在實際應用中，會出現(xiàn)一些特殊規(guī)格的字符集，密碼的每一位都有不同的定義，例如：第一位的字符集為abc，第二位的字符集為47890，第三位的字符集為z，第四位的字符集為gh，如果按照常規(guī)的窮舉算法，要將字符集整合為04789abcghz，那么4位的密碼空間為114=14641，而實際的密碼空間為5*5*1*2=50，二者相差近300倍。

目前針對上述情況的做法是編寫一段腳本代碼，使用嵌套循環(huán)遍歷來生成一部文本類型的密碼字典，然后通過文件分割工具將大字典分成較小的字典片，分發(fā)給分布式系統(tǒng)進行計算。這種方法生成字典的效率取決于I/O的速度，并且步驟繁瑣，尤其是生成較大的字典時，將成為整個系統(tǒng)的瓶頸。

因此研究出一種基于這種特殊規(guī)格的字符集分片法，目的是繞開生成字典的I/O損耗，將大大提高分布式系統(tǒng)的工作效率。

1.2 算法模型論述

例：一個4位長度的密碼，第一位字符集為（a，b），第二位字符集為（d，e，f），第三位字符集（1，4，8，3），第四位字符集（9，z，x，Y，c），每個分片包含30個密碼。處理的算法如下：

1）設定掩碼{θ1，θ2，θ3，θ4}：θ1（ab分別用01代表，2進制），θ2（def分別用012代表，3進制），θ3（1438分別用0123代表，4進制），θ4（9zxYc分別用01234代表，5進制）；

2）每個分片30個密碼即0～29，將29用掩碼表示；算法為：將29/5（5為密碼的第4位的進制數(shù)）得到商d1和余數(shù)r1，將d1/4（4為密碼第三位的進制數(shù)），得到d2和r2，將d2/3（3為密碼第二位的進制數(shù)）得到d3和r3，d3/2（2為密碼第一位的進制數(shù)）得到d4和r4；

3）{r4，r3，r2，r1}即為得出的掩碼；

4）將{r4，r3，r2，r1}所對應的字符拼接起來即完成了第一組分片，本例為：ad19～ae4c

5）同理可得第二個分片為30～59，轉換成掩碼為：{0，1，2，0}～{0，2，3，4}，反復應用上述方法可得到所有的分片字符；下圖表示了算法模型：

圖1 算法模型

1.3 算法核心腳本

[6-7]以下是算法的核心腳本，使用C#編寫，此為未經優(yōu)化的代碼，僅為說明本算法的基本工作流程及核心思想：

圖2 核心算法

1.4 實驗及數(shù)據(jù)

1.4.1 實驗環(huán)境

CPU：Intel Core2 Duo E8400@3.0G RAM：DDR3 4GB HDD：500GB OS：win7 x64 編程語言：C#2012

1.4.2 實驗方法

[8]構造一個密碼空間為1萬、10萬、100萬、1000萬、1億，10億的任務，分片數(shù)量動態(tài)設定為1千、1萬、10萬、100萬，分別用傳統(tǒng)的遍歷方法和本算法進行分片計算。

1.4.3 實驗目標

比較2種方法生成的分片是否一致；

比較2種方法各自消耗的時間；

1.4.4 實驗數(shù)據(jù)

經測試，2種方法所得的分片內容完全相同，但處理性能上有明顯差異：

傳統(tǒng)方法穩(wěn)定性差，時間隨著分片數(shù)與密碼空間的增加而增加；

本算法的計算時間基本與密碼空間的大小無關，隨分片數(shù)量的增加而呈線性增加趨勢；

從計算時間上來看，本算法時間遠遠低于傳統(tǒng)方法，性能為傳統(tǒng)方法的3～600倍，并且當密碼空間逐漸增大時差距將也來越大；

因此，本次研究的算法的結果正確，執(zhí)行質量高，可完全取代傳統(tǒng)方法，應用一些異步處理方法可提高分布式系統(tǒng)的調度能力。

實驗數(shù)據(jù)如表1所示。

表1 實驗數(shù)據(jù)比較

[任務＼&傳統(tǒng)遍歷方法時間 （ms）＼&本算法時間 （ms）＼&1千＼&1萬＼&10萬＼&100萬＼&1千＼&1萬＼&10萬＼&100萬＼&1萬＼&18.72＼&174.7＼&1475.7＼&1772＼&18.72＼&177.8＼&1781.5＼&1783＼&10萬＼&18.72＼&179.4＼&1776＼&17707＼&18.72＼&177.8＼&1789.3＼&17883＼&100萬＼&29.64＼&190.3＼&1789＼&17872＼&17.16＼&180.9＼&1797.1＼&17968＼&1000萬＼&127.92＼&310.4＼&1923＼&18036＼&18.72＼&179.4＼&1803.3＼&18052＼&1億＼&1271＼&1277＼&3077＼&19248＼&18.72＼&180.9＼&1811.1＼&18097＼&10億＼&12726＼&12754＼&12804＼&30788＼&18.72＼&182.5＼&1815.8＼&18167＼&]

2 結束語

本算法的在實際應用中，確實大大提高了系統(tǒng)執(zhí)行效率，在不同的場景下應用，預計也能取得較好的效果，譬如多線程密碼字典生成，分布式密碼字典生成等，但算法還存在一定的缺陷，例如在計算密碼空間時，當結果超出double型的范圍時，將產生溢出；在數(shù)值越來越大的時候，除法運算或取模運算將產生較大的時間損耗；這些缺陷將在今后的工作中逐步優(yōu)化，以提升性能。

參考文獻：

[1] George Coulouris. Distributed System Concepts and Design[M]. 金蓓弘，譯.3版. 北京： 機械工業(yè)出版社， 2004.

[2] 林青， 代杰. 分布式計算現(xiàn)狀及關鍵技術研究[J]. 消費電子：理論版，2013（5）.

[3] 胡金初. 分布式計算中的一個任務分配算法[C]. 北京： 2003中國計算機大會，2003.

[4] 曹麗梅， 王春航. 破揭密碼的窮舉方法分析及應對措施[J]. 科技信息：學術研究，2008（8）.

[5] 王愛英 計算機組成與結構[M]. 北京： 清華大學出版社， 2001.

[6] 煞特洛. 暴力破解算法[EB/OL]. http：//www.oschina.net/code/snippet_183849_10691.

[7] 王小科. C#開發(fā)實戰(zhàn)1200例[M]. 北京： 清華大學出版社， 2011.

[8] 萬海 分布式計算實驗教程[M]. 北京： 機械工業(yè)出版社， 2012.