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

Attack Method for Non Super-increasing Sequence Knapsack Encryption Algorithm

作　　者：于志敏[1] 古春生[1] 景征骏[1] 蔡秋茹[1] 臧海娟[1] 

机构地区：[1]江苏技术师范学院计算机工程学院,江苏常州213001

出　　处：《计算机工程》2013年第5期136-139,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(61142007);江苏省"青蓝工程"基金资助项目(KYQ0900Z);江苏技术师范学院基金资助项目(KYY11055)

摘　　要：针对栗风永等人提出的非超递增序列背包加密算法(计算机工程与设计,2011年第2期),设计基于格攻击的2种攻击方法。方法 1构造维度为3的格,在其上应用LLL算法可直接恢复私钥,时间复杂度为O(n2)。方法 2采用低密度攻击,可以较大概率恢复明文,时间复杂度为O(n3lb(max(bi)))。实验结果表明,栗风永等人提出的算法是不安全的。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（n31b（max（bi）））. Experimental results show that the scheme by Li et al is insecure.

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

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]