Lattice attack on knapsack public key cryptosystem
对一个背包公钥密码的格攻击

This paper cryptanalyzed a knapsack public key cryptosystem which was constructed by using the Merkle-Hellman knapsack cryptosystem and the Rabin scheme. The attack recovered some partial of the secret keys by solving a simultaneous Diophantine approximation problem with lattice reduction algorithms and a bivariate integral linear programming problem. The recovered partial secret keys were utilized to decrypt any ciphertext. Therefore, the knapsack public key cryptosystem is insecure.