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

Design and Optimized Implementation of Rainbow Table with GPU

作　　者：金铨[1] 谷大武[1] 赵建杰[2] 

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240 [2]上海交通大学信息安全工程学院,上海200240

出　　处：《上海交通大学学报》2011年第7期1006-1011,共6页Journal of Shanghai Jiaotong University

基　　金：教育部高校博士点基金项目(200802480019)

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

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

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]