分布式系统中的一种特殊规格字符集分片算法

黄颖臻　朱弘

摘要：通常使用分布式系统来处理网络安全产品的口令算法测试，但基于一种特殊规格的密码字符集（密码的每一位的字符集都有不同的约定），一般需要先生成字典处理，效率低下；文章通过建立一种快速分片算法，使用了一系列的进制转换方法以及掩码对应法，找到这种密码字符集的潜在规律，绕过I/O效率低下的问题；通过实验将传统分片法与本算法对比，显示本算法的速度不随字符空间的增大而增大，整体性能是传统方法的3～600倍。完全可替代传统方法。

关键词：分布式系统；密码；分片；安全；穷举；口令算法

中图分类号：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]分布式计算机系统是一种计算机硬件的配置方式和相应的功能配置方式，它是将多种类型的电脑或者计算实体通过互联网络联系起来，利用专用的软件使之构成逻辑上统一的可协同工作的系统，因此具有高度的内聚性和透明性（高內聚性是指各实体并行处理单个任务，内部联系紧密，协调性好；透明性是指用户在利用分布式系统处理任务时感觉不到有多台设备运行，也不用关心各设备的物理位置。）

正是由于分布式系统的特性，从而要求系统能对不同的种类的任务进行分片（将大的任务通过算法分割成多个较小的子任务），由分布式调度程序将这些任务分片分配到个计算实体进行并行处理。[2-3]因此对待不同的计算任务都有相应的任务分片模型算法，分片程序一般在一台独立的电脑上处理，算法的性能将直接影响到整个任务执行的效率。

1 算法描述

1.1 算法提出的背景

在安全领域，一个应用产品完工后，需要进行安全测试，其中有一项是对该产品的认证模块应用穷举法进行密码探测，以验证认证密钥算法的安全性。[4]普通的穷举算法需定义密码长度，字符集，[5]根据n进制掩码算法进行分片（扩展了传统十进制转二进制的算法），例如：密码长度为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）根据掩码和字符集的关系，得出字符串的范围为：eeee～etee；

5）应用3进制的加法，可得到下一组的起始掩码为：上一分片的起始掩码+偏移量1，结束掩码为：本次分片的起始掩码+偏移量9；结果为：{0，1，0，1}～{0，2，0，1}；

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

在实际应用中，会出现一些特殊规格的字符集，密码的每一位都有不同的定义，例如：第一位的字符集为abc，第二位的字符集为47890，第三位的字符集为z，第四位的字符集为gh，如果按照常规的穷举算法，要将字符集整合为04789abcghz，那么4位的密码空间为114=14641，而实际的密码空间为5*5*1*2=50，二者相差近300倍。

目前针对上述情况的做法是编写一段脚本代码，使用嵌套循环遍历来生成一部文本类型的密码字典，然后通过文件分割工具将大字典分成较小的字典片，分发给分布式系统进行计算。这种方法生成字典的效率取决于I/O的速度，并且步骤繁琐，尤其是生成较大的字典时，将成为整个系统的瓶颈。

因此研究出一种基于这种特殊规格的字符集分片法，目的是绕开生成字典的I/O损耗，将大大提高分布式系统的工作效率。

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位的进制数）得到商d1和余数r1，将d1/4（4为密码第三位的进制数），得到d2和r2，将d2/3（3为密码第二位的进制数）得到d3和r3，d3/2（2为密码第一位的进制数）得到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#编写，此为未经优化的代码，仅为说明本算法的基本工作流程及核心思想：

图2 核心算法

1.4 实验及数据

1.4.1 实验环境

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亿的任务，分片数量动态设定为1千、1万、10万、100万，分别用传统的遍历方法和本算法进行分片计算。

1.4.3 实验目标

比较2种方法生成的分片是否一致；

比较2种方法各自消耗的时间；

1.4.4 实验数据

经测试，2种方法所得的分片内容完全相同，但处理性能上有明显差异：

传统方法稳定性差，时间随着分片数与密码空间的增加而增加；

本算法的计算时间基本与密码空间的大小无关，随分片数量的增加而呈线性增加趋势；

从计算时间上来看，本算法时间远远低于传统方法，性能为传统方法的3～600倍，并且当密码空间逐渐增大时差距将也来越大；

因此，本次研究的算法的结果正确，执行质量高，可完全取代传统方法，应用一些异步处理方法可提高分布式系统的调度能力。

实验数据如表1所示。

表1 实验数据比较

[任务＼&传统遍历方法时间 （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 结束语

本算法的在实际应用中，确实大大提高了系统执行效率，在不同的场景下应用，预计也能取得较好的效果，譬如多线程密码字典生成，分布式密码字典生成等，但算法还存在一定的缺陷，例如在计算密码空间时，当结果超出double型的范围时，将产生溢出；在数值越来越大的时候，除法运算或取模运算将产生较大的时间损耗；这些缺陷将在今后的工作中逐步优化，以提升性能。

参考文献：

[1] George Coulouris. Distributed System Concepts and Design[M]. 金蓓弘，译.3版. 北京： 机械工业出版社， 2004.

[2] 林青， 代杰. 分布式计算现状及关键技术研究[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#开发实战1200例[M]. 北京： 清华大学出版社， 2011.

[8] 万海 分布式计算实验教程[M]. 北京： 机械工业出版社， 2012.