密码字典数据去重算法研究
2017-04-18陆浩卢军修榕康
陆浩 卢军 修榕康
摘要 对直接去重算法、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，并记录为
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.
（责任编辑：孙 娟）
