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

关键词: 背包, 非超递增序列, 格攻击, 低密度攻击, 最短向量问题, LLL算法

Abstract: Aiming at non super-increment sequence knapsack encryption algorithm, this paper proposes two methods for attacking based on lattice. Method 1 can construct three dimensions lattice and utilize LLL algorithm to recover the private key directly with time complexity O(n2); Method 2 can utilize low-density attack to recover its plaintext with high probability and time complexity O(n3lb(max(bi))). Experimental results show that the scheme by Li et al is insecure.

Key words: knapsack, non super-increasing sequence, lattice attack, low-density attack, the Shortest Vector Problem(SVP), LLL algorithm

中图分类号: 

• TP309.2