【IT168 技术】

　　注：本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见：http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案，将会逐步与大家分享，不可错过哦！

　　CUDA ZONE专区：http://cuda.it168.com/

　　CUDA技术论坛：http://cuda.itpub.net

　　这个应用是我在闲暇的时候写着玩的一个应用，网络上关于该应用的研究也很多，不过我还是想说一些我的体会和感受。

　　最近几年，信息安全越来越受到人们的重视，各种信息安全方面的应用层出不穷，各个厂家也在努力为信息安全产品造势。2010 年初发生的Google被入侵事件，使得人们对于信息安全的关注愈加强烈。而关注与信息安全相关的人员都知道，密码在信息保护方面有着不可忽视的作用。

　　本方案中是通过研究暴力破解MD5算法来测试，在利用gpu的大规模并行能力下，如何才能保证密码的安全。

　　密码破解过程中，由于其相互之间依赖性不强，本身就具有并行的潜质，同时入手相对简单，因此，在学习cuda的初期，我就以密码破解为例子，逐渐掌握cuda在并行方面的一些知识。

　　目前破解MD5算法的方法主要有彩虹表和暴力破解两种方式，现分别介绍之。

　　1、彩虹表

　　彩虹表(Rainbow Tables)就是一个庞大的、针对各种可能的字母组合预先计算好的哈希值的集合。有了它可以快速的破解各类密码。他与直接存储明文的hash值不同，在寻找hash 的过程中，需要将hash经过一系列的换算才能寻找到明文，但是相对于暴力破解，其速度提升不仅仅是几倍的问题。

　　2、暴力破解

　　暴力破解就是一个一个的生成明文，然后计算其hash值，与目标hash进行比较，如果相同，则找到了相应的明文。暴力破解不需要存储空间，但计算速度很慢。

　　并行化设计：

　　这里介绍两中方式下的破解比较：

　　1、彩虹表：由于彩虹表破解方式下，需要将彩虹表读入内存。而在这个过程中硬盘读取的速度成为彩虹表破解的瓶颈之一。另外一个瓶颈是在使用gpu进行破解时，从内存传输数据到显存的过程中的，PCIE 的带宽的限制，

　　在实际测试的过程中，发现了以下现象。

　　第一、如果程序不做任何优化，并行的效果体现就不太明显，而且由于程序需要用到大量的显存，但是在gpu中的shared memory和 constant memory 较少，大量的数据存储在global memory和 local memory中，效率导致速度与直接使用cpu的彩虹表相比，性能并没有大的提升。

　　第二、采取合理的算法，对数据的存储进行优化过后，程序的瓶颈就体现出来了，即内存和显存之间的数据拷贝问题，如何提高数据拷贝的速度，是突破数据拷贝瓶颈的关键。

　　2、暴力破解：暴力破解过程则没有内存限制和PCIE传输速度的限制。但其瓶颈则在于并行的规模，已经如何并行才能最大化利用GPU的特性。

　　在实际测试的过程中，有如下问题。

　　第一，在使用暴力破解时，需要生成明文。而明文的生成算法需要用到除法操作，一般情况是采用整数除法操作，但是由于gpu的实际机制的原因，整数除法是会先转成单精度的，等计算结果完成后，再转成整数。这成为明文生成算法的一个瓶颈。后来我将变量值由整数转换为单精度，效率一下提高了20%左右。

　　第二、暴力破解过程中记录当前计算位置的数据的传递，如果采用整数传递，则无法合理的判断当前计算的长度，因此。我通过将数据绑定到纹理，通过纹纹理的缓冲机制，能大幅度提高数据的存取速度。

　　在程序完成后，我简单的做了一个对比，在INTEL CORE I7 服务器版和 tesla c1060上做比较，测试结果是 单个cpu的速度在 70~100 M 明文hash 每秒，而在tesla c1060上的速度则是370~ 450 M明文hash每秒，性能是cpu的四倍以上。

　　当然，由于我写的程序只是实验性质的，所以程序并没有做大的优化，目前世界上最快的md5算法据说能达到680~700M 明文hash每秒。

　　我写这个程序的目的，一方面是想学习cuda编程，另一方面也是通过这篇文章，告诉大家，在大家的日常生活中，密码的设计应该尽可能的复杂一点，不然很容易被别人破解出来的。