基于随机背包的公钥密码

Public Key Cryptosystem Using Random Knapsacks

该文构造了一个背包型公钥密码算法。该背包公钥密码具有如下优点:加解密只需要加法和模减法运算,因此加解密速度快;该算法是基于随机背包问题而不是易解背包问题而构造的;证明了在攻击者不掌握私钥信息情况下该密码算法能抵抗直接求解背包问题的攻击,包括低密度攻击和联立丢番图逼近攻击等;证明了攻击者能够恢复私钥信息与攻击者能够分解一个大整数是等价的。分析表明,该算法是一个安全高效的公钥加密算法。

A knapsack-type public key cryptosystem is proposed.The proposed knapsack cryptosystem has the following advantages.The encryption and decryption only need addition and modular minus operations,so the encryption and decryption speed is high;The cryptosystem is constructed based on random knapsacks but not easy-to-solve knapsack problems;It is proven that if the secret key is not possessed by the attacker,the proposed cryptosystem can withstand the attacks launched by directly solving the underlying knapsack problem,including low-density attack and simultaneous Diophantine approximation attack;It is proven that the attacker can recover the secret keys if and only if he can factor a large integer.Analysis shows that the proposal is an efficient and secure public key encryption algorithm.