基于彩虹表的时间-存储折中攻击改进算法

杂凑函数是将任意长度的字符串映射到固定长度输出的函数,由于其具有单向性而被广泛的应用于口令认证.许多网站或服务器都使用杂凑函数来保存用户口令.时间-存储折中攻击是1980年由Martin Hellman提出的,它能够在有限的存储和计算能力的限制下,在可接受的时间内计算出常用的计算机口令.而Philippe Oechslin在2003年提出的彩虹表法极大地提升了时间-存储折中攻击的效率,此后在彩虹表法的基础上,大量改进算法被纷纷提出.本文提出了一种基于彩虹表的时间存储-折中攻击改进算法,它应用了概率统计的方法,能够在基本保证成功率的基础上大大提升搜索效率.即当成功率降低4.12%时,搜索时间降低86.21%,它是一种效率与成功率折中的算法.

Grain-v1的猜测确定新攻击方法

针对Grain-v1是否存在未知安全缺陷,提出了一种新的猜测确定攻击方法。利用内部状态转移特征和抽头位置关系,优先恢复其线性移位寄存器内部状态信息,并结合时间-存储-数据折中技术给出新的内部状态恢复攻击。结果表明:该攻击需要的数据复杂度为279bit密钥流,时间复杂度为286.3次算法加密,存储复杂度为280个160bit数据块。与已有的攻击方法相比,新攻击需要的时间复杂度更低。

一种求解背包问题的自适应算法

针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用2δ个处理机、O(ε2(n-δ)/2)的时间、O(2(n+δ)/2-ε)的空间求解背包问题(0≤δ≤n/5,1≤ε≤(n-δ)/4),根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。