试论des密码算法的彩虹攻击技术及其gpu实现

《试论des密码算法的彩虹攻击技术及其gpu实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、申请上海交通大学硕士学位论文DES密码算法的彩虹攻击技术及其GPU实现学校：上海交通大学院系：电子信息与电气工程学院班级：B0803391学号：1080339003硕士生：金铨专业：计算机系统结构导师Ⅰ：谷大武（教授）上海交通大学电子信息与电气工程学院2010年12月ADissertationSubmittedtoShanghaiJiaoTongUniversityfortheMasterDegreeofComputerScienceandTechnologyRAINBOWATTACKONDESWITHITSGPUIMPLEMENTATIONAuthor：JinQuanSpecialty:Co

2、mputerSystemandArchitectureAdvisor:Prof.GuDawuSchoolofElectronics,InformationandElectricEngineeringShanghaiJiaoTongUniversityShanghai,P.R.ChinaDecember,2010上海交通大学硕士学位论文摘要DES密码算法的彩虹攻击技术及其GPU实现摘要以DES为代表的对称密码是信息安全领域一种重要的密码体制，与公钥密码相比，对称密码计算代价低，算法相对简单，因此在工业界得到了广泛的应用。目前，针对对称密码的攻击方法除穷尽搜索外，主要包括差分分析和线性分析。然而，

3、由于实际中很难在相应密钥失效前，收集到大量的明-密文对，上述攻击极难在实际中得到应用。面对这些问题，学者们尝试各种方法。1980年，Hellman提出了著名的时空折中算法。从平均分析成本和现实可行性来看，时空折中比以往的方法有更大的威胁。2003年，Oechslin在原算法的基础上提出了彩虹表(Rainbowtable)密钥分析算法，获得了更好的分析性能。但是由于受当前PC机计算能力所限，彩虹表算法针对多比特数密钥(如大于等于56比特)的分析时间，仍然很难满足现实的需求。基于以上问题，我们设计了一种在图形处理器(GPU)上的彩虹表(Rainbowtable)密钥分析算法，主要是通过结合GPU单

4、指令多线程的特点改进了Oechslin的彩虹表算法，将预处理中彩虹链的计算分别映射到GPU的单个线程，并发地完成彩虹表的生成；并首次引入了预计算链这种新的数据结构，显著地提高了在线分析的效率。所使用的硬件平台GPUTeslaC1060相对于CPUCore2Duo2.8GHz，在运行速度方面，预处理(Pre-computation)提高了41.2倍(110M次DES加密每秒)，在线分析(OnlineAttack)提高了3.52倍。在此系统的基础上，用1.3GB的磁盘空间，平均2.73s的在线分第I页上海交通大学硕士学位论文摘要析时间以及46%的概率，成功获得了加密选择明文的40比特DES密钥。为

5、充分利用有限的内存空间，我们在GPU彩虹表算法的基础上，设计了一种新的彩虹表存储结构（简称瘦表），其原理是通过给每个EP增加一个ID的方式，使得SP能够在分析时生成，从而为每条彩虹链节约近(SP-ID)比特的空间。应用占位问题，我们进一步给出了较Hellman假警估算公式更为逼近的新方法，用于分析瘦表及相应单张彩虹表的假警增长趋势。实验表明，ID长度k取24比特长时，较单张彩虹表平均31%的成功率提高了14%，同时在假警数方面要比单纯地通过增加彩虹链长t的方法要低30%。关键词：GPU，时空折中，彩虹表，DES第II页上海交通大学硕士学位论文ABSTRACTRAINBOWATTACKONDES

6、WITHITSGPUIMPLEMENTATIONABSTRACTDESwasoneofthemostpopularblock-ciphersinthefieldofInformationSecurity.DEScanbeimplementedmoreeasilyatareasonablylowcost,comparingwiththepublic-keyciphers.Byfar,therearetwomainattackmethods,differentialcryptanalysisandlinearcryptanalysis,exceptfortheexhaustivekeysearch

7、.However,it’sdifficulttocollectenoughplain-cipherpairsbeforeitskeybecameexpired.In1980,HellmanpresentedthefirstandmostfamousTime-MemoryTradeoff(TMTO).Concerntotheanalyticalcostandfeasibilityofimplemen