破译一个新的背包公钥密码系统

BREAKING A NEW KNAPSACK PUBLIC KEY CRYPTOSYSTEM

1978年 Merkle 和 Hellman 提出了第一个基于背包问题的公钥密码系统.其后又提出了许多更复杂的基于背包问题的公钥系统(见[2]及其后所引文献).1982年以来提出了许多破译背包公钥系统的方法.这些方法虽然是针对两类系统即含超递增序列的背包系统和低密度背包系统而设计的.但由 Adlemorn 首先建议的用 Lenstra等发明的格基约化算法来攻击迭代背包系统是有一定普遍意义的.

Recently,He Jingmin and Lu Kaicheng devised a new knapsack public key cryptosystem.The system does not involve any superincreasing sequence of knapsack components.In ad-dition,it has a high density when the system parameters are properly chosen,and so is thoughtto be unbreakable by any existing methods.In this paper,a method for breaking the systemof He and Lu is given.By using this method,a solution of the private key can be found fromthe public key,with high probability,the calculated private key is exactly the private key ofthe system.In case they are not the same,the calculated private key can still be used for cor-rect decryption.