基于完美彩虹表的检查点算法改进研究

摘要

本文对完美彩虹表下的检查点算法进行了研究和改进.时间存储折中攻击是由Hellman于1980年提出的一种适用于分组密码和哈希函数的算法.该算法具有可以用空间复杂度来换取时间复杂度的特点,然而由于链之间的碰撞,算法具有较高的误报率.其一个变种,Oechslin于2003年提出的彩虹表算法可以大幅减少碰撞的数量,从而提升效率.2005年,Avoine等人提出了另一种名为"检查点"的改进,该算法从另一个角度,即降低误报的影响来提升效率.然而,检查点的设置问题(数量和位置)仍未得到完全的解答.在本文中,我们对检查点算法在基于完美彩虹表的条件下进行研究,对检查点的设置进行理论分析,推导出最佳位置的计算式,并构造实验来检验最优选择的结果.在空间复杂度相当的条件下,相较于没有设置检查点的彩虹表,攻击时间可以减少10％到30％.