（计算机科学与技术专业论文）带随机数md5破解算法的gpu加速与优化.pdf

g p ua c c e l e r a t i o na n d o p i t i m i z a t i o no ft h e d e c r y p t i o na l g o r i t h m o fm d 5w i t hs a l t c a n d i d a t e ：w e n gj i e a d v i s o r ：p r o f y a n gc a n - q u n at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h e r e q u i r e m e n t s f o rt h ep r o f e s s i o n a ld e g r e eo fm a s t e ro fe n g i n e e r i n g i nc o m p u t e r t e c h n o l o g y g r a d u a t es c h o o lo fn a t i o n a lu n i v e r s i t yo fd e f e n s et e c h n o l o g y c h a n g s h a ，h u n a n ，p r c h i n a m a r c h ，2 0 1 0 脚9m 5乃 舢1舯y 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：堂随扭数塑焦鲤篡洼鲍垒业盘逮量选焦 学位论文作者签名：一鱼复遗 日期：z 矽年巧月箩日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：堂堕扭熬迪璧鲤篡洼鲍鱼胆垄逮生选丝 学位论文作者签名： 作者指导教师签名： 日期：z 杉年月5 - 日 日期：加。年6 月j 日 国防科学技术大学研究生院工程硕士学位论文 目录 摘要i a b s t r a c t i i i 第一章引言1 1 1课题背景1 1 2 研究现状。2 1 2 1g p u 通用计算3 1 2 2g p u 加速m d 5 破解4 1 3 本文研究内容和创新一6 1 4 论文结构7 第二章g p u 相关知识与m d 5 算法分析8 2 1g p u 系统结构特点和编程模型8 2 1 1n v i d i ag t 2 0 0 结构和c u d a 编程模型8 2 1 2a m dr v 7 7 0 架构和b r o o k + 编程语言9 2 1 3o p e n c l 标准一1 0 2 2 m d 5 算法分析一1 4 2 2 1m d 5 算法1 4 2 2 2 带随机数m d 5 算法1 6 2 2 3 带随机数m d 5 破解算法1 8 2 3 小结1 8 第三章基于g p u 实现带随机数m d 5 破解算法2 0 3 1 系统级设计2 0 3 1 1 异构计算分析2 0 3 1 2 算法分析与任务分割2 2 3 2 攻击密码生成2 4 3 2 1 攻击密码生成算法2 4 3 2 2 使用o p e n c l 实现算法2 5 3 2 3 分轮生成密码2 6 3 3散列码生成2 7 3 4 散列码匹配2 7 3 4 1 散列码匹配在g p u 上实现2 8 3 4 2 散列码匹配在c p u 上实现一2 8 第1 页 国防科学技术大学研究生院t 程硕十学位论文 3 5 小结2 8 第四章使用o p e n c l 加速破解算法性能优化技术2 9 4 1 最小化数据传输2 9 4 2 全局内存访问优化3 0 4 2 1 减少全局内存访问3 0 4 2 2 全局内存对齐访问31 4 3 局部内存存取优化3 3 4 4 使用图形渲染管线加速存取3 5 4 4 1 硬件基础3 6 4 4 2 使用图形渲染管线优化算法3 6 4 5 功能性优化3 7 4 6 小结3 7 第五章测试与分析3 9 5 1测试环境3 9 5 2 性能测试与分析4 0 5 2 1 不同匹配方式性能对比4 0 5 2 2 最小化数据传输性能对比4 1 5 2 3 优化全局内存访问性能测试4 1 5 2 4 优化局部内存性能测试4 2 5 2 5 使用图形渲染管线性能测试4 3 5 3 对比测试与分析4 3 结束语4 5 6 1工作总结4 5 6 2展望4 6 致 射4 7 参考文献4 8 作者在学期间取得的学术成果5 0 第1 i 页 国防科学技术大学研究生院工程硕士学位论文 表目录 表2 1 主机和设备上内存分配和访问能力表1 1 表3 1m d 5 破解算法中各任务执行时间统计表2 2 表4 1g p u 存储单元特征表3 6 第1 i i 页 国防科学技术大学研究生院工程硕士学位论文 图目录 图1 1“天河一号 的体系结构图2 图1 2o p e n m p 到c u d a 的转换图【1 9 】3 图1 3 任务包方法示意图4 图2 1g t 2 0 0 体系结构图【2 9 】9 图2 2r v 7 7 0 架构图1 0 图2 3 o p e n c l 平台模型【9 1 1 1 图2 4 o p e n c l 设备架构模型 9 1 1 2 图2 5工作项索引计算方式【9 1 13 图2 6 按位操作示意图1 5 图2 7 计算核心单次循环示意图1 5 图2 8四轮操作示意图15 图2 9 初始化输入数据算法- 1 6 图2 1 0 数据填充算法1 7 图2 1 1增加计算复杂性算法17 图2 1 2 强力攻击方法流程图1 8 图3 1c p u 与g p u 内部结构对比图2 1 图3 2 破解算法任务分割示意图。2 3 图3 3基于g p u 的带随机数m d 5 破解算法流程图。2 3 图3 4 攻击密码生成阶段数据流图。2 4 图3 5 攻击密码生成规则示意图。2 5 图3 6内核函数定义示意图2 6 图3 7 攻击密码生成算法示意图2 6 图3 8 控制不同位数攻击密码生成示意图2 8 图4 1 o p e n c l 与g t 2 0 0 内存模型映射图。3 0 图4 2工作项访问全局内存示意图。3l 图4 3 工作项串行访问全局内存示意图3 2 图4 4非序列化工作项对齐访问示意图3 2 图4 5 非序列化工作项不对齐访问示意图。3 2 图4 6 序列化工作项不对齐访问全局内存示意图3 3 图4 7 类型特性限定结构示意图3 3 图4 8c u d a 的内存结构图1 4 1 3 4 图4 9 无存储体冲突的访问示意图3 5 第1 v 页 国防科学技术大学研究生院工程硕士学位论文 图4 1 0 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 有存储体冲突的访问示意图3 5 在c p u 和g p u 上实现散列码匹配对比4 0 采用最小化数据传输前后性能对比图一4 1 减少全局内存访问前后性能对比图4 1 采用对齐访问前后性能对比图一4 2 采用局部内存优化前后性能对比图一4 2 使用图形渲染管线优化前后性能对比图4 3 本文程序与j t r 性能对比图4 4 第v 页 国防科学技术大学研究生院工程硕+ 学位论文 第v i 页 国防科学技术大学研究生院工程硕士学位论文 摘要 在m d 5 算法中加入随机数进行运算可以有效的防止字典攻击，同时增加算法 的复杂性和不可逆性。带随机数的m d 5 ( m d 5w i t hs a l t ) 算法在f r e e b s d 等操作系 统中广泛用于权限管理，因而验证该算法的安全性十分重要。近年来使用g p u 构 建的异构平台性能不断提升，如国内首台基于g p u 异构并行架构的巨型机天河一 号峰值可达1 2 0 6 p f l o p s 。o p e n c l ( o p e nc o m p u t i n gl a n g u a g e ，开放计算语言) 标准 的发布也大大提高了g p u 程序的可移植性和可扩展性。使用强力攻击( b r u t e f o r c e a t t a c k ，亦称暴力攻击) 对带随机数的m d 5 算法进行攻击成为可能。 本文首先分析了传统体系结构上带随机数m d 5 的破解算法，对算法中任务进 行划分以便映射到主机和g p u 上；然后使用o p e n c l 实现了基于g p u 的异构平 台上的破解算法；最后针对特定的g p u 平台对破解程序进行了优化。本文完成的 主要工作如下： 1 、设计和实现了基于g p u 的带随机数m d 5 破解算法。本文对传统体系结构 上的破解算法进行分析，将计算密集的任务如生成散列码任务在g p u 上实现，将 拥有复杂控制的任务如初始化参数等在主机端进行实现；考虑各任务间的数据传 输，如攻击密码生成和散列码生成之间存在大量数据交换，因此将攻击密码生成 也在g p u 上实现；使用实验评测的方式对其他任务进行评测以决定其实现方式， 如散列码匹配任务。根据以上任务的分析和o p e n c l 语言的特点，本文使用o p e n c l 实现了基于g p u 的带随机数m d 5 破解算法。 2 、针对破解程序运行时g p u 存储空间不足问题，设计和实现了攻击密码多 轮生成算法。随着密码位数增加密钥空间不断增大，g p u 上的存储单元已不足以 存储攻击密码生成阶段产生的密码以及散列码生成阶段所产生的散列码。攻击密 码多轮生成算法将密码生成与o p e n c l 中工作项的全局索引号一一对应，每轮生 成根据g p u 的存储空间申请足够多的工作项进行密码生成；为了使各轮生成分布 均匀，算法在主机端对生成过程进行记录，并作为控制参数传输给o p e n c l 内核； 为了减少主机和g p u 的数据传输，主机端通过模拟上一轮g p u 生成算法获得标 记点并传递给下一轮生成。 3 、针对破解算法的具体特点，使用多种存储访问优化方法来进行相应的优化。 通过优化全局内存的访问来对程序进行优化，在内核代码中使用立即数赋值的方 法以减少全局内存的访问，可以获得5 的性能提升，使用o p e n c l 的类型限定特 性，对数据结构的存储方式进行控制，使其对齐全局内存的组织方式，可以获得 4 3 3 的性能提升；通过设置工作项的个数为3 2 的倍数以优化局部内存访问，获 得了8 9 的性能提升；通过使用图形渲染管线硬件结构存储访问频繁的少量数据， 第i 页 国防科学技术大学研究生院- t 程硕士学位论文 获得了6 7 1 的性能提升。 本文对最终实现的算法进行了测试，测试结果表明g p u 对破解算法有明显的 加速效果。在i n t e lq 8 2 3 0 四核c p u ( 2 3 g h z ) 和一片n v i d i ag t 2 0 0g p u 组成的 异构平台上，本文程序获得了1 8 3 倍于著名破解软件j o h nt h er i p p e r ( j t r ) 在相 同c p u 平台上四个线程的破解速度。 主题词：o p e n c l 带随机数的m d 5 算法g p u 强力攻击 第i i 页 国防科学技术大学研究生院工程硕士学位论文 a b s t r a o t a d d i n gs a l tt ot h ep a s s w o r d sb e f o r eh a s h i n gt h e mc a ni n c r e a s et h ec o m p l e x i t ya n d i r r e v e r s i b l eo ft h em d 5 a l g o r i t h m t h em d 5 w i t hs a l ti sw i d e l yu s e di na u t h o r i z a t i o no f o p e r a t i n gs y s t e m ss u c ha sf r e e b s d t h u sv e r i f y i n gt h ea l g o r i t h m ss e c u r i t yi sv e r y i m p o r t a n t t h e s ed a y st h ep e r f o r m a n c eo fg p u - b a s e dh e t e r o g e n e o u sp l a t f o r m si se v e r i n c r e a s i n g t a k et h et i a n h e ia sa ne x a m p l e i ti s b a s e do nt h eh e t e r o g e n e o u s a r c h i t e c t u r e ，w h o s ep e a kp e r f o r m a n c ei su pt o1 2 0 6 p f l o p s o p e n c ls t a n d a r da l s o g r e a t l ye n h a n c e st h ep o r t a b i l i t ya n ds c a l a b i l i t yo fg p up r o g r a m s u s i n gb r u t ef o r c e a t t a c kt oc r a c kt h em d 5w i t hs a l tb e c a m ep o s s i b l e i nt h i sp a p e rw ef i r s ta n a l y z et h em d 5w i t hs a l to nt h et r a d i t i o n a lc p u - b a s e d a r c h i t e c t u r ea n ds p l i tt h et a s k so ft h ea l g o r i t h mi no r d e rt om a pt h e ms e p a r a t e l yo n t ot h e h o s ta n dt h eg p u f i n a l l yw eu s eo p e n c ll a n g u a g et oi m p l e m e n ta n do p t i m i z et h e c r a c k i n ga l g o r i t h mo n ag p u - b a s e dh e t e r o g e n e o u sp l a t f o r m o u rw o r k sa r ea sf o l l o w s ： f i r s t l y ，w ed e s i g na n dr e a l i z eag p u - b a s e da l g o r i t h mt oc r a c kt h em d 5w i t hs a l t w ea n a l y z et h ea l g o r i t h mo nt h et r a d i t i o n a la r c h i t e c t u r e b a s e do nt h ea n a l y s i sw e i m p l e m e n tt h o s ec o m p u t i n g - i n t e n s i v et a s k s ，s u c ha sh a s hc o d eg e n e r a t i n go nt h eg p u ， t h o s ec o n t r o la n di n i t i a l i z a t i o np a r a m e t e r st a s k so nt h ec p u t a k i n gi n t oa c c o u n tt h e c o s t so fd a t at r a n s m i s s i o n ，t h ep a s s w o r dg e n e r a t i n gt a s ki sa l s oi m p l e m e n t e do nt h e g p u b a s e do ne x p e r i m e n t a le v a l u a t i o nw ed e c i d et o i m p l e m e n tt h eh a s hc o d e m a t c h i n gt a s ko nt h ec p u b a s e do nt h ea b o v et a s ka n a l y s i sa n do p e n c ll a n g u a g e f e a t u r e s ，w ei m p l e m e n tt h ea l g o r i t h m s e c o n d l y ，w ed e s i g na n dr e a l i z eam u l t i r o u n d sp a s s w o r dg e n e r a t i o na l g o r i t h mt o s o l v et h eg p um e m o r ye x h a u s tp r o b l e mw h i l et h ep r o g r a mi sn m n i n g w h i l et h ed i g i t o fp a s s w o r di n c r e a s e s ，t h ek e ys p a c ei si n c r e a s i n gs u c ht h a tt h eg p um e m o r yi sn o l o n g e rs u f f i c i e n tt os t o r et h ep a s s w o r d sg e n e r a t e dd u r i n gt h ep a s s w o r dg e n e r a t i n g p r o g r e s s w em a k ep a k so fp a s s w o r d sa n dt h eo p e n c li t e mg l o b a li n d e xn u m b e r d u r i n ge a c hr o u n dw ea p p l ya sm a n yn u m b e ro fw o r ki t e m sf o rp a s s w o r dg e n e r a t i o n c o n s i d e r e da st h em e m o r yc a nb ef u l f i l l e d t om a k et h eg e n e r a t i n ge v e n l yd i s t r i b u t e d ， w ed e s i g nh o s t s i d ea l g o r i t h mt or e c o r dt h eg e n e r a t i o np r o c e s s ，a n dt r a n s m i ti tt ot h e o p e n c lk e r n e la sac o n t r o lp a r a m e t e r w ea l s oo b t a i nm a r k e dp o i n to nt h eh o s t - s i d et o r e d u c et h eh o s ta n dg p ud a t at r a n s f e r t h i r d l y ，w eu s es e v e r a lm e m o r ya c c e s s i n go p t i m i z a t i o nm e t h o d st oo p t i m i z et h e p r o g r a ma c c o r d i n gt ot h es p e c i f i cf e a t u r e so ft h ep r o g r a m w ef i r s t l yo p t i m i z et h e g l o b a lm e m o r ya c c e s s b yu s i n gi m m e d i a t ea s s i g n m e n tm e t h o di nt h ek e r n e l w eg e t5 p e r f o r m a n c ei n c r e a s e ；b yu s i n gg l o b a lm e m o r ya l i g na c c e s s i n gm e t h o dw eo b t a i n4 3 3 o ft h ep e r f o r m a n c ei m p r o v e m e n t w ea l s oo p t i m i z el o c a lm e m o r ya c c e s sb ys e t t i n g n u m b e ro fw o r ki t e m st h em u l t i p l e so f3 2 w h i c hl e a dt oa n 8 9 p e r f o r m a n c e 第i i i 页 国防科学技术大学研究生院工程硕士学位论文 i m p r o v e m e n t b yu s i n go fg r a p h i c sr e n d e r i n gp i p e l i n eh a r d w a r ea r c h i t e c t u r et os t o r et h e f r e q u e n c yu s e dd a t a , t h ep r o g r a mo b t a i n6 7 1 p e r f o r m a n c ei n c r e a s e f i n a l l y ，w ec o m p a r eo u rp r o g r a m 谢t ht h ef a m o u sd e c r y p t i o ns o t t w a r e ，j o h nt h e r i p p e r o u rc o d er u n s18t i m e sf a s t e ro nan v i d i ag t 2 0 0g p u w i t hi n t e lq 8 2 3 0 q u a d - c o r ec p u ( 2 3 g h z ) t h a nj t rr u n n i n go nt h es a m ec p u o n l yp l a t f o r m k e yw o r d s ：o p e n c l m d 5w i t hs a l tg p ub r u t e f o r c ea t t a c k 第i v 页 国防科学技术大学研究生院工程硕士学位论文 第一章引言 近年来，g p u ( g r a p h i c sp r o c e s s i n gu n i t ，图形处理器) 的性能以大大超过摩尔定 律的速度发展，与此同时，使用g p u 进行通用计算的编程模型也在不断发展。越 来越多的研究者将g p u 用于高性能计算领域，2 0 0 9 年t o p 5 0 0 中首次出现基于g p u 异构架构的超级计算机【1 1 。借助g p u 的计算能力，以往一些依靠算法复杂度和不 可逆性来保持安全性的摘要算法如m d 5 等算法变得不再安全。 1 1 课题背景 九十年代发展起来的g p u 的计算能力现己远高于通用处理器( c p 奶一到两个 量级，并且其发展速度也比描述c p u 速度发展的“摩尔定律 要快【2 j 。此外，g p u 还具有性价比和计算密度高、能耗低等优势，引起了越来越多的关注，并在通用 计算领域得到成功应用。近年来，g p u 的发展呈现两个趋势。一方面，g p u 单卡 的性能不断提升，架构不断更新。a m d 公司在2 0 0 9 年1 1 月发布的r a d e o nh d 5 9 7 0 ， 流处理器个数已经达到了3 2 0 0 个，其单精度浮点运算能力达到了4 6 4 t f l o p s l j j 。 此外，g p u 厂商不断更新现有g p u 的架构，以适应更多高性能计算的要求，如 n v i d i a 推出的f e r m i t 4 1 架构、a m d 推出的c y p r e s s t 5 】架构等。另一方面，应用g p u 的规模在不断扩大，采用基于g p u 异构架构的高性能计算集群开始出现。如2 0 0 9 年1 0 月国防科大发布的国内首台千万亿次计算机“天河一号【6 j ，就是采用基于 g p u 的异构并行系统架构。如图1 1 所示，天河一号的计算阵列由2 5 6 0 个c p u 组成，加速阵列则由2 5 6 0 个h d 4 8 7 0 x 2 组成，其峰值性能达到1 2 0 6 p f l o p s ，在 同年t o p 5 0 0 排名中位居第五位【i j 。 与此同时，g p u 的编程模型处在不断发展的阶段。在早期的g p u 应用中，程 序员通过专门的图形接口调用g p u 进行计算。由于只有顶点处理器和像素片段处 理器两个部件是可编程的，为了调用这些部件，图形处理的大部分过程都需要程 序员指定，这就要求程序员熟悉底层复杂的硬件机制，极大提高了难度。随着g p u 用于通用计算的发展，g p u 厂商推出了更接近传统编程语言的模型如b r o o k + 1 7 j ， c u d a 8 】等。这些编程模型屏蔽了底层的硬件机制，使编程人员只需通过调用这些 接口就可以方便的开发g p u 程序。然而这些编程模型大都限于固定的g p u 平台， 使得开发人员很难通过单独的多平台源码库使用异构c p u 、g p u 和其它类型的处 理器，程序的可移植性受到影响。o p e n c l 【9 】的发布改变了这一状况，它被多家厂 商支持，可以在异构c p u 、g p u 和其它处理器上进行通用目的的并行编程，它使 软件开发者可以更加方便高效的使用异构处理平台，使得异构计算程序编写的复 第1 页 国防科学技术大学研究生院工程硕十学位论文 杂性大大降低。 图1 1“天河一号”的体系结构图 本文基于o p e n c l 模型实现带随机数的m d 5 破解算法，主要出于以下考虑： 首先，随着当前异构并行架构性能不断提高和编程模型的不断成熟，使得原 来被认为是不可能的应用成为现实。安全领域中一些常用算法变得不再安全，m d 5 算法正是其中一种。m d 5 算法【l o j 及其变种带随机数的m d 5 算法( m d 5w i t hs a l t ，亦 称m d 5 加盐算法) 【1 1 1 广泛使用在系统授权、信息保护等方面【1 2 1 ，验证其安全性具 有重要的现实意义。 其次，m d 5 算法及带随机数的m d 5 算法都是依靠计算复杂性和不可逆性增 加其安全性。纵观其加密过程易于并行且访存操作较少，正适合g p u 大量线程并 发执行的特点，因此在g p u 上实现破解算法具有可行性。 目前，越来越多的国内外研究者将目光转向使用g p u 加速通用科学计算的研 究。下一节将介绍国内外学者在g p u 通用计算领域和应用g p u 加速m d 5 的相关 工作。 1 2 研究现状 由于在性能和可编程性上不断进步，现代g p u 已经应用在计算几何【 】、代数 运算【1 4 1 、碰撞检测【1 5 】、偏微分方程1 6 1 、图像处理【1 7 1 、分子动力掣1 8 1 等科学领域中。 本文主要关注的是如何利用g p u 对破解算法进行加速，因此本节首先介绍g p u 在科学计算方面的编程方法和优化技术的相关研究，然后介绍利用g p u 加速m d 5 加密和破解过程的研究。这些研究对本文工作具有指导和借鉴意义。 第2 页 国防科学技术大学研究生院工程硕士学位论文 1 2 1g p o 通用计算 由于g p u 结构迥异于传统通用处理器的架构，因此g p u 的编程模型与传统 编程模型有较大的差异。此外，g p u 拥有复杂的存储结构，影响g p u 程序性能的 因素众多，而g p u 上又缺乏类似传统编程模型中的一些调试工具，因此在g p u 上取得较好的性能非常困难。为了简化编程模型、帮助程序员优化程序，许多研 究者都对此进行了研究。 l e e 等在文【1 9 】中文中提出一种编译框架，采用源到源的翻译方式，将标准 o p e n m p 应用转化为基于c u d a 的g p g p u 程序。这样程序员只要掌握了传统c p u 并行编程模型，就可以将其自动转化为g p g p u 程序，从而降低编程难度。如图 1 2 所示，左图中添加了o p e n m p 指导命令的代码被转化为右图中使用g p u 加速 的代码，s p 4 至s p l 、s p l 至s p 2 之间的代码被分别转化为一段内核代码，每一 次迭代均由g p u 上的一个线程完成。文中还对转化后的程序进行了一系列的优化， 使得程序访问全局内存时更有效。文中用该自动转化程序对j a c o b 和s p m u l ( 稀 疏向量矩阵乘) 进行了转化和优化，获得了5 0 到3 2 8 倍相对于c p u 上串行程序的 加速比。 图1 2o p e n m p 到c u d a 的转换刚1 9 1 b a g h s o r k h i 等在文【2 0 】中提出一种分析模型来预测一个通用程序在g p u 系统上 的性能，既可以用于自动调优，也可以作为工具帮助程序员寻找程序中的性能瓶 颈。文中分析到目前影响g p u 程序性能因素繁多，这些因素相互制约，难以取得 最优。因此文中提出一种基于编译器的性能分析模型，从而量化多种影响g p u 程 序因素，并允许编译器根据分析结果进行优化。文中引入工作流图( w o r kf l o wg r a p h ) 的概念，它是g p u 内核函数中控制流图的扩展，将存储带宽，读延迟，存储对齐 原则等影响性能的因素都量化为权重体现在控制流中。文中还通过符号评价模型 第3 页 国防科学技术大学研究生院工程硕士学位论文 和具体实验得出各因素的权重，从而精确预测不同优化后程序的性能变化趋势。 这些实验包括矩阵乘、f f t 、p r e f i xs u ms c a n 、稀疏矩阵乘等。 伊利诺伊大学厄巴纳香槟分校的s h a n er y o o 等在文【2 l 】中总结了一些使用 c u d a 进行多线程g p u 编程的一些优化原则和性能测试方法。文中研究了g e f o r c e 8 8 0 0g t x 显示卡的处理单元的组织，特点和通用优化准则。他们提出，使用c u d a 编程模型的要点在于同时使用大量线程来最大化的利用g p u 众多的计算核心和隐 藏全局内存的延迟。g e f o r c e8 8 0 0g t x 拥有1 2 8 个执行单元，如果全部利用起来， 需要数以千计的线程。此外，由于对全局内存的存取存在较大的延迟，线程会因 为无法及时获取数据而处于空闲等待的阶段。c p u 解决这一问题的方法在于增加 大量的缓存，而g p u 则与之不同，它使用了超量的线程同时执行来隐藏这一延迟。 因此，保持一个较高的计算存取比率是一个重要的原则。g e f o r c e8 8 0 0g t x 还拥 有寄存器和片上内存等快速存储器，需要合理利用这些存储器来减少对带宽的需 求并尽可能多的执行数据。由于c u d a 编程模型本质上是采用了s i m d ( 单指令流 多数据流) 这样一种形式，因此需要将大量线程分组来避免违反s i m d 原则带来的 性能下降和内存冲突。 综上所述，基于g p u 的通用计算领域的相关研究很多，新的理论和方法更新 迭代也很快。这些研究对克服g p u 通用计算的难点有独到的地方，对本文的工作 有重要的借鉴意义。例如l e e 等将通用处理器上的并行编程模型与g p u 上编程模 型进行转化的方法可以有效的减少理解g p u 编程模型的困难；而b a g h s o r k h i 、s h a n e a y o o 等提出的优化方法对本文有重要的指导作用。 1 2 2g p u 加速m d 5 破解 在传统高性能计算机上对带随机数的m d 5 算法的攻击有许多著名的研究，如 j t r ( j o h nt h er i p p e r ) 【2 2 】、d k b f 2 3 】等。 r y a nl i m 在文【2 钾中使用m p i 将j t r 并行化，使其可以在多处理器的机器上运 行，从而借助m p p 的性能优势在更短的时间内完成破解。j t r 支持标准和双精度 的d e s 、b s d i 扩展d e s 、f r e e b s dm d 5 、o p e n b s db l o w f i s h 、a f s 和w i n d o w s n tl a n m a nf o r m a t s 的破解。文中采用了任务包的方法实现了并行破解。如图1 3 所示，采用一个主机点，其余p 个处理器作为s l a v e 节点都获得大小相同的密钥组 合空间，从o 到p o s s i b l e s ( x ) 。一旦s l a v e # i ( i = l m 完成搜索，则返回给m a s t e r 节点。 l 觎l 极l 躬i l # p - 2l 批tl 柙l 0 p o s s i b l e s ( x ) 图1 3 任务包方法示意图 通过测试，在单c p u 平台上每秒可以产生11 2 4 个f r e e b s dm d 5 密钥，在双 第4 页 国防科学技术大学研究生院工程硕士学位论文 c p u 平台上每秒可以产生2 2 4 2 个f r e e b s dm d 5 密钥，在八个c p u 的平台上每秒 可以产生8 7 5 7 个f r e e b s dm d 5 密钥，基本呈线性的关系。 a d r i a nb o e i n g 等在文【2 5 】中指出许多标准密码学函数可以通过特殊的硬件进行 加速。以往这些硬件获取代价较高，只能被一小部分研究者使用。g p u 的出现改 变了这一状况，g p u 容易获得且价格相对低廉。文中使用c u d a 在n v i d i a g e f o r c e 9 8 0 0 g t x 上实现了m d 5 r c 4 算法，优化后的程序性能比原c p u 上运行的串行程 序提速近l o 倍。因此文中认为，计算密集型的算法如m d 5 和a e s 等可以在g p u 的加速下获得很高的性能。同时，文中还对当前使用g p u 加速a e s 算法的效果同 m d 5 的效果进行了比较，由于m d 5 操作的数据较a e s 更多，因此a e s 算法获得 了更高的性能。 g u a n g h u 等在文【2 6 】中设计和实现了基于c u d a 的m d 5 算法，并采用优化全 局存储访问等方法对得到的算法进行了优化。文中主要关注的是m d 5 算法应用在 高性能网络和存储系统中，这些系统对数据吞吐率要求较高。文末通过n v i d i a g e f o r c e9 8 0 0g t x + 加速的m d 5 与原程序在仅c p u 的平台上进行对比，发现随着 输入数据量的增加，g p u 的加速效果变得越来越明显。当输入数据为4 m 时，扇 出率为1 0 0 0 m b p s ，比仅c p u 平台提速近1 0 倍。 c h a n g x i nl i 等在文【27 j 中，在n v i d i a g e f o r c e9 8 0 0 g t xg p ul 。8 3 g h z 上实 现了m d 5 - - r c 4 加密算法。其执行结果与在a m ds e m p r o np r o c e s s o rl e 1 2 0 0c p u 2 1 2 g h z 上的执行结果相比，实现了3 至5 倍的加速。 通过对以上文献的了解，本文发现近年来使用g p u 加速m d 5 算法的研究非 常流行，并且也取得了较好的效果。由于m d 5 破解算法中仍然调用了多次m d 5 加密过程，因此这些研究对本文实现有重要的指导和借鉴意义。a d r i a nb o e i n g 等 人的研究指出在优化过程中需要特别关注存储单元的使用。此外，使用传统并行 算法实现的m d 5 攻击对本文工作也有参考意义，r y a nl i m 的研究指出对m d 5 的 攻击之间不需要相互通信，只需要控制密钥生成即可展开并行攻