论文部分内容阅读
以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%。