上海交通大学学报

上海交通大学学报（自然版） ›› 2011, Vol. 45 ›› Issue (07): 1006-1011.

• 自动化技术、计算机技术 • 上一篇    下一篇

彩虹表密码分析算法的图形处理器优化设计与实现

金铨a，谷大武a，赵建杰b   

  1. (上海交通大学a. 电子信息与电气工程学院；b. 信息安全工程学院，上海 200240 )
  • 收稿日期:2010-09-28 出版日期:2011-07-29 发布日期:2011-07-29
  • 基金资助:

    教育部高校博士点基金项目（200802480019）

Design and Optimized Implementation of Rainbow Table with GPU

 JIN  Quan-a, GU  Da-Wu-a, ZHAO  Jian-Jie-b   

  1. (a.School of Electronic, Information and Electrical Engineering； b. School of Information Security Engineering, Shanghai Jiaotong University,Shanghai 200240, China)
  • Received:2010-09-28 Online:2011-07-29 Published:2011-07-29

摘要： 设计了一种在图形处理器(GPU)上的彩虹表密钥分析算法.结合GPU单指令多线程的特点改进了Oechslin的彩虹表算法，将预处理中彩虹链的计算分别映射到GPU的单个线程，并利用预计算链提高了在线分析的效率.所使用的硬件平台GPU Tesla C1060 相对于CPU Core2 Duo 2.8 GHz，在运行速度方面，预处理提高了41.2倍(每秒110×106次DES加密)，在线分析提高了3.52倍.在此系统上用1.3 GB的磁盘空间，平均2.73 s的在线分析时间以及46%的概率，成功获得了加密选择明文的40 bit DES密钥.

关键词: 图形处理器, 时空折中, 彩虹表, 数据加密标准

Abstract: This paper proposed a new implementation of Rainbow table algorithm on GPU. Utilizing the GPU’s powerful SIMT capacity, the algorithm greatly improves the performance of Rainbow chain generation by dispatching the pre-computation of Rainbow chain to each GPU thread and accelerates the execution efficiency of online attack through the newly introduced pre-computation chain. The running time of pre-computation on GPU (Tesla C1060) outperforms that on CPU (Core2 Duo 2.8 GHz) by 41.2 times, that is 110×106 times DES encryptions per second; and the running time of online attack, 3.52 times faster. Based on the new hardware system, we obtain the 40 bits keys of DES in 2.73 seconds on average with successful rate of 46% by using 1.3 GB hard disk space.

Key words: graphic processing unit(GPU), time-memory tradeoff, Rainbow table, data encryption standard(DES)

中图分类号: