Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences  

作　　者：PENG Liqiang ZUO Jinyin HU Lei XU Jun 

机构地区：[1]State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences [2]University of Chinese Academy of Sciences [3]PLA Unit 95899 [4]School of Mathematical Science, Anhui University

出　　处：《Chinese Journal of Electronics》2014年第1期175-178,共4页电子学报（英文版）

基　　金：supported by the National Basic Research Program of China(No.2013CB834203);the National Natural Science Foundation of China(No.61070172,No.10990011);the Strategic Priority Research Program of Chinese Academy of Sciences(No.XDA06010702)

摘　　要：Two knapsack public key cryptosystems based on randomized knapsack sequences were proposed in2009 and 2011 respectively, where the secret knapsack sequence is transformed by secret modular linear transforms into one or three public randomized knapsack sequences with appropriate density. In this paper, we recover the secret modular linear transforms by simultaneous Diophantine approximation and propose secret key recovery attacks on these two cryptosystems. Practical attack experiments are done within one minute.Two knapsack public key cryptosystems based on randomized knapsack sequences were proposed in 2009 and 2011 respectively, where the secret knapsack se- quence is transformed by secret modular linear transforms into one or three public randomized knapsack sequences with appropriate density. In this paper, we recover the se- cret modular linear transforms by simultaneous Diophan- tine approximation and propose secret key recovery attacks on these two cryptosystems. Practical attack experiments are done within one minute.

关 键 词：Knapsack public key cryptosystem Si-multaneous Diophantine approximation LATTICE L^3 algo-rithm. 

分 类 号：TN918.4[电子电信—通信与信息系统]