学位论文 > 优秀研究生学位论文题录展示

DES密码算法的彩虹攻击技术及其GPU实现

作　者: 金铨
导　师: 谷大武
学　校: 上海交通大学
专　业: 计算机系统结构
关键词: GPU 时空折中彩虹表 DES
分类号: TN918.1
类　型: 硕士论文
年　份: 2010年
下　载: 191次
引　用: 1次
阅　读: 论文下载

内容摘要

以DES为代表的对称密码是信息安全领域一种重要的密码体制,与公钥密码相比,对称密码计算代价低,算法相对简单,因此在工业界得到了广泛的应用。目前,针对对称密码的攻击方法除穷尽搜索外,主要包括差分分析和线性分析。然而,由于实际中很难在相应密钥失效前,收集到大量的明-密文对,上述攻击极难在实际中得到应用。面对这些问题,学者们尝试各种方法。1980年,Hellman提出了著名的时空折中算法。从平均分析成本和现实可行性来看,时空折中比以往的方法有更大的威胁。2003年,Oechslin在原算法的基础上提出了彩虹表(Rainbow table)密钥分析算法,获得了更好的分析性能。但是由于受当前PC机计算能力所限,彩虹表算法针对多比特数密钥(如大于等于56比特)的分析时间,仍然很难满足现实的需求。基于以上问题,我们设计了一种在图形处理器(GPU)上的彩虹表(Rainbow table)密钥分析算法,主要是通过结合GPU单指令多线程的特点改进了Oechslin的彩虹表算法,将预处理中彩虹链的计算分别映射到GPU的单个线程,并发地完成彩虹表的生成;并首次引入了预计算链这种新的数据结构,显著地提高了在线分析的效率。所使用的硬件平台GPU Tesla C1060相对于CPU Core2 Duo 2.8GHz,在运行速度方面,预处理(Pre-computation)提高了41.2倍(110M次DES加密每秒),在线分析(Online Attack)提高了3.52倍。在此系统的基础上,用1.3GB的磁盘空间,平均2.73s的在线分析时间以及46%的概率,成功获得了加密选择明文的40比特DES密钥。为充分利用有限的内存空间,我们在GPU彩虹表算法的基础上,设计了一种新的彩虹表存储结构(简称瘦表),其原理是通过给每个EP增加一个ID的方式,使得SP能够在分析时生成,从而为每条彩虹链节约近(SP-ID)比特的空间。应用占位问题,我们进一步给出了较Hellman假警估算公式更为逼近的新方法,用于分析瘦表及相应单张彩虹表的假警增长趋势。实验表明,ID长度k取24比特长时,较单张彩虹表平均31%的成功率提高了14%,同时在假警数方面要比单纯地通过增加彩虹链长t的方法要低30%。

全文目录

摘要  3-5
ABSTRACT  5-9
第一章绪论  9-14
  1.1 研究背景  9-10
  1.2 国内外研究进展  10-12
  1.3 研究内容及主要成果  12-13
  1.4 论文结构  13-14
第二章时空折中方法  14-25
  2.1 HELLMAN 时空折中算法  14-17
    2.1.1 预计算  14-15
    2.1.2 在线分析  15
    2.1.3 TMTO 曲线  15-16
    2.1.4 分析成功率  16-17
  2.2 彩虹表算法  17-20
    2.2.1 非完美彩虹表  17-19
    2.2.2 完美彩虹表  19-20
  2.3 统一折中方法  20-24
    2.3.1 时空数据折中方法  20-22
    2.3.2 时空密钥折中方法  22-24
  2.4 本章小结  24-25
第三章 GPU 并行编程相关知识  25-37
  3.1 GPU 并行编程概述  25-27
  3.2 GPU 体系结构  27-31
    3.2.1 线程模型  27-28
    3.2.2 微架构  28-31
  3.3 GPU 性能优化方法  31-35
    3.3.1 硬件特性相关优化  31-33
    3.3.2 软件特性相关优化  33-35
  3.4 本章小结  35-37
第四章彩虹表算法的GPU 优化设计与实现  37-48
  4.1 GPU 彩虹表算法的设计  37-40
    4.1.1 预计算  37-38
    4.1.2 在线分析  38-40
  4.2 彩虹表算法的GPU 优化  40-45
    4.2.1 并发线程数  40-42
    4.2.2 存储层次  42-45
    4.2.3 优化的实验结果  45
  4.3 DES 40 比特密钥分析实验  45-46
  4.4 DES 56 比特密钥分析代价估计  46-47
  4.5 本章小结  47-48
第五章瘦表及其性能分析  48-57
  5.1 瘦表生成算法  48-49
  5.2 瘦表性能分析  49-55
    5.2.1 在线搜索深度  49-50
    5.2.2 存储空间  50-51
    5.2.3 假警代价估计及分析  51-55
  5.3 与等规模单表的性能比较实验  55-56
  5.4 本章小结  56-57
第六章全文总结  57-59
  6.1 主要结论  57
  6.2 研究展望  57-59
参考文献  59-61
致谢  61-62
攻读硕士学位期间已发表或录用的论文  62-64

DES密码算法的彩虹攻击技术及其GPU实现

内容摘要

全文目录

相似论文