非超递增序列背包加密算法的攻击方法

摘要

针对栗风永等人提出的非超递增序列背包加密算法(计算机工程与设计,201 1年第2期),设计基于格攻击的2种攻击方法.方法1构造维度为3的格,在其上应用LLL算法可直接恢复私钥,时间复杂度为O(∥).方法2采用低密度攻击,可以较大概率恢复明文,时间复杂度为O(n31b(max(bi))).实验结果表明,栗风永等人提出的算法是不安全的.