對一個背包公鑰密碼的格攻擊

摘要:對一個新的基于MerkleHellman背包密碼和Rabin公鑰密碼的背包公鑰密碼算法進行了安全性分析。使用格規約算法求解一個聯立丟番圖逼近問題和一個二元整數線性規劃問題就恢復出了該密碼算法的部分密鑰。重構的部分密鑰可以解密任意密文。因此，該背包公鑰密碼算法是不安全的。

關鍵詞:公鑰密碼; 聯立丟番圖逼近; 整數線性規劃; 格規約

中圖分類號:TP3097文獻標志碼:A

文章編號:10013695(2010)04146603

doi:10.3969/j.issn.10013695.2010.04.073