| 彩虹表密码分析算法的图形处理器优化设计与实现 |
| |
| 引用本文： | 金铨,谷大武,赵建杰.彩虹表密码分析算法的图形处理器优化设计与实现[J].上海交通大学学报,2011,45(7):1006-1011. |
| |
| 作者姓名： | 金铨 谷大武 赵建杰 |
| |
| 作者单位： | (上海交通大学a. 电子信息与电气工程学院；b. 信息安全工程学院，上海 200240 ) |
| |
| 基金项目： | 教育部高校博士点基金项目(200802480019) |
| |
| 摘 要： | 设计了一种在图形处理器(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密钥.
|
| 关 键 词： | 图形处理器 时空折中 彩虹表 数据加密标准 |
| 收稿时间： | 2010-09-28 |
Design and Optimized Implementation of Rainbow Table with GPU |
| |
| JIN Quana,GU Da-wua,ZHAO Jian-jieb.Design and Optimized Implementation of Rainbow Table with GPU[J].Journal of Shanghai Jiaotong University,2011,45(7):1006-1011. |
| |
| Authors: | JIN Quana GU Da-wua ZHAO Jian-jieb |
| |
| Institution: | (a.School of Electronic, Information and Electrical Engineering； b. School of Information Security Engineering, Shanghai Jiaotong University,Shanghai 200240, China) |
| |
| 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. |
| |
| Keywords: | graphic processing unit(GPU) time-memory tradeoff Rainbow table data encryption standard(DES) |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《上海交通大学学报》浏览原始摘要信息 |
| 点击此处可从《上海交通大学学报》下载免费的PDF全文 |
